Gem 'Ruby2D' でライフゲーム

いつもの得意技（？）のライフゲームです。Ruby 用のグラフィック・ライブラリ 'Ruby2D' を使っています。

コード。
lifegame_for_Ruby2D.rb

require 'ruby2d'
include Ruby2D::DSL

class LifeGame
  CellWidth = 10
  Margin = 20
  Space = 2
  SideWidth = 35
  W = CellWidth * SideWidth + Space * (SideWidth - 1) + Margin * 2
  
  def initialize(num)
    set width: W, height: W, title: "LifeGame", fps_cap: 3
    
    cells = SideWidth.times.map do |y|
      SideWidth.times.map do |x|
        Square.new x: Margin + (CellWidth + Space) * x,
                   y: Margin + (CellWidth + Space) * y,
                   size: CellWidth,
                   color: Color.new([rand, rand, rand, 1.0]),
                   z: 0
      end
    end
    each_cell {|x, y| cells[y][x].remove}
    
    f = [1] * num + [0] * (SideWidth ** 2 - num)
    f.shuffle!
    @field = f.each_slice(SideWidth).to_a
    
    clear
    
    update do
      each_cell do |x, y|
        @field[y][x].nonzero? ? cells[y][x].add : cells[y][x].remove
      end
      next_field
    end
  end
  
  def each_cell
    SideWidth.times {|y| SideWidth.times {|x| yield(x, y)} }
  end
  
  def next_field
    tmp = Array.new(SideWidth) {Array.new(SideWidth, 0)}
    each_cell do |x, y|
      num = neighbor(x, y)
      if @field[y][x].nonzero?
        tmp[y][x] = 1 if num == 2 or num == 3
      else
        tmp[y][x] = 1 if num == 3
      end
    end
    @field = tmp
  end
  
  def neighbor(x, y)
    dirs = [[1, 0], [1, -1], [0, -1], [-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 1]]
    dirs.map do |dx, dy|
      x1 = x + dx
      y1 = y + dy
      next if x1 < 0 or x1 >= SideWidth
      next if y1 < 0 or y1 >= SideWidth
      @field[y1][x1]
    end.compact.inject(&:+)
  end
  
  def go
    show
  end
end

LifeGame.new(250).go

ちょっとチュートリアルだけではわからないところがあったので、ソースコードを見る必要がありました。まずクラスの中で Ruby2D のメソッドをどう使ったらよいかで、これは最初に include Ruby2D::DSL を宣言しておくことで解決（他の方法もあります）。それから、メソッド update のブロックの中で状態がその都度更新されるのですが、そのフレーム数の指定はどうすればよいか。これはメソッド set のキーワード引数で :fps_cap で指定してやればできることがわかりました。なお、ソースコードはとても読みやすいものでした。
　
'Ruby2D' については以下で紹介しています。
obelisk.hatenablog.com
　

上とは関係のないどうでもいいこと

Ruby は型の指定がないのでコードが読みにくいという根強い意見がありますが、たぶんこれではないかと。

• そもそもそのコード自体が読みにくい、クソなものである → Ruby のコードは一般にシンプルで短めなので、さっと読むのは楽な方です
• 全体のコードが長すぎて読みにくい → ソースファイルを分割する必要がある
• Ruby にはジェネリクスがない → Ruby の書き方を知らないにもほどがある

なお、これらはじつは他の言語にも応用できることです。別に Ruby は完璧な言語ではありませんが、実用的な（といってもまあいろいろでしょうけれど）言語としては非常によくできたものです。オブジェクト指向言語としてはもっともよくできたもののひとつでしょうし、クロージャ、第一級関数もサポートしており、関数型プログラミングのエッセンスも詰まっています。初心者にもやさしいですし、高度なプログラミングのできるプログラマにはそれなりの優れた書き方ができます。あんまり知らないでバカにするのはやめましょう。

僕は Ruby 以外では Go が結構好きなので（ソースコードの見た目が好きです笑）、Ruby と Go が連携できるような仕組みを作って欲しいのですけれど…。C言語がうまく書けるようになるのはなかなか大変…。

それから、「デザインパターンはオワコン」という意見も見ましたが、オワコンであろうが知っておいた方がよいと思います。純粋にプログラミング技術としておもしろいものです。最近はプロのプログラマの絶対数が増えたので、プロであり自信満々でもじつはよくわかっていない人も多いですから、我々素人のプログラミング好きは気をつけたいものです。

しかし、Python や Perl で型の指定がないので読みにくいという意見は、ほとんど目にしたことがないのだが…。

Gem 'Ruby 2D' で遊ぶ（1）

　
Ruby でグラフィック表示のできる Gem 'Ruby 2D' で遊んでみました。アニメーションをしています。三角が丸たちの上にあります。色は半透明になっています。
コード。
ruby2d_sample2.rb

require 'ruby2d'

Width = 500
C = 15    #円の数
R = 20    #円の半径

L = 150   #三角形の一辺の長さ

set width: Width, height: Width

circles = C.times.map {
  Circle.new x: rand(R..Width - R), y: rand(R..Width - R),
     radius: R, color: Color.new([rand, rand, rand, 0.8]), z: 0
}
cvs = circles.map {[rand(-3.0..3.0), rand(-3.0..3.0)]}    #円の移動ベクトル

triangle = 4.times.map {|i|
  cn = Width / 2.0
  xs = [cn - L / 2.0, cn + L / 2.0]
  height = L * 0.866
  
  case i
  when 0, 1
    j = i * 2 - 1
    x1, y1 = xs[0], cn - height / 2 * j
    x2, y2 = xs[1], cn - height / 2 * j
    x3, y3 = cn, cn + height / 2 * j
  else
    j = i * 2 - 5
    x1, y1 = cn - height / 2 * j, xs[0]
    x2, y2 = cn - height / 2 * j, xs[1]
    x3, y3 = cn + height / 2 * j, cn
  end
  
  Triangle.new x1: x1, y1: y1, x2: x2, y2: y2, x3: x3, y3: y3,
     color: "#FAB536", z: 10, opacity: 0.8
}
triangle.each(&:remove)

h = {0=>0, 1=>2, 2=>1, 3=>3}
t = 0

update do
  #円の移動
  circles.zip(cvs).each do |c, vec|
    c.x += vec[0]
    c.y += vec[1]
    c.x = Width + R if c.x < -R
    c.y = Width + R if c.y < -R
    c.x = -R if c.x > Width + R 
    c.y = -R if c.y > Width + R 
  end
  
  #三角形の回転
  k = t / 100 % 4
  triangle[h[k]].add
  triangle[h[(k - 1) % 4]].remove
  
  t += 1
end

show

　
'Ruby 2D' についてはこちらで紹介しています。
obelisk.hatenablog.com

Gem 'Ruby 2D' でお絵かきしてみる

これまで Ruby でのグラフィック描画には自作の Gem 'oekaki' を使ってきましたが、高機能で簡単に使える Gem 'Ruby 2D' がリリースされたのでちょっと使ってみました。
www.ruby2d.com

インストール

Window, Mac, Linux で使えるようですが、Windows は MinGW 環境が必要なようです。自分は Linux Mint 19.1, Ruby 2.6.0 で確認しました。
とりあえず Linux 環境でのインストール方法です。上のサイトの手順どおりです。

まず SDL を使っているようなので、パッケージをインストールします。

$ sudo apt install libsdl2-dev libsdl2-image-dev libsdl2-mixer-dev libsdl2-ttf-dev

　
「simple2d」をインストールします。ここから「Source code」をダウンロード、解凍してフォルダ内に入り、

$ make && sudo make install

でインストールされます。（追記：現在はこれは不要なようです。4/27記）
　
Gem をインストールします。'gem install ruby2d' あるいは Bundler でインストール可能です。確認は例えば

$ pry
[1] pry(main)> require 'ruby2d'
=> true

となれば OK です。

（追記：現在 Windows では Gem のインストールだけで使えます。ただし MinGW-64bit 環境のみです。4/27記）
　

ヒルベルト曲線を描いてみる

Ruby 2D の使い方はシンプルで、上のサイトを見れば簡単にわかります。ヒルベルト曲線を描画してみます。

　
コード。
ruby2d_sample1.rb

require 'ruby2d'
require 'matrix'

Width = 600
N = 5

class Pen
  def initialize
    @po = Vector[35, Width - 35]
    @dir = Vector[1, 0]
  end
  
  def go
    step = (Width - 50) / (2 ** N - 1)
    next_po = @po + @dir * step
    c = Color.new("red")    #色
    Line.new(x1: @po[0], y1: @po[1], x2: next_po[0], y2: next_po[1],    #線を描く
       width: 1, color: c)
    @po = next_po
  end
  
  def left(a)
    @dir = Matrix[[0, -1], [1, 0]] * @dir * a
  end
  
  def right(a)
    @dir = Matrix[[0, 1], [-1, 0]] * @dir * a
  end
end

set title: "Hilbert curve", width: Width, height: Width    #ウィンドウの大きさなどの指定
set background: "#F8F8FF"    #背景色
pen = Pen.new

draw = ->(depth, a) {
  return if depth.zero?
  pen.right(a)
  draw.(depth - 1, -a)
  pen.go
  pen.left(a)
  draw.(depth - 1,  a)
  pen.go
  draw.(depth - 1,  a)
  pen.left(a)
  pen.go
  draw.(depth - 1, -a)
  pen.right(a)
}

draw.(N, 1)
show    #描画

　
Ruby 2D はまだまだ機能がたくさんあります。もっと使ってみたいと思います。

線分への垂線の足を求める（Ruby）

点 P から線分 AB への垂線の足 H を求めます。

Ruby の標準添付ライブラリ 'Matrix' を使います。コード。

require 'matrix'

def perpendicular_foot(a, b, p)
  s = Rational((p - a).dot(b - a), (b - a).dot(b - a))
  [h = a + (b - a) * s, s, (h - p).norm]
end

点 A, B, P は Vector[] で指定します。こんな感じ。

$ pry
[7] pry(main)> a = Vector[-2, 0]
=> Vector[-2, 0]
[8] pry(main)> b = Vector[1, 3]
=> Vector[1, 3]
[9] pry(main)> p = Vector[0, 0]
=> Vector[0, 0]
[10] pry(main)> perpendicular_foot(a, b, p)
=> [Vector[(-1/1), (1/1)], (1/3), 1.4142135623730951]

配列が返ります。順に、点 H を表す Vector、H の AB上での位置 s （H = A のとき 0、H = B のとき 1）、PH の長さを表わします。s が 0 と 1 の間にない場合は、H は線分上にはありません（もちろん直線 AB 上にはあります）。

なお、これは何次元でも使えます。

男女平等な席替え（Ruby）

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

男女15人ずつ、計30人のクラスがあります。
横 6、縦 5 の長方形に配置された机に30人が座るとき、どの生徒の席でも前後左右のいずれかに異性の席があるように座るそのしかたは、全部で何とおりになるでしょうか。
ただし、座り方は個人についてではなく、男女の区別だけを考えます。またパターンの上下左右反転、回転などは別物と考えます。

　
Ruby で解いてみました。コードです。
q69.rb

W, H = 6, 5
Num = W * H
desks = Array.new(Num, nil)
co = 0

check = ->(po) {
  return true if po < 0
  sex = desks[po]
  [1, -W, -1, W].map do |dif|
    nxt = po + dif
    next if nxt < 0
    next if nxt >= Num
    next if po % W == 0 and dif == -1
    next if po % W == W - 1 and dif == 1
    desks[nxt] == 1 - sex
  end.compact.any?
}

sit_down = ->(po, boy, girl) {
  if po == Num
    co += 1 if (Num - W...Num).map {|i| check.(i)}.all?
  else
    if boy < Num / 2
      desks[po] = 0
      sit_down.(po + 1, boy + 1, girl) if check.(po - W)
    end
    if girl < Num / 2
      desks[po] = 1
      sit_down.(po + 1, boy, girl + 1) if check.(po - W)
    end
  end
}
sit_down.(0, 0, 0)
puts co

結果。

$ time ruby q69.rb
13374192

real	5m9.299s
user	5m9.256s
sys	0m0.000s

5分も時間がかかっているのが問題ですが、このアルゴリズム（バックトラック法）だと自分にはうまい高速化の方法が浮かびませんでした。模範解答を見るとメモ化を使って 2秒ほどで解いているようですが、かなりごちゃごちゃしたコードです。なかなかむずかしい。
　

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

四則演算のパーサー（Ruby）

ある問題を解いていて、四則演算のパーサーってどんな風に書くのだろうと思って考えてみました。いわゆる「逆ポーランド記法」にパースできればあとは簡単なので、その方針で考えたのですが、自力ではちょっと荷が重かったですね。ということで検索してみたところ、既に「操車場アルゴリズム」というのがあることを知りました。なんでもあのダイクストラが考えたそうで、いや、すごいですねえ。

解説は上のリンク（Wikipedia）が充分詳しいです。Ruby コードに落としてみたのが以下です。
四則演算のパーサー（Ruby） · GitHub
メソッド parse() が逆ポーランド記法を出力するパーサー、メソッド calculate() が逆ポーランド記法を処理して実際に計算をします。

使い方はこんな感じです。四則演算の記号 + - * / と括弧（ネスト可）が使えます。演算の優先順位はもちろん通常のもの（掛け算・割り算が足し算・引き算に優先する）です。最後に = をつけます。なお、不正な記法のチェックはしていません。Runtime Error が出るか、正しくない答えが出るかのいずれかの筈です。

$ pry
[1] pry(main)> require_relative "operations_parser"
=> true
[2] pry(main)> parsed = parse("(1 + 5) * 3 - 10 / 2 =")
=> ["1", "5", "+", "3", "*", "10", "2", "/", "-"]
[3] pry(main)> calculate(parsed)
=> 13
[4] pry(main)> parsed = parse("2 * 3 - (10 + 6 / 2) =")
=> ["2", "3", "*", "10", "6", "2", "/", "+", "-"]
[5] pry(main)> calculate(parsed)
=> -7
[6] pry(main)> parsed = parse("(1.5 / (4 - 3) + 1) * 0.5 + 1.7 =")
=> ["1.5", "4", "3", "-", "/", "1", "+", "0.5", "*", "1.7", "+"]
[7] pry(main)> calculate(parsed)
=> 2.95

　
いや、操車場アルゴリズムってよくできていますね。パーサーの部分は 30行程度で書けています。

Ruby で二分探索木

勉強のために Ruby で二分探索木を書いてみました。
二分探索木の Ruby 実装 · GitHub
なお、以下のコードは説明のためなので、Gist のコードを多少簡略化しています。
　
木（Tree）のクラスと要素（Node）のクラスを定義します。Node は Struct クラスを使って簡単に定義します。key と value の値が使えます。Node を追加するたび、key の順序で整序します。

Node = Struct.new(:key, :value, :left, :right)

Tree クラスは、要素の追加と探索はこんな風になります。

class Tree
  def initialize
    @root = nil
  end
  
  def insert(key, value)
    unless @root
      @root = Node.new(key, value)
      return
    end
    node = @root
    while node
      if key < node.key
        if node.left
          node = node.left
        else
          node.left = Node.new(key, value)
          break
        end
      elsif key > node.key
        if node.right
          node = node.right
        else
          node.right = Node.new(key, value)
          break
        end
      else
        if block_given?
          node.value = yield(key, node.value, value)
        else
          node.value = value
        end
        break
      end
    end
  end
  
  def []=(key, value)
    insert(key, value)
  end
  
  # nodeを返す
  def search(key)
    node = @root
    while node
      if key < node.key
        node = node.left
      elsif key > node.key
        node = node.right
      else
        return node
      end
    end
    nil
  end
  
  # valueを返す
  def [](key)
    search(key)&.value
  end

　
これだけでこんな風に使えます。まず、t[key] = value という具合に、Node を登録しています。

$ pry
[1] pry(main)> require './binary_search_tree'
=> true
[2] pry(main)> t = Tree.new
=> #<Tree:@root=>
[3] pry(main)> t[5] = :いちご
=> :いちご
[4] pry(main)> t[3] = :みかん
=> :みかん
[5] pry(main)> t[10] = :りんご
=> :りんご
[6] pry(main)> t
=> #<Tree:@root=#<Node:@key='5', @value='いちご', @left='#<Node:@key='3', @value='みかん'>', @right='#<Node:@key='10', @value='りんご'>'>>

t[key] でハッシュのように value を見ることができます。

[7] pry(main)> t[10]
=> :りんご
[8] pry(main)> t[5]
=> :いちご

メソッド print で木を簡単に出力します。

[9] pry(main)> t.print
 -- 5 -- 3
      -- 10

さらに Node を追加します。key の順序で自動的に整序されているのがわかると思います。

[10] pry(main)> t[4] = :柿
=> :柿
[11] pry(main)> t.print
 -- 5 -- 3 --
           -- 4
      -- 10

メソッド each で木をトラバースします。

[12] pry(main)> t.each {|k, v| puts "#{k} --> #{v}"}
3 --> みかん
4 --> 柿
5 --> いちご
10 --> りんご

なお、each メソッドが定義されているので、Enumerable を include してあります。Enumerable のすべてのメソッドが使えます。

むずかしいのは Node の削除です。二分探索木の特性を壊さないように削除しなければなりません。コードはこんな感じ。

class Tree
  # Nodeを削除する
  def delete(key)
    delete_min = ->(node) {
      return node.right unless node.left
      node.left = delete_min.(node.left)
      node
    }
    del = ->(node) {
      value = nil
      if node
        if key == node.key
          value = node.value
          if node.left.nil?
            return node.right, value
          elsif node.right.nil?
            return node.left, value
          else
            min_node = search_min(node.right)
            node.key = min_node.key
            node.value = min_node.value
            node.right = delete_min.(node.right)
          end
        elsif key < node.key
          node.left , value = del.(node.left)
        else
          node.right, value = del.(node.right)
        end
      end
      return node, value
    }
    
    @root, value = del.(@root)
    value
  end
end

ここで呼ばれている search_min メソッドは、それより下のすべての Node の中から、key が最小のものを探してくるものです。

使ってみます。root を削除してみます。

[13] pry(main)> t.delete(5)
=> :いちご
[14] pry(main)> t.print
 -- 10 -- 3 --
            -- 4
       --

ちゃんと規則を壊さぬように削除できています。

最大、最小の key を探索できます。二分探索なので、一般的に高速になります。

[15] pry(main)> t.minimum
=> [3, :みかん]

　
他にもまだいろいろなメソッドが定義してありますが、これくらいが最小限度の機能だと思います。
　

メソッド一覧

• insert(key, value)
  • []= はこれを使って実装してあるが、insert の場合はブロックを取って、キーの重複があった場合の処理ができる。
• []=(key, value)
  • insert とほぼ同じだが、key が重複した場合は上書きする。
• search(key)
• [](key)
• delete(key)
• preorder(key = nil, &bk)
  • 行きがけ。key を省略した場合は root からトラバースする。
• inorder(key = nil, &bk)
  • 通りがけ。
• postorder(key = nil, &bk)
  • 帰りがけ。
• each(&bk)
  • inorder を使って実装してある。不都合なら再定義する。
• breadth_first_search(key = nil, &bk)
  • 幅優先探索。
• bfs(key = nil, &bk)
  • breadth_first_search のエイリアス。
• minimum
• maximum
• inspect
• right_rotate(key)
• left_rotate(key)
• parent_by_node(target)
• parent(key)
• add_hash(hash)
  • Hash を使って一気に insert する。
• print
  • 木構造に key を出力。デバッグ用。