Rosetta Code

Free polyominoes enumeration: Difference between revisions

Page Discussion

Free polyominoes enumeration (view source)

Revision as of 11:01, 6 December 2023

80,160 bytes added ,  5 months ago
m
→‎{{header|Wren}}: Minor tidy
m (→‎{{header|Java}}: small changes)
m (→‎{{header|Wren}}: Minor tidy)
 
(22 intermediate revisions by 11 users not shown)
Line 24:
# # # #
#</pre>
Or perhaps with corner characters (rank 5):
<pre> ┌───┐ ┌─────┐ ┌─┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌─┐ ┌─────┐ ┌─┐ ┌─┐
│ │ │ ┌───┘ ┌─┘ │ │ ┌─┘ │ ┌─┘ ┌─┘ ┌─┘ │ ┌─┘ ┌─┘ ┌─┘ │ └─┐ └─┐ ┌─┘ │ │ ┌─┘ └─┐
│ ┌─┘ │ │ │ ┌─┘ │ │ │ └─┐ └─┐ │ ┌─┘ │ │ ┌─┘ │ ┌─┘ │ │ │ │ └─┐ ┌─┘
└─┘ └─┘ │ │ │ │ └───┘ └─┘ └───┘ └─┘ │ │ └─┘ │ │ └─┘
└─┘ └─┘ └─┘ │ │
└─┘</pre>
 
For a slow but clear solution see this Haskell Wiki page: [http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Generating_Polyominoes Generating Polyominoes]
 
For a slow but clear solution see this Haskell Wiki page:
http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Generating_Polyominoes
 
<b>Bonus Task</b>: you can create an alternative program (or specialize your first program) to generate very quickly just the number of distinct free polyominoes, and to show a sequence like:
Line 32 ⟶ 39:
1, 1, 1, 2, 5, 12, 35, 108, 369, 1285, 4655, 17073, 63600, 238591, 901971, 3426576, ...
 
Number of free polyominoes (or square animals) with n cells: [[oeis:A000105|OEIS: A000105]]
http://oeis.org/A000105
 
 
Line 39 ⟶ 45:
[[Pentomino_tiling|Pentomino tiling]]
 
=={{header|C sharp|C#}}==
{{trans|D}}
Turns out the source for the counting only version of the D code example could be tweaked to show solutions as well. The max rank can be changed by supplying a command line parameter. The free polyominos of any rank can be displayed by changing the variable named '''target''' to a reasonable number. This program will also indicate the estimated times for larger ranks.
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Linq;
 
namespace cppfpe
{
class Program
{
static int n, ns; // rank, rank squared
static long[] AnyR; // Any Rotation count
static long[] nFlip; // Non-Flipped count
static long[] Frees; // Free Polyominoes count
static int[] fChk, fCkR; // field checks
static int fSiz, fWid; // field size, width
static int[] dirs; // directions
static int[] rotO, rotX, rotY; // rotations
static List<string> polys; // results
static int target; // rank to display
static int clipAt; // max columns for display
 
static int Main(string[] args)
{
polys = new List<string>();
n = 11; if (!(args.Length == 0)) int.TryParse(args[0], out n);
if (n < 1 || n > 24) return 1;
target = 5;
Console.WriteLine("Counting polyominoes to rank {0}...", n);
clipAt = 120;
DateTime start = DateTime.Now;
CountEm();
TimeSpan ti = DateTime.Now - start;
if (polys.Count > 0)
{
Console.WriteLine("Displaying rank {0}:", target);
Console.WriteLine(Assemble(polys));
}
Console.WriteLine("Displaying results:");
Console.WriteLine(" n All Rotations Non-Flipped Free Polys");
for (int i = 1; i <= n; i++)
Console.WriteLine("{0,2} :{1,17}{2,16}{3,16}", i, AnyR[i], nFlip[i], Frees[i]);
Console.WriteLine(string.Format("Elasped: {0,2}d {1,2}h {2,2}m {3:00}s {4:000}ms",
ti.Days, ti.Hours, ti.Minutes, ti.Seconds, ti.Milliseconds).Replace(" 0d ", "")
.Replace(" 0h", "").Replace(" 0m", "").Replace(" 00s", ""));
long ms = (long)ti.TotalMilliseconds, lim = int.MaxValue >> 2;
if (ms > 250)
{
Console.WriteLine("Estimated completion times:");
for (int i = n + 1; i <= n + 10; i++)
{
if (ms >= lim) break; ms += 44; ms <<= 2; ti = TimeSpan.FromMilliseconds(ms);
Console.WriteLine("{0,2} : {1,2}d {2,2}h {3,2}m {4:00}.{5:000}s", i,
ti.Days, ti.Hours, ti.Minutes, ti.Seconds, ti.Milliseconds);
}
}
if (System.Diagnostics.Debugger.IsAttached) Console.ReadKey();
return 0;
}
 
static void CountEm()
{
ns = n * n;
AnyR = new long[n + 1];
nFlip = new long[n + 1];
Frees = new long[n + 1];
fWid = n * 2 - 2;
fSiz = (n - 1) * (n - 1) * 2 + 1;
int[] pnField = new int[fSiz];
int[] pnPutList = new int[fSiz];
fChk = new int[ns];
fCkR = new int[ns];
dirs = new int[] { 1, fWid, -1, -fWid };
rotO = new int[] { 0, n - 1, ns - 1, ns - n, n - 1, 0, ns - n, ns - 1 };
rotX = new int[] { 1, n, -1, -n, -1, n, 1, -n };
rotY = new int[] { n, -1, -n, 1, n, 1, -n, -1 };
Recurse(0, pnField, pnPutList, 0, 1);
}
 
static void Recurse(int lv, int[] field, int[] putlist, int putno, int putlast)
{
CheckIt(field, lv);
if (n == lv) return;
int pos;
for (int i = putno; i < putlast; i++)
{
field[pos = putlist[i]] |= 1;
int k = 0;
foreach (int dir in dirs)
{
int pos2 = pos + dir;
if (0 <= pos2 && pos2 < fSiz && (field[pos2] == 0))
{
field[pos2] = 2;
putlist[putlast + k++] = pos2;
}
}
Recurse(lv + 1, field, putlist, i + 1, putlast + k);
for (int j = 0; j < k; j++) field[putlist[putlast + j]] = 0;
field[pos] = 2;
}
for (int i = putno; i < putlast; i++) field[putlist[i]] &= -2;
}
 
static void CheckIt(int[] field, int lv)
{
AnyR[lv]++;
for (int i = 0; i < ns; i++) fChk[i] = 0;
int x, y;
for (x = n; x < fWid; x++)
for (y = 0; y + x < fSiz; y += fWid)
if ((field[x + y] & 1) == 1) goto bail;
bail:
int x2 = n - x, t;
for (int i = 0; i < fSiz; i++)
if ((field[i] & 1) == 1) fChk[((t = (i + n - 2)) % fWid) + x2 + (t / fWid * n)] = 1;
int of1; for (of1 = 0; of1 < fChk.Length && (fChk[of1] == 0); of1++) ;
bool c = true; int r;
for (r = 1; r < 8 && c; r++)
{
for (x = 0; x < n; x++) for (y = 0; y < n; y++)
fCkR[rotO[r] + rotX[r] * x + rotY[r] * y] = fChk[x + y * n];
int of2; for (of2 = 0; of2 < fCkR.Length && (fCkR[of2] == 0); of2++) ;
of2 -= of1;
for (int i = of1; i < ns - ((of2 > 0) ? of2 : 0); i++)
{
if (fChk[i] > fCkR[i + of2]) break;
if (fChk[i] < fCkR[i + of2]) { c = false; break; }
}
}
if (r > 4) nFlip[lv]++;
if (c)
{
if (lv == target) polys.Add(toStr(field.ToArray()));
Frees[lv]++;
}
}
 
static string toStr(int[] field) // converts field into a minimal string
{
char [] res = new string(' ', n * (fWid + 1) - 1).ToCharArray();
for (int i = fWid; i < res.Length; i += fWid+1) res[i] = '\n';
for (int i = 0, j = n - 2; i < field.Length; i++, j++)
{
if ((field[i] & 1) == 1) res[j] = '#';
if (j % (fWid + 1) == fWid) i--;
}
List<string> t = new string(res).Split('\n').ToList();
int nn = 100, m = 0, v, k = 0; // trim down
foreach (string s in t)
{
if ((v = s.IndexOf('#')) < nn) if (v >= 0) nn = v;
if ((v = s.LastIndexOf('#')) > m) if (v < fWid +1) m = v;
if (v < 0) break; k++;
}
m = m - nn + 1; // convert difference to length
for (int i = t.Count - 1; i >= 0; i--)
{
if (i >= k) t.RemoveAt(i);
else t[i] = t[i].Substring(nn, m);
}
return String.Join("\n", t.ToArray());
}
 
// assembles string representation of polyominoes into larger horizontal band
static string Assemble(List<string> p)
{
List<string> lines = new List<string>();
for (int i = 0; i < target; i++) lines.Add(string.Empty);
foreach (string poly in p)
{
List<string> t = poly.Split('\n').ToList();
if (t.Count < t[0].Length) t = flipXY(t);
for (int i = 0; i < lines.Count; i++)
lines[i] += (i < t.Count) ? ' ' + t[i] + ' ': new string(' ', t[0].Length + 2);
}
for (int i = lines.Count - 1; i > 0; i--)
if (lines[i].IndexOf('#') < 0) lines.RemoveAt(i);
if (lines[0].Length >= clipAt / 2-2) Wrap(lines, clipAt / 2-2);
lines = Cornered(string.Join("\n", lines.ToArray())).Split('\n').ToList();
return String.Join("\n", lines.ToArray());
}
 
static List<string> flipXY(List<string> p) // flips a small string
{
List<string> res = new List<string>();
for (int i = 0; i < p[0].Length; i++) res.Add(string.Empty);
for (int i = 0; i < res.Count; i++)
for(int j = 0; j < p.Count; j++) res[i] += p[j][i];
return res;
}
 
static string DW(string s) // double widths a string
{
string t = string.Empty;
foreach (char c in s) t += string.Format("{0}{0}",c);
return t;
}
 
static void Wrap(List<string> s, int w) // wraps a wide List<string>
{
int last = 0;
while (s.Last().Length >= w)
{
int x = w, lim = s.Count; bool ok;
do
{
ok = true;
for (int i = last; i < lim; i++)
if (s[i][x] != ' ')
{ ok = false; x--; break; }
} while (!ok);
for (int i = last; i < lim; i++)
if (s[i].Length > x) { s.Add(s[i].Substring(x)); s[i] = s[i].Substring(0, x + 1); }
last = lim;
}
last = 0;
for (int i = s.Count - 1; i > 0; i--)
if ((last = (s[i].IndexOf('#') < 0) ? last + 1 : 0) > 1) s.RemoveAt(i + 1);
}
 
static string Cornered(string s) // converts plain ascii art into cornered version
{
string[] lines = s.Split('\n');
string res = string.Empty;
string line = DW(new string(' ', lines[0].Length)), last;
for (int i = 0; i < lines.Length; i++)
{
last = line; line = DW(lines[i]);
res += Puzzle(last, line) + '\n';
}
res += Puzzle(line, DW(new string(' ', lines.Last().Length))) + '\n';
return res;
}
 
static string Puzzle(string a, string b) // tests each intersection to determine correct corner symbol
{
string res = string.Empty;
if (a.Length > b.Length) b += new string(' ', a.Length - b.Length);
if (a.Length < b.Length) a += new string(' ', b.Length - a.Length);
for (int i = 0; i < a.Length - 1; i++)
res += " 12└4┘─┴8│┌├┐┤┬┼"[(a[i] == a[i + 1] ? 0 : 1) +
(b[i + 1] == a[i + 1] ? 0 : 2) +
(a[i] == b[i] ? 0 : 4) +
(b[i] == b[i + 1] ? 0 : 8)];
return res;
}
}
}
</syntaxhighlight>
{{out}}
<pre>Counting polyominoes to rank 11...
Displaying rank 5:
┌───┐ ┌─────┐ ┌─┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌─┐ ┌─────┐ ┌─┐ ┌─┐
│ │ │ ┌───┘ ┌─┘ │ │ ┌─┘ │ ┌─┘ ┌─┘ ┌─┘ │ ┌─┘ ┌─┘ ┌─┘ │ └─┐ └─┐ ┌─┘ │ │ ┌─┘ └─┐
│ ┌─┘ │ │ │ ┌─┘ │ │ │ └─┐ └─┐ │ ┌─┘ │ │ ┌─┘ │ ┌─┘ │ │ │ │ └─┐ ┌─┘
└─┘ └─┘ │ │ │ │ └───┘ └─┘ └───┘ └─┘ │ │ └─┘ │ │ └─┘
└─┘ └─┘ └─┘ │ │
└─┘
 
Displaying results:
n All Rotations Non-Flipped Free Polys
1 : 1 1 1
2 : 2 1 1
3 : 6 2 2
4 : 19 7 5
5 : 63 18 12
6 : 216 60 35
7 : 760 196 108
8 : 2725 704 369
9 : 9910 2500 1285
10 : 36446 9189 4655
11 : 135268 33896 17073
Elasped: 562ms
Estimated completion times:
12 : 0d 0h 0m 02.424s
13 : 0d 0h 0m 09.872s
14 : 0d 0h 0m 39.664s
15 : 0d 0h 2m 38.832s
16 : 0d 0h 10m 35.504s
17 : 0d 0h 42m 22.192s
18 : 0d 2h 49m 28.944s
19 : 0d 11h 17m 55.952s
20 : 1d 21h 11m 43.984s
21 : 7d 12h 46m 56.112s</pre>
 
=={{header|D}}==
{{trans|Haskell}}
<langsyntaxhighlight lang="d">import std.stdio, std.range, std.algorithm, std.typecons, std.conv;
 
alias Coord = byte;
Line 123 ⟶ 415:
foreach (const poly; n.rank)
writefln("%-(%s\n%)\n", poly.textRepresentation);
}</langsyntaxhighlight>
{{out}}
<pre>[1, 1, 2, 5, 12, 35, 108, 369, 1285, 4655]
Line 184 ⟶ 476:
Translated and modified from C code: http://www.geocities.jp/tok12345/countomino.txt
 
<langsyntaxhighlight lang="d">import core.stdc.stdio: printf;
import core.stdc.stdlib: atoi;
 
Line 352 ⟶ 644:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>1
Line 384 ⟶ 676:
=={{header|Elixir}}==
{{trans|Ruby}}
<langsyntaxhighlight lang="elixir">defmodule Polyominoes do
defp translate2origin(poly) do
# Finds the min x and y coordiate of a Polyomino.
Line 458 ⟶ 750:
IO.puts "\nAll free polyominoes of rank #{n}:"
Enum.sort(Polyominoes.rank(n))
|> Enum.each(fn poly -> IO.puts "#{Polyominoes.text_representation(poly)}\n" end)</langsyntaxhighlight>
 
{{out}}
Line 505 ⟶ 797:
###
#
</pre>
 
=={{header|Go}}==
{{trans|Kotlin}}
<syntaxhighlight lang="go">package main
 
import (
"fmt"
"sort"
)
 
type point struct{ x, y int }
type polyomino []point
type pointset map[point]bool
 
func (p point) rotate90() point { return point{p.y, -p.x} }
func (p point) rotate180() point { return point{-p.x, -p.y} }
func (p point) rotate270() point { return point{-p.y, p.x} }
func (p point) reflect() point { return point{-p.x, p.y} }
 
func (p point) String() string { return fmt.Sprintf("(%d, %d)", p.x, p.y) }
 
// All four points in Von Neumann neighborhood
func (p point) contiguous() polyomino {
return polyomino{point{p.x - 1, p.y}, point{p.x + 1, p.y},
point{p.x, p.y - 1}, point{p.x, p.y + 1}}
}
 
// Finds the min x and y coordinates of a Polyomino.
func (po polyomino) minima() (int, int) {
minx := po[0].x
miny := po[0].y
for i := 1; i < len(po); i++ {
if po[i].x < minx {
minx = po[i].x
}
if po[i].y < miny {
miny = po[i].y
}
}
return minx, miny
}
 
func (po polyomino) translateToOrigin() polyomino {
minx, miny := po.minima()
res := make(polyomino, len(po))
for i, p := range po {
res[i] = point{p.x - minx, p.y - miny}
}
sort.Slice(res, func(i, j int) bool {
return res[i].x < res[j].x || (res[i].x == res[j].x && res[i].y < res[j].y)
})
return res
}
 
// All the plane symmetries of a rectangular region.
func (po polyomino) rotationsAndReflections() []polyomino {
rr := make([]polyomino, 8)
for i := 0; i < 8; i++ {
rr[i] = make(polyomino, len(po))
}
copy(rr[0], po)
for j := 0; j < len(po); j++ {
rr[1][j] = po[j].rotate90()
rr[2][j] = po[j].rotate180()
rr[3][j] = po[j].rotate270()
rr[4][j] = po[j].reflect()
rr[5][j] = po[j].rotate90().reflect()
rr[6][j] = po[j].rotate180().reflect()
rr[7][j] = po[j].rotate270().reflect()
}
return rr
}
 
func (po polyomino) canonical() polyomino {
rr := po.rotationsAndReflections()
minr := rr[0].translateToOrigin()
mins := minr.String()
for i := 1; i < 8; i++ {
r := rr[i].translateToOrigin()
s := r.String()
if s < mins {
minr = r
mins = s
}
}
return minr
}
 
func (po polyomino) String() string {
return fmt.Sprintf("%v", []point(po))
}
 
func (po polyomino) toPointset() pointset {
pset := make(pointset, len(po))
for _, p := range po {
pset[p] = true
}
return pset
}
 
// Finds all distinct points that can be added to a Polyomino.
func (po polyomino) newPoints() polyomino {
pset := po.toPointset()
m := make(pointset)
for _, p := range po {
pts := p.contiguous()
for _, pt := range pts {
if !pset[pt] {
m[pt] = true // using an intermediate set is about 15% faster!
}
}
}
poly := make(polyomino, 0, len(m))
for k := range m {
poly = append(poly, k)
}
return poly
}
 
func (po polyomino) newPolys() []polyomino {
pts := po.newPoints()
res := make([]polyomino, len(pts))
for i, pt := range pts {
poly := make(polyomino, len(po))
copy(poly, po)
poly = append(poly, pt)
res[i] = poly.canonical()
}
return res
}
 
var monomino = polyomino{point{0, 0}}
var monominoes = []polyomino{monomino}
 
// Generates polyominoes of rank n recursively.
func rank(n int) []polyomino {
switch {
case n < 0:
panic("n cannot be negative. Program terminated.")
case n == 0:
return []polyomino{}
case n == 1:
return monominoes
default:
r := rank(n - 1)
m := make(map[string]bool)
var polys []polyomino
for _, po := range r {
for _, po2 := range po.newPolys() {
if s := po2.String(); !m[s] {
polys = append(polys, po2)
m[s] = true
}
}
}
sort.Slice(polys, func(i, j int) bool {
return polys[i].String() < polys[j].String()
})
return polys
}
}
 
func main() {
const n = 5
fmt.Printf("All free polyominoes of rank %d:\n\n", n)
for _, poly := range rank(n) {
for _, pt := range poly {
fmt.Printf("%s ", pt)
}
fmt.Println()
}
const k = 10
fmt.Printf("\nNumber of free polyominoes of ranks 1 to %d:\n", k)
for i := 1; i <= k; i++ {
fmt.Printf("%d ", len(rank(i)))
}
fmt.Println()
}</syntaxhighlight>
 
{{out}}
<pre>
All free polyominoes of rank 5:
 
(0, 0) (0, 1) (0, 2) (0, 3) (0, 4)
(0, 0) (0, 1) (0, 2) (0, 3) (1, 0)
(0, 0) (0, 1) (0, 2) (0, 3) (1, 1)
(0, 0) (0, 1) (0, 2) (1, 0) (1, 1)
(0, 0) (0, 1) (0, 2) (1, 0) (1, 2)
(0, 0) (0, 1) (0, 2) (1, 0) (2, 0)
(0, 0) (0, 1) (0, 2) (1, 1) (2, 1)
(0, 0) (0, 1) (0, 2) (1, 2) (1, 3)
(0, 0) (0, 1) (1, 1) (1, 2) (2, 1)
(0, 0) (0, 1) (1, 1) (1, 2) (2, 2)
(0, 0) (0, 1) (1, 1) (2, 1) (2, 2)
(0, 1) (1, 0) (1, 1) (1, 2) (2, 1)
 
Number of free polyominoes of ranks 1 to 10:
1 1 2 5 12 35 108 369 1285 4655
</pre>
 
Line 511 ⟶ 1,002:
 
Code updated and slightly improved from: http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Generating_Polyominoes
<langsyntaxhighlight lang="haskell">import DataSystem.ListEnvironment (sortgetArgs)
import Control.Arrow ((***), first)
import Data.Set (toList, fromList)
import SystemData.EnvironmentList (getArgssort)
import Data.Bool (bool)
 
type Coord = Int
 
type Point = (Coord, Coord)
 
type Polyomino = [Point]
 
Line 525 ⟶ 1,020:
translateToOrigin :: Polyomino -> Polyomino
translateToOrigin p =
let (minx, miny) = minima p in
in map (\(x, y) -> (x -subtract minx, y*** -subtract miny)) <$> p
 
rotate90, rotate180, rotate270, reflect :: Point -> Point
rotate90 = uncurry (flip (x, y) = ( y,. -xnegate)
 
rotate180 (x, y) = (-x, -y)
rotate180 = negate *** negate
rotate270 (x, y) = (-y, x)
 
reflect (x, y) = (-x, y)
rotate270 = uncurry (flip ((,) . negate))
 
reflect = first negate
 
-- All the plane symmetries of a rectangular region.
rotationsAndReflections :: Polyomino -> [Polyomino]
rotationsAndReflections p =
[p,(<*>)
(fmap <$>
map rotate90 p,
map[ rotate180 p,id
map, rotate270 p,rotate90
map, reflect p,rotate180
, rotate270
map (rotate90 . reflect) p,
map (rotate180 ., reflect) p,
map, (rotate270rotate90 . reflect) p]
, rotate180 . reflect
, rotate270 . reflect
]) .
return
 
canonical :: Polyomino -> Polyomino
canonical = minimum . map (sort . translateToOrigin) . rotationsAndReflections
 
unique
unique :: (Ord a) => [a] -> [a]
:: (Ord a)
=> [a] -> [a]
unique = toList . fromList
 
Line 559 ⟶ 1,063:
newPoints :: Polyomino -> [Point]
newPoints p =
let notInP = filter (not . flip elem p) in
in unique . notInP . concatMap contiguous $ p
 
newPolys :: Polyomino -> [Polyomino]
Line 566 ⟶ 1,070:
 
monomino = [(0, 0)]
 
monominoes = [monomino]
 
Line 575 ⟶ 1,080:
 
-- Generates a textual representation of a Polyomino.
textRepresentatontextRepresentation :: Polyomino -> String
textRepresentation p =
textRepresentaton p =
unlines
unlines [[if elem (x,y) p then '#' else ' ' | x <- [0 .. maxx - minx]]
[ [ bool ' ' '#' |((x, y) <- [0 .. maxy -`elem` miny]]p)
| x <- [0 .. maxx - minx] ]
where
| y <- [0 maxima.. :: Polyominomaxy -> Pointminy] ]
where
maxima (p:ps) = foldr (\(x, y) (mx, my) -> (max x mx, max y my)) p ps
maxima :: Polyomino -> Point
(minx, miny) = minima p
maxima (p:ps) = foldr (maxx\(x, maxyy) =(mx, maximamy) -> (max x mx, max y my)) p ps
(minx, miny) = minima p
(maxx, maxy) = maxima p
 
main :: IO ()
main = do
print $ map (length . rank) [1 .. 10]
args <- getArgs
let n = if null args then 5 elsebool (read $ head args :: Int) 5 (null args)
putStrLn ("\nAll free polyominoes of rank " ++ show n ++ ":")
mapM_ (putStrLn $ map textRepresentaton. $textRepresentation) (rank n)</langsyntaxhighlight>
{{out}}
<pre>[1,1,2,5,12,35,108,369,1285,4655]
Line 652 ⟶ 1,160:
Generating polyominoes as ascii art:
 
<langsyntaxhighlight Jlang="j">polyominoes=:verb define
if. 1>y do. i.0 0 0 return.end.
if. 1=y do. 1 1 1$'#' return.end.
Line 690 ⟶ 1,198:
trim=:verb define&|:^:2
y#~+./"1 y~:' '
)</langsyntaxhighlight>
 
Example use (boxing each pentomino for display purposes):
 
<langsyntaxhighlight lang="j"> <"2 polyominoes 5
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│#####│## │# │### │## │## │### │ ## │ # │ # │ # │ ## │
Line 700 ⟶ 1,208:
│ │# │# │# │# │## │ │## │## │### │ # │# │
│ │# │# │ │ │ │ │ │ │ │ │ │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘</langsyntaxhighlight>
 
=={{header|Java}}==
Translation of [[Free_polyominoes_enumeration#Haskell|Haskell]] via [[Free_polyominoes_enumeration#D|D]]
{{works with|Java|8}}
<langsyntaxhighlight lang="java">import java.awt.Point;
import java.util.*;
import static java.util.Arrays.asList;
Line 808 ⟶ 1,316:
}
}
}</langsyntaxhighlight>
 
<pre>(0,0) (0,1) (1,1) (1,2) (2,1)
Line 822 ⟶ 1,330:
(0,0) (0,1) (0,2) (1,0) (2,0)
(0,0) (0,1) (0,2) (0,3) (0,4)</pre>
 
=={{header|JavaScript}}==
<syntaxhighlight lang="javascript">const width = window.innerWidth;
const height = window.innerHeight;
const p = Math.floor(width/140);
const verticalScrollbarWidth = 15;
const elementSize = 1;
 
let maxHeight;
let cellSize, xSpacing, ySpacing, xOffset, yOffset;
let test_poly, starting_poly;
let stored_polys;
let maxPolyLength;
let jsonData;
let polysFound;
let typeSelected, orderSelected, modeSelected, orderValue;
 
let canvas = document.createElement('canvas');
canvas.id = "myCanvas";
canvas.width = width;
canvas.height = height;
let parentDiv = document.getElementById("div_polys");
parentDiv.appendChild(canvas);
canvas.style.backgroundColor = "lightblue";
let ctx = canvas.getContext("2d"); // Get the 2D rendering context
 
let buttonBack = document.createElement("button");
buttonBack.innerHTML = "<b>Back</b>";
buttonBack.id = "back_button_id";
buttonBack.classList.add("back_button_class");
buttonBack.style.fontSize = (7*p).toString() + "px";
buttonBack.style.position = "absolute";
buttonBack.style.top = (3*p).toString() + "px";
buttonBack.style.right = (5*p).toString() + "px";
buttonBack.style.display = "none";
buttonBack.addEventListener("click", function() {
canvas.height = height;
document.getElementById("div_polys").style.display = "none";
document.getElementById("div_menu").style.display = "block";
window.scrollTo(0,0);
stored_polys = null;
jsonData = null;
});
document.getElementById("div_polys").style.display = "block";
parentDiv.appendChild(buttonBack);
 
let buttonBack2 = buttonBack.cloneNode(true);
buttonBack2.addEventListener("click", function() {
canvas.height = height;
document.getElementById("div_polys").style.display = "none";
document.getElementById("div_menu").style.display = "block";
window.scrollTo(0,0);
stored_polys = null;
jsonData = null;
});
parentDiv.appendChild(buttonBack2);
 
//hide the info bubble when the user taps outside it on Safari browser
document.body.addEventListener("click", function(event) {
const popUps = document.querySelectorAll(".pop-up");
popUps.forEach(popUp => {
if (popUp.style.display === "block") {
popUp.style.display = "none";
}
});
});
 
function iOS() {
return [
'iPad Simulator',
'iPhone Simulator',
'iPod Simulator',
'iPad',
'iPhone',
'iPod'
].includes(navigator.platform)
// iPad on iOS 13 detection
|| (navigator.userAgent.includes("Mac") && "ontouchend" in document)
}
 
function showPolyDiv() {
document.getElementById("div_menu").style.display = "none";
document.getElementById("div_polys").style.display = "block";
window.scrollTo(0,0);
buttonBack.style.display = "none";
buttonBack2.style.display = "none";
ctx.clearRect(0, 0, canvas.width, canvas.height);
typeSelected = document.querySelector('input[name="type"]:checked').value;
orderSelected = document.querySelector('input[name="order"]:checked').value;
orderValue = parseInt(orderSelected);
modeSelected = document.querySelector('input[name="mode"]:checked').value;
 
if (iOS()) {
maxHeight = 16383;
} else {
maxHeight = 65535;
}
 
fetchPolys();
}
 
function fetchPolys() {
if (orderValue === 1) modeSelected = "1"; // So that it doesn't create the order-one polyomino because it cannot start from the previous order.
if (modeSelected === "2") {
orderSelected--;
}
cellSize = (14/(orderValue*0.35))*p; // size of each cell of a polyomino when displayed on screen
xSpacing = cellSize; ySpacing = cellSize; // horizontal and vertical spacing between polyominoes when they are displayed on screen
xOffset = xSpacing; yOffset = 20*p; // spaces between the polys displayed
canvas.width = width;
canvas.height = maxHeight; // max height
maxPolyLength = 0;
stored_polys = new Set(); // because it is set to null after returning to the menu screen
 
fetch(typeSelected + orderSelected + ".json")
.then(response => response.json())
.then(json => {
jsonData = json;
if (modeSelected === "1") displayPolys();
else if (modeSelected === "2") createPolys();
else console.log("no mode selected");
})
.catch(error => console.log(error));
}
 
function createJson(order, type, multitude, polys) {
let content =
{
order: order,
type: type,
multitude: multitude,
polys: polys
};
 
// ********** Save a JSON file with the FileSaver library (large files, more options) ************
let jsonString = JSON.stringify(content);
let blob = new Blob([jsonString], { type: "application/json;charset=utf-8" });
saveAs(blob, type + order.toString()+".json");
}
 
function createPolys() {
polysFound = 0;
for (let i = 0; i < jsonData.polys.length; i++) {
starting_poly = jsonData.polys[i];
nextOrderPolys(starting_poly);
}
if (yOffset + 3*ySpacing > maxHeight) { // max height
//canvas.height = maxHeight;
} else {
let imageData = ctx.getImageData(0, 0, canvas.width, yOffset + maxPolyLength*cellSize + ySpacing);
canvas.height = yOffset + maxPolyLength*cellSize + ySpacing;
ctx.putImageData(imageData, 0, 0);
}
ctx.fillStyle = "black";
ctx.font = (5*p).toString() + "px Verdana";
ctx.fillText(jsonData.type + " polyominoes of order " + orderValue + ": ", 6*p, 10*p);
ctx.fillText(polysFound, 6*p, 17*p);
console.log(jsonData.type + " polyominoes of order " + orderValue + " found: " + polysFound + ". Max canvas height: " + maxHeight);
let stored_polys_array = new Uint8Array(elementSize);
stored_polys_array = parseArray(stored_polys);
buttonBack2.style.top = (canvas.height - 15*p).toString() + "px";
buttonBack.style.display = "block";
if (canvas.height > height) {
buttonBack2.style.display = "block";
}
createJson(jsonData.order + 1, jsonData.type, polysFound, stored_polys_array);
}
 
function displayPolys() {
for (let i = 0; i < jsonData.polys.length; i++) {
starting_poly = jsonData.polys[i];
showPoly(starting_poly);
}
if (yOffset + 3*ySpacing > maxHeight) { // max height
//canvas.height = maxHeight;
} else {
let imageData = ctx.getImageData(0, 0, canvas.width, yOffset + maxPolyLength*cellSize + ySpacing);
canvas.height = yOffset + maxPolyLength*cellSize + ySpacing;
ctx.putImageData(imageData, 0, 0);
}
ctx.fillStyle = "black";
ctx.font = (5*p).toString() + "px Verdana";
ctx.fillText(jsonData.type + " polyominoes of order " + jsonData.order + ": ", 6*p, 10*p);
ctx.fillText(jsonData.polys.length, 6*p, 17*p);
console.log(jsonData.type + " polyominoes of order " + jsonData.order + ": " + jsonData.polys.length + ". Max canvas height: " + maxHeight);
buttonBack2.style.top = (canvas.height - 15*p).toString() + "px";
buttonBack.style.display = "block";
if (canvas.height > height) {
buttonBack2.style.display = "block";
}
}
 
function parseArray(stored) {
// gets a Set object of strings and returns an Array object of arrays
let arrayOfArrays = new Uint8Array(elementSize);
arrayOfArrays = [];
let arrayOfStrings = Array.from(stored);
for (let i = 0; i < arrayOfStrings.length; i++) {
arrayOfArrays.push(JSON.parse(arrayOfStrings[i]));
}
return arrayOfArrays;
}
 
function nextOrderPolys(poly) {
let poly1, poly2 = new Uint8Array(elementSize);
poly1 = addBlanksAroundPoly(poly);
 
for (let y = 0; y < poly1.length; y++) {
for (let x = 0; x < poly1[y].length; x++) {
if (poly1[y][x] === 0) {
try {
if (poly1[y+1][x] === 1) {
checkPoly(poly1, y, x);
}
} catch (error) { }
try {
if (poly1[y][x-1] === 1) {
checkPoly(poly1, y, x);
}
} catch (error) { }
try {
if (poly1[y-1][x] === 1) {
checkPoly(poly1, y, x);
}
} catch (error) { }
try {
if (poly1[y][x+1] === 1) {
checkPoly(poly1, y, x);
}
} catch (error) { }
}
}
}
 
}
 
function checkPoly(poly, i, j) {
let poly2, trunc_poly, rot_poly = new Uint8Array(elementSize);
let r;
poly2 = poly.map(subArray => subArray.slice()); //copies 2D array poly 1 to poly2
poly2[i][j] = 1; //2D array poly1 is not affected by this operation
trunc_poly = truncatePoly(poly2);
 
if (jsonData.type === "fixed") {
if (stored_polys.has(JSON.stringify(trunc_poly))) { // there is an identical poly in the Set
return;
}
} else if (jsonData.type === "one-sided") {
if (stored_polys.has(JSON.stringify(trunc_poly))) { // there is an identical poly in the Set
return;
}
rot_poly = trunc_poly;
for (r = 0; r < 3; r++) { // rotate the candidate poly 3 times and check if there is an identical poly in the Set
rot_poly = rotateLeftPoly(rot_poly);
if (stored_polys.has(JSON.stringify(rot_poly))) { // there is an identical poly in the Set
return;
}
}
} else if (jsonData.type === "free") {
if (stored_polys.has(JSON.stringify(trunc_poly))) { // there is an identical poly in the Set
return;
}
rot_poly = trunc_poly;
for (r = 0; r < 3; r++) { // rotate the candidate poly 3 times and check if there is an identical poly in the Set
rot_poly = rotateLeftPoly(rot_poly);
if (stored_polys.has(JSON.stringify(rot_poly))) { // there is an identical poly in the Set
return;
}
}
rot_poly = mirrorXPoly(rot_poly); // mirror candidate poly and check again
if (stored_polys.has(JSON.stringify(rot_poly))) { // there is an identical poly in the Set
return;
}
for (r = 0; r < 3; r++) { // rotate the candidate poly 3 times and check if there is an identical poly in the Set
rot_poly = rotateLeftPoly(rot_poly);
if (stored_polys.has(JSON.stringify(rot_poly))) { // there is an identical poly in the Set
return;
}
}
}
 
stored_polys.add(JSON.stringify(trunc_poly)); // The candidate poly is new. Store it in the Set
polysFound++;
showPoly(trunc_poly);
}
 
function showPoly(poly) {
ctx.lineWidth = 0.5*p;
 
//Check if the rightmost end of the new poly will be displayed outside the screen width and if yes, display the new poly in the next row
if (xOffset + poly[0].length*cellSize + verticalScrollbarWidth + ySpacing > width) {
xOffset = xSpacing;
yOffset += maxPolyLength*cellSize + ySpacing;
maxPolyLength = 0;
}
 
//display the new poly
let randomColor = "rgb("+(Math.random()*215+40)+","+(Math.random()*215+40)+","+(Math.random()*215+40)+")";
for (let y = 0; y < poly.length; y++) {
for (let x = 0; x < poly[y].length; x++) {
ctx.beginPath();
if (poly[y][x] === 1) {
ctx.fillStyle = randomColor;
ctx.strokeStyle = "black";
} else {
//ctx.fillStyle = "white";
ctx.fillStyle = "transparent";
ctx.strokeStyle = "transparent";
}
ctx.rect(xOffset + x*cellSize, yOffset + y*cellSize, cellSize, cellSize);
ctx.fill();
ctx.stroke();
}
}
 
xOffset += poly[0].length*cellSize + xSpacing; // set the left margin of the new poly to be displayed
//sets the next row for the new poly to be displayed as the maximum height from the previous row
if (poly.length > maxPolyLength) {
maxPolyLength = poly.length;
}
}
 
function truncatePoly(poly) {
let x, y;
let new_poly, transposedArray = new Uint8Array(elementSize);
//truncate rows
new_poly = [];
for (y = 0; y < poly.length; y++) {
for (x = 0; x < poly[y].length; x++) {
if (poly[y][x] === 1) {
new_poly.push(poly[y]); //copy this row to a new array
break;
}
}
}
//reverse rows and columns of the trancated array
transposedArray = new_poly[0].map((col, i) => new_poly.map(row => row[i]));
//truncate rows of the new array, so that we have trancated both rows and columns
new_poly = [];
for (y = 0; y < transposedArray.length; y++) {
for (x = 0; x < transposedArray[y].length; x++) {
if (transposedArray[y][x] === 1) {
new_poly.push(transposedArray[y]); //copy this row to a new array
break;
}
}
}
//reverse rows and columns of the trancated array again, so that the new array has the same orientation with the original
transposedArray = new_poly[0].map((col, i) => new_poly.map(row => row[i]));
return transposedArray;
}
 
function rotateLeftPoly(poly) {
let transposedArray = new Uint8Array(elementSize);
//reverse rows and columns of the original array
transposedArray = poly[0].map((col, i) => poly.map(row => row[i]));
//mirrors the transposed array
return transposedArray.slice().reverse();
}
 
function mirrorXPoly(poly) {
let mirr_poly = new Uint8Array(elementSize);
mirr_poly = poly.slice().reverse();
return mirr_poly;
}
 
function mirrorYPoly(poly) {
let mirr_poly = new Uint8Array(elementSize);
mirr_poly = poly.map(subArr => subArr.slice().reverse());
return mirr_poly;
}
 
function addBlanksAroundPoly(poly) {
//creates a loop of blank cells around a poly, so that new filled cells can be placed in the next poly order
let newLengthX = poly[0].length + 2;
let newLengthY = poly.length + 2;
let new_poly = new Uint8Array(elementSize);
new_poly = Array.from({length: newLengthY}, () => Array(newLengthX).fill(0)); //creates a 2D array filled with zeros
for (let y = 0; y < poly.length; y++) {
for (let x = 0; x < poly[y].length; x++) {
new_poly[y+1][x+1] = poly[y][x];
}
}
return new_poly;
}</syntaxhighlight>
 
{{out}}
*[https://grifoi.org/polyominoes/index.html A JavaScript polyomino maker application]
 
=={{header|Julia}}==
{{trans|Haskell}}
<syntaxhighlight lang="julia">import Base.show, Base.==, Base.hash
 
struct Point x::Float64; y::Float64 end
hash(p::Point) = hash(p.x, hash(p.y))
==(p1::Point, p2::Point) = p1.x == p2.x && p1.y == p2.y
 
pointsort!(pv) = sort!(pv, lt = (a, b) -> a.x == b.x ? a.y < b.y : a.x < b.x)
 
mutable struct Poly
vp::Vector{Point}
Poly(v::Vector{Point}) = new(pointsort!(unique(v)))
end
Poly(poly::Poly) = Poly(poly.vp)
Poly(poly::Poly, v::Vector{Point}) = Poly(vcat(poly.vp, v))
Poly(poly, f::Function) = Poly(pointsort!(map(p -> f(p), deepcopy(poly.vp))))
==(p1::Poly, p2::Poly) = length(p1.vp) == length(p2.vp) &&
all(i -> p1.vp[i] == p2.vp[i], 1:length(p1.vp))
hash(p1::Poly) = reduce((x, y) -> hash(hash(x), hash(y)), p1.vp)
 
polysort!(polyarr) = sort!(polyarr, lt = (a, b) -> string(a.vp) < string(b.vp))
 
translate_to_origin(poly) = Poly(poly, p -> Point(p.x - minimum(p -> p.x, poly.vp),
p.y - minimum(p -> p.y, poly.vp)))
 
function asciimatrix(poly)
if length(poly.vp) == 0
return reshape(Char[], 0, 0)
elseif length(poly.vp) == 1
return reshape([' '], 1, 1)
end
vp = translate_to_origin(poly).vp
sz = Int.((maximum(p -> p.x, vp), maximum(p -> p.y, vp))) .+ 1
txtmat = fill(' ', sz)
for i in 1:sz[1], j in 1:sz[2]
if Point(i-1, j-1) in vp
txtmat[i, j] = '#'
end
end
txtmat
end
 
rotate90(poly) = Poly(poly, p -> Point(p.y, -p.x))
rotate180(poly) = Poly(poly, p -> Point(-p.x, -p.y))
rotate270(poly) = Poly(poly, p -> Point(-p.y, p.x))
reflect(poly) = Poly(poly, p -> Point(-p.x, p.y))
 
rotations_and_reflections(poly) = [poly, rotate90(poly), rotate180(poly),
rotate270(poly), reflect(poly), reflect(rotate90(poly)),
reflect(rotate180(poly)), reflect(rotate270(poly))]
 
canonical(poly) = polysort!(map(translate_to_origin, rotations_and_reflections(poly)))
 
contiguous(p) = [Point(p.x - 1, p.y), Point(p.x + 1, p.y),
Point(p.x, p.y - 1), Point(p.x, p.y + 1)]
 
adjacentpoints(poly) = unique(filter(p -> !(p in poly.vp),
reduce(vcat, [contiguous(p) for p in poly.vp])))
 
nextrank_adjacentpolys(poly) = map(pv -> pv[1], unique(canonical.(
[Poly(poly, [p]) for p in adjacentpoints(poly)])))
 
const nullmino = Poly[]
const monomino = Poly([Point(0, 0)])
 
rank(n) = @assert n >= 0 && return n == 0 ? nullmino : n == 1 ? [monomino] :
unique(reduce(vcat, map(nextrank_adjacentpolys, rank(n - 1))))
 
function Base.show(io::IO, poly::Poly)
txtmat = asciimatrix(poly)
w, h = size(txtmat)
for i in 1:w
for j in 1:h
print(txtmat[i, j])
end
println()
end
end
 
function testpolys(N = 5)
println([length(rank(n)) for n in 1:10])
 
println("\nAll free polyominoes of rank $N:")
 
for poly in rank(5)
println(poly)
end
end
 
testpolys()
</syntaxhighlight>{{out}}
<pre>
[1, 1, 2, 5, 12, 35, 108, 369, 1285, 4655]
 
All free polyominoes of rank 5:
##
##
#
 
###
##
 
####
#
 
#
###
#
 
###
#
#
 
##
##
#
 
###
##
 
##
#
##
 
###
# #
 
####
#
 
###
#
#
 
#####
</pre>
 
=={{header|Kotlin}}==
{{trans|Python}}
<syntaxhighlight lang="scala">// version 1.1.51
 
class Point(val x: Int, val y: Int) : Comparable<Point> {
fun rotate90() = Point( this.y, -this.x)
fun rotate180() = Point(-this.x, -this.y)
fun rotate270() = Point(-this.y, this.x)
fun reflect() = Point(-this.x, this.y)
 
override fun equals(other: Any?): Boolean {
if (other == null || other !is Point) return false
return this.x == other.x && this.y == other.y
}
 
override fun compareTo(other: Point) =
if (this == other ) 0
else if (this.x < other.x || (this.x == other.x && this.y < other.y)) -1
else 1
 
override fun toString() = "($x, $y)"
}
 
typealias Polyomino = List<Point>
 
// Finds the min x and y coordinates of a Polyomino.
val Polyomino.minima get() = Pair(this.minBy { it.x }!!.x, this.minBy { it.y }!!.y)
 
fun Polyomino.translateToOrigin(): Polyomino {
val (minX, minY) = this.minima
return this.map { Point(it.x - minX, it.y - minY) }.sorted()
}
 
// All the plane symmetries of a rectangular region.
val Polyomino.rotationsAndReflections get() =
listOf(
this,
this.map { it.rotate90() },
this.map { it.rotate180() },
this.map { it.rotate270() },
this.map { it.reflect() },
this.map { it.rotate90().reflect() },
this.map { it.rotate180().reflect() },
this.map { it.rotate270().reflect() }
)
 
val Polyomino.canonical get() =
this.rotationsAndReflections.map { it.translateToOrigin() }.minBy { it.toString() }!!
 
// All four points in Von Neumann neighborhood
val Point.contiguous get() =
listOf(Point(x - 1, y), Point(x + 1, y), Point(x, y - 1), Point(x, y + 1))
 
// Finds all distinct points that can be added to a Polyomino.
val Polyomino.newPoints get() = this.flatMap { it.contiguous }.filter { it !in this }.distinct()
 
val Polyomino.newPolys get() = this.newPoints.map { (this + it).canonical }
 
val monomino = listOf(Point(0, 0))
val monominoes = listOf(monomino)
 
// Generates polyominoes of rank n recursively.
fun rank(n: Int): List<Polyomino> = when {
n < 0 -> throw IllegalArgumentException("n cannot be negative")
n == 0 -> emptyList<Polyomino>()
n == 1 -> monominoes
else -> rank(n - 1).flatMap { it.newPolys }
.distinctBy { it.toString() }
.sortedBy { it.toString() }
}
 
fun main(args: Array<String>) {
val n = 5
println("All free polyominoes of rank $n:\n")
for (poly in rank(n)) {
for (pt in poly) print("$pt ")
println()
}
val k = 10
println("\nNumber of free polyominoes of ranks 1 to $k:")
for (i in 1..k) print("${rank(i).size} ")
println()
}</syntaxhighlight>
 
{{out}}
<pre>
All free polyominoes of rank 5:
 
(0, 0) (0, 1) (0, 2) (0, 3) (0, 4)
(0, 0) (0, 1) (0, 2) (0, 3) (1, 0)
(0, 0) (0, 1) (0, 2) (0, 3) (1, 1)
(0, 0) (0, 1) (0, 2) (1, 0) (1, 1)
(0, 0) (0, 1) (0, 2) (1, 0) (1, 2)
(0, 0) (0, 1) (0, 2) (1, 0) (2, 0)
(0, 0) (0, 1) (0, 2) (1, 1) (2, 1)
(0, 0) (0, 1) (0, 2) (1, 2) (1, 3)
(0, 0) (0, 1) (1, 1) (1, 2) (2, 1)
(0, 0) (0, 1) (1, 1) (1, 2) (2, 2)
(0, 0) (0, 1) (1, 1) (2, 1) (2, 2)
(0, 1) (1, 0) (1, 1) (1, 2) (2, 1)
 
Number of free polyominoes of ranks 1 to 10:
1 1 2 5 12 35 108 369 1285 4655
</pre>
 
=={{header|Nim}}==
{{trans|Kotlin}}
<syntaxhighlight lang="nim">import algorithm, sequtils, strutils, sugar
 
type Point = tuple[x, y: int]
 
func rotate90(p: Point): Point = (p.y, -p.x)
func rotate180(p: Point): Point = (-p.x, -p.y)
func rotate270(p: Point): Point = (-p.y, p.x)
func reflect(p: Point): Point = (-p.x, p.y)
 
func `$`(p: Point): string = "($1, $2)".format(p.x, p.y)
 
 
type Polyomino = seq[Point]
 
func minima(poly: Polyomino): (int, int) =
## Finds the min x and y coordinates of a polyomino.
(min(poly.mapIt(it.x)), min(poly.mapIt(it.y)))
 
func translateToOrigin(poly: Polyomino): Polyomino =
let (minX, minY) = poly.minima
result = sorted(poly.mapIt((it.x - minX, it.y - minY)))
 
func rotationsAndReflections(poly: Polyomino): seq[Polyomino] =
@[poly,
poly.mapIt(it.rotate90),
poly.mapIt(it.rotate180),
poly.mapIt(it.rotate270),
poly.mapIt(it.reflect),
poly.mapIt(it.rotate90.reflect),
poly.mapIt(it.rotate180.reflect),
poly.mapIt(it.rotate270.reflect)]
 
func canonical(poly: Polyomino): Polyomino =
sortedByIt(poly.rotationsAndReflections.map(translateToOrigin), $it)[0]
 
func contiguous(p: Point): array[4, Point] =
# Return all four points in Von Neumann neighborhood.
[(p.x - 1, p.y), (p.x + 1, p.y), (p.x, p.y - 1), (p.x, p.y + 1)]
 
func newPoints(poly: Polyomino): seq[Point] =
## Return all distinct points that can be added to a Polyomino.
result = collect(newSeq):
for point in poly:
for pt in point.contiguous():
if pt notin poly: pt
result = result.deduplicate()
 
func newPolys(poly: Polyomino): seq[Polyomino] =
collect(newSeq, for pt in poly.newPoints: canonical(poly & pt))
 
const Monominoes = @[@[(x: 0, y: 0)]]
 
func rank(n: Natural): seq[Polyomino] =
if n == 0: return newSeq[Polyomino]()
if n == 1: return Monominoes
result = collect(newSeq):
for poly in rank(n - 1):
for p in poly.newPolys(): p
result = sortedByIt(result, $it).deduplicate(true)
 
when isMainModule:
 
let n = 5
echo "All free polyominoes of rank $#:\n".format(n)
for poly in rank(n): echo poly.join(" ")
 
let k = 10
echo "\nNumber of free polyominoes of ranks 1 to $#:".format(k)
for i in 1..k: stdout.write rank(i).len, ' '
echo()</syntaxhighlight>
 
{{out}}
<pre>All free polyominoes of rank 5:
 
(0, 0) (0, 1) (0, 2) (0, 3) (0, 4)
(0, 0) (0, 1) (0, 2) (0, 3) (1, 0)
(0, 0) (0, 1) (0, 2) (0, 3) (1, 1)
(0, 0) (0, 1) (0, 2) (1, 0) (1, 1)
(0, 0) (0, 1) (0, 2) (1, 0) (1, 2)
(0, 0) (0, 1) (0, 2) (1, 0) (2, 0)
(0, 0) (0, 1) (0, 2) (1, 1) (2, 1)
(0, 0) (0, 1) (0, 2) (1, 2) (1, 3)
(0, 0) (0, 1) (1, 1) (1, 2) (2, 1)
(0, 0) (0, 1) (1, 1) (1, 2) (2, 2)
(0, 0) (0, 1) (1, 1) (2, 1) (2, 2)
(0, 1) (1, 0) (1, 1) (1, 2) (2, 1)
 
Number of free polyominoes of ranks 1 to 10:
1 1 2 5 12 35 108 369 1285 4655 </pre>
 
=={{header|Perl}}==
Only shows the polyominoes up to rank 5.
<syntaxhighlight lang="perl">#!/usr/bin/perl
 
use strict;
use warnings;
 
my @new = "#\n";
 
for my $N ( 2 .. 10 )
{
@new = find( @new );
my %allbest;
$allbest{best($_)}++ for @new;
my @show = @new = sort keys %allbest;
printf "rank: %2d count: %d\n\n", $N, scalar @show;
if( @show <= 12 )
{
my $fmt = join '', map({ /\n/; '%' . ($+[0] + 1) . 's' } @show), "\n";
grep $_, @show and printf $fmt, map s/(.*)\n// && $1, @show for 0 .. $N;
print "\n";
}
}
 
sub bare
{
local $_ = shift;
s/^ *\n//gm;
s/^ //gm until /^#/m;
s/ $//gm until /#$/m;
$_;
}
 
sub transpose
{
local $_ = shift;
my $t = '';
$t .= "\n" while s/^./ $t .= $&; '' /gem;
$t;
}
 
sub rotate
{
local $_ = shift;
my $t = '';
$t .= "\n" while s/.$/ $t .= $&; '' /gem;
$t;
}
 
sub best
{
my %all = (shift, 1);
for my $p (keys %all)
{
$all{ my $tmp = rotate $p }++;
$all{ rotate $tmp }++;
}
$all{ transpose $_ }++ for keys %all;
$all{ s/(.+)/reverse $1/ger }++ for keys %all; # mirror
(sort keys %all)[-1];
}
 
sub find
{
my @before = @_;
my %new;
for my $p ( @before )
{
local $_ = $p;
s/^/ /gm;
s/\n/ \n/g;
my $line = s/\n.*/\n/sr =~ tr/\n/ /cr;
$_ = $line . $_ . $line;
my $n = -1 + length $line;
my $gap = qr/.{$n}/s;
$new{ bare "$`#$'" }++ while / (?=#)/g;
$new{ bare "$`#$'" }++ while / (?=$gap#)/g;
$new{ bare "$`#$'" }++ while /(?<=#) /g;
$new{ bare "$`#$'" }++ while /(?<=#$gap) /g;
}
keys %new;
}</syntaxhighlight>
{{out}}
<pre>
rank: 2 count: 1
 
##
 
rank: 3 count: 2
 
## ###
#
 
rank: 4 count: 5
 
## ## ### ### ####
## ## # #
 
rank: 5 count: 12
 
# ## ## ## ### ### ### ### ### #### #### #####
### # ## ## # # # # ## ## # #
# ## # # # #
 
rank: 6 count: 35
 
rank: 7 count: 108
 
rank: 8 count: 369
 
rank: 9 count: 1285
 
rank: 10 count: 4655
 
</pre>
 
=={{header|Phix}}==
Written for clarity over raw speed.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Polyominoes.exw</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">rotate90</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">x</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">reflectx</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{-</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">rotflect</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">fn</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">xy</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">return</span> <span style="color: #7060A8;">call_func</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xy</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">rotationsAndReflections</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- All the plane symmetries of a rectangular region.
-- (ie orig plus 3*90 plus reflect and another 3*90)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">8</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">fn</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">5</span><span style="color: #0000FF;">?</span><span style="color: #000000;">reflectx</span><span style="color: #0000FF;">:</span><span style="color: #000000;">rotate90</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rotflect</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">fn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">translateToOrigin</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Ensure {minx,miny} is/move it to {1,1}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">minx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">vslice</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">))-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">miny</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">vslice</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">))-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">unique</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">,{{</span><span style="color: #000000;">minx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">miny</span><span style="color: #0000FF;">}}}))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">canonical_poly</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Returns unique/min representation, eg {{1,1},{1,2}} not {{1,1},{2,1}}</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rotationsAndReflections</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">),</span><span style="color: #000000;">translateToOrigin</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">contiguous</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">pt</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- All four points in Von Neumann neighborhood</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pt</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">new_points</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Finds all distinct points that can be added to a Polyomino.</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">contiguous</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">unique</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">new_polys</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Finds all polys that can be created by adding one more point.</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">pts</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">new_points</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pts</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">pt</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pt</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">poly</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">),</span><span style="color: #000000;">pt</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">canonical_poly</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">ranks</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}}}}</span> <span style="color: #000080;font-style:italic;">-- (rank[1] = a single monomino)</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">rank</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ranks</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ranks</span><span style="color: #0000FF;">[$],</span> <span style="color: #000080;font-style:italic;">-- (extend last)</span>
<span style="color: #000000;">polys</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">polys</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">new_polys</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">polys</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">unique</span><span style="color: #0000FF;">(</span><span style="color: #000000;">polys</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">ranks</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ranks</span><span style="color: #0000FF;">,</span><span style="color: #000000;">polys</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">ranks</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">print_polys</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- pp(p,{pp_Nest,1})</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">lines</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">),</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">pi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">lines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">][</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)*(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'#'</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n%s\n\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lines</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">ri</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rank</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"rank:%d count:%d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ri</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">5</span> <span style="color: #008080;">then</span> <span style="color: #000000;">print_polys</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ri</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
rank:1  count:1
 
  # 
 
rank:2  count:1
 
  #  
  #  
 
rank:3  count:2
 
  #   ##  
  #   #   
  #       
 
rank:4  count:5
 
  #    ##   #    ##   #    
  #    #    ##   ##   ##   
  #    #    #          #   
  #                        
 
rank:5  count:12
 
  #     ##    #     ##    ##    ###   #     #     #     #     #      #    
  #     #     ##    ##    #     #     ###   #     ###   ##    ###   ###   
  #     #     #     #     ##    #     #     ##     #     ##     #    #    
  #     #     #                              #                            
  #                                                                       
 
rank:6  count:35
rank:7  count:108
rank:8  count:369
rank:9  count:1285
rank:10  count:4655
</pre>
 
=={{header|Python}}==
{{trans|Haskell}}
<langsyntaxhighlight lang="python">from itertools import imap, imap, groupby, chain, imap
from operator import itemgetter
from sys import argv
Line 903 ⟶ 2,389:
print text_representation(poly), "\n"
 
main()</langsyntaxhighlight>
{{out}}
<pre>[1, 1, 2, 5, 12, 35, 108, 369, 1285, 4655]
Line 962 ⟶ 2,448:
not included in code below). But I think it's interesting nonetheless.
 
<langsyntaxhighlight lang="racket">#lang typed/racket
;; Inspired by C code in http://www.geocities.jp/tok12345/countomino.txt
;; but tries to take advantage of arbitrary width integers
Line 1,175 ⟶ 2,661:
(when (< n 6) (draw-polynominoes p))
(printf "count: ~a~%~%" (length (polynominoes-shapes p)))
(flush-output))))</langsyntaxhighlight>
 
{{out}}
Line 1,255 ⟶ 2,741:
=={{header|Ruby}}==
{{trans|Python}}
<langsyntaxhighlight lang="ruby">require 'set'
 
def translate2origin(poly)
Line 1,326 ⟶ 2,812:
n = ARGV[0] ? ARGV[0].to_i : 5
puts "\nAll free polyominoes of rank %d:" % n
rank(n).sort.each{|poly| puts text_representation(poly),""}</langsyntaxhighlight>
 
{{out}}
Line 1,373 ⟶ 2,859:
###
#
</pre>
 
=={{header|Scala}}==
Translation of [[Free_polyominoes_enumeration#Haskell|Haskell]] via [[Free_polyominoes_enumeration#D|Java]]
{{works with|Scala|2.12}}
<syntaxhighlight lang="scala">object Free {
type Point = (Int, Int)
type Polyomino = List[Point]
 
def rotate90(p: Point): Point = (p._2, -p._1)
 
def rotate180(p: Point): Point = (-p._1, -p._2)
 
def rotate270(p: Point): Point = (-p._2, p._1)
 
def reflect(p: Point): Point = (-p._1, p._2)
 
def minima(polyomino: Polyomino): Point = {
polyomino.reduce((a,b) => (Math.min(a._1, b._1), Math.min(a._2, b._2)))
}
 
def translateToOrigin(polyomino: Polyomino): Polyomino = {
val m = minima(polyomino)
polyomino.map(p => (p._1 - m._1, p._2 - m._2))
}
 
def rotationsAndReflections(polyomino: Polyomino): List[Polyomino] = {
val refPol = polyomino.map(reflect)
List(
polyomino,
polyomino.map(rotate90),
polyomino.map(rotate180),
polyomino.map(rotate270),
refPol,
refPol.map(rotate90), // === pol
refPol.map(rotate180),
refPol.map(rotate270),
)
}
 
def canonical(polyomino: Polyomino): Polyomino = {
import Ordering.Implicits._
rotationsAndReflections(polyomino)
.map(translateToOrigin)
.map(poly => poly.sorted).min
}
 
def contiguous(p: Point): List[Point] = List(
(p._1 - 1, p._2),
(p._1 + 1, p._2),
(p._1, p._2 - 1),
(p._1, p._2 + 1),
)
 
def newPoints(polyomino: Polyomino): List[Point] = {
polyomino.flatMap(contiguous).filterNot(polyomino.contains(_)).distinct
}
 
def newPolyominos(polyomino: Polyomino): List[Polyomino] = {
newPoints(polyomino).map(p => canonical(p :: polyomino)).distinct
}
 
val monomino: Polyomino = List((0, 0))
val monominos: List[Polyomino] = List(monomino)
 
def rank(n: Int): List[Polyomino] = {
require(n >= 0)
n match {
case 0 => Nil
case 1 => monominos
case _ => rank(n - 1).flatMap(newPolyominos).distinct
}
}
}</syntaxhighlight>
 
<pre>(0,0) (0,1) (1,1) (1,2) (2,1)
(0,0) (0,1) (0,2) (1,0) (1,1)
(0,0) (0,1) (0,2) (0,3) (1,1)
(0,1) (1,0) (1,1) (1,2) (2,1)
(0,0) (0,1) (0,2) (1,1) (2,1)
(0,0) (0,1) (1,1) (1,2) (2,2)
(0,0) (0,1) (0,2) (1,2) (1,3)
(0,0) (0,1) (1,1) (2,1) (2,2)
(0,0) (0,1) (0,2) (1,0) (1,2)
(0,0) (0,1) (0,2) (0,3) (1,0)
(0,0) (0,1) (0,2) (1,0) (2,0)
(0,0) (0,1) (0,2) (0,3) (0,4)</pre>
 
=={{header|Sidef}}==
{{trans|Ruby}}
<syntaxhighlight lang="ruby">func translate2origin(poly) {
# Finds the min x and y coordiate of a Polyomino.
var minx = poly.map(:head).min
var miny = poly.map(:tail).min
poly.map {|p| [p.head-minx, p.tail-miny] }.sort
}
 
func rotate90(x,y) { [y, -x] }
func reflect(x,y) { [-x, y] }
 
# All the plane symmetries of a rectangular region.
func rotations_and_reflections(poly) {
gather {
take(poly)
take(poly.map!{ rotate90(_...) })
take(poly.map!{ rotate90(_...) })
take(poly.map!{ rotate90(_...) })
take(poly.map!{ reflect(_...) })
take(poly.map!{ rotate90(_...) })
take(poly.map!{ rotate90(_...) })
take(poly.map!{ rotate90(_...) })
}
}
 
func canonical(poly) {
rotations_and_reflections(poly).map{|pl| translate2origin(pl) }
}
 
# All four points in Von Neumann neighborhood.
func 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.
func new_points(poly) {
var points = Set()
poly.each { points << contiguous(_...)... }
points - poly
}
 
func new_polys(polys) {
var pattern = Set()
polys.map { |poly|
gather {
new_points(poly).each { |point|
var pl = translate2origin(poly + [point])
next if pattern.has(pl)
take canonical(pl).each{ pattern << _ }.min
}
}...
}
}
 
# Generates polyominoes of rank n recursively.
func rank(n) {
given (n) {
when (0) { [[]] }
when (1) { [[[0,0]]] }
else { new_polys(rank(n-1)) }
}
}
 
# Generates a textual representation of a Polyomino.
func text_representation(poly) {
var table = Hash()
for x,y in (poly) { table{[x,y]} = '#' }
var maxx = poly.map(:head).max
var maxy = poly.map(:tail).max
(0..maxx).map{|x| (0..maxy).map{|y| table{[x,y]} \\ ' ' }.join }
}
 
say 8.of { rank(_).len }
 
var n = (ARGV[0] ? ARGV[0].to_i : 5)
say ("\nAll free polyominoes of rank %d:" % n)
rank(n).sort.each{|poly| say text_representation(poly).join("\n")+"\n" }</syntaxhighlight>
{{out}}
<pre style="height:250px">
[1, 1, 1, 2, 5, 12, 35, 108]
 
All free polyominoes of rank 5:
#####
 
####
#
 
####
#
 
###
##
 
###
# #
 
###
#
#
 
###
#
#
 
###
##
 
##
##
#
 
##
##
#
 
##
#
##
 
#
###
#
</pre>
 
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-trait}}
{{libheader|Wren-math}}
{{libheader|Wren-sort}}
{{libheader|Wren-seq}}
<syntaxhighlight lang="wren">import "./trait" for Comparable
import "./math" for Nums
import "./sort" for Sort, Cmp
import "./seq" for Lst
import "io" for Stdout
 
class Point is Comparable {
construct new(x, y) {
_x = x
_y = y
}
 
x { _x }
y { _y }
 
rotate90() { Point.new( _y, -_x) }
rotate180() { Point.new(-_x, -_y) }
rotate270() { Point.new(-_y, _x) }
reflect() { Point.new(-_x, _y) }
 
compare(other) {
if (other.type != Point) Fiber.abort("Argument must be a point.")
if (_x == other.x && _y == other.y) return 0
if (_x < other.x || (_x == other.x && _y < other.y)) return -1
return 1
}
 
// All four points in Von Neumann neighborhood
contiguous {
return [
Point.new(_x - 1, _y), Point.new(_x + 1, _y),
Point.new(_x, _y - 1), Point.new(_x, _y + 1)
]
}
 
toString { "(%(x), %(y))" }
}
 
var DistinctByString = Fn.new { |list|
var m = {}
for (e in list) m[e.toString] = e
return m.keys.map { |key| m[key] }.toList
}
 
class Polyomino {
construct new(points) {
_points = points
}
 
points { _points }
 
// Finds the min x and y coordinates of a Polyomino.
minima {
var minX = Nums.min(_points.map { |p| p.x })
var minY = Nums.min(_points.map { |p| p.y })
return [minX, minY]
}
 
translateToOrigin() {
var mins = minima
var points = _points.map { |p| Point.new(p.x - mins[0], p.y - mins[1]) }.toList
Sort.quick(points)
return Polyomino.new(points)
}
 
// All the plane symmetries of a rectangular region.
rotationsAndReflections {
return [
Polyomino.new(_points),
Polyomino.new(_points.map { |p| p.rotate90() }.toList),
Polyomino.new(_points.map { |p| p.rotate180() }.toList),
Polyomino.new(_points.map { |p| p.rotate270() }.toList),
Polyomino.new(_points.map { |p| p.reflect() }.toList),
Polyomino.new(_points.map { |p| p.rotate90().reflect() }.toList),
Polyomino.new(_points.map { |p| p.rotate180().reflect() }.toList),
Polyomino.new(_points.map { |p| p.rotate270().reflect() }.toList)
]
}
 
canonical {
var toos = rotationsAndReflections.map { |poly| poly.translateToOrigin() }.toList
var cmp = Fn.new { |i, j| Cmp.string.call(i.toString, j.toString) }
Sort.quick(toos, 0, toos.count - 1, cmp)
return toos[0]
}
 
// Finds all distinct points that can be added to a Polyomino.
newPoints {
var fn = Fn.new { |p| p.contiguous }
var t = Lst.flatMap(_points, fn).where { |p| !_points.contains(p) }.toList
return DistinctByString.call(t)
}
 
newPolys { newPoints.map { |p| Polyomino.new(_points + [p]).canonical }.toList }
 
toString { _points.map { |p| p.toString }.join(" ") }
}
 
var monomino = Polyomino.new([Point.new(0, 0)])
var monominoes = [monomino]
 
// Generates polyominoes of rank n recursively.
var rank
rank = Fn.new { |n|
if (n < 0) Fiber.abort("n cannot be negative.")
if (n == 0) return []
if (n == 1) return monominoes
var t = Lst.flatMap(rank.call(n-1)) { |poly| poly.newPolys }.toList
t = DistinctByString.call(t)
var cmp = Fn.new { |i, j| Cmp.string.call(i.toString, j.toString) }
Sort.quick(t, 0, t.count - 1, cmp)
return t
}
 
var n = 5
System.print("All free polyominoes of rank %(n):\n")
for (poly in rank.call(n)) {
for (pt in poly.points) System.write("%(pt) ")
System.print()
}
var k = 10
System.print("\nNumber of free polyominoes of ranks 1 to %(k):")
for (i in 1..k) {
System.write("%(rank.call(i).count) ")
Stdout.flush()
}
System.print()</syntaxhighlight>
 
{{out}}
<pre>
All free polyominoes of rank 5:
 
(0, 0) (0, 1) (0, 2) (0, 3) (0, 4)
(0, 0) (0, 1) (0, 2) (0, 3) (1, 0)
(0, 0) (0, 1) (0, 2) (0, 3) (1, 1)
(0, 0) (0, 1) (0, 2) (1, 0) (1, 1)
(0, 0) (0, 1) (0, 2) (1, 0) (1, 2)
(0, 0) (0, 1) (0, 2) (1, 0) (2, 0)
(0, 0) (0, 1) (0, 2) (1, 1) (2, 1)
(0, 0) (0, 1) (0, 2) (1, 2) (1, 3)
(0, 0) (0, 1) (1, 1) (1, 2) (2, 1)
(0, 0) (0, 1) (1, 1) (1, 2) (2, 2)
(0, 0) (0, 1) (1, 1) (2, 1) (2, 2)
(0, 1) (1, 0) (1, 1) (1, 2) (2, 1)
 
Number of free polyominoes of ranks 1 to 10:
1 1 2 5 12 35 108 369 1285 4655
</pre>
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/251089...352550"