# Java 11, \$n=17\$ in about 8.5 minutes
### Based on [Haskell solution by Christian Sievers](https://codegolf.stackexchange.com/a/199919) – upvote his!
This answer is the result of learning enough Haskell to be able to understand Christian's answer, translating it into Java, applying numerous micro-optimizations, and throwing multiple cores at it. The exact runtime varies significantly depending on the number of cores available; this timing result is from my own two-core machine. A 48-core EC2 c5.24xlarge is able to compute \$n=17\$ in 16 seconds, and \$n=20\$ in 18 minutes.
Parallelism can be disabled by adding the JVM argument `-Djava.util.concurrent.ForkJoinPool.common.parallelism=0`. Single-threaded performance is slightly better than double that of the Haskell solution.
Some of the optimizations include:
* Representing a point using a single int value
* Using simplified hand-rolled collections based on int arrays, avoiding the primitive boxing required for the standard Java collections
* Reimplementing polyomino enumeration based on [this paper](https://doi.org/10.1016%2F0012-365X%2881%2990237-5) -- my initial attempt at a direct translation of the Haskell code performed extra throwaway work that didn't actually contribute to the computation
* Replacing higher-level [Stream](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/stream/Stream.html)-based implementations with inlined code, making it very ugly and verbose
The bulk of the processing time is spent in `Array.sort` calls in `normalizeInPlace`. Finding a way to compare polyomino transformations without sorting could easily result in a further 4x speedup. The forking is also not done very intelligently which leads to unbalanced tasks and unused cores at higher levels of parallelism.
```java
import java.util.Arrays;
import java.util.concurrent.RecursiveTask;
import java.util.function.IntPredicate;
import java.util.function.IntUnaryOperator;
import java.util.function.LongSupplier;
import java.util.function.ToLongFunction;
/**
* Utility methods for working with an int that represents a pair of short values.
*/
class Point {
static final int start = p(0, 0);
static final int[] neighbors = new int[] {-0x10000, -0x1, 0x1, 0x10000};
static int x(int p) {
return (p >> 16) - 0x4000;
}
static int y(int p) {
return (short)(p) - 0x4000;
}
static int p(int x, int y) {
return ((x + 0x4000) << 16) | (y + 0x4000);
}
static int rot(int p) {
return p(-y(p), x(p));
}
static int mirror(int p) {
return p(-x(p), y(p));
}
}
/**
* Minimal primitive array-based collections.
*/
class IntArrays {
/** Concatenates the end of the first array with the beginning of the second. */
static int[] arrayConcat(int[] a, int aOffset, int[] b, int bLen) {
int aLength = a.length - aOffset;
int[] result = new int[aLength + bLen];
System.arraycopy(a, aOffset, result, 0, aLength);
System.arraycopy(b, 0, result, aLength, bLen);
return result;
}
/** Adds a new value to a sorted set, returning the new result */
static int[] setAdd(int[] set, int val) {
int[] dst = new int[set.length + 1];
int i = 0;
for (; i < set.length && set[i] < val; i++) {
dst[i] = set[i];
}
dst[i] = val;
for (; i < set.length; i++) {
dst[i + 1] = set[i];
}
return dst;
}
private static final int[] primes = new int[] {
5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131
};
/**
* Allocate an array large enough to hold a fixed-capacity hash table
* that can contain "seen" points for generating polyominos of size n.
*/
static int[] makeHashTable(int n) {
return new int[primes[-(Arrays.binarySearch(primes, n * 3) + 1)]];
}
/** Inserts a new value to a hash table, in-place */
static void hashInsert(int[] table, int val) {
int pos = (val * 137) % table.length, startPos = pos;
if (table[pos] != 0) {
while ((table[pos = (pos + 1) % table.length]) != 0) {
if (pos == startPos) {
throw new AssertionError("table full");
}
}
}
table[pos] = val;
}
/** Checks whether a hash table contains the specified value */
static boolean hashContains(int[] table, int val) {
int pos = (val * 137) % table.length, startPos = pos;
while (true) {
int curr = table[pos];
if (curr == val) return true;
if (curr == 0) return false;
pos = (pos + 1) % table.length;
if (pos == startPos) {
throw new AssertionError("table full");
}
}
}
}
/**
* Recursively generates int arrays representing collections of Points,
* applying a function to each array to compute a long, and returns the sum
* of all such values.
*/
class PolyominoVisitor extends RecursiveTask<Long> {
PolyominoVisitor(ToLongFunction<? super int[]> func, int n) {
this(func, n, 0, 1, new int[0], IntArrays.makeHashTable(n), new int[]{Point.start});
}
private PolyominoVisitor(ToLongFunction<? super int[]> action, int n,
int i, int limit, int[] used, int[] seen, int[] untried) {
this.func = action;
this.n = n;
this.start = () -> visit(i, limit, used, seen, untried);
}
private final boolean visitSmaller = true;
private final ToLongFunction<? super int[]> func;
private final int n;
private final LongSupplier start;
@Override
protected Long compute() {
return start.getAsLong();
}
private long visit(int i, int limit, int[] used, int[] seen, int[] untried) {
long val = 0;
if (used.length + 1 == n) {
// reached the second to last level, so we can apply the function
// directly to our children
for (; i < limit; i++) {
val += func.applyAsLong(IntArrays.setAdd(used, untried[i]));
}
} else if (used.length + 6 < n && limit - i >= 2) {
// eligible to split
PolyominoVisitor[] tasks = new PolyominoVisitor[limit - i];
for (int j = 0; j < tasks.length; j++) {
tasks[j] = new PolyominoVisitor(func, n,
i + j, i + j + 1, used, seen, untried);
}
invokeAll(tasks);
for (PolyominoVisitor task : tasks) val += task.getRawResult();
return val;
} else {
// recursively visit children
int[] newReachable = new int[4];
IntPredicate inSeen = p -> !IntArrays.hashContains(seen, p);
for (; i < limit; i++) {
int candidate = untried[i];
int[] child = IntArrays.setAdd(used, candidate);
int reachableCount = neighbors(candidate, inSeen, newReachable);
int[] newSeen = seen.clone();
for (int j = 0; j < reachableCount; j++) IntArrays.hashInsert(newSeen, newReachable[j]);
int[] newUntried = IntArrays.arrayConcat(untried, i + 1, newReachable, reachableCount);
val += visit(0, newUntried.length, child, newSeen, newUntried);
}
}
if (visitSmaller && used.length > 0 && limit == untried.length) {
val += func.applyAsLong(used);
}
return val;
}
/**
* Write the greater-than-origin neighbors of the given point
* that pass the provided predicate into the provided array,
* returning the count written.
*/
private static int neighbors(int p, IntPredicate pred, int[] dst) {
int count = 0;
for (int offset : Point.neighbors) {
int n = p + offset;
if (n > Point.start && pred.test(n)) {
dst[count++] = n;
}
}
return count;
}
}
/**
* Function that computes how many buildings are constructable on a given
* polyomino base. Considers symmetry, returning 0 if the figure is not the
* canonical version (i.e. has a smaller transformation).
*
* Adapted largely unchanged from Christian Sievers
* https://codegolf.stackexchange.com/a/199919
*/
class BuildingCounter implements ToLongFunction<int[]> {
private final int n;
public BuildingCounter(int n) {
this.n = n;
}
@Override
public long applyAsLong(int[] fig) {
return combinations(n - fig.length, fig);
}
private static int[] map(int[] fig, IntUnaryOperator func) {
int[] result = new int[fig.length];
for (int i = 0; i < fig.length; i++) {
result[i] = func.applyAsInt(fig[i]);
}
return result;
}
private static int[] normalizeInPlace(int[] fig) {
Arrays.sort(fig);
int d = fig[0] - Point.start;
for (int i = 0; i < fig.length; i++) {
fig[i] -= d;
}
return fig;
}
private static int[] rot(int[] ps) {
return normalizeInPlace(map(ps, Point::rot));
}
private static int[] mirror(int[] ps) {
return normalizeInPlace(map(ps, Point::mirror));
}
private static int myf(int r, int sz, int[] fig) {
int max = Integer.MIN_VALUE;
for (int p : fig) {
if (p > max) max = p;
}
int w = Point.x(max);
if (w % 2 == 0) {
int wh = w / 2;
int myb = 0;
for (int p : fig) {
if (Point.x(p) == wh) myb++;
}
return c12(myb, (sz - myb)/2, r);
} else {
return c1h(sz, r);
}
}
private static int mdf(int r, int sz, int[] fig) {
int lo = Integer.MAX_VALUE;
for (int p : fig) {
int tmp = Point.y(p);
if (tmp < lo) lo = tmp;
}
int mdb = 0;
for (int p : fig) {
if (Point.x(p) == Point.y(p) - lo) mdb++;
}
return c12(mdb, (sz-mdb)/2, r);
}
private static long combinations(int r, int[] fig) {
int[][] alts = new int[7][];
alts[0] = rot(fig);
alts[1] = rot(alts[0]);
alts[2] = rot(alts[1]);
alts[3] = mirror(fig);
alts[4] = mirror(alts[0]);
alts[5] = mirror(alts[1]);
alts[6] = mirror(alts[2]);
int[] rfig = alts[0];
int[] cmps = new int[7];
for (int i = 0; i < 7; i++) {
if ((cmps[i] = Arrays.compare(fig, alts[i])) > 0) {
return 0;
}
}
if (r == 0) {
return 1;
}
int sz = fig.length;
int qtfc = (sz % 2 == 0) ? c1q(sz, r) : sc1x(4, sz, r);
int htfc = (sz % 2 == 0) ? c1h(sz, r) : sc1x(2, sz, r);
int idfc = c1(sz, r);
int[] fsc = new int[] {qtfc, htfc, qtfc,
myf(r, sz, fig), mdf(r, sz, fig),
myf(r, sz, rfig), mdf(r, sz, rfig)};
int gs = 1;
int allfc = idfc;
for (int i = 0; i < fsc.length; i++) {
if (cmps[i] == 0) {
allfc += fsc[i];
gs++;
}
}
return allfc / gs;
}
private static int c1(int n, int t) {
int v = 1;
for (int x = 1; x <= t; x++) {
v = v * (n+x-1) / x;
}
return v;
}
private static int c1h(int n, int t) {
return c1d(n, t, 2);
}
private static int c1q(int n, int t) {
return c1d(n, t, 4);
}
private static int c1d(int n, int t, int q) {
if (t % q == 0) {
return c1(n / q, t / q);
} else {
return 0;
}
}
private static int sc1x(int m, int n, int t) {
return c1(1 + n / m, t / m);
}
private static int c12(int s, int d, int t) {
int sum = 0;
for (int i = t/2; i >= 0; i--) {
sum += c1(s, t-2*i) * c1(d, i);
}
return sum;
}
}
public class Main {
public static long count(int n) {
return new PolyominoVisitor(new BuildingCounter(n), n).compute();
}
public static void main(String[] args) {
if (args.length > 0) {
System.out.println(args[0] + ": " + count(Integer.parseInt(args[0])));
} else {
for (int i = 1; i <= 99; i++) {
System.out.println(i + ": " + count(i));
}
}
}
}
```
### Invocation
```bash
javac Main.java
java Main 17
```
[Try it online!](https://tio.run/##tVp9b9s2Gv8/n4IrsEGqZcd20mZpXna9YsMV6G7Fsu4OKIyDLNE2E1lSRTm228tn7/0ekpJFmXKyDWeglU0@b3zeHyq34X3Yv43vvn4VyzwrSnaLhcGqFMngdVGEW3lxtLcRZWm0KgqeloNfOb5Jcc9/C@WdA3S2SqNSZOngbVq@L3gsorDkj8B9SMNi@0vOi7DMikOw77J0frPK80Twg3C/ZQT5k/l5cXR0/Pz5EXvOPgBKlFu25OUiiyWbZQVbZ8WdSOdsLcoFC1Mm0pKVi7BkBc8LLnFmyUKWh6Jg2YzJBbG8D5MVlwOQPD6KklBK9j4jvC9HDB9ZhqWI2EykYaLIYQFIVyz3hgEb@hdOqI8TlnIxX0yzQgI25Wuz@qU/3IyG@ASMvoGC@Y/WHnC4BjXitvHo/9w30tCn4OWqSJmXs@trNnrpsz7wT4GuRXnYo7HtpqE04Hv540RyRWQTaIouWt6G9QwRn11eKtH@y7ztbrWLdpGVnSLmXn8L@QJoIvc7KSxFUWTFISIbRWTbJPJQu9LPIhVLWC4vxFKUiAcWUvT0p6HkMYuyJOHK@Swvga/rGDP8QIu9QWwhRFL8k3A8zngak6fR15koZKkJa/@kxSmfizQllzVQkiM@4wGxsc8I51G4moVnVrQ9wl9mM8nLwMBN9er0HU@bylCQWJuD9xULB4n@2q/QL5qQIIOAWSVlw30r5J4iPdnB32xlyZcDJV@U5VsPctUyaTJw8qDi7h/AnCrACscgBPosF227ajDLKcgKr@OYwpzEVsHNygw/JVwd1jQyET6pnXROgOawLrUDAxS9@ofWLii3lIvdWDb1BdhKyT02mlj6ZQKAw90SZS/vAquXrIH23Xf066OYYBkMsd/rNbnSBzwJ4MpA7kg@HO2BEI3DLLtZqDMcZGOsAmjLJIiqewSEK0lSwPFWhrQ4vwjYWcBGyJGjE/yj7@cBG@P7GM8TrJ9g7RTPU6yd4vsLPF9g7@UosCi9xN4Z4M6wf4b97/H8Hs9zojkkBkPiMFQ/z4kn/RzTz5ORPs5F7WKaMjwtSTIKeKo1OrKTsJhT2Ger@YL8bpElMZxvJjY87kdhHkZUsxahxG44TXhFCVFfhkK55DPJefqM5VSFdFmb85TqKW3mWbLNliLNpKpg4jPcd2CIOHx3Gd7xf4DZb8RL5cfUkR8r7WtzfOx7OrENpoKK@Q0Pi2jh6c2ApZD2xCdv8CeTvdh7m0pelI7w2x2Z4qefJ2HEWyLfZyJWcJqIibgaxxVz0Ae5j4cdiDU6OfPZtxrD@HOgC/Z7BQbgRhDOmKcgP2J5wr5BOLb9fr0QCUdlq8GIFT3o8C1GE99JouKkkK9qYVxg9CkXRbZWqnstSQcoOj@q0vZM8WKzVZI8ayTC/SC0f@2@NY7ayAMNy71Z8OhO4szop3hhWazyTl3TZM4jMRPIpdq8thGnWZZwhANhvzFo/2dLGjOVxYq39UqEqdsFyk4BtvrIOhrkSotlgoLIdUMOa7hZmMgW4GFP2Sf6BOf4M47RdoNmy1O3/sm2Si9IxKpF0E1N3TFT1mm0QJR2VIMsA6ITooHfEghynGnRKd55GC1MRsSvKFvmK8qSLEErj7KOrkhrz3jUakm0QDlMEvwCrqsrN5nvdyEFZgvGN@i0UOmtKeaShoVro8A2imfPEpc/gBcmFZ0rr9UBtHtaSbJcCOnpvVR1JygWVcYcToJdIziws23q7@AmX5TOBsrED76zPv5BaUO1auQNnNnECgOhQRNqcatOcYX@NqjbHJ7W62lZIMDbWlBDGfWOZhSz9lIq4621aljyMGBcs3s6lwc5jAyau@ZbcXRqRrcMVWZRZG7QrydcxXUdpzb447Z2YSltujaa46qOVNMO/O2Xe14UIuYGKSsRKUiOhFB5vucouorGYI7mUhKo5z46BUyluL9uRE0Np7F6T0pBRKTRrFI6Stt56PgYsiOwcbjdqELxjfiETBzJBObM2BoFgxoiSg169DFGaFOLRQFdJSpHZKuCRUjkccFtuEabqo7t7FDpQ@fqXSlmA8XbKHYXn6aT1woz6kEv63fnTcaR3B0KeglpUmrPlUiYoQS7vmJjh8Z4IuaCMjTOKOE9pQXQjnlVJeVd1RLvbdfsWkVMKYk841aZFo9LTahu62/dSlNAH28nHQzrvNeZX2guuA30gzynK6yPutsVkd5ndxy9tKek8R1H20v@BMleafH9yvT0iyLq13D9q5rnvBYtE3rWGGRs7HD1XYVUAeh2z@q2BxwRGqoW78aZ05aZmvdoALiBjqiZoeT4zc5NrdZJ6zF3KeUpQaEaINRbERPLq4bXX7hgcRR1SkB2hE1NzHcS0BmC1PAmAy@lC3MR5tWogTl7YOnN75IIQEZTpIxBhCzGPQe0KwhscUwY2Ko204bhYsuEyDgk1getTUtbzVsao20dHiObdNCSzcHHuLVO/8OgwbHuiZW1AtYU/oNVSg/NBJTXrGqKhNbMc9dsuMtxV7XzmO22u3XlX6LoH7gvcAwj1VT8r0LAa6mEzKGskhf9chGm/axATk0bV6zm8myOaE314FxRULe/OfWPBIDqfI9KHePLLgqRmK09ZcCgImBfFUXKqdcQC72nPXe3rjlUI1G7vhpwAjv@SYZgd3HUnociEz/tSyLay9TdGvKf7iprPq7xR2eYnsHZHz5SmLnRnJLBSbIB5gEEhe9KKnQfpMTr9SZ219flacbUCmn//vWnenIga5meSbIFJp5lmG7ZdAUnhwkkbKOGUYmmL9KDD7BCbXiiVF@PMLq7HdCFrIRR4SJyu1zystg2L/@GpAB9NztfgbKQLM3ojQEnWkhXWQpTJQwNniTxPDEATeQMuk40IVMWYSphmGVIJ/BpYiHk13GYUxeo7oNQQXBCeO4cK7MiW2LYLoQsBbqkG8GJPOEsyjKXr46Poyzm8yyZkUGiO77RmAPo5Tg8Hp2fn4/OG3PR341yVBKhBneZJ3ypXnW0WmDT@n7pbnv1zmqawIFbdD3nXNTs@h@c/bAmphrPZlLQbg@9OzpjHJRuntS4CffsE1id8Ajl0PVide@V71iouLPeS6kktX99u3fjvWM8cUShvsJVRXgH6KzEmrC@g23mR8jlAZV60AMJ0nHN7Tx0Sl6YiM/8bfqertfcSq6KelYo3r59LU21jCQaTqD3Rlr4S8fXR2T9KxYfOCagHj@jeVdEd8fSdZPZVgE5Qi4DfZRXr4DuP8V96vdJf5aRpvAoL7bczpQyCz3Yyc9VRWhZTcGGG91p8DkvBj@//ed/fn/97sOPDtPkKA0tAvVdE9I9CPmGWu4yCJFYY1Pbf@MRvD0urtm3bGzuwfZLzppeMK3ZMRtf7O0tt1O7qD1F8IptJVDuE@81WhCQ6/UuDgwXVU4ZjT3ABsyTn@HZ@Oofj1EL/EcGgRp94ZFtir04PWDa@OmmTbKmZV//@w9bll50L/PaZvSic7/UEwQGhszX/PCzy/rLeNrRehxwLds6O0Ggb@IJmk1T7TcHZKJYm6iPL5aB3GpOzB3LrlzsFO5U9McJvTVNyuY7pzOs7cSiTcp@VyrV2AlS7Y2qPQPZ3h9b@6O9/RPaNwnGQf60sd3B4UUbZJ/JyzbIeOLvvd8Fd7rM00zau9Eyt5V0uAKcORM/eYVHlHTpM6WHGjw0cp4qzYo93cHQtOGKe@Mdw6eNM4UzKRkaoy53R064ahYxa/NTOaNLT0ocu6T3A9z1k0kJiAgZjTbeacDaOYLwF134ixb@2I0vYoUfjTzHLnm5jOw3qCRwoNgGSvj9yxuqOoXmRi4YqFzVXDiEUeyhqJUHW@o5ec/IXkPHrI5CJ3qkoZDRoYZCvYmp3KrjrZtmRgOpjJzXHXPZXTn2kpOmdgykxyo67KSv5HVSbmf6e1st9eE3ah2PSyRmPPcPTZj3GBO8tLfpj3wIszk0VT8u56JT0Dojxx62y4CN/cfJfXo6udMnkIstcvrxydImVTSE1KdDIQ9rpNDUJ7ClxxPL/fDpVV5FriqZ1auYA@f3RhjESZ6llmf5BD2MFXWpycYdXiVXy456TUFVHo8v9A01hVe/39YVYfd0hoFc/fFz4dP8O/KI3aHJBIiNad7Menos/TkUaTVq6nW7ZmOoPPj3CHs30bTYnknVKzZ/UL9lsbVpsVV/XLCEUN5NWYCE@nuquWw7FK01rr/amjJ/r5StygGMlZZJqjCoYeixZ6/YMzz02apmDpVOcprzDJzvP@aDlulGKh9esfPzziteh0yiLY3wH383/PXr19H4fw "Java (JDK) – Try It Online")
### Results
(when run without an argument)
```
...
16: 438030079
17: 2092403558
18: 10027947217
19: 48198234188
20: 232261124908
21: 1121853426115
```