辞書順で何番目か(Ruby)
辞書順(lexicographical order)に並べて何番目か、あるはn番目のものは何か。
要素に重複がないとして考える。数列 (1, 2, .... , n) の並べ替えとして解こう。
数列 (a1, .. , an) は辞書順で何番目か。
def number_in_lex_order(ary) n = ary.size return 1 if n <= 1 idx = ary.sort.bsearch_index { _1 >= ary[0] } (1..n - 1).inject(:*) * idx + number_in_lex_order(ary[1..-1]) end number_in_lex_order([2, 1, 5, 3, 4]) #=>29
ここでは、数列の左端の数字が、数列を昇順にソートした中で何番目に来るかがわからなければならない。それを i (=idx+1) とすると、そこまでで (n - 1)! * (i - 1) だけ既に(一桁少ない部分)数列が並んでいることになる(ただし n は ary の桁数)。
あとは左端の一桁を落として同じことを(再帰で)求め、すべての和をとってやれば求まる。
文字列などならば、ハッシュで数列に変換するテーブルを作ってやればよい。
str = "MATH" h = "AHMT".each_char.with_index(1).to_h number_in_lex_order(str.each_char.map { h[_1] }) #=>14
もっとも、文字列ならば Ruby の柔軟性(?)のおかげで、
number_in_lex_order("MATH".chars) #=>14
で求まってしまうのだが。
これの逆、つまり辞書順でn番目の数列はどうなるか。この場合、数列の長さ(size)を与えることが必要である。
def nth_sequence_in_lex_order(n, size) i = 1 table = (1..size - 1).map { i *= _1 } order = (1..size).to_a ans = [] n -= 1 size.pred.times do factorial = table.pop i = n / factorial n -= i * factorial ans << (a = order[i]) order.delete(a) break if n <= 0 end ans.concat(order) end
やってみる。
nth_sequence_in_lex_order(29, 5) #=>[2, 1, 5, 3, 4]
よさそうだ。
上と同様に、文字列でもやってみる。これも、ハッシュでテーブルを作り、Hash#invert する。
h = "AHMT".each_char.with_index(1).to_h.invert nth_sequence_in_lex_order(14, 4).map { h[_1] }.join #=>"MATH"
これもよさそうだ。
なお、いずれも不正入力には対応していない。
約数を求める(Ruby)
prime ライブラリを使う。結果は順不同。
require "prime" def divisors(n) result = [1] doit = ->(pd, acc) { return if pd.empty? x, *xs = pd (0..x[1]).each do |i| e = acc * x[0] ** i result << e doit.(xs, e) end } doit.(n.prime_division, 1) result.uniq end p divisors(24) #=>[1, 3, 2, 6, 4, 12, 8, 24]
numo-gnuplot sample
ウィンドウで表示する場合。Linux Mint 20.3。
require "numo/gnuplot" Numo.gnuplot do set terminal: "wxt font 'Noto Sans CJK JP,12'" set title: "グラフのタイトル" set xrange: 0..6 set yrange: 0..60 set xlabel: "x軸のラベル" set ylabel: "y軸のラベル" x = [1, 2, 3] y1 = [11, 25, 32] y2 = [21, 35, 42] y3 = [31, 45, 52] plot x, y1, {title: "系列1"}, x, y2, {w: :lines, title: "系列2(線のみ)"}, x, y3, {w: :linespoints, title: "系3(点と線)"}, "x * 10", {title: "y = x * 10"} end sleep
単調非減少と単調非増加で配列(Enumerator)を切断する
要するにこれです。
atcoder.jp
配列 A が与えられます。 A を何箇所かで切って、A の連続した部分であるようないくつかの数列に分けます。 この時、分けられたあとの数列は全て、単調非減少または単調非増加な列になっている必要があります。
コード
Enumerable にこんなメソッドupdown_cut
を生やしてみました。
module Enumerable def updown_cut e = to_enum updown = 0 calc = ->(compare) { case updown when 0 then [compare, false] when -1 case compare when -1, 0 then [-1, false] else [0, true] end else case compare when 1, 0 then [1, false] else [0, true] end end } begin a = e.next rescue StopIteration return self end pool = [a] loop do b = e.next updown, f = calc.(a <=> b) a = b if f yield pool pool = [a] else pool << a end end yield pool self end end
使い方
配列(あるいは Enumerator)を単調非減少、あるいは単調非増加な配列になるよう切ってくれます。切られた配列はブロック変数に入ります。
[1, 2, 3, 2, 2, 1].updown_cut { p _1 } #=> #[1, 2, 3] #[2, 2, 1] ary = ([*1..7] * 2).shuffle #=>[3, 1, 2, 7, 6, 7, 6, 5, 1, 5, 4, 4, 3, 2] ary.enum_for(:updown_cut).to_a #=>[[3, 1], [2, 7], [6, 7], [6, 5, 1], [5, 4, 4, 3, 2]] str = ("abcdef" * 4).chars.shuffle.join #=>"ecfdedcfecbabbbadfadcaef" str.each_char.enum_for(:updown_cut).map(&:join) #=>["ec", "fd", "edc", "fecba", "bbba", "df", "ad", "ca", "ef"]
いやあ、苦労しました。
Ractor でフィボナッチ数列
まずは小手調べ
take
するまで待って、take
するたびに無限に同じオブジェクトを返してくれる Ractor は、「Pull型通信」を使ってこんな風に作れる。
r = Ractor.new do loop { Ractor.yield 1 } end Array.new(5) { r.take } #=>[1, 1, 1, 1, 1]
わかりやすいですね。
では、例えば単調増加列も簡単に作れる。
r = Ractor.new do i = 1 loop do Ractor.yield i i += 1 end end Array.new(5) { r.take } #=>[1, 2, 3, 4, 5]
フィボナッチ数列を Ractor で計算してみる
こんなコードを書いてみた。
def fibonacci fib = Array.new(N + 1) 2.times do |i| fib[i] = Ractor.new(i) do |j| loop { Ractor.yield j } end end (2..N).each do |i| fib[i] = Ractor.new(fib[i - 1], fib[i - 2]) do |a, b| e = a.take + b.take loop { Ractor.yield e } end end fib[N].take end
fib[n]
はfib[n - 1]
とfib[n - 2]
が計算するまで待ち(これらすべて Ractor オブジェクト)、双方が計算を終了したらtake
されるのを待つ。それで、take
されるたび、計算結果を返し続ける。
ってまあ、ほとんど意味のないプログラムだが、計算と一種の「メモ化」ですね。おもしろいといえばおもしろい。パフォーマンスはどうかというと、N = 3000 としてわたしの環境で 3.4秒くらい。3001個の Ractor オブジェクトが生成されるわけだが、どうなのかな。
なお、fib[3000].take
の結果は、
4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555802606991585915229492453904998722256795316982874482472992263901833716778060607011615497886719879858311468870876264597369086722884023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717881930324025204312082516817125
という具合です。
Hit&Blow を Ruby で
qiita.comおもしろそうなので、自分でも書いてみた。
ルール
コンピュータの決めた、各桁に重複のない3桁の数を当てるゲーム。
当たらなかった場合、
- 入力と桁の合っている数字の数を、ヒット
- 入力と桁は合っていないが重複はしている数字の数を、ブロウ
として教えてくる。
実行例
各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 135 ヒット:1, ブロウ:0 各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 315 ヒット:0, ブロウ:1 各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 351 ヒット:0, ブロウ:1 各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 124 ヒット:1, ブロウ:0 各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 106 ヒット:1, ブロウ:1 各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 160 ヒット:2, ブロウ:0 各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 170 ヒット:2, ブロウ:0 各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 180 ヒット:2, ブロウ:0 各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 190 正解です! 9回で当てました!
コード
hit_and_blow.rb
module Hit_and_Blow module_function N = 3 def input expl = (0...N).to_a.join loop do print "各桁のそれぞれちがう、#{N}桁の数を入力して下さい(例:#{expl}): " s = gets.chomp.chars if s.size != N || s.uniq.size != N || s.any?(/\D/) puts "不正な入力です。" else return s end end end def judge(target, number) overlap = (target & number).size hit = target.zip(number).count { |a, b| a == b } [hit, overlap - hit] end def play target = [*"0".."9"].sample(N) (1..).each do |n| number = input if target == number puts "正解です! #{n}回で当てました!" break else hit, blow = judge(target, number) puts "ヒット:#{hit}, ブロウ:#{blow}" end end end end Hit_and_Blow.play
N = 3
だと簡単ですが、N = 4
にすると結構手ごわいです。
Enumerator#rest みたいなのが欲しい
Ruby の Enumerator で、列挙はひとつずつしかできない。まとめていくつか列挙できるメソッドが欲しい。
こんな感じ。
class Enumerator def rest(n=nil) ary = [] case n in nil loop { ary << self.next } in Integer => a a.times { ary << self.next } end ary end end a = [*1..10].to_enum a.next #=>1 a.next #=>2 a.rest(4) #=>[3, 4, 5, 6] a.next #=>7 a.rest #=>[8, 9, 10]
ダメですかねえ…。