Circle and Points

ヒビルテ 経由で、米国コンピュータ学会（ACM、The Association for Computing Machinery）主催の国際大学対抗プログラミングコンテストの過去問題より。Haskell の勉強を兼ねて さかいさんの Circle_and_Points.hs を Squeak の Smalltalk で例によって咀嚼のために直訳ぎみに。

| ifile pairs circles solve parsePoint parseProblems string problems answers |

pairs := nil.
pairs := [: abs |
   | aa bs |
   abs isEmpty ifTrue: [#()] ifFalse: [
   aa := abs first.
   bs := abs allButFirst.
   (bs collect: [: bb | {aa. bb}]), (pairs value: bs)]].

circles := [: pp : qq |
   | dd |
   dd := pp dist: qq.
   dd > 2 ifTrue: [#()] ifFalse: [
      | aa bb |
      aa := (qq y - pp y) arcTan: (qq x - pp x).
      bb := (dd / 2) arcCos.
      {aa + bb. aa - bb} collect: [: tt | (pp x + tt cos) @ (pp y + tt sin)]]].

solve := [: ps |
   ps isEmpty ifTrue: [0] ifFalse: [
      | xs |
      xs := OrderedCollection new.
      (pairs value: ps) do: [: pair |
         | pp qq |
         pp := pair first.
         qq := pair last.
         (circles value: pp value: qq) collect: [: cc |
            xs add: (ps count: [: point | (point dist: cc) <= 1])]].
      xs addFirst: 1.
      xs max]].

parsePoint := [: ss |
   ss collect: [: xy |
      | subStrings |
      subStrings := xy subStrings.
      subStrings first asNumber @ subStrings second asNumber]].

parseProblems := [: ss |
   | ff lines |
   ff := nil.
   ff := [: lls |
      | ll ls nn |
      ll := lls first.
      ls := lls allButFirst.
      nn := ll asNumber.
      nn = 0 ifTrue: [#()] ifFalse: [
         | ps rest |
         ps := ls first: nn.
         rest := ls allButFirst: nn.
         {parsePoint value: ps}, (ff value: rest)]].
   lines := OrderedCollection new.
   ss linesDo: [: line | lines add: line].
   ff value: lines].

ifile := FillInTheBlank request: 'input file name:' initialAnswer: 'D0.txt'.
ifile ifEmpty: [^ self].
string := (FileStream oldFileNamed: ifile) contents withSqueakLineEndings.
problems := parseProblems value: string.
answers := problems collect: [: points | solve value: points].
^ answers

これはブロックオブジェクト [...] の再帰を使っているので、ClosureCompiler が必要です。Squeak 3.8 では、SqueakMap から 2.2 と 2.9 （追記： 2.2 だけで大丈夫なようです。2.3 以降を入れるとデバッガの動きがおかしくなります。） をインストールしたのち、Preferences の #compileBlocksAsClosures を true にするとなんとなく（ぉぃ…）使えるようになります。

動きを把握したところで、Smalltalk っぽく書くのにチャレンジしたのがこちら。これはブロックの再帰はないので ClosureCompiler なしでも動きます。

| inputFileName stream nn results |

inputFileName := FillInTheBlank request: 'input file name:' initialAnswer: 'D0.txt'.
inputFileName ifEmpty: [^ self].

stream  := CrLfFileStream oldFileNamed: inputFileName.
results := OrderedCollection new.

[[(nn := stream nextLine asInteger) = 0 or: [stream atEnd]] whileFalse: [
   | points circlePositions counts |

   points := OrderedCollection new.

   nn timesRepeat: [
      | nums | 
      nums := stream nextLine subStrings collect: [: str | str asNumber].
      points add: nums first @ nums last].

   circlePositions := OrderedCollection new.

   points combinations: 2 atATimeDo: [: pair | 
      | delta dist |

      delta := pair last - pair first.
      dist := delta r.

      dist <= 2 ifTrue: [
         | theta aa bb |

         theta := (dist / 2) arcCos.
         aa := (delta rotateBy: theta about: 0 asPoint) normalized.
         bb := (delta rotateBy: theta negated about: 0 asPoint) normalized.

         circlePositions add: pair first + aa; add: pair first + bb]].

   counts := circlePositions collect: [: pos | points count: [: pt | (pos dist: pt) < 1.00001]].
   results add: 
      (counts isEmpty
         ifTrue: [1]
         ifFalse: [counts max])]] ensure: [stream ifNotNil: [stream close]].

^ results