1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に(for, while省略)

Prob.scala

// http://www.softantenna.com/wp/software/5-programming-problems/
object Prob {

  def p1(list: List[Int]) = {
    def addRec(list: List[Int], acc: Int): Int = list match {
      case Nil     => acc
      case x :: xs => addRec(xs, acc + x)
    }
    addRec(list, 0)
  }

  def p2[P, A <: P, B <: P](alist: List[A], blist: List[B]): List[P] =
    alist.zip(blist).flatMap { case (a, b) => List(a, b) }

  val fib: Stream[BigInt] = BigInt(0) #:: BigInt(1) #:: fib.zip(fib.tail).map { case (a, b) => a + b }
  def p3 = fib take 100

  def p4(list: List[Int]) = list.permutations
    .map(_.map(_.toString))
    .map(_.mkString)
    .map(BigInt(_))
    .max

  sealed trait Elem
  case class Term(value: Long) extends Elem
  sealed trait Operator extends Elem
  case object Plus extends Operator
  case object Minus extends Operator
  case object Join extends Operator

  /**
   * {{{
   * scala> import Prob._
   *
   * scala> join(List(Term(1), Join, Term(2), Join, Term(3)))
   * res1: List[Elem] = List(Term(123))
   * }}}
   */
  def join(exp: List[Elem]): List[Elem] = {
    def joinRec(reversedExp: List[Elem]): List[Elem] = reversedExp match {
      case (t1: Term) :: Join :: (t2: Term) :: es =>
        joinRec(Term((t2.value.toString + t1.value.toString).toLong) :: es)
      case Nil     => Nil
      case e :: es => e :: joinRec(es)
    }
    joinRec(exp.reverse).reverse
  }

  /**
   * {{{
   * scala> import Prob._
   *
   * scala> calc(List(Term(1), Plus, Term(2), Join, Term(3), Join, Term(4), Minus, Term(5)))
   * res1: Long = 230
   * }}}
   */
  def calc(exp: List[Elem]): Long = {
    def calcRec(exp: List[Elem]): Long = exp match {
      case Nil                                 => 0L
      case Term(v) :: Nil                      => v
      case Term(v1) :: Plus :: Term(v2) :: es  => calc(Term(v1 + v2) :: es)
      case Term(v1) :: Minus :: Term(v2) :: es => calc(Term(v1 - v2) :: es)
      case _                                   => 0L
    }
    calcRec(join(exp))
  }

  /**
   * {{{
   * scala> import Prob._
   *
   * scala> expToString(List(Term(1), Plus, Term(2), Join, Term(3), Join, Term(4), Minus, Term(5)))
   * res1: String = 1 + 234 - 5
   * }}}
   */
  def expToString(exp: List[Elem]): String = exp.map {
    case Term(v) => v.toString
    case Plus    => " + "
    case Minus   => " - "
    case Join    => ""
  }.mkString

  val operators = Stream(Plus, Minus, Join)

  def p5 = for {
    o1 <- operators
    o2 <- operators
    o3 <- operators
    o4 <- operators
    o5 <- operators
    o6 <- operators
    o7 <- operators
    o8 <- operators
    exp = List(
      Term(1), o1,
      Term(2), o2,
      Term(3), o3,
      Term(4), o4,
      Term(5), o5,
      Term(6), o6,
      Term(7), o7,
      Term(8), o8,
      Term(9))
    res = calc(exp)
    if res == 100
  } println(expToString(exp))
}