線分への垂線の足を求める(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秒ほどで解いているようですが、かなりごちゃごちゃしたコードです。なかなかむずかしい。
 

四則演算のパーサー(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)
  • minimum
  • maximum
  • inspect
  • right_rotate(key)
  • left_rotate(key)
  • parent_by_node(target)
  • parent(key)
  • add_hash(hash)
    • Hash を使って一気に insert する。
  • print

Ruby の素敵なワンライナーコマンド「rb」

つらつらと yhara.jp を見ていたら、sedやawkが覚えられないRubyistのための「rbコマンド」という記事があって大変におもしろかったです。Ruby には -n や -p といったワンライナー用のオプションがあるのですが、自分はこれが覚えられない。sedawk も覚えられないのですが、そんな私のために強い味方があらわれた感じです。

それは 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割ほど速いようです。
 

Linux Mint 19(Ubuntu 18.10)に Bundler で Ruby/Tk を入れる

Ruby 2.6.0 では以下の方法では tk はインストールできないようです。対策はいまのところわかりません。
なお、Bundler を使わず gem install でインストールするのは成功するので、tk の問題なのではなく、Bundler の問題なのかも知れません。(2019/1/26)



 
Linux Mint 19 に rbenv で Ruby 2.5.1 が入っています。これに Ruby/Tk を入れてみようと思います。
Ubuntu 18.10, Ruby 2.5.3 でも確認しました。

Ruby/Tk は Ruby 2.4 から標準添付ライブラリではなくなりました。なので、Gem として Bundler で入れてみます。


まず、ライブラリを入れます。

$ sudo apt-get update
$ sudo apt-get install tk tcl tk8.6-dev tcl8.6-dev

 
Gemfile に gem 'tk' を追加します。そして次を実行(参考)。

$ bundle config build.tk --with-tcltkversion=8.6 \
--with-tcl-lib=/usr/lib/x86_64-linux-gnu \
--with-tk-lib=/usr/lib/x86_64-linux-gnu \
--with-tcl-include=/usr/include/tcl8.6 \
--with-tk-include=/usr/include/tcl8.6 \
--enable-pthread
$ bundle install

これでエラーが出なければ OK です。

実際に入ったか確かめてみます。

$ irb
irb(main):001:0> require 'bundler/setup'
=> true
irb(main):002:0> require 'tk'
=> true

OK ですね!


確認用のサンプルコード。

require 'tk'

TkLabel.new {
  text "Hello, world!"
  bg "red"
  pack
}
TkButton.new {
  text "Close"
  command {exit}
  pack
}
Tk.mainloop

こんな Window が出てきます。
20181222000742
 

※参考
Bundler を使わない人は、ライブラリを入れたあと

$ gem install tk -- --with-tcltkversion=8.6 \
--with-tcl-lib=/usr/lib/x86_64-linux-gnu \
--with-tk-lib=/usr/lib/x86_64-linux-gnu \
--with-tcl-include=/usr/include/tcl8.6 \
--with-tk-include=/usr/include/tcl8.6 \
--enable-pthread

でよいようです。ここなどを参照してみて下さい。
 

追記

Ruby/Tk でヒルベルト曲線を描く - Camera Obscura
ここでのコードもそのまま動きました。(5次のヒルベルト曲線)
20181222002952
 
それから下も動きました。
Ruby/Tk で簡単なグラフを描く - Camera Obscura
 
※参考
Ruby Tk リンク - Camera Obscura