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

オフラインリアルタイムどう書くE28の問題「増築の果ての隣室」の実装例を、ruby で。

問題 : http://nabetani.sakura.ne.jp/hena/orde28sqst/
実装リンク集 : https://qiita.com/Nabetani/items/4e3fac2746ca05a93165
イベント : https://yhpg.doorkeeper.jp/events/81346

次回のイベントは 12/8。
詳しくは
https://yhpg.doorkeeper.jp/events/82699
を御覧ください。

で。
実装例は以下の通り：

```ruby:ruby2.5
require "json"

class Sq < Struct.new( :topleft, :w )
  def top
    topleft.imag
  end
  def bottom
    topleft.imag+w
  end
  def left
    topleft.real
  end
  def right
    topleft.real+w
  end
  def horz
    [left, right]
  end
  def vert
    [top, bottom]
  end
end

def sq(x,y,w)
  Sq.new( x+y*1i, w )
end

def add( (dir,count), f )
  t = f.map(&:top).min
  b = f.map(&:bottom).max
  r = f.map(&:right).max
  l = f.map(&:left).min
  f+case dir
  when "N"
    w = (r-l)/count
    (0...count).map{ |x| sq(l+x*w, t-w, w) }
  when "S"
    w = (r-l)/count
    (0...count).map{ |x| sq(l+x*w, b, w) }
  when "W"
    w = (b-t)/count
    (0...count).map{ |x| sq(l-w, t+w*x, w) }
  when "E"
    w = (b-t)/count
    (0...count).map{ |x| sq(r, t+w*x, w) }
  end
end

def build( ops )
  n = ops.inject(1){ |acc, (dir,count)| acc * count }
  ops.inject( [sq(0,0,n)] ){ |acc,op|
    add( op, acc )
  }
end

def has_intersection?(a, b)
  if a.min<b.min
    b.min<a.max
  elsif b.min<a.min
    a.min<b.max
  else
    true
  end
end

def nei?(a,b)
  if a.top==b.bottom || b.top==a.bottom
    has_intersection?(a.horz, b.horz)
  elsif a.left==b.right || b.left==a.right
    has_intersection?(a.vert, b.vert)
  else
    false
  end
end

def solve(src)
  sops, snum = src.split("/")
  ops = sops.chars.each_slice(2).map{ |d,n| [d,n.to_i] }
  num = snum.to_i
  f = build( ops )
  myroom = f[num-1]
  f.size.times.select{ |n|
    nei?(myroom, f[n])
  }.map{ |n| n+1 }.join(",")
end

if $0==__FILE__
  data = JSON.parse(DATA.read, symbolize_names: true)
  data[:test_data].map{ | number:, src:, expected: |
    actual = solve( src )
    okay = actual == expected
    puts [ number, (okay ? "ok" : "**NG**"), actual, expected ].join(" ")
    okay
  }.all?.yield_self{ |x| puts( x ? "okay" : "SOMETHING WRONG" ) }
end

__END__
{"event_id":"E28","event_url":"COMING SOON","test_data":[
  {"number":0,"src":"N7N4E5/8","expected":"1,7,12,13,14"},
  {"number":1,"src":"E1/1","expected":"2"},
  {"number":2,"src":"N6/5","expected":"1,4,6"},
  {"number":75,"src":"N9S9S3S6N6S7N8W4E9W7E3N5W8S9E9E9W6N3N9W8/119","expected":"73,74,78,113,120,122,123,124,131,132,133,134"}
]}
```

テストデータの大半は省略。
で。

ruby なので有理数を使えるからそこは楽できるんだけど、整数だけでも行けるよ、ということを示すためにこの実装では有理数は使っていない。

64bit 整数があれば間に合うようにテストデータを作った（JSユーザーの方、ごめんなさい）ので、C++ や Java なんかでも上記コードと同じようなことをすれば、困らずに書ける。

`add` の中で毎回 上端下端右端左端 を計算しているのでそこは計算量としてひどくもったいない感じになっている。手抜きである。

複素数を使っているものの、まったく活かせていない。こんなことなら普通に top と left を別変数にすればよかったと後悔している。

会場では、`add` 内の `f+case dir` のあたりが気持ち悪いと言われた。私としてはスッキリ書けた気がしているんだけどなぁ。一度変数に受けたほうが良かったか。

メソッドの引数で配列を分解する `def add( (dir,count), f )` も気持ち悪かったようだけど、こちらは書いている私自身も気持ち悪いと思っていた。

実相戦略は概ね上記のソースのものしかないと思う。
一部のケースで楽できるパターンもあるが、煩雑になる割にメリットが少ないと思う。

この問題は

1. なんか地図を書こう
2. 東西南北に正方形を足していくの楽しそうだ
3. 楽しい図はできたけど、何を問おうか
4. 隣のマスの番号を問う以外にいい設問が思いつかない...

という流れで作られた。「隣のマスの番号を問う」を避けたかったのは、以前 CodeIQ で同じことを問う問題を出しているから。まあ地図がぜんぜん違うから似たような問題ではないんだけれども。