プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q14:W杯出場国しりとり。

Q: どの国名も１度しか使うことができないとき、最も長く続けられる順を求め、長さを応える。

foldLeftはmapしてmaxで置き換えられるし、その方が見た目シュッとするけど、こっちの方が性能は良いはず。

val countries = Set("Brazil","Croatia","Mexico","Cameroon","Spain","Netherlands","Chile","Australia","Colombia","Greece","Cote d'lvoire","Japan","Uruguay","Costa Rica","England","Italy","Switzerland","Ecuador","France","Honduras","Argentina","Bosnia and Herzegovina","Iran","Nigeria","Germany","Portugal","Ghana","USA","Belgium","Algeria","Russia","Korea Republic")

def count(last:Char, group:Set[String], acc:Int):Int = {
  val matching = group.filter(_.head == last)
  if(matching.size == 0) acc
  else {
    matching.foldLeft(acc){ (z,country) =>
      val length = count(country.last.toUpper, group - country, acc + 1)
      if(length > z) counted else z
    }
  }
}

upperCase.foldLeft(1){(z,country) =>
  val length = count(country.last.toUpper, countries - country, 1)
  if(length > z) length else z
}