プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q02:数列の四則演算。

Q: 1000~9999で、数字の各桁の間に四則演算の演算子を最低１つは入れて計算し、元の数の桁を逆から並べた数字と同じになるものを求める。

def calc(expr:List[Either[Char, Int]]):Int = {
  def recur(expr:List[Either[Char, Int]], acc:List[Int]):Int = {
    expr match {
      case Nil => acc.sum
      case Right(x)::xs => recur(xs, x::acc)
      case Left('+')::(Right(xs)::xss) => recur(xss, xs::acc)
      case Left('-')::(Right(xs)::xss) => recur(xss, (-xs)::acc)
      case Left('*')::(Right(xs)::xss) => recur(xss, (xs*acc.head)::acc.tail)
      case _ => throw new Exception()
    }
  }
  recur(expr, Nil)
}

def gen(num:Int):List[List[Either[Char, Int]]] = {
  val parsed = num.toString.map(_.asDigit)
  var comb:List[List[Either[Char, Int]]] = List(List(Right(parsed.head)))
  def left(c:Char):Either[Char, Int] = Left(c)
  def right(n:Int):Either[Char, Int] = Right(n)
  for(n <- parsed.tail) {
    comb = comb.flatMap{ c =>
      List(c.init++(right(c.last.right.get*10 + n)::Nil),
        c++(left('+')::right(n)::Nil),
        c++(left('-')::right(n)::Nil),
        c++(left('*')::right(n)::Nil))
    }
  }
  comb
}

(1000 to 9999).flatMap { num =>
  val reverse = num.toString.reverse
  if(gen(num).withFilter(_.exists(_.isLeft)).map(calc).exists(_.toString == reverse)) Option(num)
  else None
}

#calcは引数に数値もしくは演算子のリストを受け取り、計算結果を返す。

ex.)

calc(List(Right(1), Left(+), Right(2)))
> 3

#genは引数に数値を受け取り、その数値の各桁と演算子のバリエーションの配列を返す。

ex.)

gen(12)
> List(List(Right(12)),
        List(Right(1), Left(+), Right(2)),
        List(Right(1), Left(-), Right(2)),
        List(Right(1), Left(*), Right(2)))