オフラインリアルタイムどう書くE23の実装例

問題 : http://nabetani.sakura.ne.jp/hena/orde23nokoch/
イベント : https://yhpg.doorkeeper.jp/events/71800
実装リンク集 : https://qiita.com/Nabetani/items/77e7e2c749767f197c0e

で。

最初に書いた実装

最初に書いたのは

ruby2.5

def dir_at( seq, pos )
  dirs = seq.reverse.chars.map{ |x| { "a"=>[0,5,1,0], "b"=>[0,5,0,1,0] }[x] }
  r=0
  dirs.each do |d|
    r += d[pos % d.size]
    pos /= d.size
  end
  return pos!=0 ? nil : r % 6
end

def solve(src)
  num, rules = src.split(",")
  dir = dir_at(rules, num.to_i - 1 )
  return "x" unless dir
  return "0-+"[dir % 3 ]
end

DATA.map do |line|
  num, src, expected = line.split(/\s+/ )
  actual = solve(src)
  okay = actual == expected
  p [ (okay ? "ok" : "**NG**"), src, actual, expected ]
  okay
end.all?.yield_self{ |ok| puts( ok ? "ok" : "something wrong" ) }

__END__
0 120,aabb  0 
1 100,a x 
2 3,a - 
3 3,b 0 
4 9,aa  - 

こんな感じ。
テストデータの大半は省略。

5 または 4 で割ったあまりが一番細かい部品の、線分の番号になる。
5 または 4 で割ることで、細部を無視した図形の、線分の番号になる。
ということ。

再帰を使って書き直した

フラクタルなんだから再帰だよね。ということで、再帰を使って dir_at を書き直した。

先ほどの実装は 細部→概要 という順に計算したけど、今回は 概要→細部 という順に計算した。

ruby2.5

M={ "a"=>[0,5,1,0], "b"=>[0,5,0,1,0] }
L=M.keys.each.with_object({}){ |k,o| o[k]=M[k].size }

def dir_at( seq, pos )
  return 0 if seq.empty?
  baselen, subpos = pos.divmod( seq.chars.drop(1).map{ |x| L[x] }.inject(1, :*) )
  base = M[seq[0]][baselen]
  base && dir_at(seq[1..-1], subpos )+base
end

こんな感じ。
概要を先に計算する都合で、 inject で掛け算している。

会場では、実際に線分の向きのリストを生成している方が多かった。
処理系によって 10秒で終わったり(Haskell)、2時間を超えたり(SQL)、エラーで死んだり(node.js)とさまざまだった。