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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
⍝ 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) | |
} |
50 lines (include comments) for $750, not so bad.