素数のマトリックス（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 オブジェクトを使ってみたかっただけなのでした…。一箇所だけ、わかりますかね。

「シェルピンスキーのギャスケット」を描いてみる（Ruby）

「シェルピンスキーのギャスケット」を Ruby で描いてみました。

　
フラクタルな図形なので正確ではないですが、7次まで描いてみました。描画には自作の Gem 'oekaki' を使っています。
oekaki | RubyGems.org | your community gem host
GTK+でお絵かきしてみた（Ruby） - Camera Obscura
　
コードです。
sierpinski_gasket.rb (Gist)

require 'oekaki'

Width, Height = 500, 450

Oekaki.app width: Width, height: Height, title: "Sierpinski gasket" do
  draw do
    clear
    
    x1, y1 = Width / 2, Height - Width * 0.5 * Math.sqrt(3)
    x2, y2 = 0, Height
    x3, y3 = Width, Height
    po0 = [[x1, y1], [x2, y2], [x3, y3]]
    
    color(0xff * 256, 0xd7 * 256, 0)    #gold
    polygon(true, po0)
    
    color(0, 0, 0)
    
    sg = lambda do |n, po|
      y = (po[0][1] + po[1][1]) / 2.0
      l = (po[2][0] - po[1][0]) / 2.0
      p1 = [po[1][0] + l / 2, y]
      p2 = [po[2][0] - l / 2, y]
      p3 = [po[1][0] + l, po[1][1]]
      
      polygon(true, [p1, p2, p3])
      return if n == 1
      
      sg.call(n - 1, [po[0], p1, p2])
      sg.call(n - 1, [p1, po[1], p3])
      sg.call(n - 1, [p2, p3, po[2]])
    end
    
    sg.call(7, po0)
  end
end

lambda の再帰を使って反復を実装しています。

指定したディレクトリ以下から再帰的にファイルをランダムに取ってくる

と思ったけど簡単だった

— JI@わんわんコンサル (@jaialkdanel) 2018年1月16日

　
へー、Ruby ではどうやるかなとちょっと考えてみた。

require 'find'

def get_filenames_randomly(directory)
  Find.find(directory).select {|x| File.file?(x)}.shuffle.to_enum
end

puts get_filenames_randomly("/usr/lib").take(10)

こんな感じ？　Ruby だから Enumerator を返すことにする。実質一行だな。

結果。

/usr/lib/python2.7/dist-packages/twisted/protocols/portforward.py
/usr/lib/x86_64-linux-gnu/libgtk-3.so
/usr/lib/python2.7/dist-packages/reportlab/lib/enums.py
/usr/lib/x86_64-linux-gnu/libicule.so.55.1
/usr/lib/ruby/2.3.0/rdoc/markup/attributes.rb
/usr/lib/x86_64-linux-gnu/vlc/plugins/codec/libsvcdsub_plugin.so
/usr/lib/python2.7/dist-packages/twisted/protocols/mice/__init__.pyc
/usr/lib/x86_64-linux-gnu/wine/dbghelp.dll.so
/usr/lib/python3.5/lib2to3/pgen2/__pycache__/parse.cpython-35.pyc
/usr/lib/python2.7/dist-packages/dbus/service.pyc

　
ちなみに

enum = get_filenames_randomly("/usr/lib")
10.times {puts enum.next}

でもほぼ同じ。（10回に満たない場合の挙動がちがう。）

ハノイの塔をプログラミングで解く

ハノイの塔とは一種のパズルで、ルールは以下のようです。

• 3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
• 最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
• 円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。

ハノイの塔 - Wikipedia

このルールの下で、左端に積み重ねられた円盤をすべて別のひとつの位置に移し替えるというものです。
　
再帰プログラミングでとても簡単に解けることを知りました。Ruby で解いてみます。

考え方はこうです。三つの場所を A, B, C とします。A に n 枚の円盤があるとき、

1. n - 1 枚の円盤を A から C に移します。
2. A に残った 1枚を B に移します。
3. n - 1 枚の円盤を C から B に移します。

ただし、n が 1 のときはただ A から B へ移せばよい。

これを素直にプログラミングするだけです。

def hanoi(n, from, to, via)
  if n == 1
    puts "#{from} から #{to} へ移す"
  else
    hanoi(n - 1, from, via, to)
    puts "#{from} から #{to} へ移す"
    hanoi(n - 1, via, to, from)
  end
end

hanoi(3, :A, :B, :C)

結果。円盤が 3枚の場合です。

A から B へ移す
A から C へ移す
B から C へ移す
A から B へ移す
C から A へ移す
C から B へ移す
A から B へ移す

これですべて A から B に移ります。特に n を大きくしてみると、こんな単純な再帰で解が求められるのが不思議な感じがします。
　
なお、これは以下の記事の LISP コードを Ruby に置き換えただけのことです。元記事に感謝します。