必ず解ける迷路 in Smalltalk DouKaku?

必ず解ける迷路

以下のルールを満たすn×mの迷路を出力するプログラムを作ってください。

1. 格子状の迷路であること。
2. 経路の幅は均等であること。
3. 迷路のある地点からの全ての地点に到達する経路が1つだけ存在すること。
   ループも認めません。
4. 出力の度にランダムな迷路であること。
   ランダムシードが同じ時に同じ迷路になってしまうのはよいです。

たとえば、n=4, m=5の迷路の出力は以下のようになります。

　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　■　　　■
―■■■　■■■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■　■　■
４■　■　　　■　■
―■　■　■■■　■
５■　■　　　■　■
―■■■■■■■■■

こう言うのは、×の部分が3のルールに違反するのでダメです。
　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　■×■　■
―■■■　■■■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■■■　■
４■　■×××■　■
―■　■×■■■　■
５■　■×××■　■
―■■■■■■■■■

このようなループも2のルールに違反するのでダメです。
　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　　　■　■
―■■■　■　■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■　■　■
４■　■　　　■　■
―■　■　■■■　■
５■　　　　　■　■
―■■■■■■■■■

できたプログラムを使って n=1024, m=1024 の迷路を作るのにかかった時間を教えてください。


難易度高めです。限られたメモリを使って縦方向に無限に広い迷路を
どうやって作るのかを考えると答えが見えてくると思います。
ソースコードはJavaで150行程度になりました。

post comment

Posted feedbacks - Smalltalk

Squeak Smalltalk で。

n = 1024、m = 1024 では、1 GHz PowerPC (OS X) で６分半ほどでした。

| Ｎ Ｍ 時間 出力 ライン 直前向き 上下枠描画 |
Ｎ := 1024.  Ｍ := 1024.

時間 := [
    出力 := FileStream forceNewFileNamed: 'doukaku123.out'.
    ライン := Array new: Ｎ.
    直前向き := nil.
    1 to: Ｎ do: [:idx |
        | 向き |
        向き := (直前向き = #右 ifTrue: [#(上 下 右)] ifFalse: [#(上 下 右 左)]) atRandom.
        ライン at: idx put: (直前向き := 向き)].
    (上下枠描画 := [出力 nextPutAll: (String new: Ｎ + 1 * 2 + 1 withAll: $■); cr]) value.
    出力 nextPutAll: '■　'.
    ライン do: [:向き | 出力 nextPutAll: (向き = #上 ifTrue: ['■　'] ifFalse: ['　　'])].
    出力 nextPut: $■; cr.
    Ｍ timesRepeat: [
        出力 nextPut: $■.
        直前向き := nil.
        ライン do: [:向き |
            出力 nextPut: ((直前向き = #右 or: [向き = #左]) ifTrue: [$■] ifFalse: [$　]).
            出力 nextPut: $■.
            直前向き := 向き].
        出力 nextPutAll: (直前向き = #右 ifTrue: ['■■'] ifFalse: ['　■']); cr.
        出力 nextPutAll: '■　'.
        ライン do: [:向き | 出力 nextPutAll: (向き = #下 ifTrue: ['■　'] ifFalse: ['　　'])].
        出力 nextPut: $■; cr.
        直前向き := nil.
        1 to: Ｎ do: [:idx |
            | 向き |
            向き := (直前向き = #右 ifTrue: [#(下 右)] ifFalse: [#(下 右 左)]) atRandom.
            ライン at: idx put: (直前向き := 向き)]].
    上下枠描画 value] timeToRun.
"出力 edit."
^時間 milliSeconds   "=> 0:00:06:29.346 "

DouKaku?

必ず解ける迷路

Posted feedbacks - Smalltalk

Index

Feed

Other

Link

Pathtraq