n進グレイコード（Ruby）

ゆえあって n進グレイコードへの変換式を作ることになった。
　
グレイコード - Wikipedia
グレイコードについてはここにあるとおりである。2進グレイコードなら、ネットを検索すればたくさん出てくる。具体例は、Ruby のハッシュで表すとこんな感じだ。

{"0"=>"000", "1"=>"001", "10"=>"011", "11"=>"010",
 "100"=>"110", "101"=>"111", "110"=>"101", "111"=>"100"}

キーが 2進数、値が 2進グレイコードである。10進数の 3 から 4 は 2進数だと 011 から 100 で、3つのビットが変化している。しかし、グレイコードだと 010 から 110 で 1つのビットしか変化していない。このように、連続する数値ならすべてのビットの変化が 1となるのがグレイコードである。

2進数から 2進グレイコードへの変換は、Wikipedia にあるとおりだ。

「対象の二進表現」と、「それを１ビット右シフトし、先頭に０をつけたもの」との排他的論理和をとる。

C言語なら v ^ (v >> 1) と表現されるとあるとおりである。ちなみにこれは Ruby コードでもまったく同じ表現になる。

n進グレイコードでも同じ筈である。連続するグレイコードはすべての桁の変化を合わせても 1しか変っていない、そういう数になるはずである。しかしこの変換式を作ろうとしても、自分にはむずかしかった。で、ネットに頼ったところ、Ruby で既にすばらしいコードが！　なんと実質 1行である。これ以上のコードは書けないので素直にコピペさせてもらいます。

#整数 i から n進 k桁グレイコードを計算する
def to_gray(n, k, i)
  i.to_s(n).rjust(k + 1, "0").chars.each_cons(2)
    .map {|d| ((d[1].to_i(n) - d[0].to_i(n)) % n).to_s(n)}.join
end

#n進 k桁グレイコード表を作る
def gray_code(n, k)
  (0..n ** k - 1).map {|i| [i.to_s(n), to_gray(n, k, i)]}.to_h
end

p gray_code(3, 3)

なお、Ruby なので n は 36 まで可能である。
実行結果。3進グレイコードへの変換である。（3進なので、0 と 2 の差は 1 であることに注意されたい。）

{"0"=>"000", "1"=>"001", "2"=>"002", "10"=>"012", "11"=>"010", 
 "12"=>"011", "20"=>"021", "21"=>"022", "22"=>"020", "100"=>"120",
 "101"=>"121", "102"=>"122", "110"=>"102", "111"=>"100",
 "112"=>"101", "120"=>"111", "121"=>"112", "122"=>"110",
 "200"=>"210", "201"=>"211", "202"=>"212", "210"=>"222",
 "211"=>"220", "212"=>"221", "220"=>"201", "221"=>"202", "222"=>"200"}

コピペ元はここ。

考察もすばらしいので、是非よく読んで頂きたい。

逆変換は一応自分で考えてみた。こんな感じにできた。

def gray_to_num(g, n)
  s = g[0]
  g.chars.map {|x| x.to_i(n)}.inject {|h, x| s += (h = (h + x) % n).to_s(n); h}
  s
end

しかしこれも、関連記事の方にもっといいコードがあった。

def to_n_ary(n, str)
  a = 0
  str.chars.map{|d| ((a += d.to_i(n)) % n).to_s(n)}.join
end

美しい。

グレイコードとは何やら数学的な遊びで、実用的な価値はなさそうに思えるかも知れないが、そうでもないようだ。例えば思考実験として、こんな場合が考えられる。情報の通信過程で、ある種のノイズが入り得るとする。それは、情報のどこかに 1ビットが挿入されるというものだ。例えば 2進数 0100 に 1ビットのノイズが入り、1100 になったとする。これを 10進数に直すと 4 から 12 で、伝達される値が大きく変ってしまうことになる。しかし 2進グレイコードなら 0100 から 1100 は 10進数で 7 から 8 の変化に過ぎず、10進数でも値は 1 しかちがわない。よってノイズの影響が少ない可能性がある（0000 から 1000 へのような場合はさすがにダメだが）。このような場合である。

その日は何曜日？ （Ruby）

Ruby で日付から曜日を知るにはどうしたらよいか、遊びで考えてみました。

下のコードを実行すると、こんな感じ。
曜日を知りたい日付をコマンドライン引数にして実行します。

$ ruby what_day_of_the_week.rb 1989.1.8
1989-01-08 は 日曜日です。

引数なしで実行すると、その日の曜日を出力します。

$ ruby what_day_of_the_week.rb
2018-01-26 は 金曜日です。

　
コードはこんな具合です。
what_day_of_the_week.rb

require 'date'

week = %w(日 月 火 水 木 金 土)
d = if ARGV[0]
  a = ARGV[0].split(".").map(&:to_i)
  Date.new(*a)
else
  Date.today
end
puts "#{d} は #{week[d.wday]}曜日です。"

標準添付ライブラリ 'date' を使っています。

ソートの交換回数の最小化（Ruby）

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

問題：
例えば 1~3 の数字が任意に並んだ 3桁の数字を、各桁の入れ替えによってソートする場合、その入れ替えの数が最小になるようにソートしたとします。たとえば 231 なら 231→132→123 で 2回の入れ替えになります。これをすべての順列において行い、入れ替え数の合計を出します。例えば 1~3 の場合なら、最小の入れ替え数の合計は 7回になります。
さて、これを 1~7 の 7桁の場合において求めて下さい。

　
Ruby で解いてみました。
q46.rb

h = {"1234567" => 0}
queue =[["1234567", 0]]
while (x = queue.shift)
  st, depth = x
  [*0..6].combination(2) do |i, j|
    st1 = st.dup
    st1[i], st1[j] = st1[j], st1[i]
    next if h[st1]
    h[st1] = depth + 1
    if h.size == 5040
      puts h.values.inject(:+)    #=>22212
      exit
    end
    queue.push([st1, depth + 1])
  end
end

求める最小の入れ替え数の合計は 22212回になります。かかった時間は僕の環境で 0.1秒あまりです。

ソートの目標の "1234567" から出発して、すべての入れ替えを行い、深さを 1ずつ増やしていって最終的にすべてのパターン（7! = 5040 とおり）があらわれるまで繰り返します。そして、最後に合計数を求めます。

ただこれ、幅優先探索で正解が求められるのですが、深さ優先にするとダメなのですよね。どうしてなのかいまひとつよくわからないのが恥ずかしい…。
いや、当り前か。いきなり深く潜ったらもっと早く出ている筈のパターンが深くなってしまうか。

ちなみに、深さの最大値は 6 です。これは考えてみたら当然ですね。7桁なら最大 6回入れ替えればソートできると。
　

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

素数のマトリックス（Ruby）

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

問題：

1	1	3
2	3	3
7	9	7

3桁の異なる素数3つを選びます。これら（例えば 113, 233, 797）を上のように横に行列で並べたとき（行を入れ替えたものは別の行列とみなします）、行列を縦に見て得られる3つの数（ここでは 127, 139, 337）がすべて 3桁の素数であるような選び方は何とおりあるでしょうか？　ただし、最初に選んだ素数と縦に見て得られた素数あわせて6つは、すべて異ならなくてはなりません。

　
Ruby で解いてみました。
q45.rb

require 'prime'

co = 0
prs = Prime.each(999).select {|i| i >= 100}
prs.permutation(3) do |x|
  x1 = x.map(&:to_s)
  catch(:jump) do
    memo = []
    3.times do |i|
      n = (x1[0][i] + x1[1][i] + x1[2][i]).to_i
      throw(:jump) if x.include?(n) or memo.include?(n) or !prs.include?(n)
      memo << n
    end
    co += 1
  end
end
puts co    #=>29490

答えは 29490とおりです。時間は結構かかって、自分の環境だと 7秒くらいでした。特に工夫していないですからね。ちなみに、ループを回している回数は 3412145回です。
　

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

　

追記

もう少しエレガントにやってみようと思ったのですが…。

require 'prime'

table = (0..999).map {|i| Prime.prime?(i)}
co = (100..999).select {|i| table[i]}.permutation(3).map do |rows|
  rs = rows.map(&:to_s)
  cols = 3.times.map {|i| rs.map {|s| s[i]}.join.to_i}
  next if (rows + cols).uniq.size != 6
  cols.all? {|n| n >= 100 and table[n]}
end.compact.count(true)
puts co

これだと 14.5秒くらいかかりますね。最初の単純にやった方がだいぶ速いという結果でした。（2019/4/9）

グラスの水を半分に（Ruby）

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

問題：
すべて大きさのちがう３つのグラス A, B, C があります。その容積は A = B + C, B > C（ただしすべて自然数）で、かつ B と C の値は互いに素とします。
まず、A のグラスに水をいっぱいに入れます。ここから水をどんどん移していきますが、水の移動は一方が空になるか、あるいは一方が満タンになるかのいずれかしか可能でないとします。そして、最終的に A のグラスに残る量がちょうど半分にできるかどうかを考えます。
A の容積が 10 以上 100 以下の偶数のとき、上のようにして A のグラスの水が半分にできるような A, B, C の組み合わせの総数を求めなさい。

　
Ruby で解いてみました。
q44.rb

def check(quantity)
  queue = [[quantity[0], 0, 0]]
  memo = []
  while (x = queue.shift)
    next if memo.include?(x)
    memo << x
    
    move = lambda do |from, to|
      result = x.dup
      return false if x[from].zero?
      return false if x[to] == quantity[to]
      i = quantity[to] - x[to]
      if i >= x[from]
        result[from] = 0
        result[to] = x[from] + x[to]
      else
        result[to] = quantity[to]
        result[from] -= i 
      end
      result
    end
    
    [*0..2].permutation(2) do |from, to|
      y = move.call(from, to)
      next unless y
      return true if y[0] == quantity[0] / 2
      queue.push(y)
    end
  end
  false
end

memo = []
10.step(100, 2) do |a|
  (a / 2 + 1).upto(a - 1) do |b|
    c = a - b
    next if b.gcd(c) != 1
    x = [a, b, c]
    memo << x if check(x)
  end
end
puts memo.size    #=>514

答えは 514 とおりです。かかった時間は自分の環境でほぼ 3秒ほどでした。
メソッド check によって与えられたグラスで水を半分にできるかチェックしています。メソッド check 内では幅優先で探索します。水が半分にできれば true を、そうでなければ false を返します。check 内の memo にはすべての状態が格納されていて、同じものが与えられればその手順は捨てます。

クロージャとても便利。
　

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

Gosu + Chipmunk で遊ぶ（Ruby）

物理エンジン Chipmunk + Gosu でごく簡単なドミノ倒しみたいな動画を作ってみました。Ruby 2.3.3, Linux Mint 18.3 で確認しました。

gosu_chipmunk_sample3.rb

require 'gosu'
require 'rmagick'
require 'chipmunk'

CV = CP::Vec2

Width, Height = 500, 200
Wall_h = 50
BOD_w, BOD_h = 20, 100

class MyWindow < Gosu::Window
  def initialize
    super Width, Height, false
    self.caption = "Gosu + Chipmunk"
    
    @space = CP::Space.new
    @space.iterations = 3
    @space.gravity = CV.new(0, 100)
    
    background = Magick::Image.new(Width, Height) {self.background_color = "snow"}
    
    #地面
    gc = Magick::Draw.new
    gc.fill('firebrick')
    gc.rectangle(0, Height - Wall_h, Width, Height)
    gc.draw(background)
    
    #板
    board_image = Magick::Image.new(BOD_w, BOD_h)
    gc = Magick::Draw.new
    gc.fill('lightgreen')
    gc.rectangle(0, 0, BOD_w, BOD_h)
    gc.draw(board_image)
    @board = Gosu::Image.new(board_image)
    
    #円
    circle_image = Magick::Image.new(11, 11) {self.background_color = 'transparent'}
    gc = Magick::Draw.new
    gc.fill('skyblue')
    gc.circle(5, 5, 0, 5)
    gc.draw(circle_image)
    @circle = Gosu::Image.new(circle_image)
    
    #chipmunk
    #地面
    sb = CP::Body.new_static
    x1, y1 = 0, Height - Wall_h
    x2, y2 = Width, Height
    verts = [CV.new(x1, y1), CV.new(x1, y2), CV.new(x2, y2), CV.new(x2, y1)]
    wshape = CP::Shape::Poly.new(sb, verts, CV.new(0, 0))
    wshape.e = 1
    wshape.u = 1
    @space.add_shape(wshape)
    
    #板
    set_boards(5)
    
    #円
    @bodyc = CP::Body.new(7, CP::INFINITY)
    @bodyc.p = CV.new(0, 20)
    @bodyc.v = CV.new(50, 0)
    shape = CP::Shape::Circle.new(@bodyc, 5, CV.new(0, 0))
    shape.e = 0.8
    shape.u = 0
    @space.add_body(@bodyc)
    @space.add_shape(shape)
    
    @background_image = Gosu::Image.new(background)
  end
  
  def set_boards(n)
    @boards = []
    n.times do |i|
      x, y = BOD_w / 2.0, BOD_h / 2.0
      bx = [CV.new(-x, -y), CV.new(-x, y), CV.new(x, y), CV.new(x, -y)]
      body = CP::Body.new(10, CP.moment_for_poly(10, bx, CV.new(0, 0)))
      body.p = CV.new(50 + 80 * i, Height - Wall_h - y)
      shape = CP::Shape::Poly.new(body, bx, CV.new(0, 0))
      shape.e = 0
      shape.u = 1
      @space.add_body(body)
      @space.add_shape(shape)
      
      @boards << body
    end
  end
  
  def update
    @space.step(1.0 / 60)
  end
  
  def draw
    @background_image.draw(0, 0, 0)
    @boards.each do |b|
      @board.draw_rot(b.p.x, b.p.y, 2, (b.a - Math::PI / 2).radians_to_gosu)
    end
    @circle.draw_rot(@bodyc.p.x, @bodyc.p.y, 1, 0)
  end
end

MyWindow.new.show

パラメータの調節がむずかしかったですね。それぞれの質量の値は重要です。長方形はあんまり軽すぎると不安定になったりします。

GTK+ で落書き 14（Ruby）

自作の Gem 'oekaki' を使っています。
oekaki | RubyGems.org | your community gem host
GTK+でお絵かきしてみた（Ruby） - Camera Obscura
　
oekaki_sample17.rb

require 'oekaki'

Width = 500
circles = []    #作った円の情報を保持しておく配列

check = ->(x, y, r) {
  return false if x < r or y < r or x > Width - r or y > Width - r
  circles.each do |x1, y1, r1|
    l = Math.sqrt((x1 - x) ** 2 + (y1 - y) ** 2)
    return false if l < r + r1
  end
  circles << [x, y, r]
  true
}

Oekaki.app width: Width, height: Width do
  draw do
    clear(color(0xadff, 0xd8ff, 0xe6ff))    #lightblue
  end
  
  id = timer(100) do
    catch(:jump) do
      x = y = r = i = 0
      
      #円を一個生成する
      loop do
        x, y = rand(Width), rand(Width)
        r = rand(10..100)
        break if check.(x, y, r)
        i += 1
        if i > 10000    #円が混み過ぎたら終了
          timer_stop(id)
          puts "stop"
          throw(:jump)
        end
      end
      
      color(rand(0x10000), rand(0x10000), rand(0x10000))
      circle(true, x, y, r)
    end
    
    true
  end
end

つまらないものなのですけれど、じつは Kernel#rand の引数に Range オブジェクトを使ってみたかっただけなのでした…。一箇所だけ、わかりますかね。