There are plenty of programming languages and, of course, Xmas elves have their own. Although your main goal is still to find the Chief Historian, we are now in a warehouse, historian minions are wandering around looking for their boss and we are tasked to fix the computer1.
This puzzle seemed a bit easier than the first two days, but I found it somewhat underspecified. You have to scan a text for patterns like “mul(n,m)” with n and m integers. For each pattern multiply n by m and sum all the products together.
My instinct prompted me to solve using bash. A grep -o extracts all the matching “mul([0-9]+,[0-9]+),” then a sed replaces mul(n,m) with +n*m. Last, we feed everything to bc.
But my mission is to solve with Scala, so I dig into regexp documentation. The idea to solve the puzzle is to compute the sum of products line per line and then sum everything:
def step1( data: List[String] ) : Int = data.map( computeProducts ).sum
The function to compute the sum of products is based on regular expression:
import scala.util.matching.Regex def computeProducts( t: String ) : Int = val pattern: Regex = "mul\\(([0-9]+),([0-9]+)\\)".r pattern.findAllMatchIn( t ).foldLeft( 0 )( (s,m) => s+m.group(1).toInt*m.group(2).toInt)
To improve the performance I could have built the Regex beforehand, avoiding rebuilding it every time the computeProducts function is called. But the problem is negligible. To extract matching strings you need to enclose the relevant parts of the pattern in parenthesis. I made sure to capture the first and second operands in this way.
The findAllMatchIn method iterates over the argument string to consider all the possible matches. Since it spits out an Iterator, I can chain a foldLeft that performs the sum of the product. It is just a bit of conversion verbosity, but the function is straightforward.
The first part is done, now it is time to tackle the second part.
This is a bit harder (as expected), because it adds some semantics to the language – everything is enclosed by a “don’t()” – “do()” pair has to be ignored. i.e. all the valid mul statements within that pair do not concur to the grandtotal.
The specifications just say that you start considering mul statement, but doesn’t specify:
- whether don’t / do pair split into the adjacent lines has to force the ignore muls or not;
- whether don’t / do are always paired or the sequence may end with a don’t.
Oddly enough I had some issues with authentication and the first time I completed the puzzle the second point above was not a problem, since the sequence ended with a do, while the second time I got exactly that case.
I decided that line break is not to be considered a restart condition for don’t/do, so I joined together all the lines. Then, rather than parsing the input to handle the two states (consider muls and don’t consider them), I opted for removing the sequence “don’t().*do()” so to reuse my computeProducts function I wrote for the first part of the puzzle –
def step2( data: List[String] ) : Int =
val all = data.mkString("")
val valid = removeDonts(all)
computeProducts(valid)
The main problem in removeDonts (set aside looking for regexp documentation), is that the regexp “don’t().*do()” must not be greedy, otherwise it will wipe out everything from the first “don’t()” to the last “do()”. The trick is to put a “?” after the “*”. This appears to be a standard for regexp.
Another problem is that parenthesis is used for grouping expressions. I tried to escape them as I did in the first part, but for some reason, it didn’t work (possibly the problem was elsewhere), so I employed the trick of putting them as a single character of a set: [(] and [)] –
def removeDonts( t: String ) : String = val pairPattern: Regex = "don't[(][)].*?do[(][)]".r val allButLast = pairPattern.replaceAllIn(t,"") val lastPattern: Regex = "don't[(][)].*?$".r lastPattern.replaceAllIn(allButLast,"")
I have to run the removal twice – first to remove everything between pairs of don’t/do, and then to remove from the last don’t (if present) to the end of the string.
As usual, you can find my solution on gitlab.
In the end, this puzzle was mostly about flexing regular expression muscles, so not that fun to solve. Another approach would have been to write a parser. I suspect it would have been somewhat more complex and time-consuming and I’m not sure how much of the first part solution could have been reused for the second part.
I’m not sure for how long I can keep up with solving the puzzle and posting the commented solution on my blog, so if I miss a day you know why.
How is your advent of code going?
- I’m sure this rings a bell – so you are a programmer, right? You work with computers, right? Please fix mine. ↩︎