-
Notifications
You must be signed in to change notification settings - Fork 6
/
A193838.java
87 lines (80 loc) · 2.44 KB
/
A193838.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
package irvine.oeis.a193;
import java.util.Arrays;
import java.util.HashSet;
import irvine.math.z.Z;
import irvine.oeis.Sequence1;
/**
* A193838 Size k of smallest square of k X k lattice points from which n points with distinct mutual distances can be chosen.
* @author Sean A. Irvine
*/
public class A193838 extends Sequence1 {
private final boolean mVerbose = "true".equals(System.getProperty("oeis.verbose"));
private int mSize = 0;
private int mN = 0;
private final HashSet<Integer> mDistances = new HashSet<>();
private boolean isSolved(final int[] x, final int[] y, final int remaining) {
if (remaining == 0) {
if (mVerbose) {
System.out.println("x=" + Arrays.toString(x) + " y=" + Arrays.toString(y) + " distances=" + mDistances);
}
return true;
}
for (int k = y[remaining]; k < mSize; ++k) {
for (int j = k == y[remaining] ? x[remaining] + 1 : 0; j < mSize; ++j) {
boolean ok = true;
for (int i = x.length - 1; i >= remaining; --i) {
final int dx = x[i] - j;
final int dy = y[i] - k;
final int d = dx * dx + dy * dy;
if (!mDistances.add(d)) {
// Bzzzt, we already have this distance, unwind
for (int l = x.length - 1; l > i; --l) {
final int dxl = x[l] - j;
final int dyl = y[l] - k;
final int dl = dxl * dxl + dyl * dyl;
mDistances.remove(dl);
}
ok = false;
break;
}
}
if (ok) {
// This point is usable
x[remaining - 1] = j;
y[remaining - 1] = k;
if (isSolved(x, y, remaining - 1)) {
return true;
}
for (int i = x.length - 1; i >= remaining; --i) {
final int dx = x[i] - j;
final int dy = y[i] - k;
final int d = dx * dx + dy * dy;
mDistances.remove(d);
}
}
}
}
return false;
}
private boolean isSolved(final int size, final int n) {
// WLOG there must be at least one point on the bottom row
final int[] x = new int[n];
final int[] y = new int[n];
mDistances.clear();
for (int k = 0; k < size; ++k) {
x[n - 1] = k;
if (isSolved(x, y, n - 1)) {
return true;
}
}
return false;
}
@Override
public Z next() {
++mN;
while (!isSolved(mSize, mN)) {
++mSize;
}
return Z.valueOf(mSize);
}
}