Problem 185

Number Mind: recover unique 16-digit sequence from guesses.

Answer	`4640261571849533`
Output	`4640261571849533`
Status	PASS
Native helper	no
Runtime	540 ms
Peak memory	1120 KB
Time complexity	`O(n^3)` (estimated)
Space complexity	`O(n)` (estimated)

Performance comparison

Metric	Our solution	Best known
Time complexity	`O(n^3)`	`O(n!)`
Space complexity	`O(n)`	`O(n)`
Approach	Flow solution	Permutation enumeration or constraint search
Verdict	Optimal

Flow source

# Project Euler 185
# Number Mind: recover unique 16-digit sequence from guesses.

extern {
    function calloc(n: i64, size: i64) -> ptr<void>
    function free(p: ptr<void>) -> void
    function fopen(path: string, mode: string) -> ptr<void>
    function fgetc(f: ptr<void>) -> i32
    function fclose(f: ptr<void>) -> i32
}

let mut seed: i64 = 0

function myrand(modulo: i32) -> i32 {
    seed = seed * 1103515245 + 12345
    # keep lower 32 bits
    seed = seed - (seed / 4294967296) * 4294967296
    if seed < 0 { seed = seed + 4294967296 }
    return (seed % (modulo as i64)) as i32
}

function shuffle_digit(digit: i32) -> i32 {
    let old: i32 = digit
    let mut d: i32 = myrand(10)
    while d == old {
        d = myrand(10)
    }
    return d
}

function distance(cur: ptr<i32>, seqs: ptr<i32>, hits: ptr<i32>, ng: i32, nd: i32) -> i32 {
    let mut errors: i32 = 0
    let mut i: i32 = 0
    while i < ng {
        let mut same: i32 = 0
        let mut j: i32 = 0
        while j < nd {
            if cur[j] == seqs[i * nd + j] { same = same + 1 }
            j = j + 1
        }
        if same > hits[i] { errors = errors + (same - hits[i]) }
        else { errors = errors + (hits[i] - same) }
        i = i + 1
    }
    return errors
}

function main() -> i32 {
    let f: ptr<void> = fopen("data/p185.txt", "r")
    if f == null {
        printf("missing data\n")
        return 1
    }
    let NG: i32 = 22
    let ND: i32 = 16
    let seqs: ptr<i32> = calloc((NG * ND) as i64, 4)
    let hits: ptr<i32> = calloc(NG as i64, 4)
    let cur: ptr<i32> = calloc(ND as i64, 4)
    if seqs == null || hits == null || cur == null { return 1 }

    let mut gi: i32 = 0
    let mut di: i32 = 0
    let mut in_guess: bool = true
    let mut hit_val: i32 = 0
    let mut reading_hit: bool = false
    let mut c: i32 = fgetc(f)
    while c >= 0 && gi < NG {
        if c >= 48 && c <= 57 {
            if in_guess && di < ND {
                seqs[gi * ND + di] = c - 48
                di = di + 1
            } elif reading_hit {
                hit_val = hit_val * 10 + (c - 48)
            }
        } elif c == 59 {
            in_guess = false
            reading_hit = true
            hit_val = 0
        } elif c == 10 || c == 13 {
            if di == ND {
                hits[gi] = hit_val
                gi = gi + 1
            }
            di = 0
            in_guess = true
            reading_hit = false
            hit_val = 0
        }
        c = fgetc(f)
    }
    # last line without newline
    if gi < NG && di == ND {
        hits[gi] = hit_val
        gi = gi + 1
    }
    fclose(f)
    if gi != NG {
        printf("parse fail %d\n", gi)
        return 1
    }

    let mut attempt: i32 = 0
    while attempt < 100 {
        seed = attempt as i64
        let mut i: i32 = 0
        while i < ND {
            cur[i] = myrand(10)
            i = i + 1
        }
        let mut errors: i32 = distance(cur, seqs, hits, NG, ND)
        let mut previous: i32 = errors
        let mut quiet: i32 = 0
        let mut steps: i32 = 0
        while errors != 0 && steps < 100000 {
            i = 0
            while i < ND {
                let prev_d: i32 = cur[i]
                cur[i] = shuffle_digit(prev_d)
                let modified: i32 = distance(cur, seqs, hits, NG, ND)
                if modified <= errors {
                    errors = modified
                } else {
                    cur[i] = prev_d
                }
                i = i + 1
            }
            if errors == previous {
                quiet = quiet + 1
                if quiet == 20 {
                    let idx: i32 = myrand(ND)
                    cur[idx] = shuffle_digit(cur[idx])
                    errors = distance(cur, seqs, hits, NG, ND)
                    quiet = 0
                }
            } else {
                quiet = 0
                previous = errors
            }
            steps = steps + 1
        }
        if errors == 0 { break }
        attempt = attempt + 1
    }

    let mut ans: i64 = 0
    let mut i: i32 = 0
    while i < ND {
        ans = ans * 10 + (cur[i] as i64)
        i = i + 1
    }
    printf("%lld\n", ans)
    free(seqs); free(hits); free(cur)
    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 myrand_i32(int32_t modulo);
int32_t shuffle_digit_i32(int32_t digit);
int32_t distance_ptr_i32_ptr_i32_ptr_i32_i32_i32(int32_t* cur, int32_t* seqs, int32_t* hits, int32_t ng, int32_t nd);
int32_t main(void);

/* Module statics */
static int64_t seed = 0;






int32_t myrand_i32(int32_t modulo) {
    seed = ((seed * 1103515245) + 12345);
    seed = (seed - (FLOW_CHECKED_DIV((seed), (4294967296)) * 4294967296));
    if (seed < 0) {
        seed = (seed + 4294967296);
    }
    return ((int32_t)(FLOW_CHECKED_MOD((seed), (((int64_t)(modulo))))));
}

int32_t shuffle_digit_i32(int32_t digit) {
    int32_t old = digit;
    int32_t d = myrand_i32(10);
    while (d == old) {
        d = myrand_i32(10);
    }
    return d;
}

int32_t distance_ptr_i32_ptr_i32_ptr_i32_i32_i32(int32_t* cur, int32_t* seqs, int32_t* hits, int32_t ng, int32_t nd) {
    int32_t errors = 0;
    int32_t i = 0;
    while (i < ng) {
        int32_t same = 0;
        int32_t j = 0;
        while (j < nd) {
            if (cur[j] == seqs[((i * nd) + j)]) {
                same = (same + 1);
            }
            j = (j + 1);
        }
        if (same > hits[i]) {
            errors = (errors + (same - hits[i]));
        } else {
            errors = (errors + (hits[i] - same));
        }
        i = (i + 1);
    }
    return errors;
}

int32_t main(void) {
    void* f = (void*)(fopen("data/p185.txt", "r"));
    if (f == NULL) {
        printf("missing data\n");
        return 1;
    }
    int32_t NG = 22;
    int32_t ND = 16;
    int32_t* seqs = (int32_t*)(calloc(((int64_t)((NG * ND))), 4));
    int32_t* hits = (int32_t*)(calloc(((int64_t)(NG)), 4));
    int32_t* cur = (int32_t*)(calloc(((int64_t)(ND)), 4));
    if (((seqs == NULL || hits == NULL) || cur == NULL)) {
        return 1;
    }
    int32_t gi = 0;
    int32_t di = 0;
    bool in_guess = 1;
    int32_t hit_val = 0;
    bool reading_hit = 0;
    int32_t c = fgetc(f);
    while ((c >= 0 && gi < NG)) {
        if ((c >= 48 && c <= 57)) {
            if ((in_guess && di < ND)) {
                seqs[((gi * ND) + di)] = (c - 48);
                di = (di + 1);
            } else if (reading_hit) {
                hit_val = ((hit_val * 10) + (c - 48));
            }
        } else if (c == 59) {
            in_guess = 0;
            reading_hit = 1;
            hit_val = 0;
        } else if ((c == 10 || c == 13)) {
            if (di == ND) {
                hits[gi] = hit_val;
                gi = (gi + 1);
            }
            di = 0;
            in_guess = 1;
            reading_hit = 0;
            hit_val = 0;
        }
        c = fgetc(f);
    }
    if ((gi < NG && di == ND)) {
        hits[gi] = hit_val;
        gi = (gi + 1);
    }
    fclose(f);
    if (gi != NG) {
        printf("parse fail %d\n", gi);
        return 1;
    }
    int32_t attempt = 0;
    while (attempt < 100) {
        seed = ((int64_t)(attempt));
        int32_t i = 0;
        while (i < ND) {
            cur[i] = myrand_i32(10);
            i = (i + 1);
        }
        int32_t errors = distance_ptr_i32_ptr_i32_ptr_i32_i32_i32(cur, seqs, hits, NG, ND);
        int32_t previous = errors;
        int32_t quiet = 0;
        int32_t steps = 0;
        while ((errors != 0 && steps < 100000)) {
            i = 0;
            while (i < ND) {
                int32_t prev_d = cur[i];
                cur[i] = shuffle_digit_i32(prev_d);
                int32_t modified = distance_ptr_i32_ptr_i32_ptr_i32_i32_i32(cur, seqs, hits, NG, ND);
                if (modified <= errors) {
                    errors = modified;
                } else {
                    cur[i] = prev_d;
                }
                i = (i + 1);
            }
            if (errors == previous) {
                quiet = (quiet + 1);
                if (quiet == 20) {
                    int32_t idx = myrand_i32(ND);
                    cur[idx] = shuffle_digit_i32(cur[idx]);
                    errors = distance_ptr_i32_ptr_i32_ptr_i32_i32_i32(cur, seqs, hits, NG, ND);
                    quiet = 0;
                }
            } else {
                quiet = 0;
                previous = errors;
            }
            steps = (steps + 1);
        }
        if (errors == 0) {
            break;
        }
        attempt = (attempt + 1);
    }
    int64_t ans = 0;
    int32_t i = 0;
    while (i < ND) {
        ans = ((ans * 10) + ((int64_t)(cur[i])));
        i = (i + 1);
    }
    printf("%lld\n", ans);
    free(seqs);
    free(hits);
    free(cur);
    return 0;
}

Generated MLIR

module {
  llvm.func @printf(!llvm.ptr, ...) -> i32
  llvm.mlir.global internal constant @str_0("data/p185.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("missing data\n\00") {addr_space = 0 : i32} : !llvm.array<14 x i8>
  llvm.mlir.global internal constant @str_3("parse fail %d\n\00") {addr_space = 0 : i32} : !llvm.array<15 x i8>
  llvm.mlir.global internal constant @str_4("%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 @fopen(!llvm.ptr, !llvm.ptr) -> !llvm.ptr
  func.func private @fgetc(!llvm.ptr) -> i32
  func.func private @fclose(!llvm.ptr) -> i32
  // Module static: seed
  llvm.mlir.global internal @seed(0 : i64) : i64
  func.func @myrand(%arg0: i32) -> i32 {
    %0 = llvm.mlir.addressof @seed : !llvm.ptr
    %1 = llvm.load %0 : !llvm.ptr -> i64
    %2 = arith.constant 1103515245 : i32
    %4 = arith.extsi %2 : i32 to i64
    %3 = arith.muli %1, %4 : i64
    %5 = arith.constant 12345 : i32
    %7 = arith.extsi %5 : i32 to i64
    %6 = arith.addi %3, %7 : i64
    %8 = llvm.mlir.addressof @seed : !llvm.ptr
    llvm.store %6, %8 : i64, !llvm.ptr
    %9 = llvm.mlir.addressof @seed : !llvm.ptr
    %10 = llvm.load %9 : !llvm.ptr -> i64
    %11 = llvm.mlir.addressof @seed : !llvm.ptr
    %12 = llvm.load %11 : !llvm.ptr -> i64
    %13 = arith.constant 0 : i32
    %15 = arith.extsi %13 : i32 to i64
    %14 = arith.divsi %12, %15 : i64
    %16 = arith.constant 0 : i32
    %18 = arith.extsi %16 : i32 to i64
    %17 = arith.muli %14, %18 : i64
    %19 = arith.subi %10, %17 : i64
    %20 = llvm.mlir.addressof @seed : !llvm.ptr
    llvm.store %19, %20 : i64, !llvm.ptr
    %21 = llvm.mlir.addressof @seed : !llvm.ptr
    %22 = llvm.load %21 : !llvm.ptr -> i64
    %23 = arith.constant 0 : i32
    %25 = arith.extsi %23 : i32 to i64
    %24 = arith.cmpi slt, %22, %25 : i64
    cf.cond_br %24, ^bb0, ^bb1
    ^bb0:
      %26 = llvm.mlir.addressof @seed : !llvm.ptr
      %27 = llvm.load %26 : !llvm.ptr -> i64
      %28 = arith.constant 0 : i32
      %30 = arith.extsi %28 : i32 to i64
      %29 = arith.addi %27, %30 : i64
      %31 = llvm.mlir.addressof @seed : !llvm.ptr
      llvm.store %29, %31 : i64, !llvm.ptr
      cf.br ^bb2
    ^bb1:
      cf.br ^bb2
    ^bb2:
    %32 = llvm.mlir.addressof @seed : !llvm.ptr
    %33 = llvm.load %32 : !llvm.ptr -> i64
    %34 = arith.extsi %arg0 : i32 to i64
    %35 = arith.remsi %33, %34 : i64
    %36 = arith.trunci %35 : i64 to i32
    func.return %36 : i32
  }
  func.func @shuffle_digit(%arg0: i32) -> i32 {
    %38 = arith.constant 10 : i32
    %37 = func.call @myrand(%38) : (i32) -> i32
    %39 = llvm.mlir.constant(1 : i64) : i64
    %40 = llvm.alloca %39 x i32 : (i64) -> !llvm.ptr
    llvm.store %37, %40 : i32, !llvm.ptr
    cf.br ^bb3
    ^bb3:
    %41 = llvm.load %40 : !llvm.ptr -> i32
    %42 = arith.cmpi eq, %41, %arg0 : i32
    cf.cond_br %42, ^bb4, ^bb5
    ^bb4:
      %44 = arith.constant 10 : i32
      %43 = func.call @myrand(%44) : (i32) -> i32
      llvm.store %43, %40 : i32, !llvm.ptr
      cf.br ^bb3
    ^bb5:
    %45 = llvm.load %40 : !llvm.ptr -> i32
    func.return %45 : i32
  }
  func.func @distance(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: i32, %arg4: i32) -> i32 {
    %46 = arith.constant 0 : i32
    %47 = llvm.mlir.constant(1 : i64) : i64
    %48 = llvm.alloca %47 x i32 : (i64) -> !llvm.ptr
    llvm.store %46, %48 : i32, !llvm.ptr
    %49 = arith.constant 0 : i32
    %50 = llvm.mlir.constant(1 : i64) : i64
    %51 = llvm.alloca %50 x i32 : (i64) -> !llvm.ptr
    llvm.store %49, %51 : i32, !llvm.ptr
    cf.br ^bb6
    ^bb6:
    %52 = llvm.load %51 : !llvm.ptr -> i32
    %53 = arith.cmpi slt, %52, %arg3 : i32
    cf.cond_br %53, ^bb7, ^bb8
    ^bb7:
      %54 = arith.constant 0 : i32
      %55 = llvm.mlir.constant(1 : i64) : i64
      %56 = llvm.alloca %55 x i32 : (i64) -> !llvm.ptr
      llvm.store %54, %56 : i32, !llvm.ptr
      %57 = arith.constant 0 : i32
      %58 = llvm.mlir.constant(1 : i64) : i64
      %59 = llvm.alloca %58 x i32 : (i64) -> !llvm.ptr
      llvm.store %57, %59 : i32, !llvm.ptr
      cf.br ^bb9
      ^bb9:
      %60 = llvm.load %59 : !llvm.ptr -> i32
      %61 = arith.cmpi slt, %60, %arg4 : i32
      cf.cond_br %61, ^bb10, ^bb11
      ^bb10:
        %63 = llvm.load %59 : !llvm.ptr -> i32
        %64 = arith.extsi %63 : i32 to i64
        %65 = llvm.getelementptr %arg0[%64] : (!llvm.ptr, i64) -> !llvm.ptr, i32
        %62 = llvm.load %65 : !llvm.ptr -> i32
        %67 = llvm.load %51 : !llvm.ptr -> i32
        %68 = arith.muli %67, %arg4 : i32
        %69 = llvm.load %59 : !llvm.ptr -> i32
        %70 = arith.addi %68, %69 : i32
        %71 = arith.extsi %70 : i32 to i64
        %72 = llvm.getelementptr %arg1[%71] : (!llvm.ptr, i64) -> !llvm.ptr, i32
        %66 = llvm.load %72 : !llvm.ptr -> i32
        %73 = arith.cmpi eq, %62, %66 : i32
        cf.cond_br %73, ^bb12, ^bb13
        ^bb12:
          %74 = llvm.load %56 : !llvm.ptr -> i32
          %75 = arith.constant 1 : i32
          %76 = arith.addi %74, %75 : i32
          llvm.store %76, %56 : i32, !llvm.ptr
          cf.br ^bb14
        ^bb13:
          cf.br ^bb14
        ^bb14:
        %77 = llvm.load %59 : !llvm.ptr -> i32
        %78 = arith.constant 1 : i32
        %79 = arith.addi %77, %78 : i32
        llvm.store %79, %59 : i32, !llvm.ptr
        cf.br ^bb9
      ^bb11:
      %80 = llvm.load %56 : !llvm.ptr -> i32
      %82 = llvm.load %51 : !llvm.ptr -> i32
      %83 = arith.extsi %82 : i32 to i64
      %84 = llvm.getelementptr %arg2[%83] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      %81 = llvm.load %84 : !llvm.ptr -> i32
      %85 = arith.cmpi sgt, %80, %81 : i32
      cf.cond_br %85, ^bb15, ^bb16
      ^bb15:
        %86 = llvm.load %48 : !llvm.ptr -> i32
        %87 = llvm.load %56 : !llvm.ptr -> i32
        %89 = llvm.load %51 : !llvm.ptr -> i32
        %90 = arith.extsi %89 : i32 to i64
        %91 = llvm.getelementptr %arg2[%90] : (!llvm.ptr, i64) -> !llvm.ptr, i32
        %88 = llvm.load %91 : !llvm.ptr -> i32
        %92 = arith.subi %87, %88 : i32
        %93 = arith.addi %86, %92 : i32
        llvm.store %93, %48 : i32, !llvm.ptr
        cf.br ^bb17
      ^bb16:
        %94 = llvm.load %48 : !llvm.ptr -> i32
        %96 = llvm.load %51 : !llvm.ptr -> i32
        %97 = arith.extsi %96 : i32 to i64
        %98 = llvm.getelementptr %arg2[%97] : (!llvm.ptr, i64) -> !llvm.ptr, i32
        %95 = llvm.load %98 : !llvm.ptr -> i32
        %99 = llvm.load %56 : !llvm.ptr -> i32
        %100 = arith.subi %95, %99 : i32
        %101 = arith.addi %94, %100 : i32
        llvm.store %101, %48 : i32, !llvm.ptr
        cf.br ^bb17
      ^bb17:
      %102 = llvm.load %51 : !llvm.ptr -> i32
      %103 = arith.constant 1 : i32
      %104 = arith.addi %102, %103 : i32
      llvm.store %104, %51 : i32, !llvm.ptr
      cf.br ^bb6
    ^bb8:
    %105 = llvm.load %48 : !llvm.ptr -> i32
    func.return %105 : i32
  }
  func.func @main() -> i32 {
    %107 = llvm.mlir.addressof @str_0 : !llvm.ptr
    %108 = llvm.mlir.addressof @str_1 : !llvm.ptr
    %106 = func.call @fopen(%107, %108) : (!llvm.ptr, !llvm.ptr) -> !llvm.ptr
    %109 = llvm.mlir.zero : !llvm.ptr
    %110 = llvm.icmp "eq" %106, %109 : !llvm.ptr
    cf.cond_br %110, ^bb18, ^bb19
    ^bb18:
      %111 = llvm.mlir.addressof @str_2 : !llvm.ptr
      %112 = llvm.call @printf(%111) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr) -> i32
      %113 = arith.constant 1 : i32
      func.return %113 : i32
    ^bb19:
      cf.br ^bb20
    ^bb20:
    %114 = arith.constant 22 : i32
    %115 = arith.constant 16 : i32
    %117 = arith.muli %114, %115 : i32
    %118 = arith.extsi %117 : i32 to i64
    %119 = arith.constant 4 : i32
    %120 = arith.extsi %119 : i32 to i64
    %116 = func.call @calloc(%118, %120) : (i64, i64) -> !llvm.ptr
    %122 = arith.extsi %114 : i32 to i64
    %123 = arith.constant 4 : i32
    %124 = arith.extsi %123 : i32 to i64
    %121 = func.call @calloc(%122, %124) : (i64, i64) -> !llvm.ptr
    %126 = arith.extsi %115 : i32 to i64
    %127 = arith.constant 4 : i32
    %128 = arith.extsi %127 : i32 to i64
    %125 = func.call @calloc(%126, %128) : (i64, i64) -> !llvm.ptr
    %129 = llvm.mlir.zero : !llvm.ptr
    %130 = llvm.icmp "eq" %116, %129 : !llvm.ptr
    %131 = scf.if %130 -> (i1) {
      %132 = arith.constant true
      scf.yield %132 : i1
    } else {
      %133 = llvm.mlir.zero : !llvm.ptr
      %134 = llvm.icmp "eq" %121, %133 : !llvm.ptr
      scf.yield %134 : i1
    }
    %135 = scf.if %131 -> (i1) {
      %136 = arith.constant true
      scf.yield %136 : i1
    } else {
      %137 = llvm.mlir.zero : !llvm.ptr
      %138 = llvm.icmp "eq" %125, %137 : !llvm.ptr
      scf.yield %138 : i1
    }
    cf.cond_br %135, ^bb21, ^bb22
    ^bb21:
      %139 = arith.constant 1 : i32
      func.return %139 : i32
    ^bb22:
      cf.br ^bb23
    ^bb23:
    %140 = arith.constant 0 : i32
    %141 = llvm.mlir.constant(1 : i64) : i64
    %142 = llvm.alloca %141 x i32 : (i64) -> !llvm.ptr
    llvm.store %140, %142 : i32, !llvm.ptr
    %143 = arith.constant 0 : i32
    %144 = llvm.mlir.constant(1 : i64) : i64
    %145 = llvm.alloca %144 x i32 : (i64) -> !llvm.ptr
    llvm.store %143, %145 : i32, !llvm.ptr
    %146 = arith.constant 1 : i1
    %147 = llvm.mlir.constant(1 : i64) : i64
    %148 = llvm.alloca %147 x i1 : (i64) -> !llvm.ptr
    llvm.store %146, %148 : i1, !llvm.ptr
    %149 = arith.constant 0 : i32
    %150 = llvm.mlir.constant(1 : i64) : i64
    %151 = llvm.alloca %150 x i32 : (i64) -> !llvm.ptr
    llvm.store %149, %151 : i32, !llvm.ptr
    %152 = arith.constant 0 : i1
    %153 = llvm.mlir.constant(1 : i64) : i64
    %154 = llvm.alloca %153 x i1 : (i64) -> !llvm.ptr
    llvm.store %152, %154 : i1, !llvm.ptr
    %155 = func.call @fgetc(%106) : (!llvm.ptr) -> i32
    %156 = llvm.mlir.constant(1 : i64) : i64
    %157 = llvm.alloca %156 x i32 : (i64) -> !llvm.ptr
    llvm.store %155, %157 : i32, !llvm.ptr
    cf.br ^bb24
    ^bb24:
    %158 = llvm.load %157 : !llvm.ptr -> i32
    %159 = arith.constant 0 : i32
    %160 = arith.cmpi sge, %158, %159 : i32
    %161 = scf.if %160 -> (i1) {
      %162 = llvm.load %142 : !llvm.ptr -> i32
      %163 = arith.cmpi slt, %162, %114 : i32
      scf.yield %163 : i1
    } else {
      %164 = arith.constant false
      scf.yield %164 : i1
    }
    cf.cond_br %161, ^bb25, ^bb26
    ^bb25:
      %165 = llvm.load %157 : !llvm.ptr -> i32
      %166 = arith.constant 48 : i32
      %167 = arith.cmpi sge, %165, %166 : i32
      %168 = scf.if %167 -> (i1) {
        %169 = llvm.load %157 : !llvm.ptr -> i32
        %170 = arith.constant 57 : i32
        %171 = arith.cmpi sle, %169, %170 : i32
        scf.yield %171 : i1
      } else {
        %172 = arith.constant false
        scf.yield %172 : i1
      }
      cf.cond_br %168, ^bb27, ^bb28
      ^bb27:
        %173 = llvm.load %148 : !llvm.ptr -> i1
        %174 = scf.if %173 -> (i1) {
          %175 = llvm.load %145 : !llvm.ptr -> i32
          %176 = arith.cmpi slt, %175, %115 : i32
          scf.yield %176 : i1
        } else {
          %177 = arith.constant false
          scf.yield %177 : i1
        }
        cf.cond_br %174, ^bb30, ^bb31
        ^bb30:
          %178 = llvm.load %157 : !llvm.ptr -> i32
          %179 = arith.constant 48 : i32
          %180 = arith.subi %178, %179 : i32
          %181 = llvm.load %142 : !llvm.ptr -> i32
          %182 = arith.muli %181, %115 : i32
          %183 = llvm.load %145 : !llvm.ptr -> i32
          %184 = arith.addi %182, %183 : i32
          %185 = arith.extsi %184 : i32 to i64
          %186 = llvm.getelementptr %116[%185] : (!llvm.ptr, i64) -> !llvm.ptr, i32
          llvm.store %180, %186 : i32, !llvm.ptr
          %187 = llvm.load %145 : !llvm.ptr -> i32
          %188 = arith.constant 1 : i32
          %189 = arith.addi %187, %188 : i32
          llvm.store %189, %145 : i32, !llvm.ptr
          cf.br ^bb32
        ^bb31:
          %190 = llvm.load %154 : !llvm.ptr -> i1
          cf.cond_br %190, ^bb33, ^bb32
        ^bb33:
          %191 = llvm.load %151 : !llvm.ptr -> i32
          %192 = arith.constant 10 : i32
          %193 = arith.muli %191, %192 : i32
          %194 = llvm.load %157 : !llvm.ptr -> i32
          %195 = arith.constant 48 : i32
          %196 = arith.subi %194, %195 : i32
          %197 = arith.addi %193, %196 : i32
          llvm.store %197, %151 : i32, !llvm.ptr
          cf.br ^bb32
        ^bb32:
        cf.br ^bb29
      ^bb28:
        %198 = llvm.load %157 : !llvm.ptr -> i32
        %199 = arith.constant 59 : i32
        %200 = arith.cmpi eq, %198, %199 : i32
        cf.cond_br %200, ^bb35, ^bb34
      ^bb35:
        %201 = arith.constant 0 : i1
        llvm.store %201, %148 : i1, !llvm.ptr
        %202 = arith.constant 1 : i1
        llvm.store %202, %154 : i1, !llvm.ptr
        %203 = arith.constant 0 : i32
        llvm.store %203, %151 : i32, !llvm.ptr
        cf.br ^bb29
      ^bb34:
        %204 = llvm.load %157 : !llvm.ptr -> i32
        %205 = arith.constant 10 : i32
        %206 = arith.cmpi eq, %204, %205 : i32
        %207 = scf.if %206 -> (i1) {
          %208 = arith.constant true
          scf.yield %208 : i1
        } else {
          %209 = llvm.load %157 : !llvm.ptr -> i32
          %210 = arith.constant 13 : i32
          %211 = arith.cmpi eq, %209, %210 : i32
          scf.yield %211 : i1
        }
        cf.cond_br %207, ^bb36, ^bb29
      ^bb36:
        %212 = llvm.load %145 : !llvm.ptr -> i32
        %213 = arith.cmpi eq, %212, %115 : i32
        cf.cond_br %213, ^bb37, ^bb38
        ^bb37:
          %214 = llvm.load %151 : !llvm.ptr -> i32
          %215 = llvm.load %142 : !llvm.ptr -> i32
          %216 = arith.extsi %215 : i32 to i64
          %217 = llvm.getelementptr %121[%216] : (!llvm.ptr, i64) -> !llvm.ptr, i32
          llvm.store %214, %217 : i32, !llvm.ptr
          %218 = llvm.load %142 : !llvm.ptr -> i32
          %219 = arith.constant 1 : i32
          %220 = arith.addi %218, %219 : i32
          llvm.store %220, %142 : i32, !llvm.ptr
          cf.br ^bb39
        ^bb38:
          cf.br ^bb39
        ^bb39:
        %221 = arith.constant 0 : i32
        llvm.store %221, %145 : i32, !llvm.ptr
        %222 = arith.constant 1 : i1
        llvm.store %222, %148 : i1, !llvm.ptr
        %223 = arith.constant 0 : i1
        llvm.store %223, %154 : i1, !llvm.ptr
        %224 = arith.constant 0 : i32
        llvm.store %224, %151 : i32, !llvm.ptr
        cf.br ^bb29
      ^bb29:
      %225 = func.call @fgetc(%106) : (!llvm.ptr) -> i32
      llvm.store %225, %157 : i32, !llvm.ptr
      cf.br ^bb24
    ^bb26:
    %226 = llvm.load %142 : !llvm.ptr -> i32
    %227 = arith.cmpi slt, %226, %114 : i32
    %228 = scf.if %227 -> (i1) {
      %229 = llvm.load %145 : !llvm.ptr -> i32
      %230 = arith.cmpi eq, %229, %115 : i32
      scf.yield %230 : i1
    } else {
      %231 = arith.constant false
      scf.yield %231 : i1
    }
    cf.cond_br %228, ^bb40, ^bb41
    ^bb40:
      %232 = llvm.load %151 : !llvm.ptr -> i32
      %233 = llvm.load %142 : !llvm.ptr -> i32
      %234 = arith.extsi %233 : i32 to i64
      %235 = llvm.getelementptr %121[%234] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      llvm.store %232, %235 : i32, !llvm.ptr
      %236 = llvm.load %142 : !llvm.ptr -> i32
      %237 = arith.constant 1 : i32
      %238 = arith.addi %236, %237 : i32
      llvm.store %238, %142 : i32, !llvm.ptr
      cf.br ^bb42
    ^bb41:
      cf.br ^bb42
    ^bb42:
    %239 = func.call @fclose(%106) : (!llvm.ptr) -> i32
    %240 = llvm.load %142 : !llvm.ptr -> i32
    %241 = arith.cmpi ne, %240, %114 : i32
    cf.cond_br %241, ^bb43, ^bb44
    ^bb43:
      %242 = llvm.mlir.addressof @str_3 : !llvm.ptr
      %243 = llvm.load %142 : !llvm.ptr -> i32
      %244 = llvm.call @printf(%242, %243) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i32) -> i32
      %245 = arith.constant 1 : i32
      func.return %245 : i32
    ^bb44:
      cf.br ^bb45
    ^bb45:
    %246 = arith.constant 0 : i32
    %247 = llvm.mlir.constant(1 : i64) : i64
    %248 = llvm.alloca %247 x i32 : (i64) -> !llvm.ptr
    llvm.store %246, %248 : i32, !llvm.ptr
    cf.br ^bb46
    ^bb46:
    %249 = llvm.load %248 : !llvm.ptr -> i32
    %250 = arith.constant 100 : i32
    %251 = arith.cmpi slt, %249, %250 : i32
    cf.cond_br %251, ^bb47, ^bb48
    ^bb47:
      %252 = llvm.load %248 : !llvm.ptr -> i32
      %253 = arith.extsi %252 : i32 to i64
      %254 = llvm.mlir.addressof @seed : !llvm.ptr
      llvm.store %253, %254 : i64, !llvm.ptr
      %255 = arith.constant 0 : i32
      %256 = llvm.mlir.constant(1 : i64) : i64
      %257 = llvm.alloca %256 x i32 : (i64) -> !llvm.ptr
      llvm.store %255, %257 : i32, !llvm.ptr
      cf.br ^bb49
      ^bb49:
      %258 = llvm.load %257 : !llvm.ptr -> i32
      %259 = arith.cmpi slt, %258, %115 : i32
      cf.cond_br %259, ^bb50, ^bb51
      ^bb50:
        %261 = arith.constant 10 : i32
        %260 = func.call @myrand(%261) : (i32) -> i32
        %262 = llvm.load %257 : !llvm.ptr -> i32
        %263 = arith.extsi %262 : i32 to i64
        %264 = llvm.getelementptr %125[%263] : (!llvm.ptr, i64) -> !llvm.ptr, i32
        llvm.store %260, %264 : i32, !llvm.ptr
        %265 = llvm.load %257 : !llvm.ptr -> i32
        %266 = arith.constant 1 : i32
        %267 = arith.addi %265, %266 : i32
        llvm.store %267, %257 : i32, !llvm.ptr
        cf.br ^bb49
      ^bb51:
      %268 = func.call @distance(%125, %116, %121, %114, %115) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i32, i32) -> i32
      %269 = llvm.mlir.constant(1 : i64) : i64
      %270 = llvm.alloca %269 x i32 : (i64) -> !llvm.ptr
      llvm.store %268, %270 : i32, !llvm.ptr
      %271 = llvm.load %270 : !llvm.ptr -> i32
      %272 = llvm.mlir.constant(1 : i64) : i64
      %273 = llvm.alloca %272 x i32 : (i64) -> !llvm.ptr
      llvm.store %271, %273 : i32, !llvm.ptr
      %274 = arith.constant 0 : i32
      %275 = llvm.mlir.constant(1 : i64) : i64
      %276 = llvm.alloca %275 x i32 : (i64) -> !llvm.ptr
      llvm.store %274, %276 : i32, !llvm.ptr
      %277 = arith.constant 0 : i32
      %278 = llvm.mlir.constant(1 : i64) : i64
      %279 = llvm.alloca %278 x i32 : (i64) -> !llvm.ptr
      llvm.store %277, %279 : i32, !llvm.ptr
      cf.br ^bb52
      ^bb52:
      %280 = llvm.load %270 : !llvm.ptr -> i32
      %281 = arith.constant 0 : i32
      %282 = arith.cmpi ne, %280, %281 : i32
      %283 = scf.if %282 -> (i1) {
        %284 = llvm.load %279 : !llvm.ptr -> i32
        %285 = arith.constant 100000 : i32
        %286 = arith.cmpi slt, %284, %285 : i32
        scf.yield %286 : i1
      } else {
        %287 = arith.constant false
        scf.yield %287 : i1
      }
      cf.cond_br %283, ^bb53, ^bb54
      ^bb53:
        %288 = arith.constant 0 : i32
        llvm.store %288, %257 : i32, !llvm.ptr
        cf.br ^bb55
        ^bb55:
        %289 = llvm.load %257 : !llvm.ptr -> i32
        %290 = arith.cmpi slt, %289, %115 : i32
        cf.cond_br %290, ^bb56, ^bb57
        ^bb56:
          %292 = llvm.load %257 : !llvm.ptr -> i32
          %293 = arith.extsi %292 : i32 to i64
          %294 = llvm.getelementptr %125[%293] : (!llvm.ptr, i64) -> !llvm.ptr, i32
          %291 = llvm.load %294 : !llvm.ptr -> i32
          %295 = func.call @shuffle_digit(%291) : (i32) -> i32
          %296 = llvm.load %257 : !llvm.ptr -> i32
          %297 = arith.extsi %296 : i32 to i64
          %298 = llvm.getelementptr %125[%297] : (!llvm.ptr, i64) -> !llvm.ptr, i32
          llvm.store %295, %298 : i32, !llvm.ptr
          %299 = func.call @distance(%125, %116, %121, %114, %115) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i32, i32) -> i32
          %300 = llvm.load %270 : !llvm.ptr -> i32
          %301 = arith.cmpi sle, %299, %300 : i32
          cf.cond_br %301, ^bb58, ^bb59
          ^bb58:
            llvm.store %299, %270 : i32, !llvm.ptr
            cf.br ^bb60
          ^bb59:
            %302 = llvm.load %257 : !llvm.ptr -> i32
            %303 = arith.extsi %302 : i32 to i64
            %304 = llvm.getelementptr %125[%303] : (!llvm.ptr, i64) -> !llvm.ptr, i32
            llvm.store %291, %304 : i32, !llvm.ptr
            cf.br ^bb60
          ^bb60:
          %305 = llvm.load %257 : !llvm.ptr -> i32
          %306 = arith.constant 1 : i32
          %307 = arith.addi %305, %306 : i32
          llvm.store %307, %257 : i32, !llvm.ptr
          cf.br ^bb55
        ^bb57:
        %308 = llvm.load %270 : !llvm.ptr -> i32
        %309 = llvm.load %273 : !llvm.ptr -> i32
        %310 = arith.cmpi eq, %308, %309 : i32
        cf.cond_br %310, ^bb61, ^bb62
        ^bb61:
          %311 = llvm.load %276 : !llvm.ptr -> i32
          %312 = arith.constant 1 : i32
          %313 = arith.addi %311, %312 : i32
          llvm.store %313, %276 : i32, !llvm.ptr
          %314 = llvm.load %276 : !llvm.ptr -> i32
          %315 = arith.constant 20 : i32
          %316 = arith.cmpi eq, %314, %315 : i32
          cf.cond_br %316, ^bb64, ^bb65
          ^bb64:
            %317 = func.call @myrand(%115) : (i32) -> i32
            %320 = arith.extsi %317 : i32 to i64
            %321 = llvm.getelementptr %125[%320] : (!llvm.ptr, i64) -> !llvm.ptr, i32
            %319 = llvm.load %321 : !llvm.ptr -> i32
            %318 = func.call @shuffle_digit(%319) : (i32) -> i32
            %322 = arith.extsi %317 : i32 to i64
            %323 = llvm.getelementptr %125[%322] : (!llvm.ptr, i64) -> !llvm.ptr, i32
            llvm.store %318, %323 : i32, !llvm.ptr
            %324 = func.call @distance(%125, %116, %121, %114, %115) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i32, i32) -> i32
            llvm.store %324, %270 : i32, !llvm.ptr
            %325 = arith.constant 0 : i32
            llvm.store %325, %276 : i32, !llvm.ptr
            cf.br ^bb66
          ^bb65:
            cf.br ^bb66
          ^bb66:
          cf.br ^bb63
        ^bb62:
          %326 = arith.constant 0 : i32
          llvm.store %326, %276 : i32, !llvm.ptr
          %327 = llvm.load %270 : !llvm.ptr -> i32
          llvm.store %327, %273 : i32, !llvm.ptr
          cf.br ^bb63
        ^bb63:
        %328 = llvm.load %279 : !llvm.ptr -> i32
        %329 = arith.constant 1 : i32
        %330 = arith.addi %328, %329 : i32
        llvm.store %330, %279 : i32, !llvm.ptr
        cf.br ^bb52
      ^bb54:
      %331 = llvm.load %270 : !llvm.ptr -> i32
      %332 = arith.constant 0 : i32
      %333 = arith.cmpi eq, %331, %332 : i32
      cf.cond_br %333, ^bb67, ^bb68
      ^bb67:
        cf.br ^bb48
      ^bb68:
        cf.br ^bb69
      ^bb69:
      %334 = llvm.load %248 : !llvm.ptr -> i32
      %335 = arith.constant 1 : i32
      %336 = arith.addi %334, %335 : i32
      llvm.store %336, %248 : i32, !llvm.ptr
      cf.br ^bb46
    ^bb48:
    %337 = arith.constant 0 : i32
    %338 = arith.extsi %337 : i32 to i64
    %339 = llvm.mlir.constant(1 : i64) : i64
    %340 = llvm.alloca %339 x i64 : (i64) -> !llvm.ptr
    llvm.store %338, %340 : i64, !llvm.ptr
    %341 = arith.constant 0 : i32
    %342 = llvm.mlir.constant(1 : i64) : i64
    %343 = llvm.alloca %342 x i32 : (i64) -> !llvm.ptr
    llvm.store %341, %343 : i32, !llvm.ptr
    cf.br ^bb70
    ^bb70:
    %344 = llvm.load %343 : !llvm.ptr -> i32
    %345 = arith.cmpi slt, %344, %115 : i32
    cf.cond_br %345, ^bb71, ^bb72
    ^bb71:
      %346 = llvm.load %340 : !llvm.ptr -> i64
      %347 = arith.constant 10 : i32
      %349 = arith.extsi %347 : i32 to i64
      %348 = arith.muli %346, %349 : i64
      %351 = llvm.load %343 : !llvm.ptr -> i32
      %352 = arith.extsi %351 : i32 to i64
      %353 = llvm.getelementptr %125[%352] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      %350 = llvm.load %353 : !llvm.ptr -> i32
      %354 = arith.extsi %350 : i32 to i64
      %355 = arith.addi %348, %354 : i64
      llvm.store %355, %340 : i64, !llvm.ptr
      %356 = llvm.load %343 : !llvm.ptr -> i32
      %357 = arith.constant 1 : i32
      %358 = arith.addi %356, %357 : i32
      llvm.store %358, %343 : i32, !llvm.ptr
      cf.br ^bb70
    ^bb72:
    %359 = llvm.mlir.addressof @str_4 : !llvm.ptr
    %360 = llvm.load %340 : !llvm.ptr -> i64
    %361 = llvm.call @printf(%359, %360) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
    func.call @free(%116) : (!llvm.ptr) -> ()
    func.call @free(%121) : (!llvm.ptr) -> ()
    func.call @free(%125) : (!llvm.ptr) -> ()
    %365 = arith.constant 0 : i32
    func.return %365 : i32
  }
}