rustedの日記 このページをアンテナに追加 RSSフィード

ruby勉強するよ。

2006-12-20

[][]Amazing Mazes (#31) 08:16 Amazing Mazes (#31) - rustedの日記 を含むブックマーク はてなブックマーク - Amazing Mazes (#31) - rustedの日記

今度は迷路の自動生成(とその解き方)(http://www.rubyquiz.com/quiz31.html)。

All nodes of the maze must be reachable from any point.

まず全てのノードに到達できるようにすること。これは生成後に移動可能な場所をチェックして、いっていないところがあったら穴をあけることで解決した。

Furthermore, let us enforce that only 1 viable solution for the maze exists for any given start/stop (you cannot reach the same destination from 2 different routes).

もう1つ注意点。ただ1つの解になるようにすること、ということなので環ができていたら埋めてみました。

生成した迷路を解くほうは再帰でサクっと書いてみた。

ソースstart/stopランダムで決定されるよ。

#!/usr/bin/ruby
# Amazing Mazes (#31)

class Maze
  LEFT = 1
  TOP = 2
  RIGHT = 4
  BOTTOM = 8
  def initialize(w, h)
    if h <= 0 || w <= 0
      raise 'error : invalid size'
    end
    @width = w
    @height = h
    @start = rand(@width * @height)
    @stop = rand(@width * @height)
    while @start == @stop
      @stop = rand(@width * @height)
    end
    @data = Array.new(@width * @height) { |i| 0 }
    @solve = Array.new(@width * @height) { |i| 0 }
  end
  
  def dig(i, d)
    if d == 0
      if i % @width != 0
        @data[i] |= LEFT
        @data[i - 1] |= RIGHT
      end
    elsif d == 1
      if i >= @width
        @data[i] |= TOP
        @data[i - @width] |= BOTTOM
      end
    elsif d == 2
      if i % @width != @width - 1
        @data[i] |= RIGHT
        @data[i + 1] |= LEFT
      end
    elsif d == 3
      if i < @width * @height - @width
        @data[i] |= BOTTOM
        @data[i + @width] |= TOP
      end
    end
  end
  
  def fill(i, d)
    if d == 0
      if i % @width != 0
        @data[i] &= ~LEFT
        @data[i - 1] &= ~RIGHT
      end
    elsif d == 1
      if i >= @width
        @data[i] &= ~TOP
        @data[i - @width] &= ~BOTTOM
      end
    elsif d == 2
      if i % @width != @width - 1
        @data[i] &= ~RIGHT
        @data[i + 1] &= ~LEFT
      end
    elsif d == 3
      if i < @width * @height - @width
        @data[i] &= ~BOTTOM
        @data[i + @width] &= ~TOP
      end
    end
  end
  
  def generate
    n = @width * @height
    list = Array.new(n) { |i| i }
    
    cnt = 0
    while cnt < 10000
      i = rand(n)
      j = rand(n)
      tmp = list[i]
      list[i] = list[j]
      list[j] = tmp
      cnt += 1
    end
    
    list.each_index { |i| 
      while !dig(i, rand(4))
      end
    }
  end
  
  def search(list, x, y, d)
    if(list[x + y * @width] == 1)
      fill(x + y * @width, d)
      return
    end
    list[x + y * @width] = 1
    
    if (d != 0) && (x > 0) && (@data[x + y * @width] & LEFT != 0)
      search(list, x - 1, y, 2)
    end
    if  (d != 1) && (y > 0) && (@data[x + y * @width] & TOP != 0)
      search(list, x, y - 1, 3)
    end
    if  (d != 2) && (x < @width - 1) && (@data[x + y * @width] & RIGHT != 0)
      search(list, x + 1, y, 0)
    end
    if  (d != 3) && (y < @height - 1) && (@data[x + y * @width] & BOTTOM != 0)
      search(list, x, y + 1, 1)
    end
  end
  
  def check
    list = Array.new(@width * @height) { |i| 0 }
    search(list, rand(@width), rand(@height), -1)
    
    dig_list = Array.new
    list.each_index { |i|
      if list[i] == 0
        dig_list.push(i)
      end
    }
    
    if dig_list.size > 0
      while !dig(dig_list[rand(dig_list.size)], rand(4))
      end
      return false
    end
    return true
  end
  
  def solve(x, y, d)
    if @stop == x + y * @width
      return true
    end
    
    if (d != 0) && (x > 0) && (@data[x + y * @width] & LEFT != 0) && (solve(x - 1, y, 2))
      @solve[x + y * @width] = 1
      return true
    end
    if  (d != 1) && (y > 0) && (@data[x + y * @width] & TOP != 0) && (solve(x, y - 1, 3))
      @solve[x + y * @width] = 1
      return true
    end
    if  (d != 2) && (x < @width - 1) && (@data[x + y * @width] & RIGHT != 0) && (solve(x + 1, y, 0))
      @solve[x + y * @width] = 1
      return true
    end
    if  (d != 3) && (y < @height - 1) && (@data[x + y * @width] & BOTTOM != 0) && (solve(x, y + 1, 1))
      @solve[x + y * @width] = 1
      return true
    end
    return false
  end
  
  def solving_maze
    solve(@start % @width, @start / @width, -1)
  end
  
  def print_maze
    y = 0
    while y < @height
      if y == 0
        x = 0
        while x < @width
          if x == 0
            print "+"
          end
          if @data[x + y * @width] & TOP != 0
            print " "
          else
            print "+"
          end
          print "+"
          x += 1
        end
        print "\n"
      end
      x = 0
      while x < @width
        if x == 0
          if @data[x + y * @width] & LEFT != 0
            print " "
          else
            print "+"
          end
        end
        if @start == x + y * @width
          print "S"
        elsif @stop == x + y * @width
          print "P"
        elsif @solve[x + y * @width] == 1
          print "."
        else
          print " "
        end
        if @data[x + y * @width] & RIGHT != 0
          print " "
        else
          print "+"
        end
        x += 1
      end
      print "\n"
      x = 0
      while x < @width
        if x == 0
          print "+"
        end
        if @data[x + y * @width] & BOTTOM != 0
          print " "
        else
          print "+"
        end
        print "+"
        x += 1
      end
      print "\n"
      y += 1
    end
  end
end

m = Maze.new((ARGV[0] || 8).to_i, (ARGV[1] || 8).to_i)
m.generate
while !m.check
end
m.print_maze
m.solving_maze
m.print_maze

実行!

$ ruby maze.rb
+++++++++++++++++
+ +P  + +       +
+ +++ + +++ +++ +
+     +  S    + +
+ +++++++++++++ +
+ +   + +   +   +
+ + +++ +++ + + +
+     +       + +
+ +++ +++ + +++++
+ +     + +     +
+ +++ + +++ + +++
+   + +     + + +
+++ + +++++++++ +
+   +   +     + +
+++ + +++ +++ + +
+   +     +     +
+++++++++++++++++
+++++++++++++++++
+ +P .+ +  . . .+
+ +++ + +++ +++ +
+. . .+  S .  +.+
+ +++++++++++++ +
+.+   + +   +. .+
+ + +++ +++ + + +
+. . .+    . .+ +
+ +++ +++ + +++++
+ +  . .+ +.    +
+ +++ + +++ + +++
+   + +. . .+ + +
+++ + +++++++++ +
+   +   +     + +
+++ + +++ +++ + +
+   +     +     +
+++++++++++++++++

できた!

AnibalAnibal2012/05/24 02:12I thuoght finding this would be so arduous but it's a breeze!

qpdovwpikcoqpdovwpikco2012/05/24 11:311Y3tEJ <a href="http://htkvrnwrcwuo.com/">htkvrnwrcwuo</a>

vunjvpvunjvp2012/05/25 15:067ERx6q , [url=http://ixlmsvaujdex.com/]ixlmsvaujdex[/url], [link=http://savglgtqnctc.com/]savglgtqnctc[/link], http://yqfetetzdsph.com/

pnuzxeegeppnuzxeegep2012/05/25 17:11AbH2wG , [url=http://kjlildmopokz.com/]kjlildmopokz[/url], [link=http://wbgnuqliopsu.com/]wbgnuqliopsu[/link], http://cibtscycnbwg.com/

zropusqzropusq2012/05/25 19:295x90up , [url=http://lwlqwbzgxyor.com/]lwlqwbzgxyor[/url], [link=http://sihwpywrrdrz.com/]sihwpywrrdrz[/link], http://zqefsciumrcj.com/

juucrfjxqjuucrfjxq2012/05/26 15:19TtvI89 <a href="http://kldbcjvczieo.com/">kldbcjvczieo</a>

2006-10-19

[]csv 22:45 csv - rustedの日記 を含むブックマーク はてなブックマーク - csv - rustedの日記

Comma Separated Valueのほう。CSVクラスを使って操作してみる。サクっとできた。

require 'CSV'

CSV.open(ARGV[0], "r") do |row|
  row.each_index { |x| print "X", x, "=", row[x], "\n" }
end

GregGreg2007/02/05 03:59If you wanna stop guestbook spammers just confirm url of this page to anti.spam.police@gmail.com with subject:ANTISPAM. Thx.

Greg NilsonGreg Nilson2007/02/05 16:55If you wanna stop guestbook spammers just confirm url of this page to anti.spam.police@gmail.com with subject:ANTISPAM. Thx.

NdazionaNdaziona2012/08/04 15:46This is a most useful contribution to the dbetae

mnlhafgmrmnlhafgmr2012/08/05 15:15KzApEq <a href="http://uagwakanijxn.com/">uagwakanijxn</a>

2006-10-07

[]Array.each_index { |i| ... } 10:56 Array.each_index { |i| ... } - rustedの日記 を含むブックマーク はてなブックマーク - Array.each_index { |i| ... } - rustedの日記

while文を延々と使ってきたけど、c言語のfor文のように使えるものも当然あったのでした。

a.each_index { |i| a[i].no = i}

2006-09-27

[]Array.delete_if 20:55 Array.delete_if - rustedの日記 を含むブックマーク はてなブックマーク - Array.delete_if - rustedの日記

ブロックの結果が真になった要素を全て削除する。

@grid.delete_if { |g| g.size != size }

ここではgが@gridの各要素になる。

MehwashMehwash2012/08/04 17:46God, I feel like I shloud be takin notes! Great work

wdobbywdobby2012/08/05 15:31UBooIV <a href="http://pvpaeyylytjv.com/">pvpaeyylytjv</a>

dvscflhpnjbdvscflhpnjb2012/08/05 21:12AS7eZQ , [url=http://pvuaczrmcykq.com/]pvuaczrmcykq[/url], [link=http://hdhgakiplaku.com/]hdhgakiplaku[/link], http://lamrbcgdhjsj.com/

rckaspyftabrckaspyftab2012/08/07 19:16fuuI4q , [url=http://pdkmyzuonynf.com/]pdkmyzuonynf[/url], [link=http://rsiviblsvhjn.com/]rsiviblsvhjn[/link], http://asddjzpsgucz.com/

2006-09-23

[][]Grid Folding (#63) 22:29 Grid Folding (#63) - rustedの日記 を含むブックマーク はてなブックマーク - Grid Folding (#63) - rustedの日記

16×16サイズの紙を指定されたコマンドで半分ずつ折っていく問題(http://www.rubyquiz.com/quiz63.html)。最終的に1×1サイズになったところで、グリッドについていた番号を上から並べて出力する。

この例がわかりやすい。

12

34

fold("RB") => [3, 4, 2, 1]

fold("TL") => [3, 1, 2, 4]

fold("LR") => raise exception for invalid input

コマンドは"T"(上辺を下辺に合わせるように折る。折った後、上辺側が上になる)、"B"(下辺を上辺に~)、"L"(左辺を右辺に~)、"R"(右辺を左辺に~)の4つ。折ったときに上になるほうは並びが反転するけど、下になるほうはそのままなことに注意する必要があるかな。

Extra credit: Make your fold function take an additional input parameter(s), the dimensions of the paper; dimensions should be power-of-2 in order to fold down to one cell.

サイズを指定できるようにするといいらしい。あと最終的に1つのマスにたたみこむために、1辺の長さを2の累乗にするべきとのこと。

今回のソース

#!/usr/bin/ruby
# Grid Folding (#63)

class Paper
  def initialize(n)
    i = 2
    while i != n
      if i > n
        raise "invalid dimension"
      end
      i *= 2
    end
    @width = n
    @height = n
    @grid = Array.new(n * n)
    i = 0
    while i < @grid.size
      @grid[i] = [ i + 1 ]
      i += 1
    end
  end

  def pos(x, y)
    return x + y * @width
  end

  def to_bottom
    if @height == 1
      raise "invalid input"
    end
    size = @grid[0].size * 2
    x = 0
    y = @height / 2
    while y < @height
      while x < @width
        i = pos(x, @height - 1 - y) 
        @grid[i] = @grid[i].reverse
        @grid[pos(x, y)] = @grid[i] + @grid[pos(x, y)]
        x += 1
      end
      x = 0
      y += 1
    end    
    @grid.delete_if { |g| g.size != size }
    @height = @height / 2
  end
  
  def to_top
    if @height == 1
      raise "invalid input"
    end
    size = @grid[0].size * 2
    x = 0
    y = 0
    while y < @height / 2
      while x < @width
        i = pos(x, @height - 1 - y)
        @grid[i] = @grid[i].reverse
        @grid[pos(x, y)] = @grid[i] + @grid[pos(x, y)]
        x += 1
      end
      x = 0
      y += 1
    end
    @grid.delete_if { |g| g.size != size }
    @height = @height / 2
  end

  def to_right
    if @width == 1
      raise "invalid input"
    end
    size = @grid[0].size * 2
    x = @width / 2
    y = 0
    while y < @height
      while x < @width
        i = pos(@width - 1 - x, y)
        @grid[i] = @grid[i].reverse
        @grid[pos(x, y)] = @grid[i] + @grid[pos(x, y)]
        x += 1
      end
      x = @width / 2
      y += 1
    end
    @grid.delete_if { |g| g.size != size }
    @width = @width / 2
  end
  
  def to_left
    if @width == 1
      raise "invalid input"
    end
    size = @grid[0].size * 2
    x = 0
    y = 0
    while y < @height
      while x < @width / 2
        i = pos(@width - 1 - x, y)
        @grid[i] = @grid[i].reverse
        @grid[pos(x, y)] = @grid[i] + @grid[pos(x, y)]
        x += 1
      end
      x = 0
      y += 1
    end
    @grid.delete_if { |g| g.size != size }
    @width = @width / 2
  end

  def fold(str)
    while str.size > 0
      case str
      when /\AT/o
        to_bottom
      when /\AB/o
        to_top
      when /\AL/o
        to_right
      when /\AR/o
        to_left
      when /\A./o
        raise "invalid input"
      end
      str = $'
    end
    return @grid.first
  end
end

paper = Paper.new((ARGV[1] || 16).to_i)
p paper.fold(ARGV[0] || "")

実行結果。

$ ./grid_folding.rb "RBLT" 4
[2, 3, 15, 14, 13, 16, 4, 1, 5, 8, 12, 9, 10, 11, 7, 6]
$ ./grid_folding.rb "RBLTRT" 8
[19, 22, 46, 43, 42, 47, 23, 18, 10, 15, 55, 50, 51, 54, 14, 11, 12, 13, 53, 52, 
49, 56, 16, 9, 17, 24, 48, 41, 44, 45, 21, 20, 28, 29, 37, 36, 33, 40, 32, 25, 
1, 8, 64, 57, 60, 61, 5, 4, 3, 6, 62, 59, 58, 63, 7, 2, 26, 31, 39, 34, 35, 38, 
30, 27]
$ ./grid_folding.rb "LLLLBBBB" 16
[32, 17, 24, 25, 28, 21, 20, 29, 30, 19, 22, 27, 26, 23, 18, 31, 239, 226, 231, 
234, 235, 230, 227, 238, 237, 228, 229, 236, 233, 232, 225, 240, 160, 145, 152, 
153, 156, 149, 148, 157, 158, 147, 150, 155, 154, 151, 146, 159, 111, 98, 103, 
106, 107, 102, 99, 110, 109, 100, 101, 108, 105, 104, 97, 112, 96, 81, 88, 89, 92, 
85, 84, 93, 94, 83, 86, 91, 90, 87, 82, 95, 175, 162, 167, 170, 171, 166, 163, 
174, 173, 164, 165, 172, 169, 168, 161, 176, 224, 209, 216, 217, 220, 213, 212, 
221, 222, 211, 214, 219, 218, 215, 210, 223, 47, 34, 39, 42, 43, 38, 35, 46, 45, 
36, 37, 44, 41, 40, 33, 48, 64, 49, 56, 57, 60, 53, 52, 61, 62, 51, 54, 59, 58, 
55, 50, 63, 207, 194, 199, 202, 203, 198, 195, 206, 205, 196, 197, 204, 201, 
200, 193, 208, 192, 177, 184, 185, 188, 181, 180, 189, 190, 179, 182, 187, 186, 
183, 178, 191, 79, 66, 71, 74, 75, 70, 67, 78, 77, 68, 69, 76, 73, 72, 65, 80, 
128, 113, 120, 121, 124, 117, 116, 125, 126, 115, 118, 123, 122, 119, 114, 127, 
143, 130, 135, 138, 139, 134, 131, 142, 141, 132, 133, 140, 137, 136, 129, 144, 
256, 241, 248, 249, 252, 245, 244, 253, 254, 243, 246, 251, 250, 247, 242, 255, 
15, 2, 7, 10, 11, 6, 3, 14, 13, 4, 5, 12, 9, 8, 1, 16]

できた??サイズ4×4ではできているはず。チェック関数も実装する必要があるかな。