「絶対左折禁止」の迷路を解く(Ruby)


ブログにスターを頂いて、上のサイトを知りました。オリジナルの様々な迷路が出題されている、すばらしくおもしろそうなブログです。皆さんも御覧になってはいかがでしょうか?


…とは別にステマでも何でもないのですが、そこで「絶対左折禁止」という迷路が出題されているのが目に止まりました。こんなのです。リンク先を御覧下さい。
とまたよくない病が…。Ruby で解いてやろうというのですね。もしかしたら作者様には失礼に当たるかもしれません。であればどうかお許しください。


ルールとしては、もちろん交差路では左折してはいけませんが(直進と右折のみ)、角でも左に曲がってはいけないというものです。さて、どう解くか。迷路を交差路と角のつながりとして抽象化しようかと思いましたが、どうも面倒で、えいテキストエディタで入力だ! ということにしました(笑)。これがそうです。
maze_never_turn_left.txt

0000000000000000   00000000000
0 0 0 0 0 0 0
00S 0000000000000000 0 0
0 0 0 0 000000
0 0 000000 0 0
0 0000 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0000 00000 0 0 0 0
0 0 0 00000000000 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0000000000 0 00000000000
0 0 0 0 0 0 0
000000 00000000 00000000000
0 0 0 0 0
0 0 0 0 0
0 000000000000000000 00000000
0 0 0 0 0 0 0 0 0
0 000000 0 000000000000 0
0 0 0 0 0 0
0 00000000000000000 G00
0 0 0 0 0 0
0 0 0 0 0 0
00000000 0000000000000000000
ぽちぽちと手作業で入力しました。


とりあえず迷路はデータ化しました。あとは解くだけですね。コードはこんな風に出来上がりました。何の準備もなくいきあたりばったりにコーディングしたので、途中でかなりおかしなことをしていたりしました。完成させるのに数時間もかかってしまいました。
maze_never_turn_left.rb

class SolveMaze
  open("maze_never_turn_left.txt") {|io| @@field = io.readlines}
  @@field.map! {|f| " " + f.chomp + " "}
  a = [" " * @@field[0].size]
  @@field = a + @@field + a
  
  class Position
    def initialize(x, y, dir = nil, parent = nil)
      @x, @y = x, y
      @kind = get[y][x]
      @dir = dir
      @parent = parent
    end
    attr_reader :x, :y, :dir, :parent, :kind
    
    def neighbor
       result = []
       [[0, -1], [1, 0], [0, 1], [-1, 0]].each_with_index do |step, i|
          x = @x + step[0]
          y = @y + step[1]
          result << Position.new(x, y, i, self) if get[y][x] != " "
       end
       result
    end
    
    def get
      SolveMaze.class_variable_get(:@@field)
    end
    
    def finish
      result = [[@x, @y]]
      a = parent
      field = Marshal.load(Marshal.dump(get))
      loop do
        result << [a.x, a.y]
        break if a.kind == "S"
        field[a.y][a.x] = %w(↑ → ↓ ←)[a.dir]
        a = a.parent
      end
      #puts result.reverse.flatten.join(",")    #GIF画像作成用
      field.map {|x| x.gsub!("0", " ")}
      field.each {|x| puts x}
      #exit
    end
    
    def check
      a = self
      loop do
        a = a.parent
        return true if a.kind == "S"
        return false if a.x == @x and a.y == @y and a.dir == @dir
      end
    end
  end
  
  def initialize
    n = @@field.join.index("S")
    l = @@field[0].length
    @queue = Position.new(n % l, n / l).neighbor
  end
  
  def go
    while (po = @queue.shift)
      pos = po.neighbor.reject {|a| a.dir == (po.dir + 2) % 4}   #あと戻り以外に行ける場所
      pos.each do |nxt|
        next if (po.dir - nxt.dir) % 4 == 1       #左折禁止
        if nxt.kind == "G"
          nxt.finish
        elsif nxt.kind == "0" and (pos.size < 2 or nxt.check)
          @queue << nxt
        end
      end
    end
  end
end

SolveMaze.new.go

Position クラスは現在の位置の他、場所の種類(@kind)、どちらの方向から来たのか(@dir)とひとつ前の位置(@parent)の情報を保持しています。SolveMaze#go がメインループ、Position#check は無限ループしないかチェックしています。Position#neighbor は現在位置の周囲の情報を与えます。

結果です。解くのにかかった時間は自分の環境で 0.1秒未満です。

 ↑→→→→→→→→→→→→      ↑→→→→→→→→→→ 
↑ ↓ ↑ ↓
←←S ↑→→→↓→→→→→→→ ↓
↑ ↓ ↓ ↓
↑ ↓→→→ ↓ ↓
↑ ↓ ↓ ↓ ↓
↑ ↓ ↓ ↓ ↓
↑ ↓ ↓ ↓ ↓
↑ ↓←←←←←←↓→→→ ↓
↑ ↓ ↓ ↑ ↓ ↓
↑ ↓ ↓ ↑ ↓ ↓
←←←←↓ ↓ ←←←↓→→→→ ↓
↑ ↓ ↓ ↑ ↓ ↓
↑→→→→→ ←←←←←←←↓ ←←←←←←←←←←↓
↑ ↓ ↓ ↑ ↓
↑ ↓ ↓ ↑ ↓
↑ ↑→→↓→→→→→↓→→→→→→→→ ↑→→→↓→→→
↑ ↑ ↓ ↓ ↑ ↓ ↑ ↓ ↓
↑ ←↑→→→→ ↓ ←←←←↓ ←←←←↓ ↓
↑ ↑ ↓ ↓ ↓
↑ ←←←←←←←←↓ G←↓
↑ ↓
↑ ↓
←←←←←←←↓
正直いってちょっとわかりにくいですね。なので GIFアニメを作ってみました。
 

 
どうでしょうか。関連するすべてのコードは Gist にあります。
絶対左折禁止の迷路を解く · GitHub
 
なお、この迷路の解はひとつだけで、複数の解はありません(意味のないループを除く。)複数解があればすべて出力します。また、任意の「絶対左折禁止」の迷路が解ける筈です。(ただし、迷路をあらわすテキストファイルは、すべての行の長さを同じにして下さい。)

左折禁止ではない、任意の迷路を解くように改変するのも容易です。左折禁止を判断している一行を削除すればよろしい。ただし、すべての解を求めるのが冗長ならば、SolveMaze#finish メソッドの終わりに exit を追加すればよいです。その際はひとつの最短ステップの解を出力して終了します。なお、いまのままだと同じ地点を通っても向きがちがえば許容されるので、同じ地点を通らないようにするには Position#check メソッドの判定条件を変える必要があります。


作者様、楽しい迷路をありがとうございました!

与えられた迷路の最短経路を求める(Go言語)

以前 Ruby で解いたのの Go言語版です。Go言語のお勉強に移植してみました。

まずは実行結果。

$ go build solve_maze.go
$ time ./solve_maze
**************************
*S* *$$$$                *
*$* *$ *$ *************  *
*$*$$$* $  ************  *
*$$$ *  $$$$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$  *$$$$$$$$$$$$$$G  *
*  *$$$$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************

real	0m0.002s
user	0m0.000s
sys	0m0.000s

この程度ならじつに一瞬で解けますね。


もとの Ruby 版とちがうのは、まず迷路ファイルの読み込みが Ruby ほど楽でないこと。それから最短距離を求めるのに幅優先探索を使うので、キューを特に実装しなくてはいけません(しかしこれはここで解決)。あとはオブジェクト指向プログラミングができないので、そこらをどうするかですね。文字列処理は多少面倒でしたが、思ったほど厄介ではありませんでした。

やはりわかりにくかったのは構造体のポインタですね。でもこれは Go で必須なので、慣れないといけない。

コード。
solve_maze.go

package main
import ("fmt"; "os"; "bufio"; "strings")

var field []string

type Step struct {
    x, y int
    parent *Step
}

func err_exit(e error) {
    fmt.Println(e.Error())
    os.Exit(1)
}

func read_maze() {
    f, err := os.Open("maze.txt")
    if err != nil {err_exit(err)}
    
    defer f.Close()
    
    scanner := bufio.NewScanner(f)
    for scanner.Scan() {
        field = append(field, scanner.Text())
    }
    if err := scanner.Err(); err != nil {err_exit(err)}
}

func next_step(st *Step, i int) *Step {
    x, y := st.x, st.y
    switch i {
    case 0: y--
    case 1: y++
    case 2: x--
    case 3: x++
    }
    return &Step{x, y, st}
}

func get(st *Step) string {
    return field[st.y][st.x : st.x + 1]
}

func set(st *Step, char string) {
    s := field[st.y]
    field[st.y] = s[:st.x] + char + s[st.x + 1:]
}

func finish(st *Step) {
    for i, s := range field {
        field[i] = strings.Replace(s, "@", " ", -1)
    }
    for st.parent != nil {
        set(st, "$")
        st = st.parent
    }
    for _, s := range field {
        fmt.Println(s)
    }
    os.Exit(0)
}

func main() {
    read_maze()
    
    queue := []*Step{&Step{x: 1, y: 1}}
    for {
        step := queue[0]
        queue = queue[1:]
        
        for i := 0; i < 4; i++ {
            next := next_step(step, i)
            switch get(next) {
            case "G":
                finish(step)
            case " ":
                set(next, "@")
                queue = append(queue, next)
            }
        }
    }
}

maze.txt

**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************

 
やはり Go言語はコードが読みやすいですよね。


この本を買ってお勉強しています。ひと通り読みましたが、他言語の経験のある人ならとてもわかりやすいのではないでしょうか。いい本だと思います。

スターティングGo言語 (CodeZine BOOKS)

スターティングGo言語 (CodeZine BOOKS)

ある再帰曲線を描く(Ruby)

フィボナッチのうさぎ―数学探険旅行

フィボナッチのうさぎ―数学探険旅行

この本で言及されている再帰曲線を Ruby で描いてみました。何という名前なのか、はたして名前があるのか、よく知りません。

こんなです。左が 3次、右が 5次です。

 
描画には自作の Gem 'oekaki' を使いました。最新バージョンでタートルグラフィックスをサポートしています(参照)。
oekaki | RubyGems.org | your community gem host
GTK+でお絵かきしてみた(Ruby) - Camera Obscura
 
コード。

require 'oekaki'

Oekaki.app width: 420, height: 420, title: "Turtle" do
  draw do
    clear
    
    t = Oekaki::Turtle.new
    t.color(0, 0xffff, 0)
    
    drawing = lambda do |n, p1, p2|
      v1 = p2 - p1
      v2 = Vector[-v1[1], v1[0]]
      if n == 1
        l = v1.norm / sqrt(2)
        t.move(*p1.to_a)
        t.dir = v1.normalize
        t.left(45)
        t.forward(l)
        t.right(90)
        t.forward(l)
      else
        drawing[n - 1, v3 = p1 + v2 / 2, p1]
        drawing[n - 1, v3, v4 = v3 + v1 / 2]
        drawing[n - 1, v4, v5 = v4 + v1 / 2]
        drawing[n - 1, p2, v5]
      end
    end
    
    drawing[5, Vector[-200, -200], Vector[200, -200]]
  end
end

 

ゴシック・フリーズ(p.102~)。それぞれ 1, 2, 3, 6次。


 
コード。

require 'oekaki'

Oekaki.app width: 420, height: 420, title: "Turtle" do
  draw do
    clear
    
    t = Oekaki::Turtle.new
    t.color(0xffff, 0x45ff, 0)    #orangered
    t.move(-200, -200)
    t.left(45)
    
    drawing = lambda do |n, l|
      if n == 1
        t.forward(l)
      else
        drawing[n - 1, l / 3]
        t.left(90) 
        drawing[n - 1, l / 3] 
        t.right(90)
        drawing[n - 1, l / 3] 
        t.right(90)
        drawing[n - 1, l / 3] 
        t.left(90)
        drawing[n - 1, l / 3] 
      end
    end
    
    drawing[6, 400 * sqrt(2)]
  end
end

 
アニメーション版も作ってみました。コードはこちら

 

タートルグラフィックスによるその他の再帰曲線については、こちらもどうぞ。

急がば回れ(Ruby)

アルゴリズム・パズルです。
 

問題:
20180214012431
上のような規則があります。縦が 5cm、横が 6cm の長方形の場合、A から B までの最長経路は何 cm でしょうか。

 
Ruby で解いてみました。
q50.rb

W, H = 6, 5

def yoko?(y)
  @yoko[y].inject(:+) < 2
end

def tate?(x)
  @tate[x].inject(:+) < 2
end

def search(x, y, co)
  if x == W and y == H
    @max = co if co > @max
    return
  end
  if x < W and yoko?(y)
    @yoko[y][x] += 1
    search(x + 1, y, co + 1)
    @yoko[y][x] -= 1
  end
  if x > 0 and yoko?(y)
    @yoko[y][x - 1] += 1
    search(x - 1, y, co + 1)
    @yoko[y][x - 1] -= 1
  end
  if y < H and tate?(x)
    @tate[x][y] += 1
    search(x, y + 1, co + 1)
    @tate[x][y] -= 1
  end
  if y > 0 and tate?(x)
    @tate[x][y - 1] += 1
    search(x, y - 1, co + 1)
    @tate[x][y - 1] -= 1
  end
end

@tate = Array.new(W + 1) {Array.new(H, 0)}
@yoko = Array.new(H + 1) {Array.new(W, 0)}
@max = 0

search(0, 0, 0)
puts @max    #=>25

25 cm が答えです。自分の環境で 3.1 秒かかりました。ループの回数は 1513353 回です。
解法はごく素直に、再帰を使った深さ優先探索です。


ルートは全部で 805通りあります。すべての画像を出力するコードはこちら。 Gem 'cairo' を使っています。下は GIF化(参照)した画像です。

 

反転で作る互い違い(Ruby)

アルゴリズム・パズルです。

問題:
表が白で裏が黒の 16 枚のカードがあります。まず、これらを白と黒が 8 枚ずつ連続して見えるように円形に並べます。
そして、連続した 3 枚のカードを裏返していくことにします。適当な位置でこのように反転していくとき、すべてのカードが白と黒の互いちがいになるような手順の回数は、最小で何回で済むでしょうか。

 
Ruby で解いてみました。
q49.rb

mask = [14, 28, 56, 112, 224, 448, 896, 1792, 3584,
        7168, 14336, 28672, 57344, 49153, 32771]
15.times do |i|
  mask.combination(i + 1) do |m|
    field = 0b0000000011111000
    m.each do |x|
      field = field ^ x
      if field == 0b1010101010101010
        p [i + 2, m]    #=>[8, [14, 28, 448, 896, 14336, 28672, 57344]]
        exit
      end
    end
  end
end

答えは 8 回ですね。かかった時間は自分の環境で 0.084 秒でした。ループの回数は 59669 回です。
考え方としては、ビット演算で XOR を取ればビットが反転することを使っています。それから、ビットの反転の順序は答えに関係がないことがポイントです。円形というのは、一箇所を固定して横一列で考えればいいです。なので、始める前に適当に1箇所あらかじめ反転させておきます。


XOR でビットの反転というのは、こういうことですね。

[1] pry(main)> (0b01010101 ^ 0b111).to_s(2)
=> "1010010"

演算 ^ で XOR を取ります。01010101 の右3桁が反転しているのがわかります。
 

Go言語で汎用両端キューの実装

Go でキューの実装は、上記事で append を使って簡単にしています。なるほどと思いました。


ふつうはこれで充分ですよね。スタックは2本のキューで実装できるので、これも簡単です。しかし、任意の型を入れられるキュー、しかもメモリを効率よく使うキューがあれば便利かと思って、遊びで実装してみました。Go は3日前にさわり始めたばかりなので、おそらくはおかしなことをしていると思います。

queue.go

package main
import "fmt"
import "os"

const QueueMax = 100      //キューのサイズ
var qfield [QueueMax]interface{}    //実際に使う配列の宣言

type Queue struct {
    out int
    in  int
    length int
    field []interface{}
}

func (q *Queue) enqueue(obj interface{}) {
    if q.length == QueueMax {
       fmt.Println("Queue Overflow")
       os.Exit(1)
    }
    q.field[q.in] = obj
    q.in++
    q.length++
    if q.in == QueueMax {q.in = 0}
}

func (q *Queue) dequeue() (obj interface{}) {
    if q.length == 0 {return false}
    obj = q.field[q.out]
    q.out++
    q.length--
    if q.out == QueueMax {q.out = 0}
    return obj
}

どんな型でも入れられるように、空のインターフェースを使っています。
 
実際に使ってみます。わかりやすいように、const QueueMax = 2(長さ 2 の配列を使う)としています。

func main() {
    queue := &Queue{out: 0, in: 0, length: 0, field: qfield[:]}
    
    queue.enqueue(100)
    queue.enqueue("二百")
    fmt.Println(queue.field)       //=>[100 二百]
    fmt.Println(queue.dequeue())   //=>100
    fmt.Println(queue.field)       //=>[100 二百]
    queue.enqueue(300)
    fmt.Println(queue.field)       //=>[300 二百]
    fmt.Println(queue.dequeue())   //=>二百
    queue.enqueue([1]int{400})
    fmt.Println(queue.field)       //=>[300 [400]]
    fmt.Println(queue.dequeue())   //=>300
    fmt.Println(queue.dequeue())   //=>[400]
    fmt.Println(queue.dequeue())   //=>false
    fmt.Println(queue.dequeue())   //=>false
}

どうでしょうか。いろんな型が入り混じっていると思います。長さ 2 の配列を使っているのに、途中で dequeue しているので 4 回 enqueue できていますね。まあ遊びですが。
なお、空のキューに dequeue すると、エラーではなくて false を返します。キューが溢れるとエラー終了します。


ちなみに、上記事と同じ人の書いたこれも、ハマりやすいことをわかりやすく教えてくれるなあと思いました。
これも構造体とポインタの話でわかりやすかった。


※追記
pop() と shift() も加えて、両端キューにしてみました。

func (q *Queue) pop() (obj interface{}) {
    if q.length == 0 {return false}
    q.in--
    q.length--
    if q.in == -1 {q.in = QueueMax - 1}
    obj = q.field[q.in]
    return obj
}

func (q *Queue) shift(obj interface{}) {
    if q.length == QueueMax {
       fmt.Println("Queue Overflow")
       os.Exit(1)
    }
    q.out--
    q.length++
    if q.out == -1 {q.out = QueueMax - 1}
    q.field[q.out] = obj
}

メソッドの名前は言語によっていろいろです。上で enqueue() というのは push() がふつうですかね。shift() ってのはどうなのか知りませんが、僕は Ruby から採りました。
しかし、こうなると out, in ではなくて head, tail とでもしておけばよかったかな。


ここまでとりあえず、図書館から借りてきた下の本と Google 先生だけでやっています。まだゴルーチンとかわからない…。

改訂2版 基礎からわかる Go言語

改訂2版 基礎からわかる Go言語

Go は簡単だっていうけれど、ポインタとかあるしやはり初心者にはそんなに簡単でもない。「参照型」の考え方とかも必須だし。でも、やはり C よりははるかにラクですっきりしていますね。コードの見た目がすっきりしていて好きだ。必要ない記述は書かないでよいという態度がいいですね。DRY 精神として Ruby と似ている。
でも素人が3日でこの程度は書けるようになるから、やはり簡単なのかなあ…。

Go言語でじゃんけんゲーム

Go言語のお勉強にいつものじゃんけんゲームを作ってみました。こんなのでも悩みましたよ…。
janken.go(Gist

package main
import "fmt"
import "math/rand"
import "time"

type Player struct {
    name  string
    point byte
    hand  byte
}

func show_hand(hand byte) string {
    hn := [...]string{"グー", "チョキ", "パー"}
    return hn[hand - 1]
}

func judge(p1 *Player, p2 *Player) {
    h1, h2 := p1.hand, p2.hand
    fmt.Printf("%s 対 %s で ", show_hand(h2), show_hand(h1))
    var win *Player
    if h1 == h2 {
        fmt.Println("引き分けです。")
        return
    } else if (h2 - h1) % 3 == 2 {
        win = p2
    } else {
        win = p1
    }
    fmt.Printf("%sの勝ちです。\n", win.name)
    win.point++
}

func game(p1 *Player, p2 *Player, n int) {
    fmt.Printf("*** %d回戦 ***\n", n)
    
    p1.hand = 0
    p2.hand = 0
    
    for p1.hand < 1 || 3 < p1.hand {
        fmt.Printf("%sの手を入力して下さい(1:グー, 2:チョキ, 3:パー):", p1.name)
        fmt.Scanf("%d", &p1.hand)
    }
    p2.hand = byte(rand.Intn(3) + 1)
    
    judge(p1, p2)
}

func final_winner(p1 *Player, p2 *Player) {
    po1, po2 := p1.point, p2.point
    fmt.Println("\n*** 最終結果 ***")
    fmt.Printf("%d 対 %d で ", po2, po1)
    var win *Player
    if po1 == po2 {
        fmt.Println("引き分けです。")
        return
    } else if po1 > po2 {
        win = p1
    } else {
        win = p2
    }
    fmt.Printf("%sの勝ちです。\n", win.name)
}

func main() {
    rand.Seed(time.Now().UnixNano())
    
    man := &Player{point: 0}
    cpu := &Player{name: "Computer", point: 0}
    
    fmt.Print("あなたの名前を入力して下さい:")
    fmt.Scanf("%s", &man.name)
    fmt.Printf("%s 対 %s :じゃんけん開始\n\n", cpu.name, man.name)
    
    for i := 1; i <= 5; i++ {
        game(man, cpu, i)
    }
    
    final_winner(man, cpu)
}

 

過去のそれぞれ C言語C#Ruby での実装です。