DouKaku?beta

challenge ライフゲーム 

セルオートマトンに関するお題です. 
2次元タイプの'ライフゲーム'を実装して下さい. 
初期値としては10行10列程度の格子上の平面に0.3程度の人口(?)密度を考え, 
末端はループするようにして下さい. (例: 座標[-1, -1] = [10, 10])

それだけだと簡単すぎると思われる方は, 
過密状態で間引きが発生するような機能を組み込んで下さい. 
間引きは, 少なくともその後の1時間ステップにおける死亡率が, 
それをしなかった場合よりも小さくなれば結構です. 
(死亡率の最小化は複雑性が高すぎる感がありますし. )
サンプル:
t = 0
[ ][*][ ][ ][ ][ ][*][*][*][ ]
[ ][ ][ ][ ][*][ ][ ][*][*][ ]
[ ][ ][ ][*][ ][ ][*][ ][*][ ]
[*][ ][*][*][ ][ ][*][ ][ ][ ]
[ ][*][ ][ ][ ][ ][ ][ ][*][ ]
[*][ ][ ][ ][*][ ][*][*][ ][*]
[ ][*][ ][ ][ ][ ][*][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ][ ][*]
[*][ ][ ][ ][ ][ ][*][ ][ ][*]
[ ][ ][ ][ ][*][*][ ][ ][*][ ]
t = 1
[ ][ ][ ][ ][*][ ][ ][ ][ ][*]
[ ][ ][ ][ ][ ][*][ ][ ][ ][*]
[ ][ ][*][ ][*][*][*][ ][*][*]
[ ][*][ ][*][ ][ ][ ][ ][ ][*]
[ ][ ][*][*][ ][*][*][ ][*][ ]
[ ][*][ ][ ][ ][*][*][ ][*][*]
[ ][ ][ ][ ][ ][*][*][*][*][*]
[ ][ ][ ][ ][ ][ ][ ][ ][ ][*]
[*][ ][ ][ ][ ][*][ ][ ][*][ ]
[*][ ][ ][ ][ ][ ][ ][ ][ ][ ]

see: Wikipedia:ライフゲーム

post comment

Posted feedbacks - Ruby

ライフゲームとは関係ないところで妙な小細工

  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
require 'curses'
require 'enumerator'

class Object
  def make_instance_variables (_binding)
    eval(<<'EOC', _binding)
      local_variables.each do
        |lv_name|
        instance_variable_set("@#{lv_name}", eval(lv_name))
      end
EOC
  end
end

class World
    attr_reader :height, :width, :rate

    def initialize (height, width, rate)
        make_instance_variables(binding)
        @cells = Array.new(height * width) { rand < rate }
    end

    def [] (x, y)
        @cells[fix_position(x, y)]
    end

    def []= (x, y, v)
        @cells[fix_position(x, y)] = v
    end

    def livings (x, y)
        result = 0
        (-1..1).each {|dy| (-1..1).each {|dx| result += 1 if self[x + dx, y + dy] unless dx == 0 and dy == 0 }}
        result
    end

    def update
        @cells = @cells.dup.enum_for(:each_with_index).map do
            |l, idx|
            x, y = idx % width, idx / width
            ls = livings(x, y)
            if l  
                (2..3) === ls
            else
                ls == 3
            end
        end
    end

    def inspect
        @cells.map {|it| "[#{it ? '*' : ' '}]" }.join.gsub(/.{#{3*width}}/){|it| "#{it}\n" }
    end

    private

    def fix_position (x, y)
        y % width * width + x % height
    end
end

class OptionParser
    def self.parse (args)
        require 'ostruct'
        require 'optparse'

        options = OpenStruct.new
        options.population = 0.3
        options.interval = 0.5
        options.height = options.width = 10

        parser = OptionParser.new do
            |parser|
            parser.banner = "Usage: #{File.basename($0)} [options] "
            parser.on('-p', '--population-rate [RATE]') { |it| options.population = it.to_f }
            parser.on('-i', '--interval [SEC]') { |it| options.interval = it.to_f }
            parser.on('-w', '--width [WIDTH]') { |it| options.interval = it.to_f }
            parser.on('-h', '--height [HEIGHT]') { |it| options.interval = it.to_f }
        end

        parser.parse!(args)
        options
    rescue
        puts parser.help
        exit
    end
end

options = OptionParser.parse(ARGV)

w = World.new(options.width, options.height, options.population) 

Curses.init_screen
loop do
    Curses.clear
    Curses.addstr(w.inspect)
    Curses.refresh
    sleep(options.interval)
    w.update
end
Curses.close_screen


死ぬことが予想されるセルを殺して, 周囲のセルを活かました. 
生存率は2-3倍ほどに上昇. 
行を減らすために`and'を利用してやたら文を連結してますが, 
結合度については考慮しているので, セミコロンに置き替えて読んで下さっても
同じことです. 

 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
require 'Matrix'
require 'kconv'
N, M = 10, 10
Density = 0.7
class CellMatrix
  Lived, Died = '[*]', '[ ]'
  Threshold = 4 and ModerateDensity = 0.5
  def initialize(n, m, &block)
    @cell_matrix = Array.new(n){|i| Array.new(m){|j| block_given? ? (yield [i, j]) : 0}}
    @time, @victim = 0, 0
  end
  def gen_seed(n)
    i, j = rand(r_size), rand(c_size)
    live(i,j) && n -= 1 if at(i,j) == 0
    gen_seed(n) if n > 0
  end
  def step
    env_mat = get_env and each{|i,j|
      case at(i,j)
      when 0: live(i,j) if env_mat.at(i,j) == 3
      when 1: die(i,j)  if env_mat.at(i,j) != 2..3
      end
    } and @time += 1
  end
  def thin_out #間引き
    env_mat = get_env and each{|i,j|
      max = {:pos => [], :value => 0} and env_mat.scan_env(i,j){|k,l|
        max[:pos] = [k,l] and max[:value] = env_mat.at(k,l) if env_mat.at(k,l) > max[:value]
      }
      kill(*max[:pos]) and @victim += 1 if max[:value] >= Threshold and at(*max[:pos]) == 1
    } and remain <= r_size * c_size * ModerateDensity ? true : thin_out
  end
  def dup; CellMatrix.new(r_size, c_size){|i,j| at(i,j)} end
  def remain; count = 0 and each{|i,j| count += at(i,j)} and count end
  def output(comment="")
    puts "t = #{@time} Remain: #{remain}, Victim: #{@victim} ##{comment}\n#{out}\n".tosjis
  end
  protected
  def at(i,j) @cell_matrix[i][j] end
  def each(&block) r_size.times{|i| c_size.times{|j| yield [i,j]}} end
  def scan_env(i, j, &block)
    a = [i == 0 ? r_size - 1 : i-1, i, i == r_size - 1 ? 0 : i+1]
    b = [j == 0 ? c_size - 1 : j-1, j, j == c_size - 1 ? 0 : j+1]
    a.each{|k| b.each{|l| yield [k,l] unless k == i && l == j}}
  end
  private
  def out; @cell_matrix.map{|line| "#{line.map{|x| x == 0 ? Died : Lived}.join}\n"}.join end
  def r_size;   @cell_matrix.size end
  def c_size;   @cell_matrix.first.size end
  def live(i,j) @cell_matrix[i][j] = 1 end
  def die(i,j)  @cell_matrix[i][j] = 0 end
  alias :kill :die
  def get_env #周囲のセルの状態
    CellMatrix.new(r_size, c_size){|i,j|
      count = 0 and scan_env(i,j){|k,l| count += at(k,l)} and count
    }
  end
end
real = CellMatrix.new(N, M)
initial = (N*M*Density).to_i
real.gen_seed(initial)
real.output('過密状態')
virtual = real.dup and virtual.step
virtual.output('間引きなし')
real.thin_out and real.step
real.output('間引きあり')

ライフゲームは初めて実装しましたが、面白いものですねえ。

LifeGame::Board#drawメソッドが気持ち悪いのですが、とりあえず投稿します。本当はLifeGame::Board#to_sの結果を画面に描画するほうが良いのですが‥‥。

 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
#!/usr/bin/env ruby

require 'curses'

module LifeGame
  class Board
    def initialize(board)
      @board = board
    end

    def width
      @board.map {|i| i.size }.max
    end

    def height
      @board.size
    end

    def check(x, y)
      @board[y][x]
    end

    def set(x, y, cell)
      @board[y][x] = cell
    end

    def draw(window)
      (1..(height)).each do |i|
        window.setpos(i, 1)
        window.addstr(@board[i - 1].join)
        window.refresh
      end
    end

    def to_s
      @board.map {|i| i.join }.join("\n")
    end

    def next
      result = Board.new(Array.new(height).map { Array.new(width) })
      (-1..(height - 2)).each do |j|
        (-1..(width - 2)).each do |i|
          result.set(i, j, next_life(check(i, j),
            [check(i - 1, j - 1),
             check(i, j - 1),
             check(i + 1, j - 1),
             check(i - 1, j),
             check(i + 1, j),
             check(i - 1, j + 1),
             check(i, j +1 ),
             check(i + 1, j + 1)]))
        end
      end
      result
    end

    private
    def next_life(cell, arrownd = [])
      case
      when (cell == ' ') && (arrownd.grep(/\*/).size == 3)
        '*'
      when (cell == '*') && (arrownd.grep(/\*/).size.between?(2, 3))
        '*'
      else
        ' '
      end
    end
  end
end

if __FILE__ == $0
  begin
    board = LifeGame::Board.new([
      [' ', '*', ' ', ' ', ' ', ' ', '*', '*', '*', ' '],
      [' ', ' ', ' ', ' ', '*', ' ', ' ', '*', '*', ' '],
      [' ', ' ', ' ', '*', ' ', ' ', '*', ' ', '*', ' '],
      ['*', ' ', '*', '*', ' ', ' ', '*', ' ', ' ', ' '],
      [' ', '*', ' ', ' ', ' ', ' ', ' ', ' ', '*', ' '],
      ['*', ' ', ' ', ' ', '*', ' ', '*', '*', ' ', '*'],
      [' ', '*', ' ', ' ', ' ', ' ', '*', ' ', ' ', ' '],
      [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '*'],
      ['*', ' ', ' ', ' ', ' ', ' ', '*', ' ', ' ', '*'],
      [' ', ' ', ' ', ' ', '*', '*', ' ', ' ', '*', ' ']])
    time = 0
    window = Curses::Window.new(Curses.lines, Curses.cols, 0, 0)
    sub_window = window.subwin(board.height + 2, board.width + 2, 2, 2)
    sub_window.box(?|, ?-, ?+)
    loop do
      window.setpos(0, 0)
      window.addstr("t = #{time}")
      board.draw(sub_window)
      window.getch
      time += 1
      board = board.next
    end
  ensure
    window.close
  end
end

何か適当なキーをぽちぽちすると世代が進みます。 生きているセルの周りをスコア付けして、維持・誕生・消滅の判断をしています。 テストコードを書いてないので合っているかちょっと不安ですが・・・

 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
require 'curses'

module LifeWorld
  class World
    def initialize(map)
      @map = map
    end

    def to_s 
      str = ""
      @map.each do |line|
        line.each do |cell|
          str += "[#{cell}]"
        end
        str += "¥n"
      end

      str
    end

    def next 
      ranking.each_with_index do |line, h|
        @map[h] = line.map {|cell| [3, 12, 13].include?(cell) ? '*' : ' ' }
      end
    end

    private
    def live_list
      list = []
      @map.each_with_index do |line, h|
        line.each_with_index {|cell, w| list << [h,w] if cell == '*'}
      end

      list
    end

    def set_score(rank_map, live)
      (-1..1).each do |x|
        (-1..1).each do |y|
          score = x == y && y  == 0 ? 10 : 1
          rank_map[live[0]+x][live[1]+y] = rank_map[live[0]+x][live[1]+y] + score
        end
      end
    end

    def ranking
      rank_map = List.new
      @map.size.times { rank_map << List.new(@map[0].size, 0) }

      live_list.each do |live|
        set_score(rank_map.clone, live)
      end

      rank_map
    end
  end

  class List < Array
    alias original_get []
    alias original_set []=

      def [](index)
        original_get(index % size)
      end

    def []=(index, value)
      original_set(index % size, value)
    end
  end
end

if __FILE__ == $0
  begin
    game = LifeWorld::World.new([
                                [' ', '*', ' ', ' ', ' ', ' ', '*', '*', '*', ' '],
                                [' ', ' ', ' ', ' ', '*', ' ', ' ', '*', '*', ' '],
                                [' ', ' ', ' ', '*', ' ', ' ', '*', ' ', '*', ' '],
                                ['*', ' ', '*', '*', ' ', ' ', '*', ' ', ' ', ' '],
                                [' ', '*', ' ', ' ', ' ', ' ', ' ', ' ', '*', ' '],
                                ['*', ' ', ' ', ' ', '*', ' ', '*', '*', ' ', '*'],
                                [' ', '*', ' ', ' ', ' ', ' ', '*', ' ', ' ', ' '],
                                [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '*'],
                                ['*', ' ', ' ', ' ', ' ', ' ', '*', ' ', ' ', '*'],
                                [' ', ' ', ' ', ' ', '*', '*', ' ', ' ', '*', ' ']])

    window = Curses::Window.new(Curses.lines, Curses.cols, 0, 0)
    loop do
      window.setpos(0, 0)
      window.addstr(game.to_s)
      game.next 
      window.getch
    end
  ensure
    window.close
  end
end

Index

Feed

Other

Link

Pathtraq

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