Codeへの愛とCuriosity

CodeIQ への出題・解説解題・その周辺について、思いつくままに。

位置関係2題の解説・解題

先日、CodeIQ に出していた

という２つの問題が締め切られた。

私が出した問題が締め切られるのは久々だったので、ちょっと慣れない感じ。

で。

この問題は、タイトルの通り、2つの図形の位置関係を分類する問題になっている。
２つの円の方は、中心と中心の距離を見ればいいだけなので簡単。
円と線分はいろいろ見なくちゃいけないし、分類も多いのでちょっと大変、ということになっている。

数学力はあまり問うていないつもり。高校程度なんだと思う。

いつもなら、一つの事象をひとつのテストデータにするんだけど、今回はそれだと件数が多くなりすぎる感じなので、ひとつのテストデータにたくさんの事象を仕込むことにした。


問題の概要については
http://ange1.hateblo.jp/entry/2016/07/23/001128
をご覧いただくことにして、出題意図を列挙すると。

  • ごちゃごちゃした分類を誤らずに実装できるかどうか
  • 浮動小数点の除算や平方根を使うべきではないという判断ができるかどうか

というつもり。浮動小数点を使っても解決できてしまう場合が多かったようで、この点はテストデータの追い込みが足りなかったと反省している。


「接する」というデリケートな条件を判断する必要がある問題になっているので、誤差がまったくない計算をする必要がある。そして、この問題はそのような実装を無理なくできる問題になっている。入力は整数だし。


誤差のない計算ということで、有理数が簡単に扱える ruby や python だと実装が楽になる。
JavaScript だと苦しい感じかもしれない。


私の場合はやっぱり ruby でこんな感じ：

２つの円の位置関係の実装例：

def solve_one(s)
  x0,y0,r0,x1,y1,r1 = s.scan( /\d+/ ).map(&:to_i)
  d2 = (x0-x1)**2 + (y0-y1)**2
  r0,r1=[r0,r1].minmax
  return "A" if d2==0 && r0==r1
  sr2 = (r0+r1)**2
  return "F" if sr2<d2
  return "E" if sr2==d2
  dr2=(r1-r0)**2
  return "B" if d2<dr2
  return "C" if d2==dr2
  return "D" if d2>dr2
  raise "unexpected"
end

def solve( src )
  src.split(" ").map{ |s|
    solve_one( s )
  }.join("")
end

puts solve(gets)

円と線分の位置関係の実装例：

def calc_min2( a, b, c )
  candidates=[
    c, # x==0
    a+b+c # x==1
  ]
  x=-b/2.to_r/a
  candidates.push( a*x*x+b*x+c ) if 0<=x && x<=1
  candidates.min
end

def solve_one(s)
  cx,cy,r,ax,ay,bx,by = s.scan( /\d+/ ).map(&:to_r)
  ax-=cx
  ay-=cy
  bx-=cx
  by-=cy
  a=ax*ax+ay*ay<=>r*r
  b=bx*bx+by*by<=>r*r
  return "A" if a<0 && b<0
  return "C" if a==0 && b==0
  return "B" if a<=0 && b<=0
  return "F" if a*b<0
  vx=bx-ax
  vy=by-ay
  min2 = calc_min2(vx*vx+vy*vy, 2*(ax*vx+ay*vy), ax*ax+ay*ay )
  case min2<=>r*r
  when -1; a*b==0  ? "D": "E"
  when 0; a*b==0  ? "G": "H"
  when 1; "I"
  end
end

def solve( src )
  src.split(" ").map{ |s|
    solve_one( s )
  }.join("")
end

puts solve(gets)

我ながらもう少しなんとかならなかったのかと思わなくもない。

ともあれ。


多くの方に挑戦いただき大変うれしく思っています。ありがとうございました。