I thought Day 6 of Advent of Code was a pretty interesting problem. The first part was relatively straightforward. You are given a grid containing empty space an obstructions and the location of a guard who start facing north. The guard moved forward until hitting an obstruction and then will always turn right and continue on his path. Eventually the guard moves off the grid. The code I wrote is on github. To maintain the guard’s current state I used a type with position and direction. I also defined a type to use if the guard’s walk was interrupted either by an obstruction, Collision, or going off the grid, OffMap.

The first part was to count how many locations on the grid the guard occupied before moving off the grid. To accomplish this, I just saved the coordinates of the guard’s position as he ot she moved. I could then just count the number of items in the set. This proved fairly simple, and I was ready for part 2.

In part 2 the idea is to find the locations where, by adding an obstruction, you can cause the guard to move in a loop and never exit the grid. It is here where I started making a few assumptions which were incorrect.

For my first stab at this, I decided to find places where the guard crossed his or her previous path and put an obstruction there which would cause him or her to retrace his or her steps. This successfully found only 3 out of 6 of the obstruction locations in the test data as it is possible to put the guard into a loop by placing obstructions at locations which do not fit this criterea. I then took some time to try to think of a way to select only relevant portions of the grid on which to try putting an obstruction.

For my second attempt I put an obstruction ahead of every step the guard made which did not already have an obstruction, and then checked to see if this would result in a loop. I’m sure this is not optimal, but it was not terribly slow either. Unfortunately I got a number that was too high! This really confused me for a while, and I decided to rerun each grid from the beginning with each obstruction I found, and indeed I found many of these obstructions did not actually result in infinite loops, so where did I go wrong?

It turns out that the issue I was having was that in some cases I was placing obstructions along paths the guard had already tred in a different direction. These obstructions were already checked earlier along the path, and would have disrupted the path prior to the point I was currently checking. It is likely that the guard would not end up along the path he or she was currently walking had there been an obstruction in that location. When I decided to skip checking locations where the guard had already been, I ended up getting the correct number of obstructions.

Although likely inefficient, this code ran in less than 2 seconds, so it is not terrible, still I hate the feeling of tryping a solution in the web site and getting the message that your number is too high.