Helping Elves One Star at a Time

That period of the year has finally come. That cozy winter feeling of cold outside the window, while busy waiting for the holidays. As a long-standing tradition that started last year, this is the time I help Elves prepare for Xmas in the Advent of Code.

Each day of Advent, the Advent of Code, proposes a couple of puzzles that can be solved by writing some code. There are no constraints on the language or the approach since the result of the puzzle is an integer number. Also, there is no deadline, you can continue working on the puzzles after Xmas. And there is no prize, you just know you did the right thing helping the elves and Santa.

I decided to face the challenge armed with my tried and true Scala knowledge and a lot of patience from my family who let me indulge in spending some time a day in this activity.

The first puzzle was not hard, you have a sequence of number pairs, and you need to sort independently and sum all the distances.

To save a bit of time, I recovered last year’s driver:

 @main
def main(): Unit = {
  val filename = "src/data.in"
  val source = Source.fromFile(filename)
  val lines = source.getLines().toList
  source.close()
  println(s"step1: ${step1(lines)}")
  println(s"step2: ${step2(lines)}")
}

The input file is dutifully named (by me) “data.in”. I read the file in one pass and converted the lines into a list of strings. Then I call the two steps, meaning the two parts of the puzzle.

Step 1, first task is to convert inputs into something we can work on – from a List[String] to a List[Array[Int]]:

def step1( data: List[String] ) : Int =
  lazy val in = data.map(_.split("\\s+").map(_.toInt))
  ...

The funny-looking argument of the split function – "\\s+" – means to split the string on the regular expression – one or more spaces. This is needed because the text for the puzzle uses 3 spaces to separate the first from the second column.

Now we need to sort the two columns independently and paste them together in their new order. I used map to extract the first and the second columns and zip to paste the sorted sequence back in one List[(Int,Int)] :

  lazy val compare = in.map(_(0)).sorted.zip(in.map(_(1)).sorted)

Now, it’s time map again to compute the distance and sum to sum everything together:

  compare.map(p => abs(p._1 - p._2)).sum

Run the code and get the solution. As already noted in my past analysis of this game, elegance is not a goal, you need the right number and if it is right it is right regardless of how you got it. This is to say that I am not very satisfied with my solution – sometimes I use arrays for pairs and sometimes I use a more fitting tuple.

Nonetheless, the code is compact and straightforward, with no condition, no control statement, no recursion, just plain transformation of data.

Time to get to the second puzzle. As usual, things get a bit more complex – now you need to seek numbers from the first column into the second, counting how many times they appear and multiplying the count by the sought number. The result is the sum of all these products.

That’s not much I can reuse from the first part, but for the transformation of the input text. Then it is worth splitting the input into two lists:

def step2( data: List[String] ) : Long =
  lazy val in = data.map(_.split("\\s+").map(_.toInt))
  lazy val seeks = in.map( _(0) )
  lazy val targetsAll = in.map( _(1) )

(I used Long as the return type because I feared the result could overflow an Int).

To avoid scanning targetsAll for every item in the seeks list, I decided to convert the targets into a hash map where keys are the target numbers and values are the count of how many times they appear in the target list. I implemented this conversion with a function:

def countTargets(ints: List[Int]) : HashMap[Int,Int] =
  def loop( ints: List[Int], old: HashMap[Int,Int] ) : HashMap[Int,Int] =
    ints match {
      case Nil =>
        old
      case h :: tail =>
        loop( tail, old.updated( h, old.getOrElse(h,0)+1) )
    }

  loop( ints, HashMap.empty )

Being functional, I opted for a recursive function. This pattern is quite common: the real recursive function is a member function (loop here) called with “augmented” arguments to the outer function. This allows you to define the initial condition (in this case, the empty hash map).

Another point worth noticing is the hash map is immutable, which means that I cannot modify it by adding one to the value for the given key, The updated operation produces an updated version of the hash map with the desired value. This may seem inefficient and possibly is but not as much as you would expect, thanks to some compiler magic and clever management of the memory (and it hasn’t been a problem on my PC).

Type converted, it is trivial to map each value of the first column into the product we need and sum everything:

  val targets = countTargets( targetsAll )
  seeks.map( x => (x*targets.getOrElse(x,0)).toLong ).sum

And that’s it.

Again I have the impression something could have been done better – more precisely I guess the countTargets function could have been replaced with maps and/or folds or other similar operations. But I got the result and a little time left to write this article. This is the full code for my solution.

How was your solution?