いまどきの Ruby なフィボナッチ数列

Enumerator.produceを使います。

fib = Enumerator.produce([1, 1]) { |a, b| [b, a + b] }.lazy.map(&:first)

#最初の10個
fib.first(10)
#=>[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

#数列の100以上3000未満の部分
fib.drop_while { _1 < 100 }.take_while { _1 < 3000 }.force
#=>[144, 233, 377, 610, 987, 1597, 2584]

#1000未満で素数であるもの
require "prime"
fib.select(&:prime?).take_while { _1 < 1000 }.force
#=>[2, 3, 5, 13, 89, 233]

追記（12/6）

無駄に便利にしてみました。

module Fib
  Seq = Enumerator.produce([1, 1]) { |a, b| [b, a + b] }.lazy.map(&:first)
  
  class << self
    def method_missing(name, *args, &bk)
      Seq.__send__(name, *args, &bk)
    end
    
    def [](arg)
      case arg
      in Integer => i
        drop(i).first
      in Range => r
        a = r.begin
        if r.end
          b = r.exclude_end? ? r.end - 1 : r.end
          drop(a).take(b - a + 1).force
        else
          drop(a)
        end
      end
    end
  end
end

#最初の10個
Fib.first(10)    #=>[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

#最初の5個をそれぞれ2乗した数列
Fib.map { _1 ** 2 }.first(5)    #=>[1, 1, 4, 9, 25]

#（0番始まりで）9番目の値
Fib[9]    #=>55

#（0番始まりで）3番目から9番目までの数列
Fib[3..9]    #=>[3, 5, 8, 13, 21, 34, 55]

#3番めから9-1番目までの数列
Fib[3...9]    #=>[3, 5, 8, 13, 21, 34]

#3番目からの無限数列を10個取ったもの
Fib[3..].first(10)    #=>[3, 5, 8, 13, 21, 34, 55, 89, 144, 233]

Ruby 的に自然な FizzBuzz

まことに FizzBuzz の種は盡きまじ。
　

fizzbuzz = Enumerator.new {|y|
  (1..).each do |i|
    f = (i % 3).zero?
    b = (i % 5).zero?
    y << case
         when f && b then "FizzBuzz"
         when f      then "Fizz"
         when b      then "Buzz"
         else             i.to_s
         end
  end
}

puts fizzbuzz.take(40)

Enumerator と Endless Range は使いたいよね。場合分けは case ~ when。

関数を微分して gnuplot で出力（Ruby）

　
コード。

require "numo/gnuplot"

dx = 0.0001

dif = ->(f, x) {
  (f.(x+dx)-f.(x))/dx
}.curry

f = ->(x) { x*x-2*x+1 }

dif_f = dif.(f)

xs = -5.step(5, 0.1).to_a
ys1 = xs.map(&f)
ys2 = xs.map(&dif_f)

Numo.gnuplot do
  set terminal: :x11
  unset :key
  set xrange: -5..5
  set yrange: -5..10
  set grid: true
  plot xs, ys1, {w: :lines, lw: 2},
       xs, ys2, {w: :lines, lw: 2}
end
gets    #終了待ち

ビット操作メソッド三題（Ruby）

Ruby を使っているとビット操作はあまり必要なのだが、競技プログラミングをやっていたりすると時にはビット操作したくなることもある。で、Ruby をあらためて見てみると（当り前だが）ビット操作も一通り揃っているわけだ。競プロで便利だなと思うのは例えば「ビットの立っている」ものを数える、つまり整数を二進数表現に直して "1" の数を数えるというもので、Ruby では

to_s(2).chars.count { _1 == "1" }
#追記　以下でよい
to_s(2).count("1")

と簡潔に書ける。
　また、いわゆる「ビット全探索」は、Ruby ではビットを使わなくても簡単に書ける。例えば、[0, 1, 2, 3, 4]のすべての部分集合を列挙する場合は、

ary = [0, 1, 2, 3, 4]
co = 0
(0..ary.size).each do |i|
  ary.combination(i) do |sub_set|
    p [co, sub_set]
    co += 1
  end
end

などと書ける。結果は

[0, []]
[1, [0]]
[2, [1]]
[3, [2]]
[4, [3]]
[5, [4]]
[6, [0, 1]]
[7, [0, 2]]
[8, [0, 3]]
[9, [0, 4]]
[10, [1, 2]]
[11, [1, 3]]
[12, [1, 4]]
[13, [2, 3]]
[14, [2, 4]]
[15, [3, 4]]
[16, [0, 1, 2]]
[17, [0, 1, 3]]
[18, [0, 1, 4]]
[19, [0, 2, 3]]
[20, [0, 2, 4]]
[21, [0, 3, 4]]
[22, [1, 2, 3]]
[23, [1, 2, 4]]
[24, [1, 3, 4]]
[25, [2, 3, 4]]
[26, [0, 1, 2, 3]]
[27, [0, 1, 2, 4]]
[28, [0, 1, 3, 4]]
[29, [0, 2, 3, 4]]
[30, [1, 2, 3, 4]]
[31, [0, 1, 2, 3, 4]]

となって、確かにすべての部分集合が列挙されている（空集合を含む場合）。Ruby の組み込みメソッドにないのが不思議なくらいだが、これはだから

class Array
  def each_subset(empty_set=true)
    if block_given?
      n = empty_set ? 0 : 1
      (n..size).each do |i|
        combination(i) { yield _1 }
      end
    else
      to_enum(__method__, empty_set)
    end
  end
end

とでもして Array クラスに追加してやったらよい。で、上のと同じ結果を得ようと思えば

[0, 1, 2, 3, 4].each_subset.with_index do |ary, i|
  p [i, ary]
end

とでもすればよいのである。これがあったら競プロに便利だろうね。組み込みに追加されないかね。

で、以下が本題というほどでもないのだが、Ruby にビット操作メソッドを三つ追加してみた。いずれも実用性はないものと考えられ、たんなる遊び。
こんな感じである。

class Integer
  def each_bit
    if block_given?
      to_s(2).chars.reverse.map { _1 == "1" }.each { yield _1 }
      #これでよい
      #digits(2).each { yield _1 == 1 }
    else
      to_enum(__method__)
    end
  end
  
  def bit_reverse
    to_s(2).chars.reverse.join.to_i(2)
    #これでよい
    #to_s(2).reverse.to_i(2)
  end
end

class Array
  def to_i
    map { _1 ? "1" : "0" }.reverse.join.to_i(2)
  end
end

　
まず、Integer#each_bitはビットごとにブロックを実行し、ブロック変数にはビットが 1 なら true、0 なら false が入るというもの。

0b10101101.each_bit { p _1 }

を実行すると

true
false
true
true
false
true
false
true

が出力となる。下位ビットから実行されていくのに注意。だから最後は必ず true になる。

173.each_bit.map(&:itself)    #=>[true, false, true, true, false, true, false, true]
0.each_bit.map(&:itself)      #=>[false]

など。

Array#to_iはこれの反対。配列の中身で真のものを 1、偽のものを 0 として二進表現と見做し、Integer に変換する。これも配列の左から下位ビットに詰められていくのに注意。

[:a, nil, 1, -1, 1 == 0, 1.integer?, 0.1 < 0, true].to_i    #=>173
173.each_bit.map(&:itself).to_i    #=>173

　
Integer#bit_reverseはテキトーに思いついたもの。Integer のビットを左右反転させた Integer を作る。まぎらわしいが、ビット反転（否定、Integer#~）とは全然ちがうのです。

173.bit_reverse    #=>181
173.to_s(2)    #=>"10101101"
181.to_s(2)    #=>"10110101"

なお、bit_reverse.bit_reverseは必ずしも元に戻らないので注意（わかりますね？）。
　

おそまつ様でした。

RactorEnum の使用例（Ruby）

obelisk.hatenablog.com前回作った RactorEnum を作ってみます。

迷路のスタート（S）から水を流し、お宝が水没するたびにお宝の座標と種類を（リアルタイムで）出力するというものです。
幅優先探索で、お宝に到達するたびにre.pipeに流し込みます。

require_relative "ractor_enum"

re = RactorEnum.new

field = DATA.readlines

Ractor.new(field, re) do |field, re|
  queue = [[1, 1]]
  while (now = queue.shift)
    x, y = now
    [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy|
      x1 = x + dx
      y1 = y + dy
      a = field[y1][x1]
      re.pipe << [a, [x1, y1]] if a != " " && a != "." && a != "#"
      if a != "#" && a != "."
        queue << [x1, y1]
        field[y1][x1] = "."
      end
    end
  end
  re.pipe << RactorEnum::End.new
end

re.each { |item, (x, y)| puts "(%2d,%2d) -> #{item}" % [x, y] }

__END__
###########################
#S  #               =     #
##  #  @     #            #
#+           ##########   #
########  >  #     *      #
#   #        #        #####
#  !#        #            #
#  ###  ############      #
#    #  #                 #
#       #    #      $     #
#   #####    #            #
#   #        ##############
#   #        #       #    #
#   #   V         #  #  & #
#                 #       #
###########################

出力。

( 1, 1) -> S
( 1, 3) -> +
( 7, 2) -> @
(10, 4) -> >
(20, 1) -> =
( 3, 6) -> !
( 8,13) -> V
(19, 4) -> *
(20, 9) -> $
(24,13) -> &

Ractor の Enumerable 化？（Ruby）

オブジェクトを順に Ractor に流し込んで、（無限連鎖の）Enumerable（親クラス）として取り出すというものです。
　
こんな感じです。
ractor_enum.rb

class RactorEnum
  class End end
  
  def initialize
    @pipe = Ractor.new do
      loop do
        e = Ractor.receive
        if e.instance_of?(RactorEnum::End)
          Ractor.current.close_outgoing
        else
          Ractor.yield e
        end
      end
    end
  end
  attr_reader :pipe

  def each
    loop { yield @pipe.take }
  end
  
  include Enumerable
end

loop do ~ endはRactor::ClosedErrorを捕捉するようです。
　
re = RactorEnum.newしてre.pipeに流し込み、Enumerable として取り出します。

re = RactorEnum.new
re.pipe << :Hello
re.pipe << :World!
re.take(2)    #=>[:Hello, :World!]

無限連鎖なので、re.mapとかするとフリーズします。lazy化するとよいかも知れません。

re = RactorEnum.new
20.times { re.pipe << rand(97..122) }
re.lazy.map(&:chr).first(8).join    #=>"mnflrutp"

　
あるいはRactorEnum::End.newで流し込みの終わりを指定します。

re = RactorEnum.new
20.times { re.pipe << rand(97..122) }
re.pipe << RactorEnum::End.new

re.map(&:chr).join    #=>"ccwbjfecegtyjwszeued"

　
Ractor を使えば、後から流し込むこともできます。

re = RactorEnum.new

Ractor.new(re) do |re|
  re.each { puts _1 }
end

re.pipe << 1
sleep(1)
re.pipe << 2
sleep(1)    #これがないと"2"を表示する前に終わってしまうことがある

"1" が表示され、1秒後に "2" が表示されます。
　
重い処理を分散して実行し、流し込んだ順に Enumerable として取り出します。

re = RactorEnum.new

#3つの分散処理
3.times do |i|
  Ractor.new(re, i) do |re, i|
    #何か重い処理
    10.times do
      sleep(rand(2.0..3.0))
      re.pipe << rand(i*10..(i+1)*10-1)
    end
  end
end

re.each_slice(3).with_index(1) do |ary, i|
  p ary.map { _1 + 1000 }
  re.pipe.close_outgoing if i == 4
end

出力例。3つずつ流し込まれた時点で出力します。

[1012, 1026, 1000]
[1004, 1011, 1029]
[1013, 1002, 1024]
[1009, 1015, 1020]

　
適当に数を20個流し込んで、素数があったところで切って出力します。

require "prime"

re = RactorEnum.new

#サーバー
Ractor.new(re) do |re|
  20.times do
    sleep(rand)
    re.pipe << rand(2..30)
  end
  re.pipe << RactorEnum::End.new
end

re.slice_after(&:prime?).each do |ary|
  p ary
end

出力例。

[5]
[14, 29]
[13]
[10, 28, 19]
[15, 30, 3]
[15, 13]
[5]
[23]
[6, 3]
[13]
[15, 8, 28]    #最後は素数で終わるとは限らない

　
分散処理の例。

require "prime"

N = 100

re1 = RactorEnum.new
re2 = RactorEnum.new

3.times.map do
  Ractor.new(re1, re2) do |re1, re2|
    re1.each { |n| re2.pipe << [n, n.prime?] }
  end
end

(1..N).each { |i| re1.pipe << i }
re1.pipe << RactorEnum::End.new

p re2.take(N).sort_by { |n, b| n }

　
素数があったらその次の 5つを出力する、というのを続ける。RactorEnum を Enumerator に変換しています。

require "prime"

re = RactorEnum.new

#サーバー
Ractor.new(re) do |re|
  (2..40).each do |i|
    sleep(rand)
    re.pipe << i
  end
  re.pipe << RactorEnum::End.new
end

enum = re.to_enum

loop do
  n = enum.next
  if n.prime?
    p enum.take(5)
  end
end

出力。

[3, 4, 5, 6, 7]
[12, 13, 14, 15, 16]
[18, 19, 20, 21, 22]
[24, 25, 26, 27, 28]
[30, 31, 32, 33, 34]
[38, 39, 40]

Ractor#takeがあるのでこんなことをしてもあまり意味はないけれど、まあ敢て Enumerable で取り出したかったら…。

不思議な"&"（Ruby）

こんなコードが可能なのだな。
　

(2..10).map(&"5".to_i.method(:to_s))
#=>["101", "12", "11", "10", "5", "5", "5", "5", "5"]

やっていることは、"5" を 2~10 進数表記で表現するということですが…。意味はありません。

もうひとつ。

(1..5).map(&"Ruby!".method(:slice).curry(2).call(0))
#=>["R", "Ru", "Rub", "Ruby", "Ruby!"]

意味がわからないな（笑）。