続・3時間クッキング
今度は空白だらけの地図でも迷わないよ。
ネットの解答例をかなり読んでから再挑戦したため、僕の実力じゃあないんだけどさ。
結局、アメーバのように全方位まんべんなくジワジワと探査して、探査をやり直すハメになったときの手間を減らす作戦をとった。重みとか関係ないからダイクストラ法とはいえないね。
pythonまだ慣れないけど、なんかselfだらけになるなあコレ。そこだけは仕様としてしっくりこない。
# -*- coding: mbcs -*- ''' 迷路を記述されたファイルを受け取って、最短経路を記述したファイルを出力します input:filepath of maze writefile 'result.txt' in directory of inputfile @author: Keniya ''' import os import sys SPACE = ' '; BLOCK = '*'; START = 'S'; GOAL = 'G'; MOVED = '$'; MAZE_CHARSET = (SPACE,BLOCK,START,GOAL,MOVED) class Maze: def __init__(self,filepath): self.mazeMap = [] file = open(filepath) try: yidx = 0 for line in file: mazeline = [] xidx = 0; for char in line: mazeCell = {'c':char, 'step':0, 'prev':None} if char in MAZE_CHARSET: mazeline.append(mazeCell) if char == 'S': self.sPos = (yidx,xidx) elif char == 'G': self.gPos = (yidx,xidx) elif char != '\n': raise 'UnexpectedChar',char xidx += 1 self.mazeMap.append(mazeline) yidx += 1 finally: file.close() def __str__(self): s = ''; for line in self.mazeMap: for cell in line: s += cell['c'] s += '\n' return s def __canMove(self, y, x, cnt): #移動できる？ try: status = self.mazeMap[y][x]['c'] if (status != SPACE) and (status != GOAL): return False except: return False #最小歩数到達ならOK! return (self.mazeMap[y][x]['step'] < 1) or (self.mazeMap[y][x]['step'] > cnt) def putResultFile(self,filepath): f = open(filepath + '\\result.txt','w') try: s = str(self) f.write(s) finally: f.close() def solve(self): print self searching = True candidates = [self.sPos] while searching: for pos in candidates: y = pos[0] x = pos[1] cnt = self.mazeMap[y][x]['step'] char = self.mazeMap[y][x]['c'] for p in [(y,x+1),(y,x-1),(y+1,x),(y-1,x)]: if self.__canMove(p[0], p[1], cnt+1): candidates.append(p) self.mazeMap[p[0]][p[1]]['step'] = cnt+1 self.mazeMap[p[0]][p[1]]['prev'] = pos candidates.remove(pos) if not candidates: candidates.__str__() break prev = self.gPos while True: char = self.mazeMap[prev[0]][prev[1]]['c'] if char == START: break if char == SPACE: self.mazeMap[prev[0]][prev[1]]['c'] = MOVED prev = self.mazeMap[prev[0]][prev[1]]['prev'] print "Step:",self.mazeMap[self.gPos[0]][self.gPos[1]]['step'] print self #---------------------------------------- # Main始まるよー #---------------------------------------- if __name__ == "__main__": print 'start' import time t1 = time.time() #引数からファイルパス取得 filepath = sys.argv[1] #解け！ maze = Maze(filepath) maze.solve() maze.putResultFile(os.path.dirname(filepath)) t2 = time.time() print (t2-t1)*1000,'ms' print 'end'
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*なんてアルゴリズムはさらに上を行くらしい。ははー、かなわないなあ。
さらに追記
リンク先が間違っていたのと、リンクと気づきにくかったため修正。
翌日の日記にさらに修正したコードを貼った。
一週間
月曜日。やっと問題のブツを作り終えた。昼の12時半に帰宅。ラスボス倒してから積んでた魔王物語物語を最終クリアしたりとかして、つーかアレ、隠しボス強すぎだろってことで2時間くらいレベル上げしてたら簡単にレベルカンストするし、むしろカンスト前提んじゃねって気もしたけど、きっと低レベルクリアする人もいるんだろーね。序盤は亀の血と亀の甲羅で防御力ゲー、中盤は人を殺せる本とザーラマントで撲殺ゲー、後半はレベルあげてゴリ押しゲーでした。はっはっは、ゴリ押しに慣れてしまうとダメだねー。プレイヤーレベル低くて申し訳ない気持ちになったけど、やっぱRPGはゴリ押しだね！ 12時間くらい寝る。
火曜日-木曜日。昼前に出て夜に帰る。だらだらと仕事をする振りをする。
金曜日。月曜日に出したものに僕のミスが見つかる。うわああああああああ。
でもまあ、ブツ絡みの三人で、反省会名目で飲みに出かけた。タウンクライヤーという、ブリテッシュバーのくせに昼は角煮をだしてきたりする店だ。ギネス飲んだりウイスキー飲んだり。本場と違ってちゃんと美味しい料理を出してくれる店で、人生で初めてお金を払っていいフィッシュアンドチップスを食べたよ。つーかイギリスの飯がまずいのはあれだね、あれは素材が悪いのもあるよね。あいつら品種改良とか頭にないもんね、リンゴとか生で食えたもんじゃねーし。日本なんてトマトまで甘いし。なんだよトマトが甘いって。おかしいよ。まあとにかくその店は昼はお気に入りなのだけれども、夜はドアが開けっ放しで風が入り込んできて寒かった。なるほど、金曜の夜なのに人がいない理由がわかった。寒いものね。寒い店に人が溜まるわけはないよね。そのあとそのまま同期の家まで行って飲んだり騒いだりダーツしたりブラックジャックでカモられたり同居人の誕生日を祝ったりした。10人くらいが集まった。人徳あるなあ。すごいなあ。
土曜日曜で積んでるメガテンでもやろうかと思っていたけど、結局なんにもしなかったなあ。
エンジェル・ハイロゥ
今日の満月は輪を伴って、空から町を睥睨していた。
24時の深夜。空を均一に薄く覆う雲に月の光が散らされて、霧の向うに太陽が一度ったときに虹の輪ができるように、空に大きく月光の輪が形作られていた。視野角に広く占めるその円は、ビルの向うに。電線の向うに。歩いても歩いても、月の輪はそこにあった。
それはひどく幻想的な光景で、今ここは特別な時間なのではないかと錯覚させるに足る印象を与えた。いつもの帰り道、足が止まって、しばらく月の眼に縛られた。
だけれども、地上に意識を戻すと、空に向けて顔をあげるものは僕の他にいなくて、とにかく誰かにこの感覚を共有してほしくて、道行く人をかたっぱしから捕まえて、なんで上を見上げないんだ、と問いただしたかった。今大変なことになっているんだ、と叫びたかった。その替りに、比較的近くに住んでいる友達にメールを送った。Twitterとかやってるひとはこうなのかと思った。常に世間に叫びたいことがあるのだ。共有したことがたくさんあるのだ。僕にそんなものはないけど、今はそうなんだ。みんな、空を見上げてほしいのだ。これはね、めったにあることじゃあないんだ。
iPhoneで写真もとったけど、夜空に対してはパワー不足はなはだしく、貧弱なものにしかならない。せめてシャッタースピードくらい弄りたいが、Appleにそんなことを期待しても仕方がない。
iPadは買わない
iPadが発表されました。iSlateでもなく、iTabletでもなく。
いつもどおり、Appleらしい製品だなあと思いました。だって、SDカードスロットとかDVDドライブとかないし、FLASH使えないからニコニコ見れないし、持ち歩いて外で使うにはデカイから、屋内で使うってなら別にノートPCでいいし、だいたい液晶ってのはなんだ、そろそろOLEDに変えていこうよ。明らかに僕には不要なシロモノだ。SDカードを削いだのって、ストレージ容量の差分でボるためだけだよね？ さすがアップル汚い。だけど、製品は文句なくカッコいい。憧れる。いいなあ、アップルいいなあ。
ノートPCから機能を削ぎ落としていく方向性なら、GoogleChromeOsのほうが筋がいいと思う。iPadはPC（Mac）との同期が必要な時点で、めんどくさいよねえ。はやくGoogleChromeOSの製品が見たい。
再来年くらいになると、こういった超限定版ネットブック的ナニカが世間に広まっていくのかもしれない。だといいね。
アバター3D吹替板
もののけ姫だコレ！
吹替版ってあまり見ないんだけど、3Dということで字幕が邪魔になるのを考えて、吹替にしてみた。一気に木曜洋画劇場の気分。溢れ出すB級感。これはいいぞ。
ストーリーはひょんなことから太陽系外惑星にインした主人公が、向こうの世界の楽しさに目覚めてリアルを捨てるというネトゲ廃人話。「おいすー^^」「あ、ジェイクたんインしたお！」
そんなストーリーはどうでもいいとして……、画面は本当にすばらしい！ 一面が緑の森の中や、崖から見下ろす絶景、雲中に浮かぶ岩島（ラピュタは本当にあったんだ！）などの風景は美しい。そこに暮らす生物たちは幻想的で、時に厳しく、時に優しく、生き生きと存在している。そして、その聖域に土足で踏みいってくる人類の兵器の雄々しさ！ 恒星間飛行ができる時代になんでこんな現代的な武装なんだ大佐！ 爆撃ヘリvs飛竜！ ボトムズvs亜人間！ ラピュタを背景にミサイルが飛び交い、唸る鉄腕の握りしめたナイフが密林に火花を散らすのさァ！ 轟音！ 炎上！ 死体！ 死体！ うおおおおこいつは興奮するぜェエエエ！ と、いう映画が楽しいひとにオススメ。完全にスクリーン向けですね、はい。なんだかんだ言いつつ、ラストバトルではちょっと涙ぐみました。これだけ気合入れて作ったファンタジー映画が結局ドンパチになるんだから、ハリウッドは豪華だなあ。
米軍側が完全に悪役に回っているんだけど、元海兵隊の大佐が森を焼き払うなら、それを止めるのは元海兵隊の主人公。アメリカ人にとって、やっぱり海兵隊はヒーローなんだな。
人類は衰退しました 5巻
安定飛行した面白さ。巻ごとに「今回こそは飽きるんじゃないだろうか」という微妙な心理で手にとっているものの、今のところは全然大丈夫のようだ。これは蟲師症候群と呼ぼう。ドラえもん系金太郎飴作品は常にリスクを背負っている。
前編が学舎時代のお話。孤独にやつれる主人公が年月を重ねてついに仲間を得るというハートフルな展開なのだが、ヤンデレもいる。ロボットとの遣り取りが映像化されたら僕は泣く自信がある。
後編が妖精アイテムに振り回される、いつものパターン展開。万物がTVゲーム化するという、そこまで聞くとありがちなパターンだけど、ネタの詰め込み具合が多彩多量でとても楽しめた。テトリスやドラクエの描画切り替えによるチラツキ（５人並ぶ）から、はては「Dといったらドラゴン」まで。そういや職場の先輩がローグライクのメンテナをやっていたなあ。
