Problem 186
Calls until PM's friends reach 99% of network (Lagged Fibonacci + DSU).
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^2) | O(log n) |
|---|
| Space complexity | O(n) | O(1) |
|---|
| Approach | Flow solution | Matrix exponentiation |
|---|
| Verdict | Suboptimal |
|---|
Flow source
# Project Euler 186
# Calls until PM's friends reach 99% of network (Lagged Fibonacci + DSU).
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function find(parent: ptr<i32>, x: i32) -> i32 {
let mut cur: i32 = x
while parent[cur] != cur {
parent[cur] = parent[parent[cur]]
cur = parent[cur]
}
return cur
}
function main() -> i32 {
let N: i32 = 1000000
let parent: ptr<i32> = calloc(N as i64, 4)
let sz: ptr<i32> = calloc(N as i64, 4)
let hist: ptr<i32> = calloc(200, 4)
if parent == null || sz == null || hist == null { return 1 }
let mut i: i32 = 0
while i < N {
parent[i] = i
sz[i] = 1
i = i + 1
}
let mut hlen: i32 = 0
let mut calls: i64 = 0
let phone: i32 = 524287
let target: i32 = 990000
while true {
let mut from_id: i32 = 0
let mut to_id: i32 = 0
let mut t: i32 = 0
while t < 2 {
let mut cur: i32 = 0
if hlen < 55 {
let k: i64 = (hlen + 1) as i64
let v: i64 = (300007 * k * k * k - 200003 * k + 100003) % 1000000
if v < 0 { cur = (v + 1000000) as i32 } else { cur = v as i32 }
} else {
let a: i32 = hist[hlen - 55]
let b: i32 = hist[hlen - 24]
cur = (a + b) % 1000000
}
hist[hlen] = cur
hlen = hlen + 1
if hlen >= 160 {
# compact history keep last 55
let mut j: i32 = 0
while j < 55 {
hist[j] = hist[hlen - 55 + j]
j = j + 1
}
hlen = 55
}
if t == 0 { from_id = cur } else { to_id = cur }
t = t + 1
}
if from_id == to_id { continue }
calls = calls + 1
let rx: i32 = find(parent, from_id)
let ry: i32 = find(parent, to_id)
if rx != ry {
if sz[rx] >= sz[ry] {
parent[ry] = rx
sz[rx] = sz[rx] + sz[ry]
} else {
parent[rx] = ry
sz[ry] = sz[ry] + sz[rx]
}
}
let root: i32 = find(parent, phone)
if sz[root] >= target { break }
}
printf("%lld\n", calls)
free(parent); free(sz); free(hist)
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; }
int32_t find_ptr_i32_i32(int32_t* parent, int32_t x);
int32_t main(void);
int32_t find_ptr_i32_i32(int32_t* parent, int32_t x) {
int32_t cur = x;
while (parent[cur] != cur) {
parent[cur] = parent[parent[cur]];
cur = parent[cur];
}
return cur;
}
int32_t main(void) {
int32_t N = 1000000;
int32_t* parent = (int32_t*)(calloc(((int64_t)(N)), 4));
int32_t* sz = (int32_t*)(calloc(((int64_t)(N)), 4));
int32_t* hist = (int32_t*)(calloc(200, 4));
if (((parent == NULL || sz == NULL) || hist == NULL)) {
return 1;
}
int32_t i = 0;
while (i < N) {
parent[i] = i;
sz[i] = 1;
i = (i + 1);
}
int32_t hlen = 0;
int64_t calls = 0;
int32_t phone = 524287;
int32_t target = 990000;
while (1) {
int32_t from_id = 0;
int32_t to_id = 0;
int32_t t = 0;
while (t < 2) {
int32_t cur = 0;
if (hlen < 55) {
int64_t k = ((int64_t)((hlen + 1)));
int64_t v = FLOW_CHECKED_MOD(((((((300007 * k) * k) * k) - (200003 * k)) + 100003)), (1000000));
if (v < 0) {
cur = ((int32_t)((v + 1000000)));
} else {
cur = ((int32_t)(v));
}
} else {
int32_t a = hist[(hlen - 55)];
int32_t b = hist[(hlen - 24)];
cur = FLOW_CHECKED_MOD(((a + b)), (1000000));
}
hist[hlen] = cur;
hlen = (hlen + 1);
if (hlen >= 160) {
int32_t j = 0;
while (j < 55) {
hist[j] = hist[((hlen - 55) + j)];
j = (j + 1);
}
hlen = 55;
}
if (t == 0) {
from_id = cur;
} else {
to_id = cur;
}
t = (t + 1);
}
if (from_id == to_id) {
continue;
}
calls = (calls + 1);
int32_t rx = find_ptr_i32_i32(parent, from_id);
int32_t ry = find_ptr_i32_i32(parent, to_id);
if (rx != ry) {
if (sz[rx] >= sz[ry]) {
parent[ry] = rx;
sz[rx] = (sz[rx] + sz[ry]);
} else {
parent[rx] = ry;
sz[ry] = (sz[ry] + sz[rx]);
}
}
int32_t root = find_ptr_i32_i32(parent, phone);
if (sz[root] >= target) {
break;
}
}
printf("%lld\n", calls);
free(parent);
free(sz);
free(hist);
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) -> ()
func.func @find(%arg0: !llvm.ptr, %arg1: i32) -> i32 {
%0 = llvm.mlir.constant(1 : i64) : i64
%1 = llvm.alloca %0 x i32 : (i64) -> !llvm.ptr
llvm.store %arg1, %1 : i32, !llvm.ptr
cf.br ^bb0
^bb0:
%3 = llvm.load %1 : !llvm.ptr -> i32
%4 = arith.extsi %3 : i32 to i64
%5 = llvm.getelementptr %arg0[%4] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%2 = llvm.load %5 : !llvm.ptr -> i32
%6 = llvm.load %1 : !llvm.ptr -> i32
%7 = arith.cmpi ne, %2, %6 : i32
cf.cond_br %7, ^bb1, ^bb2
^bb1:
%10 = llvm.load %1 : !llvm.ptr -> i32
%11 = arith.extsi %10 : i32 to i64
%12 = llvm.getelementptr %arg0[%11] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%9 = llvm.load %12 : !llvm.ptr -> i32
%13 = arith.extsi %9 : i32 to i64
%14 = llvm.getelementptr %arg0[%13] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%8 = llvm.load %14 : !llvm.ptr -> i32
%15 = llvm.load %1 : !llvm.ptr -> i32
%16 = arith.extsi %15 : i32 to i64
%17 = llvm.getelementptr %arg0[%16] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %8, %17 : i32, !llvm.ptr
%19 = llvm.load %1 : !llvm.ptr -> i32
%20 = arith.extsi %19 : i32 to i64
%21 = llvm.getelementptr %arg0[%20] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%18 = llvm.load %21 : !llvm.ptr -> i32
llvm.store %18, %1 : i32, !llvm.ptr
cf.br ^bb0
^bb2:
%22 = llvm.load %1 : !llvm.ptr -> i32
func.return %22 : i32
}
func.func @main() -> i32 {
%23 = arith.constant 1000000 : i32
%25 = arith.extsi %23 : i32 to i64
%26 = arith.constant 4 : i32
%27 = arith.extsi %26 : i32 to i64
%24 = func.call @calloc(%25, %27) : (i64, i64) -> !llvm.ptr
%29 = arith.extsi %23 : i32 to i64
%30 = arith.constant 4 : i32
%31 = arith.extsi %30 : i32 to i64
%28 = func.call @calloc(%29, %31) : (i64, i64) -> !llvm.ptr
%33 = arith.constant 200 : i32
%34 = arith.constant 4 : i32
%35 = arith.extsi %33 : i32 to i64
%36 = arith.extsi %34 : i32 to i64
%32 = func.call @calloc(%35, %36) : (i64, i64) -> !llvm.ptr
%37 = llvm.mlir.zero : !llvm.ptr
%38 = llvm.icmp "eq" %24, %37 : !llvm.ptr
%39 = scf.if %38 -> (i1) {
%40 = arith.constant true
scf.yield %40 : i1
} else {
%41 = llvm.mlir.zero : !llvm.ptr
%42 = llvm.icmp "eq" %28, %41 : !llvm.ptr
scf.yield %42 : i1
}
%43 = scf.if %39 -> (i1) {
%44 = arith.constant true
scf.yield %44 : i1
} else {
%45 = llvm.mlir.zero : !llvm.ptr
%46 = llvm.icmp "eq" %32, %45 : !llvm.ptr
scf.yield %46 : i1
}
cf.cond_br %43, ^bb3, ^bb4
^bb3:
%47 = arith.constant 1 : i32
func.return %47 : i32
^bb4:
cf.br ^bb5
^bb5:
%48 = arith.constant 0 : i32
%49 = llvm.mlir.constant(1 : i64) : i64
%50 = llvm.alloca %49 x i32 : (i64) -> !llvm.ptr
llvm.store %48, %50 : i32, !llvm.ptr
cf.br ^bb6
^bb6:
%51 = llvm.load %50 : !llvm.ptr -> i32
%52 = arith.cmpi slt, %51, %23 : i32
cf.cond_br %52, ^bb7, ^bb8
^bb7:
%53 = llvm.load %50 : !llvm.ptr -> i32
%54 = llvm.load %50 : !llvm.ptr -> i32
%55 = arith.extsi %54 : i32 to i64
%56 = llvm.getelementptr %24[%55] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %53, %56 : i32, !llvm.ptr
%57 = arith.constant 1 : i32
%58 = llvm.load %50 : !llvm.ptr -> i32
%59 = arith.extsi %58 : i32 to i64
%60 = llvm.getelementptr %28[%59] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %57, %60 : i32, !llvm.ptr
%61 = llvm.load %50 : !llvm.ptr -> i32
%62 = arith.constant 1 : i32
%63 = arith.addi %61, %62 : i32
llvm.store %63, %50 : i32, !llvm.ptr
cf.br ^bb6
^bb8:
%64 = arith.constant 0 : i32
%65 = llvm.mlir.constant(1 : i64) : i64
%66 = llvm.alloca %65 x i32 : (i64) -> !llvm.ptr
llvm.store %64, %66 : i32, !llvm.ptr
%67 = arith.constant 0 : i32
%68 = arith.extsi %67 : i32 to i64
%69 = llvm.mlir.constant(1 : i64) : i64
%70 = llvm.alloca %69 x i64 : (i64) -> !llvm.ptr
llvm.store %68, %70 : i64, !llvm.ptr
%71 = arith.constant 524287 : i32
%72 = arith.constant 990000 : i32
cf.br ^bb9
^bb9:
%73 = arith.constant 1 : i1
cf.cond_br %73, ^bb10, ^bb11
^bb10:
%74 = arith.constant 0 : i32
%75 = llvm.mlir.constant(1 : i64) : i64
%76 = llvm.alloca %75 x i32 : (i64) -> !llvm.ptr
llvm.store %74, %76 : i32, !llvm.ptr
%77 = arith.constant 0 : i32
%78 = llvm.mlir.constant(1 : i64) : i64
%79 = llvm.alloca %78 x i32 : (i64) -> !llvm.ptr
llvm.store %77, %79 : i32, !llvm.ptr
%80 = arith.constant 0 : i32
%81 = llvm.mlir.constant(1 : i64) : i64
%82 = llvm.alloca %81 x i32 : (i64) -> !llvm.ptr
llvm.store %80, %82 : i32, !llvm.ptr
cf.br ^bb12
^bb12:
%83 = llvm.load %82 : !llvm.ptr -> i32
%84 = arith.constant 2 : i32
%85 = arith.cmpi slt, %83, %84 : i32
cf.cond_br %85, ^bb13, ^bb14
^bb13:
%86 = arith.constant 0 : i32
%87 = llvm.mlir.constant(1 : i64) : i64
%88 = llvm.alloca %87 x i32 : (i64) -> !llvm.ptr
llvm.store %86, %88 : i32, !llvm.ptr
%89 = llvm.load %66 : !llvm.ptr -> i32
%90 = arith.constant 55 : i32
%91 = arith.cmpi slt, %89, %90 : i32
cf.cond_br %91, ^bb15, ^bb16
^bb15:
%92 = llvm.load %66 : !llvm.ptr -> i32
%93 = arith.constant 1 : i32
%94 = arith.addi %92, %93 : i32
%95 = arith.extsi %94 : i32 to i64
%96 = arith.constant 300007 : i32
%98 = arith.extsi %96 : i32 to i64
%97 = arith.muli %98, %95 : i64
%99 = arith.muli %97, %95 : i64
%100 = arith.muli %99, %95 : i64
%101 = arith.constant 200003 : i32
%103 = arith.extsi %101 : i32 to i64
%102 = arith.muli %103, %95 : i64
%104 = arith.subi %100, %102 : i64
%105 = arith.constant 100003 : i32
%107 = arith.extsi %105 : i32 to i64
%106 = arith.addi %104, %107 : i64
%108 = arith.constant 1000000 : i32
%110 = arith.extsi %108 : i32 to i64
%109 = arith.remsi %106, %110 : i64
%111 = arith.constant 0 : i32
%113 = arith.extsi %111 : i32 to i64
%112 = arith.cmpi slt, %109, %113 : i64
cf.cond_br %112, ^bb18, ^bb19
^bb18:
%114 = arith.constant 1000000 : i32
%116 = arith.extsi %114 : i32 to i64
%115 = arith.addi %109, %116 : i64
%117 = arith.trunci %115 : i64 to i32
llvm.store %117, %88 : i32, !llvm.ptr
cf.br ^bb20
^bb19:
%118 = arith.trunci %109 : i64 to i32
llvm.store %118, %88 : i32, !llvm.ptr
cf.br ^bb20
^bb20:
cf.br ^bb17
^bb16:
%120 = llvm.load %66 : !llvm.ptr -> i32
%121 = arith.constant 55 : i32
%122 = arith.subi %120, %121 : i32
%123 = arith.extsi %122 : i32 to i64
%124 = llvm.getelementptr %32[%123] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%119 = llvm.load %124 : !llvm.ptr -> i32
%126 = llvm.load %66 : !llvm.ptr -> i32
%127 = arith.constant 24 : i32
%128 = arith.subi %126, %127 : i32
%129 = arith.extsi %128 : i32 to i64
%130 = llvm.getelementptr %32[%129] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%125 = llvm.load %130 : !llvm.ptr -> i32
%131 = arith.addi %119, %125 : i32
%132 = arith.constant 1000000 : i32
%133 = arith.remsi %131, %132 : i32
llvm.store %133, %88 : i32, !llvm.ptr
cf.br ^bb17
^bb17:
%134 = llvm.load %88 : !llvm.ptr -> i32
%135 = llvm.load %66 : !llvm.ptr -> i32
%136 = arith.extsi %135 : i32 to i64
%137 = llvm.getelementptr %32[%136] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %134, %137 : i32, !llvm.ptr
%138 = llvm.load %66 : !llvm.ptr -> i32
%139 = arith.constant 1 : i32
%140 = arith.addi %138, %139 : i32
llvm.store %140, %66 : i32, !llvm.ptr
%141 = llvm.load %66 : !llvm.ptr -> i32
%142 = arith.constant 160 : i32
%143 = arith.cmpi sge, %141, %142 : i32
cf.cond_br %143, ^bb21, ^bb22
^bb21:
%144 = arith.constant 0 : i32
%145 = llvm.mlir.constant(1 : i64) : i64
%146 = llvm.alloca %145 x i32 : (i64) -> !llvm.ptr
llvm.store %144, %146 : i32, !llvm.ptr
cf.br ^bb24
^bb24:
%147 = llvm.load %146 : !llvm.ptr -> i32
%148 = arith.constant 55 : i32
%149 = arith.cmpi slt, %147, %148 : i32
cf.cond_br %149, ^bb25, ^bb26
^bb25:
%151 = llvm.load %66 : !llvm.ptr -> i32
%152 = arith.constant 55 : i32
%153 = arith.subi %151, %152 : i32
%154 = llvm.load %146 : !llvm.ptr -> i32
%155 = arith.addi %153, %154 : i32
%156 = arith.extsi %155 : i32 to i64
%157 = llvm.getelementptr %32[%156] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%150 = llvm.load %157 : !llvm.ptr -> i32
%158 = llvm.load %146 : !llvm.ptr -> i32
%159 = arith.extsi %158 : i32 to i64
%160 = llvm.getelementptr %32[%159] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %150, %160 : i32, !llvm.ptr
%161 = llvm.load %146 : !llvm.ptr -> i32
%162 = arith.constant 1 : i32
%163 = arith.addi %161, %162 : i32
llvm.store %163, %146 : i32, !llvm.ptr
cf.br ^bb24
^bb26:
%164 = arith.constant 55 : i32
llvm.store %164, %66 : i32, !llvm.ptr
cf.br ^bb23
^bb22:
cf.br ^bb23
^bb23:
%165 = llvm.load %82 : !llvm.ptr -> i32
%166 = arith.constant 0 : i32
%167 = arith.cmpi eq, %165, %166 : i32
cf.cond_br %167, ^bb27, ^bb28
^bb27:
%168 = llvm.load %88 : !llvm.ptr -> i32
llvm.store %168, %76 : i32, !llvm.ptr
cf.br ^bb29
^bb28:
%169 = llvm.load %88 : !llvm.ptr -> i32
llvm.store %169, %79 : i32, !llvm.ptr
cf.br ^bb29
^bb29:
%170 = llvm.load %82 : !llvm.ptr -> i32
%171 = arith.constant 1 : i32
%172 = arith.addi %170, %171 : i32
llvm.store %172, %82 : i32, !llvm.ptr
cf.br ^bb12
^bb14:
%173 = llvm.load %76 : !llvm.ptr -> i32
%174 = llvm.load %79 : !llvm.ptr -> i32
%175 = arith.cmpi eq, %173, %174 : i32
cf.cond_br %175, ^bb30, ^bb31
^bb30:
cf.br ^bb9
^bb31:
cf.br ^bb32
^bb32:
%176 = llvm.load %70 : !llvm.ptr -> i64
%177 = arith.constant 1 : i32
%179 = arith.extsi %177 : i32 to i64
%178 = arith.addi %176, %179 : i64
llvm.store %178, %70 : i64, !llvm.ptr
%181 = llvm.load %76 : !llvm.ptr -> i32
%180 = func.call @find(%24, %181) : (!llvm.ptr, i32) -> i32
%183 = llvm.load %79 : !llvm.ptr -> i32
%182 = func.call @find(%24, %183) : (!llvm.ptr, i32) -> i32
%184 = arith.cmpi ne, %180, %182 : i32
cf.cond_br %184, ^bb33, ^bb34
^bb33:
%186 = arith.extsi %180 : i32 to i64
%187 = llvm.getelementptr %28[%186] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%185 = llvm.load %187 : !llvm.ptr -> i32
%189 = arith.extsi %182 : i32 to i64
%190 = llvm.getelementptr %28[%189] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%188 = llvm.load %190 : !llvm.ptr -> i32
%191 = arith.cmpi sge, %185, %188 : i32
cf.cond_br %191, ^bb36, ^bb37
^bb36:
%192 = arith.extsi %182 : i32 to i64
%193 = llvm.getelementptr %24[%192] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %180, %193 : i32, !llvm.ptr
%195 = arith.extsi %180 : i32 to i64
%196 = llvm.getelementptr %28[%195] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%194 = llvm.load %196 : !llvm.ptr -> i32
%198 = arith.extsi %182 : i32 to i64
%199 = llvm.getelementptr %28[%198] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%197 = llvm.load %199 : !llvm.ptr -> i32
%200 = arith.addi %194, %197 : i32
%201 = arith.extsi %180 : i32 to i64
%202 = llvm.getelementptr %28[%201] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %200, %202 : i32, !llvm.ptr
cf.br ^bb38
^bb37:
%203 = arith.extsi %180 : i32 to i64
%204 = llvm.getelementptr %24[%203] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %182, %204 : i32, !llvm.ptr
%206 = arith.extsi %182 : i32 to i64
%207 = llvm.getelementptr %28[%206] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%205 = llvm.load %207 : !llvm.ptr -> i32
%209 = arith.extsi %180 : i32 to i64
%210 = llvm.getelementptr %28[%209] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%208 = llvm.load %210 : !llvm.ptr -> i32
%211 = arith.addi %205, %208 : i32
%212 = arith.extsi %182 : i32 to i64
%213 = llvm.getelementptr %28[%212] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %211, %213 : i32, !llvm.ptr
cf.br ^bb38
^bb38:
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
%214 = func.call @find(%24, %71) : (!llvm.ptr, i32) -> i32
%216 = arith.extsi %214 : i32 to i64
%217 = llvm.getelementptr %28[%216] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%215 = llvm.load %217 : !llvm.ptr -> i32
%218 = arith.cmpi sge, %215, %72 : i32
cf.cond_br %218, ^bb39, ^bb40
^bb39:
cf.br ^bb11
^bb40:
cf.br ^bb41
^bb41:
cf.br ^bb9
^bb11:
%219 = llvm.mlir.addressof @str_0 : !llvm.ptr
%220 = llvm.load %70 : !llvm.ptr -> i64
%221 = llvm.call @printf(%219, %220) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%24) : (!llvm.ptr) -> ()
func.call @free(%28) : (!llvm.ptr) -> ()
func.call @free(%32) : (!llvm.ptr) -> ()
%225 = arith.constant 0 : i32
func.return %225 : i32
}
}