Scalaで"1時間以内に解けなければプログラマ失格となってしまう5つの問題"をやってみた

今更感ありますが、タイトルの通りです。元ネタはこちら。詳しくはこちらをどうぞ。

問題１

説明の必要はないですよね。

object Problem1 {
  def sumByWhile(list:Int*) = {
    var sum = 0
    var index = 0
    while(index < list.length) {
      sum = sum + list(index)
      index = index + 1
    }
    sum
  }

  def sumByFor(list:Int*) = {
    var sum = 0
    for(i <- list) sum = sum + i
    sum
  }

  def sumByRec(list:Int*) = {
    def go(list:Seq[Int], ac:Int = 0):Int = {
      list match {
        case Nil => ac
        case head :: tail => go(tail, ac + head)
      }
    }
    go(list.toList)
  }
}

問題2

以下略。

object Problem2 {
  def mutuallyList(a:Any*)(b:Any*) = a.zip(b).flatMap{x => x._1::x._2::Nil}
}

問題3

以下略。

object Problem3 {
  def fibStream(a:BigInt, b:BigInt):Stream[BigInt] = a #:: fibStream(b, a+b)
  def fib(n:Int) = fibStream(0,1).take(n).toList
  def fib100 = fib(100)
}

問題4

Seq.permutationsで、全ての順列(nPn)を取得できます。数値に変換し、その中の最大値を返しています。

object Problem4 {
  def max(list:Seq[Int]) = list.permutations.map(_.map(_.toString).mkString.toInt).max
}

問題5

数値を１つづつ読み込んだ時、その数値は前の数値に対して
* 足す
* 引く
* 連結して、１桁目になる

の３パターンが考えられます。

なので、各数値に対して3つのパターンを生成し、式の文字列のリストを作ります。
作った式を評価し、結果が100になるものを返します。

式の文字列の評価は、再帰下降法を使います。

object Problem5 {
  val numberReg = """([0-9]+)(.*)""".r
  val opReg = """([\+\-])([0-9]+)(.*)""".r

  def calc(expr:String) = {
    def recur(str:String, acc:Int = 0):Int = {
      str match {
        case "" => acc
        case numberReg(x, xs) => recur(xs, acc + x.toInt)
        case opReg("+", x, xs) => recur(xs, acc + x.toInt)
        case opReg("-", x, xs) => recur(xs, acc - x.toInt)
      }
    }
    recur(expr)
  }

  def find = {
    var comb = Seq("1")
    for(n <- 2 to 9) comb = comb.flatMap{c => Seq(c+n, s"$c+$n", s"$c-$n")}
    comb.filter(calc(_) == 100)
  }
}

GitHubはこちら。