Just some grain rain.
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
When I saw today's example input, I was worried!
498,4 -> 498,6 -> 496,6 503,4 -> 502,4 -> 502,9 -> 494,9
But my parser of "lists of lists" already worked on this and then I just needed to split and convert the coordinates to integers.
This hoenstly felt pretty straight-forward.
I implemented a dictionary with the given values, but ignored air. In the same step I also got the maximum depth.
Then I just used a while loop to drop the sand grains down to their position with three if statements checking for the middle, left and right.
Then I just repeated that until the first grain dropped below the maximum depth.
def sand_grain(grid, max_depth): loc = complex(500) while loc.imag < max_depth + 1: if loc + 1j not in grid: loc += 1j elif loc - 1 + 1j not in grid: loc += -1 + 1j elif loc + 1 + 1j not in grid: loc += 1 + 1j else: grid.add(loc) return grid return False
In part 2, I extended this logic with a floor:
def sand_grain(grid, max_depth, floor=None): loc = complex(500) if floor is not None: max_depth = floor while loc.imag < max_depth + 1: if loc.imag + 1 == floor: grid.add(loc) return grid ...
This allowed me to not assume a width of the stone floor, but simply used an additional logic step.
I wasn't happy with the dictionary implementation, the deep if structure and using x,y when complex numbers would work.
The refactor is already live and a little cleaner.
The part 2 is still fairly slow, and there is a way to calculate it as triangles, but we have to subtract the negative space under horizontal parts and that's a bit of work.
Well... that worked out alright!
- Not an error, but I did get a wrong intermittent result, when I forgot to change
range(min(b,y), max(b,y) + 1):
if not grid and start in grid: TypeError: argument of type 'bool' is not iterablewant to make it work with the existing function, but messed up one return.
- Wrong answer for example part 2, but that was just a off-by-one error in the floor.