bonotakeの日記

ソフトウェア工学系研究者 → AIエンジニア → スクラムマスター・アジャイルコーチ

どう書く?.org『島の数をカウントする』をAlloyで解いてみた

アルゴリズム書かなくていいので行数短くなるかなと思ったら、マップの制約を書くのに行数食ってしまうという罠。

問題

m×nの長方形のマス目のうちいくつかを黒く塗りつぶします。
このとき、白の島、黒の島がそれぞれいくつあるかをカウントしてください。

ただし、2つのマスは、同色マスの上下左右の移動で移れるとき、
同じ島にあると定義します。

例:
□■■□
□□■□
□■□□
□■■□
白の島は2つ
黒の島は2つ

例:
□□□□
■□■□
□■□□
□□□□
白の島は1つ
黒の島は3つ

解答

キモとなる島の判定ロジックは、次のように書いてます。

fact islandLaw {
  all disj s,s': Square | s.island = s'.island iff
      s' in s.^{s1,s2: Square | (s2 in s1.(left+down) or s1 in s2.(left+down)) and s1.color = s2.color } 
}

要は「隣同士で色が同じになってるマスをずっと辿っていって、到達するマスは全部同じ島」ってことです。


以下は「仕様」全文。

one sig Answer {
  width, height, blackIslands, whiteIslands: Int
}
{
  blackIslands = #{x: Island | some g:Square | g.island = x and g.color = Black} 
  whiteIslands = #{x: Island | some g:Square | g.island = x and g.color = White} 
}
sig Square {
  row, col: Int,
  left, down: lone Square,
  color: Color,
  island: Island
}
abstract sig Color {}
one sig White, Black extends Color {}
sig Island {}
fact islandLaw {
  all disj s,s': Square | s.island = s'.island iff
      s' in s.^{s1,s2: Square | (s2 in s1.(left+down) or s1 in s2.(left+down)) and s1.color = s2.color } 
}

fact squareLaws {
  all s1, s2: Square | s1.row = s2.row and s1.col = s2.col iff s1 = s2
  all g: Square {
    g.col = Answer.width - 1 => no g.left
      else g.left.row = g.row and g.left.col = g.col + 1
    g.row = Answer.height - 1 => no g.down
      else g.down.row = g.row + 1 and g.down.col = g.col
  }
}
pred setSquare (r,c: Int, cl: Color) {
  some g: Square | g.row = r and g.col = c and g.color = cl
}

pred example1 () {
  Answer.width = 4 and Answer.height = 4
  setSquare[0,0,White] and setSquare[0,1,Black] and setSquare[0,2,Black] and setSquare[0,3,White]
  setSquare[1,0,White] and setSquare[1,1,White] and setSquare[1,2,Black] and setSquare[1,3,White]
  setSquare[2,0,White] and setSquare[2,1,Black] and setSquare[2,2,White] and setSquare[2,3,White]
  setSquare[3,0,White] and setSquare[3,1,Black] and setSquare[3,2,Black] and setSquare[3,3,White]
}
run example1 for 16

pred example2 () {
  Answer.width = 4 and Answer.height = 4
  setSquare[0,0,White] and setSquare[0,1,White] and setSquare[0,2,White] and setSquare[0,3,White]
  setSquare[1,0,Black] and setSquare[1,1,White] and setSquare[1,2,Black] and setSquare[1,3,White]
  setSquare[2,0,White] and setSquare[2,1,Black] and setSquare[2,2,White] and setSquare[2,3,White]
  setSquare[3,0,White] and setSquare[3,1,White] and setSquare[3,2,White] and setSquare[3,3,White]
}
run example2 for 16

pred noExample () { -- おまけ:マップも自動生成
  Answer.width = 4 and Answer.height = 4
}
run example2 for 16
注:bonotakeは、amazon.co.jpを宣伝しリンクすることによってサイトが紹介料を獲得できる手段を提供することを目的に設定されたアフィリエイト宣伝プログラムである、 Amazonアソシエイト・プログラムの参加者です。