Problem 096
Sum of first three digits of each of 50 sudoku solutions (top-left). Iterative backtracking (heap stack) — deep recursion overflows the C stack.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^2) | O(n!) |
|---|
| Space complexity | O(1) | O(n^2) |
|---|
| Approach | Flow solution | Backtracking search |
|---|
| Verdict | Optimal |
|---|
Flow source
# Project Euler 096
# Sum of first three digits of each of 50 sudoku solutions (top-left).
# Iterative backtracking (heap stack) — deep recursion overflows the C stack.
extern {
function fopen(path: string, mode: string) -> ptr<void>
function fgetc(f: ptr<void>) -> i32
function fclose(f: ptr<void>) -> i32
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function solve_iter(grid: ptr<i32>) -> bool {
let row: ptr<i32> = calloc(9, 4)
let col: ptr<i32> = calloc(9, 4)
let box: ptr<i32> = calloc(9, 4)
# stack frames: position, digit tried
let st_pos: ptr<i32> = calloc(81, 4)
let st_dig: ptr<i32> = calloc(81, 4)
if row == null || col == null || box == null || st_pos == null || st_dig == null {
return false
}
let mut i: i32 = 0
while i < 81 {
let v: i32 = grid[i]
if v != 0 {
let m: i32 = 1 << (v - 1)
let r: i32 = i / 9
let c: i32 = i % 9
let b: i32 = (r / 3) * 3 + c / 3
row[r] = row[r] | m
col[c] = col[c] | m
box[b] = box[b] | m
}
i = i + 1
}
# find first empty
let mut pos: i32 = 0
while pos < 81 && grid[pos] != 0 {
pos = pos + 1
}
if pos == 81 {
free(row)
free(col)
free(box)
free(st_pos)
free(st_dig)
return true
}
let mut sp: i32 = 0
st_pos[0] = pos
st_dig[0] = 1
while sp >= 0 {
pos = st_pos[sp]
let r: i32 = pos / 9
let c: i32 = pos % 9
let b: i32 = (r / 3) * 3 + c / 3
# undo previous try at this frame if any
if grid[pos] != 0 {
let old: i32 = grid[pos]
let om: i32 = 1 << (old - 1)
row[r] = row[r] ^ om
col[c] = col[c] ^ om
box[b] = box[b] ^ om
grid[pos] = 0
}
let used: i32 = row[r] | col[c] | box[b]
let mut d: i32 = st_dig[sp]
let mut found: bool = false
while d <= 9 {
let m: i32 = 1 << (d - 1)
if (used & m) == 0 {
grid[pos] = d
row[r] = row[r] | m
col[c] = col[c] | m
box[b] = box[b] | m
st_dig[sp] = d + 1
# advance to next empty
let mut np: i32 = pos + 1
while np < 81 && grid[np] != 0 {
np = np + 1
}
if np == 81 {
free(row)
free(col)
free(box)
free(st_pos)
free(st_dig)
return true
}
sp = sp + 1
st_pos[sp] = np
st_dig[sp] = 1
found = true
break
}
d = d + 1
}
if !found {
st_dig[sp] = 1
sp = sp - 1
}
}
free(row)
free(col)
free(box)
free(st_pos)
free(st_dig)
return false
}
function main() -> i32 {
let f: ptr<void> = fopen("data/p096.txt", "r")
if f == null {
printf("failed to read data/p096.txt\n")
return 1
}
let grid: ptr<i32> = calloc(81, 4)
if grid == null { return 1 }
let mut total: i64 = 0
let mut c: i32 = fgetc(f)
let mut puzzles: i32 = 0
while c >= 0 && puzzles < 50 {
# Skip "Grid XX" header line (must not treat its digits as cells).
if c == 10 {
c = fgetc(f)
}
while c >= 0 && c != 10 {
c = fgetc(f)
}
if c == 10 {
c = fgetc(f)
}
let mut i: i32 = 0
while i < 81 && c >= 0 {
if c >= 48 && c <= 57 {
grid[i] = c - 48
i = i + 1
}
c = fgetc(f)
}
if i == 81 {
if solve_iter(grid) {
total = total + (grid[0] as i64) * 100 + (grid[1] as i64) * 10 + (grid[2] as i64)
}
puzzles = puzzles + 1
}
}
fclose(f)
printf("%lld\n", total)
free(grid)
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; }
bool solve_iter_ptr_i32(int32_t* grid);
int32_t main(void);
bool solve_iter_ptr_i32(int32_t* grid) {
int32_t* row = (int32_t*)(calloc(9, 4));
int32_t* col = (int32_t*)(calloc(9, 4));
int32_t* box = (int32_t*)(calloc(9, 4));
int32_t* st_pos = (int32_t*)(calloc(81, 4));
int32_t* st_dig = (int32_t*)(calloc(81, 4));
if (((((row == NULL || col == NULL) || box == NULL) || st_pos == NULL) || st_dig == NULL)) {
return 0;
}
int32_t i = 0;
while (i < 81) {
int32_t v = grid[i];
if (v != 0) {
int32_t m = FLOW_CHECKED_SHL((1), ((v - 1)));
int32_t r = FLOW_CHECKED_DIV((i), (9));
int32_t c = FLOW_CHECKED_MOD((i), (9));
int32_t b = ((FLOW_CHECKED_DIV((r), (3)) * 3) + FLOW_CHECKED_DIV((c), (3)));
row[r] = (row[r] | m);
col[c] = (col[c] | m);
box[b] = (box[b] | m);
}
i = (i + 1);
}
int32_t pos = 0;
while ((pos < 81 && grid[pos] != 0)) {
pos = (pos + 1);
}
if (pos == 81) {
free(row);
free(col);
free(box);
free(st_pos);
free(st_dig);
return 1;
}
int32_t sp = 0;
st_pos[0] = pos;
st_dig[0] = 1;
while (sp >= 0) {
pos = st_pos[sp];
int32_t r = FLOW_CHECKED_DIV((pos), (9));
int32_t c = FLOW_CHECKED_MOD((pos), (9));
int32_t b = ((FLOW_CHECKED_DIV((r), (3)) * 3) + FLOW_CHECKED_DIV((c), (3)));
if (grid[pos] != 0) {
int32_t old = grid[pos];
int32_t om = FLOW_CHECKED_SHL((1), ((old - 1)));
row[r] = (row[r] ^ om);
col[c] = (col[c] ^ om);
box[b] = (box[b] ^ om);
grid[pos] = 0;
}
int32_t used = ((row[r] | col[c]) | box[b]);
int32_t d = st_dig[sp];
bool found = 0;
while (d <= 9) {
int32_t m = FLOW_CHECKED_SHL((1), ((d - 1)));
if ((used & m) == 0) {
grid[pos] = d;
row[r] = (row[r] | m);
col[c] = (col[c] | m);
box[b] = (box[b] | m);
st_dig[sp] = (d + 1);
int32_t np = (pos + 1);
while ((np < 81 && grid[np] != 0)) {
np = (np + 1);
}
if (np == 81) {
free(row);
free(col);
free(box);
free(st_pos);
free(st_dig);
return 1;
}
sp = (sp + 1);
st_pos[sp] = np;
st_dig[sp] = 1;
found = 1;
break;
}
d = (d + 1);
}
if ((!(found))) {
st_dig[sp] = 1;
sp = (sp - 1);
}
}
free(row);
free(col);
free(box);
free(st_pos);
free(st_dig);
return 0;
}
int32_t main(void) {
void* f = (void*)(fopen("data/p096.txt", "r"));
if (f == NULL) {
printf("failed to read data/p096.txt\n");
return 1;
}
int32_t* grid = (int32_t*)(calloc(81, 4));
if (grid == NULL) {
return 1;
}
int64_t total = 0;
int32_t c = fgetc(f);
int32_t puzzles = 0;
while ((c >= 0 && puzzles < 50)) {
if (c == 10) {
c = fgetc(f);
}
while ((c >= 0 && c != 10)) {
c = fgetc(f);
}
if (c == 10) {
c = fgetc(f);
}
int32_t i = 0;
while ((i < 81 && c >= 0)) {
if ((c >= 48 && c <= 57)) {
grid[i] = (c - 48);
i = (i + 1);
}
c = fgetc(f);
}
if (i == 81) {
if (solve_iter_ptr_i32(grid)) {
total = (((total + (((int64_t)(grid[0])) * 100)) + (((int64_t)(grid[1])) * 10)) + ((int64_t)(grid[2])));
}
puzzles = (puzzles + 1);
}
}
fclose(f);
printf("%lld\n", total);
free(grid);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("data/p096.txt\00") {addr_space = 0 : i32} : !llvm.array<14 x i8>
llvm.mlir.global internal constant @str_1("r\00") {addr_space = 0 : i32} : !llvm.array<2 x i8>
llvm.mlir.global internal constant @str_2("failed to read data/p096.txt\n\00") {addr_space = 0 : i32} : !llvm.array<30 x i8>
llvm.mlir.global internal constant @str_3("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func private @fopen(!llvm.ptr, !llvm.ptr) -> !llvm.ptr
func.func private @fgetc(!llvm.ptr) -> i32
func.func private @fclose(!llvm.ptr) -> i32
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func @solve_iter(%arg0: !llvm.ptr) -> i1 {
%1 = arith.constant 9 : i32
%2 = arith.constant 4 : i32
%3 = arith.extsi %1 : i32 to i64
%4 = arith.extsi %2 : i32 to i64
%0 = func.call @calloc(%3, %4) : (i64, i64) -> !llvm.ptr
%6 = arith.constant 9 : i32
%7 = arith.constant 4 : i32
%8 = arith.extsi %6 : i32 to i64
%9 = arith.extsi %7 : i32 to i64
%5 = func.call @calloc(%8, %9) : (i64, i64) -> !llvm.ptr
%11 = arith.constant 9 : i32
%12 = arith.constant 4 : i32
%13 = arith.extsi %11 : i32 to i64
%14 = arith.extsi %12 : i32 to i64
%10 = func.call @calloc(%13, %14) : (i64, i64) -> !llvm.ptr
%16 = arith.constant 81 : i32
%17 = arith.constant 4 : i32
%18 = arith.extsi %16 : i32 to i64
%19 = arith.extsi %17 : i32 to i64
%15 = func.call @calloc(%18, %19) : (i64, i64) -> !llvm.ptr
%21 = arith.constant 81 : i32
%22 = arith.constant 4 : i32
%23 = arith.extsi %21 : i32 to i64
%24 = arith.extsi %22 : i32 to i64
%20 = func.call @calloc(%23, %24) : (i64, i64) -> !llvm.ptr
%25 = llvm.mlir.zero : !llvm.ptr
%26 = llvm.icmp "eq" %0, %25 : !llvm.ptr
%27 = scf.if %26 -> (i1) {
%28 = arith.constant true
scf.yield %28 : i1
} else {
%29 = llvm.mlir.zero : !llvm.ptr
%30 = llvm.icmp "eq" %5, %29 : !llvm.ptr
scf.yield %30 : i1
}
%31 = scf.if %27 -> (i1) {
%32 = arith.constant true
scf.yield %32 : i1
} else {
%33 = llvm.mlir.zero : !llvm.ptr
%34 = llvm.icmp "eq" %10, %33 : !llvm.ptr
scf.yield %34 : i1
}
%35 = scf.if %31 -> (i1) {
%36 = arith.constant true
scf.yield %36 : i1
} else {
%37 = llvm.mlir.zero : !llvm.ptr
%38 = llvm.icmp "eq" %15, %37 : !llvm.ptr
scf.yield %38 : i1
}
%39 = scf.if %35 -> (i1) {
%40 = arith.constant true
scf.yield %40 : i1
} else {
%41 = llvm.mlir.zero : !llvm.ptr
%42 = llvm.icmp "eq" %20, %41 : !llvm.ptr
scf.yield %42 : i1
}
cf.cond_br %39, ^bb0, ^bb1
^bb0:
%43 = arith.constant 0 : i1
func.return %43 : i1
^bb1:
cf.br ^bb2
^bb2:
%44 = arith.constant 0 : i32
%45 = llvm.mlir.constant(1 : i64) : i64
%46 = llvm.alloca %45 x i32 : (i64) -> !llvm.ptr
llvm.store %44, %46 : i32, !llvm.ptr
cf.br ^bb3
^bb3:
%47 = llvm.load %46 : !llvm.ptr -> i32
%48 = arith.constant 81 : i32
%49 = arith.cmpi slt, %47, %48 : i32
cf.cond_br %49, ^bb4, ^bb5
^bb4:
%51 = llvm.load %46 : !llvm.ptr -> i32
%52 = arith.extsi %51 : i32 to i64
%53 = llvm.getelementptr %arg0[%52] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%50 = llvm.load %53 : !llvm.ptr -> i32
%54 = arith.constant 0 : i32
%55 = arith.cmpi ne, %50, %54 : i32
cf.cond_br %55, ^bb6, ^bb7
^bb6:
%56 = arith.constant 1 : i32
%57 = arith.constant 1 : i32
%58 = arith.subi %50, %57 : i32
%59 = arith.shli %56, %58 : i32
%60 = llvm.load %46 : !llvm.ptr -> i32
%61 = arith.constant 9 : i32
%62 = arith.divsi %60, %61 : i32
%63 = llvm.load %46 : !llvm.ptr -> i32
%64 = arith.constant 9 : i32
%65 = arith.remsi %63, %64 : i32
%66 = arith.constant 3 : i32
%67 = arith.divsi %62, %66 : i32
%68 = arith.constant 3 : i32
%69 = arith.muli %67, %68 : i32
%70 = arith.constant 3 : i32
%71 = arith.divsi %65, %70 : i32
%72 = arith.addi %69, %71 : i32
%74 = arith.extsi %62 : i32 to i64
%75 = llvm.getelementptr %0[%74] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%73 = llvm.load %75 : !llvm.ptr -> i32
%76 = arith.ori %73, %59 : i32
%77 = arith.extsi %62 : i32 to i64
%78 = llvm.getelementptr %0[%77] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %76, %78 : i32, !llvm.ptr
%80 = arith.extsi %65 : i32 to i64
%81 = llvm.getelementptr %5[%80] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%79 = llvm.load %81 : !llvm.ptr -> i32
%82 = arith.ori %79, %59 : i32
%83 = arith.extsi %65 : i32 to i64
%84 = llvm.getelementptr %5[%83] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %82, %84 : i32, !llvm.ptr
%86 = arith.extsi %72 : i32 to i64
%87 = llvm.getelementptr %10[%86] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%85 = llvm.load %87 : !llvm.ptr -> i32
%88 = arith.ori %85, %59 : i32
%89 = arith.extsi %72 : i32 to i64
%90 = llvm.getelementptr %10[%89] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %88, %90 : i32, !llvm.ptr
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
%91 = llvm.load %46 : !llvm.ptr -> i32
%92 = arith.constant 1 : i32
%93 = arith.addi %91, %92 : i32
llvm.store %93, %46 : i32, !llvm.ptr
cf.br ^bb3
^bb5:
%94 = arith.constant 0 : i32
%95 = llvm.mlir.constant(1 : i64) : i64
%96 = llvm.alloca %95 x i32 : (i64) -> !llvm.ptr
llvm.store %94, %96 : i32, !llvm.ptr
cf.br ^bb9
^bb9:
%97 = llvm.load %96 : !llvm.ptr -> i32
%98 = arith.constant 81 : i32
%99 = arith.cmpi slt, %97, %98 : i32
%100 = scf.if %99 -> (i1) {
%102 = llvm.load %96 : !llvm.ptr -> i32
%103 = arith.extsi %102 : i32 to i64
%104 = llvm.getelementptr %arg0[%103] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%101 = llvm.load %104 : !llvm.ptr -> i32
%105 = arith.constant 0 : i32
%106 = arith.cmpi ne, %101, %105 : i32
scf.yield %106 : i1
} else {
%107 = arith.constant false
scf.yield %107 : i1
}
cf.cond_br %100, ^bb10, ^bb11
^bb10:
%108 = llvm.load %96 : !llvm.ptr -> i32
%109 = arith.constant 1 : i32
%110 = arith.addi %108, %109 : i32
llvm.store %110, %96 : i32, !llvm.ptr
cf.br ^bb9
^bb11:
%111 = llvm.load %96 : !llvm.ptr -> i32
%112 = arith.constant 81 : i32
%113 = arith.cmpi eq, %111, %112 : i32
cf.cond_br %113, ^bb12, ^bb13
^bb12:
func.call @free(%0) : (!llvm.ptr) -> ()
func.call @free(%5) : (!llvm.ptr) -> ()
func.call @free(%10) : (!llvm.ptr) -> ()
func.call @free(%15) : (!llvm.ptr) -> ()
func.call @free(%20) : (!llvm.ptr) -> ()
%119 = arith.constant 1 : i1
func.return %119 : i1
^bb13:
cf.br ^bb14
^bb14:
%120 = arith.constant 0 : i32
%121 = llvm.mlir.constant(1 : i64) : i64
%122 = llvm.alloca %121 x i32 : (i64) -> !llvm.ptr
llvm.store %120, %122 : i32, !llvm.ptr
%123 = llvm.load %96 : !llvm.ptr -> i32
%124 = arith.constant 0 : i32
%125 = arith.extsi %124 : i32 to i64
%126 = llvm.getelementptr %15[%125] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %123, %126 : i32, !llvm.ptr
%127 = arith.constant 1 : i32
%128 = arith.constant 0 : i32
%129 = arith.extsi %128 : i32 to i64
%130 = llvm.getelementptr %20[%129] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %127, %130 : i32, !llvm.ptr
cf.br ^bb15
^bb15:
%131 = llvm.load %122 : !llvm.ptr -> i32
%132 = arith.constant 0 : i32
%133 = arith.cmpi sge, %131, %132 : i32
cf.cond_br %133, ^bb16, ^bb17
^bb16:
%135 = llvm.load %122 : !llvm.ptr -> i32
%136 = arith.extsi %135 : i32 to i64
%137 = llvm.getelementptr %15[%136] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%134 = llvm.load %137 : !llvm.ptr -> i32
llvm.store %134, %96 : i32, !llvm.ptr
%138 = llvm.load %96 : !llvm.ptr -> i32
%139 = arith.constant 9 : i32
%140 = arith.divsi %138, %139 : i32
%141 = llvm.load %96 : !llvm.ptr -> i32
%142 = arith.constant 9 : i32
%143 = arith.remsi %141, %142 : i32
%144 = arith.constant 3 : i32
%145 = arith.divsi %140, %144 : i32
%146 = arith.constant 3 : i32
%147 = arith.muli %145, %146 : i32
%148 = arith.constant 3 : i32
%149 = arith.divsi %143, %148 : i32
%150 = arith.addi %147, %149 : i32
%152 = llvm.load %96 : !llvm.ptr -> i32
%153 = arith.extsi %152 : i32 to i64
%154 = llvm.getelementptr %arg0[%153] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%151 = llvm.load %154 : !llvm.ptr -> i32
%155 = arith.constant 0 : i32
%156 = arith.cmpi ne, %151, %155 : i32
cf.cond_br %156, ^bb18, ^bb19
^bb18:
%158 = llvm.load %96 : !llvm.ptr -> i32
%159 = arith.extsi %158 : i32 to i64
%160 = llvm.getelementptr %arg0[%159] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%157 = llvm.load %160 : !llvm.ptr -> i32
%161 = arith.constant 1 : i32
%162 = arith.constant 1 : i32
%163 = arith.subi %157, %162 : i32
%164 = arith.shli %161, %163 : i32
%166 = arith.extsi %140 : i32 to i64
%167 = llvm.getelementptr %0[%166] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%165 = llvm.load %167 : !llvm.ptr -> i32
%168 = arith.xori %165, %164 : i32
%169 = arith.extsi %140 : i32 to i64
%170 = llvm.getelementptr %0[%169] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %168, %170 : i32, !llvm.ptr
%172 = arith.extsi %143 : i32 to i64
%173 = llvm.getelementptr %5[%172] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%171 = llvm.load %173 : !llvm.ptr -> i32
%174 = arith.xori %171, %164 : i32
%175 = arith.extsi %143 : i32 to i64
%176 = llvm.getelementptr %5[%175] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %174, %176 : i32, !llvm.ptr
%178 = arith.extsi %150 : i32 to i64
%179 = llvm.getelementptr %10[%178] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%177 = llvm.load %179 : !llvm.ptr -> i32
%180 = arith.xori %177, %164 : i32
%181 = arith.extsi %150 : i32 to i64
%182 = llvm.getelementptr %10[%181] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %180, %182 : i32, !llvm.ptr
%183 = arith.constant 0 : i32
%184 = llvm.load %96 : !llvm.ptr -> i32
%185 = arith.extsi %184 : i32 to i64
%186 = llvm.getelementptr %arg0[%185] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %183, %186 : i32, !llvm.ptr
cf.br ^bb20
^bb19:
cf.br ^bb20
^bb20:
%188 = arith.extsi %140 : i32 to i64
%189 = llvm.getelementptr %0[%188] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%187 = llvm.load %189 : !llvm.ptr -> i32
%191 = arith.extsi %143 : i32 to i64
%192 = llvm.getelementptr %5[%191] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%190 = llvm.load %192 : !llvm.ptr -> i32
%193 = arith.ori %187, %190 : i32
%195 = arith.extsi %150 : i32 to i64
%196 = llvm.getelementptr %10[%195] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%194 = llvm.load %196 : !llvm.ptr -> i32
%197 = arith.ori %193, %194 : i32
%199 = llvm.load %122 : !llvm.ptr -> i32
%200 = arith.extsi %199 : i32 to i64
%201 = llvm.getelementptr %20[%200] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%198 = llvm.load %201 : !llvm.ptr -> i32
%202 = llvm.mlir.constant(1 : i64) : i64
%203 = llvm.alloca %202 x i32 : (i64) -> !llvm.ptr
llvm.store %198, %203 : i32, !llvm.ptr
%204 = arith.constant 0 : i1
%205 = llvm.mlir.constant(1 : i64) : i64
%206 = llvm.alloca %205 x i1 : (i64) -> !llvm.ptr
llvm.store %204, %206 : i1, !llvm.ptr
cf.br ^bb21
^bb21:
%207 = llvm.load %203 : !llvm.ptr -> i32
%208 = arith.constant 9 : i32
%209 = arith.cmpi sle, %207, %208 : i32
cf.cond_br %209, ^bb22, ^bb23
^bb22:
%210 = arith.constant 1 : i32
%211 = llvm.load %203 : !llvm.ptr -> i32
%212 = arith.constant 1 : i32
%213 = arith.subi %211, %212 : i32
%214 = arith.shli %210, %213 : i32
%215 = arith.andi %197, %214 : i32
%216 = arith.constant 0 : i32
%217 = arith.cmpi eq, %215, %216 : i32
cf.cond_br %217, ^bb24, ^bb25
^bb24:
%218 = llvm.load %203 : !llvm.ptr -> i32
%219 = llvm.load %96 : !llvm.ptr -> i32
%220 = arith.extsi %219 : i32 to i64
%221 = llvm.getelementptr %arg0[%220] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %218, %221 : i32, !llvm.ptr
%223 = arith.extsi %140 : i32 to i64
%224 = llvm.getelementptr %0[%223] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%222 = llvm.load %224 : !llvm.ptr -> i32
%225 = arith.ori %222, %214 : i32
%226 = arith.extsi %140 : i32 to i64
%227 = llvm.getelementptr %0[%226] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %225, %227 : i32, !llvm.ptr
%229 = arith.extsi %143 : i32 to i64
%230 = llvm.getelementptr %5[%229] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%228 = llvm.load %230 : !llvm.ptr -> i32
%231 = arith.ori %228, %214 : i32
%232 = arith.extsi %143 : i32 to i64
%233 = llvm.getelementptr %5[%232] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %231, %233 : i32, !llvm.ptr
%235 = arith.extsi %150 : i32 to i64
%236 = llvm.getelementptr %10[%235] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%234 = llvm.load %236 : !llvm.ptr -> i32
%237 = arith.ori %234, %214 : i32
%238 = arith.extsi %150 : i32 to i64
%239 = llvm.getelementptr %10[%238] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %237, %239 : i32, !llvm.ptr
%240 = llvm.load %203 : !llvm.ptr -> i32
%241 = arith.constant 1 : i32
%242 = arith.addi %240, %241 : i32
%243 = llvm.load %122 : !llvm.ptr -> i32
%244 = arith.extsi %243 : i32 to i64
%245 = llvm.getelementptr %20[%244] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %242, %245 : i32, !llvm.ptr
%246 = llvm.load %96 : !llvm.ptr -> i32
%247 = arith.constant 1 : i32
%248 = arith.addi %246, %247 : i32
%249 = llvm.mlir.constant(1 : i64) : i64
%250 = llvm.alloca %249 x i32 : (i64) -> !llvm.ptr
llvm.store %248, %250 : i32, !llvm.ptr
cf.br ^bb27
^bb27:
%251 = llvm.load %250 : !llvm.ptr -> i32
%252 = arith.constant 81 : i32
%253 = arith.cmpi slt, %251, %252 : i32
%254 = scf.if %253 -> (i1) {
%256 = llvm.load %250 : !llvm.ptr -> i32
%257 = arith.extsi %256 : i32 to i64
%258 = llvm.getelementptr %arg0[%257] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%255 = llvm.load %258 : !llvm.ptr -> i32
%259 = arith.constant 0 : i32
%260 = arith.cmpi ne, %255, %259 : i32
scf.yield %260 : i1
} else {
%261 = arith.constant false
scf.yield %261 : i1
}
cf.cond_br %254, ^bb28, ^bb29
^bb28:
%262 = llvm.load %250 : !llvm.ptr -> i32
%263 = arith.constant 1 : i32
%264 = arith.addi %262, %263 : i32
llvm.store %264, %250 : i32, !llvm.ptr
cf.br ^bb27
^bb29:
%265 = llvm.load %250 : !llvm.ptr -> i32
%266 = arith.constant 81 : i32
%267 = arith.cmpi eq, %265, %266 : i32
cf.cond_br %267, ^bb30, ^bb31
^bb30:
func.call @free(%0) : (!llvm.ptr) -> ()
func.call @free(%5) : (!llvm.ptr) -> ()
func.call @free(%10) : (!llvm.ptr) -> ()
func.call @free(%15) : (!llvm.ptr) -> ()
func.call @free(%20) : (!llvm.ptr) -> ()
%273 = arith.constant 1 : i1
func.return %273 : i1
^bb31:
cf.br ^bb32
^bb32:
%274 = llvm.load %122 : !llvm.ptr -> i32
%275 = arith.constant 1 : i32
%276 = arith.addi %274, %275 : i32
llvm.store %276, %122 : i32, !llvm.ptr
%277 = llvm.load %250 : !llvm.ptr -> i32
%278 = llvm.load %122 : !llvm.ptr -> i32
%279 = arith.extsi %278 : i32 to i64
%280 = llvm.getelementptr %15[%279] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %277, %280 : i32, !llvm.ptr
%281 = arith.constant 1 : i32
%282 = llvm.load %122 : !llvm.ptr -> i32
%283 = arith.extsi %282 : i32 to i64
%284 = llvm.getelementptr %20[%283] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %281, %284 : i32, !llvm.ptr
%285 = arith.constant 1 : i1
llvm.store %285, %206 : i1, !llvm.ptr
cf.br ^bb23
^bb25:
cf.br ^bb26
^bb26:
%286 = llvm.load %203 : !llvm.ptr -> i32
%287 = arith.constant 1 : i32
%288 = arith.addi %286, %287 : i32
llvm.store %288, %203 : i32, !llvm.ptr
cf.br ^bb21
^bb23:
%289 = llvm.load %206 : !llvm.ptr -> i1
%291 = arith.constant 1 : i1
%290 = arith.xori %289, %291 : i1
cf.cond_br %290, ^bb33, ^bb34
^bb33:
%293 = arith.constant 1 : i32
%294 = llvm.load %122 : !llvm.ptr -> i32
%295 = arith.extsi %294 : i32 to i64
%296 = llvm.getelementptr %20[%295] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %293, %296 : i32, !llvm.ptr
%297 = llvm.load %122 : !llvm.ptr -> i32
%298 = arith.constant 1 : i32
%299 = arith.subi %297, %298 : i32
llvm.store %299, %122 : i32, !llvm.ptr
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
cf.br ^bb15
^bb17:
func.call @free(%0) : (!llvm.ptr) -> ()
func.call @free(%5) : (!llvm.ptr) -> ()
func.call @free(%10) : (!llvm.ptr) -> ()
func.call @free(%15) : (!llvm.ptr) -> ()
func.call @free(%20) : (!llvm.ptr) -> ()
%305 = arith.constant 0 : i1
func.return %305 : i1
}
func.func @main() -> i32 {
%307 = llvm.mlir.addressof @str_0 : !llvm.ptr
%308 = llvm.mlir.addressof @str_1 : !llvm.ptr
%306 = func.call @fopen(%307, %308) : (!llvm.ptr, !llvm.ptr) -> !llvm.ptr
%309 = llvm.mlir.zero : !llvm.ptr
%310 = llvm.icmp "eq" %306, %309 : !llvm.ptr
cf.cond_br %310, ^bb36, ^bb37
^bb36:
%311 = llvm.mlir.addressof @str_2 : !llvm.ptr
%312 = llvm.call @printf(%311) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr) -> i32
%313 = arith.constant 1 : i32
func.return %313 : i32
^bb37:
cf.br ^bb38
^bb38:
%315 = arith.constant 81 : i32
%316 = arith.constant 4 : i32
%317 = arith.extsi %315 : i32 to i64
%318 = arith.extsi %316 : i32 to i64
%314 = func.call @calloc(%317, %318) : (i64, i64) -> !llvm.ptr
%319 = llvm.mlir.zero : !llvm.ptr
%320 = llvm.icmp "eq" %314, %319 : !llvm.ptr
cf.cond_br %320, ^bb39, ^bb40
^bb39:
%321 = arith.constant 1 : i32
func.return %321 : i32
^bb40:
cf.br ^bb41
^bb41:
%322 = arith.constant 0 : i32
%323 = arith.extsi %322 : i32 to i64
%324 = llvm.mlir.constant(1 : i64) : i64
%325 = llvm.alloca %324 x i64 : (i64) -> !llvm.ptr
llvm.store %323, %325 : i64, !llvm.ptr
%326 = func.call @fgetc(%306) : (!llvm.ptr) -> i32
%327 = llvm.mlir.constant(1 : i64) : i64
%328 = llvm.alloca %327 x i32 : (i64) -> !llvm.ptr
llvm.store %326, %328 : i32, !llvm.ptr
%329 = arith.constant 0 : i32
%330 = llvm.mlir.constant(1 : i64) : i64
%331 = llvm.alloca %330 x i32 : (i64) -> !llvm.ptr
llvm.store %329, %331 : i32, !llvm.ptr
cf.br ^bb42
^bb42:
%332 = llvm.load %328 : !llvm.ptr -> i32
%333 = arith.constant 0 : i32
%334 = arith.cmpi sge, %332, %333 : i32
%335 = scf.if %334 -> (i1) {
%336 = llvm.load %331 : !llvm.ptr -> i32
%337 = arith.constant 50 : i32
%338 = arith.cmpi slt, %336, %337 : i32
scf.yield %338 : i1
} else {
%339 = arith.constant false
scf.yield %339 : i1
}
cf.cond_br %335, ^bb43, ^bb44
^bb43:
%340 = llvm.load %328 : !llvm.ptr -> i32
%341 = arith.constant 10 : i32
%342 = arith.cmpi eq, %340, %341 : i32
cf.cond_br %342, ^bb45, ^bb46
^bb45:
%343 = func.call @fgetc(%306) : (!llvm.ptr) -> i32
llvm.store %343, %328 : i32, !llvm.ptr
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
cf.br ^bb48
^bb48:
%344 = llvm.load %328 : !llvm.ptr -> i32
%345 = arith.constant 0 : i32
%346 = arith.cmpi sge, %344, %345 : i32
%347 = scf.if %346 -> (i1) {
%348 = llvm.load %328 : !llvm.ptr -> i32
%349 = arith.constant 10 : i32
%350 = arith.cmpi ne, %348, %349 : i32
scf.yield %350 : i1
} else {
%351 = arith.constant false
scf.yield %351 : i1
}
cf.cond_br %347, ^bb49, ^bb50
^bb49:
%352 = func.call @fgetc(%306) : (!llvm.ptr) -> i32
llvm.store %352, %328 : i32, !llvm.ptr
cf.br ^bb48
^bb50:
%353 = llvm.load %328 : !llvm.ptr -> i32
%354 = arith.constant 10 : i32
%355 = arith.cmpi eq, %353, %354 : i32
cf.cond_br %355, ^bb51, ^bb52
^bb51:
%356 = func.call @fgetc(%306) : (!llvm.ptr) -> i32
llvm.store %356, %328 : i32, !llvm.ptr
cf.br ^bb53
^bb52:
cf.br ^bb53
^bb53:
%357 = arith.constant 0 : i32
%358 = llvm.mlir.constant(1 : i64) : i64
%359 = llvm.alloca %358 x i32 : (i64) -> !llvm.ptr
llvm.store %357, %359 : i32, !llvm.ptr
cf.br ^bb54
^bb54:
%360 = llvm.load %359 : !llvm.ptr -> i32
%361 = arith.constant 81 : i32
%362 = arith.cmpi slt, %360, %361 : i32
%363 = scf.if %362 -> (i1) {
%364 = llvm.load %328 : !llvm.ptr -> i32
%365 = arith.constant 0 : i32
%366 = arith.cmpi sge, %364, %365 : i32
scf.yield %366 : i1
} else {
%367 = arith.constant false
scf.yield %367 : i1
}
cf.cond_br %363, ^bb55, ^bb56
^bb55:
%368 = llvm.load %328 : !llvm.ptr -> i32
%369 = arith.constant 48 : i32
%370 = arith.cmpi sge, %368, %369 : i32
%371 = scf.if %370 -> (i1) {
%372 = llvm.load %328 : !llvm.ptr -> i32
%373 = arith.constant 57 : i32
%374 = arith.cmpi sle, %372, %373 : i32
scf.yield %374 : i1
} else {
%375 = arith.constant false
scf.yield %375 : i1
}
cf.cond_br %371, ^bb57, ^bb58
^bb57:
%376 = llvm.load %328 : !llvm.ptr -> i32
%377 = arith.constant 48 : i32
%378 = arith.subi %376, %377 : i32
%379 = llvm.load %359 : !llvm.ptr -> i32
%380 = arith.extsi %379 : i32 to i64
%381 = llvm.getelementptr %314[%380] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %378, %381 : i32, !llvm.ptr
%382 = llvm.load %359 : !llvm.ptr -> i32
%383 = arith.constant 1 : i32
%384 = arith.addi %382, %383 : i32
llvm.store %384, %359 : i32, !llvm.ptr
cf.br ^bb59
^bb58:
cf.br ^bb59
^bb59:
%385 = func.call @fgetc(%306) : (!llvm.ptr) -> i32
llvm.store %385, %328 : i32, !llvm.ptr
cf.br ^bb54
^bb56:
%386 = llvm.load %359 : !llvm.ptr -> i32
%387 = arith.constant 81 : i32
%388 = arith.cmpi eq, %386, %387 : i32
cf.cond_br %388, ^bb60, ^bb61
^bb60:
%389 = func.call @solve_iter(%314) : (!llvm.ptr) -> i1
cf.cond_br %389, ^bb63, ^bb64
^bb63:
%390 = llvm.load %325 : !llvm.ptr -> i64
%392 = arith.constant 0 : i32
%393 = arith.extsi %392 : i32 to i64
%394 = llvm.getelementptr %314[%393] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%391 = llvm.load %394 : !llvm.ptr -> i32
%395 = arith.extsi %391 : i32 to i64
%396 = arith.constant 100 : i32
%398 = arith.extsi %396 : i32 to i64
%397 = arith.muli %395, %398 : i64
%399 = arith.addi %390, %397 : i64
%401 = arith.constant 1 : i32
%402 = arith.extsi %401 : i32 to i64
%403 = llvm.getelementptr %314[%402] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%400 = llvm.load %403 : !llvm.ptr -> i32
%404 = arith.extsi %400 : i32 to i64
%405 = arith.constant 10 : i32
%407 = arith.extsi %405 : i32 to i64
%406 = arith.muli %404, %407 : i64
%408 = arith.addi %399, %406 : i64
%410 = arith.constant 2 : i32
%411 = arith.extsi %410 : i32 to i64
%412 = llvm.getelementptr %314[%411] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%409 = llvm.load %412 : !llvm.ptr -> i32
%413 = arith.extsi %409 : i32 to i64
%414 = arith.addi %408, %413 : i64
llvm.store %414, %325 : i64, !llvm.ptr
cf.br ^bb65
^bb64:
cf.br ^bb65
^bb65:
%415 = llvm.load %331 : !llvm.ptr -> i32
%416 = arith.constant 1 : i32
%417 = arith.addi %415, %416 : i32
llvm.store %417, %331 : i32, !llvm.ptr
cf.br ^bb62
^bb61:
cf.br ^bb62
^bb62:
cf.br ^bb42
^bb44:
%418 = func.call @fclose(%306) : (!llvm.ptr) -> i32
%419 = llvm.mlir.addressof @str_3 : !llvm.ptr
%420 = llvm.load %325 : !llvm.ptr -> i64
%421 = llvm.call @printf(%419, %420) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%314) : (!llvm.ptr) -> ()
%423 = arith.constant 0 : i32
func.return %423 : i32
}
}