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問
- 作者: 増井敏克
- 出版社/メーカー: 翔泳社
- 発売日: 2015/10/16
- メディア: Kindle版
- この商品を含むブログ (9件) を見る
四則演算のパーサー(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 する。
Ruby の素敵なワンライナーコマンド「rb」
ふらふらと yhara.jp を見ていたら、sedやawkが覚えられないRubyistのための「rbコマンド」という記事があって大変におもしろかったです。Ruby には -n や -p といったワンライナー用のオプションがあるのですが、自分はこれが覚えられない。sed も awk も覚えられないのですが、そんな私のために強い味方があらわれた感じです。
それは Ruby で書かれた rb コマンドというやつ。yhara さんの挙げられている例だと、ps コマンドで PID の部分だけ抜き出す。
$ ps | rb -l split[0] PID 8123 8203 8204
おお、簡単ですね。Ruby のコードがそのまま書けていて、なるほどよくわかる。これは -l オプションがついているやつですね。
デフォルトだとこんな感じ。僕の Ruby コードたちから、"maze" という文字を含むファイルネームを抜き出してみます(grep を使うといいのだが、まあ例だから)。
$ ls -l | rb 'select {|l| /maze/.match(l)}' -rw-r--r-- 1 tomoki tomoki 2225 7月 25 16:52 3d_maze_generate.rb -rw-r--r-- 1 tomoki tomoki 4237 10月 26 15:08 3d_maze_walk.rb -rwxrwxrwx 1 tomoki tomoki 3180 4月 19 2018 maze.png -rwxrwxrwx 1 tomoki tomoki 3086 4月 19 2018 maze.rb -rwxrwxrwx 1 tomoki tomoki 2919 4月 19 2018 maze1.rb -rwxrwxrwx 1 tomoki tomoki 1397 4月 19 2018 maze_another.rb -rwxrwxrwx 1 tomoki tomoki 2629384 4月 19 2018 maze_never_turn_left.gif -rwxrwxrwx 1 tomoki tomoki 1869 4月 19 2018 maze_never_turn_left.rb -rwxrwxrwx 1 tomoki tomoki 744 4月 19 2018 maze_never_turn_left.txt -rwxrwxrwx 1 tomoki tomoki 1348 4月 19 2018 maze_never_turn_left_make_result_png.rb -rwxrwxrwx 1 tomoki tomoki 1485 4月 19 2018 maze_never_turn_left_result.txt -rwxrwxrwx 1 tomoki tomoki 1357 4月 19 2018 solve_maze.rb -rw-rw-r-- 1 tomoki tomoki 985 12月 12 11:39 solve_maze1.rb -rw-r--r-- 1 tomoki tomoki 846 7月 12 10:04 test_3d_maze.rb -rwxrwxrwx 1 tomoki tomoki 2730 4月 19 2018 walk_maze.rb
おお、簡単。でも、どうなっているのだ?
本体はすごくシンプル。
rb
#!/usr/bin/env ruby File.join(Dir.home, '.rbrc').tap { |f| load f if File.exists?(f) } def execute(_, code) puts _.instance_eval(&code) rescue Errno::EPIPE exit end single_line = ARGV.delete('-l') code = eval("Proc.new { #{ARGV.join(' ')} }") single_line ? STDIN.each { |l| execute(l.chomp, code) } : execute(STDIN.each_line, code)
これに "rb" という名前をつけて、実行権を与えてパスのとおったところに置くだけ。たった 9行で、すごい。なるほど、よくわかるコードですね。引数で与えられたコードを eval で Proc 化して、instance_eval で実行しているだけ。デフォルトでは Enumerator を返していて、-l オプションだと各行について実行してくれるわけですね。いやあ、これは便利に使わせてもらいます。
なお、第 1 行目('File.join'...)は、'.rbrc' ファイルを設定ファイルにしていて、これがあると先にロードしておくというものです。
もともとの作者のページはこちら。
https://github.com/thisredone/rb
インストール(というほどではないが)がよくわからない人は、作者が全部自動でインストールできるコードを載せてくれてあります(Linux 用)。
$ sudo curl https://raw.githubusercontent.com/thisredone/rb/master/rb -o /usr/local/bin/rb && sudo chmod +x /usr/local/bin/rb
隣り合わないのがマナー?(Ruby)
アルゴリズム・パズルです。
電車の中に 6人がけのロングシートが向かい合いになって、計12の席があるとします。
すべて空いている状態からすべてが埋まるまで、両隣が空いている空席があるときはそちらから座るというルールで、全部で何通りの席の埋まり方があるでしょうか?
Ruby で解いてみました。
q68.rb
L = 6 # 両隣が空いている空席を返す def get_scattered(spaces) before = spaces.select {|i| i < L} after = spaces - before result = ([-1] + before + [L]).chunk_while {|i, j| i + 1 == j} .select {|a| a.size >= 3}.flat_map {|a| a[1..-2]} result + ([L - 1] + after + [L * 2]).chunk_while {|i, j| i + 1 == j} .select {|a| a.size >= 3}.flat_map {|a| a[1..-2]} end # 与えられた空席での座り方の総数を返す def sit_down(spaces) return 2 if spaces.size == 2 return @memo[spaces] if @memo.has_key?(spaces) co = 0 scattered = get_scattered(spaces) if scattered.empty? spaces.each {|sit| co += sit_down(spaces - [sit])} else scattered.each {|sit| co += sit_down(spaces - [sit])} end @memo[spaces] = co end @memo = {} puts sit_down([*0...L * 2])
メモ化で高速化を図っています。
結果。
$ time ruby q68.rb 14100480 real 0m0.148s user 0m0.088s sys 0m0.024s
RubyPico で
じつは最初は待ち時間に RubyPico でコーディングしていたのでした。RubyPico でもほぼ同じコードが走りますが、Enumerable#chunk_while
が mruby で実装されていないようなので、自分でこんな風に実装してみました。このあたりがオープンクラスの Ruby (mruby) のおもしろいところですよね。
module Enumerable def chunk_while result, tmp = [], [] f = true a = nil each do |b| if f tmp << b f = false else if yield(a, b) tmp << b else result << tmp tmp = [b] end end a = b end result + (tmp.empty? ? [] : [tmp]) end end
もちろん答えは同じで、時間は自分の iPad mini で 0.396秒ほどになりました。Core i5 の PC と比べて 2.6倍くらい遅い(0.37倍の速さ)という感じでしょうか。まずまずですよね。
追記
メソッド get_scattered
はこういう実装の方が簡潔かな?
def get_scattered(spaces) before = spaces.select {|i| i < L} after = spaces - before result = ([-1] + before + [L]).each_cons(3) .map {|a, b, c| b + c == 2 * a + 3 ? b : nil}.compact result + ([L - 1] + after + [L * 2]).each_cons(3) .map {|a, b, c| b + c == 2 * a + 3 ? b : nil}.compact end
ここでは実行時間はまるで変わりません。L = 10 にして実行してみると、こちらの方が 2割ほど速いようです。
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問
- 作者: 増井敏克
- 出版社/メーカー: 翔泳社
- 発売日: 2015/10/16
- メディア: Kindle版
- この商品を含むブログ (9件) を見る