Day 4 of the Advent of Code presents you with two new puzzles based on the word search puzzle idea. For some reason, you are teleported to the Ceres Elven Station (that made an appearance in AoC 2019), but there’s nothing for you to see here (yet) – not even the chief historian we looking for. So a small elf asks for your help to solve her word search.
Being Xmas elves the word you have to look for is “XMAS”, it can be written straight or reverse and can be written in any direction left, up left, up, up right, right down right, down and down left.
My first thought was to try to trim down a bit the search space. So if I search for XMAS and SAMX (XMAS reversed), I can only look right and never left and the same holds for the other directions. In the end, instead of 8 directions, I explore just 4.
I cheated a bit by reusing:
- a Position case class, and
- a Grid component
I developed last year for AoC. It just simplifies the access. Knowing about the direction to go, I employed scala 3 enums to define the directions:
enum Direction:
case Right,
Down,
UpRight,
DownRight
And then a function that from a position and a direction gives me the next position in that direction:
def next( p: Position, d: Direction ): Position =
d match {
case Direction.Right => p.copy( x = p.x+1 )
case Direction.Down => p.copy( y = p.y+1 )
case Direction.UpRight => p.copy( x = p.x+1, y = p.y-1 )
case Direction.DownRight => p.copy( x = p.x+1, y = p.y+1 )
}
Going top down, my step function is
def step1( data: List[String] ) : Int = val table = SimpleGrid[Char](data,x => x) count( "XMAS", table )
SimpleGrid wants a function to convert from a Char (as given in the input data) to the parameter type. Since I wanted a Grid of Char, the identity function is fine (I tried to use _, which to me meant identity function, but for some unknown reasons, didn’t work, and I had to replace it with the explicit form).
Unknowing of the second part of the puzzle, I left the string to search as a parameter.
In the count function, I sweep the grid and count in every position how many times I can find the string:
def count( s: String, table: SimpleGrid[Char] ): Int =
val w = for( y <- 0 until table.height ) yield
for( x <- 0 until table.width) yield
countPosition( Position(x,y), s, table )
w.flatten.sum
This part employs one of my favorite Scala constructs – for / yield. Basically, it behaves like a map, but you can see it as a view to have a for loop to produce a value. E.g. for( x < 0 until 10 ) yield x produces an iterable sequence with numbers from 0 to 10 (excluded).
In my code, I create a duplicate of the grid where each position contains how many times the string is found at that position. flatten and sum do the trick to get a single value.
countPosition is rather unimaginative –
def countPosition( p: Position, s: String, table: SimpleGrid[Char]) : Int = countDirection( p, s, table, Direction.Right ) + countDirection( p, s, table, Direction.Down ) + countDirection( p, s, table, Direction.UpRight ) + countDirection( p, s, table, Direction.DownRight )
I’m sure that something better could have been done, but I had no idea but this.
def countDirection( p: Position, s: String, table: SimpleGrid[Char], d: Direction ) : Int =
val straight = matchDirection( p, s, table, d )
val reverse = matchDirection( p, s.reverse, table, d )
(straight,reverse) match {
case (true,true) => 2
case (true,false) => 1
case (false,true) => 1
case (false,false) => 0
}
we are approaching the bottom – now we just scan one direction and check first for straight string and then for reverse string. I had matchDirection returning a boolean value and since there is no standard way to convert a boolean into an integer, I opted for the match statement. Again I expect this can be done more elegantly, but.. hey it’s a speed challenge!
And eventually here is the main gear of the device –
@tailrec
def matchDirection(p: Position, s: String, table: SimpleGrid[Char], d: Direction) : Boolean =
s match {
case "" => true
case s if !table.isValidPosition(p) => false
case h +: _ if h != table.getAt(p) => false
case _ +: tail => matchDirection( next(p,d), tail, table, d )
}
Yes, this is recursive (tail-recursive) so to match one character at a time. If we have no more characters to match, then the entire string is matched. If this position is not a valid grid position then there is no match. Also, there is no match if the current character is different from the first character of the string. Otherwise, let’s go to the next character and the next position.
To the more attentive readers, it won’t go unnoticed that (head :: tail) deconstructor works only for List and other classes but not for String. That’s true, indeed I had to write my version:
object +: {
def unapply(s: String): Option[(Char, String)] =
s.headOption.map {
(_, s.tail)
}
}
With this, I was able to compute to answer to the first part.
The second part, unexpectedly seemed easier than the first part. You have to find on the grid all the occurrences of the word MAS (straight or reverse) that form an X.
I didn’t see much to recycle from part 1, but I would scan for ‘A’ in all positions of the grid but the outer border (so that I don’t have to check for valid positions). Then I check the edgy points of the cross – if one is ‘M’ the other has to be ‘S’ or vice-versa.
Pending this gorgeous plan, I set course to solve part two:
def step2( data: List[String] ) : Int = val table = SimpleGrid[Char](data, x => x) countXmas( table )
countXmas still use the same sweep developed for count, but with reduced loops:
def countXmas(table: SimpleGrid[Char]): Int =
val w = for( y <- 1 until table.height-1 ) yield
for( x <- 1 until table.width-1 ) yield
countPositionXmas( Position(x,y), table )
w.flatten.sum
countPositionXmas has to check if Position(x,y) is the center of a MAS cross –
def countPositionXmas( p: Position, table: SimpleGrid[Char] ): Int =
if( table.getAt(p) == 'A' )
val ul = table.getAt( next( p, Direction.UpLeft ))
val dr = table.getAt( next( p, Direction.DownRight ))
val uldr = (ul,dr) match {
case ('M','S') => 1
case ('S','M') => 1
case _ => 0
}
val ur = table.getAt( next( p, Direction.UpRight ))
val dl = table.getAt( next( p, Direction.DownLeft ))
val urdl = (ur,dl) match {
case ('M','S') => 1
case ('S','M') => 1
case _ => 0
}
urdl*uldr
else
0
I have to admit that the outer if doesn’t make me happy at all. Possibly I could have filtered positions in a list, to avoid this, but… yes it is a time challenge.
To make this work I had to add directions to the Direction enumeration (Left, UpLeft, Up, and DownLeft) and change the next function to process these new directions. I don’t bother you with the details because they are exactly as you imagine.
The ending product is a way to express the “and” condition – to be a MAS cross, you need M and S on one diagonal and again on the other.
The challenge level up to now has been quite low. I remember the first day quite intensive last year, so I expect the difficulty to go up steeply in a few days.
Any suggestion to improve my Scala style? See you on day 5!