It couldn’t last forever—spending consecutive days writing about my progress in the Advent of Code took too much time and the rest of my life knocked on the door. In this post, I will try to update you quickly on days five and six.
On day 5 we had to assist an unfortunate handbook printer to get the updated pages in the correct order. Being magic-elven stuff, the proper order is not the natural increasing order of integers, but a custom order defined by number pairs – e.g. 43|12 means that page 43 has to be followed immediately by page 12. But stuff is not that simple, the order relationship is not linear like a–b–c, but may branch, so to give you an idea, after a may come either b or d and then are both followed by c.
The puzzle input is split into two parts, the first defines page orders, and the second lists groups or pages that must be printed.
The first part is not too hard – you have to select the groups that are in the correct order (according to the defined orders) and sum the middle number of the sequence (all the sequences are conveniently composed of an odd number of integers).
I found the second part very hard – you have to pick the sequences that are not in order and reorder them. Again the answer to the puzzle is the sum of the numbers in the middle of the reordered sequences.
My approach was to turn the group of pages into a set. Then pick a page at a time, try all the available successors, and continue until I run out of pages (solution found) or I can’t find a successor to the last page.
The code ran slowly though completed in an acceptable time. Surely I missed some optimization – keeping the list of the resulting sequence in order causes the penalty of scanning the entire list each time I need the last item. I could keep the finding order and then reverse it last (although we need the middle item which is the middle item regardless of the ordering).
And it didn’t help that when writing the code I didn’t find a way to shortcut to the end of iteration when a solution was found.
Also, I lost a lot of time because I failed to notice that HashMap.get returns an option. The code compiled and didn’t complain with some surprise on my side. It happens that in Scala:
Some(1).contains("")
Is considered valid, it triggers no warning and always returns false.
So I won, but it left me with a bitter taste. As usual, you can find my code here. (I don’t report anything here ’cause I feel a bit ashamed)
Day 6 introduced a new type of puzzle, I call this category the “walkers” puzzle, you are provided with a board, and some movement rules and you have to figure out something by moving something else on the board.
So to sneak into a warehouse (always searching for the chief historian), you need to know the path followed by a guard. The guard will turn clockwise 90° every time she faces an obstacle. The board has some obstacle squares, so if you mark all the squares where the guard patrolled, how many free blocks are there?
The approach I followed is the standard top-down with the help of a couple of classes I defined in my utils –
def step1( data: List[String] ) : Int = var board = decode(data) val start = findGuard( data, '^' ) countVisited( board, start )
I skip over the decode function since it just converts a List of Strings in a SimpleGrid[Cell], where Cell is defined as:
enum Cell: case Empty, Obstacle
Also, the findGuard function is uninteresting, it just locates the Guard initial position marker (‘^’) in the map. countVisited is where the fun begins:
def countVisited( board: Board, start: Position) : Int =
val visitMap = SimpleGrid[Boolean]( board.width, board.height, false )
@tailrec
def loop( guard: Position, facing: Facing, visit: Set[CellVisit] ) : Unit =
val current = CellVisit(guard, facing)
if (visit.contains(current))
()
else
visitMap.setAt(guard, true)
val newVisit = visit + current
val next = nextPosition( guard, facing )
if( board.isValidPosition( next ) )
board.getAt(next) match
case Cell.Obstacle =>
val newFacing = rotateCw( facing )
loop( guard, newFacing, newVisit )
case Cell.Empty =>
loop( next, facing, newVisit )
loop( start, Facing.North, Set.empty )
println(s"${toString(visitMap)}")
visitMap.count( x => x )
I wrote the usual recursive loop, at each step, I check if the guard already was on this cell with the same facing (meaning that I would end up here again, there is a loop). If not I mark this place as visited and compute the next position. If the next position contains an obstacle, then I change facing and recurse. Otherwise, the next position is free, so I move the guard there and recurse.
The second part requires us to travel through time and set one obstacle so that the guard moves along a loop never leaving her path.
The first idea I got was to put an obstacle at a time on each square of the board and trace the path. But wouldn’t make too much sense since many squares are never crossed. So I decided to modify the loop of the first part to temporarily insert an obstacle before every move, trace the resulting path, and check for a loop.
This was fast and the code computed the right result on the example but failed on the actual puzzle input.
After checking my code in and out, I re-read the instructions and got the problem. You cannot insert an obstacle in the position of the guard. This is because in doing so the guard would have walked a different path. So in order to place the temporary obstacle you need to check both for an empty square and that this square has not already been visited (regardless of facing) by the guard.
The core of this solution lies in the following code:
def loop( guard: Position, facing: Facing, visit: Set[CellVisit], count: Int) : Int =
val current = CellVisit(guard, facing)
val newVisit = visit + current
val next = nextPosition(guard, facing)
if (board.isValidPosition(next))
board.getAt(next) match
case Cell.Obstacle =>
val newFacing = rotateCw(facing)
loop(guard, newFacing, newVisit, count)
case Cell.Empty =>
if( next != start && visit.forall( next != _.position ) )
board.setAt( next, Obstacle );
val result = patrol( guard, facing, visit )
val newCount = result match
case LeftArea => count
case Loop => count+1
board.setAt( next, Empty );
loop(next, facing, newVisit, newCount )
else
loop(next, facing, newVisit, count )
else
count
loop(start, Facing.North, Set.empty, 0)
This is pretty close to countVisited, but you can see the placing and then removal of the obstacles in the Cell.Empty branch (board.setAt( next, Obstacle )). The patrol function just performs the standard patrolling and returns whether the guard entered a loop or left the area.
In solving this puzzle the utils class proved to be an advantage, reducing the overall time and letting me focus on the core of the problem to solve.
That’s all for the last two days. Happy advent-coding.