3時間クッキング

　完全に時代に取り残されているけど、今更話題を知って、業務アプリケーション開発歴4年の俺が挑戦してみた。
人生を書き換える者すらいた。: 人材獲得作戦・４　試験問題
　お題は「与えられた迷路の最短経路を出力するプログラムを3時間以内に作れ」。
　僕がとった戦略は「再帰で全ルート走査。ただしより少ない歩数で既に通ったルートは二度と踏まない」。
　前提知識なしでJavaで組んだら2時間半、今日pythonで組みなおしてみたら3時間かかった。Javaのときはアルゴリズムを考えるのが楽しくて、Pythonのときは新しい言語に出会うのが楽しかった。Pythonいいかもね。
　以下、コード。うへえ、精進精進。

# -*- coding: mbcs -*-

'''
迷路を記述されたファイルを受け取って、最短経路を記述したファイルを出力します

input:filepath of maze 
writefile 'result.txt' in directory of inputfile

@author: Keniya
'''
import sys
import copy
import os

SPACE = ' ';
BLOCK = '*';
START = 'S';
GOAL = 'G';
MOVED = '$';
MAZE_CHARSET = (SPACE,BLOCK,START,GOAL,MOVED)

__shortestStep = 0;
__shortestResult = [];

def buildMazeFromFile(filepath):
    maze = []
    file = open(filepath)
    try:
        yidx = 0
        for line in file:
            mazeline = []
            xidx = 0;
            for char in line:
                mazeCell = {'c':char, 'step':0}
                if char in MAZE_CHARSET:
                    mazeline.append(mazeCell)
                    if char == 'S':
                        sPos = (yidx,xidx)
                    elif char == 'G':
                        gPos = (yidx,xidx)
                elif char != '\n':
                    raise 'UnexpectedChar',char
                xidx += 1
            maze.append(mazeline)
            yidx += 1
        return maze,sPos,gPos
    finally:
        file.close()

def printMaze(maze):
    print toStrMaze(maze)

def toStrMaze(maze):
    s = '';
    for line in maze:
        for cell in line:
            s += cell['c']
        s += '\n'
    return s

def move(maze, y, x, cnt):
    #記録を残す
    cnt += 1
    maze[y][x]['step'] = cnt
    
    #ゴールしたならひとつ戻って、別の道を探す
    if maze[y][x]['c'] == GOAL:
        global __shortestStep
        global __shortestResult;
        if (__shortestStep < 1) or (__shortestStep > cnt):
            __shortestStep = cnt
            __shortestResult = copy.deepcopy(maze)
            print "GOAL! step:", cnt 
            printMaze(maze)
        return True;
    
    #足跡を残す
    if maze[y][x]['c'] == SPACE:
        maze[y][x]['c'] = MOVED
    
    #東西南北目指してみる
    if (canMove(maze, y, x+1, cnt)):
        move(maze, y, x+1, cnt)
    if (canMove(maze, y, x-1, cnt)):
        move(maze, y, x-1, cnt)
    if (canMove(maze, y+1, x, cnt)):
        move(maze, y+1, x, cnt)
    if (canMove(maze, y-1, x, cnt)):
        move(maze, y-1, x, cnt)
    
    #どこにも行けないどんづまりなら、跡を汚さずひとつ戻って別の道を探す
    if maze[y][x]['c'] == MOVED:
        maze[y][x]['c'] = SPACE
    return True

def canMove(maze, y, x, cnt):    
    #移動できる？
    try:
        status = maze[y][x]['c']
        if (status != SPACE) and (status != GOAL):
            return False 
    except:
        return False
    #最小歩数ならOK!
    return (maze[y][x]['step'] < 1) or (maze[y][x]['step'] > cnt)

def putResultFile(maze,filepath):
    f = open(filepath + '\\result.txt','w')
    try:
        s = toStrMaze(maze)
        f.write(s)
    finally:
        f.close()

def solve(filepath): 
    maze,sPos,gPos = buildMazeFromFile(filepath)
    printMaze(maze)
    
    move(maze, sPos[0], sPos[1], 0)
    
    return __shortestResult,__shortestStep
        
#----------------------------------------
# Main始まるよー
#----------------------------------------
print 'start'
import time
t1 = time.time()

#引数からファイルパス取得
filepath = sys.argv[1]

#解け！
result,stepcnt = solve(filepath)
print 'shortestStepCnt:', stepcnt
printMaze(result)

#結果をファイルに出力
putResultFile(result, os.path.dirname(filepath))

t2 = time.time()
print (t2-t1)*1000,'ms'

print 'end'

　こーいうアルゴリズムは基礎体力なんだろうね。3時間かけてこんなコードじゃ駄目なのはわかってる。頑張ろっと。
　とりあえず1時間以内に解けるようになって、「でもサービスの全体を企画・デザインできる開発者の方が、コーダーより会社の収益に貢献するんじゃね？」って反論したい。

追記

　四方の壁のほかは全部スペース、完全に空洞の迷路でテストしたら30分かかっても答えが帰ってこなくてワロタ。
　「より少ない歩数で既に通ったルートは二度と踏まない」を意識的に行う経路探索のアルゴリズムをダイクストラ法というらしい。へー。僕のやり方より効率的に枝刈りができそうだ。昔の人は賢いなあ。構造化プログラミングを提唱したのもダイクストラさんなの？ あとで組んでみよう。
　A*なんてアルゴリズムはさらに上を行くらしい。ははー、かなわないなあ。

さらに追記

　リンク先が間違っていたのと、リンクと気づきにくかったため修正。
　翌日の日記にさらに修正したコードを貼った。