The Art Gallery Guardian

Generate Polyominoes in APL


I have won the 3rd Place on 2013 APL Problem Solving Competition by solving one problem, the mathematical one. The judges decided that:

Chao used Dfns to produce clean, compact, and efficient code.  His solution for PolyGen was more than twice as fast as the next closest entry.

The other two problems are too messy for me to handle. Ahh, I’m not the engineering type.

Here is my submission with comments, and the problem itself can be seen here.

⍝ The canonical representation.
⍝ The matrix with width <= height and has
⍝ the smalelst value if expressed as a binary number.
CanonPoly←{
⍝ Remove zero rows
rm←{(⍵∨.≠0)⌿⍵}
allMatrix←{
⍝ Every mutation of the matrix(reflection and rotation)
allHorMat←{(⍵)(⍉⊖⍉⊖⍵)(⊖⍵)(⍉⊖⍉⍵)}
allVerMat←{(⍉⊖⍵)(⊖⍉⍵)(⍉⍵)(⊖⍉⊖⍵)}
⍝ We don't have to compute half of the matrices if
⍝ height doesn't equal to width.
>/⍴⍵:allHorMat ⍵
</⍴⍵:allVerMat ⍵
(allHorMat ⍵),allVerMat ⍵
}
m←allMatrix rm⍉rm ⍵
⍝ Represent the matrices as a binary number, and pick the smallest.
⊃m[⊃⍒{2⊥,⍵}¨m]
}
⍝ match a matrix in every direction.
⍝ Implemented by rotate the matrix in each direction, do the match, and rotate back.
Match ← {(⍺⍷⍵)∨(⊖⍉⍺⍷⍉⊖⍵)∨(⊖⍉⊖⍉⍺⍷⍉⊖⍉⊖⍵)∨(⍉⊖⍺⍷⊖⍉⍵)}
⍝ Two polyominoes are smiliar if and only if
⍝ they have the same canonical representation.
SimilarPoly ← {(CanonPoly ⍺) ≡ CanonPoly ⍵}
ValidPoly ← {
⍝ Expected input MUST BE a boolean matrix, otherwise undefined behavior.
⍝ First set a 1 to 2, then expand the area of 2 by BFS.
bfs ← {({(1 2 Match ⍵)+⍵}⍣(+/+/⍵))⍵}
⍝ The matrix represents a polyominoes if there is no 1 in the resulting matrix.
~(1 ∊ bfs ⍵+((⍴⍵)⍴<\,⍵))
}
PolyGen←{
⍝ Add a border of 0's.
br←{¯1⊖(⍵⍪0)⍪0}
⍝ remove duplicates.
nub←{((⍵⍳⍵)≡¨⍳⍴⍵)/⍵}
⍝ matrix with exactly one 1.
basis←{((×/⍵),⍵)⍴(1,(×/⍵)⍴0)}
⍝ Possible positions to add a new cell.
deltas←{(,(0 1 Match ⍵))⌿basis(⍴⍵)}
⍝ all possible polyominoes within one move from input polyomino
NextPoly←{nub CanonPoly¨⊂[2,3](deltas ⍵)+[2,3]⍵}
⍝ The set of polyominoes generated by adding one more cell to them
NextPolys←{nub⊃,/NextPoly¨br¨⍉¨br¨⍵}
⍝ Iterate NextPolys, starting from a set of monomino.
(NextPolys⍣(⍵-1)),⊂(1 1⍴1)
}
view raw Polyominoes.apl hosted with ❤ by GitHub

50 lines (include comments) for $750, not so bad.

Posted by Chao Xu on .
Tags: random.