P93. Scala로 풀어본 Arithmetic Puzzle

P93 (***) An arithmetic puzzle.

Given a list of integer numbers, find a correct way of inserting arithmetic signs (operators) such that the result is a correct equation. Example: With the list of numbers List(2,3,5,7,11) we can form the equations 2-3+5+7 = 11 or 2 = (3*5+7)/11 (and ten others!).

리스트로 주어진 수의 사이에 '=' 를 넣어 양 쪽 식의 값이 같게 되는 경우를 찾는 문제다.

List(2, 3, 5, 7, 11)을 입력했을 때 답의 일부는 아래와 같다.

2 = (3 - (5 + (7 - 11))) (2 * (3 - 5)) = (7 - 11) ((2 - (3 - 5)) + 7) = 11

함수를 일반 자료형처럼 사용할 수 있다는 점을 기억하면

한 값과 나머지 값으로 재귀호출해 Combination를 구하는 26번 문제와 아주 비슷하다.

특이 사항으로는 값을 계산하기 위한 순서, 그러니까 ( )로 표기되는 순서를 생각해야 한다는 것이다.

그 두가지 외에는 오히려 답보다 답을 '출력'하기 위한 방법을 고민해야 했다.

좀 더 쉬운 경우로 먼저 생각해 보자. 

List(1, 3, 2)를 입력받는다고 하자. 1 = List(3, 2) List(1, 3) = 2 이렇게 두 부분으로 나눌 수 있다. List(3, 2)는 ( 3 + 2 ), ( 3 - 2 ), ( 3 * 2 ), ( 3 / 2 ) 네가지로 나눌 수 있다. List(1, 3)은 ( 1 + 3 ), ( 1 - 3 ), ( 1 * 3 ), ( 1 / 3 ) 네가지다. 답은 1 = ( 3 - 2 )임을 쉽게 알 수 있다.

조금 더 어려운 경우를 생각 해 보자.

List( 1, 3, 2, 4 )를 입력받는다고 하자. 1 = List( 3, 2, 4 ) List( 1, 3 ) = List( 2, 4 ) List( 1, 3, 2 ) = 4 List( 3, 2, 4 )의 경우는 3 [+, -, *, /] List( 2, 4 ) List ( 3, 2 ) [+, -, *, /] 4  두가지 경우로 나눌 수 있다. 다시, List( 3, 2, 4 )는  List( 2, 4 )의 답에 첫 번째 요소 3을 각 연산으로 계산한 결과와 List( 3, 2 )의 답에 마지막 요소 4를 각 연산한 결과, 두가지 경우의 합이다. 리스트에 두 개의 값이 있는 경우는 위와 같으므로 생략한다.

앞서 말했듯, P26과 아주 비슷하다.

식을 왼쪽 식이 될 값의 리스트와 오른쪽 식이 될 값의 리스트로 나누어 각 경우의 조합을 만들어 계산하면 된다.

스칼라로 구현하면 아래와 같다.

/**
  * @since 2017-02-04
  */
class ArithmeticPuzzle {

  /**
    *  함수명과 함수를 위한 케이스 클래스.
    * @param name 함수의 이름. toString 메소드에서 사용한다.
    * @param function 함수
    */
  case class ArithmeticFunction(name: String, function: (Int, Int) => Int) {
    def apply(left: Int, right: Int): Int = function(left, right)
    override def toString: String = name
  }

  /** 기록된 함수로 계산한 결과 케이스 클래스.
    * @param value 계산 결과
    * @param str 지금까지 함수를 이용해 계산한
    */
  case class CalcResult(value: Int, str: String) {
    override def toString: String = str
  }

  // +, -, *, / 각 연산들
  val arithmeticFunctions = List(ArithmeticFunction("+", _ + _),
                                 ArithmeticFunction("-", _ - _),
                                 ArithmeticFunction("*", _ * _),
                                 ArithmeticFunction("/", _ / _))

  /**
    * 양 쪽 값을 입력받아 가능한 계산 결과를 만들어 내는 메소드.
    * @param leftValues 왼쪽 값들
    * @param rightValues 오른쪽 값들
    * @return 왼쪽 값과 오른쪽 값으로 만들 수 있는 계산 결과들
    */
  private def calcResults(leftValues: List[CalcResult],
                          rightValues: List[CalcResult]): List[CalcResult] = (leftValues, rightValues) match {
    case (_, Nil) => Nil // 왼쪽으로 값이 모두 넘어간 경우 재귀호출 하지 않음.
    case (Nil, rv::Nil) =>  // 오른쪽 값 하나만 있는 경우 그 값을 그대로 리턴.
      List(rv)              // 재귀호출 할 때 왼쪽 값을 Nil로 시작하기 때문.
    case (lLst, rLst@rh::rt) =>
      val result = for{ lv <- calcResults(Nil, lLst)         // 왼쪽 값으로 재귀호출
                        rv <- calcResults(Nil, rLst)          // 오른쪽 값으로 재귀호출
                        func <- arithmeticFunctions           // 가능한 연산들
                        if rv.value != 0 && func.name != "/" } // 0으로 나누는 경우를 제외함.
                   yield CalcResult(func(lv.value, rv.value), s"( $lv $func $rv )")

      // 현재 단계에서 가능한 결과를 모두 구하고 오른쪽 값을 왼쪽 값으로 재귀호출한다.
      result ::: calcResults(lLst :+ rh, rt)
  }


  /** 답을 구하는 메소드
    * @param lst 숫자 리스트
    * @return 구한 결과들
    */
  def solve(lst: List[Int]): List[String] = {

    /** 왼쪽에 들어가는 숫자들로 만든 값과 오른쪽에 들어가는 숫자들로 만든 값이
      * 일치하는 결과를 리턴하는 메소드.
      *
      * @param leftFormula 왼쪽 식에 들어가는 숫자들
      * @param rightFormula 오른쪽 식에 들어가는 숫자들
      * @return 왼쪽 식과 오른쪽 식이 같은 결과들
      */
    def solveRecu(leftFormula: List[Int], rightFormula: List[Int]): List[String] = (leftFormula, rightFormula) match {
      case (_, Nil) => Nil
      case (lLst, rLst@rh::rt) =>
      val result = for { lv <- calcResults(Nil, lLst.map(v => CalcResult(v, v.toString)))
                         rv <- calcResults(Nil, rLst.map(v => CalcResult(v, v.toString)))
                         if lv.value == rv.value} yield s"${lv.str} = ${rv.str}"
      result ::: solveRecu(lLst :+ rh, rt)
    }
    solveRecu(Nil, lst)
  }

}

계산의 순서와 중간 값을 기록하기 위한 case class와 

String에 기록하기 위한 함수의 이름과 식을 가지고있는 case class를 만들었다.

또, 이 문제는 for문을 사용해야 편하다. flatMap과 map을 겹쳐 사용하는 방식으론 훨씬 어렵고 복잡해진다.

문제를 풀 때는 자연스럽게 풀었는데, 이 글을 작성하기 전 다시 풀어보니 오히려 생소했던 문제다.

내가 이전에 어떻게 이런 생각을 했는지 의문스럽다...