組み合わせ爆発について、おねえさんが教えてくれて壮大で切ない結末を迎えるという動画が話題になっていました。おねえさんの決意に感動すること間違いなしです。 そこで、ぼくたちもおねえさんと一緒に25万年数えるためのプログラムを作ってみました。 LinkedList#popメソッドが、最後からとってくるんだと思ったら最初からとってきてたという勘違いではまったけど。 工夫なく計算してるので、6x6マスの時点で5分くらいかかります。 考え方としては、始点から上右下左と移動して、移動先でも上右下左と移動して、移動できなくなったら戻るという感じでやってます。 あと、最初に右に行くパターンと下に行くパターンは対称なので同じ回数ずつあるということから、最初は右に行ったことにして、最後に2倍してます。 まあでも、この程度の工夫では25万年が12.5万年になるくらいで、根本的な解決にはなりません。 計算量として