Edited at

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

More than 1 year has passed since last update.

問題 : 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)とさまざまだった。