Problem 961
Removing Digits — impartial game W(10^18). Only nonzero digit positions matter; count first-player wins among n < 10^18.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n log n) | ? |
|---|
| Space complexity | O(n) | ? |
|---|
| Approach | Flow solution | Not curated |
|---|
| Verdict | Unknown |
|---|
Flow source
# Project Euler 961
# Removing Digits — impartial game W(10^18).
# Only nonzero digit positions matter; count first-player wins among n < 10^18.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
let mut win_memo: ptr<i8> = null
let mut win_ready: ptr<i8> = null
function idx(d: i64, mask: i64) -> i64 {
return d * (1 << 18) + mask
}
function first_wins(d: i64, mask: i64) -> i64 {
let i: i64 = idx(d, mask)
if win_ready[i] != 0 {
return win_memo[i] as i64
}
if mask == 0 {
win_ready[i] = 1
win_memo[i] = 0
return 0
}
let mut pos: i64 = 0
while pos < d {
let mut bits: [i64; 18]
let mut n: i64 = 0
let mut j: i64 = 0
while j < d {
if j != pos {
bits[n] = (mask >> (d - 1 - j)) & 1
n = n + 1
}
j = j + 1
}
let mut any: i64 = 0
j = 0
while j < n {
if bits[j] != 0 { any = 1 }
j = j + 1
}
if any == 0 {
win_ready[i] = 1
win_memo[i] = 1
return 1
}
let mut start: i64 = 0
while start < n && bits[start] == 0 {
start = start + 1
}
let nd: i64 = n - start
let mut nm: i64 = 0
j = start
while j < n {
nm = (nm << 1) | bits[j]
j = j + 1
}
if first_wins(nd, nm) == 0 {
win_ready[i] = 1
win_memo[i] = 1
return 1
}
pos = pos + 1
}
win_ready[i] = 1
win_memo[i] = 0
return 0
}
function ipow9(k: i64) -> i64 {
let mut r: i64 = 1
let mut i: i64 = 0
while i < k {
r = r * 9
i = i + 1
}
return r
}
function W_digits(d: i64) -> i64 {
let mut total: i64 = 0
let lim: i64 = 1 << d
let mut mask: i64 = 0
while mask < lim {
if ((mask >> (d - 1)) & 1) != 0 {
if first_wins(d, mask) != 0 {
let mut k: i64 = 0
let mut b: i64 = 0
while b < d {
if (mask & (1 << b)) != 0 { k = k + 1 }
b = b + 1
}
total = total + ipow9(k)
}
}
mask = mask + 1
}
return total
}
function main() -> i32 {
let cells: i64 = 19 * (1 << 18)
win_memo = calloc(cells, 1)
win_ready = calloc(cells, 1)
if win_memo == null || win_ready == null { return 1 }
let mut total: i64 = 0
let mut d: i64 = 1
while d <= 18 {
total = total + W_digits(d)
d = d + 1
}
printf("%lld\n", total)
free(win_memo)
free(win_ready)
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 idx_i64_i64(int64_t d, int64_t mask);
int64_t first_wins_i64_i64(int64_t d, int64_t mask);
int64_t ipow9_i64(int64_t k);
int64_t W_digits_i64(int64_t d);
int32_t main(void);
/* Module statics */
static int8_t* win_memo = NULL;
static int8_t* win_ready = NULL;
int64_t idx_i64_i64(int64_t d, int64_t mask) {
return ((d * FLOW_CHECKED_SHL((1), (18))) + mask);
}
int64_t first_wins_i64_i64(int64_t d, int64_t mask) {
int64_t i = idx_i64_i64(d, mask);
if (win_ready[i] != 0) {
return ((int64_t)(win_memo[i]));
}
if (mask == 0) {
win_ready[i] = 1;
win_memo[i] = 0;
return 0;
}
int64_t pos = 0;
while (pos < d) {
int64_t bits[18];
int64_t n = 0;
int64_t j = 0;
while (j < d) {
if (j != pos) {
bits[n] = (FLOW_CHECKED_SHR((mask), (((d - 1) - j))) & 1);
n = (n + 1);
}
j = (j + 1);
}
int64_t any = 0;
j = 0;
while (j < n) {
if ((((unsigned)(j) < 18) ? bits[j] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(j), 18), flow_fault_handler("array index out of bounds"), bits[0])) != 0) {
any = 1;
}
j = (j + 1);
}
if (any == 0) {
win_ready[i] = 1;
win_memo[i] = 1;
return 1;
}
int64_t start = 0;
while ((start < n && (((unsigned)(start) < 18) ? bits[start] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(start), 18), flow_fault_handler("array index out of bounds"), bits[0])) == 0)) {
start = (start + 1);
}
int64_t nd = (n - start);
int64_t nm = 0;
j = start;
while (j < n) {
nm = (FLOW_CHECKED_SHL((nm), (1)) | (((unsigned)(j) < 18) ? bits[j] : (fprintf(stderr, "array index %d out of bounds (size %d)\n", (int)(j), 18), flow_fault_handler("array index out of bounds"), bits[0])));
j = (j + 1);
}
if (first_wins_i64_i64(nd, nm) == 0) {
win_ready[i] = 1;
win_memo[i] = 1;
return 1;
}
pos = (pos + 1);
}
win_ready[i] = 1;
win_memo[i] = 0;
return 0;
}
int64_t ipow9_i64(int64_t k) {
int64_t r = 1;
int64_t i = 0;
while (i < k) {
r = (r * 9);
i = (i + 1);
}
return r;
}
int64_t W_digits_i64(int64_t d) {
int64_t total = 0;
int64_t lim = FLOW_CHECKED_SHL((1), (d));
int64_t mask = 0;
while (mask < lim) {
if ((FLOW_CHECKED_SHR((mask), ((d - 1))) & 1) != 0) {
if (first_wins_i64_i64(d, mask) != 0) {
int64_t k = 0;
int64_t b = 0;
while (b < d) {
if ((mask & FLOW_CHECKED_SHL((1), (b))) != 0) {
k = (k + 1);
}
b = (b + 1);
}
total = (total + ipow9_i64(k));
}
}
mask = (mask + 1);
}
return total;
}
int32_t main(void) {
int64_t cells = (19 * FLOW_CHECKED_SHL((1), (18)));
win_memo = calloc(cells, 1);
win_ready = calloc(cells, 1);
if ((win_memo == NULL || win_ready == NULL)) {
return 1;
}
int64_t total = 0;
int64_t d = 1;
while (d <= 18) {
total = (total + W_digits_i64(d));
d = (d + 1);
}
printf("%lld\n", total);
free(win_memo);
free(win_ready);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
// Module static: win_memo
llvm.mlir.global internal @win_memo() {addr_space = 0 : i32} : !llvm.ptr {
%0 = llvm.mlir.zero : !llvm.ptr
llvm.return %0 : !llvm.ptr
}
// Module static: win_ready
llvm.mlir.global internal @win_ready() {addr_space = 0 : i32} : !llvm.ptr {
%1 = llvm.mlir.zero : !llvm.ptr
llvm.return %1 : !llvm.ptr
}
func.func @idx(%arg0: i64, %arg1: i64) -> i64 {
%2 = arith.constant 1 : i32
%3 = arith.constant 18 : i32
%4 = arith.shli %2, %3 : i32
%6 = arith.extsi %4 : i32 to i64
%5 = arith.muli %arg0, %6 : i64
%7 = arith.addi %5, %arg1 : i64
func.return %7 : i64
}
func.func @first_wins(%arg0: i64, %arg1: i64) -> i64 {
%8 = func.call @idx(%arg0, %arg1) : (i64, i64) -> i64
%10 = llvm.mlir.addressof @win_ready : !llvm.ptr
%11 = llvm.load %10 : !llvm.ptr -> !llvm.ptr
%12 = llvm.getelementptr %11[%8] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%9 = llvm.load %12 : !llvm.ptr -> i8
%13 = arith.constant 0 : i32
%15 = arith.extsi %9 : i8 to i32
%14 = arith.cmpi ne, %15, %13 : i32
cf.cond_br %14, ^bb0, ^bb1
^bb0:
%17 = llvm.mlir.addressof @win_memo : !llvm.ptr
%18 = llvm.load %17 : !llvm.ptr -> !llvm.ptr
%19 = llvm.getelementptr %18[%8] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%16 = llvm.load %19 : !llvm.ptr -> i8
%20 = arith.extsi %16 : i8 to i64
func.return %20 : i64
^bb1:
cf.br ^bb2
^bb2:
%21 = arith.constant 0 : i32
%23 = arith.extsi %21 : i32 to i64
%22 = arith.cmpi eq, %arg1, %23 : i64
cf.cond_br %22, ^bb3, ^bb4
^bb3:
%24 = arith.constant 1 : i32
%25 = llvm.mlir.addressof @win_ready : !llvm.ptr
%26 = llvm.load %25 : !llvm.ptr -> !llvm.ptr
%27 = arith.trunci %24 : i32 to i8
%28 = llvm.getelementptr %26[%8] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %27, %28 : i8, !llvm.ptr
%29 = arith.constant 0 : i32
%30 = llvm.mlir.addressof @win_memo : !llvm.ptr
%31 = llvm.load %30 : !llvm.ptr -> !llvm.ptr
%32 = arith.trunci %29 : i32 to i8
%33 = llvm.getelementptr %31[%8] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %32, %33 : i8, !llvm.ptr
%34 = arith.constant 0 : i32
%35 = arith.extsi %34 : i32 to i64
func.return %35 : i64
^bb4:
cf.br ^bb5
^bb5:
%36 = arith.constant 0 : i32
%37 = arith.extsi %36 : i32 to i64
%38 = llvm.mlir.constant(1 : i64) : i64
%39 = llvm.alloca %38 x i64 : (i64) -> !llvm.ptr
llvm.store %37, %39 : i64, !llvm.ptr
cf.br ^bb6
^bb6:
%40 = llvm.load %39 : !llvm.ptr -> i64
%41 = arith.cmpi slt, %40, %arg0 : i64
cf.cond_br %41, ^bb7, ^bb8
^bb7:
%42 = memref.alloca() {type = memref<18xi64>} : memref<18xi64>
%43 = arith.constant 0 : i32
%44 = arith.extsi %43 : i32 to i64
%45 = llvm.mlir.constant(1 : i64) : i64
%46 = llvm.alloca %45 x i64 : (i64) -> !llvm.ptr
llvm.store %44, %46 : i64, !llvm.ptr
%47 = arith.constant 0 : i32
%48 = arith.extsi %47 : i32 to i64
%49 = llvm.mlir.constant(1 : i64) : i64
%50 = llvm.alloca %49 x i64 : (i64) -> !llvm.ptr
llvm.store %48, %50 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%51 = llvm.load %50 : !llvm.ptr -> i64
%52 = arith.cmpi slt, %51, %arg0 : i64
cf.cond_br %52, ^bb10, ^bb11
^bb10:
%53 = llvm.load %50 : !llvm.ptr -> i64
%54 = llvm.load %39 : !llvm.ptr -> i64
%55 = arith.cmpi ne, %53, %54 : i64
cf.cond_br %55, ^bb12, ^bb13
^bb12:
%56 = arith.constant 1 : i32
%58 = arith.extsi %56 : i32 to i64
%57 = arith.subi %arg0, %58 : i64
%59 = llvm.load %50 : !llvm.ptr -> i64
%60 = arith.subi %57, %59 : i64
%61 = arith.shrsi %arg1, %60 : i64
%62 = arith.constant 1 : i32
%64 = arith.extsi %62 : i32 to i64
%63 = arith.andi %61, %64 : i64
%65 = llvm.load %46 : !llvm.ptr -> i64
%66 = arith.index_cast %65 : i32 to index
memref.store %63, %42[%66] : memref<18xi64>
%67 = llvm.load %46 : !llvm.ptr -> i64
%68 = arith.constant 1 : i32
%70 = arith.extsi %68 : i32 to i64
%69 = arith.addi %67, %70 : i64
llvm.store %69, %46 : i64, !llvm.ptr
cf.br ^bb14
^bb13:
cf.br ^bb14
^bb14:
%71 = llvm.load %50 : !llvm.ptr -> i64
%72 = arith.constant 1 : i32
%74 = arith.extsi %72 : i32 to i64
%73 = arith.addi %71, %74 : i64
llvm.store %73, %50 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
%75 = arith.constant 0 : i32
%76 = arith.extsi %75 : i32 to i64
%77 = llvm.mlir.constant(1 : i64) : i64
%78 = llvm.alloca %77 x i64 : (i64) -> !llvm.ptr
llvm.store %76, %78 : i64, !llvm.ptr
%79 = arith.constant 0 : i32
%80 = arith.extsi %79 : i32 to i64
llvm.store %80, %50 : i64, !llvm.ptr
cf.br ^bb15
^bb15:
%81 = llvm.load %50 : !llvm.ptr -> i64
%82 = llvm.load %46 : !llvm.ptr -> i64
%83 = arith.cmpi slt, %81, %82 : i64
cf.cond_br %83, ^bb16, ^bb17
^bb16:
%85 = llvm.load %50 : !llvm.ptr -> i64
%86 = arith.index_cast %85 : i32 to index
%84 = memref.load %42[%86] : memref<18xi64>
%87 = arith.constant 0 : i32
%89 = arith.extsi %87 : i32 to i64
%88 = arith.cmpi ne, %84, %89 : i64
cf.cond_br %88, ^bb18, ^bb19
^bb18:
%90 = arith.constant 1 : i32
%91 = arith.extsi %90 : i32 to i64
llvm.store %91, %78 : i64, !llvm.ptr
cf.br ^bb20
^bb19:
cf.br ^bb20
^bb20:
%92 = llvm.load %50 : !llvm.ptr -> i64
%93 = arith.constant 1 : i32
%95 = arith.extsi %93 : i32 to i64
%94 = arith.addi %92, %95 : i64
llvm.store %94, %50 : i64, !llvm.ptr
cf.br ^bb15
^bb17:
%96 = llvm.load %78 : !llvm.ptr -> i64
%97 = arith.constant 0 : i32
%99 = arith.extsi %97 : i32 to i64
%98 = arith.cmpi eq, %96, %99 : i64
cf.cond_br %98, ^bb21, ^bb22
^bb21:
%100 = arith.constant 1 : i32
%101 = llvm.mlir.addressof @win_ready : !llvm.ptr
%102 = llvm.load %101 : !llvm.ptr -> !llvm.ptr
%103 = arith.trunci %100 : i32 to i8
%104 = llvm.getelementptr %102[%8] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %103, %104 : i8, !llvm.ptr
%105 = arith.constant 1 : i32
%106 = llvm.mlir.addressof @win_memo : !llvm.ptr
%107 = llvm.load %106 : !llvm.ptr -> !llvm.ptr
%108 = arith.trunci %105 : i32 to i8
%109 = llvm.getelementptr %107[%8] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %108, %109 : i8, !llvm.ptr
%110 = arith.constant 1 : i32
%111 = arith.extsi %110 : i32 to i64
func.return %111 : i64
^bb22:
cf.br ^bb23
^bb23:
%112 = arith.constant 0 : i32
%113 = arith.extsi %112 : i32 to i64
%114 = llvm.mlir.constant(1 : i64) : i64
%115 = llvm.alloca %114 x i64 : (i64) -> !llvm.ptr
llvm.store %113, %115 : i64, !llvm.ptr
cf.br ^bb24
^bb24:
%116 = llvm.load %115 : !llvm.ptr -> i64
%117 = llvm.load %46 : !llvm.ptr -> i64
%118 = arith.cmpi slt, %116, %117 : i64
%119 = scf.if %118 -> (i1) {
%121 = llvm.load %115 : !llvm.ptr -> i64
%122 = arith.index_cast %121 : i32 to index
%120 = memref.load %42[%122] : memref<18xi64>
%123 = arith.constant 0 : i32
%125 = arith.extsi %123 : i32 to i64
%124 = arith.cmpi eq, %120, %125 : i64
scf.yield %124 : i1
} else {
%126 = arith.constant false
scf.yield %126 : i1
}
cf.cond_br %119, ^bb25, ^bb26
^bb25:
%127 = llvm.load %115 : !llvm.ptr -> i64
%128 = arith.constant 1 : i32
%130 = arith.extsi %128 : i32 to i64
%129 = arith.addi %127, %130 : i64
llvm.store %129, %115 : i64, !llvm.ptr
cf.br ^bb24
^bb26:
%131 = llvm.load %46 : !llvm.ptr -> i64
%132 = llvm.load %115 : !llvm.ptr -> i64
%133 = arith.subi %131, %132 : i64
%134 = arith.constant 0 : i32
%135 = arith.extsi %134 : i32 to i64
%136 = llvm.mlir.constant(1 : i64) : i64
%137 = llvm.alloca %136 x i64 : (i64) -> !llvm.ptr
llvm.store %135, %137 : i64, !llvm.ptr
%138 = llvm.load %115 : !llvm.ptr -> i64
llvm.store %138, %50 : i64, !llvm.ptr
cf.br ^bb27
^bb27:
%139 = llvm.load %50 : !llvm.ptr -> i64
%140 = llvm.load %46 : !llvm.ptr -> i64
%141 = arith.cmpi slt, %139, %140 : i64
cf.cond_br %141, ^bb28, ^bb29
^bb28:
%142 = llvm.load %137 : !llvm.ptr -> i64
%143 = arith.constant 1 : i32
%145 = arith.extsi %143 : i32 to i64
%144 = arith.shli %142, %145 : i64
%147 = llvm.load %50 : !llvm.ptr -> i64
%148 = arith.index_cast %147 : i32 to index
%146 = memref.load %42[%148] : memref<18xi64>
%149 = arith.ori %144, %146 : i64
llvm.store %149, %137 : i64, !llvm.ptr
%150 = llvm.load %50 : !llvm.ptr -> i64
%151 = arith.constant 1 : i32
%153 = arith.extsi %151 : i32 to i64
%152 = arith.addi %150, %153 : i64
llvm.store %152, %50 : i64, !llvm.ptr
cf.br ^bb27
^bb29:
%155 = llvm.load %137 : !llvm.ptr -> i64
%154 = func.call @first_wins(%133, %155) : (i64, i64) -> i64
%156 = arith.constant 0 : i32
%158 = arith.extsi %156 : i32 to i64
%157 = arith.cmpi eq, %154, %158 : i64
cf.cond_br %157, ^bb30, ^bb31
^bb30:
%159 = arith.constant 1 : i32
%160 = llvm.mlir.addressof @win_ready : !llvm.ptr
%161 = llvm.load %160 : !llvm.ptr -> !llvm.ptr
%162 = arith.trunci %159 : i32 to i8
%163 = llvm.getelementptr %161[%8] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %162, %163 : i8, !llvm.ptr
%164 = arith.constant 1 : i32
%165 = llvm.mlir.addressof @win_memo : !llvm.ptr
%166 = llvm.load %165 : !llvm.ptr -> !llvm.ptr
%167 = arith.trunci %164 : i32 to i8
%168 = llvm.getelementptr %166[%8] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %167, %168 : i8, !llvm.ptr
%169 = arith.constant 1 : i32
%170 = arith.extsi %169 : i32 to i64
func.return %170 : i64
^bb31:
cf.br ^bb32
^bb32:
%171 = llvm.load %39 : !llvm.ptr -> i64
%172 = arith.constant 1 : i32
%174 = arith.extsi %172 : i32 to i64
%173 = arith.addi %171, %174 : i64
llvm.store %173, %39 : i64, !llvm.ptr
cf.br ^bb6
^bb8:
%175 = arith.constant 1 : i32
%176 = llvm.mlir.addressof @win_ready : !llvm.ptr
%177 = llvm.load %176 : !llvm.ptr -> !llvm.ptr
%178 = arith.trunci %175 : i32 to i8
%179 = llvm.getelementptr %177[%8] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %178, %179 : i8, !llvm.ptr
%180 = arith.constant 0 : i32
%181 = llvm.mlir.addressof @win_memo : !llvm.ptr
%182 = llvm.load %181 : !llvm.ptr -> !llvm.ptr
%183 = arith.trunci %180 : i32 to i8
%184 = llvm.getelementptr %182[%8] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %183, %184 : i8, !llvm.ptr
%185 = arith.constant 0 : i32
%186 = arith.extsi %185 : i32 to i64
func.return %186 : i64
}
func.func @ipow9(%arg0: i64) -> i64 {
%187 = arith.constant 1 : i32
%188 = arith.extsi %187 : i32 to i64
%189 = llvm.mlir.constant(1 : i64) : i64
%190 = llvm.alloca %189 x i64 : (i64) -> !llvm.ptr
llvm.store %188, %190 : i64, !llvm.ptr
%191 = arith.constant 0 : i32
%192 = arith.extsi %191 : i32 to i64
%193 = llvm.mlir.constant(1 : i64) : i64
%194 = llvm.alloca %193 x i64 : (i64) -> !llvm.ptr
llvm.store %192, %194 : i64, !llvm.ptr
cf.br ^bb33
^bb33:
%195 = llvm.load %194 : !llvm.ptr -> i64
%196 = arith.cmpi slt, %195, %arg0 : i64
cf.cond_br %196, ^bb34, ^bb35
^bb34:
%197 = llvm.load %190 : !llvm.ptr -> i64
%198 = arith.constant 9 : i32
%200 = arith.extsi %198 : i32 to i64
%199 = arith.muli %197, %200 : i64
llvm.store %199, %190 : i64, !llvm.ptr
%201 = llvm.load %194 : !llvm.ptr -> i64
%202 = arith.constant 1 : i32
%204 = arith.extsi %202 : i32 to i64
%203 = arith.addi %201, %204 : i64
llvm.store %203, %194 : i64, !llvm.ptr
cf.br ^bb33
^bb35:
%205 = llvm.load %190 : !llvm.ptr -> i64
func.return %205 : i64
}
func.func @W_digits(%arg0: i64) -> i64 {
%206 = arith.constant 0 : i32
%207 = arith.extsi %206 : i32 to i64
%208 = llvm.mlir.constant(1 : i64) : i64
%209 = llvm.alloca %208 x i64 : (i64) -> !llvm.ptr
llvm.store %207, %209 : i64, !llvm.ptr
%210 = arith.constant 1 : i32
%212 = arith.extsi %210 : i32 to i64
%211 = arith.shli %212, %arg0 : i64
%213 = arith.constant 0 : i32
%214 = arith.extsi %213 : i32 to i64
%215 = llvm.mlir.constant(1 : i64) : i64
%216 = llvm.alloca %215 x i64 : (i64) -> !llvm.ptr
llvm.store %214, %216 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%217 = llvm.load %216 : !llvm.ptr -> i64
%218 = arith.cmpi slt, %217, %211 : i64
cf.cond_br %218, ^bb37, ^bb38
^bb37:
%219 = llvm.load %216 : !llvm.ptr -> i64
%220 = arith.constant 1 : i32
%222 = arith.extsi %220 : i32 to i64
%221 = arith.subi %arg0, %222 : i64
%223 = arith.shrsi %219, %221 : i64
%224 = arith.constant 1 : i32
%226 = arith.extsi %224 : i32 to i64
%225 = arith.andi %223, %226 : i64
%227 = arith.constant 0 : i32
%229 = arith.extsi %227 : i32 to i64
%228 = arith.cmpi ne, %225, %229 : i64
cf.cond_br %228, ^bb39, ^bb40
^bb39:
%231 = llvm.load %216 : !llvm.ptr -> i64
%230 = func.call @first_wins(%arg0, %231) : (i64, i64) -> i64
%232 = arith.constant 0 : i32
%234 = arith.extsi %232 : i32 to i64
%233 = arith.cmpi ne, %230, %234 : i64
cf.cond_br %233, ^bb42, ^bb43
^bb42:
%235 = arith.constant 0 : i32
%236 = arith.extsi %235 : i32 to i64
%237 = llvm.mlir.constant(1 : i64) : i64
%238 = llvm.alloca %237 x i64 : (i64) -> !llvm.ptr
llvm.store %236, %238 : i64, !llvm.ptr
%239 = arith.constant 0 : i32
%240 = arith.extsi %239 : i32 to i64
%241 = llvm.mlir.constant(1 : i64) : i64
%242 = llvm.alloca %241 x i64 : (i64) -> !llvm.ptr
llvm.store %240, %242 : i64, !llvm.ptr
cf.br ^bb45
^bb45:
%243 = llvm.load %242 : !llvm.ptr -> i64
%244 = arith.cmpi slt, %243, %arg0 : i64
cf.cond_br %244, ^bb46, ^bb47
^bb46:
%245 = llvm.load %216 : !llvm.ptr -> i64
%246 = arith.constant 1 : i32
%247 = llvm.load %242 : !llvm.ptr -> i64
%249 = arith.extsi %246 : i32 to i64
%248 = arith.shli %249, %247 : i64
%250 = arith.andi %245, %248 : i64
%251 = arith.constant 0 : i32
%253 = arith.extsi %251 : i32 to i64
%252 = arith.cmpi ne, %250, %253 : i64
cf.cond_br %252, ^bb48, ^bb49
^bb48:
%254 = llvm.load %238 : !llvm.ptr -> i64
%255 = arith.constant 1 : i32
%257 = arith.extsi %255 : i32 to i64
%256 = arith.addi %254, %257 : i64
llvm.store %256, %238 : i64, !llvm.ptr
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
%258 = llvm.load %242 : !llvm.ptr -> i64
%259 = arith.constant 1 : i32
%261 = arith.extsi %259 : i32 to i64
%260 = arith.addi %258, %261 : i64
llvm.store %260, %242 : i64, !llvm.ptr
cf.br ^bb45
^bb47:
%262 = llvm.load %209 : !llvm.ptr -> i64
%264 = llvm.load %238 : !llvm.ptr -> i64
%263 = func.call @ipow9(%264) : (i64) -> i64
%265 = arith.addi %262, %263 : i64
llvm.store %265, %209 : i64, !llvm.ptr
cf.br ^bb44
^bb43:
cf.br ^bb44
^bb44:
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
%266 = llvm.load %216 : !llvm.ptr -> i64
%267 = arith.constant 1 : i32
%269 = arith.extsi %267 : i32 to i64
%268 = arith.addi %266, %269 : i64
llvm.store %268, %216 : i64, !llvm.ptr
cf.br ^bb36
^bb38:
%270 = llvm.load %209 : !llvm.ptr -> i64
func.return %270 : i64
}
func.func @main() -> i32 {
%271 = arith.constant 19 : i32
%272 = arith.constant 1 : i32
%273 = arith.constant 18 : i32
%274 = arith.shli %272, %273 : i32
%275 = arith.muli %271, %274 : i32
%276 = arith.extsi %275 : i32 to i64
%278 = arith.constant 1 : i32
%279 = arith.extsi %278 : i32 to i64
%277 = func.call @calloc(%276, %279) : (i64, i64) -> !llvm.ptr
%280 = llvm.mlir.addressof @win_memo : !llvm.ptr
llvm.store %277, %280 : !llvm.ptr, !llvm.ptr
%282 = arith.constant 1 : i32
%283 = arith.extsi %282 : i32 to i64
%281 = func.call @calloc(%276, %283) : (i64, i64) -> !llvm.ptr
%284 = llvm.mlir.addressof @win_ready : !llvm.ptr
llvm.store %281, %284 : !llvm.ptr, !llvm.ptr
%285 = llvm.mlir.addressof @win_memo : !llvm.ptr
%286 = llvm.load %285 : !llvm.ptr -> !llvm.ptr
%287 = llvm.mlir.zero : !llvm.ptr
%288 = llvm.icmp "eq" %286, %287 : !llvm.ptr
%289 = scf.if %288 -> (i1) {
%290 = arith.constant true
scf.yield %290 : i1
} else {
%291 = llvm.mlir.addressof @win_ready : !llvm.ptr
%292 = llvm.load %291 : !llvm.ptr -> !llvm.ptr
%293 = llvm.mlir.zero : !llvm.ptr
%294 = llvm.icmp "eq" %292, %293 : !llvm.ptr
scf.yield %294 : i1
}
cf.cond_br %289, ^bb51, ^bb52
^bb51:
%295 = arith.constant 1 : i32
func.return %295 : i32
^bb52:
cf.br ^bb53
^bb53:
%296 = arith.constant 0 : i32
%297 = arith.extsi %296 : i32 to i64
%298 = llvm.mlir.constant(1 : i64) : i64
%299 = llvm.alloca %298 x i64 : (i64) -> !llvm.ptr
llvm.store %297, %299 : i64, !llvm.ptr
%300 = arith.constant 1 : i32
%301 = arith.extsi %300 : i32 to i64
%302 = llvm.mlir.constant(1 : i64) : i64
%303 = llvm.alloca %302 x i64 : (i64) -> !llvm.ptr
llvm.store %301, %303 : i64, !llvm.ptr
cf.br ^bb54
^bb54:
%304 = llvm.load %303 : !llvm.ptr -> i64
%305 = arith.constant 18 : i32
%307 = arith.extsi %305 : i32 to i64
%306 = arith.cmpi sle, %304, %307 : i64
cf.cond_br %306, ^bb55, ^bb56
^bb55:
%308 = llvm.load %299 : !llvm.ptr -> i64
%310 = llvm.load %303 : !llvm.ptr -> i64
%309 = func.call @W_digits(%310) : (i64) -> i64
%311 = arith.addi %308, %309 : i64
llvm.store %311, %299 : i64, !llvm.ptr
%312 = llvm.load %303 : !llvm.ptr -> i64
%313 = arith.constant 1 : i32
%315 = arith.extsi %313 : i32 to i64
%314 = arith.addi %312, %315 : i64
llvm.store %314, %303 : i64, !llvm.ptr
cf.br ^bb54
^bb56:
%316 = llvm.mlir.addressof @str_0 : !llvm.ptr
%317 = llvm.load %299 : !llvm.ptr -> i64
%318 = llvm.call @printf(%316, %317) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%320 = llvm.mlir.addressof @win_memo : !llvm.ptr
%321 = llvm.load %320 : !llvm.ptr -> !llvm.ptr
func.call @free(%321) : (!llvm.ptr) -> ()
%323 = llvm.mlir.addressof @win_ready : !llvm.ptr
%324 = llvm.load %323 : !llvm.ptr -> !llvm.ptr
func.call @free(%324) : (!llvm.ptr) -> ()
%325 = arith.constant 0 : i32
func.return %325 : i32
}
}