Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What are the problem?

More than 3 years have passed since last update.

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

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
0
Help us understand the problem. What are the problem?