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