ことさら−古都プログラマーの更級日記

京都でお寺を回りながら御朱印集めをしていたり、LoLをしたり試合を見に行ったりしているエンジニアのブログです。技術的なはなしとか日常的なはなし、カメラやLoLや競馬の話も書きます。右メニューに検索やらカテゴリーやらがあるので、見たい記事だけ見てね!

Code Quest 「毒沼ノ試練」を頑張って探索してクリアする

この記事は 〇〇勉強してみた Advent Calendar 2017 の6日目の記事です。

昨日も書いた Code Quest の記事ですが、今回は皆が一番苦戦したであろう「毒沼ノ試練」について書こうと思います。

Code Quest

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

geek-out.jp

毒沼の試練

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も確保しなければならないので、案外惜しくないことがわかります。

エクストラモードは?

時間がなくて解けていませんが、死神が移動するだけなので、ほぼおなじコードでクリアできるはずです。

基本的な方針は同じでPriority Queueを使えばよいと思います。ただ、メモリと実行時間の問題があるので、もう少し効率の良い枝刈りができるのではないでしょうか。