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

「1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に」で紹介されている問題に挑戦してみました。といっても、一時間なんてとんでもなくて2週間くらいかけてますけどね...

問題4

正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる。

def makeBiggestNumber(ns: List[Int]): Int =
  ns.permutations.toList.map(_.foldLeft("")((a, x) => a + x).toInt).max

これはこんな感じでいいですかね。

問題5

1,2,…,9の数をこの順序で、”+”、”-“、またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる。

def makeList(ns: List[Int]): Set[List[Int]] = {
  def makeList(ns: List[Int], ms: List[Int], rs: Set[List[Int]]): Set[List[Int]] =
    if (ns.isEmpty) rs + ms
    else if (ms.isEmpty) makeList(ns.tail, List(ns.head), rs)
    else makeList(ns.tail, ns.head :: ms,
           makeList(ns.tail, ms.head * 10 + ns.head :: ms.tail, rs))
  makeList(ns, List[Int](), Set[List[Int]]()).map(_.reverse)
}
def makeListsWithNegative(ns: List[Int]): Set[List[Int]] = {
  def makeListsWithNegative(ns: List[Int], ms: List[Int], rs: Set[List[Int]]): Set[List[Int]] =
    if (ns.isEmpty) rs + ms
    else makeListsWithNegative(ns.tail, ns.head :: ms,
           makeListsWithNegative(ns.tail, -ns.head :: ms, rs))
  makeListsWithNegative(ns, List[Int](), Set[List[Int]]()).map(_.reverse)
}
def resolve: Set[List[Int]] = 
  makeList(Range(1, 10).toList).flatMap(ns => makeListsWithNegative(ns).filter(ms => ms.sum == 100))

こちらは、えー、深さ優先探索っていうんですか、初めて書きました。関数名がイマイチですが勘弁してください。問題を解くとはリストを作ること、っていう基本に忠実にやってみたつもりです。

問題5の別解

def solve: List[List[Int]] =
  Range(1, 10).foldLeft(List[List[Int]]()) {
    case (_, 1) => List(List(1))
    case (a, n) => a.flatMap(ls => List(n :: ls, ls.head * 10 + n :: ls.tail))
  }.flatMap(ls => ls.foldLeft(List(List[Int]()))((a, n) => 
    a.flatMap(ms => List(n :: ms, -n :: ms))
  )).filter(ls => ls.sum == 100)

foldでaccを処理すると可能性広がるなってことと、flatMap超便利！ってことが学びです。