Free polyominoes enumeration: Difference between revisions
→{{header|Haskell}}: Applied hlint hindent, reduced some sub-expressions, and now a little faster, without, I hope, reducing legibility too much
(Added Sidef) |
(→{{header|Haskell}}: Applied hlint hindent, reduced some sub-expressions, and now a little faster, without, I hope, reducing legibility too much) |
||
Line 1,003:
Code updated and slightly improved from: http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Generating_Polyominoes
<lang haskell>import
import Control.Arrow ((***), first)
import Data.Set (toList, fromList)
import
import Data.Bool (bool)
type Coord = Int
type Point = (Coord, Coord)
type Polyomino = [Point]
Line 1,017 ⟶ 1,021:
translateToOrigin :: Polyomino -> Polyomino
translateToOrigin p =
in
rotate90, rotate180, rotate270, reflect :: Point -> Point
rotate90 = uncurry (flip (
rotate180
rotate270 (x, y) = (-y, x)▼
reflect = first negate
-- All the plane symmetries of a rectangular region.
rotationsAndReflections :: Polyomino -> [Polyomino]
rotationsAndReflections
(fmap <$>
, rotate270
map (rotate90 . reflect) p,▼
, rotate270 . reflect
return
canonical :: Polyomino -> Polyomino
canonical = minimum . map (sort . translateToOrigin) . rotationsAndReflections
unique
unique :: (Ord a) => [a] -> [a]▼
:: (Ord a)
unique = toList . fromList
Line 1,051 ⟶ 1,064:
newPoints :: Polyomino -> [Point]
newPoints p =
newPolys :: Polyomino -> [Polyomino]
Line 1,058 ⟶ 1,071:
monomino = [(0, 0)]
monominoes = [monomino]
Line 1,067 ⟶ 1,081:
-- Generates a textual representation of a Polyomino.
textRepresentation p =
unlines
unlines [[if elem (x,y) p then '#' else ' ' | x <- [0 .. maxx - minx]]▼
[ [ bool ' ' '#'
▲ where
| y <- [0
where
maxima :: Polyomino -> Point
(minx, miny) = minima p▼
maxima (p:ps) = foldr (
(maxx, maxy) = maxima p
main :: IO ()
main = do
{{out}}
<pre>[1,1,2,5,12,35,108,369,1285,4655]
|