Ok this one seems a bit easier! Finally <3
Some counting and some network shuffling.
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
Ok, so we parse a list of lists again and see what's happening!
2,2,2 1,2,2 3,2,2 2,1,2 2,3,2 2,2,1 2,2,3 2,2,4 2,2,6 1,2,5 3,2,5 2,1,5 2,3,5
This is fairly simple and will absolutely not scale for part 2.
I set up a dictionary with counts of 6 sides for every cube.
Then I use
itertools.combinations to do pairwise combinations and subtract matching sides.
def check_neighbours(data): for pair in combinations(data, 2): diffs = (abs(a - b) for a, b in zip(*pair)) if sum(diffs) == 1: data[pair] -= 1 data[pair] -= 1 return data
That's all. Just a final sum and we have the solution.
So this one is a bit more involved.
I was considering using something like scipy or scikit-image to close the holes.
But we've been working with
networkx for a bit in AOC, especially with the neat tricks in Day 12.
The Boundary section shows that we can go for edges or nodes.
So we need a cube around the lava.
We don't have a 2D grid graph, but we can just use
nx.grid_graph with arbitrary dimensions.
def steam(data): min_x, max_x, min_y, max_y, min_z, max_z = find_extents(data) min_all, max_all = min(min_x, min_y, min_z), max(max_x, max_y, max_z) cube = nx.grid_graph(dim=[range(min_all - 2, max_all + 2)] * 3)
Then we need a copy of the cube. And hole it out with our lava.
hole = cube.copy() hole.remove_nodes_from(data.keys())
Then we want to remove all the air pockets, which means we'll keep the connected components surrounding the lava, chiseling away the holey bits in the center.
We'll keep the largest component, which is the outside.
lava = max(nx.connected_components(hole), key=len)
And then we can look back to the Boundary part and get the edge between the full cube and the hole left by the lava.
return nx.edge_boundary(cube, lava)
The biggest part was getting the extent of the cube, to reduce the computational cost here.
- Made a logic error, where I thought a single dimension has to be offset by one to be a neighbour. No idea how I had that error in my mind.
cube = nx.grid_graph(dim=(range(min_x-2, max_x+2), range(min_y-2, max_y+2), range(min_z-2, max_z+2)) SyntaxError: '(' was never closedjust autocomplete things.
KeyError: (-2, -2, -2)oops. wrong minimum