JavaScript (Node.js), \$N=10\$ за 4 минуты 2 секунды1
1: на Intel Code i7, 7-го поколения
Это включает лишь некоторые тривиальные оптимизации и поэтому весьма неэффективно. По крайней мере, это подтверждает результаты, перечисленные в задании.
...
16: 438030079
17: 2092403558
18: 10027947217
19: 48198234188
20: 232261124908
21: 1121853426115
Попробуйте онлайн! (до \$N=8\$)
Выход
javac Main.java
java Main 17
||answer||
Java 8, \$n=14\$ за 2 минуты 31 секунду1
1. Используя дистрибутив AdoptOpenJDK8, на 2-ядерный процессор Intel Core i5 Янтарного озерана базе Mac. На Амазон EC2 m5.xlarge, берет 1м16с.
При этом применяется индуктивный подход, при котором для каждого ранга строятся все здания предыдущего ранга, размещая кубы во всех допустимых позициях (поверх и рядом с существующими кубами), а затем удаляя здания, которые (возможно, преобразованы) являются дубликатами. других зданий. Это означает, что для перечисления зданий в ранге необходимо также вычислить все предыдущие ранги. И время вычислений, и память являются ограниченными ресурсами — этот алгоритм основан на хранении миллионов объектов Building в памяти — поэтому мне было трудно выполнять вычисления за пределами \$n=14\$ на моей машине даже без ограничения времени в 10 минут.
Это решение включает в себя подход на основе параллельного потока (который можно включить с помощью 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));
}
}
}
}
JVM system property) which is faster on a multi-core system but also more memory-hungry. This approach was used for the timing results above. The non-parallel approach takes almost twice as long to count \$n=14\$ but is able to do so using only a third of the memory.
Параметры и настройка сборщика мусора могут оказать существенное влияние на время выполнения и возможность завершения процесса. Я также тестировал OpenJDK 13, но по какой-то причине пока лучшие результаты получены на 8.
normalizeInPlace
Попробуйте онлайн! (непараллельный, до n=12)
Призыв
Array.sort
ParallelGC используется по умолчанию в Java 8, но он включен в случае, если вы используете более позднюю версию JDK, где G1GC является значением по умолчанию.
Выход
-Djava.util.concurrent.ForkJoinPool.common.parallelism=0
(Для справки: \$15 \rightarrow 92{,}038{,}062\$)
![[artcapital] Фондовый рынок сша. Старт сезона отчетностей](/assets/images/icons/forum6.png){kind=icon}
![[Своим ходом] [Лиза и Виталик] Улётный гайд (2019)](/assets/images/icons/forum0.png){kind=icon}
![[radionic Program] Аудиопрограмма](/assets/images/icons/forum4.png){kind=icon}
