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?
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] 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)): if reverser: i = len(grid) - q - 1 ii = len(grid) - 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.
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)): 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
else in Python:
for i, right in enumerate(range(lon + 1, len(grid))): if grid[lat][right] >= grid[lat][lon]: out.append(i + 1) break else: out.append(len(grid) - lon - 1)
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 definedRemoved
flip()thinking it wasn't needed, as I don't need to flip anymore.
data = """30373 IndentationError: unexpected indentaccidentally 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 valueforgot to remove an
- 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 valuetried quick and dirty. Didn't work.