DouKaku?beta

challenge 必ず解ける迷路 

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

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

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

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

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

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

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


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

Posted feedbacks - OCaml

前々から気になっていたので今更ながら挑戦してみました。棒倒し法です。


OS, マシンスペックは以下の通り。
OS: FreeBSD 7.0-STABLE
CPU: Celeron 500MHz
Mem: 320MB
…orz


バイトコードとネイティブコードを作成して性能を比べてみました。

mitsu@garlic$ ocamlfind c -package unix -linkpkg -o maze.byte maze.ml
mitsu@garlic$ ocamlfind opt -package unix -linkpkg -o maze.native maze.ml

mitsu@garlic$ time ./maze.byte 1024 1024 > /dev/null

real    0m15.978s
user    0m15.583s
sys     0m0.132s
mitsu@garlic$ time ./maze.native 1024 1024 > /dev/null

real    0m2.443s
user    0m2.367s
sys     0m0.037s
mitsu@garlic$

ネイティブコードはさすがに早いなぁ、と思いました。

あと、このマシンスペックで3秒を切っているので、まぁ良いかな、と。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
let x = int_of_string (Sys.argv.(1))
let y = int_of_string (Sys.argv.(2))

let line_loop line func =
  let rec loop pos =
    if pos < x * 2 - 1 then (
      func line pos;
      loop (pos + 1)
    ) in
  loop 0

let make_line v = Array.make (x * 2 - 1) v

let make_empty_line () = make_line 0

let make_filled_line () = make_line 1

let make_checked_line () =
  let line = make_empty_line () in
  line_loop line (
    fun l p -> if (p mod 2) = 1 then l.(p) <- 1
  );
  line

let print_line line =
  print_string "■";
  line_loop line (
    fun l p -> if l.(p) = 1 then print_string "■" else print_string "　"
  );
  print_endline "■"

type mode = Top | Normal

let make_maze mode lines =
  let way = match mode with Top -> 4 | Normal -> 3 in
  let rec make_wall pos =
    let (y, x) =
      match (Random.int way) with
      | 0 -> (1, pos + 1)
      | 1 -> (2, pos)
      | 2 -> (1, pos - 1)
      | 3 -> (0, pos)
      | _ -> failwith "invalid value" in
    if lines.(y).(x) = 1 then make_wall pos else lines.(y).(x) <- 1 in
  let rec loop pos =
    if pos < x * 2 - 1 then (
      if pos mod 2 = 1 then make_wall pos; loop (pos + 1)
    ) in
  loop 0

let main () =
  let _ = Random.init (int_of_float (Unix.time ())) in
  let filled_line = make_filled_line () in
  print_line filled_line;
  let rec loop cnt last_line =
    if cnt < y
      then (
        let lines = [|last_line; make_checked_line (); make_empty_line ()|] in
        make_maze (if cnt = 0 then Top else Normal) lines;
        print_line lines.(0);
        print_line lines.(1);
        loop (cnt + 1) lines.(2)
      )
      else print_line last_line in
  loop 0 (make_empty_line ());
  print_line filled_line

let _ = main ()

壁かどうかはヴァリアントにすべきでした… 自己満足ですが修正版を。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
type field = Space | Wall

let x = int_of_string (Sys.argv.(1))
let y = int_of_string (Sys.argv.(2))

let line_loop line func =
  let rec loop pos =
    if pos < x * 2 - 1 then (
      func line pos;
      loop (pos + 1)
    ) in
  loop 0

let make_line v = Array.make (x * 2 - 1) v

let make_empty_line () = make_line Space

let make_filled_line () = make_line Wall

let make_checked_line () =
  let line = make_empty_line () in
  line_loop line (
    fun l p -> if (p mod 2) = 1 then l.(p) <- Wall
  );
  line

let print_line line =
  print_string "■";
  line_loop line (
    fun l p -> if l.(p) = Wall then print_string "■" else print_string "　"
  );
  print_endline "■"

_build  maze.ml
type mode = Top | Normal

let make_maze mode lines =
  let way = match mode with Top -> 4 | Normal -> 3 in
  let rec make_wall pos =
    let (y, x) =
      match (Random.int way) with
      | 0 -> (1, pos + 1)
      | 1 -> (2, pos)
      | 2 -> (1, pos - 1)
      | 3 -> (0, pos)
      | _ -> failwith "invalid value" in
    if lines.(y).(x) = Wall then make_wall pos else lines.(y).(x) <- Wall in
  let rec loop pos =
    if pos < x * 2 - 1 then (
      if pos mod 2 = 1 then make_wall pos; loop (pos + 1)
    ) in
  loop 0

let main () =
  let _ = Random.init (int_of_float (Unix.time ())) in
  let filled_line = make_filled_line () in
  print_line filled_line;
  let rec loop cnt last_line =
    if cnt < y
      then (
        let lines = [|last_line; make_checked_line (); make_empty_line ()|] in
        make_maze (if cnt = 0 then Top else Normal) lines;
        print_line lines.(0);
        print_line lines.(1);
        loop (cnt + 1) lines.(2)
      )
      else print_line last_line in
  loop 0 (make_empty_line ());
  print_line filled_line

let _ = main ()

osiireさんからブログ経由でアドバイスを頂いたのを皮切りに、色々無駄な処理が気になってきたので再度修正した自己満足第三弾。Array.iter等を使うように、などなど。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
type field = Space | Wall

let x = int_of_string (Sys.argv.(1))
let y = int_of_string (Sys.argv.(2))

let rec repeate f x i n =
  if i < n then repeate f (f i x) (i + 1) n else x

let make_line v = Array.make (x * 2 - 1) v

let make_empty_line () = make_line Space

let make_filled_line () = make_line Wall

let print_line line =
  print_string "■";
  Array.iter (
    fun a -> if a = Wall then print_string "■" else print_string "　"
  ) line;
  print_endline "■"

type mode = Top | Normal

let make_maze mode lines =
  let way = match mode with Top -> 4 | Normal -> 3 in
  let rec make_wall pos =
    let (y, x) =
      match (Random.int way) with
      | 0 -> (1, pos + 1)
      | 1 -> (2, pos)
      | 2 -> (1, pos - 1)
      | 3 -> (0, pos)
      | _ -> failwith "invalid value" in
    if lines.(y).(x) = Wall
      then make_wall pos
      else (
        lines.(1).(pos) <- Wall;
        lines.(y).(x) <- Wall
      ) in
  Array.iteri (fun i a -> if i mod 2 = 1 then make_wall i) lines.(0)

let main () =
  let _ = Random.init (int_of_float (Unix.time ())) in
  let draw_maze pos last_line =
    let lines = [|last_line; make_empty_line (); make_empty_line ()|] in
    make_maze (if pos = 0 then Top else Normal) lines;
    print_line lines.(0);
    print_line lines.(1);
    lines.(2) in
  let filled_line = make_filled_line () in
  print_line filled_line;
  print_line (repeate draw_maze (make_empty_line ()) 0 y);
  print_line filled_line

let _ = main ()

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]