Code Quest

プログラミング学習用ゲーム的な、あるいはプログラミングコンテスト的なサムシングです。

毒沼の試練

f:id:yoshiki_utakata:20171204161930p:plain

クリアしたコード

手動でやってみると、HP49まではいくのですが、なかなか50にならなくてクリアできません。ということで、プログラムに探索させることにしました。実際クリアしたコードはgithub上に置いておきました。以下のコードを、メモリ8GBくらい与えた上で実行させ、寝ておきたらクリアしていました（解くのに5〜6時間くらいかかった？）。

github.com

このコードにメモリを8GBくらい与えて放置します。

php -d memory_limit=-8196M  poison_maze.php

とりあえす放置して寝たらクリアしていると思います。

このコードに至るまでのいきさつ

まず普通に深さ優先探索する

とりあえずダメ元で深さ優先探索させますがダメでした。当然ながら時間がかかりすぎます。

最初のHPより低くはならないように枝刈り

次に実施したのが枝刈りです。最初のHPが36なので、HPが35以下になってしまった場合は探索を打ち切ります（実際のコードでは少し余裕を持って34以下にしてあります）。結構切れるかなと思ったのですがこれでもダメでした。

一旦 Priority Queue を使った探索に切り替える。

深さ優先探索の場合、探索効率が悪いな、ということで、PriorityQueueを使った探索に変更します。PriorityQueueのPriorityには現在の体力を採用します。つまり、HPが高くなるようなルートから優先的に探索を進めていくようにします。

さて、深さ優先探索に比べて Priority Queue を使った探索（あるいは幅優先探索）は、探索効率がよくなる変わりにメモリを多く消費するという欠点があります。HP35以上という条件は残したまま Priority Queue 探索を進めていたのですが、メモリが足りず最後まで探索できませんでした。今時分が使っているPCの限界を攻めて、8GBのメモリを与えてやりましたが無理でした。そこでもっと枝刈りを強化します。

さらに枝刈りを強化

そこで最後に入れた枝刈りがこちらです。

if((35 + (count($state->history) / 5)) > $state->life) return;

現在、単純に HP が 35 以下の枝を買っていますが、この枝刈りだと、 HP36 -> 42 -> 36 -> 40 のように、一旦増えた体力をまた減らして、そしてまた増えて、... みたいなルートまで探索しています。HPは、移動を重ねるほど増えることが期待されるので、 35 + (移動回数 / 5) 以下のHPになるような枝を刈るようにしました。

この枝刈りを施したプログラムを回したまま寝落ちしてしまったのですが、起きたら問題が解かれていました。

どうでもいいTips

この問題、勇者と魔王の位置関係的に、勇者->魔王までたどり着くには偶数回の移動をする必要があります。つまり、魔王の隣に行くには奇数回の移動をする必要があります。一回の移動でHPは +1, -1 のどちらかが加算されます。初期HPが偶数ですので、奇数回の移動をした後のHPは必ず奇数になります。最後の魔王のマスに移動する時はHPの増減はありませんので、魔王と戦う時のHPはかならず奇数になりますよね。ということで、HP50ピッタリで魔王にたどり着くことはできず、かならずHP51になります。HP49、一見惜しいように見えますが、こう考えると、あとHPを2も確保しなければならないので、案外惜しくないことがわかります。