RubyGem 'Salamander' でコッホ曲線を描く

以前、自作の Gem 'oekaki' でコッホ曲線を描いてみましたが（参照）、タートルグラフックスを実装している Gem 'salamander'（参照）を使って同じことをしてみました。

4次のコッホ曲線です。

　
salamander_koch_curve.rb

require 'salamander'
require 'salamander/support/radians'
include Salamander
include Salamander::Drawing

screen = Salamander.setup(600, 300)

Actor.draw(screen) do
  move_to 50, 200
  color :cyan
  face  :east
  
  drawing = proc do |length, depth|
    if depth.zero?
      line length
    else
      drawing[length / 3, depth - 1]
      turn -60.degrees
      drawing[length / 3, depth - 1]
      turn 120.degrees
      drawing[length / 3, depth - 1]
      turn -60.degrees
      drawing[length / 3, depth - 1]
    end
  end
  
  drawing[500.0, 4]
end
screen.redraw

loop { break if SDL.WaitEvent.type == SDL::QUIT }

みんな大好き FizzBuzz（Ruby, Python）

外部イテレータ FizzBuzz。

a = ["Fizz", "Buzz", "FizzBuzz"]
h = {0=>a[2], 3=>a[0], 6=>a[0], 9=>a[0], 12=>a[0], 5=>a[1], 10=>a[1]}

g = Enumerator.new do |y|
  loop.with_index(1) do |_, i|
    y << (h[i % 15] || i.to_s)
  end
end

p g.take(20)
#=>["1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz",
#   "11", "Fizz", "13", "14", "FizzBuzz", "16", "17", "Fizz", "19", "Buzz"]

Ruby では外部イテレータを使うことはあまりないように思いますが、この例のように Ruby でも「無限リスト」を実装することができます。
あと、上ではハッシュを使ったのが工夫してみたところです。それから、Enumerator#with_index って知っていました？

n 番目の値を出力するため、遊んでみました。上にさらにコードを追加します。

class Enumerator
  def [](num)
    first(num).last
  end
end

1.upto(15) {|i| print "#{g[i]} "}
puts
p g[105]

結果。

1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 
"FizzBuzz"

まあこんなことをするのなら、最初から外部イテレータなど使わなければいいので、倒錯していますね（笑）。
　
※参考

　

Python

同等のことを Python でもやってみました。Python は全然慣れていないので、もっと上手くやるような仕方があると思うのですが。リスト処理のところがまったく無様なので、このやり方を採る意味がないですね。内包表記を使ってもっときれいに書けないでしょうか。

def generate():
    i = 1
    while True:
        if i % 15 == 0:
            a = "FizzBuzz"
        elif i % 3 == 0:
            a = "Fizz"
        elif i % 5 == 0:
            a = "Buzz"
        else:
            a = str(i)
        yield a
        i += 1

g = generate()
l = []
for i in range(20):
    l.append(next(g))
print(l)
#=>['1', '2', 'Fizz', '4', 'Buzz', 'Fizz', '7', '8', 'Fizz', 'Buzz',
#   '11', 'Fizz', '13', '14', 'FizzBuzz', '16', '17', 'Fizz', '19', 'Buzz']

ジェネレータ関数を一度変数に入れなければならないというのも美しくないですね。余分な操作のようにも思えます。
　
こうすれば内包表記で書けるか。

g = generate()
print([next(g) for _ in range(20)])

Ruby のブロックはオブジェクト

これ、タイトルは釣りだと思うのだけれど、一応。

Ruby のブロックはもちろんオブジェクトです。Proc オブジェクトとして持ち運ぶことができます。例えば

def hoge(&bk)
  p bk
  bk.call
end

hoge do
  puts "fuga"
end

というコードがあります（むっちゃテキトーですが）。これを実行すると

#<Proc:0x005637e7cddff0@hoge.rb:6>
fuga

などと出力されます。hoge メソッドはブロックが Proc オブジェクトであることを出力し、さらにブロックを実行していることがわかると思います。なお、bk.call はここでは yield と同等です。

なお、上のリンク先の引用内の

If I ask it to tell me its class it replies "syntax error"!

というのはどういうことなのでしょうね。

p ({puts "fuga"})

ということでしょうか*1。確かにこれは syntax error になります。でもこれ、意味がないのですけれど。

p (proc {puts "fuga"})
#=>#<Proc:0x0055dc8c132568@hoge.rb:1>

とすればいいのですから。これではイカンの？　インチキ？　この Proc オブジェクトはブロックとして使うことができます。実際

a = proc {puts "fuga"}
hoge(&a)

は、最初の例とまったく同じ結果をもたらすのですから*2。「&」はブロックを Proc オブジェクトに、また Proc オブジェクトをブロックに変換します。

*1:p {puts "fuga"} と書かないのは、括弧内がメソッド p のブロックとして解釈されて syntax error にならないからです。Ruby のすべてのメソッドはブロックを取ることができます。処理が定義されていない場合は無視されます。

*2:自分はやりませんが、hoge(&proc {puts "fuga"}) とだって書けます。

RubyGem 'Salamander' でヒルベルト曲線を描く

RubyGem 'Salamander' は Ruby/SDL を使ってタートルグラフックスを実装しています。これを使ってヒルベルト曲線を描いてみました。Linux Mint 18.2 と Ruby 2.3.3 で確認しています。

インストールは Bundler で入りますが（$ gem install salamander でもたぶん入るでしょう）、その前に Linux Mint に SDL 用のライブラリを入れなくてはなりません。

$ sudo apt-get install libsdl1.2-dev libsdl-gfx1.2-dev libsdl-image1.2-dev libsdl-mixer1.2-dev libsdl-ttf2.0-dev

Ruby/SDL は何もしなくても入るようです。

5次のヒルベルト曲線です。　


salamander_hilbert.rb

require 'salamander'
require 'salamander/support/radians'
include Salamander
include Salamander::Drawing

Step = 15
screen = Salamander.setup(500, 500)

Actor.draw(screen) do
  def draw(depth, angle)
    return if depth <= 0
    turn  angle.degrees
    draw(depth - 1, -angle)
    line Step
    turn -angle.degrees
    draw(depth - 1,  angle)
    line Step
    draw(depth - 1,  angle)
    turn -angle.degrees
    line Step
    draw(depth - 1, -angle)
    turn  angle.degrees
  end
  
  color :red
  move_to 20, 20
  face :east
  draw(5, 90)
end
screen.redraw

loop { break if SDL.WaitEvent.type == SDL::QUIT }

　
Salamander を使うための試行錯誤は以下。
RubyGem 'Salamander' が動かないよ - Marginalia
RubyGem 'Salamander' がようやく動いたよ - Marginalia
　
ヒルベルト曲線についての過去記事は以下。
Python の Turtle でヒルベルト曲線 - Camera Obscura
GTK+でヒルベルト曲線（Ruby） - Camera Obscura
JavaScript でヒルベルト曲線を描く - Camera Obscura
Ruby/Tk でヒルベルト曲線を描く - Camera Obscura
　

Ruby のイテレーションされる配列の破壊的変更について

この Ruby コードの出力がわかりますか。

ar = [["a"],["b"]]
ar.each do |x|
  p x
  ar[1] = 1
end
p ar

　
結果はこうです。

["a"]
1
[["a"], 1]

イテレーションされる配列をブロック内で変更すると、イテレーションがおかしくなります。わかりにくいので、これを前提としたコーディングはしない方が無難かと思われます。

ベルマン−フォード・アルゴリズム（Ruby）

ベルマン−フォード・アルゴリズムは、ダイクストラ法にさらに辺の重みが負の場合も含めて最短経路を求めることができます。入出力などはダイクストラ法の場合を参照して下さい。

コーディングは Ruby で行いました。返り値は配列 [shortest, pred] で、pred を見ると最短経路がわかります。
bellman_ford.rb

def bellman_ford(g, s)
  h = g.map {|x| [x[0], x[1].keys]}.to_h
  
  shortest = Hash.new(Float::INFINITY)
  pred = {}
  
  shortest[s] = 0
  
  (h.size - 1).times do
    h.each do |k, v|
      v.each do |x|
        if (a = shortest[k] + g[k][x]) < shortest[x]
          shortest[x] = a
          pred[x] = k
        end
      end
    end
  end
  
  [shortest, pred]
end

if __FILE__ == $0
  g = {s: {t: 6, y: 7}, t: {x: 5, y: 8, z: -4},
       x: {t: -2}, y: {z: 9, x: -3}, z: {s: 2, x: 7}}
  p bellman_ford(g, :s)
end
#=>[{:s=>0, :t=>2, :y=>7, :x=>4, :z=>-2}, {:t=>:x, :y=>:s, :x=>:y, :z=>:t}]

ベルマン−フォード・アルゴリズムは負の閉路を検出できます。下の find_negative_weight_cycle メソッドで、負の閉路がない場合は空の配列を、ある場合は閉路の頂点の順番を配列で返します。

def find_negative_weight_cycle(g, s)
  shortest, pred = bellman_ford(g, s)
  
  g.each do |u, v1|
    v1.each_key do |v2|

      if shortest[u] + g[u][v2] < shortest[v2]
        visited = Hash.new(false)
        x = v2
        until visited[x]
          visited[x] = true
          x = pred[x]
        end
        
        v = pred[x]
        cycle = [x]
        until v == x
          cycle.unshift(v)
          v = pred[v]
        end
        return cycle
      end
      
    end
  end
  []
end

if __FILE__ == $0
  g = {s: {t: 6, y: 7}, t: {x: 5, y: 8, z: -4},
       x: {t: -2}, y: {z: 9, x: -3}, z: {s: 2, x: 7, y: 1}}
  p bellman_ford(g, :s)
  p find_negative_weight_cycle(g, :s)
end
#=>[{:s=>-4, :t=>-2, :y=>-5, :x=>-4, :z=>-6}, {:t=>:x, :y=>:z, :x=>:y, :z=>:t, :s=>:z}]
#=>[:z, :y, :x, :t]

アルゴリズムの基本

組み込みクラスのすべてを移譲する（Ruby）

require 'delegate'

class MyArray < DelegateClass(Array)
  def initialize(*args, &bk)
    super(Array.new(*args, &bk))
  end
  
  def to_s
    join('_')
  end
end

a = MyArray.new(5) {rand(5)}
p a         #=>[4, 2, 3, 2, 4]
p a.to_s    #=>"4_2_3_2_4"

　
MyArray クラスは（リテラルがない以外）Array とまったく同様に使うことができます。新しいメソッドを作ったりインスタンス変数を定義したりしても、移譲なので、元の Array クラスにはまったく影響しません。