-
Notifications
You must be signed in to change notification settings - Fork 6
/
A006782.java
65 lines (57 loc) · 1.39 KB
/
A006782.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
package irvine.oeis.a006;
import java.util.HashSet;
import irvine.math.z.Z;
import irvine.oeis.Sequence1;
import irvine.util.Point;
/**
* A006782 Number of polygons of length 4n on L-lattice.
* @author Sean A. Irvine
*/
public class A006782 extends Sequence1 {
// L-lattice is infinite plane like this
//
// | ^ | ^ |
// V | V | V
// .-->.<--.-->.<--.
// ^ | ^ | ^
// | V | V |
// .<--.-->.<--.-->.
private int mN = 0;
private long mCount = 0;
private final HashSet<Point> mUsed = new HashSet<>();
private void search(final int x, final int y, final int remaining) {
if (remaining == 0) {
if (x == 0 && y == 0) {
++mCount;
}
return;
}
if (y < 0 || (y == 0 && x < 0)) {
// Origin is not leftmost topmost
return;
}
if (x + y > remaining) {
// Cannot possibly make it back to origin in remaining moves (A*)
return;
}
final Point p = new Point(x, y);
if (mUsed.add(p)) {
if (((x + y) & 1) == 0) {
search(x, y + 1, remaining - 1);
search(x, y - 1, remaining - 1);
} else {
search(x + 1, y, remaining - 1);
search(x - 1, y, remaining - 1);
}
mUsed.remove(p);
}
}
@Override
public Z next() {
mN += 4;
mCount = 0;
mUsed.add(new Point(0, 0));
search(0, 1, mN - 1);
return Z.valueOf(mCount);
}
}