Project Euler: Problem 32

Euler0032.scala

package euler.zerosum

object Euler0032 {
  /**
   * [1..9]の順列によって得られる9桁の数を2箇所で区切って得られるx,y,zの3数が
   * x*y=zをみたす桁数の組み合わせ(digit(x), digit(y), digit(z))は
   * {(1, 4, 4), (2, 3, 4)}のいずれか
   *
   * (∵)
   * 1桁*3桁、2桁*2桁の演算は高々4桁、また、
   * 1桁*5桁、2桁*4桁、3桁*3桁の演算は少なくとも5桁以上になる
   * よって 4 < digit(x)+digit(y) < 6
   */

  val NINE_DIGIT_NUMS = List("1", "2", "3", "4", "5", "6", "7", "8", "9").permutations

  def main(args: Array[String]) {
    println(NINE_DIGIT_NUMS.foldRight(List(0))(findPandigitalProducts(_, List(1, 2), _)).sum)
  }

  private def findPandigitalProducts(nineDigitNumber: List[String], positions: List[Int], dst: List[Int]): List[Int] = {
    positions.foldRight(dst)((position, products) => {
      val product = nineDigitNumber.drop(5).reduceLeft(_ + _).toInt
      val multiples = nineDigitNumber.take(5).splitAt(position)
      val multiplicand = multiples._1.reduceLeft(_ + _).toInt
      val multiplier = multiples._2.reduceLeft(_ + _).toInt

      if (multiplicand * multiplier == product && !products.contains(product)) {
        product :: products
      } else {
        products
      }
    })
  }
}