# Project Euler 459
# Flipping Cards — tartan theorem + 1D Grundy prefixes + nim-product matching.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const N: i64 = 1000000
const M: i64 = 1024
const MEMO_CAP: i64 = 2097152
let mut G_mk1: ptr<i64> = null
let mut G_mk2: ptr<i64> = null
let mut G_mv: ptr<i64> = null
let mut G_mu: ptr<i8> = null
function memo_get(a: i64, b: i64) -> i64 {
# returns -1 if miss
let mut h: i64 = (a * 1315423911 + b) % MEMO_CAP
if h < 0 { h = h + MEMO_CAP }
while G_mu[h] != 0 {
if G_mk1[h] == a && G_mk2[h] == b {
return G_mv[h]
}
h = h + 1
if h == MEMO_CAP { h = 0 }
}
return -1
}
function memo_put(a: i64, b: i64, v: i64) -> void {
let mut h: i64 = (a * 1315423911 + b) % MEMO_CAP
if h < 0 { h = h + MEMO_CAP }
while G_mu[h] != 0 {
if G_mk1[h] == a && G_mk2[h] == b {
G_mv[h] = v
return
}
h = h + 1
if h == MEMO_CAP { h = 0 }
}
G_mu[h] = 1
G_mk1[h] = a
G_mk2[h] = b
G_mv[h] = v
}
function fermat(i: i64) -> i64 {
# F_i = 2^(2^i)
return 1 << (1 << i)
}
function fermat_index(x: i64) -> i64 {
let mut i: i64 = 0
while i + 1 < 7 && fermat(i + 1) <= x {
i = i + 1
}
return i
}
function nim_mul(a0: i64, b0: i64) -> i64 {
let mut a: i64 = a0
let mut b: i64 = b0
if a == 0 || b == 0 { return 0 }
if a == 1 { return b }
if b == 1 { return a }
if a < b {
let t: i64 = a
a = b
b = t
}
let cached: i64 = memo_get(a, b)
if cached >= 0 { return cached }
let m: i64 = fermat_index(a)
let n: i64 = fermat_index(b)
let mut r: i64 = 0
if m != n {
if m > n {
let Fm: i64 = fermat(m)
let shift: i64 = 1 << m
let a1: i64 = a / Fm
let a2: i64 = a % Fm
r = (nim_mul(a1, b) << shift) ^ nim_mul(a2, b)
} else {
let Fn: i64 = fermat(n)
let shift: i64 = 1 << n
let b1: i64 = b / Fn
let b2: i64 = b % Fn
r = (nim_mul(a, b1) << shift) ^ nim_mul(a, b2)
}
} else {
let Fn: i64 = fermat(n)
let shift: i64 = 1 << n
let a1: i64 = a / Fn
let a2: i64 = a % Fn
let b1: i64 = b / Fn
let b2: i64 = b % Fn
let p1: i64 = nim_mul(a1, b1)
let p2: i64 = nim_mul(a2, b2)
let p3: i64 = nim_mul(a1 ^ a2, b1 ^ b2)
let p4: i64 = nim_mul(p1, Fn / 2)
let p5: i64 = p3 ^ p2
r = (p5 << shift) ^ p2 ^ p4
}
memo_put(a, b, r)
return r
}
function nim_pow(a0: i64, e0: i64) -> i64 {
let mut res: i64 = 1
let mut base: i64 = a0
let mut e: i64 = e0
while e > 0 {
if (e & 1) == 1 {
res = nim_mul(res, base)
}
e = e / 2
if e > 0 {
base = nim_mul(base, base)
}
}
return res
}
function nim_inv(a: i64) -> i64 {
return nim_pow(a, 65534)
}
function compute_1d(n: i64, L: ptr<i64>, Llen: i64, freq: ptr<i64>) -> i64 {
# returns C[n]; fills freq[0..M)
let C: ptr<i32> = calloc(n + 1, 4)
let mark: ptr<i32> = calloc(M, 4)
let cnt: ptr<i32> = calloc(M, 4)
let touched: ptr<i32> = calloc(M, 4)
if C == null || mark == null || cnt == null || touched == null { return 0 }
let mut mi: i64 = 0
let mut x: i64 = 1
while x <= n {
while mi < Llen && L[mi] <= x {
mi = mi + 1
}
let cx_prev: i64 = C[x - 1] as i64
let mut tlen: i64 = 0
let mut j: i64 = 0
while j < mi {
let v: i64 = cx_prev ^ (C[x - L[j]] as i64)
if (mark[v] as i64) != x {
mark[v] = x as i32
cnt[v] = 1
touched[tlen] = v as i32
tlen = tlen + 1
} else {
cnt[v] = cnt[v] + 1
}
j = j + 1
}
let mut t: i64 = 0
while (mark[t] as i64) == x {
t = t + 1
}
let cx: i64 = cx_prev ^ t
C[x] = cx as i32
let mut i2: i64 = 0
while i2 < tlen {
let v2: i64 = touched[i2] as i64
freq[v2 ^ t] = freq[v2 ^ t] + (cnt[v2] as i64)
i2 = i2 + 1
}
x = x + 1
}
let cn: i64 = C[n] as i64
free(touched)
free(cnt)
free(mark)
free(C)
return cn
}
function main() -> i32 {
G_mk1 = calloc(MEMO_CAP, 8)
G_mk2 = calloc(MEMO_CAP, 8)
G_mv = calloc(MEMO_CAP, 8)
G_mu = calloc(MEMO_CAP, 1)
let squares: ptr<i64> = calloc(1024, 8)
let tris: ptr<i64> = calloc(2048, 8)
let freq_sq: ptr<i64> = calloc(M, 8)
let freq_tr: ptr<i64> = calloc(M, 8)
if G_mk1 == null || G_mk2 == null || G_mv == null || G_mu == null { return 1 }
if squares == null || tris == null || freq_sq == null || freq_tr == null { return 1 }
let mut ns: i64 = 0
let mut k: i64 = 1
while k * k <= N {
squares[ns] = k * k
ns = ns + 1
k = k + 1
}
let mut nt: i64 = 0
k = 1
while true {
let t: i64 = k * (k + 1) / 2
if t > N { break }
tris[nt] = t
nt = nt + 1
k = k + 1
}
let Csq: i64 = compute_1d(N, squares, ns, freq_sq)
let Ctr: i64 = compute_1d(N, tris, nt, freq_tr)
let board: i64 = nim_mul(Csq, Ctr)
let mut sum_sq: i64 = 0
let mut sum_tr: i64 = 0
let mut a: i64 = 0
while a < M {
sum_sq = sum_sq + freq_sq[a]
sum_tr = sum_tr + freq_tr[a]
a = a + 1
}
let mut total: i64 = 0
if board == 0 {
let a0: i64 = freq_sq[0]
let b0: i64 = freq_tr[0]
total = a0 * sum_tr + (sum_sq - a0) * b0
} else {
a = 1
while a < M {
let fa: i64 = freq_sq[a]
if fa != 0 {
let inva: i64 = nim_inv(a)
let b: i64 = nim_mul(board, inva)
if b < M {
total = total + fa * freq_tr[b]
}
}
a = a + 1
}
}
printf("%lld\n", total)
free(freq_tr)
free(freq_sq)
free(tris)
free(squares)
free(G_mu)
free(G_mv)
free(G_mk2)
free(G_mk1)
return 0
}
Generated C
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
while (flow_temp_head) {
flow_temp_node* n = flow_temp_head;
flow_temp_head = n->next;
free(n);
}
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
if (!node) return NULL;
node->next = flow_temp_head;
flow_temp_head = node;
if (!flow_temp_atexit_set) {
flow_temp_atexit_set = 1;
atexit(flow_temp_free_all);
}
return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
char* r = (char*)flow_temp_alloc(la + lb + 1);
if (!r) return NULL;
if (la) memcpy(r, a, la);
if (lb) memcpy(r + la, b, lb);
r[la + lb] = '\0';
return r;
}
#define __flow_in_arr(arr, val) __extension__ ({ \
int _found = 0; \
size_t _n = sizeof(arr)/sizeof((arr)[0]); \
for (size_t _i = 0; _i < _n; _i++) { \
if ((arr)[_i] == (val)) { _found = 1; break; } \
} _found; })
/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
abort();
#if defined(__GNUC__) || defined(__clang__)
__builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")
#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#include <math.h>
void* _ui_state = NULL;
static inline float i32_to_f32(int32_t v) { return (float)v; }
/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }
int64_t memo_get_i64_i64(int64_t a, int64_t b);
void memo_put_i64_i64_i64(int64_t a, int64_t b, int64_t v);
int64_t fermat_i64(int64_t i);
int64_t fermat_index_i64(int64_t x);
int64_t nim_mul_i64_i64(int64_t a0, int64_t b0);
int64_t nim_pow_i64_i64(int64_t a0, int64_t e0);
int64_t nim_inv_i64(int64_t a);
int64_t compute_1d_i64_ptr_i64_i64_ptr_i64(int64_t n, int64_t* L, int64_t Llen, int64_t* freq);
int32_t main(void);
static const int64_t N = 1000000;
static const int64_t M = 1024;
static const int64_t MEMO_CAP = 2097152;
/* Module statics */
static int64_t* G_mk1 = NULL;
static int64_t* G_mk2 = NULL;
static int64_t* G_mv = NULL;
static int8_t* G_mu = NULL;
int64_t memo_get_i64_i64(int64_t a, int64_t b) {
int64_t h = FLOW_CHECKED_MOD((((a * 1315423911) + b)), (MEMO_CAP));
if (h < 0) {
h = (h + MEMO_CAP);
}
while (G_mu[h] != 0) {
if ((G_mk1[h] == a && G_mk2[h] == b)) {
return G_mv[h];
}
h = (h + 1);
if (h == MEMO_CAP) {
h = 0;
}
}
return (-1);
}
void memo_put_i64_i64_i64(int64_t a, int64_t b, int64_t v) {
int64_t h = FLOW_CHECKED_MOD((((a * 1315423911) + b)), (MEMO_CAP));
if (h < 0) {
h = (h + MEMO_CAP);
}
while (G_mu[h] != 0) {
if ((G_mk1[h] == a && G_mk2[h] == b)) {
G_mv[h] = v;
return;
}
h = (h + 1);
if (h == MEMO_CAP) {
h = 0;
}
}
G_mu[h] = 1;
G_mk1[h] = a;
G_mk2[h] = b;
G_mv[h] = v;
}
int64_t fermat_i64(int64_t i) {
return FLOW_CHECKED_SHL((1), (FLOW_CHECKED_SHL((1), (i))));
}
int64_t fermat_index_i64(int64_t x) {
int64_t i = 0;
while (((i + 1) < 7 && fermat_i64((i + 1)) <= x)) {
i = (i + 1);
}
return i;
}
int64_t nim_mul_i64_i64(int64_t a0, int64_t b0) {
int64_t a = a0;
int64_t b = b0;
if ((a == 0 || b == 0)) {
return 0;
}
if (a == 1) {
return b;
}
if (b == 1) {
return a;
}
if (a < b) {
int64_t t = a;
a = b;
b = t;
}
int64_t cached = memo_get_i64_i64(a, b);
if (cached >= 0) {
return cached;
}
int64_t m = fermat_index_i64(a);
int64_t n = fermat_index_i64(b);
int64_t r = 0;
if (m != n) {
if (m > n) {
int64_t Fm = fermat_i64(m);
int64_t shift = FLOW_CHECKED_SHL((1), (m));
int64_t a1 = FLOW_CHECKED_DIV((a), (Fm));
int64_t a2 = FLOW_CHECKED_MOD((a), (Fm));
r = (FLOW_CHECKED_SHL((nim_mul_i64_i64(a1, b)), (shift)) ^ nim_mul_i64_i64(a2, b));
} else {
int64_t Fn = fermat_i64(n);
int64_t shift = FLOW_CHECKED_SHL((1), (n));
int64_t b1 = FLOW_CHECKED_DIV((b), (Fn));
int64_t b2 = FLOW_CHECKED_MOD((b), (Fn));
r = (FLOW_CHECKED_SHL((nim_mul_i64_i64(a, b1)), (shift)) ^ nim_mul_i64_i64(a, b2));
}
} else {
int64_t Fn = fermat_i64(n);
int64_t shift = FLOW_CHECKED_SHL((1), (n));
int64_t a1 = FLOW_CHECKED_DIV((a), (Fn));
int64_t a2 = FLOW_CHECKED_MOD((a), (Fn));
int64_t b1 = FLOW_CHECKED_DIV((b), (Fn));
int64_t b2 = FLOW_CHECKED_MOD((b), (Fn));
int64_t p1 = nim_mul_i64_i64(a1, b1);
int64_t p2 = nim_mul_i64_i64(a2, b2);
int64_t p3 = nim_mul_i64_i64((a1 ^ a2), (b1 ^ b2));
int64_t p4 = nim_mul_i64_i64(p1, FLOW_CHECKED_DIV((Fn), (2)));
int64_t p5 = (p3 ^ p2);
r = ((FLOW_CHECKED_SHL((p5), (shift)) ^ p2) ^ p4);
}
memo_put_i64_i64_i64(a, b, r);
return r;
}
int64_t nim_pow_i64_i64(int64_t a0, int64_t e0) {
int64_t res = 1;
int64_t base = a0;
int64_t e = e0;
while (e > 0) {
if ((e & 1) == 1) {
res = nim_mul_i64_i64(res, base);
}
e = FLOW_CHECKED_DIV((e), (2));
if (e > 0) {
base = nim_mul_i64_i64(base, base);
}
}
return res;
}
int64_t nim_inv_i64(int64_t a) {
return nim_pow_i64_i64(a, 65534);
}
int64_t compute_1d_i64_ptr_i64_i64_ptr_i64(int64_t n, int64_t* L, int64_t Llen, int64_t* freq) {
int32_t* C = (int32_t*)(calloc((n + 1), 4));
int32_t* mark = (int32_t*)(calloc(M, 4));
int32_t* cnt = (int32_t*)(calloc(M, 4));
int32_t* touched = (int32_t*)(calloc(M, 4));
if ((((C == NULL || mark == NULL) || cnt == NULL) || touched == NULL)) {
return 0;
}
int64_t mi = 0;
int64_t x = 1;
while (x <= n) {
while ((mi < Llen && L[mi] <= x)) {
mi = (mi + 1);
}
int64_t cx_prev = ((int64_t)(C[(x - 1)]));
int64_t tlen = 0;
int64_t j = 0;
while (j < mi) {
int64_t v = (cx_prev ^ ((int64_t)(C[(x - L[j])])));
if (((int64_t)(mark[v])) != x) {
mark[v] = ((int32_t)(x));
cnt[v] = 1;
touched[tlen] = ((int32_t)(v));
tlen = (tlen + 1);
} else {
cnt[v] = (cnt[v] + 1);
}
j = (j + 1);
}
int64_t t = 0;
while (((int64_t)(mark[t])) == x) {
t = (t + 1);
}
int64_t cx = (cx_prev ^ t);
C[x] = ((int32_t)(cx));
int64_t i2 = 0;
while (i2 < tlen) {
int64_t v2 = ((int64_t)(touched[i2]));
freq[(v2 ^ t)] = (freq[(v2 ^ t)] + ((int64_t)(cnt[v2])));
i2 = (i2 + 1);
}
x = (x + 1);
}
int64_t cn = ((int64_t)(C[n]));
free(touched);
free(cnt);
free(mark);
free(C);
return cn;
}
int32_t main(void) {
G_mk1 = calloc(MEMO_CAP, 8);
G_mk2 = calloc(MEMO_CAP, 8);
G_mv = calloc(MEMO_CAP, 8);
G_mu = calloc(MEMO_CAP, 1);
int64_t* squares = (int64_t*)(calloc(1024, 8));
int64_t* tris = (int64_t*)(calloc(2048, 8));
int64_t* freq_sq = (int64_t*)(calloc(M, 8));
int64_t* freq_tr = (int64_t*)(calloc(M, 8));
if ((((G_mk1 == NULL || G_mk2 == NULL) || G_mv == NULL) || G_mu == NULL)) {
return 1;
}
if ((((squares == NULL || tris == NULL) || freq_sq == NULL) || freq_tr == NULL)) {
return 1;
}
int64_t ns = 0;
int64_t k = 1;
while ((k * k) <= N) {
squares[ns] = (k * k);
ns = (ns + 1);
k = (k + 1);
}
int64_t nt = 0;
k = 1;
while (1) {
int64_t t = FLOW_CHECKED_DIV(((k * (k + 1))), (2));
if (t > N) {
break;
}
tris[nt] = t;
nt = (nt + 1);
k = (k + 1);
}
int64_t Csq = compute_1d_i64_ptr_i64_i64_ptr_i64(N, squares, ns, freq_sq);
int64_t Ctr = compute_1d_i64_ptr_i64_i64_ptr_i64(N, tris, nt, freq_tr);
int64_t board = nim_mul_i64_i64(Csq, Ctr);
int64_t sum_sq = 0;
int64_t sum_tr = 0;
int64_t a = 0;
while (a < M) {
sum_sq = (sum_sq + freq_sq[a]);
sum_tr = (sum_tr + freq_tr[a]);
a = (a + 1);
}
int64_t total = 0;
if (board == 0) {
int64_t a0 = freq_sq[0];
int64_t b0 = freq_tr[0];
total = ((a0 * sum_tr) + ((sum_sq - a0) * b0));
} else {
a = 1;
while (a < M) {
int64_t fa = freq_sq[a];
if (fa != 0) {
int64_t inva = nim_inv_i64(a);
int64_t b = nim_mul_i64_i64(board, inva);
if (b < M) {
total = (total + (fa * freq_tr[b]));
}
}
a = (a + 1);
}
}
printf("%lld\n", total);
free(freq_tr);
free(freq_sq);
free(tris);
free(squares);
free(G_mu);
free(G_mv);
free(G_mk2);
free(G_mk1);
return 0;
}