# Project Euler 419 — Look and Say via Conway element-decay matrices mod 2^30.
# Ported from C++. Uses string manipulation and matrix exponentiation.
# Conway's cosmological theorem limits distinct elements to ~92.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>)
function printf(fmt: ptr<i8>, ...) -> i32
function strlen(s: ptr<i8>) -> i64
function strcmp(a: ptr<i8>, b: ptr<i8>) -> i32
function strcpy(dst: ptr<i8>, src: ptr<i8>) -> ptr<i8>
function strcat(dst: ptr<i8>, src: ptr<i8>) -> ptr<i8>
function memcpy(dst: ptr<void>, src: ptr<void>, n: i64) -> ptr<void>
}
const MOD_MASK: u32 = 1073741823
const MAX_ELEMS: i32 = 200
const MAX_ELEM_LEN: i32 = 128
const MAX_STR: i32 = 70000
const MAX_SPLIT: i32 = 10000
# String buffer for look-and-say generation
let mut g_buf1: ptr<i8> = null
let mut g_buf2: ptr<i8> = null
# Element table: flat MAX_ELEMS * MAX_ELEM_LEN bytes
let mut g_elems: ptr<i8> = null
let mut g_nelems: i32 = 0
function elem_ptr(i: i32) -> ptr<i8> {
return g_elems + ((i as i64) * (MAX_ELEM_LEN as i64))
}
function find_or_add(e: ptr<i8>) -> i32 {
let mut i: i32 = 0
while i < g_nelems {
if strcmp(elem_ptr(i), e) == 0 { return i }
i = i + 1
}
let j: i32 = g_nelems
g_nelems = g_nelems + 1
strcpy(elem_ptr(j), e)
return j
}
# Look-and-say: read input, write output to out
function say(input: ptr<i8>, out: ptr<i8>) -> void {
let n: i64 = strlen(input)
let mut i: i64 = 0
let mut op: i64 = 0
while i < n {
let ch: i8 = input[i]
let mut j: i64 = i + 1
while j < n && input[j] == ch { j = j + 1 }
let count: i64 = j - i
# Write count as decimal
let digits: ptr<i8> = calloc(20, 1)
let mut dc: i32 = 0
let mut c: i64 = count
if c == 0 {
digits[0] = 48
dc = 1
}
while c > 0 {
digits[dc] = ((c % 10) as i8) + 48
dc = dc + 1
c = c / 10
}
# Reverse digits into out
let mut d: i32 = dc - 1
while d >= 0 {
out[op] = digits[d]
op = op + 1
d = d - 1
}
free(digits as ptr<void>)
out[op] = ch
op = op + 1
i = j
}
out[op] = 0
}
# spl00_at: check if position j is a split point for the "00" sub-pattern
function spl00_at(s: ptr<i8>, j: i64) -> i32 {
let n: i64 = strlen(s)
if j + 2 < n && s[j] == 49 && s[j + 1] == 49 && s[j + 2] == 49 { return 1 }
if j == n - 1 && s[j] == 49 { return 0 }
if j + 1 < n && s[j] == 49 && s[j + 1] == 49 { return 0 }
if j + 2 < n && s[j] == 49 && s[j + 1] == 50 && s[j + 2] == 50 { return 0 }
if j + 2 < n && s[j] == 49 && s[j + 1] == 51 && s[j + 2] == 51 { return 0 }
if j < n && s[j] == 50 { return 0 }
if j + 3 < n && s[j] == 51 && s[j + 1] == 49 && s[j + 2] == 49 && s[j + 3] == 49 { return 0 }
if j + 3 < n && s[j] == 51 && s[j + 1] == 50 && s[j + 2] == 50 && s[j + 3] == 50 { return 0 }
if j + 1 < n && s[j] == 51 && s[j + 1] == 51 { return 0 }
return 1
}
function spl0_at(s: ptr<i8>, i: i64) -> i32 {
let n: i64 = strlen(s)
let ch: i8 = s[i]
if ch == 49 && i == n - 1 { return 1 }
if ch == 49 && i + 2 < n && s[i + 1] == 50 && s[i + 2] == 50 {
return spl00_at(s, i + 3)
}
if ch == 50 { return spl00_at(s, i + 1) }
if ch == 51 && i == n - 1 { return 1 }
if ch == 51 && i + 2 < n && s[i + 1] == 50 && s[i + 2] == 50 {
return spl00_at(s, i + 3)
}
return 0
}
# Split string into elements, return count and fill indices array
# Each element is written to the out_elems buffer as null-terminated strings
function split_elements(s: ptr<i8>, out_count: ptr<i32>, out_elems: ptr<i8>) -> void {
let n: i64 = strlen(s)
if n == 0 { out_count[0] = 0
return
}
let mut start: i64 = 0
let mut count: i32 = 0
let mut i: i64 = 0
while i < n {
if spl0_at(s, i) == 1 {
# Copy s[start..i+1] to out_elems[count]
let dst: ptr<i8> = out_elems + ((count as i64) * (MAX_ELEM_LEN as i64))
let mut k: i64 = start
while k <= i {
dst[k - start] = s[k]
k = k + 1
}
dst[i + 1 - start] = 0
count = count + 1
start = i + 1
}
i = i + 1
}
if start < n {
let dst2: ptr<i8> = out_elems + ((count as i64) * (MAX_ELEM_LEN as i64))
let mut k2: i64 = start
while k2 < n {
dst2[k2 - start] = s[k2]
k2 = k2 + 1
}
dst2[n - start] = 0
count = count + 1
}
out_count[0] = count
}
# Matrix multiply mod 2^30. Matrices are flat m*m arrays of u32.
function mat_mul(A: ptr<u32>, B: ptr<u32>, out: ptr<u32>, m: i32) -> void {
memset_zero_u32(out, (m as i64) * (m as i64))
let mut i: i32 = 0
while i < m {
let mut k: i32 = 0
while k < m {
let a: u32 = A[i * m + k]
if a == 0 { k = k + 1
continue
}
let mut j: i32 = 0
while j < m {
out[i * m + j] = ((out[i * m + j] as u64) + ((a as u64) * (B[k * m + j] as u64))) as u32 & MOD_MASK
j = j + 1
}
k = k + 1
}
i = i + 1
}
}
# Vector * matrix mod 2^30
function vec_mul(v: ptr<u32>, M: ptr<u32>, out: ptr<u32>, m: i32) -> void {
memset_zero_u32(out, m as i64)
let mut i: i32 = 0
while i < m {
let a: u32 = v[i]
if a == 0 { i = i + 1
continue
}
let mut j: i32 = 0
while j < m {
out[j] = ((out[j] as u64) + ((a as u64) * (M[i * m + j] as u64))) as u32 & MOD_MASK
j = j + 1
}
i = i + 1
}
}
function memset_zero_u32(arr: ptr<u32>, n: i64) -> void {
let mut i: i64 = 0
while i < n {
arr[i] = 0
i = i + 1
}
}
# Vector * M^exp using binary exponentiation
function vec_mul_pow(v: ptr<u32>, M: ptr<u32>, exp: i64, m: i32, out: ptr<u32>) -> void {
let cur_v: ptr<u32> = calloc((m as i64), 4)
memcpy(cur_v as ptr<void>, v as ptr<void>, (m as i64) * 4)
let cur_M: ptr<u32> = calloc((m as i64) * (m as i64), 4)
memcpy(cur_M as ptr<void>, M as ptr<void>, (m as i64) * (m as i64) * 4)
let tmp_v: ptr<u32> = calloc((m as i64), 4)
let tmp_M: ptr<u32> = calloc((m as i64) * (m as i64), 4)
let mut e: i64 = exp
while e > 0 {
if (e & 1) == 1 {
vec_mul(cur_v, cur_M, tmp_v, m)
memcpy(cur_v as ptr<void>, tmp_v as ptr<void>, (m as i64) * 4)
}
e = e >> 1
if e > 0 {
mat_mul(cur_M, cur_M, tmp_M, m)
memcpy(cur_M as ptr<void>, tmp_M as ptr<void>, (m as i64) * (m as i64) * 4)
}
}
memcpy(out as ptr<void>, cur_v as ptr<void>, (m as i64) * 4)
free(cur_v as ptr<void>)
free(cur_M as ptr<void>)
free(tmp_v as ptr<void>)
free(tmp_M as ptr<void>)
}
function counts_in_term(term: ptr<i8>, outA: ptr<u32>, outB: ptr<u32>, outC: ptr<u32>) -> void {
let mut A: u32 = 0
let mut B: u32 = 0
let mut C: u32 = 0
let n: i64 = strlen(term)
let mut i: i64 = 0
while i < n {
let ch: i8 = term[i]
if ch == 49 { A = A + 1 }
else {
if ch == 50 { B = B + 1 }
else {
if ch == 51 { C = C + 1 }
}
}
i = i + 1
}
outA[0] = A
outB[0] = B
outC[0] = C
}
function main() -> i32 {
let n: i64 = 1000000000000
g_buf1 = calloc((MAX_STR as i64), 1)
g_buf2 = calloc((MAX_STR as i64), 1)
g_elems = calloc((MAX_SPLIT as i64) * (MAX_ELEM_LEN as i64), 1)
# Start with "1"
g_buf1[0] = 49
g_buf1[1] = 0
let steps: i32 = 39
if n - 1 < (steps as i64) { steps = (n - 1) as i32 }
let mut i: i32 = 0
while i < steps {
say(g_buf1, g_buf2)
memcpy(g_buf1 as ptr<void>, g_buf2 as ptr<void>, (MAX_STR as i64))
i = i + 1
}
if n <= 40 {
let Aptr: ptr<u32> = calloc(1, 4)
let Bptr: ptr<u32> = calloc(1, 4)
let Cptr: ptr<u32> = calloc(1, 4)
counts_in_term(g_buf1, Aptr, Bptr, Cptr)
printf("%u,%u,%u\n", Aptr[0], Bptr[0], Cptr[0])
free(Aptr as ptr<void>)
free(Bptr as ptr<void>)
free(Cptr as ptr<void>)
free(g_buf1 as ptr<void>)
free(g_buf2 as ptr<void>)
free(g_elems as ptr<void>)
return 0
}
# Split seed elements
let seed_buf: ptr<i8> = calloc((MAX_SPLIT as i64) * (MAX_ELEM_LEN as i64), 1)
let seed_count_ptr: ptr<i32> = calloc(1, 4)
split_elements(g_buf1, seed_count_ptr, seed_buf)
let seed_count: i32 = seed_count_ptr[0]
free(seed_count_ptr as ptr<void>)
# Add seed elements to global table
let mut si: i32 = 0
while si < seed_count {
let e: ptr<i8> = seed_buf + ((si as i64) * (MAX_ELEM_LEN as i64))
find_or_add(e)
si = si + 1
}
# Add children of each element
let child_buf: ptr<i8> = calloc((MAX_SPLIT as i64) * (MAX_ELEM_LEN as i64), 1)
let child_count_ptr: ptr<i32> = calloc(1, 4)
let mut p: i32 = 0
while p < g_nelems {
let ep: ptr<i8> = elem_ptr(p)
say(ep, g_buf2)
split_elements(g_buf2, child_count_ptr, child_buf)
let cc: i32 = child_count_ptr[0]
let mut ci: i32 = 0
while ci < cc {
let ce: ptr<i8> = child_buf + ((ci as i64) * (MAX_ELEM_LEN as i64))
find_or_add(ce)
ci = ci + 1
}
p = p + 1
}
free(child_count_ptr as ptr<void>)
free(child_buf as ptr<void>)
let m: i32 = g_nelems
# Build transition matrix M
let M: ptr<u32> = calloc((m as i64) * (m as i64), 4)
let dec_buf: ptr<i8> = calloc((MAX_SPLIT as i64) * (MAX_ELEM_LEN as i64), 1)
let dec_count_ptr: ptr<i32> = calloc(1, 4)
let mut mi: i32 = 0
while mi < m {
say(elem_ptr(mi), g_buf2)
split_elements(g_buf2, dec_count_ptr, dec_buf)
let dc: i32 = dec_count_ptr[0]
let mut di: i32 = 0
while di < dc {
let de: ptr<i8> = dec_buf + ((di as i64) * (MAX_ELEM_LEN as i64))
let idx: i32 = find_or_add(de)
# But find_or_add may have increased m! We need to handle this.
# Actually, all elements should already be in the table from the pre-pass.
M[mi * m + idx] = M[mi * m + idx] + 1
di = di + 1
}
mi = mi + 1
}
free(dec_count_ptr as ptr<void>)
free(dec_buf as ptr<void>)
# Recompute m in case new elements were added (shouldn't happen)
let m2: i32 = g_nelems
# If m2 != m, we'd need to rebuild. But cosmological theorem guarantees closure.
# Count 1s, 2s, 3s in each element
let ones: ptr<u32> = calloc((m as i64), 4)
let twos: ptr<u32> = calloc((m as i64), 4)
let threes: ptr<u32> = calloc((m as i64), 4)
let mut ci2: i32 = 0
while ci2 < m {
let ep2: ptr<i8> = elem_ptr(ci2)
let len: i64 = strlen(ep2)
let mut k: i64 = 0
while k < len {
let ch: i8 = ep2[k]
if ch == 49 { ones[ci2] = ones[ci2] + 1 }
else {
if ch == 50 { twos[ci2] = twos[ci2] + 1 }
else {
if ch == 51 { threes[ci2] = threes[ci2] + 1 }
}
}
k = k + 1
}
ci2 = ci2 + 1
}
# Build initial vector from seed elements
let v: ptr<u32> = calloc((m as i64), 4)
let mut si2: i32 = 0
while si2 < seed_count {
let e: ptr<i8> = seed_buf + ((si2 as i64) * (MAX_ELEM_LEN as i64))
let found: i32 = find_or_add(e)
v[found] = v[found] + 1
si2 = si2 + 1
}
free(seed_buf as ptr<void>)
# v = v * M^(n-40)
let v_final: ptr<u32> = calloc((m as i64), 4)
vec_mul_pow(v, M, n - 40, m, v_final)
let mut A: u32 = 0
let mut B: u32 = 0
let mut C: u32 = 0
let mut ri: i32 = 0
while ri < m {
if v_final[ri] != 0 {
A = ((A as u64) + ((v_final[ri] as u64) * (ones[ri] as u64))) as u32 & MOD_MASK
B = ((B as u64) + ((v_final[ri] as u64) * (twos[ri] as u64))) as u32 & MOD_MASK
C = ((C as u64) + ((v_final[ri] as u64) * (threes[ri] as u64))) as u32 & MOD_MASK
}
ri = ri + 1
}
printf("%u,%u,%u\n", A, B, C)
free(M as ptr<void>)
free(ones as ptr<void>)
free(twos as ptr<void>)
free(threes as ptr<void>)
free(v as ptr<void>)
free(v_final as ptr<void>)
free(g_buf1 as ptr<void>)
free(g_buf2 as ptr<void>)
free(g_elems as ptr<void>)
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; }
int8_t* elem_ptr_i32(int32_t i);
int32_t find_or_add_ptr_i8(int8_t* e);
void say_ptr_i8_ptr_i8(int8_t* input, int8_t* out);
int32_t spl00_at_ptr_i8_i64(int8_t* s, int64_t j);
int32_t spl0_at_ptr_i8_i64(int8_t* s, int64_t i);
void split_elements_ptr_i8_ptr_i32_ptr_i8(int8_t* s, int32_t* out_count, int8_t* out_elems);
void mat_mul_ptr_u32_ptr_u32_ptr_u32_i32(uint32_t* A, uint32_t* B, uint32_t* out, int32_t m);
void vec_mul_ptr_u32_ptr_u32_ptr_u32_i32(uint32_t* v, uint32_t* M, uint32_t* out, int32_t m);
void memset_zero_u32_ptr_u32_i64(uint32_t* arr, int64_t n);
void vec_mul_pow_ptr_u32_ptr_u32_i64_i32_ptr_u32(uint32_t* v, uint32_t* M, int64_t exp, int32_t m, uint32_t* out);
void counts_in_term_ptr_i8_ptr_u32_ptr_u32_ptr_u32(int8_t* term, uint32_t* outA, uint32_t* outB, uint32_t* outC);
int32_t main(void);
static const uint32_t MOD_MASK = 1073741823;
static const int32_t MAX_ELEMS = 200;
static const int32_t MAX_ELEM_LEN = 128;
static const int32_t MAX_STR = 70000;
static const int32_t MAX_SPLIT = 10000;
/* Module statics */
static int8_t* g_buf1 = NULL;
static int8_t* g_buf2 = NULL;
static int8_t* g_elems = NULL;
static int32_t g_nelems = 0;
int8_t* elem_ptr_i32(int32_t i) {
return (g_elems + (((int64_t)(i)) * ((int64_t)(MAX_ELEM_LEN))));
}
int32_t find_or_add_ptr_i8(int8_t* e) {
int32_t i = 0;
while (i < g_nelems) {
if (strcmp(elem_ptr_i32(i), e) == 0) {
return i;
}
i = (i + 1);
}
int32_t j = g_nelems;
g_nelems = (g_nelems + 1);
strcpy(elem_ptr_i32(j), e);
return j;
}
void say_ptr_i8_ptr_i8(int8_t* input, int8_t* out) {
int64_t n = strlen(input);
int64_t i = 0;
int64_t op = 0;
while (i < n) {
int8_t ch = input[i];
int64_t j = (i + 1);
while ((j < n && input[j] == ch)) {
j = (j + 1);
}
int64_t count = (j - i);
int8_t* digits = (int8_t*)(calloc(20, 1));
int32_t dc = 0;
int64_t c = count;
if (c == 0) {
digits[0] = 48;
dc = 1;
}
while (c > 0) {
digits[dc] = (((int8_t)(FLOW_CHECKED_MOD((c), (10)))) + 48);
dc = (dc + 1);
c = FLOW_CHECKED_DIV((c), (10));
}
int32_t d = (dc - 1);
while (d >= 0) {
out[op] = digits[d];
op = (op + 1);
d = (d - 1);
}
free(((void*)(digits)));
out[op] = ch;
op = (op + 1);
i = j;
}
out[op] = 0;
}
int32_t spl00_at_ptr_i8_i64(int8_t* s, int64_t j) {
int64_t n = strlen(s);
if (((((j + 2) < n && s[j] == 49) && s[(j + 1)] == 49) && s[(j + 2)] == 49)) {
return 1;
}
if ((j == (n - 1) && s[j] == 49)) {
return 0;
}
if ((((j + 1) < n && s[j] == 49) && s[(j + 1)] == 49)) {
return 0;
}
if (((((j + 2) < n && s[j] == 49) && s[(j + 1)] == 50) && s[(j + 2)] == 50)) {
return 0;
}
if (((((j + 2) < n && s[j] == 49) && s[(j + 1)] == 51) && s[(j + 2)] == 51)) {
return 0;
}
if ((j < n && s[j] == 50)) {
return 0;
}
if ((((((j + 3) < n && s[j] == 51) && s[(j + 1)] == 49) && s[(j + 2)] == 49) && s[(j + 3)] == 49)) {
return 0;
}
if ((((((j + 3) < n && s[j] == 51) && s[(j + 1)] == 50) && s[(j + 2)] == 50) && s[(j + 3)] == 50)) {
return 0;
}
if ((((j + 1) < n && s[j] == 51) && s[(j + 1)] == 51)) {
return 0;
}
return 1;
}
int32_t spl0_at_ptr_i8_i64(int8_t* s, int64_t i) {
int64_t n = strlen(s);
int8_t ch = s[i];
if ((ch == 49 && i == (n - 1))) {
return 1;
}
if ((((ch == 49 && (i + 2) < n) && s[(i + 1)] == 50) && s[(i + 2)] == 50)) {
return spl00_at_ptr_i8_i64(s, (i + 3));
}
if (ch == 50) {
return spl00_at_ptr_i8_i64(s, (i + 1));
}
if ((ch == 51 && i == (n - 1))) {
return 1;
}
if ((((ch == 51 && (i + 2) < n) && s[(i + 1)] == 50) && s[(i + 2)] == 50)) {
return spl00_at_ptr_i8_i64(s, (i + 3));
}
return 0;
}
void split_elements_ptr_i8_ptr_i32_ptr_i8(int8_t* s, int32_t* out_count, int8_t* out_elems) {
int64_t n = strlen(s);
if (n == 0) {
out_count[0] = 0;
return;
}
int64_t start = 0;
int32_t count = 0;
int64_t i = 0;
while (i < n) {
if (spl0_at_ptr_i8_i64(s, i) == 1) {
int8_t* dst = (int8_t*)((out_elems + (((int64_t)(count)) * ((int64_t)(MAX_ELEM_LEN)))));
int64_t k = start;
while (k <= i) {
dst[(k - start)] = s[k];
k = (k + 1);
}
dst[((i + 1) - start)] = 0;
count = (count + 1);
start = (i + 1);
}
i = (i + 1);
}
if (start < n) {
int8_t* dst2 = (int8_t*)((out_elems + (((int64_t)(count)) * ((int64_t)(MAX_ELEM_LEN)))));
int64_t k2 = start;
while (k2 < n) {
dst2[(k2 - start)] = s[k2];
k2 = (k2 + 1);
}
dst2[(n - start)] = 0;
count = (count + 1);
}
out_count[0] = count;
}
void mat_mul_ptr_u32_ptr_u32_ptr_u32_i32(uint32_t* A, uint32_t* B, uint32_t* out, int32_t m) {
memset_zero_u32_ptr_u32_i64(out, (((int64_t)(m)) * ((int64_t)(m))));
int32_t i = 0;
while (i < m) {
int32_t k = 0;
while (k < m) {
uint32_t a = A[((i * m) + k)];
if (a == 0) {
k = (k + 1);
continue;
}
int32_t j = 0;
while (j < m) {
out[((i * m) + j)] = (((uint32_t)((((uint64_t)(out[((i * m) + j)])) + (((uint64_t)(a)) * ((uint64_t)(B[((k * m) + j)])))))) & MOD_MASK);
j = (j + 1);
}
k = (k + 1);
}
i = (i + 1);
}
}
void vec_mul_ptr_u32_ptr_u32_ptr_u32_i32(uint32_t* v, uint32_t* M, uint32_t* out, int32_t m) {
memset_zero_u32_ptr_u32_i64(out, ((int64_t)(m)));
int32_t i = 0;
while (i < m) {
uint32_t a = v[i];
if (a == 0) {
i = (i + 1);
continue;
}
int32_t j = 0;
while (j < m) {
out[j] = (((uint32_t)((((uint64_t)(out[j])) + (((uint64_t)(a)) * ((uint64_t)(M[((i * m) + j)])))))) & MOD_MASK);
j = (j + 1);
}
i = (i + 1);
}
}
void memset_zero_u32_ptr_u32_i64(uint32_t* arr, int64_t n) {
int64_t i = 0;
while (i < n) {
arr[i] = 0;
i = (i + 1);
}
}
void vec_mul_pow_ptr_u32_ptr_u32_i64_i32_ptr_u32(uint32_t* v, uint32_t* M, int64_t exp, int32_t m, uint32_t* out) {
uint32_t* cur_v = (uint32_t*)(calloc(((int64_t)(m)), 4));
memcpy(((void*)(cur_v)), ((void*)(v)), (((int64_t)(m)) * 4));
uint32_t* cur_M = (uint32_t*)(calloc((((int64_t)(m)) * ((int64_t)(m))), 4));
memcpy(((void*)(cur_M)), ((void*)(M)), ((((int64_t)(m)) * ((int64_t)(m))) * 4));
uint32_t* tmp_v = (uint32_t*)(calloc(((int64_t)(m)), 4));
uint32_t* tmp_M = (uint32_t*)(calloc((((int64_t)(m)) * ((int64_t)(m))), 4));
int64_t e = exp;
while (e > 0) {
if ((e & 1) == 1) {
vec_mul_ptr_u32_ptr_u32_ptr_u32_i32(cur_v, cur_M, tmp_v, m);
memcpy(((void*)(cur_v)), ((void*)(tmp_v)), (((int64_t)(m)) * 4));
}
e = FLOW_CHECKED_SHR((e), (1));
if (e > 0) {
mat_mul_ptr_u32_ptr_u32_ptr_u32_i32(cur_M, cur_M, tmp_M, m);
memcpy(((void*)(cur_M)), ((void*)(tmp_M)), ((((int64_t)(m)) * ((int64_t)(m))) * 4));
}
}
memcpy(((void*)(out)), ((void*)(cur_v)), (((int64_t)(m)) * 4));
free(((void*)(cur_v)));
free(((void*)(cur_M)));
free(((void*)(tmp_v)));
free(((void*)(tmp_M)));
}
void counts_in_term_ptr_i8_ptr_u32_ptr_u32_ptr_u32(int8_t* term, uint32_t* outA, uint32_t* outB, uint32_t* outC) {
uint32_t A = 0;
uint32_t B = 0;
uint32_t C = 0;
int64_t n = strlen(term);
int64_t i = 0;
while (i < n) {
int8_t ch = term[i];
if (ch == 49) {
A = (A + 1);
} else {
if (ch == 50) {
B = (B + 1);
} else {
if (ch == 51) {
C = (C + 1);
}
}
}
i = (i + 1);
}
outA[0] = A;
outB[0] = B;
outC[0] = C;
}
int32_t main(void) {
int64_t n = 1000000000000;
g_buf1 = calloc(((int64_t)(MAX_STR)), 1);
g_buf2 = calloc(((int64_t)(MAX_STR)), 1);
g_elems = calloc((((int64_t)(MAX_SPLIT)) * ((int64_t)(MAX_ELEM_LEN))), 1);
g_buf1[0] = 49;
g_buf1[1] = 0;
int32_t steps = 39;
if ((n - 1) < ((int64_t)(steps))) {
steps = ((int32_t)((n - 1)));
}
int32_t i = 0;
while (i < steps) {
say_ptr_i8_ptr_i8(g_buf1, g_buf2);
memcpy(((void*)(g_buf1)), ((void*)(g_buf2)), ((int64_t)(MAX_STR)));
i = (i + 1);
}
if (n <= 40) {
uint32_t* Aptr = (uint32_t*)(calloc(1, 4));
uint32_t* Bptr = (uint32_t*)(calloc(1, 4));
uint32_t* Cptr = (uint32_t*)(calloc(1, 4));
counts_in_term_ptr_i8_ptr_u32_ptr_u32_ptr_u32(g_buf1, Aptr, Bptr, Cptr);
printf("%u,%u,%u\n", Aptr[0], Bptr[0], Cptr[0]);
free(((void*)(Aptr)));
free(((void*)(Bptr)));
free(((void*)(Cptr)));
free(((void*)(g_buf1)));
free(((void*)(g_buf2)));
free(((void*)(g_elems)));
return 0;
}
int8_t* seed_buf = (int8_t*)(calloc((((int64_t)(MAX_SPLIT)) * ((int64_t)(MAX_ELEM_LEN))), 1));
int32_t* seed_count_ptr = (int32_t*)(calloc(1, 4));
split_elements_ptr_i8_ptr_i32_ptr_i8(g_buf1, seed_count_ptr, seed_buf);
int32_t seed_count = seed_count_ptr[0];
free(((void*)(seed_count_ptr)));
int32_t si = 0;
while (si < seed_count) {
int8_t* e = (int8_t*)((seed_buf + (((int64_t)(si)) * ((int64_t)(MAX_ELEM_LEN)))));
find_or_add_ptr_i8(e);
si = (si + 1);
}
int8_t* child_buf = (int8_t*)(calloc((((int64_t)(MAX_SPLIT)) * ((int64_t)(MAX_ELEM_LEN))), 1));
int32_t* child_count_ptr = (int32_t*)(calloc(1, 4));
int32_t p = 0;
while (p < g_nelems) {
int8_t* ep = (int8_t*)(elem_ptr_i32(p));
say_ptr_i8_ptr_i8(ep, g_buf2);
split_elements_ptr_i8_ptr_i32_ptr_i8(g_buf2, child_count_ptr, child_buf);
int32_t cc = child_count_ptr[0];
int32_t ci = 0;
while (ci < cc) {
int8_t* ce = (int8_t*)((child_buf + (((int64_t)(ci)) * ((int64_t)(MAX_ELEM_LEN)))));
find_or_add_ptr_i8(ce);
ci = (ci + 1);
}
p = (p + 1);
}
free(((void*)(child_count_ptr)));
free(((void*)(child_buf)));
int32_t m = g_nelems;
uint32_t* M = (uint32_t*)(calloc((((int64_t)(m)) * ((int64_t)(m))), 4));
int8_t* dec_buf = (int8_t*)(calloc((((int64_t)(MAX_SPLIT)) * ((int64_t)(MAX_ELEM_LEN))), 1));
int32_t* dec_count_ptr = (int32_t*)(calloc(1, 4));
int32_t mi = 0;
while (mi < m) {
say_ptr_i8_ptr_i8(elem_ptr_i32(mi), g_buf2);
split_elements_ptr_i8_ptr_i32_ptr_i8(g_buf2, dec_count_ptr, dec_buf);
int32_t dc = dec_count_ptr[0];
int32_t di = 0;
while (di < dc) {
int8_t* de = (int8_t*)((dec_buf + (((int64_t)(di)) * ((int64_t)(MAX_ELEM_LEN)))));
int32_t idx = find_or_add_ptr_i8(de);
M[((mi * m) + idx)] = (M[((mi * m) + idx)] + 1);
di = (di + 1);
}
mi = (mi + 1);
}
free(((void*)(dec_count_ptr)));
free(((void*)(dec_buf)));
int32_t m2 = g_nelems;
uint32_t* ones = (uint32_t*)(calloc(((int64_t)(m)), 4));
uint32_t* twos = (uint32_t*)(calloc(((int64_t)(m)), 4));
uint32_t* threes = (uint32_t*)(calloc(((int64_t)(m)), 4));
int32_t ci2 = 0;
while (ci2 < m) {
int8_t* ep2 = (int8_t*)(elem_ptr_i32(ci2));
int64_t len = strlen(ep2);
int64_t k = 0;
while (k < len) {
int8_t ch = ep2[k];
if (ch == 49) {
ones[ci2] = (ones[ci2] + 1);
} else {
if (ch == 50) {
twos[ci2] = (twos[ci2] + 1);
} else {
if (ch == 51) {
threes[ci2] = (threes[ci2] + 1);
}
}
}
k = (k + 1);
}
ci2 = (ci2 + 1);
}
uint32_t* v = (uint32_t*)(calloc(((int64_t)(m)), 4));
int32_t si2 = 0;
while (si2 < seed_count) {
int8_t* e = (int8_t*)((seed_buf + (((int64_t)(si2)) * ((int64_t)(MAX_ELEM_LEN)))));
int32_t found = find_or_add_ptr_i8(e);
v[found] = (v[found] + 1);
si2 = (si2 + 1);
}
free(((void*)(seed_buf)));
uint32_t* v_final = (uint32_t*)(calloc(((int64_t)(m)), 4));
vec_mul_pow_ptr_u32_ptr_u32_i64_i32_ptr_u32(v, M, (n - 40), m, v_final);
uint32_t A = 0;
uint32_t B = 0;
uint32_t C = 0;
int32_t ri = 0;
while (ri < m) {
if (v_final[ri] != 0) {
A = (((uint32_t)((((uint64_t)(A)) + (((uint64_t)(v_final[ri])) * ((uint64_t)(ones[ri])))))) & MOD_MASK);
B = (((uint32_t)((((uint64_t)(B)) + (((uint64_t)(v_final[ri])) * ((uint64_t)(twos[ri])))))) & MOD_MASK);
C = (((uint32_t)((((uint64_t)(C)) + (((uint64_t)(v_final[ri])) * ((uint64_t)(threes[ri])))))) & MOD_MASK);
}
ri = (ri + 1);
}
printf("%u,%u,%u\n", A, B, C);
free(((void*)(M)));
free(((void*)(ones)));
free(((void*)(twos)));
free(((void*)(threes)));
free(((void*)(v)));
free(((void*)(v_final)));
free(((void*)(g_buf1)));
free(((void*)(g_buf2)));
free(((void*)(g_elems)));
return 0;
}