kakuyonの日記

Webアプリやセキュリティに関する事を書いていけたらと考えています。

トップ > Python > CODE QUESTの「毒沼ノ試練」を一応解いてみた

CODE QUESTの「毒沼ノ試練」を一応解いてみた

Python

Pythonの学習をある程度進めてきたので、練習として何かやってみようと思い、
半年ほど前に話題になっていた、CODE QUESTに挑戦してみました。

目次

CODE QUESTとは

GeekOutさんが提供されている、エンジニア向けのゲーム(？)です。

最近は、第二弾としてクイズ形式で遊べるものも用意されたみたいです。
以前、このゲームに挑戦した時は解法が分からず惨敗したので、
リベンジがてら「毒沼ノ試練」に挑戦してみました。

毒沼ノ試練

f:id:kakuyon:20180619021901p:plain

人力で10分くらい試してみましたが、ギリギリ行けそうで行けなかったので、
とりあえず、どこかで見かけてうろ覚えだったアルゴリズムを用いて解くことにしました。

とりあえず書いたコード
from copy import deepcopy

data = [[-1,1,1,-1,-1,1,1,-1,-1,1],
        [1,"S",1,"L",-1,-1,-1,-1,-1,-1],
        [-1,-1,-1,1,1,-1,1,-1,1,1],
        [1,"L",-1,-1,1,-1,1,-1,1,-1],
        [-1,1,1,-1,-1,-1,-1,"L",1,-1],
        [1,-1,1,-1,-1,1,-1,1,-1,1],
        [-1,"L",-1,-1,-1,1,-1,-1,-1,1],
        [-1,1,-1,1,1,-1,1,-1,-1,-1],
        [-1,1,-1,-1,-1,1,1,-1,"G",1],
        [-1,-1,1,1,-1,-1,-1,1,-1,-1]]
y = 1
x = 1
ans = []

def search_route(field, y, x, hp=36, route=''):
	# ゴール地点へ到達したら終了
	if field[y][x] == 'G':
		if hp >= 50: ans.append(route)
		return

        # HP増減処理
	if field[y][x] == 1: hp += 1
	if field[y][x] == -1: hp -= 1
	if hp <= 0: return 

	field[y][x] = 'L'

        # 移動可能なマスを探索する
	if y - 1 >= 0 and field[y-1][x] != 'L':
		search_route(deepcopy(field), y-1, x, hp, route + 'U')
	if y + 1 <= 9 and field[y+1][x] != 'L':
		search_route(deepcopy(field), y+1, x, hp, route + 'D')
	if x + 1 <= 9 and field[y][x+1] != 'L':
		search_route(deepcopy(field), y, x+1, hp, route + 'R')
	if x - 1 >= 0 and field[y][x-1] != 'L':
		search_route(deepcopy(field), y, x-1, hp, route + 'L')
	return

search_route(deepcopy(data), y, x)
print(ans)

data内にマップの情報が入っています。
文字列Sはスタート地点、Gはゴール地点、Lが死神です。

スタート地点から上下左右、移動可能なマスへ再帰的に関数を呼び出しています。
マップからはみ出しておらず、死神の居ないマスが移動可能なマスです。

一度来た道は引き返せないように、死神を設置しながら移動するようにして、
後は現在の居場所に応じて体力を増減させたりする‥‥大体こんな感じです。

実行すると固まります。
一日くらい放置してたら解は出るかもしれませんが、暇なので色々調べてると、
枝刈り法というものがあるっぽい事に気づいたので、早速試してみました。

枝刈り法を用いたコード
from copy import deepcopy

data = [[-1,1,1,-1,-1,1,1,-1,-1,1],
        [1,"S",1,"L",-1,-1,-1,-1,-1,-1],
        [-1,-1,-1,1,1,-1,1,-1,1,1],
        [1,"L",-1,-1,1,-1,1,-1,1,-1],
        [-1,1,1,-1,-1,-1,-1,"L",1,-1],
        [1,-1,1,-1,-1,1,-1,1,-1,1],
        [-1,"L",-1,-1,-1,1,-1,-1,-1,1],
        [-1,1,-1,1,1,-1,1,-1,-1,-1],
        [-1,1,-1,-1,-1,1,1,-1,"G",1],
        [-1,-1,1,1,-1,-1,-1,1,-1,-1]]
y = 1
x = 1
ans = []

def search_route(field, y, x, hp=36, route='', cnt=0):
	# ゴール地点へ到達したら終了
	if field[y][x] == 'G':
		if hp >= 50: ans.append(route)
		return

        # HP増減処理
	if field[y][x] == 1: hp += 1
	if field[y][x] == -1: hp -= 1
	if hp <= 0: return

        # 見込み以上のHPが無い場合は終了
	if hp <= 32 + cnt // 3: return        

	field[y][x] = 'L'

        # 移動可能なマスを探索する
	if y - 1 >= 0 and field[y-1][x] != 'L':
		search_route(deepcopy(field), y-1, x, hp, route + 'U', cnt+1)
	if y + 1 <= 9 and field[y+1][x] != 'L':
		search_route(deepcopy(field), y+1, x, hp, route + 'D', cnt+1)
	if x + 1 <= 9 and field[y][x+1] != 'L':
		search_route(deepcopy(field), y, x+1, hp, route + 'R', cnt+1)
	if x - 1 >= 0 and field[y][x-1] != 'L':
		search_route(deepcopy(field), y, x-1, hp, route + 'L', cnt+1)
	return

search_route(deepcopy(data), y, x)
print(ans)

if hp <= 32 + cnt // 3: return

この部分で枝刈りを行っています。
移動量に比例して求めるHPの量を増やしていくことで無駄な探索を削れている…はずです。

実行結果
['RDRRDRRUUULLLLLLDDDDRRDDDLDDRRUURDRRUULURRRUUURDDDDDDL',
 'RDRRDRRUUULLLLLLDDDDRRDDDLDDRRUURDRRULUURRRUUURDDDDDDL',
 'RDRRDRRUUULLLLLLDDDDRRDDDLDDRRUURRDRUULURRRUUURDDDDDDL',
 'RDRRDRRUUULLLLLLDDDDRRDDDLDRDRUURDRRUULURRRUUURDDDDDDL',
 'RDRRDRRUUULLLLLLDDDDRRDDDLDRDRUURDRRULUURRRUUURDDDDDDL',
 'RDRRDRRUUULLLLLLDDDDRRDDDLDRDRUURRDRUULURRRUUURDDDDDDL']
[Finished in 1754.8s]

実行時間1754.8sは置いておいて、とりあえず結果が出力されましたので、これに沿って移動してみると！
f:id:kakuyon:20180619034352p:plain

というわけで一応クリアできました。
どう見ても実行時間が普通ではないので、どこかに改善の余地があるのでしょうが、よく分からない&疲れたので、これで一旦終了ということにしておきます。
改善案が見つかったら更新するかもしれないししないかもしれません。