Elves’ Advent Quest – Day 2

After warming up with the first day’s puzzle, here we are with the second day. The bar is still low, but not as low as yesterday. With the coordinates decoded in the last puzzle, everyone runs to the nearest location which happens to be a nuclear plant (for reindeer needs). While we are here the elves running the plant ask for your help to analyze some data looking for anomalies.

Yes, we are in a hurry to look for the chief historian elf, but we also have 25 days to fill with puzzles. So here we go.

We are given a list of integer number sequences. Each sequence has to be analyzed to determine whether it is valid or invalid. To be valid it must be either increasing or decreasing, and the distance of two consecutive numbers must be within the 1-3 range. The result of the puzzle is the number of valid reports.

With the driver from yesterday, I started implementing the step1 function and went top-down:

def step1( data: List[String] ) : Int =
  data.map(toReport).count(isReportValid)

The first pass is to convert the string containing the sequence of ints into a report, then count how many of them satisfy the validity condition. How nicely Scala fits the logical steps you would go for solving this puzzle.

A Report is a sequence of numbers, I used the Array[Int] type¹ and the toReport function is promptly coded as:

def toReport( s: String ) : Array[Int] =
  s.split( ' ' ).map( _.toInt )

Magic is done by split (this time numbers are separated by a single space) and map. Time to write the isReportValid function. Here I spent some time trying to understand if there was an elegant math solution that could avoid conditionals, but the inspiration just yielded a blank slate. So I went for the dumb approach of splitting the two cases – increasing sequence and decreasing sequence:

def isReportValid( r: Array[Int] ) : Boolean =
  if( r(0) == r(1) )
    false
  else if( r(0) > r(1))
    isDecreasingReportValid( r )
  else
    isIncreasingReportValid( r )

If the first two items are the same, then this is not increasing or decreasing, so the sequence is not valid at all. The greater-than relationship between the first two items must be preserved for all the other items, so I can check isDecreatingReportValid or isIncreasingReportValid.

def isIncreasingReportValid(r: Array[Int]): Boolean =
  r.sliding(2, 1).map(x => x(1) - x(0)).forall(x => x >= 1 && x <= 3)

Sliding creates a sliding window from the array so that each pair of adjacent values can be compared. Forall checks that the property is valid for all the elements of the sequence.²

Now isDecrementingReportValid is pretty identical, save for the order of x(1) and x(0). That begs me because I try to live by the DRY design principle. Now, with the wisdom of hindsight, I think I could have reversed the decreasing sequence to check if it was a good increasing sequence. But time is a scarce resource, so I tested and run the program to get the answer to the puzzle that was indeed correct and unlocked the second part.

The second part follows the tradition of adjusting the form of the fist part by pretending the elves formulating the puzzle forgot something. So the real truth is that a single problem can be tolerated and the sequence considered correct. In other words, if removing one item in the sequence the resulting sequence is valid, then the entire sequence has to be considered valid.

My first idea was to start checking the validity adjacent pair by adjacent pair and discarding an item on the go it it failed the validity and then continue. This can be intuitive and easy doing manually, but it is not so obvious to implement – an increasing sequence could become a decreasing sequence after removing the second item. Also discarding the item is not compatible with the sliding window. It is true that every problem can be solved with a fold, but the function of the fold would be rather complex.

So I decided yet again for a dumb approach – if the isReportValid fails, I remove one item and retry. And continue like this until the sequence is considered valid, or I tried all the possible sequences by removing one item in the original sequence.

Additional benefit is that I leverage the isReportValid function as is.

def isReportAlmostValid( r: Array[Int]) : Boolean =
  def loop( n: Int, r: Array[Int]) : Boolean =
    if( n < r.length )
      val front = r.take(n)
      val item = r(n)
      val back = r.drop(n+1)
      isReportValid( front ++ back ) || loop( n+1, r )
    else
      false

  isReportValid( r ) || loop( 0, r )

def step2( data: List[String] ) : Int =
  data.map(toReport).count(isReportAlmostValid)

I found that “isReportAlmostValid” was a good name for this function. As for yesterday puzzle, I use a recursive function that accepts the position of the item to remove and the array. This is really a loop from 0 to the length of the sequence.

To punch a hole in the sequence I use take to extract the first n items from the array and get the back part of the array by dropping n+1 items. The two parts are then combined with the ++ array operator.

This may not be the fastest solution, but it succeeds as soon as the validity is found.

Yet again my concerns for performance was unbased, since the function ran in no time on my PC.

And that’s all. Here is all the code. Waiting for the next puzzle.

1. I chose Arrays, even knowing that Arrays are not the favorite functional programmers’ vector types (they are fond of lists, as proven by LISP). But until the first part of the puzzle, there was no specific reason to choose something else. ↩︎
2. Guess what happens when you apply forall to an empty sequence… My wrong assumption made me fail one of the exercises of Functional Programming in Scala. ↩︎