Help us understand the problem. What is going on with this article?

オフラインリアルタイムどう書く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)とさまざまだった。

Nabetani
横浜へなちょこプログラミング勉強会をやっていました。 / CodeIQ の出題者でした。 / 日経 WinPC に連載を持っていました(名義が違うけど) / Yokohama rb に半分ぐらい参加しています。 / twitter : http://twitter.com/Nabetani
https://nabetani.hatenadiary.com/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away