Embedded Files
Day 15
Solution - Part 1
Solution - Part 1
Solution - Part 2
Solution - Part 2
Today was arguably the most interesting puzzle so far! A lot of things going on, and a lot to look into - that's why this update comes so late, and I felt sick :(
This is yet another grid problem (making me think an implementation puzzle is coming up soon). For Part 1, I instinctually did a BFS - again in a similar fashion to previous days. A few things to note is that the runtime was still a little long at around 5 seconds. I also set t to be 1e99; 1x10^99. For the purposes of this puzzle, this is essentially infinity and easier to write than just spamming in 9s on the keyboard. I also fell into the trap of thinking that you could only move right and down, based off the example. Thankfully, this did not impact my result to part 1 and probably ended up decreasing the runtime!
Part 2 was clearly going to be harder - a simple BFS would not suffice given the drastic increase of graph size. A much smarter algorithm, such as A* or Dijkstra's would be needed here. I chose the latter because I knew it better (using NetworkX would make solving both parts of the puzzle significantly easier though - it has a built in function for both of these algorithms!). However, I did not actually know how to implement a priority queue in Python, so there was a delay whilst I scrambled to find some examples of "python dijkstra" on the internet. I saw an implementation using just a list, and then sorting it after every iteration to imitate the heap, but this had a longer runtime. This time, I realised that you could go in all 4 directions in the graph, and not just right or down! The clever bit for this puzzle was working out the values of the new graph without actually extending it. This is what the 'd' function above does. It finds the value of that coordinate, but in the original input. Then it adds numbers to reach what the real value should be. Then it mods the value by 9 - but to preserve the fact that 9 is still a valid number, I have to take away one from the value, mod it, then re-add that one. Trust me - the maths works out!
Now to code a NetworkX solution and cry about how easy it could have been....
** bonus networkx **
** bonus networkx **
Right, so this solution is not that much shorter (if at all) than the previous one, and the runtime is slightly slower! NetworkX does not seem the best way to solve this unless you are extremely fluent in it - programming your own Dijkstra could be faster! An issue I encountered whilst writing this was making the graph undirected (100% my fault), which normally wouldn't matter given the nature of the puzzle, but the problem is that most of the paths would be 'overwritten' in the nested for loops hence yielding incorrect weights and thus an incorrect answer! My part 2 solution using NetworkX;
Page updated
Google Sites
Report abuse