問題の名前 : ぐるぐる数
問題 : http://nabetani.sakura.ne.jp/hena/orde31rotnum/
実装リンク集 : https://qiita.com/Nabetani/items/d139d5ef70aa23c2d038
次回のイベントは 4/6 最終回にするかも。
see https://yhpg.doorkeeper.jp/events/88379
で。
やや遅い実装
まずは、やや遅い実装。
# frozen_string_literal: true
require "json"
def next_vals(b,n)
[n, (n+1)%b]
end
def build_number(b, head, size, states)
(size-1).times.with_object([head]) do |ix,o|
candidates = next_vals(b, o.last).sort
o.push candidates[:low==states[ix] ? 0 : 1]
end
end
def undigits(b,d)
d.reverse_each.inject(0) do |acc,n|
acc*b+n
end
end
def build_states(b, digits)
r=digits.each_cons(2).with_object([]){ |(p,q),o|
candidates = next_vals( b, p )
o << %i(low high above)[candidates.count{ |e| e<q }]
break o unless candidates.include?(q)
}
r + [:low]*(digits.size-1-r.size)
end
def guru(b,digits)
states = build_states(b, digits)
above = states.index(:above)
return build_number(b, digits.first, digits.size, states) unless above
# 繰り上がり処理がある
n = undigits(b,digits[0,above+1].reverse)
d = (n+1).digits(b).reverse
head = guru(b,d)
head + [next_vals( b, head.last).min] * (digits.size-above-1)
end
def sup(b,x)
undigits(b, guru(b, x.digits(b).reverse).reverse)
end
def solve_impl( b, x, y )
x = sup(b,x)
count = 0
while x<=y
count+=1
x = sup(b,x+1)
end
count
end
def solve( src )
sb, *sxy = src.split(",")
b = sb.to_i
xy = sxy.map{ |e| e.to_i(b) }
if b==2
(xy[1] - xy[0]+1).to_s
else
solve_impl( b, *xy ).to_s
end
end
if __FILE__==$PROGRAM_NAME
json = File.open( ARGV[0], &:read)
data = JSON.parse( json, symbolize_names:true )
data[:test_data].map{ |number:, src:, expected:|
actual = solve( src )
ok = expected==actual
p [ (ok ? "ok" : "**NG**"), number, src, expected, actual ]
ok
}.tap{ |r| puts( r.all? ? "everything is okay" : "something wrong" ) }
end
ruby 1.rb data.json のように実行する。
「次に大きいぐるぐる数」という計算ができればよいというアイディアだけど、MikuriyaHiroshi さんのアイディアの方が平易なコードになっていいかもね。
ただ。
b が 2 のときはすべての数がぐるぐる数なので、この計算をするとえらく時間がかかる。
そこで b が 2 のときは単に引き算するというショートカットをしている。
手元のマシンで3秒弱。
速い実装
つづいてちゃんとした実装。
# frozen_string_literal: true
require "json"
def state(b, x)
x.each_cons(2).map{ |prev,cur|
lambda{ |lo,hi|
return :below if cur<lo
return :lo if cur==lo
return :mid if cur<hi
return :hi if cur==hi
return :above
}[*[ prev, (prev+1) % b ].sort]
}
end
def count_state( s )
return 1 if s.empty?
case s[0]
when :below then 0
when :lo then count_state(s.drop(1))
when :mid then 2**(s.size-1)
when :hi then count_state(s.drop(1)) + 2**(s.size-1)
when :above then 2**s.size
end
end
# x 以下の ぐるぐる数の個数
def guru_count( b, x )
# x.size 未満の桁数
s0 = (1...x.size).sum{ |keta| (b-1)*(2**(keta-1)) }
# x.size 桁で、先頭が 1..(x.first-1)
s1 = (x.first-1)*(2**(x.size-1))
# 先頭が x.first
s2 = count_state( state(b, x) )
[s0, s1, s2].sum
end
def solve( src )
sb,sx,sy = src.split(",")
b = sb.to_i
x = (sx.to_i(b) - 1).digits(b).reverse
y = sy.to_i(b).digits(b).reverse
ycount = guru_count(b,y)
xcount = guru_count(b,x)
( ycount - xcount ).to_s
end
if __FILE__==$PROGRAM_NAME
json = File.open( ARGV[0], &:read)
data = JSON.parse( json, symbolize_names:true )
data[:test_data].map{ |number:, src:, expected:|
actual = solve( src )
ok = expected==actual
p [ (ok ? "ok" : "**NG**"), number, src, expected, actual ]
ok
}.tap{ |r| puts( r.all? ? "everything is okay" : "something wrong" ) }
end
まずはこの手の問題の定石。
「0<=x<=y で、x<=i<=y である i について C(i)が真になる i の数は？」みたいな問題は、しばしば「0<=x で、0<=i<x である i について C(i)が真になる i の数」を求める関数を書くと楽になる。
で。
問題はその『「0<=x で、0<=i<x である i について C(i)が真になる i の数」を求める関数』の実装。
例えば。
455734 ( 10進数、6桁 )
よりも小さいぐるぐる数の数を数えたい。そうすると、これは
a) 1桁〜5桁のぐるぐる数 の数
b) 1〜3で始まる6桁のぐるぐる数 の数
c) 4で始まる6桁のぐるぐるで455734より小さいものの数
の三種類の合計になる。a と b は簡単に求まる。
c は
c1) 44 で始まる 6桁のぐるぐる数 の数
c2) 45 で始まる 455734 より小さい 6桁のぐるぐる数 の数
の2つに分けられる。
c1 は簡単に求まる。
c2 は「5で始まる 5桁のぐるぐる数」の数と同じになるので、再帰呼出しで解決できる
というわけ。
これを実行すると ruby自体の起動時間に隠れるぐらいの時間で計算が終わる。
まとめ
会場の方の反応を見ると、やや難しかった模様。
わりときれいな、それでいてオリジナリティのある問題だと思ったんだけど、どうだろう。
次回 4月6日(土曜)は、最終回になるかもしれない（ならないかもしれない）です。
ご興味がお有りなら是非。