Jesper Dramsch , , read in 4 minutes

The first grid, so be prepared for off-by-one errors!

What is Advent of Code?

In this little series, I want to write about the thought processes I have behind solving the puzzles presented in Advent of Code.

During the Advent of Code small coding puzzles are presented with varying levels of difficulty. They're always Christmas-themed text puzzles where you help elves out of some mess to save the holidays. The puzzles are deliberately ambiguous to not bias puzzlers into a certain solution, they always have an example input in the text to explain some details and an input file for each day that comes in the form of a text file you can download. The solution is a simple number or a string you enter, which is checked by the website automatically. After you finish part 1, part 2 unlocks, which is a variation on part 2. This can be a little twist on part 1 or a large twist that changes the problem formulation into a problem that would take brute force solutions to compute longer than the heat death of the universe would take.

Find my solutions here: github.com/JesperDramsch/advent-of-code

These descriptions won't be a perfect narrative, but rather how I think about these problems and where I see different solutions. I apologise for the possibility of rambling!

The example input

Ah yes, grids.

30373
25512
65332
33549
35390

Grid are always tricky. Do you just go for numpy? Lists of lists?

The implementation

I decided on lists of lists, as there was no larger benefit to using numpy yet.

I knew I had to check the rows and the columns for visibility. So I figured, I could flip the list of lists on the side to easily iterate through the lists.

def flip(grid):
    return [list(x) for x in zip(*grid)]

But that wasn't the solution I ended up using.

I started out using enumerate to go through the lists and get an index. But I also had to check each list backwards, which turned out to be a nightmare with this approach.

Mind you, I built a list of lists with all boolean set to False called visibility:

visible = [[False for _ in row] for row in grid]

I figured this way I could do multiple passes on the visibility checks, which I ended up abandoning, but the visibility list was useful anyways.

I keep a list of the maximum heights for the rows and the columns each, which resets between the forward and backward pass.

for reverser in [False, True]:
    max_height_row = [-1 for _ in grid[0]]
    max_height_col = [-1 for _ in range(len(grid))]

So instead of flipping the grid, I just did some indexing shenanigans and simply did that work in a for loop over the grid.

    for q in range(len(grid)):
        for qq in range(len(grid[0])):
            if reverser:
                i = len(grid) - q - 1
                ii = len(grid[0]) - qq - 1
            else: 
                i, ii = q, qq

Then I could simply update the visibility list and the max heights.

                cell = grid[i][ii]
                if cell > max_height_row[ii]:
                    visible[i][ii] = True
                    max_height_row[ii] = cell
                if cell > max_height_col[i]:
                    visible[i][ii] = True
                    max_height_col[i] = cell

Simple enough, it was more of a question of making the indices work.

Part Deux

I'm sure there is a smart way to do this, but I simply iterated out from every point in the grid.

def check_trees(grid):
    for i in range(len(grid)):
        for ii in range(len(grid[0])):
            yield viewing_distance(grid, i, ii)

for each entry, I check up down right left and return the score directly. I'm making use of the dynamic of for, break, and else in Python:

for i, right in enumerate(range(lon+1, len(grid[0]))):
    if grid[lat][right] >= grid[lat][lon]:
        out.append(i+1)
        break
else:
    out.append(len(grid[0]) - lon - 1)

Error Log

  • if cell > max_height[ii]: TypeError: '>' not supported between instances of 'str' and 'int' forgot to change the variable name in function
  • Tried to do some fancy indexing in a row, but realised I'm not checking the list forward and backward. Will just have to do indexing normally without enumerate to keep the code tidy.
  • Forgot to remove print statements before the big input. What a wall of text!
  • visible = check_visibility(flip(grid), flip(visible)) NameError: name 'flip' is not defined Removed flip() thinking it wasn't needed, as I don't need to flip anymore.
  • data = """30373 IndentationError: unexpected indent accidentally hit tab
  • My logic in part 2 seems faulty. Something isn't increasing numbers how I expected it to. May be the enumerate(range(...)). Have to investigate.
  • UnboundLocalError: cannot access local variable 'i' where it is not associated with a value forgot to remove an i
  • Found the error, I was starting ON the tree of the tree house so all viewing distances were seen as 0... Off-by-one errors. The bane of my coding existence.
  • out.append(i+1) UnboundLocalError: cannot access local variable 'i' where it is not associated with a value tried quick and dirty. Didn't work.