Anonymous user
Free polyominoes enumeration: Difference between revisions
→{{header|Java}}: added Java
(→{{header|Java}}: added Java) |
|||
Line 696:
│ │# │# │ │ │ │ │ │ │ │ │ │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘</lang>
=={{header|Java}}==
{{works with|Java|8}}
<lang java>import java.awt.Point;
import java.util.*;
import java.util.function.Function;
import static java.util.Comparator.comparing;
import static java.util.stream.Collectors.toList;
public class FreePolyominoesEnum {
static final List<Function<Point, Point>> transforms = new ArrayList<>();
static {
transforms.add(p -> new Point(p.y, -p.x));
transforms.add(p -> new Point(-p.x, -p.y));
transforms.add(p -> new Point(-p.y, p.x));
transforms.add(p -> new Point(-p.x, p.y));
transforms.add(p -> new Point(-p.y, -p.x));
transforms.add(p -> new Point(p.x, -p.y));
transforms.add(p -> new Point(p.y, p.x));
}
static Point findMinima(List<Point> poly) {
return new Point(
poly.stream().mapToInt(a -> a.x).min().getAsInt(),
poly.stream().mapToInt(a -> a.y).min().getAsInt());
}
static List<Point> translateToOrigin(List<Point> poly) {
final Point min = findMinima(poly);
return poly.stream().map(p -> new Point(p.x - min.x, p.y - min.y))
.collect(toList());
}
static List<List<Point>> rotationsAndReflections(List<Point> poly) {
List<List<Point>> lst = new ArrayList<>();
lst.add(poly);
for (Function<Point, Point> t : transforms)
lst.add(poly.stream().map(t).collect(toList()));
return lst;
}
static Comparator<Point> byCoords = Comparator.<Point>comparingInt(p -> p.x)
.thenComparingInt(p -> p.y);
static List<Point> normalize(List<Point> poly) {
return rotationsAndReflections(poly).stream()
.map(lst -> translateToOrigin(lst))
.map(lst -> lst.stream().sorted(byCoords).collect(toList()))
.min(comparing(Object::toString)) // not efficient but simple
.get();
}
static List<Point> neighborhoods(Point p) {
return Arrays.asList(new Point[]{new Point(p.x - 1, p.y),
new Point(p.x + 1, p.y), new Point(p.x, p.y - 1),
new Point(p.x, p.y + 1)});
}
static List<Point> concat(List<Point> lst, Point p) {
List<Point> r = lst.stream().map(pt -> new Point(pt)).collect(toList());
r.add(new Point(p));
return r;
}
static List<Point> newPoints(List<Point> poly) {
return poly.stream()
.flatMap(p -> neighborhoods(p).stream())
.filter(p -> !poly.contains(p))
.distinct()
.collect(toList());
}
static List<List<Point>> constructNextRank(List<Point> poly) {
return newPoints(poly).stream()
.map(p -> normalize(concat(poly, p)))
.distinct()
.collect(toList());
}
static List<List<Point>> rank(int n) {
if (n < 0)
throw new IllegalArgumentException("n cannot be negative");
if (n < 2) {
List<List<Point>> r = new ArrayList<>();
if (n == 1)
r.add(Arrays.asList(new Point[]{new Point(0, 0)}));
return r;
}
return rank(n - 1).stream()
.flatMap(lst -> constructNextRank(lst).stream())
.distinct()
.collect(toList());
}
public static void main(String[] args) {
for (List<Point> poly : rank(5)) {
for (Point p : poly)
System.out.printf("(%d,%d) ", p.x, p.y);
System.out.println();
}
}
}</lang>
<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|Python}}==
| |||