DouKaku?beta

Comment detail

必ず解ける迷路 (Nested Flatten) 
メモリを O(n) でしか使わないのを書いてみました。
最後の行で辻褄を合わせていますが、それなりな迷路になっているかと思います。

n=4, m=5, seed=6 でこんな感じになりました。

■■■■■■■■■
■　■　　　■　■
■　■　■■■　■
■　■　　　　　■
■　■　■■■■■
■　　　■　■　■
■■■　■　■　■
■　　　　　■　■
■■■■■　■　■
■　　　　　　　■
■■■■■■■■■

  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
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Iterator;
import java.util.Random;


public class Sample123 {
    public static void main(String[] args) {
        try {
            BufferedWriter writer = new BufferedWriter(new FileWriter("result.txt"));

            long start = System.currentTimeMillis();
            Iterator<String> ite = new MazeLineIterator(4, 5, 6);
            while (ite.hasNext()) {
                writer.append(ite.next());
                writer.newLine();
            }
            long end = System.currentTimeMillis();

            writer.close();
            System.out.println("elapse: " + (end - start) + "(ms)");
        } catch (IOException ex) {
            ex.printStackTrace();
        }
    }
}

class MazeLineIterator implements Iterator<String> {
    public static final String WALL_CHAR = "■";
    public static final String SPACE_CHAR = "　";

    private static final int WALL_AREA = 0;

    private final Random random_;

    private long line_ = -1;
    private boolean oddLine_ = false;    // oddLine_ == true の時が通路の行、falseの時が柱の行
    private int counter_ = 1;

    private final int maxCol_;
    private final long maxRow_;
    private final int[] mazeLine_;

    public MazeLineIterator(int col, long row) {
        maxCol_ = col;
        maxRow_ = row;
        mazeLine_ = new int[col * 2 + 1];
        random_ = new Random();
    }
    public MazeLineIterator(int col, long row, long seed) {
        maxCol_ = col;
        maxRow_ = row;
        mazeLine_ = new int[col * 2 + 1];
        random_ = new Random(seed);
    }


    public boolean hasNext() {
        return (line_ < maxRow_);
    }

    public String next() {
        if (line_ < 0 || (line_ == maxRow_ - 1 && !oddLine_)) {
            for (int index = 0; index < mazeLine_.length; index++) {
                mazeLine_[index] = WALL_AREA;
            }
        } else {
            if (oddLine_) {
                createOddLine();
            } else {
                createEvenLine();
            }
        }

        if (!oddLine_) line_++;
        oddLine_ = !oddLine_;
        return createDisplay(mazeLine_);
    }

    private String createDisplay(int[] line) {
        StringBuilder builder = new StringBuilder(line.length);
        for (int index: line) {
            //builder.append(index);
            builder.append(isWall(index)? WALL_CHAR: SPACE_CHAR);
        }
        return builder.toString();
    }


    private void createOddLine() {
        int area = 0;
        for (int index = 0; index < maxCol_; index++) {
            int lastArea = mazeLine_[index * 2 + 1];
            if (isWall(lastArea)) {
                if (isWall(area)) {
                    area = counter_++;
                }
                mazeLine_[index * 2 + 1] = area;
            } else {
                if (!isWall(area)) {
                    if (area == lastArea) {
                        mazeLine_[index * 2] = WALL_AREA;
                    } else {
                        area = replaceArea(area, lastArea);
                    }
                } else {
                    area = lastArea;
                }
            }

            if (index > 0 && line_ == maxRow_ - 1) {
                if (mazeLine_[index * 2 + 1] != mazeLine_[index * 2 - 1]) {
                    area = replaceArea(mazeLine_[index * 2 - 1], mazeLine_[index * 2 + 1]);
                    mazeLine_[index * 2] = area;
                }
            }
            if (index == maxCol_ - 1) break;
            if (random_.nextBoolean()) {
                area = WALL_AREA;
            }
            mazeLine_[(index + 1) * 2] = area;
        }
    }

    private void createEvenLine() {
        for (int index = 0; index < maxCol_; index++) {
            int lastArea = mazeLine_[index * 2 + 1];
            if (searchArea(lastArea, index * 2 + 1) && random_.nextBoolean()) {
                mazeLine_[index * 2 + 1] = WALL_AREA;
            }
            mazeLine_[(index + 1) * 2] = WALL_AREA;
        }
    }

    private boolean isWall(int area) {
        return (area == WALL_AREA);
    }
    private int replaceArea(int oldArea, int newArea) {
        if (oldArea < newArea) {
            return replaceArea(newArea, oldArea);
        }
        for (int index = 0; index < mazeLine_.length; index++) {
            if (mazeLine_[index] == oldArea) {
                mazeLine_[index] = newArea;
            }
        }
        if (oldArea == counter_) {
            counter_--;
        }
        return newArea;
    }

    private boolean searchArea(int area, int excludeIndex) {
        for (int index = 0; index < mazeLine_.length; index++) {
            if (index == excludeIndex) continue;
            if (mazeLine_[index] == area) return true;
        }
        return false;
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }
}

1024x1024を出力したら、Pen4 2.4GHzで 10秒弱でした。

棒倒し法も空間計算量がO(n)ですね。
すみません勘違いしてました。

私の考えたアルゴリズムと同じです。
棒倒し法の1行バッファ版と言えるようです。

以下、n=5, m=5の迷路の例でアルゴリズムを解説します。

・最初の行
Ｓ■■■■■■■■■■■←
まずバッファを用意して、全て壁にします。

・1行目(奇数行)
Ｓ■■■■■■■■■■■
１■★■★■★■★■★■←
★の箇所に穴を開けます。

Ｓ■■■■■■■■■■■
１■Ａ■Ｂ■Ｃ■Ｄ■Ｅ■←
穴を開けた場所をＡ～Ｅとします。

Ｓ■■■■■■■■■■■
１■Ａ★Ｂ★Ｃ★Ｄ★Ｅ■←
★の箇所に穴を開けるかどうかを乱数で決定します。

Ｓ■■■■■■■■■■■
１■Ａ▲Ｂ★Ｃ★Ｄ★Ｅ■←
たとえば▲に穴を開ける場合。

Ｓ■■■■■■■■■■■
１■ＡＡＡ★Ｃ★Ｄ★Ｅ■←
ＡとＢの領域が結合されるため、Ｂ領域をＡ領域に統合します。
仮にＢ領域に飛び地があっても、それもＡ領域に統合します。
また、★の左右が同じ領域だった場合は、穴を開けてはいけません。
ループ経路が出来てしまうからです。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■←
この調子で穴を開けていきます。
全ての★を乱数で決定したら1行確定です。

・2行目(偶数行)
Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ☆Ａ☆Ａ☆Ａ★Ｅ■←
☆の箇所を壁にします。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■Ａ■Ａ■Ａ■Ｅ■←
★の箇所はすでに壁なので特に何もしません。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■☆■☆■☆■☆■Ｅ■←
☆の箇所を壁にするかどうかを乱数で決定します。

ただし、残り１つになっているＥの列は壁になってはいけません。
また、４つの☆は３つまでは壁にしてもよいですが、
最後のひとつは壁にしてしてはいけません。
４つとも壁にしてしまうと
　Ｓ■■■■■■■■■■■
　１■ＡＡＡＡＡＡＡ■Ｅ■
　２■■■■■■■■■Ｅ■←
こうなって、Ａの領域に侵入できなくなってしまうからです。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■←
乱数を使って結局２箇所を壁にすることになりました。
全ての☆を乱数で決定したら1行確定です。

・3行目(奇数行)
Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■Ａ■★■Ａ■★■Ｅ■←
1行目と同じく、★の箇所に穴を開けてＢ,Ｃ領域と
します。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■Ａ★Ｂ★Ａ★Ｃ★Ｅ■←
★の箇所に穴を開けるかどうかを乱数で決定します。


あとは同じように、
偶数行→奇数行→偶数行→・・・
と繰り返します。


・9行目(最後の一つ前の行&奇数行)
Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ■Ａ■Ｃ■Ｃ■Ｃ■←
最後の一つ前の行は辻褄あわせが必要です。
具体的には、すべての領域を統合しなければなりません。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ■Ａ★Ｃ■Ｃ■Ｃ■←
今回は、たまたまＡ領域とＣ領域しかないため、
★の箇所の壁を取り除けばＯＫです。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ★Ａ☆Ｃ★Ｃ★Ｃ■
★☆の箇所に穴を開けるか乱数で決定します。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ■ＡＡＡ★Ａ★Ａ■
☆確定まで。
この例では、☆以外はたまたま左右が同じ領域なので、
選択肢がありません。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ■ＡＡＡ■Ａ■Ａ■
Ａ領域とＣ領域が統合されたため、
残りの★も穴をあけられなくなりました。

・最後の行
Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ■ＡＡＡ■Ａ■Ａ■
Ｅ■■■■■■■■■■■
全て壁で埋めます。

これでおしまいです。


私の書いたJavaコードだと出力無しで1372ミリ秒でした。
　　PentiumM 2.1GHz
　　java version "1.6.0_02"
　　Java(TM) SE Runtime Environment (build 1.6.0_02-b05)
　　Java HotSpot(TM) Server VM (build 1.6.0_02-b05, mixed mode)

このアルゴリズムで組んでみました。Pentium2 266MHzで30秒です。きっともっと最適化の余地があることでしょう。。。。

  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
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#include <vector>
#include <fstream>
#include <algorithm>
#include <cstdlib> // random, srand
#include <cassert> // assert
#include <ctime> // time

#define REP(i, b, e) for (size_t i = b; i < e; ++i)
#define STEP(i, b, e, step) for (size_t i = b; i < e; i += step)

const size_t wall = static_cast<size_t>(-1);

bool random()
{
    return std::rand() < RAND_MAX / 2;
}

void print(std::ostream& out, const std::vector<size_t>& map)
{
    REP(i, 0, map.size())
    {
        out << (map[i] == wall ? "¡" : "@");
    }

    out << std::endl;
}

void create_maze(const char* path, size_t n, size_t m)
{
    assert(n >= 1); assert(m >= 1);

    std::ofstream out(path);

    std::vector<size_t> areas(n); // identifers of areas

    REP(i, 0, n) areas[i] = i;

    std::vector<size_t> map(2 * n + 1, wall);

    print(out, map);

    for (--m; ; --m)
    {
        STEP(i, 1, 2 * n, 2) if (map[i] == wall)
        {
            assert(! areas.empty());

            map[i] = areas.back();

            areas.pop_back();
        }

        STEP(i, 2, 2 * n, 2) if (map[i - 1] != map[i + 1] && (m == 0 || random()))
        {
            const size_t old_area = map[i - 1];

            const size_t new_area = map[i + 1];

            areas.push_back(old_area);

            std::replace(map.begin(), map.end(), old_area, new_area); // caution! passed by reference

            map[i] = new_area;
        }

        print(out, map);

        if (m == 0)
        {
            break;
        }

        STEP(i, 2, 2 * n, 2)
        {
            map[i] = wall;
        }

        std::vector<size_t> count(n, 0);

        STEP(i, 1, 2 * n, 2)
        {
            ++count[map[i]];
        }

        STEP(i, 1, 2 * n, 2) if (count[map[i]] >= 2 && random())
        {
            --count[map[i]]; map[i] = wall;
        }

        print(out, map);
    }

    print(out, std::vector<size_t>(2 * n + 1, wall));
}

int main()
{
    std::srand(std::time(NULL));

    create_maze("result.txt", 1024, 1024);
}

最適化の余地があるというのは、アルゴリズムにではなく、私のコードに、です。念のため(^^;

C++, Pentium2 266MHzで30秒ですか。

私の使ったPentiumM 2100MHzとの性能差を約10倍とすると。
(クロック差8倍とメモリとかキャッシュとかで+2倍)
13秒ぐらいで生成できそうなんですが・・・。

あ、そういえば速度を計ったときには出力コードをコメント
にしてました。

純粋にバッファ操作の時間だけ計測すると何秒ぐらいになり
ますか？
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// こんな感じで。
void print(std::ostream& out, const std::vector<size_t>& map)
{
    REP(i, 0, map.size())
    {
//      out << (map[i] == wall ? "■" : "　");
    }

//  out << std::endl;
}

23秒でした。ていうか、私のコード、日本語部分が化けてますね。すみません（汗）

#日ごろ秀丸＋欧文フォントで組んでるので、そのままコピーペーストするとこうなる

> 23秒でした。

（・３・）アルェー？
速くなったけど13秒には及ばないですね。
いくつもあるループを統合したら改善するのかも。

-------------
　STEP(x) {
　	A
　}

　STEP(x) {
　	B
　}
-------------

　　↓

-------------
　STEP(x) {
　	A
　	B
　}
-------------

> #日ごろ秀丸＋欧文フォントで組んでるので、
> そのままコピーペーストするとこうなる

シブイ！
Courierでしょうか？

私はプロポーショナルフォント(英字Tahoma + 日本語MSUIGothic)で
プログラムしてます。
周りからは変態呼ばわりされてます(笑)
>速くなったけど13秒には及ばないですね。

うーん、コンパイラが違うとか。g++ -O2 でコンパイルしました。まあ、色々古いパソコンなので他にも原因があるかも。

>シブイ！
>Courierでしょうか？

Courier Newです（笑）

>私はプロポーショナルフォント(英字Tahoma + 日本語MSUIGothic)で
>プログラムしてます。
>周りからは変態呼ばわりされてます(笑)

・・・変態（ぼそ）(^^;

Index

Feed

Other

Link

Pathtraq

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