# Project Euler 782
# Distinct Rows and Columns -- C(10^4).
# Pure Flow port of the native C helper. qsort is replaced by a heapsort.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function malloc(n: i64) -> ptr<void>
}
# Count k in [0..n^2] achievable with complexity <= 3.
function count_le_3(n: i32) -> i64 {
let n2: i64 = (n as i64) * (n as i64)
let half: i64 = n2 / 2
let seen: ptr<i8> = calloc(half + 1, 1)
# Orbit 1: k = x*y, 0 <= x <= y <= n.
let mut y: i32 = 1
while y <= n {
let mut x: i32 = 0
while x <= y {
let mut k: i64 = (x as i64) * (y as i64)
if k > half {
k = n2 - k
}
seen[k] = 1
x = x + 1
}
y = y + 1
}
seen[0] = 1
# Orbit 2: k = v^2 - d^2, 0 <= d <= v <= n.
let mut v: i32 = 0
while v <= n {
let vv: i64 = (v as i64) * (v as i64)
let mut d: i32 = 0
while d <= v {
let mut k: i64 = vv - (d as i64) * (d as i64)
if k > half {
k = n2 - k
}
if k >= 0 && k <= half {
seen[k] = 1
}
d = d + 1
}
v = v + 1
}
# q[b] = 2*b*(n-b) for b = 0..floor(n/2).
let bmax_global: i32 = n / 2
let q: ptr<i64> = malloc(((bmax_global + 1) as i64) * 8)
let mut cur: i64 = 0
let mut delta: i64 = 2 * ((n - 1) as i64)
let mut b: i32 = 0
while b < bmax_global {
q[b] = cur
cur = cur + delta
delta = delta - 4
b = b + 1
}
q[bmax_global] = cur
# Orbits 3/4/5/6: depend on s = a+b and ab = a(s-a).
let mut s: i32 = 0
while s <= n {
let c: i32 = n - s
let c2: i64 = (c as i64) * (c as i64)
let c2n: i64 = (c as i64) * (2 * (n as i64) - (c as i64))
let cs: i64 = (c as i64) * (s as i64)
if s % 2 == 0 {
let v2: i32 = s / 2
let base: i64 = (v2 as i64) * (v2 as i64)
let mut d: i32 = 0
while d <= v2 {
let ab: i64 = base - (d as i64) * (d as i64)
let two_ab: i64 = ab << 1
let mut k: i64 = c2 + two_ab
if k > half { k = n2 - k }
seen[k] = 1
k = c2n + two_ab
if k > half { k = n2 - k }
seen[k] = 1
k = cs + ab
if k > half { k = n2 - k }
seen[k] = 1
k = (cs + ab) << 1
if k > half { k = n2 - k }
seen[k] = 1
d = d + 1
}
} else {
let v2: i32 = s / 2
let base: i64 = (v2 as i64) * ((v2 + 1) as i64)
let mut pr: i64 = 0
let mut step: i64 = 2
let mut d: i32 = 0
while d <= v2 {
let ab: i64 = base - pr
let two_ab: i64 = ab << 1
let mut k: i64 = c2 + two_ab
if k > half { k = n2 - k }
seen[k] = 1
k = c2n + two_ab
if k > half { k = n2 - k }
seen[k] = 1
k = cs + ab
if k > half { k = n2 - k }
seen[k] = 1
k = (cs + ab) << 1
if k > half { k = n2 - k }
seen[k] = 1
pr = pr + step
step = step + 2
d = d + 1
}
}
s = s + 1
}
# Orbit 7: k = c^2 + 2*b*(n-b), 0 <= b <= min(n-c, n/2).
let mut c: i32 = 0
while c <= n {
let c2: i64 = (c as i64) * (c as i64)
let mut bmax: i32 = n - c
if bmax > bmax_global {
bmax = bmax_global
}
let mut b: i32 = 0
while b <= bmax {
let mut k: i64 = c2 + q[b]
if k > half { k = n2 - k }
seen[k] = 1
b = b + 1
}
c = c + 1
}
let mut cnt: i64 = 0
let mut i: i64 = 0
while i <= half {
cnt = cnt + (seen[i] as i64)
i = i + 1
}
let mut result: i64 = 2 * cnt
if n2 % 2 == 0 {
result = 2 * cnt - (seen[half] as i64)
}
free(seen)
free(q)
return result
}
# Heapsort on ptr<i64> of length m.
function sift_down(a: ptr<i64>, start: i32, end: i32) {
let mut root: i32 = start
while 2 * root + 1 <= end {
let mut child: i32 = 2 * root + 1
if child + 1 <= end {
if a[child + 1] > a[child] {
child = child + 1
}
}
if a[child] > a[root] {
let tmp: i64 = a[root]
a[root] = a[child]
a[child] = tmp
root = child
} else {
return
}
}
}
function heapsort_i64(a: ptr<i64>, m: i32) {
let mut start: i32 = (m - 2) / 2
while start >= 0 {
sift_down(a, start, m - 1)
start = start - 1
}
let mut end: i32 = m - 1
while end > 0 {
let tmp: i64 = a[0]
a[0] = a[end]
a[end] = tmp
end = end - 1
sift_down(a, 0, end)
}
}
# Count k in [0..n^2] whose minimum complexity is exactly 2.
function count_eq_2(n: i32) -> i64 {
let n2: i64 = (n as i64) * (n as i64)
let vals: ptr<i64> = malloc((4 * ((n + 1) as i64)) * 8)
let mut m: i32 = 0
let mut a: i32 = 0
while a <= n {
let a2: i64 = (a as i64) * (a as i64)
let t: i64 = 2 * (a as i64) * ((n - a) as i64)
vals[m] = a2
m = m + 1
vals[m] = n2 - a2
m = m + 1
vals[m] = t
m = m + 1
vals[m] = n2 - t
m = m + 1
a = a + 1
}
heapsort_i64(vals, m)
let mut cnt: i64 = 0
let mut i: i32 = 0
while i < m {
if vals[i] == 0 || vals[i] == n2 {
i = i + 1
} else {
if i == 0 || vals[i] != vals[i - 1] {
cnt = cnt + 1
}
i = i + 1
}
}
free(vals)
return cnt
}
function main() -> i32 {
let n: i32 = 10000
let n2: i64 = (n as i64) * (n as i64)
let total: i64 = n2 + 1
let s3: i64 = count_le_3(n)
let n4: i64 = total - s3
let n2cnt: i64 = count_eq_2(n)
printf("%lld\n", 3 * total - 4 - n2cnt + n4)
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 count_le_3_i32(int32_t n);
void sift_down_ptr_i64_i32_i32(int64_t* a, int32_t start, int32_t end);
void heapsort_i64_ptr_i64_i32(int64_t* a, int32_t m);
int64_t count_eq_2_i32(int32_t n);
int32_t main(void);
int64_t count_le_3_i32(int32_t n) {
int64_t n2 = (((int64_t)(n)) * ((int64_t)(n)));
int64_t half = FLOW_CHECKED_DIV((n2), (2));
int8_t* seen = (int8_t*)(calloc((half + 1), 1));
int32_t y = 1;
while (y <= n) {
int32_t x = 0;
while (x <= y) {
int64_t k = (((int64_t)(x)) * ((int64_t)(y)));
if (k > half) {
k = (n2 - k);
}
seen[k] = 1;
x = (x + 1);
}
y = (y + 1);
}
seen[0] = 1;
int32_t v = 0;
while (v <= n) {
int64_t vv = (((int64_t)(v)) * ((int64_t)(v)));
int32_t d = 0;
while (d <= v) {
int64_t k = (vv - (((int64_t)(d)) * ((int64_t)(d))));
if (k > half) {
k = (n2 - k);
}
if ((k >= 0 && k <= half)) {
seen[k] = 1;
}
d = (d + 1);
}
v = (v + 1);
}
int32_t bmax_global = FLOW_CHECKED_DIV((n), (2));
int64_t* q = (int64_t*)(malloc((((int64_t)((bmax_global + 1))) * 8)));
int64_t cur = 0;
int64_t delta = (2 * ((int64_t)((n - 1))));
int32_t b = 0;
while (b < bmax_global) {
q[b] = cur;
cur = (cur + delta);
delta = (delta - 4);
b = (b + 1);
}
q[bmax_global] = cur;
int32_t s = 0;
while (s <= n) {
int32_t c = (n - s);
int64_t c2 = (((int64_t)(c)) * ((int64_t)(c)));
int64_t c2n = (((int64_t)(c)) * ((2 * ((int64_t)(n))) - ((int64_t)(c))));
int64_t cs = (((int64_t)(c)) * ((int64_t)(s)));
if (FLOW_CHECKED_MOD((s), (2)) == 0) {
int32_t v2 = FLOW_CHECKED_DIV((s), (2));
int64_t base = (((int64_t)(v2)) * ((int64_t)(v2)));
int32_t d = 0;
while (d <= v2) {
int64_t ab = (base - (((int64_t)(d)) * ((int64_t)(d))));
int64_t two_ab = FLOW_CHECKED_SHL((ab), (1));
int64_t k = (c2 + two_ab);
if (k > half) {
k = (n2 - k);
}
seen[k] = 1;
k = (c2n + two_ab);
if (k > half) {
k = (n2 - k);
}
seen[k] = 1;
k = (cs + ab);
if (k > half) {
k = (n2 - k);
}
seen[k] = 1;
k = FLOW_CHECKED_SHL(((cs + ab)), (1));
if (k > half) {
k = (n2 - k);
}
seen[k] = 1;
d = (d + 1);
}
} else {
int32_t v2 = FLOW_CHECKED_DIV((s), (2));
int64_t base = (((int64_t)(v2)) * ((int64_t)((v2 + 1))));
int64_t pr = 0;
int64_t step = 2;
int32_t d = 0;
while (d <= v2) {
int64_t ab = (base - pr);
int64_t two_ab = FLOW_CHECKED_SHL((ab), (1));
int64_t k = (c2 + two_ab);
if (k > half) {
k = (n2 - k);
}
seen[k] = 1;
k = (c2n + two_ab);
if (k > half) {
k = (n2 - k);
}
seen[k] = 1;
k = (cs + ab);
if (k > half) {
k = (n2 - k);
}
seen[k] = 1;
k = FLOW_CHECKED_SHL(((cs + ab)), (1));
if (k > half) {
k = (n2 - k);
}
seen[k] = 1;
pr = (pr + step);
step = (step + 2);
d = (d + 1);
}
}
s = (s + 1);
}
int32_t c = 0;
while (c <= n) {
int64_t c2 = (((int64_t)(c)) * ((int64_t)(c)));
int32_t bmax = (n - c);
if (bmax > bmax_global) {
bmax = bmax_global;
}
int32_t b = 0;
while (b <= bmax) {
int64_t k = (c2 + q[b]);
if (k > half) {
k = (n2 - k);
}
seen[k] = 1;
b = (b + 1);
}
c = (c + 1);
}
int64_t cnt = 0;
int64_t i = 0;
while (i <= half) {
cnt = (cnt + ((int64_t)(seen[i])));
i = (i + 1);
}
int64_t result = (2 * cnt);
if (FLOW_CHECKED_MOD((n2), (2)) == 0) {
result = ((2 * cnt) - ((int64_t)(seen[half])));
}
free(seen);
free(q);
return result;
}
void sift_down_ptr_i64_i32_i32(int64_t* a, int32_t start, int32_t end) {
int32_t root = start;
while (((2 * root) + 1) <= end) {
int32_t child = ((2 * root) + 1);
if ((child + 1) <= end) {
if (a[(child + 1)] > a[child]) {
child = (child + 1);
}
}
if (a[child] > a[root]) {
int64_t tmp = a[root];
a[root] = a[child];
a[child] = tmp;
root = child;
} else {
return;
}
}
}
void heapsort_i64_ptr_i64_i32(int64_t* a, int32_t m) {
int32_t start = FLOW_CHECKED_DIV(((m - 2)), (2));
while (start >= 0) {
sift_down_ptr_i64_i32_i32(a, start, (m - 1));
start = (start - 1);
}
int32_t end = (m - 1);
while (end > 0) {
int64_t tmp = a[0];
a[0] = a[end];
a[end] = tmp;
end = (end - 1);
sift_down_ptr_i64_i32_i32(a, 0, end);
}
}
int64_t count_eq_2_i32(int32_t n) {
int64_t n2 = (((int64_t)(n)) * ((int64_t)(n)));
int64_t* vals = (int64_t*)(malloc(((4 * ((int64_t)((n + 1)))) * 8)));
int32_t m = 0;
int32_t a = 0;
while (a <= n) {
int64_t a2 = (((int64_t)(a)) * ((int64_t)(a)));
int64_t t = ((2 * ((int64_t)(a))) * ((int64_t)((n - a))));
vals[m] = a2;
m = (m + 1);
vals[m] = (n2 - a2);
m = (m + 1);
vals[m] = t;
m = (m + 1);
vals[m] = (n2 - t);
m = (m + 1);
a = (a + 1);
}
heapsort_i64_ptr_i64_i32(vals, m);
int64_t cnt = 0;
int32_t i = 0;
while (i < m) {
if ((vals[i] == 0 || vals[i] == n2)) {
i = (i + 1);
} else {
if ((i == 0 || vals[i] != vals[(i - 1)])) {
cnt = (cnt + 1);
}
i = (i + 1);
}
}
free(vals);
return cnt;
}
int32_t main(void) {
int32_t n = 10000;
int64_t n2 = (((int64_t)(n)) * ((int64_t)(n)));
int64_t total = (n2 + 1);
int64_t s3 = count_le_3_i32(n);
int64_t n4 = (total - s3);
int64_t n2cnt = count_eq_2_i32(n);
printf("%lld\n", ((((3 * total) - 4) - n2cnt) + n4));
return 0;
}