Scala: fun with Lists

So, I’m slowly working my way though some of the programming exercises at Project Euler as a means of learning scala (and hopefully a little bit of FP at the same time).
Problem #11 is my most recent success, and it’s highlighted a number of interesting points. In brief, the problem provides you with a 20×20 square of 2-digit integers, and asks for the largest product of any 4 adjacent numbers in any direction (up, down, left, right, diagonally). Kind of like a word-search, but with extra maths.

For no better reason than the afore-mentioned desire to get a bit more acquainted with a functional style of programming, I chose to implement it with no mutable state. I’m not sure if that was really sensible or not. It led to a solution that’s almost certainly less efficient, but potentially simpler than some of the other solutions I’ve seen.

So, step one: Give that we’re going to represent the grid as a List[List[Int]], let’s see if we can get the set of 4-element runs going horizontally left-to-right:

    def toQuadList()= {
      def lrQuadsFromLine(line: List[Int], accumulator: List[List[Int]]): List[List[Int]] = {
        if (line.length < 4)
          accumulator
        else
          lrQuadsFromLine(line.tail, accumulator :+ line.slice(0, 4))
      }
      data.flatMap(line => lrQuadsFromLine(line, List.empty))
    }

(“data” is the List[List[Int]] representing the grid). Here we define a recursive function that takes a List[Int], obtains the first 4-number run (line.slice), adds it to an accumulator, and then pops the first item from the list and calls itself with the remainder.
Then we just call flatMap() on the original List-of-Lists to obtain all such quadruples. We could call Map, but that would give us a list of lists of quadruples – flatMap mushes it down into one list.
It would be nice to find a way to make the if/else go away, but other than just transliterating it into a match, I can’t see a way to do it.

Given that list, finding the largest product is trivial.

   def findMaxProduct = data.map((x: List[Int]) => x.reduce(_ * _)).max

- take each Quadruple in turn and transform it into a single number by multiplying each element with the next. Then call .max to find the largest.

So now we can do one of the 6 directions. However, a bit of thought at this point can save us some time: the Right-to-Left result is guaranteed to be the same as the left-to-right, since multiplication doesn’t care about order (the set of quadruples will be the same in each direction). Similarly, the downwards result will be the same as the upwards one.

Next time-saver: Calculating the downwards result is the same as rotating the grid by 90 degrees and then calculating the left-to-right result. So we just need a rotate function, and we get the vertical results for free:

   def rotate90Deg() = {
      data.head.zipWithIndex.map((t) => data.map((row: List[Int]) => row(t._2)).reverse)
    }

Doing this without mutable state took me some pondering, but the solution is reasonably concise. Doing zipWithIndex on an arbitrary row of the grid (I used .head because it’s easy to access) gives us an iterator with an index number in, so we can now build up a List containing the _n_th element from each of the original lists. (The outer map() iterates over the columns in the grid, the inner one over the rows in the grid))

So now we have the horizontal and vertical totals, we need to do the diagonals. It would be nice if we could once again re-use the left-to-right quadruple-finding code, so we need to get the grid into a form where going left to right gets the sequences that would previously have been diagonals. We can do this by offsetting subsequent rows by one each time, the rotating; like this:

1,2,3
4,5,6
7,8,9

?,?,1,2,3
?,4,5,6,?
7,8,9,?,?

7,?,?
8,4,?
9,5,1
?,6,2
?,?,3

You can see that the horizontal sequences are now the original diagonals. Initially, I started using Option[Int] for the items in the grid, so I could use None for the “question marks”. However, after more time than it ought to have taken me, I realised that using zero for those would work perfectly, as any zero in a quadruple will immediately set that quad’s product to zero, thus excluding it from our calculation (which is what we want).
The function to do the offseting is still rather complex, but not too bad (it owes a lot to the recursive toQuadList function above:

    def diagonalize() = {
      def shiftOneRow(rowsRemaining: List[List[Int]], lPad: List[Int], rPad: List[Int], rowsDone: List[List[Int]]): List[List[Int]] = {
        rowsRemaining match {
          case Nil => rowsDone
          case _ => {
            val newRow: List[Int] = lPad ::: rowsRemaining.head ::: rPad
            shiftOneRow(rowsRemaining.tail,
              lPad.tail,
              0 :: rPad,
              rowsDone ::: List(newRow))
          }
        }
      }
      shiftOneRow(data, List.fill(data.size)(0), List.empty, List.empty)
    }

We define a recursive function that takes a list of rows yet to be padded, a list of zeros to pad the left-hand-side with, another for the right-hand-side, and an accumulator of rows already padded. As we loop through, we remove from the remaining rows, add to the done rows, remove from the left-padding, and add to the right padding. It kind of feels like there ought to be a neater way to do this, but I’m not quite sure what yet.

To get the “other” diagonals, just flip the grid left-to-right before diagonalizing it.

Once that’s done, all that remains is to glue it together. Because I’ve been thinking in OO for so long, I chose to wrap this behaviour in a couple of classes; one for the list-of-quadruples, and one for the grid itself. Then I can finish the job with:

 println(
      List(new Grid(data).toQuadList.findMaxProduct,
      new Grid(data).rotate90Deg.toQuadList.findMaxProduct,
      new Grid(data).diagonalize.rotate90Deg.toQuadList.findMaxProduct,
      new Grid(data).flipLR.diagonalize.rotate90Deg.toQuadList.findMaxProduct).max)

Chris May : 26 Jun 2011 00:01 |  Comments (0) |  Report a problem