Ruby の slice が便利になった

Python

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10][1:10:3]    #=>[2, 5, 8]

って便利ですよね。Ruby でこれをやろうとすると、ちょっと工夫が必要でした。

例えばこんな感じに。

1.step(9, 3).map { [*1..10][_1] }    #=>[2, 5, 8]

 
しかし、これはいまではこんな風に書けるようです。

s = (1...10).step(3)
s.class    #=>Enumerator::ArithmeticSequence
[*1..10].slice(s)    #=>[2, 5, 8]

 
これの応用で、さらに短く書けます。

[*1..10].slice((1...10) % 3)   #=>[2, 5, 8]
[*1..10][(1...10) % 3]   #=>[2, 5, 8]

便利ですね。

Ruby でコラッツの問題

ja.wikipedia.org
「コラッツの問題」というのは、自然数 n を取り、

  • n が偶数なら2で割る
  • n が奇数なら、3倍して1を足す

という操作を繰り返したところ、どうなるかという問題。じつはこれは難問で、いまだに解決されていない。いまのところ、初期値が268あたりまで、1に帰結することが知られているそうである。

Ruby で計算してみる。初期値が10万までの範囲での、1に至るステップ数の最大値を求めるコードを、再帰で実装する。

def collatz(n, co = 0)
  return co if n == 1
  n.even? ? collatz(n / 2, co + 1) : collatz(3 * n + 1, co + 1)
end

puts (1..10_0000).map(&method(:collatz)).max    #=>350

最大値は350ステップとわかる。実行時間は、僕の環境で0.94秒ほどでした。


350ステップかかるときの初期値を求めてみる。コードの後半をこう書き直す。

max = 0
max_idx = 1
(1..10_0000).each do |i|
  step = collatz(i)
  if step > max
    max = step
    max_idx = i
  end
end
p [max_idx, max]    #=>[77031, 350]

初期値が77031のとき350ステップかかることがわかる。
 

追記

メモ化できるよう、コードを修正してみる。

$memo = {}

def collatz(n)
  return $memo[n] if $memo[n]
  return 0 if n == 1
  sum = n.even? ? collatz(n / 2) : collatz(3 * n + 1)
  $memo[n] = sum + 1
end

puts (1..10_0000).map(&method(:collatz)).max    #=>350

これだと0.12秒で済む。100_0000回までやっても1.5秒ほど、ちなみに初期値が837799のとき、最大値524ステップを取る。もう一桁上げて、1000_0000回までやると、初期値8400511のとき、最大値685ステップ。

いまどきの 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)

20210116152153
 
コード。

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) -> &