Anonymous user
Free polyominoes enumeration: Difference between revisions
+ slow D, slow Haskell, slow Python versions
(First draft of the task) |
(+ slow D, slow Haskell, slow Python versions) |
||
Line 35:
Number of free polyominoes (or square animals) with n cells:
http://oeis.org/A000105
=={{header|D}}==
{{trans|Haskell}}
<lang d>import std.stdio, std.range, std.algorithm, std.typecons, std.conv;
alias Coord = byte;
alias Point = Tuple!(Coord,"x", Coord,"y");
alias Polyomino = Point[];
/// Finds the min x and y coordiate of a Polyomino.
enum minima = (in Polyomino poly) pure @safe =>
Point(poly.map!q{ a.x }.reduce!min, poly.map!q{ a.y }.reduce!min);
Polyomino translateToOrigin(in Polyomino poly) {
const minP = poly.minima;
return poly.map!(p => Point(cast(Coord)(p.x - minP.x), cast(Coord)(p.y - minP.y))).array;
}
enum Point function(in Point p) pure nothrow @safe @nogc
rotate90 = p => Point( p.y, -p.x),
rotate180 = p => Point(-p.x, -p.y),
rotate270 = p => Point(-p.y, p.x),
reflect = p => Point(-p.x, p.y);
/// All the plane symmetries of a rectangular region.
auto rotationsAndReflections(in Polyomino poly) pure nothrow {
return only(poly,
poly.map!rotate90.array,
poly.map!rotate180.array,
poly.map!rotate270.array,
poly.map!reflect.array,
poly.map!(pt => pt.rotate90.reflect).array,
poly.map!(pt => pt.rotate180.reflect).array,
poly.map!(pt => pt.rotate270.reflect).array);
}
enum canonical = (in Polyomino poly) =>
poly.rotationsAndReflections.map!(pl => pl.translateToOrigin.sort().release).reduce!min;
auto unique(T)(T[] seq) pure nothrow {
return seq.sort().uniq;
}
/// All four points in Von Neumann neighborhood.
enum contiguous = (in Point pt) pure nothrow @safe @nogc =>
only(Point(cast(Coord)(pt.x - 1), pt.y), Point(cast(Coord)(pt.x + 1), pt.y),
Point(pt.x, cast(Coord)(pt.y - 1)), Point(pt.x, cast(Coord)(pt.y + 1)));
/// Finds all distinct points that can be added to a Polyomino.
enum newPoints = (in Polyomino poly) nothrow =>
poly.map!contiguous.joiner.filter!(pt => !poly.canFind(pt)).array.unique;
enum newPolys = (in Polyomino poly) =>
poly.newPoints.map!(pt => canonical(poly ~ pt)).array.unique;
/// Generates polyominoes of rank n recursively.
Polyomino[] rank(in uint n) {
static immutable Polyomino monomino = [Point(0, 0)];
static Polyomino[] monominoes = [monomino]; // Mutable.
if (n == 0) return [];
if (n == 1) return monominoes;
return rank(n - 1).map!newPolys.join.unique.array;
}
/// Generates a textual representation of a Polyomino.
char[][] textRepresentation(in Polyomino poly) pure @safe {
immutable minPt = poly.minima;
immutable maxPt = Point(poly.map!q{ a.x }.reduce!max, poly.map!q{ a.y }.reduce!max);
auto table = new char[][](maxPt.y - minPt.y + 1, maxPt.x - minPt.x + 1);
foreach (row; table)
row[] = ' ';
foreach (immutable pt; poly)
table[pt.y - minPt.y][pt.x - minPt.x] = '#';
return table;
}
void main(in string[] args) {
iota(1, 11).map!(n => n.rank.length).writeln;
immutable n = (args.length == 2) ? args[1].to!uint : 5;
writefln("\nAll free polyominoes of rank %d:", n);
foreach (const poly; n.rank)
writefln("%-(%s\n%)\n", poly.textRepresentation);
}</lang>
{{out}}
<pre>[1, 1, 2, 5, 12, 35, 108, 369, 1285, 4655]
All free polyominoes of rank 5:
#
#
#
#
#
##
#
#
#
#
##
#
#
##
##
#
##
#
##
###
#
#
#
###
#
#
#
##
#
#
###
#
#
##
##
#
###
#
#
###
#</pre>
=={{header|Haskell}}==
This Haskell solution is relatively slow, it's meant to be readable and as manifestly correct as possible.
<lang haskell>import Data.List (sort)
import Data.Set (toList, fromList)
import System.Environment (getArgs)
type Coord = Int
type Point = (Coord, Coord)
type Polyomino = [Point]
-- Finds the min x and y coordiate of a Polyomino.
minima :: Polyomino -> Point
minima (p:ps) = foldr (\(x, y) (mx, my) -> (min x mx, min y my)) p ps
translateToOrigin :: Polyomino -> Polyomino
translateToOrigin p =
let (minx, miny) = minima p in
map (\(x, y) -> (x - minx, y - miny)) p
rotate90, rotate180, rotate270, reflect :: Point -> Point
rotate90 (x, y) = ( y, -x)
rotate180 (x, y) = (-x, -y)
rotate270 (x, y) = (-y, x)
reflect (x, y) = (-x, y)
-- All the plane symmetries of a rectangular region.
rotationsAndReflections :: Polyomino -> [Polyomino]
rotationsAndReflections p =
[p,
map rotate90 p,
map rotate180 p,
map rotate270 p,
map reflect p,
map (rotate90 . reflect) p,
map (rotate180 . reflect) p,
map (rotate270 . reflect) p]
canonical :: Polyomino -> Polyomino
canonical = minimum . map (sort . translateToOrigin) . rotationsAndReflections
unique :: (Ord a) => [a] -> [a]
unique = toList . fromList
-- All four points in Von Neumann neighborhood.
contiguous :: Point -> [Point]
contiguous (x, y) = [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]
-- Finds all distinct points that can be added to a Polyomino.
newPoints :: Polyomino -> [Point]
newPoints p =
let notInP = filter (not . flip elem p) in
unique . notInP . concatMap contiguous $ p
newPolys :: Polyomino -> [Polyomino]
newPolys p = unique . map (canonical . flip (:) p) $ newPoints p
monomino = [(0, 0)]
monominoes = [monomino]
-- Generates polyominoes of rank n recursively.
rank :: Int -> [Polyomino]
rank 0 = []
rank 1 = monominoes
rank n = unique . concatMap newPolys $ rank (n - 1)
-- Generates a textual representation of a Polyomino.
textRepresentaton :: Polyomino -> String
textRepresentaton p =
unlines [[if elem (x,y) p then '#' else ' ' | x <- [0 .. maxx - minx]]
| y <- [0 .. maxy - miny]]
where
maxima :: Polyomino -> Point
maxima (p:ps) = foldr (\(x, y) (mx, my) -> (max x mx, max y my)) p ps
(minx, miny) = minima p
(maxx, maxy) = maxima p
main = do
print $ map (length . rank) [1 .. 10]
args <- getArgs
let n = if null args then 5 else read $ head args :: Int
putStrLn ("\nAll free polyominoes of rank " ++ show n ++ ":")
mapM_ putStrLn $ map textRepresentaton $ rank n</lang>
{{out}}
<pre>[1,1,2,5,12,35,108,369,1285,4655]
All free polyominoes of rank 5:
#
#
#
#
#
##
#
#
#
#
##
#
#
##
##
#
##
#
##
###
#
#
#
###
#
#
#
##
#
#
###
#
#
##
##
#
###
#
#
###
# </pre>
=={{header|Python}}==
{{trans|Haskell}}
<lang python>from itertools import imap, imap, groupby, chain, imap
from operator import itemgetter
from sys import argv
from array import array
def concat_map(func, it):
return list(chain.from_iterable(imap(func, it)))
def minima(poly):
"""Finds the min x and y coordiate of a Polyomino."""
return (min(pt[0] for pt in poly), min(pt[1] for pt in poly))
def translate_to_origin(poly):
(minx, miny) = minima(poly)
return [(x - minx, y - miny) for (x, y) in poly]
rotate90 = lambda (x, y): ( y, -x)
rotate180 = lambda (x, y): (-x, -y)
rotate270 = lambda (x, y): (-y, x)
reflect = lambda (x, y): (-x, y)
def rotations_and_reflections(poly):
"""All the plane symmetries of a rectangular region."""
return (poly,
map(rotate90, poly),
map(rotate180, poly),
map(rotate270, poly),
map(reflect, poly),
[reflect(rotate90(pt)) for pt in poly],
[reflect(rotate180(pt)) for pt in poly],
[reflect(rotate270(pt)) for pt in poly])
def canonical(poly):
return min(sorted(translate_to_origin(pl)) for pl in rotations_and_reflections(poly))
def unique(lst):
lst.sort()
return map(next, imap(itemgetter(1), groupby(lst)))
# All four points in Von Neumann neighborhood.
contiguous = lambda (x, y): [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]
def new_points(poly):
"""Finds all distinct points that can be added to a Polyomino."""
return unique([pt for pt in concat_map(contiguous, poly) if pt not in poly])
def new_polys(poly):
return unique([canonical(poly + [pt]) for pt in new_points(poly)])
monomino = [(0, 0)]
monominoes = [monomino]
def rank(n):
"""Generates polyominoes of rank n recursively."""
assert n >= 0
if n == 0: return []
if n == 1: return monominoes
return unique(concat_map(new_polys, rank(n - 1)))
def text_representation(poly):
"""Generates a textual representation of a Polyomino."""
min_pt = minima(poly)
max_pt = (max(p[0] for p in poly), max(p[1] for p in poly))
table = [array('c', ' ') * (max_pt[1] - min_pt[1] + 1)
for _ in xrange(max_pt[0] - min_pt[0] + 1)]
for pt in poly:
table[pt[0] - min_pt[0]][pt[1] - min_pt[1]] = '#'
return "\n".join(row.tostring() for row in table)
def main():
print [len(rank(n)) for n in xrange(1, 11)]
n = int(argv[1]) if (len(argv) == 2) else 5
print "\nAll free polyominoes of rank %d:" % n
for poly in rank(n):
print text_representation(poly), "\n"
main()</lang>
{{out}}
<pre>[1, 1, 2, 5, 12, 35, 108, 369, 1285, 4655]
All free polyominoes of rank 5:
#####
####
#
####
#
###
##
###
# #
###
#
#
###
#
#
###
##
##
##
#
##
##
#
##
#
##
#
###
# </pre>
| |||