オフラインリアルタイムどう書く E31 の実装例(Ruby)

問題の名前 : ぐるぐる数
問題 : http://nabetani.sakura.ne.jp/hena/orde31rotnum/
実装リンク集 : https://qiita.com/Nabetani/items/d139d5ef70aa23c2d038

次回のイベントは 4/6 最終回にするかも。
see https://yhpg.doorkeeper.jp/events/88379

で。

# やや遅い実装

まずは、やや遅い実装。

```ruby:ruby
# 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 さんのアイディア]( https://qiita.com/Nabetani/items/d139d5ef70aa23c2d038#comment-da9d83eaa0aaea54a8d3 )の方が平易なコードになっていいかもね。

ただ。
`b` が 2 のときはすべての数が**ぐるぐる数**なので、この計算をするとえらく時間がかかる。
そこで `b` が 2 のときは単に引き算するというショートカットをしている。

手元のマシンで3秒弱。

# 速い実装

つづいてちゃんとした実装。

```ruby:ruby
# 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日(土曜)]( https://yhpg.doorkeeper.jp/events/88379 )は、最終回になるかもしれない（ならないかもしれない）です。
ご興味がお有りなら是非。