Problem 103
Optimum special sum set of size 7 — concatenate its elements.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^8) | O(n * sum) |
|---|
| Space complexity | O(1) | O(sum) |
|---|
| Approach | Flow solution | Subset sum DP |
|---|
| Verdict | Unknown |
|---|
Flow source
# Project Euler 103
# Optimum special sum set of size 7 — concatenate its elements.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function is_special(a: ptr<i32>, n: i32) -> bool {
# Rule: sum of smallest (k+1) > sum of largest k for k=1..
let mut k: i32 = 1
while 2 * k <= n {
let mut small: i32 = 0
let mut i: i32 = 0
while i <= k {
small = small + a[i]
i = i + 1
}
let mut large: i32 = 0
i = n - k
while i < n {
large = large + a[i]
i = i + 1
}
if small <= large { return false }
k = k + 1
}
# All subset sums distinct
let mut seen: ptr<i8> = calloc(2000, 1)
if seen == null { return false }
let mut mask: i32 = 1
let lim: i32 = 1 << n
while mask < lim {
let mut s: i32 = 0
let mut i: i32 = 0
while i < n {
if ((mask >> i) & 1) == 1 {
s = s + a[i]
}
i = i + 1
}
if seen[s] != 0 {
free(seen)
return false
}
seen[s] = 1
mask = mask + 1
}
free(seen)
return true
}
function concat7(a: ptr<i32>) -> i64 {
let mut r: i64 = 0
let mut i: i32 = 0
while i < 7 {
let v: i64 = a[i] as i64
if v >= 100 {
r = r * 1000 + v
} elif v >= 10 {
r = r * 100 + v
} else {
r = r * 10 + v
}
i = i + 1
}
return r
}
function main() -> i32 {
# Seed from n=6 optimum; PE construction: b = middle, then b + previous
# previous = [11,18,19,20,22,25], b=20 → base [20,31,38,39,40,42,45]
let base: ptr<i32> = calloc(7, 4)
if base == null { return 1 }
base[0] = 20
base[1] = 31
base[2] = 38
base[3] = 39
base[4] = 40
base[5] = 42
base[6] = 45
let cand: ptr<i32> = calloc(7, 4)
if cand == null { free(base); return 1 }
let mut best_sum: i32 = 1000000
let mut best_concat: i64 = 0
let mut o0: i32 = -3
while o0 <= 3 {
let mut o1: i32 = -3
while o1 <= 3 {
let mut o2: i32 = -3
while o2 <= 3 {
let mut o3: i32 = -3
while o3 <= 3 {
let mut o4: i32 = -3
while o4 <= 3 {
let mut o5: i32 = -3
while o5 <= 3 {
let mut o6: i32 = -3
while o6 <= 3 {
cand[0] = base[0] + o0
cand[1] = base[1] + o1
cand[2] = base[2] + o2
cand[3] = base[3] + o3
cand[4] = base[4] + o4
cand[5] = base[5] + o5
cand[6] = base[6] + o6
if cand[0] > 0 && cand[0] < cand[1] && cand[1] < cand[2] && cand[2] < cand[3] && cand[3] < cand[4] && cand[4] < cand[5] && cand[5] < cand[6] {
let mut s: i32 = 0
let mut i: i32 = 0
while i < 7 {
s = s + cand[i]
i = i + 1
}
if s < best_sum && is_special(cand, 7) {
best_sum = s
best_concat = concat7(cand)
}
}
o6 = o6 + 1
}
o5 = o5 + 1
}
o4 = o4 + 1
}
o3 = o3 + 1
}
o2 = o2 + 1
}
o1 = o1 + 1
}
o0 = o0 + 1
}
printf("%lld\n", best_concat)
free(cand)
free(base)
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 is_special_ptr_i32_i32(int32_t* a, int32_t n);
int64_t concat7_ptr_i32(int32_t* a);
int32_t main(void);
bool is_special_ptr_i32_i32(int32_t* a, int32_t n) {
int32_t k = 1;
while ((2 * k) <= n) {
int32_t small = 0;
int32_t i = 0;
while (i <= k) {
small = (small + a[i]);
i = (i + 1);
}
int32_t large = 0;
i = (n - k);
while (i < n) {
large = (large + a[i]);
i = (i + 1);
}
if (small <= large) {
return 0;
}
k = (k + 1);
}
int8_t* seen = (int8_t*)(calloc(2000, 1));
if (seen == NULL) {
return 0;
}
int32_t mask = 1;
int32_t lim = FLOW_CHECKED_SHL((1), (n));
while (mask < lim) {
int32_t s = 0;
int32_t i = 0;
while (i < n) {
if ((FLOW_CHECKED_SHR((mask), (i)) & 1) == 1) {
s = (s + a[i]);
}
i = (i + 1);
}
if (seen[s] != 0) {
free(seen);
return 0;
}
seen[s] = 1;
mask = (mask + 1);
}
free(seen);
return 1;
}
int64_t concat7_ptr_i32(int32_t* a) {
int64_t r = 0;
int32_t i = 0;
while (i < 7) {
int64_t v = ((int64_t)(a[i]));
if (v >= 100) {
r = ((r * 1000) + v);
} else if (v >= 10) {
r = ((r * 100) + v);
} else {
r = ((r * 10) + v);
}
i = (i + 1);
}
return r;
}
int32_t main(void) {
int32_t* base = (int32_t*)(calloc(7, 4));
if (base == NULL) {
return 1;
}
base[0] = 20;
base[1] = 31;
base[2] = 38;
base[3] = 39;
base[4] = 40;
base[5] = 42;
base[6] = 45;
int32_t* cand = (int32_t*)(calloc(7, 4));
if (cand == NULL) {
free(base);
return 1;
}
int32_t best_sum = 1000000;
int64_t best_concat = 0;
int32_t o0 = (-3);
while (o0 <= 3) {
int32_t o1 = (-3);
while (o1 <= 3) {
int32_t o2 = (-3);
while (o2 <= 3) {
int32_t o3 = (-3);
while (o3 <= 3) {
int32_t o4 = (-3);
while (o4 <= 3) {
int32_t o5 = (-3);
while (o5 <= 3) {
int32_t o6 = (-3);
while (o6 <= 3) {
cand[0] = (base[0] + o0);
cand[1] = (base[1] + o1);
cand[2] = (base[2] + o2);
cand[3] = (base[3] + o3);
cand[4] = (base[4] + o4);
cand[5] = (base[5] + o5);
cand[6] = (base[6] + o6);
if (((((((cand[0] > 0 && cand[0] < cand[1]) && cand[1] < cand[2]) && cand[2] < cand[3]) && cand[3] < cand[4]) && cand[4] < cand[5]) && cand[5] < cand[6])) {
int32_t s = 0;
int32_t i = 0;
while (i < 7) {
s = (s + cand[i]);
i = (i + 1);
}
if ((s < best_sum && is_special_ptr_i32_i32(cand, 7))) {
best_sum = s;
best_concat = concat7_ptr_i32(cand);
}
}
o6 = (o6 + 1);
}
o5 = (o5 + 1);
}
o4 = (o4 + 1);
}
o3 = (o3 + 1);
}
o2 = (o2 + 1);
}
o1 = (o1 + 1);
}
o0 = (o0 + 1);
}
printf("%lld\n", best_concat);
free(cand);
free(base);
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 @is_special(%arg0: !llvm.ptr, %arg1: i32) -> i1 {
%0 = arith.constant 1 : i32
%1 = llvm.mlir.constant(1 : i64) : i64
%2 = llvm.alloca %1 x i32 : (i64) -> !llvm.ptr
llvm.store %0, %2 : i32, !llvm.ptr
cf.br ^bb0
^bb0:
%3 = arith.constant 2 : i32
%4 = llvm.load %2 : !llvm.ptr -> i32
%5 = arith.muli %3, %4 : i32
%6 = arith.cmpi sle, %5, %arg1 : i32
cf.cond_br %6, ^bb1, ^bb2
^bb1:
%7 = arith.constant 0 : i32
%8 = llvm.mlir.constant(1 : i64) : i64
%9 = llvm.alloca %8 x i32 : (i64) -> !llvm.ptr
llvm.store %7, %9 : i32, !llvm.ptr
%10 = arith.constant 0 : i32
%11 = llvm.mlir.constant(1 : i64) : i64
%12 = llvm.alloca %11 x i32 : (i64) -> !llvm.ptr
llvm.store %10, %12 : i32, !llvm.ptr
cf.br ^bb3
^bb3:
%13 = llvm.load %12 : !llvm.ptr -> i32
%14 = llvm.load %2 : !llvm.ptr -> i32
%15 = arith.cmpi sle, %13, %14 : i32
cf.cond_br %15, ^bb4, ^bb5
^bb4:
%16 = llvm.load %9 : !llvm.ptr -> i32
%18 = llvm.load %12 : !llvm.ptr -> i32
%19 = arith.extsi %18 : i32 to i64
%20 = llvm.getelementptr %arg0[%19] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%17 = llvm.load %20 : !llvm.ptr -> i32
%21 = arith.addi %16, %17 : i32
llvm.store %21, %9 : i32, !llvm.ptr
%22 = llvm.load %12 : !llvm.ptr -> i32
%23 = arith.constant 1 : i32
%24 = arith.addi %22, %23 : i32
llvm.store %24, %12 : i32, !llvm.ptr
cf.br ^bb3
^bb5:
%25 = arith.constant 0 : i32
%26 = llvm.mlir.constant(1 : i64) : i64
%27 = llvm.alloca %26 x i32 : (i64) -> !llvm.ptr
llvm.store %25, %27 : i32, !llvm.ptr
%28 = llvm.load %2 : !llvm.ptr -> i32
%29 = arith.subi %arg1, %28 : i32
llvm.store %29, %12 : i32, !llvm.ptr
cf.br ^bb6
^bb6:
%30 = llvm.load %12 : !llvm.ptr -> i32
%31 = arith.cmpi slt, %30, %arg1 : i32
cf.cond_br %31, ^bb7, ^bb8
^bb7:
%32 = llvm.load %27 : !llvm.ptr -> i32
%34 = llvm.load %12 : !llvm.ptr -> i32
%35 = arith.extsi %34 : i32 to i64
%36 = llvm.getelementptr %arg0[%35] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%33 = llvm.load %36 : !llvm.ptr -> i32
%37 = arith.addi %32, %33 : i32
llvm.store %37, %27 : i32, !llvm.ptr
%38 = llvm.load %12 : !llvm.ptr -> i32
%39 = arith.constant 1 : i32
%40 = arith.addi %38, %39 : i32
llvm.store %40, %12 : i32, !llvm.ptr
cf.br ^bb6
^bb8:
%41 = llvm.load %9 : !llvm.ptr -> i32
%42 = llvm.load %27 : !llvm.ptr -> i32
%43 = arith.cmpi sle, %41, %42 : i32
cf.cond_br %43, ^bb9, ^bb10
^bb9:
%44 = arith.constant 0 : i1
func.return %44 : i1
^bb10:
cf.br ^bb11
^bb11:
%45 = llvm.load %2 : !llvm.ptr -> i32
%46 = arith.constant 1 : i32
%47 = arith.addi %45, %46 : i32
llvm.store %47, %2 : i32, !llvm.ptr
cf.br ^bb0
^bb2:
%49 = arith.constant 2000 : i32
%50 = arith.constant 1 : i32
%51 = arith.extsi %49 : i32 to i64
%52 = arith.extsi %50 : i32 to i64
%48 = func.call @calloc(%51, %52) : (i64, i64) -> !llvm.ptr
%53 = llvm.mlir.constant(1 : i64) : i64
%54 = llvm.alloca %53 x !llvm.ptr : (i64) -> !llvm.ptr
llvm.store %48, %54 : !llvm.ptr, !llvm.ptr
%55 = llvm.load %54 : !llvm.ptr -> !llvm.ptr
%56 = llvm.mlir.zero : !llvm.ptr
%57 = llvm.icmp "eq" %55, %56 : !llvm.ptr
cf.cond_br %57, ^bb12, ^bb13
^bb12:
%58 = arith.constant 0 : i1
func.return %58 : i1
^bb13:
cf.br ^bb14
^bb14:
%59 = arith.constant 1 : i32
%60 = llvm.mlir.constant(1 : i64) : i64
%61 = llvm.alloca %60 x i32 : (i64) -> !llvm.ptr
llvm.store %59, %61 : i32, !llvm.ptr
%62 = arith.constant 1 : i32
%63 = arith.shli %62, %arg1 : i32
cf.br ^bb15
^bb15:
%64 = llvm.load %61 : !llvm.ptr -> i32
%65 = arith.cmpi slt, %64, %63 : i32
cf.cond_br %65, ^bb16, ^bb17
^bb16:
%66 = arith.constant 0 : i32
%67 = llvm.mlir.constant(1 : i64) : i64
%68 = llvm.alloca %67 x i32 : (i64) -> !llvm.ptr
llvm.store %66, %68 : i32, !llvm.ptr
%69 = arith.constant 0 : i32
%70 = llvm.mlir.constant(1 : i64) : i64
%71 = llvm.alloca %70 x i32 : (i64) -> !llvm.ptr
llvm.store %69, %71 : i32, !llvm.ptr
cf.br ^bb18
^bb18:
%72 = llvm.load %71 : !llvm.ptr -> i32
%73 = arith.cmpi slt, %72, %arg1 : i32
cf.cond_br %73, ^bb19, ^bb20
^bb19:
%74 = llvm.load %61 : !llvm.ptr -> i32
%75 = llvm.load %71 : !llvm.ptr -> i32
%76 = arith.shrsi %74, %75 : i32
%77 = arith.constant 1 : i32
%78 = arith.andi %76, %77 : i32
%79 = arith.constant 1 : i32
%80 = arith.cmpi eq, %78, %79 : i32
cf.cond_br %80, ^bb21, ^bb22
^bb21:
%81 = llvm.load %68 : !llvm.ptr -> i32
%83 = llvm.load %71 : !llvm.ptr -> i32
%84 = arith.extsi %83 : i32 to i64
%85 = llvm.getelementptr %arg0[%84] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%82 = llvm.load %85 : !llvm.ptr -> i32
%86 = arith.addi %81, %82 : i32
llvm.store %86, %68 : i32, !llvm.ptr
cf.br ^bb23
^bb22:
cf.br ^bb23
^bb23:
%87 = llvm.load %71 : !llvm.ptr -> i32
%88 = arith.constant 1 : i32
%89 = arith.addi %87, %88 : i32
llvm.store %89, %71 : i32, !llvm.ptr
cf.br ^bb18
^bb20:
%91 = llvm.load %54 : !llvm.ptr -> !llvm.ptr
%92 = llvm.load %68 : !llvm.ptr -> i32
%93 = arith.extsi %92 : i32 to i64
%94 = llvm.getelementptr %91[%93] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%90 = llvm.load %94 : !llvm.ptr -> i8
%95 = arith.constant 0 : i32
%97 = arith.extsi %90 : i8 to i32
%96 = arith.cmpi ne, %97, %95 : i32
cf.cond_br %96, ^bb24, ^bb25
^bb24:
%99 = llvm.load %54 : !llvm.ptr -> !llvm.ptr
func.call @free(%99) : (!llvm.ptr) -> ()
%100 = arith.constant 0 : i1
func.return %100 : i1
^bb25:
cf.br ^bb26
^bb26:
%101 = arith.constant 1 : i32
%102 = llvm.load %54 : !llvm.ptr -> !llvm.ptr
%103 = llvm.load %68 : !llvm.ptr -> i32
%104 = arith.trunci %101 : i32 to i8
%105 = arith.extsi %103 : i32 to i64
%106 = llvm.getelementptr %102[%105] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %104, %106 : i8, !llvm.ptr
%107 = llvm.load %61 : !llvm.ptr -> i32
%108 = arith.constant 1 : i32
%109 = arith.addi %107, %108 : i32
llvm.store %109, %61 : i32, !llvm.ptr
cf.br ^bb15
^bb17:
%111 = llvm.load %54 : !llvm.ptr -> !llvm.ptr
func.call @free(%111) : (!llvm.ptr) -> ()
%112 = arith.constant 1 : i1
func.return %112 : i1
}
func.func @concat7(%arg0: !llvm.ptr) -> i64 {
%113 = arith.constant 0 : i32
%114 = arith.extsi %113 : i32 to i64
%115 = llvm.mlir.constant(1 : i64) : i64
%116 = llvm.alloca %115 x i64 : (i64) -> !llvm.ptr
llvm.store %114, %116 : i64, !llvm.ptr
%117 = arith.constant 0 : i32
%118 = llvm.mlir.constant(1 : i64) : i64
%119 = llvm.alloca %118 x i32 : (i64) -> !llvm.ptr
llvm.store %117, %119 : i32, !llvm.ptr
cf.br ^bb27
^bb27:
%120 = llvm.load %119 : !llvm.ptr -> i32
%121 = arith.constant 7 : i32
%122 = arith.cmpi slt, %120, %121 : i32
cf.cond_br %122, ^bb28, ^bb29
^bb28:
%124 = llvm.load %119 : !llvm.ptr -> i32
%125 = arith.extsi %124 : i32 to i64
%126 = llvm.getelementptr %arg0[%125] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%123 = llvm.load %126 : !llvm.ptr -> i32
%127 = arith.extsi %123 : i32 to i64
%128 = arith.constant 100 : i32
%130 = arith.extsi %128 : i32 to i64
%129 = arith.cmpi sge, %127, %130 : i64
cf.cond_br %129, ^bb30, ^bb31
^bb30:
%131 = llvm.load %116 : !llvm.ptr -> i64
%132 = arith.constant 1000 : i32
%134 = arith.extsi %132 : i32 to i64
%133 = arith.muli %131, %134 : i64
%135 = arith.addi %133, %127 : i64
llvm.store %135, %116 : i64, !llvm.ptr
cf.br ^bb32
^bb31:
%136 = arith.constant 10 : i32
%138 = arith.extsi %136 : i32 to i64
%137 = arith.cmpi sge, %127, %138 : i64
cf.cond_br %137, ^bb34, ^bb33
^bb34:
%139 = llvm.load %116 : !llvm.ptr -> i64
%140 = arith.constant 100 : i32
%142 = arith.extsi %140 : i32 to i64
%141 = arith.muli %139, %142 : i64
%143 = arith.addi %141, %127 : i64
llvm.store %143, %116 : i64, !llvm.ptr
cf.br ^bb32
^bb33:
%144 = llvm.load %116 : !llvm.ptr -> i64
%145 = arith.constant 10 : i32
%147 = arith.extsi %145 : i32 to i64
%146 = arith.muli %144, %147 : i64
%148 = arith.addi %146, %127 : i64
llvm.store %148, %116 : i64, !llvm.ptr
cf.br ^bb32
^bb32:
%149 = llvm.load %119 : !llvm.ptr -> i32
%150 = arith.constant 1 : i32
%151 = arith.addi %149, %150 : i32
llvm.store %151, %119 : i32, !llvm.ptr
cf.br ^bb27
^bb29:
%152 = llvm.load %116 : !llvm.ptr -> i64
func.return %152 : i64
}
func.func @main() -> i32 {
%154 = arith.constant 7 : i32
%155 = arith.constant 4 : i32
%156 = arith.extsi %154 : i32 to i64
%157 = arith.extsi %155 : i32 to i64
%153 = func.call @calloc(%156, %157) : (i64, i64) -> !llvm.ptr
%158 = llvm.mlir.zero : !llvm.ptr
%159 = llvm.icmp "eq" %153, %158 : !llvm.ptr
cf.cond_br %159, ^bb35, ^bb36
^bb35:
%160 = arith.constant 1 : i32
func.return %160 : i32
^bb36:
cf.br ^bb37
^bb37:
%161 = arith.constant 20 : i32
%162 = arith.constant 0 : i32
%163 = arith.extsi %162 : i32 to i64
%164 = llvm.getelementptr %153[%163] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %161, %164 : i32, !llvm.ptr
%165 = arith.constant 31 : i32
%166 = arith.constant 1 : i32
%167 = arith.extsi %166 : i32 to i64
%168 = llvm.getelementptr %153[%167] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %165, %168 : i32, !llvm.ptr
%169 = arith.constant 38 : i32
%170 = arith.constant 2 : i32
%171 = arith.extsi %170 : i32 to i64
%172 = llvm.getelementptr %153[%171] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %169, %172 : i32, !llvm.ptr
%173 = arith.constant 39 : i32
%174 = arith.constant 3 : i32
%175 = arith.extsi %174 : i32 to i64
%176 = llvm.getelementptr %153[%175] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %173, %176 : i32, !llvm.ptr
%177 = arith.constant 40 : i32
%178 = arith.constant 4 : i32
%179 = arith.extsi %178 : i32 to i64
%180 = llvm.getelementptr %153[%179] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %177, %180 : i32, !llvm.ptr
%181 = arith.constant 42 : i32
%182 = arith.constant 5 : i32
%183 = arith.extsi %182 : i32 to i64
%184 = llvm.getelementptr %153[%183] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %181, %184 : i32, !llvm.ptr
%185 = arith.constant 45 : i32
%186 = arith.constant 6 : i32
%187 = arith.extsi %186 : i32 to i64
%188 = llvm.getelementptr %153[%187] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %185, %188 : i32, !llvm.ptr
%190 = arith.constant 7 : i32
%191 = arith.constant 4 : i32
%192 = arith.extsi %190 : i32 to i64
%193 = arith.extsi %191 : i32 to i64
%189 = func.call @calloc(%192, %193) : (i64, i64) -> !llvm.ptr
%194 = llvm.mlir.zero : !llvm.ptr
%195 = llvm.icmp "eq" %189, %194 : !llvm.ptr
cf.cond_br %195, ^bb38, ^bb39
^bb38:
func.call @free(%153) : (!llvm.ptr) -> ()
%197 = arith.constant 1 : i32
func.return %197 : i32
^bb39:
cf.br ^bb40
^bb40:
%198 = arith.constant 1000000 : i32
%199 = llvm.mlir.constant(1 : i64) : i64
%200 = llvm.alloca %199 x i32 : (i64) -> !llvm.ptr
llvm.store %198, %200 : i32, !llvm.ptr
%201 = arith.constant 0 : i32
%202 = arith.extsi %201 : i32 to i64
%203 = llvm.mlir.constant(1 : i64) : i64
%204 = llvm.alloca %203 x i64 : (i64) -> !llvm.ptr
llvm.store %202, %204 : i64, !llvm.ptr
%205 = arith.constant 3 : i32
%207 = arith.constant 0 : i32
%206 = arith.subi %207, %205 : i32
%208 = llvm.mlir.constant(1 : i64) : i64
%209 = llvm.alloca %208 x i32 : (i64) -> !llvm.ptr
llvm.store %206, %209 : i32, !llvm.ptr
cf.br ^bb41
^bb41:
%210 = llvm.load %209 : !llvm.ptr -> i32
%211 = arith.constant 3 : i32
%212 = arith.cmpi sle, %210, %211 : i32
cf.cond_br %212, ^bb42, ^bb43
^bb42:
%213 = arith.constant 3 : i32
%215 = arith.constant 0 : i32
%214 = arith.subi %215, %213 : i32
%216 = llvm.mlir.constant(1 : i64) : i64
%217 = llvm.alloca %216 x i32 : (i64) -> !llvm.ptr
llvm.store %214, %217 : i32, !llvm.ptr
cf.br ^bb44
^bb44:
%218 = llvm.load %217 : !llvm.ptr -> i32
%219 = arith.constant 3 : i32
%220 = arith.cmpi sle, %218, %219 : i32
cf.cond_br %220, ^bb45, ^bb46
^bb45:
%221 = arith.constant 3 : i32
%223 = arith.constant 0 : i32
%222 = arith.subi %223, %221 : i32
%224 = llvm.mlir.constant(1 : i64) : i64
%225 = llvm.alloca %224 x i32 : (i64) -> !llvm.ptr
llvm.store %222, %225 : i32, !llvm.ptr
cf.br ^bb47
^bb47:
%226 = llvm.load %225 : !llvm.ptr -> i32
%227 = arith.constant 3 : i32
%228 = arith.cmpi sle, %226, %227 : i32
cf.cond_br %228, ^bb48, ^bb49
^bb48:
%229 = arith.constant 3 : i32
%231 = arith.constant 0 : i32
%230 = arith.subi %231, %229 : i32
%232 = llvm.mlir.constant(1 : i64) : i64
%233 = llvm.alloca %232 x i32 : (i64) -> !llvm.ptr
llvm.store %230, %233 : i32, !llvm.ptr
cf.br ^bb50
^bb50:
%234 = llvm.load %233 : !llvm.ptr -> i32
%235 = arith.constant 3 : i32
%236 = arith.cmpi sle, %234, %235 : i32
cf.cond_br %236, ^bb51, ^bb52
^bb51:
%237 = arith.constant 3 : i32
%239 = arith.constant 0 : i32
%238 = arith.subi %239, %237 : i32
%240 = llvm.mlir.constant(1 : i64) : i64
%241 = llvm.alloca %240 x i32 : (i64) -> !llvm.ptr
llvm.store %238, %241 : i32, !llvm.ptr
cf.br ^bb53
^bb53:
%242 = llvm.load %241 : !llvm.ptr -> i32
%243 = arith.constant 3 : i32
%244 = arith.cmpi sle, %242, %243 : i32
cf.cond_br %244, ^bb54, ^bb55
^bb54:
%245 = arith.constant 3 : i32
%247 = arith.constant 0 : i32
%246 = arith.subi %247, %245 : i32
%248 = llvm.mlir.constant(1 : i64) : i64
%249 = llvm.alloca %248 x i32 : (i64) -> !llvm.ptr
llvm.store %246, %249 : i32, !llvm.ptr
cf.br ^bb56
^bb56:
%250 = llvm.load %249 : !llvm.ptr -> i32
%251 = arith.constant 3 : i32
%252 = arith.cmpi sle, %250, %251 : i32
cf.cond_br %252, ^bb57, ^bb58
^bb57:
%253 = arith.constant 3 : i32
%255 = arith.constant 0 : i32
%254 = arith.subi %255, %253 : i32
%256 = llvm.mlir.constant(1 : i64) : i64
%257 = llvm.alloca %256 x i32 : (i64) -> !llvm.ptr
llvm.store %254, %257 : i32, !llvm.ptr
cf.br ^bb59
^bb59:
%258 = llvm.load %257 : !llvm.ptr -> i32
%259 = arith.constant 3 : i32
%260 = arith.cmpi sle, %258, %259 : i32
cf.cond_br %260, ^bb60, ^bb61
^bb60:
%262 = arith.constant 0 : i32
%263 = arith.extsi %262 : i32 to i64
%264 = llvm.getelementptr %153[%263] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%261 = llvm.load %264 : !llvm.ptr -> i32
%265 = llvm.load %209 : !llvm.ptr -> i32
%266 = arith.addi %261, %265 : i32
%267 = arith.constant 0 : i32
%268 = arith.extsi %267 : i32 to i64
%269 = llvm.getelementptr %189[%268] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %266, %269 : i32, !llvm.ptr
%271 = arith.constant 1 : i32
%272 = arith.extsi %271 : i32 to i64
%273 = llvm.getelementptr %153[%272] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%270 = llvm.load %273 : !llvm.ptr -> i32
%274 = llvm.load %217 : !llvm.ptr -> i32
%275 = arith.addi %270, %274 : i32
%276 = arith.constant 1 : i32
%277 = arith.extsi %276 : i32 to i64
%278 = llvm.getelementptr %189[%277] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %275, %278 : i32, !llvm.ptr
%280 = arith.constant 2 : i32
%281 = arith.extsi %280 : i32 to i64
%282 = llvm.getelementptr %153[%281] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%279 = llvm.load %282 : !llvm.ptr -> i32
%283 = llvm.load %225 : !llvm.ptr -> i32
%284 = arith.addi %279, %283 : i32
%285 = arith.constant 2 : i32
%286 = arith.extsi %285 : i32 to i64
%287 = llvm.getelementptr %189[%286] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %284, %287 : i32, !llvm.ptr
%289 = arith.constant 3 : i32
%290 = arith.extsi %289 : i32 to i64
%291 = llvm.getelementptr %153[%290] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%288 = llvm.load %291 : !llvm.ptr -> i32
%292 = llvm.load %233 : !llvm.ptr -> i32
%293 = arith.addi %288, %292 : i32
%294 = arith.constant 3 : i32
%295 = arith.extsi %294 : i32 to i64
%296 = llvm.getelementptr %189[%295] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %293, %296 : i32, !llvm.ptr
%298 = arith.constant 4 : i32
%299 = arith.extsi %298 : i32 to i64
%300 = llvm.getelementptr %153[%299] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%297 = llvm.load %300 : !llvm.ptr -> i32
%301 = llvm.load %241 : !llvm.ptr -> i32
%302 = arith.addi %297, %301 : i32
%303 = arith.constant 4 : i32
%304 = arith.extsi %303 : i32 to i64
%305 = llvm.getelementptr %189[%304] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %302, %305 : i32, !llvm.ptr
%307 = arith.constant 5 : i32
%308 = arith.extsi %307 : i32 to i64
%309 = llvm.getelementptr %153[%308] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%306 = llvm.load %309 : !llvm.ptr -> i32
%310 = llvm.load %249 : !llvm.ptr -> i32
%311 = arith.addi %306, %310 : i32
%312 = arith.constant 5 : i32
%313 = arith.extsi %312 : i32 to i64
%314 = llvm.getelementptr %189[%313] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %311, %314 : i32, !llvm.ptr
%316 = arith.constant 6 : i32
%317 = arith.extsi %316 : i32 to i64
%318 = llvm.getelementptr %153[%317] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%315 = llvm.load %318 : !llvm.ptr -> i32
%319 = llvm.load %257 : !llvm.ptr -> i32
%320 = arith.addi %315, %319 : i32
%321 = arith.constant 6 : i32
%322 = arith.extsi %321 : i32 to i64
%323 = llvm.getelementptr %189[%322] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %320, %323 : i32, !llvm.ptr
%325 = arith.constant 0 : i32
%326 = arith.extsi %325 : i32 to i64
%327 = llvm.getelementptr %189[%326] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%324 = llvm.load %327 : !llvm.ptr -> i32
%328 = arith.constant 0 : i32
%329 = arith.cmpi sgt, %324, %328 : i32
%330 = scf.if %329 -> (i1) {
%332 = arith.constant 0 : i32
%333 = arith.extsi %332 : i32 to i64
%334 = llvm.getelementptr %189[%333] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%331 = llvm.load %334 : !llvm.ptr -> i32
%336 = arith.constant 1 : i32
%337 = arith.extsi %336 : i32 to i64
%338 = llvm.getelementptr %189[%337] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%335 = llvm.load %338 : !llvm.ptr -> i32
%339 = arith.cmpi slt, %331, %335 : i32
scf.yield %339 : i1
} else {
%340 = arith.constant false
scf.yield %340 : i1
}
%341 = scf.if %330 -> (i1) {
%343 = arith.constant 1 : i32
%344 = arith.extsi %343 : i32 to i64
%345 = llvm.getelementptr %189[%344] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%342 = llvm.load %345 : !llvm.ptr -> i32
%347 = arith.constant 2 : i32
%348 = arith.extsi %347 : i32 to i64
%349 = llvm.getelementptr %189[%348] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%346 = llvm.load %349 : !llvm.ptr -> i32
%350 = arith.cmpi slt, %342, %346 : i32
scf.yield %350 : i1
} else {
%351 = arith.constant false
scf.yield %351 : i1
}
%352 = scf.if %341 -> (i1) {
%354 = arith.constant 2 : i32
%355 = arith.extsi %354 : i32 to i64
%356 = llvm.getelementptr %189[%355] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%353 = llvm.load %356 : !llvm.ptr -> i32
%358 = arith.constant 3 : i32
%359 = arith.extsi %358 : i32 to i64
%360 = llvm.getelementptr %189[%359] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%357 = llvm.load %360 : !llvm.ptr -> i32
%361 = arith.cmpi slt, %353, %357 : i32
scf.yield %361 : i1
} else {
%362 = arith.constant false
scf.yield %362 : i1
}
%363 = scf.if %352 -> (i1) {
%365 = arith.constant 3 : i32
%366 = arith.extsi %365 : i32 to i64
%367 = llvm.getelementptr %189[%366] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%364 = llvm.load %367 : !llvm.ptr -> i32
%369 = arith.constant 4 : i32
%370 = arith.extsi %369 : i32 to i64
%371 = llvm.getelementptr %189[%370] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%368 = llvm.load %371 : !llvm.ptr -> i32
%372 = arith.cmpi slt, %364, %368 : i32
scf.yield %372 : i1
} else {
%373 = arith.constant false
scf.yield %373 : i1
}
%374 = scf.if %363 -> (i1) {
%376 = arith.constant 4 : i32
%377 = arith.extsi %376 : i32 to i64
%378 = llvm.getelementptr %189[%377] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%375 = llvm.load %378 : !llvm.ptr -> i32
%380 = arith.constant 5 : i32
%381 = arith.extsi %380 : i32 to i64
%382 = llvm.getelementptr %189[%381] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%379 = llvm.load %382 : !llvm.ptr -> i32
%383 = arith.cmpi slt, %375, %379 : i32
scf.yield %383 : i1
} else {
%384 = arith.constant false
scf.yield %384 : i1
}
%385 = scf.if %374 -> (i1) {
%387 = arith.constant 5 : i32
%388 = arith.extsi %387 : i32 to i64
%389 = llvm.getelementptr %189[%388] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%386 = llvm.load %389 : !llvm.ptr -> i32
%391 = arith.constant 6 : i32
%392 = arith.extsi %391 : i32 to i64
%393 = llvm.getelementptr %189[%392] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%390 = llvm.load %393 : !llvm.ptr -> i32
%394 = arith.cmpi slt, %386, %390 : i32
scf.yield %394 : i1
} else {
%395 = arith.constant false
scf.yield %395 : i1
}
cf.cond_br %385, ^bb62, ^bb63
^bb62:
%396 = arith.constant 0 : i32
%397 = llvm.mlir.constant(1 : i64) : i64
%398 = llvm.alloca %397 x i32 : (i64) -> !llvm.ptr
llvm.store %396, %398 : i32, !llvm.ptr
%399 = arith.constant 0 : i32
%400 = llvm.mlir.constant(1 : i64) : i64
%401 = llvm.alloca %400 x i32 : (i64) -> !llvm.ptr
llvm.store %399, %401 : i32, !llvm.ptr
cf.br ^bb65
^bb65:
%402 = llvm.load %401 : !llvm.ptr -> i32
%403 = arith.constant 7 : i32
%404 = arith.cmpi slt, %402, %403 : i32
cf.cond_br %404, ^bb66, ^bb67
^bb66:
%405 = llvm.load %398 : !llvm.ptr -> i32
%407 = llvm.load %401 : !llvm.ptr -> i32
%408 = arith.extsi %407 : i32 to i64
%409 = llvm.getelementptr %189[%408] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%406 = llvm.load %409 : !llvm.ptr -> i32
%410 = arith.addi %405, %406 : i32
llvm.store %410, %398 : i32, !llvm.ptr
%411 = llvm.load %401 : !llvm.ptr -> i32
%412 = arith.constant 1 : i32
%413 = arith.addi %411, %412 : i32
llvm.store %413, %401 : i32, !llvm.ptr
cf.br ^bb65
^bb67:
%414 = llvm.load %398 : !llvm.ptr -> i32
%415 = llvm.load %200 : !llvm.ptr -> i32
%416 = arith.cmpi slt, %414, %415 : i32
%417 = scf.if %416 -> (i1) {
%419 = arith.constant 7 : i32
%418 = func.call @is_special(%189, %419) : (!llvm.ptr, i32) -> i1
scf.yield %418 : i1
} else {
%420 = arith.constant false
scf.yield %420 : i1
}
cf.cond_br %417, ^bb68, ^bb69
^bb68:
%421 = llvm.load %398 : !llvm.ptr -> i32
llvm.store %421, %200 : i32, !llvm.ptr
%422 = func.call @concat7(%189) : (!llvm.ptr) -> i64
llvm.store %422, %204 : i64, !llvm.ptr
cf.br ^bb70
^bb69:
cf.br ^bb70
^bb70:
cf.br ^bb64
^bb63:
cf.br ^bb64
^bb64:
%423 = llvm.load %257 : !llvm.ptr -> i32
%424 = arith.constant 1 : i32
%425 = arith.addi %423, %424 : i32
llvm.store %425, %257 : i32, !llvm.ptr
cf.br ^bb59
^bb61:
%426 = llvm.load %249 : !llvm.ptr -> i32
%427 = arith.constant 1 : i32
%428 = arith.addi %426, %427 : i32
llvm.store %428, %249 : i32, !llvm.ptr
cf.br ^bb56
^bb58:
%429 = llvm.load %241 : !llvm.ptr -> i32
%430 = arith.constant 1 : i32
%431 = arith.addi %429, %430 : i32
llvm.store %431, %241 : i32, !llvm.ptr
cf.br ^bb53
^bb55:
%432 = llvm.load %233 : !llvm.ptr -> i32
%433 = arith.constant 1 : i32
%434 = arith.addi %432, %433 : i32
llvm.store %434, %233 : i32, !llvm.ptr
cf.br ^bb50
^bb52:
%435 = llvm.load %225 : !llvm.ptr -> i32
%436 = arith.constant 1 : i32
%437 = arith.addi %435, %436 : i32
llvm.store %437, %225 : i32, !llvm.ptr
cf.br ^bb47
^bb49:
%438 = llvm.load %217 : !llvm.ptr -> i32
%439 = arith.constant 1 : i32
%440 = arith.addi %438, %439 : i32
llvm.store %440, %217 : i32, !llvm.ptr
cf.br ^bb44
^bb46:
%441 = llvm.load %209 : !llvm.ptr -> i32
%442 = arith.constant 1 : i32
%443 = arith.addi %441, %442 : i32
llvm.store %443, %209 : i32, !llvm.ptr
cf.br ^bb41
^bb43:
%444 = llvm.mlir.addressof @str_0 : !llvm.ptr
%445 = llvm.load %204 : !llvm.ptr -> i64
%446 = llvm.call @printf(%444, %445) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%189) : (!llvm.ptr) -> ()
func.call @free(%153) : (!llvm.ptr) -> ()
%449 = arith.constant 0 : i32
func.return %449 : i32
}
}