-
Notifications
You must be signed in to change notification settings - Fork 6
/
A336742.java
60 lines (53 loc) · 1.32 KB
/
A336742.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
package irvine.oeis.a336;
import java.util.HashSet;
import irvine.math.z.Z;
import irvine.oeis.Sequence0;
import irvine.util.Point;
/**
* A336742 Number of self-avoiding cycles of length 2n on the half-Manhattan lattice.
* @author Sean A. Irvine
*/
public class A336742 extends Sequence0 {
private int mN = -2;
private long mCount = 0;
private final HashSet<Point> mUsed = new HashSet<>();
private int d(final int z) {
return 1 - ((z & 1) << 1);
}
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 (Math.abs(x) + Math.abs(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)) {
search(x + d(y), y, remaining - 1);
search(x, y - 1, remaining - 1);
search(x, y + 1, remaining - 1);
mUsed.remove(p);
}
}
@Override
public Z next() {
mN += 2;
if (mN == 0) {
return Z.ONE;
}
mCount = 0;
mUsed.add(new Point(0, 0));
search(0, 1, mN - 1);
mCount *= 2; // for (0, -1)
search(1, 0, mN - 1);
return Z.valueOf(mCount);
}
}