みんな大好き 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)[-1]
  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']

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

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 MintSDL 用のライブラリを入れなくてはなりません。

$ 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次のヒルベルト曲線です。 
20170814224406

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]

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

『Cプログラミング診断室』について

Cプログラミング診断室
おもしろいサイトを見つけました。

C言語のヒドいコード(いわゆるクソコード^^;)を眺めて、リファクタリングしようというものです。僕などのように、独学で誰もまわりにプログラミングを知っている人のいない孤独なアマチュアプログラマにはとても参考になるものです。書籍化もされている(というか、書籍の方が先なのかな?)ようですが、既に絶版のようです。クソコードか、耳が痛いな…。
 

改訂新版 Cプログラミング診断室

改訂新版 Cプログラミング診断室

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


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

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

require './dag_shortest_paths'

class Hash
  def bellman_ford(s)
    h = 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 {|x| relax(k, x)}
      end
    end
    
    [@shortest, @pred]
  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}}
  p g.bellman_ford(:s)
end
#=>[{:s=>0, :t=>2, :y=>7, :x=>4, :z=>-2}, {:t=>:x, :y=>:s, :x=>:y, :z=>:t}]

dag_shortest_paths.rb はここのコードです。


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

class Hash
  def find_negative_weight_cycle(s)
    bellman_ford(s)
    
    each do |u, v1|
      v1.each_key do |v2|
  
        if @shortest[u] + self[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
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 g.bellman_ford(:s)
  p g.find_negative_weight_cycle(: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 クラスにはまったく影響しません。