Java 11, \$n=17\$ in about 8.5 minutes
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 -- 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-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.
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
javac Main.java
java Main 17
Try it online!
Results
(when run without an argument)
...
16: 438030079
17: 2092403558
18: 10027947217
19: 48198234188
20: 232261124908
21: 1121853426115
