# Project Euler 253
# Expected maximum number of pieces when randomly clearing a row of 40.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
# Represent state as sorted list of segment lengths in a fixed buffer of 40 i8s + length.
# Memo: open addressing hash map key = state bytes + best, value = f64.
function pack_key(seg: ptr<i8>, nseg: i32, best: i32, out: ptr<i8>) -> void {
for i in 0..nseg {
out[i] = seg[i]
}
for i in nseg..40 {
out[i] = 0
}
out[40] = best as i8
}
function hash_key(key: ptr<i8>) -> i64 {
let mut h: i64 = 1469598103934665603
for i in 0..41 {
h = h ^ (key[i] as i64)
h = h * 1099511628211
}
if h < 0 { h = -h }
return h
}
function sort_segs(seg: ptr<i8>, n: i32) -> void {
for i in 1..n {
let key: i8 = seg[i]
let mut j: i32 = i - 1
while j >= 0 && (seg[j] as i32) > (key as i32) {
seg[j + 1] = seg[j]
j = j - 1
}
seg[j + 1] = key
}
}
# Global-ish via pointers passed around
function expected(seg: ptr<i8>, nseg: i32, best: i32, keys: ptr<i8>, vals: ptr<f64>, used: ptr<i8>, cap: i64) -> f64 {
if nseg == 0 {
return best as f64
}
let key: ptr<i8> = calloc(41, 1)
pack_key(seg, nseg, best, key)
let h0: i64 = hash_key(key) % cap
let mut slot: i64 = h0
while used[slot] == 1 {
let mut same: bool = true
let mut i: i32 = 0
while i < 41 {
if keys[slot * 41 + i] != key[i] { same = false; break }
i = i + 1
}
if same {
let v: f64 = vals[slot]
free(key)
return v
}
slot = slot + 1
if slot == cap { slot = 0 }
}
# compute
let mut remaining: i32 = 0
for i in 0..nseg {
remaining = remaining + (seg[i] as i32)
}
let mut total: f64 = 0.0
let mut i: i32 = 0
while i < nseg {
let seg_len: i32 = seg[i] as i32
let mut j: i32 = i + 1
while j < nseg && (seg[j] as i32) == seg_len {
j = j + 1
}
let count: i32 = j - i
# build base = state without one copy of seg_len at i
let base: ptr<i8> = calloc(40, 1)
let mut bn: i32 = 0
for k in 0..nseg {
if k != i {
base[bn] = seg[k]
bn = bn + 1
}
}
if seg_len == 1 {
let nb: i32 = best
let mut nn: i32 = bn
# next state is base
let nxt: ptr<i8> = calloc(40, 1)
for k in 0..bn { nxt[k] = base[k] }
let nbest: i32 = nb
if nn > nbest { nbest = nn }
total = total + (count as f64) * expected(nxt, nn, nbest, keys, vals, used, cap)
free(nxt)
} else {
# case: shrink to seg_len-1
let nxt: ptr<i8> = calloc(40, 1)
for k in 0..bn { nxt[k] = base[k] }
nxt[bn] = (seg_len - 1) as i8
let nn: i32 = bn + 1
sort_segs(nxt, nn)
let nbest: i32 = best
if nn > nbest { nbest = nn }
total = total + (2.0 * (count as f64)) * expected(nxt, nn, nbest, keys, vals, used, cap)
free(nxt)
# splits
let rest: i32 = seg_len - 1
for left in 1..(rest / 2 + 1) {
let right: i32 = rest - left
let mult: f64 = 2.0
if left == right { mult = 1.0 }
let nxt2: ptr<i8> = calloc(40, 1)
for k in 0..bn { nxt2[k] = base[k] }
nxt2[bn] = left as i8
nxt2[bn + 1] = right as i8
let nn2: i32 = bn + 2
sort_segs(nxt2, nn2)
let nbest2: i32 = best
if nn2 > nbest2 { nbest2 = nn2 }
total = total + (mult * (count as f64)) * expected(nxt2, nn2, nbest2, keys, vals, used, cap)
free(nxt2)
}
}
free(base)
i = j
}
let result: f64 = total / (remaining as f64)
# insert
used[slot] = 1
for i in 0..41 {
keys[slot * 41 + i] = key[i]
}
vals[slot] = result
free(key)
return result
}
function main() -> i32 {
let CAP: i64 = 2000003
let keys: ptr<i8> = calloc(CAP * 41, 1)
let vals: ptr<f64> = calloc(CAP, 8)
let used: ptr<i8> = calloc(CAP, 1)
let seg: ptr<i8> = calloc(40, 1)
seg[0] = 40
let ans: f64 = expected(seg, 1, 1, keys, vals, used, CAP)
printf("%.6f\n", ans)
free(keys); free(vals); free(used); free(seg)
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; }
void pack_key_ptr_i8_i32_i32_ptr_i8(int8_t* seg, int32_t nseg, int32_t best, int8_t* out);
int64_t hash_key_ptr_i8(int8_t* key);
void sort_segs_ptr_i8_i32(int8_t* seg, int32_t n);
double expected_ptr_i8_i32_i32_ptr_i8_ptr_f64_ptr_i8_i64(int8_t* seg, int32_t nseg, int32_t best, int8_t* keys, double* vals, int8_t* used, int64_t cap);
int32_t main(void);
void pack_key_ptr_i8_i32_i32_ptr_i8(int8_t* seg, int32_t nseg, int32_t best, int8_t* out) {
int32_t __flow_step_1 = 1;
for (int32_t i = 0; (0 <= nseg) ? i < nseg : i > nseg; i += (0 <= nseg) ? 1 : -1) {
out[i] = seg[i];
}
int32_t __flow_step_2 = 1;
for (int32_t i = nseg; (nseg <= 40) ? i < 40 : i > 40; i += (nseg <= 40) ? 1 : -1) {
out[i] = 0;
}
out[40] = ((int8_t)(best));
}
int64_t hash_key_ptr_i8(int8_t* key) {
int64_t h = 1469598103934665603;
int32_t __flow_step_3 = 1;
for (int32_t i = 0; (0 <= 41) ? i < 41 : i > 41; i += (0 <= 41) ? 1 : -1) {
h = (h ^ ((int64_t)(key[i])));
h = (h * 1099511628211);
}
if (h < 0) {
h = (-h);
}
return h;
}
void sort_segs_ptr_i8_i32(int8_t* seg, int32_t n) {
int32_t __flow_step_4 = 1;
for (int32_t i = 1; (1 <= n) ? i < n : i > n; i += (1 <= n) ? 1 : -1) {
int8_t key = seg[i];
int32_t j = (i - 1);
while ((j >= 0 && ((int32_t)(seg[j])) > ((int32_t)(key)))) {
seg[(j + 1)] = seg[j];
j = (j - 1);
}
seg[(j + 1)] = key;
}
}
double expected_ptr_i8_i32_i32_ptr_i8_ptr_f64_ptr_i8_i64(int8_t* seg, int32_t nseg, int32_t best, int8_t* keys, double* vals, int8_t* used, int64_t cap) {
if (nseg == 0) {
return ((double)(best));
}
int8_t* key = (int8_t*)(calloc(41, 1));
pack_key_ptr_i8_i32_i32_ptr_i8(seg, nseg, best, key);
int64_t h0 = FLOW_CHECKED_MOD((hash_key_ptr_i8(key)), (cap));
int64_t slot = h0;
while (used[slot] == 1) {
bool same = 1;
int32_t i = 0;
while (i < 41) {
if (keys[((slot * 41) + i)] != key[i]) {
same = 0;
break;
}
i = (i + 1);
}
if (same) {
double v = vals[slot];
free(key);
return v;
}
slot = (slot + 1);
if (slot == cap) {
slot = 0;
}
}
int32_t remaining = 0;
int32_t __flow_step_5 = 1;
for (int32_t i = 0; (0 <= nseg) ? i < nseg : i > nseg; i += (0 <= nseg) ? 1 : -1) {
remaining = (remaining + ((int32_t)(seg[i])));
}
double total = 0.0;
int32_t i = 0;
while (i < nseg) {
int32_t seg_len = ((int32_t)(seg[i]));
int32_t j = (i + 1);
while ((j < nseg && ((int32_t)(seg[j])) == seg_len)) {
j = (j + 1);
}
int32_t count = (j - i);
int8_t* base = (int8_t*)(calloc(40, 1));
int32_t bn = 0;
int32_t __flow_step_6 = 1;
for (int32_t k = 0; (0 <= nseg) ? k < nseg : k > nseg; k += (0 <= nseg) ? 1 : -1) {
if (k != i) {
base[bn] = seg[k];
bn = (bn + 1);
}
}
if (seg_len == 1) {
int32_t nb = best;
int32_t nn = bn;
int8_t* nxt = (int8_t*)(calloc(40, 1));
int32_t __flow_step_7 = 1;
for (int32_t k = 0; (0 <= bn) ? k < bn : k > bn; k += (0 <= bn) ? 1 : -1) {
nxt[k] = base[k];
}
int32_t nbest = nb;
if (nn > nbest) {
nbest = nn;
}
total = (total + (((double)(count)) * expected_ptr_i8_i32_i32_ptr_i8_ptr_f64_ptr_i8_i64(nxt, nn, nbest, keys, vals, used, cap)));
free(nxt);
} else {
int8_t* nxt = (int8_t*)(calloc(40, 1));
int32_t __flow_step_8 = 1;
for (int32_t k = 0; (0 <= bn) ? k < bn : k > bn; k += (0 <= bn) ? 1 : -1) {
nxt[k] = base[k];
}
nxt[bn] = ((int8_t)((seg_len - 1)));
int32_t nn = (bn + 1);
sort_segs_ptr_i8_i32(nxt, nn);
int32_t nbest = best;
if (nn > nbest) {
nbest = nn;
}
total = (total + ((2.0 * ((double)(count))) * expected_ptr_i8_i32_i32_ptr_i8_ptr_f64_ptr_i8_i64(nxt, nn, nbest, keys, vals, used, cap)));
free(nxt);
int32_t rest = (seg_len - 1);
int32_t __flow_step_9 = 1;
for (int32_t left = 1; (1 <= (FLOW_CHECKED_DIV((rest), (2)) + 1)) ? left < (FLOW_CHECKED_DIV((rest), (2)) + 1) : left > (FLOW_CHECKED_DIV((rest), (2)) + 1); left += (1 <= (FLOW_CHECKED_DIV((rest), (2)) + 1)) ? 1 : -1) {
int32_t right = (rest - left);
double mult = 2.0;
if (left == right) {
mult = 1.0;
}
int8_t* nxt2 = (int8_t*)(calloc(40, 1));
int32_t __flow_step_10 = 1;
for (int32_t k = 0; (0 <= bn) ? k < bn : k > bn; k += (0 <= bn) ? 1 : -1) {
nxt2[k] = base[k];
}
nxt2[bn] = ((int8_t)(left));
nxt2[(bn + 1)] = ((int8_t)(right));
int32_t nn2 = (bn + 2);
sort_segs_ptr_i8_i32(nxt2, nn2);
int32_t nbest2 = best;
if (nn2 > nbest2) {
nbest2 = nn2;
}
total = (total + ((mult * ((double)(count))) * expected_ptr_i8_i32_i32_ptr_i8_ptr_f64_ptr_i8_i64(nxt2, nn2, nbest2, keys, vals, used, cap)));
free(nxt2);
}
}
free(base);
i = j;
}
double result = (total / ((double)(remaining)));
used[slot] = 1;
int32_t __flow_step_11 = 1;
for (int32_t i = 0; (0 <= 41) ? i < 41 : i > 41; i += (0 <= 41) ? 1 : -1) {
keys[((slot * 41) + i)] = key[i];
}
vals[slot] = result;
free(key);
return result;
}
int32_t main(void) {
int64_t CAP = 2000003;
int8_t* keys = (int8_t*)(calloc((CAP * 41), 1));
double* vals = (double*)(calloc(CAP, 8));
int8_t* used = (int8_t*)(calloc(CAP, 1));
int8_t* seg = (int8_t*)(calloc(40, 1));
seg[0] = 40;
double ans = expected_ptr_i8_i32_i32_ptr_i8_ptr_f64_ptr_i8_i64(seg, 1, 1, keys, vals, used, CAP);
printf("%.6f\n", ans);
free(keys);
free(vals);
free(used);
free(seg);
return 0;
}