迷路を最短経路で解く問題を Squeak Smalltalk で
いまさらですが…。
さて試験問題です。
内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。
たとえば、S:スタート G:ゴール *:壁 $:解答の経路 としたとき、**************************
*S* * *
* * * * ************* *
* * * ************ *
* * *
************** ***********
* *
** ***********************
* * G *
* * *********** * *
* * ******* * *
* * *
**************************という入力に対し、
**************************
*S* * $$$ *
*$* *$$*$ ************* *
*$* $$* $$$************ *
*$$$$* $$$$$ *
**************$***********
* $$$$$$$$$$$$$ *
**$***********************
* $$$$$*$$$$$$$$$$$$$$G *
* * $$$ *********** * *
* * ******* * *
* * *
**************************という出力が来ればOK、というわけです。（ブラウザだと見づらいかもしれないのでテキストエディタ等にコピーすれば見やすくなります）
もうちょっと細かい条件としては、
人材獲得作戦・４ 試験問題ほか: 人生を書き換える者すらいた。
●入出力はテキストデータを用いる
●一度に動けるのは上下左右のみ。斜めは不可
●最短経路が複数あるときはそのうちの１つが出力されていればOK
●入力データのバリデーション（長方形になっているか、スタート・ゴールが１つずつあるかどうか、等）は不要
●制限時間は３時間
●プログラム言語・OSは自由
です。
はずかしながら、Ａ＊とか知らないので愚直に。print it の直後にそのままペースト操作をすると、結果を同内容の等幅フォントテキストに置き換えられます。
| data nSteps deltas selectIndicesOf map ansMap goalPos | data := #( '**************************' '*S* * *' '* * * * ************* *' '* * * ************ *' '* * *' '************** ***********' '* *' '** ***********************' '* * G *' '* * *********** * *' '* * ******* * *' '* * *' '**************************' ). map := Matrix rows: data size columns: data anyOne size contents: data concatenation. selectIndicesOf := [:target | map withIndicesInject: #() into: [:ps :currVal :nRow :nCol | currVal = target ifTrue: [ps, {nCol@nRow}] ifFalse: [ps]]]. deltas := {-1@0. 1@0. 0@-1. 0@1}. goalPos := (selectIndicesOf value: $G) anyOne. ansMap := map copy. 'SG* ' with: {0. Float infinity. -1. Float infinity} do: [:ori :alt | map replaceAll: ori with: alt]. nSteps := 0. [:exit | [ | neighs | neighs := ((selectIndicesOf value: nSteps) collect: [:pos | pos + deltas]) concatenation asSet. (neighs includes: goalPos) ifTrue: [exit value]. nSteps := nSteps + 1. neighs do: [:neighPos | | val | val := map at: neighPos y at: neighPos x. map at: neighPos y at: neighPos x put: (nSteps min: val)] ] repeat ] valueWithExit. map at: goalPos y at: goalPos x put: nSteps + 1. nSteps to: 1 by: -1 do: [:val | (selectIndicesOf value: val) do: [:currPos | (currPos + deltas noneSatisfy: [:neighPos | (map at: neighPos y at: neighPos x) = (val + 1)]) ifTrue: [map at: currPos y at: currPos x put: nil]]]. pos := (selectIndicesOf value: 0) anyOne. 1 to: nSteps do: [:currSteps | pos := pos + deltas detect: [:neighPos | (map at: neighPos y at: neighPos x) = currSteps]. ansMap at: pos y at: pos x put: $$]. Clipboard clipboardText: (Text string: (String streamContents: [:ss | data do: [:row | ss cr; nextPutAll: row]. ss cr. (1 to: ansMap rowCount) do: [:nRow | ss cr; nextPutAll: '', (ansMap atRow: nRow)]. ss cr; cr; nextPutAll: nSteps printString, ' steps'; cr]) attribute: (TextFontReference toFont: ((TextConstants at: #DefaultFixedTextStyle) defaultFont))). ^Clipboard clipboardText
************************** *S* * * * * * * ************* * * * * ************ * * * * ************** *********** * * ** *********************** * * G * * * *********** * * * * ******* * * * * * ************************** ************************** *S* * $$$$ * *$* *$$* $************* * *$* $$* $$************ * *$$$$* $$$$$ * **************$*********** * $$$$$$$$$$$$$ * **$*********************** * $$$$$* $$$$$$$$$$$$$G * * * $$$$*********** * * * * ******* * * * * * ************************** 59 steps
違う迷路の場合。
************************** *S* * * * * * * * ***** *** ** * * * * **** *** *** * * * * * ***** * ************* **** **** *** **** **** ** ********* **** *** **** * * *G * * ** *********** * * * * ***** ******* * **** * * ************************** ************************** *S* * $$$$ *$$$$$ * *$* *$$* $*****$***$** * *$* $$* $$****$***$*** * *$$$$* $$$$$$ *$$$ * ***** * *************$**** **** *** ****$$$$$**** ** ********* ****$*** **** * *$$$$$$$$$$ *G$ * * ** $$ *********** *$ * * * $***** ******* $$ * **** $$$$$$$$$$$$$$$$* * ************************** 75 steps
補足
Matrix>>#indexOf: が row@column を返すという タコ仕様 特性を持っていたためスタート地点の検索にバグがありましたので自作関数（ブロック）の selectIndicesOf に差し替えることで対応しました（ゴールの検索も #indexOf: でいいやん的修正 → 無限ループ orz で判明。まあ、そういう意味では repeat ブロックの中で、neighs ifEmpty: [^self error: 'ゴール到達、できましぇんっ！'] 程度のチェックは入れておくべきかも）。
あと、#first をすべて #anyOne に差し替えました。ちなみに、#anyOne は SequenceableCollection ではたんに #first のエイリアスに過ぎないので、なんとなく気分的な意味（スタートとかゴールが複数あってもしらないよ、どれか適当に選んどくよ、的な意思表明）でしかありませんのであしからず。^^;
