プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q25:オシャレな靴ひもの結び方。

Q: スニーカーの合計12カ所の穴にひもを通すとき、交差する点が最も多くなるときの交点の数を求める。ただし、ひもを結ぶ位置は一番上とし、左右交互に使用する。

for {
  l <- (1 to n-1).permutations
  r <- (1 to n-1).permutations
} yield {
  val path = (0+:l.init).zip(r).zip(l.zip(r)).foldLeft(Seq.empty[(Int,Int)]){(z,n)=>z:+n._1:+n._2}:+(l.last,0)
  (0 to path.length).foldLeft(0){(z,i) =>
    z + (i+1 until path.length).count{ j =>
      (path(i)._1 - path(j)._1) * (path(i)._2 - path(j)._2) < 0
    }
  }
}

5行目のひもの通す順番を生成する部分がかなりカオスになってしまった。。