Euler14.scala

object Solution {

  import scala.io.Source

  def chain(y: Int, c: Int): Int = {

    if (y == 1) c
    else if (y % 2 == 0) chain(y / 2, c + 1)
    else chain(3 * y + 1, c + 1)

  }

  def calculate(n: Int, max: Int, maxVal: Int): Int = {

    if (n == 1) maxVal
    else {

      val c = chain(n, 1)

      if (c > max) calculate(n - 1, c, n)
      else calculate(n - 1, max, maxVal)

    }
  }

  def main(args: Array[String]) {
    for (ln <- Source.stdin.getLines().drop(1)) {
      println(calculate(ln.toInt, 0, 0))
    }
  }
}


object NearOptimizedSolution {

  import scala.io.Source

  def chain(y: Long, map: scala.collection.mutable.Map[Long, Long],
            stack: scala.collection.mutable.Stack[Long],
            c: Long): Long = {

    if (y == 1) {
      c
    } else {

      val x = map.getOrElse(y, 0L)

      if (x != 0) {

        x + c - 1

      } else {

        if (y % 2 == 0) {

          stack.push(y/2)
          chain(y / 2, map, stack, c + 1)

        } else {

          stack.push(3*y + 1)
          chain(3 * y + 1, map, stack, c + 1)
        }
      }
    }
  }

  def calculate(n: Long,
                map: scala.collection.mutable.Map[Long, Long],
                stack: scala.collection.mutable.Stack[Long],
                max: Long, maxVal: Long): Long = {

    if (n == 1) maxVal
    else {

      val x = map.getOrElse(n, 0L)
      val c = if (x == 0) {
        val c = chain(n, map, stack, 1)
        map(n) = c

        stack.reverse.zip(c - 1 to 1L by -1).foreach { elem =>
          map += elem
        }
        stack.clear()
        c

      } else {
        x
      }

      if (c > max) calculate(n - 1, map, stack, c, n)
      else calculate(n - 1, map, stack, max, maxVal)

    }
  }

  def main(args: Array[String]) {

    val map = scala.collection.mutable.Map[Long, Long]()
    val stack = scala.collection.mutable.Stack[Long]()

    for (ln <- Source.stdin.getLines().drop(1)) {
      println(calculate(ln.toLong, map, stack, 0, 0))
    }
  }
}