← All problems Problem 951
Count length 2n strings with n R, n B and no maximal run of length 2. Answer = C(2n,n) - count_balanced_no_run2(n) for n=26.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(1)?Space complexity O(n)?Approach Flow solution Not curated Verdict Unknown
Flow source
# Project Euler 951: Unique Subsets
# Count length 2n strings with n R, n B and no maximal run of length 2.
# Answer = C(2n,n) - count_balanced_no_run2(n) for n=26.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function memset(dst: ptr<void>, val: i32, n: i64) -> void
}
function comb(n: i32, k0: i32) -> i64 {
if k0 < 0 || k0 > n { return 0 }
let mut k: i32 = k0
if k > n - k { k = n - k }
let mut result: i64 = 1
let mut i: i32 = 0
while i < k {
result = result * (n - i) as i64 / (i + 1) as i64
i = i + 1
}
return result
}
function idx(r: i32, last: i32, rs: i32) -> i64 {
return (r as i64) * 6 + (last as i64) * 3 + (rs as i64)
}
function count_balanced_no_run2(n: i32) -> i64 {
if n <= 0 {
if n == 0 { return 1 }
return 0
}
let L: i32 = 2 * n
let R: i32 = n + 1
let sz: i64 = (R as i64) * 6
let mut dp: ptr<i64> = calloc(sz, 8)
let mut nw: ptr<i64> = calloc(sz, 8)
dp[idx(1, 0, 0)] = 1
dp[idx(0, 1, 0)] = 1
let mut pos: i32 = 1
while pos < L {
memset(nw as ptr<void>, 0, sz * 8)
let mut r: i32 = 0
while r <= n {
let b: i32 = pos - r
if b < 0 || b > n {
r = r + 1
continue
}
let mut last: i32 = 0
while last < 2 {
let mut rs: i32 = 0
while rs < 3 {
let val: i64 = dp[idx(r, last, rs)]
if val != 0 {
let rscat: i32 = rs + 1
if r + 1 <= n {
if last == 0 {
let mut nrs: i32 = rscat + 1
if rscat >= 3 { nrs = 3 }
nw[idx(r + 1, 0, nrs - 1)] = nw[idx(r + 1, 0, nrs - 1)] + val
} else {
if rscat != 2 {
nw[idx(r + 1, 0, 0)] = nw[idx(r + 1, 0, 0)] + val
}
}
}
if b + 1 <= n {
if last == 1 {
let mut nrs: i32 = rscat + 1
if rscat >= 3 { nrs = 3 }
nw[idx(r, 1, nrs - 1)] = nw[idx(r, 1, nrs - 1)] + val
} else {
if rscat != 2 {
nw[idx(r, 1, 0)] = nw[idx(r, 1, 0)] + val
}
}
}
}
rs = rs + 1
}
last = last + 1
}
r = r + 1
}
let tmp: ptr<i64> = dp
dp = nw
nw = tmp
pos = pos + 1
}
let mut total: i64 = 0
let mut last: i32 = 0
while last < 2 {
total = total + dp[idx(n, last, 0)]
total = total + dp[idx(n, last, 2)]
last = last + 1
}
free(dp)
free(nw)
return total
}
function main() -> i32 {
let n: i32 = 26
let total: i64 = comb(2 * n, n)
let unfair: i64 = count_balanced_no_run2(n)
printf("%lld\n", total - unfair)
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 comb_i32_i32(int32_t n, int32_t k0);
int64_t idx_i32_i32_i32(int32_t r, int32_t last, int32_t rs);
int64_t count_balanced_no_run2_i32(int32_t n);
int32_t main(void);
int64_t comb_i32_i32(int32_t n, int32_t k0) {
if ((k0 < 0 || k0 > n)) {
return 0;
}
int32_t k = k0;
if (k > (n - k)) {
k = (n - k);
}
int64_t result = 1;
int32_t i = 0;
while (i < k) {
result = FLOW_CHECKED_DIV(((result * ((int64_t)((n - i))))), (((int64_t)((i + 1)))));
i = (i + 1);
}
return result;
}
int64_t idx_i32_i32_i32(int32_t r, int32_t last, int32_t rs) {
return (((((int64_t)(r)) * 6) + (((int64_t)(last)) * 3)) + ((int64_t)(rs)));
}
int64_t count_balanced_no_run2_i32(int32_t n) {
if (n <= 0) {
if (n == 0) {
return 1;
}
return 0;
}
int32_t L = (2 * n);
int32_t R = (n + 1);
int64_t sz = (((int64_t)(R)) * 6);
int64_t* dp = (int64_t*)(calloc(sz, 8));
int64_t* nw = (int64_t*)(calloc(sz, 8));
dp[idx_i32_i32_i32(1, 0, 0)] = 1;
dp[idx_i32_i32_i32(0, 1, 0)] = 1;
int32_t pos = 1;
while (pos < L) {
memset(((void*)(nw)), 0, (sz * 8));
int32_t r = 0;
while (r <= n) {
int32_t b = (pos - r);
if ((b < 0 || b > n)) {
r = (r + 1);
continue;
}
int32_t last = 0;
while (last < 2) {
int32_t rs = 0;
while (rs < 3) {
int64_t val = dp[idx_i32_i32_i32(r, last, rs)];
if (val != 0) {
int32_t rscat = (rs + 1);
if ((r + 1) <= n) {
if (last == 0) {
int32_t nrs = (rscat + 1);
if (rscat >= 3) {
nrs = 3;
}
nw[idx_i32_i32_i32((r + 1), 0, (nrs - 1))] = (nw[idx_i32_i32_i32((r + 1), 0, (nrs - 1))] + val);
} else {
if (rscat != 2) {
nw[idx_i32_i32_i32((r + 1), 0, 0)] = (nw[idx_i32_i32_i32((r + 1), 0, 0)] + val);
}
}
}
if ((b + 1) <= n) {
if (last == 1) {
int32_t nrs = (rscat + 1);
if (rscat >= 3) {
nrs = 3;
}
nw[idx_i32_i32_i32(r, 1, (nrs - 1))] = (nw[idx_i32_i32_i32(r, 1, (nrs - 1))] + val);
} else {
if (rscat != 2) {
nw[idx_i32_i32_i32(r, 1, 0)] = (nw[idx_i32_i32_i32(r, 1, 0)] + val);
}
}
}
}
rs = (rs + 1);
}
last = (last + 1);
}
r = (r + 1);
}
int64_t* tmp = (int64_t*)(dp);
dp = nw;
nw = tmp;
pos = (pos + 1);
}
int64_t total = 0;
int32_t last = 0;
while (last < 2) {
total = (total + dp[idx_i32_i32_i32(n, last, 0)]);
total = (total + dp[idx_i32_i32_i32(n, last, 2)]);
last = (last + 1);
}
free(dp);
free(nw);
return total;
}
int32_t main(void) {
int32_t n = 26;
int64_t total = comb_i32_i32((2 * n), n);
int64_t unfair = count_balanced_no_run2_i32(n);
printf("%lld\n", (total - unfair));
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 private @memset(!llvm.ptr, i32, i64) -> ()
func.func @comb(%arg0: i32, %arg1: i32) -> i64 {
%0 = arith.constant 0 : i32
%1 = arith.cmpi slt, %arg1, %0 : i32
%2 = scf.if %1 -> (i1) {
%3 = arith.constant true
scf.yield %3 : i1
} else {
%4 = arith.cmpi sgt, %arg1, %arg0 : i32
scf.yield %4 : i1
}
cf.cond_br %2, ^bb0, ^bb1
^bb0:
%5 = arith.constant 0 : i32
%6 = arith.extsi %5 : i32 to i64
func.return %6 : i64
^bb1:
cf.br ^bb2
^bb2:
%7 = llvm.mlir.constant(1 : i64) : i64
%8 = llvm.alloca %7 x i32 : (i64) -> !llvm.ptr
llvm.store %arg1, %8 : i32, !llvm.ptr
%9 = llvm.load %8 : !llvm.ptr -> i32
%10 = llvm.load %8 : !llvm.ptr -> i32
%11 = arith.subi %arg0, %10 : i32
%12 = arith.cmpi sgt, %9, %11 : i32
cf.cond_br %12, ^bb3, ^bb4
^bb3:
%13 = llvm.load %8 : !llvm.ptr -> i32
%14 = arith.subi %arg0, %13 : i32
llvm.store %14, %8 : i32, !llvm.ptr
cf.br ^bb5
^bb4:
cf.br ^bb5
^bb5:
%15 = arith.constant 1 : i32
%16 = arith.extsi %15 : i32 to i64
%17 = llvm.mlir.constant(1 : i64) : i64
%18 = llvm.alloca %17 x i64 : (i64) -> !llvm.ptr
llvm.store %16, %18 : i64, !llvm.ptr
%19 = arith.constant 0 : i32
%20 = llvm.mlir.constant(1 : i64) : i64
%21 = llvm.alloca %20 x i32 : (i64) -> !llvm.ptr
llvm.store %19, %21 : i32, !llvm.ptr
cf.br ^bb6
^bb6:
%22 = llvm.load %21 : !llvm.ptr -> i32
%23 = llvm.load %8 : !llvm.ptr -> i32
%24 = arith.cmpi slt, %22, %23 : i32
cf.cond_br %24, ^bb7, ^bb8
^bb7:
%25 = llvm.load %18 : !llvm.ptr -> i64
%26 = llvm.load %21 : !llvm.ptr -> i32
%27 = arith.subi %arg0, %26 : i32
%28 = arith.extsi %27 : i32 to i64
%29 = arith.muli %25, %28 : i64
%30 = llvm.load %21 : !llvm.ptr -> i32
%31 = arith.constant 1 : i32
%32 = arith.addi %30, %31 : i32
%33 = arith.extsi %32 : i32 to i64
%34 = arith.divsi %29, %33 : i64
llvm.store %34, %18 : i64, !llvm.ptr
%35 = llvm.load %21 : !llvm.ptr -> i32
%36 = arith.constant 1 : i32
%37 = arith.addi %35, %36 : i32
llvm.store %37, %21 : i32, !llvm.ptr
cf.br ^bb6
^bb8:
%38 = llvm.load %18 : !llvm.ptr -> i64
func.return %38 : i64
}
func.func @idx(%arg0: i32, %arg1: i32, %arg2: i32) -> i64 {
%39 = arith.extsi %arg0 : i32 to i64
%40 = arith.constant 6 : i32
%42 = arith.extsi %40 : i32 to i64
%41 = arith.muli %39, %42 : i64
%43 = arith.extsi %arg1 : i32 to i64
%44 = arith.constant 3 : i32
%46 = arith.extsi %44 : i32 to i64
%45 = arith.muli %43, %46 : i64
%47 = arith.addi %41, %45 : i64
%48 = arith.extsi %arg2 : i32 to i64
%49 = arith.addi %47, %48 : i64
func.return %49 : i64
}
func.func @count_balanced_no_run2(%arg0: i32) -> i64 {
%50 = arith.constant 0 : i32
%51 = arith.cmpi sle, %arg0, %50 : i32
cf.cond_br %51, ^bb9, ^bb10
^bb9:
%52 = arith.constant 0 : i32
%53 = arith.cmpi eq, %arg0, %52 : i32
cf.cond_br %53, ^bb12, ^bb13
^bb12:
%54 = arith.constant 1 : i32
%55 = arith.extsi %54 : i32 to i64
func.return %55 : i64
^bb13:
cf.br ^bb14
^bb14:
%56 = arith.constant 0 : i32
%57 = arith.extsi %56 : i32 to i64
func.return %57 : i64
^bb10:
cf.br ^bb11
^bb11:
%58 = arith.constant 2 : i32
%59 = arith.muli %58, %arg0 : i32
%60 = arith.constant 1 : i32
%61 = arith.addi %arg0, %60 : i32
%62 = arith.extsi %61 : i32 to i64
%63 = arith.constant 6 : i32
%65 = arith.extsi %63 : i32 to i64
%64 = arith.muli %62, %65 : i64
%67 = arith.constant 8 : i32
%68 = arith.extsi %67 : i32 to i64
%66 = func.call @calloc(%64, %68) : (i64, i64) -> !llvm.ptr
%69 = llvm.mlir.constant(1 : i64) : i64
%70 = llvm.alloca %69 x !llvm.ptr : (i64) -> !llvm.ptr
llvm.store %66, %70 : !llvm.ptr, !llvm.ptr
%72 = arith.constant 8 : i32
%73 = arith.extsi %72 : i32 to i64
%71 = func.call @calloc(%64, %73) : (i64, i64) -> !llvm.ptr
%74 = llvm.mlir.constant(1 : i64) : i64
%75 = llvm.alloca %74 x !llvm.ptr : (i64) -> !llvm.ptr
llvm.store %71, %75 : !llvm.ptr, !llvm.ptr
%76 = arith.constant 1 : i32
%77 = llvm.load %70 : !llvm.ptr -> !llvm.ptr
%79 = arith.constant 1 : i32
%80 = arith.constant 0 : i32
%81 = arith.constant 0 : i32
%78 = func.call @idx(%79, %80, %81) : (i32, i32, i32) -> i64
%82 = arith.extsi %76 : i32 to i64
%83 = llvm.getelementptr %77[%78] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %82, %83 : i64, !llvm.ptr
%84 = arith.constant 1 : i32
%85 = llvm.load %70 : !llvm.ptr -> !llvm.ptr
%87 = arith.constant 0 : i32
%88 = arith.constant 1 : i32
%89 = arith.constant 0 : i32
%86 = func.call @idx(%87, %88, %89) : (i32, i32, i32) -> i64
%90 = arith.extsi %84 : i32 to i64
%91 = llvm.getelementptr %85[%86] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %90, %91 : i64, !llvm.ptr
%92 = arith.constant 1 : i32
%93 = llvm.mlir.constant(1 : i64) : i64
%94 = llvm.alloca %93 x i32 : (i64) -> !llvm.ptr
llvm.store %92, %94 : i32, !llvm.ptr
cf.br ^bb15
^bb15:
%95 = llvm.load %94 : !llvm.ptr -> i32
%96 = arith.cmpi slt, %95, %59 : i32
cf.cond_br %96, ^bb16, ^bb17
^bb16:
%98 = llvm.load %75 : !llvm.ptr -> !llvm.ptr
%99 = arith.constant 0 : i32
%100 = arith.constant 8 : i32
%102 = arith.extsi %100 : i32 to i64
%101 = arith.muli %64, %102 : i64
func.call @memset(%98, %99, %101) : (!llvm.ptr, i32, i64) -> ()
%103 = arith.constant 0 : i32
%104 = llvm.mlir.constant(1 : i64) : i64
%105 = llvm.alloca %104 x i32 : (i64) -> !llvm.ptr
llvm.store %103, %105 : i32, !llvm.ptr
cf.br ^bb18
^bb18:
%106 = llvm.load %105 : !llvm.ptr -> i32
%107 = arith.cmpi sle, %106, %arg0 : i32
cf.cond_br %107, ^bb19, ^bb20
^bb19:
%108 = llvm.load %94 : !llvm.ptr -> i32
%109 = llvm.load %105 : !llvm.ptr -> i32
%110 = arith.subi %108, %109 : i32
%111 = arith.constant 0 : i32
%112 = arith.cmpi slt, %110, %111 : i32
%113 = scf.if %112 -> (i1) {
%114 = arith.constant true
scf.yield %114 : i1
} else {
%115 = arith.cmpi sgt, %110, %arg0 : i32
scf.yield %115 : i1
}
cf.cond_br %113, ^bb21, ^bb22
^bb21:
%116 = llvm.load %105 : !llvm.ptr -> i32
%117 = arith.constant 1 : i32
%118 = arith.addi %116, %117 : i32
llvm.store %118, %105 : i32, !llvm.ptr
cf.br ^bb18
^bb22:
cf.br ^bb23
^bb23:
%119 = arith.constant 0 : i32
%120 = llvm.mlir.constant(1 : i64) : i64
%121 = llvm.alloca %120 x i32 : (i64) -> !llvm.ptr
llvm.store %119, %121 : i32, !llvm.ptr
cf.br ^bb24
^bb24:
%122 = llvm.load %121 : !llvm.ptr -> i32
%123 = arith.constant 2 : i32
%124 = arith.cmpi slt, %122, %123 : i32
cf.cond_br %124, ^bb25, ^bb26
^bb25:
%125 = arith.constant 0 : i32
%126 = llvm.mlir.constant(1 : i64) : i64
%127 = llvm.alloca %126 x i32 : (i64) -> !llvm.ptr
llvm.store %125, %127 : i32, !llvm.ptr
cf.br ^bb27
^bb27:
%128 = llvm.load %127 : !llvm.ptr -> i32
%129 = arith.constant 3 : i32
%130 = arith.cmpi slt, %128, %129 : i32
cf.cond_br %130, ^bb28, ^bb29
^bb28:
%132 = llvm.load %70 : !llvm.ptr -> !llvm.ptr
%134 = llvm.load %105 : !llvm.ptr -> i32
%135 = llvm.load %121 : !llvm.ptr -> i32
%136 = llvm.load %127 : !llvm.ptr -> i32
%133 = func.call @idx(%134, %135, %136) : (i32, i32, i32) -> i64
%137 = llvm.getelementptr %132[%133] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%131 = llvm.load %137 : !llvm.ptr -> i64
%138 = arith.constant 0 : i32
%140 = arith.extsi %138 : i32 to i64
%139 = arith.cmpi ne, %131, %140 : i64
cf.cond_br %139, ^bb30, ^bb31
^bb30:
%141 = llvm.load %127 : !llvm.ptr -> i32
%142 = arith.constant 1 : i32
%143 = arith.addi %141, %142 : i32
%144 = llvm.load %105 : !llvm.ptr -> i32
%145 = arith.constant 1 : i32
%146 = arith.addi %144, %145 : i32
%147 = arith.cmpi sle, %146, %arg0 : i32
cf.cond_br %147, ^bb33, ^bb34
^bb33:
%148 = llvm.load %121 : !llvm.ptr -> i32
%149 = arith.constant 0 : i32
%150 = arith.cmpi eq, %148, %149 : i32
cf.cond_br %150, ^bb36, ^bb37
^bb36:
%151 = arith.constant 1 : i32
%152 = arith.addi %143, %151 : i32
%153 = llvm.mlir.constant(1 : i64) : i64
%154 = llvm.alloca %153 x i32 : (i64) -> !llvm.ptr
llvm.store %152, %154 : i32, !llvm.ptr
%155 = arith.constant 3 : i32
%156 = arith.cmpi sge, %143, %155 : i32
cf.cond_br %156, ^bb39, ^bb40
^bb39:
%157 = arith.constant 3 : i32
llvm.store %157, %154 : i32, !llvm.ptr
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
%159 = llvm.load %75 : !llvm.ptr -> !llvm.ptr
%161 = llvm.load %105 : !llvm.ptr -> i32
%162 = arith.constant 1 : i32
%163 = arith.addi %161, %162 : i32
%164 = arith.constant 0 : i32
%165 = llvm.load %154 : !llvm.ptr -> i32
%166 = arith.constant 1 : i32
%167 = arith.subi %165, %166 : i32
%160 = func.call @idx(%163, %164, %167) : (i32, i32, i32) -> i64
%168 = llvm.getelementptr %159[%160] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%158 = llvm.load %168 : !llvm.ptr -> i64
%169 = arith.addi %158, %131 : i64
%170 = llvm.load %75 : !llvm.ptr -> !llvm.ptr
%172 = llvm.load %105 : !llvm.ptr -> i32
%173 = arith.constant 1 : i32
%174 = arith.addi %172, %173 : i32
%175 = arith.constant 0 : i32
%176 = llvm.load %154 : !llvm.ptr -> i32
%177 = arith.constant 1 : i32
%178 = arith.subi %176, %177 : i32
%171 = func.call @idx(%174, %175, %178) : (i32, i32, i32) -> i64
%179 = llvm.getelementptr %170[%171] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %169, %179 : i64, !llvm.ptr
cf.br ^bb38
^bb37:
%180 = arith.constant 2 : i32
%181 = arith.cmpi ne, %143, %180 : i32
cf.cond_br %181, ^bb42, ^bb43
^bb42:
%183 = llvm.load %75 : !llvm.ptr -> !llvm.ptr
%185 = llvm.load %105 : !llvm.ptr -> i32
%186 = arith.constant 1 : i32
%187 = arith.addi %185, %186 : i32
%188 = arith.constant 0 : i32
%189 = arith.constant 0 : i32
%184 = func.call @idx(%187, %188, %189) : (i32, i32, i32) -> i64
%190 = llvm.getelementptr %183[%184] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%182 = llvm.load %190 : !llvm.ptr -> i64
%191 = arith.addi %182, %131 : i64
%192 = llvm.load %75 : !llvm.ptr -> !llvm.ptr
%194 = llvm.load %105 : !llvm.ptr -> i32
%195 = arith.constant 1 : i32
%196 = arith.addi %194, %195 : i32
%197 = arith.constant 0 : i32
%198 = arith.constant 0 : i32
%193 = func.call @idx(%196, %197, %198) : (i32, i32, i32) -> i64
%199 = llvm.getelementptr %192[%193] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %191, %199 : i64, !llvm.ptr
cf.br ^bb44
^bb43:
cf.br ^bb44
^bb44:
cf.br ^bb38
^bb38:
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
%200 = arith.constant 1 : i32
%201 = arith.addi %110, %200 : i32
%202 = arith.cmpi sle, %201, %arg0 : i32
cf.cond_br %202, ^bb45, ^bb46
^bb45:
%203 = llvm.load %121 : !llvm.ptr -> i32
%204 = arith.constant 1 : i32
%205 = arith.cmpi eq, %203, %204 : i32
cf.cond_br %205, ^bb48, ^bb49
^bb48:
%206 = arith.constant 1 : i32
%207 = arith.addi %143, %206 : i32
%208 = llvm.mlir.constant(1 : i64) : i64
%209 = llvm.alloca %208 x i32 : (i64) -> !llvm.ptr
llvm.store %207, %209 : i32, !llvm.ptr
%210 = arith.constant 3 : i32
%211 = arith.cmpi sge, %143, %210 : i32
cf.cond_br %211, ^bb51, ^bb52
^bb51:
%212 = arith.constant 3 : i32
llvm.store %212, %209 : i32, !llvm.ptr
cf.br ^bb53
^bb52:
cf.br ^bb53
^bb53:
%214 = llvm.load %75 : !llvm.ptr -> !llvm.ptr
%216 = llvm.load %105 : !llvm.ptr -> i32
%217 = arith.constant 1 : i32
%218 = llvm.load %209 : !llvm.ptr -> i32
%219 = arith.constant 1 : i32
%220 = arith.subi %218, %219 : i32
%215 = func.call @idx(%216, %217, %220) : (i32, i32, i32) -> i64
%221 = llvm.getelementptr %214[%215] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%213 = llvm.load %221 : !llvm.ptr -> i64
%222 = arith.addi %213, %131 : i64
%223 = llvm.load %75 : !llvm.ptr -> !llvm.ptr
%225 = llvm.load %105 : !llvm.ptr -> i32
%226 = arith.constant 1 : i32
%227 = llvm.load %209 : !llvm.ptr -> i32
%228 = arith.constant 1 : i32
%229 = arith.subi %227, %228 : i32
%224 = func.call @idx(%225, %226, %229) : (i32, i32, i32) -> i64
%230 = llvm.getelementptr %223[%224] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %222, %230 : i64, !llvm.ptr
cf.br ^bb50
^bb49:
%231 = arith.constant 2 : i32
%232 = arith.cmpi ne, %143, %231 : i32
cf.cond_br %232, ^bb54, ^bb55
^bb54:
%234 = llvm.load %75 : !llvm.ptr -> !llvm.ptr
%236 = llvm.load %105 : !llvm.ptr -> i32
%237 = arith.constant 1 : i32
%238 = arith.constant 0 : i32
%235 = func.call @idx(%236, %237, %238) : (i32, i32, i32) -> i64
%239 = llvm.getelementptr %234[%235] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%233 = llvm.load %239 : !llvm.ptr -> i64
%240 = arith.addi %233, %131 : i64
%241 = llvm.load %75 : !llvm.ptr -> !llvm.ptr
%243 = llvm.load %105 : !llvm.ptr -> i32
%244 = arith.constant 1 : i32
%245 = arith.constant 0 : i32
%242 = func.call @idx(%243, %244, %245) : (i32, i32, i32) -> i64
%246 = llvm.getelementptr %241[%242] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %240, %246 : i64, !llvm.ptr
cf.br ^bb56
^bb55:
cf.br ^bb56
^bb56:
cf.br ^bb50
^bb50:
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
cf.br ^bb32
^bb31:
cf.br ^bb32
^bb32:
%247 = llvm.load %127 : !llvm.ptr -> i32
%248 = arith.constant 1 : i32
%249 = arith.addi %247, %248 : i32
llvm.store %249, %127 : i32, !llvm.ptr
cf.br ^bb27
^bb29:
%250 = llvm.load %121 : !llvm.ptr -> i32
%251 = arith.constant 1 : i32
%252 = arith.addi %250, %251 : i32
llvm.store %252, %121 : i32, !llvm.ptr
cf.br ^bb24
^bb26:
%253 = llvm.load %105 : !llvm.ptr -> i32
%254 = arith.constant 1 : i32
%255 = arith.addi %253, %254 : i32
llvm.store %255, %105 : i32, !llvm.ptr
cf.br ^bb18
^bb20:
%256 = llvm.load %70 : !llvm.ptr -> !llvm.ptr
%257 = llvm.load %75 : !llvm.ptr -> !llvm.ptr
llvm.store %257, %70 : !llvm.ptr, !llvm.ptr
llvm.store %256, %75 : !llvm.ptr, !llvm.ptr
%258 = llvm.load %94 : !llvm.ptr -> i32
%259 = arith.constant 1 : i32
%260 = arith.addi %258, %259 : i32
llvm.store %260, %94 : i32, !llvm.ptr
cf.br ^bb15
^bb17:
%261 = arith.constant 0 : i32
%262 = arith.extsi %261 : i32 to i64
%263 = llvm.mlir.constant(1 : i64) : i64
%264 = llvm.alloca %263 x i64 : (i64) -> !llvm.ptr
llvm.store %262, %264 : i64, !llvm.ptr
%265 = arith.constant 0 : i32
%266 = llvm.mlir.constant(1 : i64) : i64
%267 = llvm.alloca %266 x i32 : (i64) -> !llvm.ptr
llvm.store %265, %267 : i32, !llvm.ptr
cf.br ^bb57
^bb57:
%268 = llvm.load %267 : !llvm.ptr -> i32
%269 = arith.constant 2 : i32
%270 = arith.cmpi slt, %268, %269 : i32
cf.cond_br %270, ^bb58, ^bb59
^bb58:
%271 = llvm.load %264 : !llvm.ptr -> i64
%273 = llvm.load %70 : !llvm.ptr -> !llvm.ptr
%275 = llvm.load %267 : !llvm.ptr -> i32
%276 = arith.constant 0 : i32
%274 = func.call @idx(%arg0, %275, %276) : (i32, i32, i32) -> i64
%277 = llvm.getelementptr %273[%274] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%272 = llvm.load %277 : !llvm.ptr -> i64
%278 = arith.addi %271, %272 : i64
llvm.store %278, %264 : i64, !llvm.ptr
%279 = llvm.load %264 : !llvm.ptr -> i64
%281 = llvm.load %70 : !llvm.ptr -> !llvm.ptr
%283 = llvm.load %267 : !llvm.ptr -> i32
%284 = arith.constant 2 : i32
%282 = func.call @idx(%arg0, %283, %284) : (i32, i32, i32) -> i64
%285 = llvm.getelementptr %281[%282] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%280 = llvm.load %285 : !llvm.ptr -> i64
%286 = arith.addi %279, %280 : i64
llvm.store %286, %264 : i64, !llvm.ptr
%287 = llvm.load %267 : !llvm.ptr -> i32
%288 = arith.constant 1 : i32
%289 = arith.addi %287, %288 : i32
llvm.store %289, %267 : i32, !llvm.ptr
cf.br ^bb57
^bb59:
%291 = llvm.load %70 : !llvm.ptr -> !llvm.ptr
func.call @free(%291) : (!llvm.ptr) -> ()
%293 = llvm.load %75 : !llvm.ptr -> !llvm.ptr
func.call @free(%293) : (!llvm.ptr) -> ()
%294 = llvm.load %264 : !llvm.ptr -> i64
func.return %294 : i64
}
func.func @main() -> i32 {
%295 = arith.constant 26 : i32
%297 = arith.constant 2 : i32
%298 = arith.muli %297, %295 : i32
%296 = func.call @comb(%298, %295) : (i32, i32) -> i64
%299 = func.call @count_balanced_no_run2(%295) : (i32) -> i64
%300 = llvm.mlir.addressof @str_0 : !llvm.ptr
%301 = arith.subi %296, %299 : i64
%302 = llvm.call @printf(%300, %301) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%303 = arith.constant 0 : i32
func.return %303 : i32
}
}