Project Euler 11: Largest product in a grid

projecteuler11.scala

package ysl.p11

object Direction extends Enumeration {
  type Direction = Value
  val Horizontal, Vertical, Diagonal = Value
}

class LargestProductInGrid(val grid:List[List[Int]]) {  
  import Direction._

  val width:Int = grid(0).length
  require(grid.forall( _.length == width ))
  val height:Int = grid.length
  
  var direction:Direction = Direction.Horizontal
  private val count = 4
  
  def elems(dir:Direction = direction, count:Int = count)(x:Int, y:Int):List[Int] = {
    if (count == 0) 
      Nil 
    else
    grid(y)(x) :: (dir match {
          case Horizontal => elems(dir, count-1)(x+1,y)
        case Vertical => elems(dir, count-1)(x, y+1)
      case Diagonal => elems(dir, count-1)(x+1, y+1)
    })
  }
  
  // TODO: 1) for generator 활용, 2) pattern matching
  def largestProduct:Int = {
    def _largestProduct(dir:Direction):Int = {
      var result:Int = 0
      val limit_x = dir match {
        case Horizontal | Diagonal => width - count
        case Vertical => height - 1
      } 
      val limit_y = dir match {
        case Vertical | Diagonal => height - count
        case Horizontal => width -1
      }  
      
      for(y <- 0 to limit_y; x <- 0 to limit_x) {
        val product = elems(dir)(x,y).reduceLeft((p, elem) => p*elem)
        if (product > result) result = product 
      }
      println( Direction, result)
      result
    }
    Direction.values.map( _largestProduct(_)).max 
  }
}

projecteuler11_test.scala

package ysl.p11

import org.scalatest.FunSpec

class LargestProductInGridSpec extends FunSpec {

  // project euler 11 20*20 matrix 
  val matrix_large: List[List[Int]] = List(
    List(8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8),
    List(49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0),
    List(81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65),
    List(52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91),
    List(22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80),
    List(24, 47, 32, 60, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50),
    List(32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70),
    List(67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21),
    List(24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72),
    List(21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95),
    List(78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92),
    List(16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57),
    List(86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58),
    List(19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40),
    List(4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66),
    List(88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69),
    List(4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36),
    List(20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16),
    List(20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54),
    List(1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48))

  val matrix_small = List(
      List(1,2,3,4),
      List(1,2,3,4),
      List(1,2,3,4),
      List(1,2,3,4)
      )
    
  describe("특정 위치에서 각 방향의 연속된 원소 가져오기") {
    val grid = new LargestProductInGrid(matrix_large)

    // partially applied functions
    val horizontalElems = grid.elems(Direction.Horizontal, 4)_
    val verticalElems = grid.elems(Direction.Vertical, 4)_
    val diagonalElems = grid.elems(Direction.Diagonal, 4)_

    it("(0,0)위치에서 가로, 세로, 대각선 방향으로 4개의 원소 가져오기") {
      assert(horizontalElems(0, 0) == List(8, 2, 22, 97))
      assert(verticalElems(0, 0) == List(8, 49, 81, 52))
      assert(diagonalElems(0, 0) == List(8, 49, 31, 23))
    }
    
    it("fetch four horizontally sequential elememts from position 16, 16)") {
      assert(horizontalElems(16, 16) == List(40, 62, 76, 36))
      assert(verticalElems(16, 16) == List(40, 74, 23, 89))
      assert(diagonalElems(16, 16) == List(40, 4, 5, 48))
    }
  }
  
  describe("연속된 원소의 곱하기 중 최댓값 구하기(small set)") {
    val grid_small = new LargestProductInGrid(matrix_small)
    
    it("최댓값은 4^4 == 256") {
      assert(grid_small.largestProduct == 4 * 4 * 4 * 4)
    }
  }
  
  describe("연속된 원소의 곱하기 중 최댓값 구하기(large set)") {
    val grid_large = new LargestProductInGrid(matrix_large)
    
    it("20 * 20 행렬 내 연속된 네 자리수 곱의 최댓값은?") {
      println("Largest product in 20*20 matrix is %d".format(grid_large.largestProduct))
    }
  }
}