Euler88.scala

import scala.util.control.TailCalls._

object Main extends App {
  
  def findSumProduct(factors: Int): Option[Long] = {

    def recurseStartNumber(level: Int): Int = if (level < factors - 2) 1 else 2

    def inner(level: Int, currentNumber: Int, sum: Long, product: Long, knownMin: Option[Long]): TailRec[Option[Long]] = {

      val newSum = sum + currentNumber
      val newProduct = product * currentNumber

      def continue(newMin: Option[Long]) = inner(level, currentNumber + 1, sum, product, newMin)

      val noBetterMinimumPossible = {
        val minProduct = newProduct * Math.pow(currentNumber, (factors - level - 1))
        val minSum = newSum + currentNumber * (factors - level - 1)
        
        knownMin.map(minProduct >= _).getOrElse(false) || minProduct > minSum
      }

      if (newProduct > newSum || noBetterMinimumPossible) done(knownMin) else {
        if (level == factors - 1) {
          // Last level
          if (newProduct == newSum) done(Some(newProduct))
          else tailcall(continue(knownMin))
        } else {
          val newLevel = level + 1
          val newStartNumber = 
            if (currentNumber > 1) currentNumber
            else recurseStartNumber(newLevel)

          tailcall(inner(newLevel, newStartNumber, newSum, newProduct, knownMin)) flatMap { maybeResult =>
            val newMin = (knownMin zip maybeResult).map(z => Math.min(z._1, z._2)).headOption 
              .orElse(knownMin)
              .orElse(maybeResult)
            tailcall(continue(newMin))
          }
        }
      }
    }

    inner(0, recurseStartNumber(0), 0, 1, None).result
  }

  val count = new java.util.concurrent.atomic.AtomicInteger(0)

  val numbers = 2.to(12000).par map { k =>
    println(s"${count.getAndIncrement()} / 12000 - k = $k")

    findSumProduct(k).getOrElse(sys.error(s"Couldn't find sum product for k = $k"))
  }

  println(s"Sum: ${numbers.distinct.sum}")
 
}