-
Notifications
You must be signed in to change notification settings - Fork 6
/
A051602.java
129 lines (119 loc) · 3.96 KB
/
A051602.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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
package irvine.oeis.a051;
import java.util.HashSet;
import java.util.Set;
import irvine.math.z.Z;
import irvine.oeis.Sequence0;
import irvine.util.Point;
/**
* A051602 a(n) is the maximal number of squares that can be formed from n points in the plane.
* @author Sean A. Irvine
*/
public class A051602 extends Sequence0 {
// Heuristics:
//
// 1. All points are assumed to have integer coordinates in the plane.
// 2. All required points fit in a square of width ceil(sqrt(n)).
private final boolean mVerbose = "true".equals(System.getProperty("oeis.verbose"));
private int mN = -1;
private final HashSet<Point> mCurrentPoints = new HashSet<>();
private long mBestCount = 0;
private HashSet<Point> mBestPoints = null;
// Count the number of squares defined by a set of points (i.e., number of squares
// such that every corner of the square is in the set of points).
private long countSquares(final Set<Point> pts) {
long cnt = 0;
for (final Point a : pts) {
for (final Point b : pts) {
if (a.compareTo(b) < 0) {
// a and b define an edge of a potential square
final int dx = b.left() - a.left();
final int dy = b.right() - a.right();
final Point c = new Point(b.left() - dy, b.right() + dx);
if (a.compareTo(c) < 0 && pts.contains(c)) {
final Point d = new Point(c.left() - dx, c.right() - dy);
if (a.compareTo(d) < 0 && pts.contains(d)) {
//System.out.println(a + " -- " + b + " -- " + c + " -- " + d);
++cnt;
}
}
}
}
}
return cnt;
}
private String colour(final int dx, final int dy) {
if (dx == 0 || dy == 0) {
return "gray";
} else if (Math.abs(dx) == Math.abs(dy)) {
return "blue";
} else if (Math.abs(Math.abs(dx) - Math.abs(dy)) == 1) {
return "green";
} else {
return "red";
}
}
// Used to make pictures of solutions
private void tikz(final Set<Point> pts) {
if (pts != null) {
System.out.println("$a(" + pts.size() + ")=" + countSquares(pts) + "$:");
System.out.println("\\begin{center}");
System.out.println("\\begin{tikzpicture}");
for (final Point p : pts) {
System.out.println(" \\fill " + p + " circle (3pt);");
}
System.out.println();
for (final Point a : pts) {
for (final Point b : pts) {
if (a.compareTo(b) < 0) {
// a and b define an edge of a potential square
final int dx = b.left() - a.left();
final int dy = b.right() - a.right();
final Point c = new Point(b.left() - dy, b.right() + dx);
if (a.compareTo(c) < 0 && pts.contains(c)) {
final Point d = new Point(c.left() - dx, c.right() - dy);
if (pts.contains(d) && a.compareTo(d) < 0) {
System.out.println(" \\draw [" + colour(dx, dy) + "] " + a + " -- " + b + " -- " + c + " -- " + d + " -- cycle;");
}
}
}
}
}
System.out.println("\\end{tikzpicture}");
System.out.println("\\end{center}");
}
}
private void search(final Point[] grid, final int k) {
if (mCurrentPoints.size() == mN) {
final long cnt = countSquares(mCurrentPoints);
if (cnt > mBestCount) {
mBestCount = cnt;
mBestPoints = new HashSet<>(mCurrentPoints);
}
return;
}
if (k < grid.length) {
mCurrentPoints.add(grid[k]);
search(grid, k + 1);
mCurrentPoints.remove(grid[k]);
search(grid, k + 1);
}
}
@Override
public Z next() {
++mN;
mBestCount = 0;
mBestPoints = null;
final int s = (int) Math.ceil(Math.sqrt(mN));
final Point[] grid = new Point[(s + 1) * (s + 1)];
for (int z = 0, y = 0; y <= s; ++y) {
for (int x = 0; x <= s; ++x, ++z) {
grid[z] = new Point(x, y);
}
}
search(grid, 0);
if (mVerbose) {
tikz(mBestPoints);
}
return Z.valueOf(mBestCount);
}
}