ビット操作メソッド三題（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!"]

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

Object#method とカリー化で関数型っぽく（Ruby）

Object#method はメソッドをオブジェクト化するものである。
　

Method は取り出しの対象であるメソッドがなければ作れませんが、Proc は準備なしに作れます。その点から Proc は使い捨てに向き、Method は何度も繰り返し生成する場合に向くと言えます。また内包するコードの大きさという点では Proc は小規模、Method は大規模コードに向くと言えます。

https://docs.ruby-lang.org/ja/latest/class/Method.html

　
例として、ここのダイクストラ法のメソッドを使ってみる。まず、Hash で全体のグラフ構造を与える。

graph = {s: {t: 6, y: 4}, t: {x: 3, y: 2},
         x: {z: 4}, y: {z: 3, t: 1, x: 9}, z: {s: 7, x: 5}}

このグラフに対して、始点を与えてダイクストラ法を実行する関数を、Method オブジェクトから作ってみる。

dijkstra = method(:dijkstra).curry
give_shortest = dijkstra.(graph)

これで、例えば始点:s、:xを与えて最短経路が求められる。

give_shortest.(:s).first    #=>{:s=>0, :t=>5, :y=>4, :z=>7, :x=>8}
give_shortest.(:x).first    #=>{:x=>0, :z=>4, :s=>11, :t=>16, :y=>15}

例えば:sを始点としたとき、:xまでの最短距離は8であるとわかる。同様に、:xを始点としたとき、:sまでの最短距離は11である。

次いで、始点と終点を与え、最短距離と最短経路を出力する関数を作ってみる。

calc_path = ->(dijkstra_func, start, goal) {
  shortest, pred = dijkstra_func.(start)
  
  route = [goal]
  route.unshift(pred[route[0]]) until route[0] == start

  [shortest[goal], route]
}.curry
shortest_path = calc_path.(give_shortest)

こんな風に使える。

shortest_path.(:s, :x)    #=>[8, [:s, :y, :t, :x]]
shortest_path.(:x, :s)    #=>[11, [:x, :z, :s]]

つまり、始点が:sで終点が:xのとき、最短経路は8で、その経路は s→y→t→x の順であるとわかる。

このように、Method オブジェクトがカリー化されたgive_shortestが、何度も使い回されていることがわかると思う。これを変えれば、同じコードで別のグラフにも簡単に対応できる。

メソッドと Proc の相互変換（Ruby）

これらができたからとて、特にうれしいことはない感じです。

メソッド→Proc。Object#method と Method#to_proc を使う。

m = 100.method(:to_s)

p m    #=>#<Method: Integer#to_s(*)>
p m.call(2)    #=>"1100100"

pr = m.to_proc

p pr    #=>#<Proc:0x000055e967ad8300 (lambda)>
p pr.call(16)    #=>"64"

　
Proc→メソッド。Proc は無名関数なので、メソッド名が必要。あとは Module#define_method を使えばよい。

pr = ->(n, base) {n.to_s(base)}

define_method(:to_string, pr)

p to_string(100, 16)    #=>"64"

最大値をもつものを集める（Ruby）

例えば都道府県名をローマ字化したものから、文字数の最大値と、その文字数をもつすべての県名を得たいとする。そのとき、こんなメソッドを作ってみるといいかも知れない。
　

module ExEnumerable
  refine Enumerable do
    def max_select
      pool = []
      max_num = -Float::INFINITY
      each do |i|
        n = yield(i)
        if n > max_ num
          max_ num = n
          pool = [i]
        elsif n == max_ num
          pool << i
        end
      end
      [max_ num, pool]
    end
  end

  [Array, Enumerator, Hash].each {|mdl| mdl.include Enumerable}
end

Enumerable#max_selectは、ブロックの返り値の最大値（max_num）を求めて、そのような最大値になるようなものをレシーバーから集め（pool）、[max_num, pool]を返す。

これを使って、最初の課題を解いてみる。

require "open-uri"
using ExEnumerable

url = "https://gist.githubusercontent.com/koseki/38926/raw/671d5279db1e5cb2c137465e22424c6ba27f4524/todouhuken.txt"
prefectures = URI.open(url).each_line.map {|l| l.chomp.split.last}
prefectures.max_select(&:size)
#=>[9, ["fukushima", "yamanashi", "hiroshima", "yamaguchi", "tokushima", "kagoshima"]]

9文字が最大値だとわかる。県名のリストも返ってくる。

※参考
Ruby で関数型プログラミングっぽく（コピペ） + Haskell 版 - Camera Obscura