# Question
Title: Write the most optimized assembly program to detect a prime number (from a bigger range!)
This is the second version of the task. The original task had a defect that the given range of integers was too small. This was pointed out by @harold that other methods couldn't defeat the way of hard-coding all the possible prime divisors. Now you have a larger range of integers to test from `0` to `2000000`. Also, the result of your program must be sane for all possible input.

Multiplication now stores the overflowed bits in the `r0` register. You can name labels with minimum restriction, and the added `dbg` instruction dumps the value of all registers.

---

Write a program in assembly that will find out whether the input is a prime number. The program will run through **mjvm** which has a simple set of instructions and a determined number of clock cycles for each instruction. The input will be from `0` to `2000000` inclusive, and the objective is to write the most optimized program spending the least number of clock cycles to determine the primality of all inputs.

This is an example program doing a primality test in mjvm assembly.

```
.     ind  r1 .    ; r1 = input ; originally meant input as decimal
.     lti  r1 2    ; r0 = r1 < 2 ; test less than immediate
.     cjmp false . ; if (r0) goto false
.     eqi  r1 2    ; r0 = r1 == 2
.     cjmp true .  ; if (r0) goto true
.     mv   r2 r1   ; r2 = r1
.     andi r2 1    ; r2 &= 1
.     eqi  r2 0    ; r0 = r2 == 0
.     cjmp false . ; if (r0) goto false
.     mvi  r3 3    ; r3 = 3
loop  mv   r2 r3   ; r2 = r3
.     mul  r2 r2   ; r2 *= r2
.     gt   r2 r1   ; r0 = r2 > r1
.     cjmp true .  ; if (r0) goto true
.     mv   r2 r1   ; r2 = r1
.     div  r2 r3   ; r2 /= r3, r0 = r2 % r3
.     lnot r0 .    ; r0 = !r0 ; logical not
.     cjmp false . ; if (r0) goto false
.     addi r3 2    ; r3 += 2
.     jmp  loop .  ; goto loop
true  mvi  r1 0xffffffff ; r1 = -1
.     outd r1 .    ; print r1 as decimal
.     end  .  .    ; end program
false mvi  r1 0
.     outd r1 .
.     end  .  .

```

For input from `0` to `2000000`, this program consumes total `4043390047` cycles. While some obvious optimizations have been done, there is still a lot of room for improvement.

Now if you're interested, this is the whole list of instructions. Each instruction takes a fixed number of arguments, which can either be a register, an immediate (constant), or a label (address). The type of the argument is also fixed; `r` means register, `i` means immediate, and `L` means label. An instruction with an `i` suffix takes an immediate as the third argument while the same instruction without an `i` takes a register as the third argument. Also, I'll explain later, but `r0` is a special register.

```
end - end program
dbg - dumps the value of all registers and pause the program
ind  r - read the input in decimal digits and store the value in `r`
outd r - output the value in `r` as decimal digits
not  r - bitwise not; set `r` to `~r` (all bits reversed)
lnot r - logical not; if `r` is 0, set `r` to ~0 (all bits on); otherwise, set `r` to 0
jmp  L - jump to `L`
cjmp L - if `r0` is non-zero, jump to L

mv(i)  r1 r2(i) - copy `r2(i)` to `r1`
cmv(i) r1 r2(i) - if `r0` is non-zero, copy `r2(i)` to `r1`

eq(i)  r1 r2(i) - if `r1` equals `r2(i)`, set `r0` to ~0; otherwise set `r0` to 0

neq(i), lt(i), le(i), gt(i), ge(i) - analogus to eq(i)

and(i) r1 r2(i) - set `r1` to `r1 & r2(i)`; bitwise `and`

or(i), xor(i) - analogus to and(i)

shl(i), shr(i) - shift left and shift right; analogus to and(i);

add(i), sub(i) - analogus to and(i)

mul(i) r1 r2(i) - from the result of `r1 * r2(i)`, the high bits are stored in `r0`
                  and the low bits are stored in `r1`;
                  if the first argument is `r0`, the low bits are stored in `r0`;
                  the high bits are 0 when there is no overflow

div(i) r1 r2(i) - set `r0` to `r1 % r2(i)` and set `r1` to `r1 / r2(i)`;
                  if the first argument is `r0`, `r0` is `r1 / r2(i)`

```

As you can see, the result of comparison instructions and the remainder part of division is stored in `r0`. The value is also used to perform a conditional jump or move.

These instructions consume 2 clock cycles.

```
cjmp, cmv(i), mul(i)

```

These instructions consume 32 clock cycles.

```
div(i)

```

These instructions consume 10 clock cycles.

```
ind, outd

```

`dbg` does not consume any clock cycle.

All other instructions, including `end` consume 1 clock cycle.

When the program starts, a cycle is consumed per each instruction of the whole program. That means, for example, if your program has 15 instructions in total, initially 15 cycles will be counted.

There are 16 registers from `r0` to `rf` each holding a 32-bit *unsigned* integer. The number after `r` is hexadecimal. The initial value of all registers is 0. There is no memory other than the registers.

The result of an operation after an overflow is guaranteed to be `result % pow(2, 32)`. This also applies to an immediate value outside the range of unsigned 32-bits. Division by zero is undefined, but most likely you'll get a hardware interrupt.

Labels can be any sequence of characters except whitespaces and `.`. The maximum length of each label is 15 characters, and there can be total 256 labels in a single program.

An immediate operand can be hexadecimal starting with `0x` or `0X`, or octal starting with `0`.

You start the program by reading an input with `ind`. The input will be automatically given by the VM. You end the program by a sequence of `outd` and `end`. The VM will determine whether your final output is correct.

If the input is not prime, the output shall be `0`. If the input is prime, the output shall be `~0`. 0 and 1 are not prime numbers. All the comparison instructions result as `~0` for a `true` value, and you can often use this for efficient bitwise logic.

In the assembly code file, each line should start with 4 instructions divided by one or more whitespaces, and `.` is used as a placeholder. Everything else in the line is ignored and thus can be used as comments.

The current implementation of the VM may have bugs, you can report any faulty code in the comments. An alternative implementation is also welcomed. I will post here if there is any.

This is the code of the VM to measure your program's correctness and efficiency. You can compile with any C compiler, and the program will interpret your assembly file given as the first argument.

```
#include <stdint.h>
#include <stdarg.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>

static uint32_t prime(uint32_t n) {
    if (n < 2) return 0;
    if (n == 2) return -1;
    if (!(n % 2)) return 0;
    for (int d = 3; d * d <= n; d += 2) {
        if (!(n % d)) return 0;
    }
    return -1;
}

enum {
    NOP, DBG, END,
    IND, OUTD,
    NOT, LNOT,
    JMP, CJMP,
    MV, CMV,
    EQ, NEQ, LT, LE, GT, GE,
    AND, OR, XOR, SHL, SHR,
    ADD, SUB, MUL, DIV,
    MVI, CMVI,
    EQI, NEQI, LTI, LEI, GTI, GEI,
    ANDI, ORI, XORI, SHLI, SHRI,
    ADDI, SUBI, MULI, DIVI,
};

_Noreturn static void verr_(const char *m, va_list a) {
    vprintf(m, a);
    putchar('\n');
    exit(1);
}

_Noreturn static void err(const char *m, ...) {
    va_list a;
    va_start(a, m);
    verr_(m, a);
}

static void chk(int ok, const char *m, ...) {
    if (!ok) {
        va_list a;
        va_start(a, m);
        verr_(m, a);
    }
}

#define LBL_DIC_CAP 0x100

typedef struct {
    struct {
        char id[0x10];
        int i;
    } _[LBL_DIC_CAP];
    int n;
} lblDic_t;

static void lblDic_init(lblDic_t *_) {
    _->n = 0;
}

static void lblDic_add(lblDic_t *_, const char *id, int i) {
    chk(_->n < LBL_DIC_CAP, "too many labels");
    strcpy(_->_[_->n].id, id);
    _->_[_->n++].i = i;
}

static int cmp_(const void *a, const void *b) {
    return strcmp(a, b);
}

static void lblDic_sort(lblDic_t *_) {
    qsort(_, _->n, sizeof(*_->_), cmp_);
}

static int lblDic_search(lblDic_t *_, const char *id) {
    int o = &_->_->i - (int *)_;
    int *p = bsearch(id, _, _->n, sizeof(*_->_), cmp_);
    if (!p) return -1;
    return p[o];
}

static int ins(const char *s) {
    if (!strcmp(s, "dbg")) return DBG;
    if (!strcmp(s, "end")) return END;
    if (!strcmp(s, "ind")) return IND;
    if (!strcmp(s, "outd")) return OUTD;
    if (!strcmp(s, "not")) return NOT;
    if (!strcmp(s, "lnot")) return LNOT;
    if (!strcmp(s, "jmp")) return JMP;
    if (!strcmp(s, "cjmp")) return CJMP;
    if (!strcmp(s, "mv")) return MV;
    if (!strcmp(s, "cmv")) return CMV;
    if (!strcmp(s, "eq")) return EQ;
    if (!strcmp(s, "neq")) return NEQ;
    if (!strcmp(s, "lt")) return LT;
    if (!strcmp(s, "le")) return LE;
    if (!strcmp(s, "gt")) return GT;
    if (!strcmp(s, "ge")) return GE;
    if (!strcmp(s, "and")) return AND;
    if (!strcmp(s, "or")) return OR;
    if (!strcmp(s, "xor")) return XOR;
    if (!strcmp(s, "shl")) return SHL;
    if (!strcmp(s, "shr")) return SHR;
    if (!strcmp(s, "add")) return ADD;
    if (!strcmp(s, "sub")) return SUB;
    if (!strcmp(s, "mul")) return MUL;
    if (!strcmp(s, "div")) return DIV;
    if (!strcmp(s, "mvi")) return MVI;
    if (!strcmp(s, "cmvi")) return CMVI;
    if (!strcmp(s, "eqi")) return EQI;
    if (!strcmp(s, "neqi")) return NEQI;
    if (!strcmp(s, "lti")) return LTI;
    if (!strcmp(s, "lei")) return LEI;
    if (!strcmp(s, "gti")) return GTI;
    if (!strcmp(s, "gei")) return GEI;
    if (!strcmp(s, "andi")) return ANDI;
    if (!strcmp(s, "ori")) return ORI;
    if (!strcmp(s, "xori")) return XORI;
    if (!strcmp(s, "shli")) return SHLI;
    if (!strcmp(s, "shri")) return SHRI;
    if (!strcmp(s, "addi")) return ADDI;
    if (!strcmp(s, "subi")) return SUBI;
    if (!strcmp(s, "muli")) return MULI;
    if (!strcmp(s, "divi")) return DIVI;
    err("invalid instruction: %s", s);
}

static int reg(const char *s) {
    chk(*s == 'r', "invalid register: %s", s);
    if ('0' <= s[1] && s[1] <= '9') return s[1] - '0';
    if ('a' <= s[1] && s[1] <= 'f') return s[1] - 'a' + 10;
    err("invalid register: %s", s);
}

int main(int argc, char **argv) {
    chk(argc == 2, "must have 1 argument");
    int sz;
    uint32_t p[0x10000][3];
    uint32_t r[0x10];
    lblDic_t l;
    lblDic_init(&l);
    FILE *f = fopen(argv[1], "r");
    chk((int)f, "failed to open file: %s", argv[1]);
    for (int i = 0;; ++i) {
        char s[0x100];
        int m = fscanf(f, "%s", s);
        if (m < 0) break;
        chk(strlen(s) < 0x10, "%s is too long", s);
        if (*s != '.') {
            if (lblDic_search(&l, s) < 0) {
                lblDic_add(&l, s, i);
                lblDic_sort(&l);
            }
        }
        int c;
        while ((c = getc(f)) != '\n' && m > 0);
    }
    rewind(f);
    char s[4][0x10];
    for (int i = 0;; ++i) {
        int m = fscanf(f, "%s %s %s %s", *s, s[1], s[2], s[3]);
        if (m < 0) {
            sz = i;
            break;
        }
        chk(m == 4, "parse error at line %d", i + 1);
        *p[i] = ins(s[1]);
        if (*p[i] <= END) {
            p[i][1] = NOP;
        } else if (*p[i] == JMP || *p[i] == CJMP) {
            p[i][1] = lblDic_search(&l, s[2]);
            chk(p[i][1] != -1u, "unknown label: %s", s[2]);
        } else {
            p[i][1] = reg(s[2]);
        }
        if (*p[i] <= CJMP) {
            p[i][2] = NOP;
        } else if (*p[i] >= MVI) {
            p[i][2] = strtoul(s[3], NULL, 0);
        } else {
            p[i][2] = reg(s[3]);
        }
        while ((m = getc(f)) != '\n' && m > 0);
    }
    chk(!fclose(f), "sth's very twisted with your system");
    for (int i = 0; i < l.n; ++i) {
        printf("%16s%6d\n", l._[i].id, l._[i].i);
    }
    for (int i = 0; i < sz; ++i) {
        printf("%6d%4u%4u  %u\n", i, *p[i], p[i][1], p[i][2]);
    }
    long long c = 0;
    for (int n = 0; n <= 2000000; ++n) {
        memset(r, 0, sizeof(r));
        uint32_t o = 1;
        c += sz;
        for (uint32_t *i = *p; i < p[sz]; i += 3) {
        start:
            switch(*i) {
                case DBG: {
                    for (int i = 0; i < 010; ++i) {
                        printf("r%x%11u  r%x%11u\n", i, r[i], i + 010, r[i + 010]);
                    }
                    fputs("press ENTER to continue", stdout);
                    getchar();
                    break;
                }
                case END: ++c; goto end;
                case IND: c += 10; r[i[1]] = n; break;
                case OUTD: c += 10; o = r[i[1]]; break;
                case NOT: ++c; r[i[1]] = ~r[i[1]]; break;
                case LNOT: ++c; r[i[1]] = r[i[1]] ? 0 : -1; break;
                case JMP: ++c; i = p[i[1]]; goto start;
                case CJMP: c += 2; if (*r) {i = p[i[1]]; goto start;} break;
                case MV: ++c; r[i[1]] = r[i[2]]; break;
                case CMV: c += 2; if (*r) r[i[1]] = r[i[2]]; break;
                case EQ: ++c; *r = r[i[1]] == r[i[2]] ? -1 : 0; break;
                case NEQ: ++c; *r = r[i[1]] != r[i[2]] ? -1 : 0; break;
                case LT: ++c; *r = r[i[1]] < r[i[2]] ? -1 : 0; break;
                case LE: ++c; *r = r[i[1]] <= r[i[2]] ? -1 : 0; break;
                case GT: ++c; *r = r[i[1]] > r[i[2]] ? -1 : 0; break;
                case GE: ++c; *r = r[i[1]] >= r[i[2]] ? -1 : 0; break;
                case AND: ++c; r[i[1]] &= r[i[2]]; break;
                case OR: ++c; r[i[1]] |= r[i[2]]; break;
                case XOR: ++c; r[i[1]] ^= r[i[2]]; break;
                case SHL: ++c; r[i[1]] <<= r[i[2]]; break;
                case SHR: ++c; r[i[1]] >>= r[i[2]]; break;
                case ADD: ++c; r[i[1]] += r[i[2]]; break;
                case SUB: ++c; r[i[1]] -= r[i[2]]; break;
                case MUL: {
                    c += 2;
                    uint64_t p = (uint64_t)r[i[1]] * r[i[2]];
                    *r = p >> 0x20;
                    r[i[1]] = p;
                    break;
                }
                case DIV: {
                    c += 32;
                    uint32_t rm = r[i[1]] % r[i[2]];
                    uint32_t q = r[i[1]] / r[i[2]];
                    *r = rm;
                    r[i[1]] = q;
                    break;
                }
                case MVI: ++c; r[i[1]] = i[2]; break;
                case CMVI: c += 2; if (*r) r[i[1]] = i[2]; break;
                case EQI: ++c; *r = r[i[1]] == i[2] ? -1 : 0; break;
                case NEQI: ++c; *r = r[i[1]] != i[2] ? -1 : 0; break;
                case LTI: ++c; *r = r[i[1]] < i[2] ? -1 : 0; break;
                case LEI: ++c; *r = r[i[1]] <= i[2] ? -1 : 0; break;
                case GTI: ++c; *r = r[i[1]] > i[2] ? -1 : 0; break;
                case GEI: ++c; *r = r[i[1]] >= i[2] ? -1 : 0; break;
                case ANDI: ++c; r[i[1]] &= i[2]; break;
                case ORI: ++c; r[i[1]] |= i[2]; break;
                case XORI: ++c; r[i[1]] ^= i[2]; break;
                case SHLI: ++c; r[i[1]] <<= i[2]; break;
                case SHRI: ++c; r[i[1]] >>= i[2]; break;
                case ADDI: ++c; r[i[1]] += i[2]; break;
                case SUBI: ++c; r[i[1]] -= i[2]; break;
                case MULI: {
                    c += 2;
                    uint64_t p = (uint64_t)r[i[1]] * i[2];
                    *r = p >> 0x20;
                    r[i[1]] = p;
                    break;
                }
                case DIVI: {
                    c += 32;
                    uint32_t rm = r[i[1]] % i[2];
                    uint32_t q = r[i[1]] / i[2];
                    *r = rm;
                    r[i[1]] = q;
                    break;
                }
            }
        }
    end:
        chk(o == prime(n), "wrong result for %d", n);
    }
    printf("total cycles: %lld\n", c);
    return 0;
}

```

# Answer
> 5 votes
Stuff at the bottom is for the earlier version of the question.

Here's a simple technique to optimize the basic trial division from the example code, at 2736719982 cycles. It hopefully won't be the fastest (it's a bit boring), but at least it's a new target to beat. Techniques used were:

* Rewritten loop logic to have the branch at the bottom, and no jmp.
* Change the trial division base from { 2 } to { 2, 3 }. There are an explicit div-by-3 test, and a special case for small numbers, before the loop to enable that. The alternating increment pattern of 2, 4, 2, 4 .. is achieved with `xori r6 6` which changes a 2 to a 4, and a 4 to a 2. The base { 2, 3, 5 } with its increment pattern of `[4, 2, 4, 2, 4, 6, 2, 6]` by contrast wouldn't be anywhere near that nice to implement.
* Reuse an `outd/end` pair by using a `jmp`, saving code-size that way was worth over a million cycles.
* > Also, the result of your program must be sane for all possible input.

I did not verify this, so maybe I cheated, who knows. Actually I tried to test more inputs, but that was too slow and I gave up.

Code:

```
. ind  r1 .
. lti  r1 2
. cjmp F .
. eqi  r1 2
. cjmp T .
. mv   r2 r1
. andi r2 1
. eqi  r2 0
. cjmp F .
. lei  r1 8
. cjmp T .
. mv   r2 r1
. muli r2 -1431655765
. lei  r2 1431655765
. cjmp F .
. mvi  r3 5
. mvi  r6 4
L mv   r2 r1
. div  r2 r3
. lnot r0 .
. cjmp F .
. xori r6 6
. add  r3 r6
. mv   r2 r3
. mul  r2 r2
. le   r2 r1
. cjmp L .
T mvi  r1 -1
. jmp X .
F mvi  r1 0
X outd r1 .
. end  . .

```

---

For previous version of the question:

I have tried a couple of approaches. So far, the one that is winning is a relatively boring one.. namely an unrolled trial division, at ~~886783~~ 795197 (using Anders Kaseorg's suggestion) cycles:

```
. ind  r2 .
. eqi  r2 2
. cjmp T .
. mv   r0 r2
. andi r0 1
. lnot r0 .
. cjmp F .
. lei  r2 68
. cjmp A .
. mv   r1 r2
. muli r2 -1431655765
. lei  r2 1431655765
. cjmp F .
. muli r2 1717986919
. lei  r2 858993459
. cjmp F .
. muli r2 -1840700269
. lei  r2 613566756
. cjmp F .
. muli r2 390451573
. lei  r2 390451572
. cjmp F .
. muli r2 1982292599
. lei  r2 330382099
. cjmp F .
. muli r2 1010580541
. lei  r2 252645135
. cjmp F .
. muli r2 -1356305461
. lei  r2 226050910
. cjmp F .
. muli r2 1493901669
. lei  r2 186737708
. cjmp F .
. muli r2 592409283
. lei  r2 148102320
. cjmp F .
. muli r2 -2078209981
. lei  r2 138547332
. cjmp F .
. muli r2 -1741202957
. lei  r2 116080197
. cjmp F .
. muli r2 -104755299
. lei  r2 104755299
. cjmp F .
. muli r2 -1598127365
. lei  r2 99882960
. cjmp F .
. muli r2 1644881093
. lei  r2 91382282
. cjmp F .
. muli r2 -1215556781
. lei  r2 81037118
. cjmp F .
. muli r2 1019144783
. lei  r2 72796055
. cjmp F .
. muli r2 2112278999
. lei  r2 70409299
. cjmp F .
. lti  r1 4489
. cjmp T .
. muli r2 -769247873
. lei  r2 64103989
. cjmp F .
. lti  r1 5041
. cjmp T .
. muli r2 1935759909
. lei  r2 60492497
. cjmp F .
. lti  r1 5329
. cjmp T .
. muli r2 1882725391
. lei  r2 58835168
. cjmp F .
. lti  r1 6241
. cjmp T .
. muli r2 -1196066841
. lei  r2 54366674
. cjmp F .
. lti  r1 6889
. cjmp T .
. muli r2 1397158037
. lei  r2 51746593
. cjmp F .
. lti  r1 7921
. cjmp T .
. muli r2 579096715
. lei  r2 48258059
. cjmp F .
. lti  r1 9409
. cjmp T .
. muli r2 132834041
. lei  r2 44278013
. cjmp F .
T mvi  r1 -1
. outd r1 .
. end  . .
F mvi  r1 0
. outd r1 .
. end  . .
A mvi  r1 1689570158
. shri r2 1
. shr  r1 r2
. andi r1 1
. mvi  r0 0
. sub  r0 r1
. outd r0 .
. end  . .

```

First I test whether the input is 2 (output True), then whether it is even (output False), then there is a small bitmap of odd primes, and then there is a bunch of divisibility tests by primes from 3 up through 97, which is enough to cover everything up to 10000.

The divisibility tests are basically of the form `if (n * mulinv(d) <= 0xFFFFFFFF / d) output False` where `mulinv` is the multiplicative inverse modulo 232, except that instead of using the actual `n` each time, the result of the multiplication is carried forward and that multiplication is implicitly "undone" by multiplying by `d1 * mulinv(d2)` where `d1` is the previous divisor and `d2` is the current one. Some of them have an extra test first to see if the input is smaller than the square of the divisor, and then output True.

Oddly it seems that the main effect of the small "bitmap of primes"-test for small numbers is that it gets rid of some of those extra "input is smaller than square of divisor"-tests, which is not why I added it, but so be it.

I also tried a deterministic Miller Rabin test with bases 2 and 3, which I was very hopeful for, but it was actually quite bad: over 3 million cycles initially, then I added some of those divisibility tests from above so the main MR-test would run less often, but it turned out that the best thing to do was to add *all* of them .. and then remove the actual MR-test.

# Answer
> 2 votes
**hard-coded divisibility test to its extreme - 2156770452 cycles**

During an attempt to optimize @harold's solution, I discovered that every time I add an hard-coded divisibility test, the number of cycles decrease. The reason is actually quite simple. A `div` instruction consumes 32 cycles, but a hard-coded divisibility test can be achieved by a sequence of `mv -> muli -> lei -> cjmp`, which is total 6 cycles plus 3 cycles for the increased code size. `div` can only be optimized out when the value of the operand is specified.

The result is a program with **917** instructions, and the few instructions at the end are just there to produce correct output outside the given range of the task. Of course I did not write this by hand, I generated it with a Python script.

---

Out of curiosity, I wanted to check if the hard-coded division method scales well at least to the range of 32-bit unsigned integers. I found this paper that describes an efficient algorithm (FJ32\_256) doing a primality test in the range of 32-bit unsigned integers. I decided to use this algorithm for comparison, then generated a C program (pastebin) with the same Python script tuned to generate C instead of mjvm assembly (pastebin), for a larger range of possible input from \\$0\\$ to \\$2^{32}\\$

The test was done through these 5 ranges

```
[0, 20000000)
[100000000, 120000000)
[200000000, 220000000)
[300000000, 320000000)
[400000000, 420000000)

```

This is the result where the numbers are the counted (real) clock cycles from my 2.4GHz CPU.

```
range 0 - hard-coded 1966207882
range 0 - FJ32_256   1896766512

range 1 - hard-coded 1877253992
range 1 - FJ32_256   2118426310

range 2 - hard-coded 1874180510
range 2 - FJ32_256   2196823877

range 3 - hard-coded 5235061704
range 3 - FJ32_256   2244187362

range 4 - hard-coded 5173315658
range 4 - FJ32_256   2266020651

```

From this non-rigorous test, we can see that hard-coded divisibility test actually performs well up to 220 million, and then the performance drops due to the increased number of divisibility tests for larger numbers. `FJ32_256` on the other hand has a very stable performance throughout the whole range.

---

This is the actual generated assembly code.

```
. ind r1 .
. lti r1 2
. cjmp F .
. eqi r1 2
. cjmp T .
. mv r0 r1
. andi r0 1
. lnot r0 .
. cjmp F .
. lti r1 9
. cjmp T .
. mv r2 r1
. muli r2 0xaaaaaaab
. lei r2 0x55555555
. cjmp F .
. mv r2 r1
. muli r2 0xcccccccd
. lei r2 0x33333333
. cjmp F .
. mv r2 r1
. muli r2 0xb6db6db7
. lei r2 0x24924924
. cjmp F .
. lti r1 121
. cjmp T .
. mv r2 r1
. muli r2 0xba2e8ba3
. lei r2 0x1745d174
. cjmp F .
. mv r2 r1
. muli r2 0xc4ec4ec5
. lei r2 0x13b13b13
. cjmp F .
. mv r2 r1
. muli r2 0xf0f0f0f1
. lei r2 0xf0f0f0f
. cjmp F .
. mv r2 r1
. muli r2 0x286bca1b
. lei r2 0xd79435e
. cjmp F .
. mv r2 r1
. muli r2 0xe9bd37a7
. lei r2 0xb21642c
. cjmp F .
. mv r2 r1
. muli r2 0x4f72c235
. lei r2 0x8d3dcb0
. cjmp F .
. mv r2 r1
. muli r2 0xbdef7bdf
. lei r2 0x8421084
. cjmp F .
. mv r2 r1
. muli r2 0x914c1bad
. lei r2 0x6eb3e45
. cjmp F .
. mv r2 r1
. muli r2 0xc18f9c19
. lei r2 0x63e7063
. cjmp F .
. mv r2 r1
. muli r2 0x2fa0be83
. lei r2 0x5f417d0
. cjmp F .
. mv r2 r1
. muli r2 0x677d46cf
. lei r2 0x572620a
. cjmp F .
. mv r2 r1
. muli r2 0x8c13521d
. lei r2 0x4d4873e
. cjmp F .
. mv r2 r1
. muli r2 0xa08ad8f3
. lei r2 0x456c797
. cjmp F .
. mv r2 r1
. muli r2 0xc10c9715
. lei r2 0x4325c53
. cjmp F .
. mv r2 r1
. muli r2 0x7a44c6b
. lei r2 0x3d22635
. cjmp F .
. mv r2 r1
. muli r2 0xe327a977
. lei r2 0x39b0ad1
. cjmp F .
. mv r2 r1
. muli r2 0xc7e3f1f9
. lei r2 0x381c0e0
. cjmp F .
. mv r2 r1
. muli r2 0x613716af
. lei r2 0x33d91d2
. cjmp F .
. mv r2 r1
. muli r2 0x2b2e43db
. lei r2 0x3159721
. cjmp F .
. mv r2 r1
. muli r2 0xfa3f47e9
. lei r2 0x2e05c0b
. cjmp F .
. mv r2 r1
. muli r2 0x5f02a3a1
. lei r2 0x2a3a0fd
. cjmp F .
. mv r2 r1
. muli r2 0x7c32b16d
. lei r2 0x288df0c
. cjmp F .
. mv r2 r1
. muli r2 0xd3431b57
. lei r2 0x27c4597
. cjmp F .
. mv r2 r1
. muli r2 0x8d28ac43
. lei r2 0x2647c69
. cjmp F .
. mv r2 r1
. muli r2 0xda6c0965
. lei r2 0x2593f69
. cjmp F .
. mv r2 r1
. muli r2 0xfdbc091
. lei r2 0x243f6f0
. cjmp F .
. lti r1 16129
. cjmp T .
. mv r2 r1
. muli r2 0xefdfbf7f
. lei r2 0x2040810
. cjmp F .
. mv r2 r1
. muli r2 0xc9484e2b
. lei r2 0x1f44659
. cjmp F .
. mv r2 r1
. muli r2 0x77975b9
. lei r2 0x1de5d6e
. cjmp F .
. mv r2 r1
. muli r2 0x70586723
. lei r2 0x1d77b65
. cjmp F .
. mv r2 r1
. muli r2 0x8ce2cabd
. lei r2 0x1b7d6c3
. cjmp F .
. mv r2 r1
. muli r2 0xbf937f27
. lei r2 0x1b20364
. cjmp F .
. mv r2 r1
. muli r2 0x2c0685b5
. lei r2 0x1a16d3f
. cjmp F .
. mv r2 r1
. muli r2 0x451ab30b
. lei r2 0x1920fb4
. cjmp F .
. mv r2 r1
. muli r2 0xdb35a717
. lei r2 0x1886e5f
. cjmp F .
. mv r2 r1
. muli r2 0xd516325
. lei r2 0x17ad220
. cjmp F .
. mv r2 r1
. muli r2 0xd962ae7b
. lei r2 0x16e1f76
. cjmp F .
. mv r2 r1
. muli r2 0x10f8ed9d
. lei r2 0x16a13cd
. cjmp F .
. mv r2 r1
. muli r2 0xee936f3f
. lei r2 0x1571ed3
. cjmp F .
. mv r2 r1
. muli r2 0x90948f41
. lei r2 0x1539094
. cjmp F .
. mv r2 r1
. muli r2 0x3d137e0d
. lei r2 0x14cab88
. cjmp F .
. mv r2 r1
. muli r2 0xef46c0f7
. lei r2 0x149539e
. cjmp F .
. mv r2 r1
. muli r2 0x6e68575b
. lei r2 0x13698df
. cjmp F .
. mv r2 r1
. muli r2 0xdb43bb1f
. lei r2 0x125e227
. cjmp F .
. mv r2 r1
. muli r2 0x9ba144cb
. lei r2 0x120b470
. cjmp F .
. mv r2 r1
. muli r2 0x478bbced
. lei r2 0x11e2ef3
. cjmp F .
. mv r2 r1
. muli r2 0x1fdcd759
. lei r2 0x1194538
. cjmp F .
. mv r2 r1
. muli r2 0x437b2e0f
. lei r2 0x112358e
. cjmp F .
. mv r2 r1
. muli r2 0x10fef011
. lei r2 0x10fef01
. cjmp F .
. mv r2 r1
. muli r2 0x9a020a33
. lei r2 0x105197f
. cjmp F .
. mv r2 r1
. muli r2 0xff00ff01
. lei r2 0xff00ff
. cjmp F .
. mv r2 r1
. muli r2 0x70e99cb7
. lei r2 0xf92fb2
. cjmp F .
. mv r2 r1
. muli r2 0x6205b5c5
. lei r2 0xf3a0d5
. cjmp F .
. mv r2 r1
. muli r2 0xa27acdef
. lei r2 0xf1d48b
. cjmp F .
. mv r2 r1
. muli r2 0x25e4463d
. lei r2 0xec9791
. cjmp F .
. mv r2 r1
. muli r2 0x749cb29
. lei r2 0xe93965
. cjmp F .
. mv r2 r1
. muli r2 0xc9b97113
. lei r2 0xe79372
. cjmp F .
. mv r2 r1
. muli r2 0x84ce32ad
. lei r2 0xdfac1f
. cjmp F .
. mv r2 r1
. muli r2 0xc74be1fb
. lei r2 0xd578e9
. cjmp F .
. mv r2 r1
. muli r2 0xa7198487
. lei r2 0xd2ba08
. cjmp F .
. mv r2 r1
. muli r2 0x39409d09
. lei r2 0xd16154
. cjmp F .
. mv r2 r1
. muli r2 0x6f71de15
. lei r2 0xcebcf8
. cjmp F .
. mv r2 r1
. muli r2 0xbfce8063
. lei r2 0xc5fe74
. cjmp F .
. mv r2 r1
. muli r2 0xf61fe7b1
. lei r2 0xc27806
. cjmp F .
. mv r2 r1
. muli r2 0x70e046d3
. lei r2 0xbcdd53
. cjmp F .
. mv r2 r1
. muli r2 0xf1545af5
. lei r2 0xbbc840
. cjmp F .
. mv r2 r1
. muli r2 0x9a7862a1
. lei r2 0xb9a786
. cjmp F .
. mv r2 r1
. muli r2 0x2a128a57
. lei r2 0xb68d31
. cjmp F .
. mv r2 r1
. muli r2 0xb7747d8f
. lei r2 0xb2927c
. cjmp F .
. mv r2 r1
. muli r2 0xbb5e06dd
. lei r2 0xafb321
. cjmp F .
. mv r2 r1
. muli r2 0x12e9b5b3
. lei r2 0xaceb0f
. cjmp F .
. mv r2 r1
. muli r2 0xec9dbe7f
. lei r2 0xab1cbd
. cjmp F .
. mv r2 r1
. muli r2 0xec41cf4d
. lei r2 0xa87917
. cjmp F .
. mv r2 r1
. muli r2 0xaec02945
. lei r2 0xa513fd
. cjmp F .
. mv r2 r1
. muli r2 0x8382df71
. lei r2 0xa36e71
. cjmp F .
. mv r2 r1
. muli r2 0x84b1c2a9
. lei r2 0xa03c16
. cjmp F .
. mv r2 r1
. muli r2 0x75eb3a0b
. lei r2 0x9c6916
. cjmp F .
. mv r2 r1
. muli r2 0xfa86fe2d
. lei r2 0x9baade
. cjmp F .
. mv r2 r1
. muli r2 0x3f8df54f
. lei r2 0x980e41
. cjmp F .
. mv r2 r1
. muli r2 0x975a751
. lei r2 0x975a75
. cjmp F .
. mv r2 r1
. muli r2 0xc3efac07
. lei r2 0x9548e4
. cjmp F .
. mv r2 r1
. muli r2 0xa8299b73
. lei r2 0x93efd1
. cjmp F .
. mv r2 r1
. muli r2 0x9ba70e41
. lei r2 0x91f5bc
. cjmp F .
. mv r2 r1
. muli r2 0x23d9e879
. lei r2 0x8f67a1
. cjmp F .
. mv r2 r1
. muli r2 0xc494d305
. lei r2 0x8e2917
. cjmp F .
. mv r2 r1
. muli r2 0xab67652f
. lei r2 0x8d8be3
. cjmp F .
. mv r2 r1
. muli r2 0xfb10fe5b
. lei r2 0x8c5584
. cjmp F .
. mv r2 r1
. muli r2 0xbf54fa1f
. lei r2 0x88d180
. cjmp F .
. mv r2 r1
. muli r2 0xb98f81d7
. lei r2 0x869222
. cjmp F .
. mv r2 r1
. muli r2 0xe90f1ec3
. lei r2 0x85797b
. cjmp F .
. mv r2 r1
. muli r2 0xbed87f3b
. lei r2 0x8355ac
. cjmp F .
. mv r2 r1
. muli r2 0x16e70fc7
. lei r2 0x824a4e
. cjmp F .
. mv r2 r1
. muli r2 0x9dece355
. lei r2 0x80c121
. cjmp F .
. mv r2 r1
. muli r2 0x73f62c39
. lei r2 0x7dc9f3
. cjmp F .
. mv r2 r1
. muli r2 0xad46f9a3
. lei r2 0x7d4ece
. cjmp F .
. mv r2 r1
. muli r2 0x24e8d035
. lei r2 0x79237d
. cjmp F .
. mv r2 r1
. muli r2 0x2319bd8b
. lei r2 0x77cf53
. cjmp F .
. mv r2 r1
. muli r2 0xc7ed9da5
. lei r2 0x75a8ac
. cjmp F .
. mv r2 r1
. muli r2 0xfea2c8fb
. lei r2 0x7467ac
. cjmp F .
. mv r2 r1
. muli r2 0xce0f4c09
. lei r2 0x732d70
. cjmp F .
. mv r2 r1
. muli r2 0x544986f3
. lei r2 0x72c62a
. cjmp F .
. mv r2 r1
. muli r2 0x55a10dc1
. lei r2 0x7194a1
. cjmp F .
. mv r2 r1
. muli r2 0x85e33763
. lei r2 0x6fa549
. cjmp F .
. mv r2 r1
. muli r2 0xd84886b1
. lei r2 0x6e8419
. cjmp F .
. mv r2 r1
. muli r2 0x31260967
. lei r2 0x6d68b5
. cjmp F .
. mv r2 r1
. muli r2 0xd1ff25e9
. lei r2 0x6d0b80
. cjmp F .
. mv r2 r1
. muli r2 0x5b84d99f
. lei r2 0x6bf790
. cjmp F .
. mv r2 r1
. muli r2 0x1335df6d
. lei r2 0x6ae907
. cjmp F .
. mv r2 r1
. muli r2 0x75d5add9
. lei r2 0x6a3799
. cjmp F .
. mv r2 r1
. muli r2 0x3c619a43
. lei r2 0x69dfbd
. cjmp F .
. mv r2 r1
. muli r2 0x4767747
. lei r2 0x67dc4c
. cjmp F .
. mv r2 r1
. muli r2 0x663d81
. lei r2 0x663d80
. cjmp F .
. mv r2 r1
. muli r2 0x671ddc2b
. lei r2 0x65ec17
. cjmp F .
. mv r2 r1
. muli r2 0xc1e12337
. lei r2 0x654ac8
. cjmp F .
. mv r2 r1
. muli r2 0x9cd09045
. lei r2 0x645c85
. cjmp F .
. mv r2 r1
. muli r2 0x91496b9b
. lei r2 0x637299
. cjmp F .
. mv r2 r1
. muli r2 0xc7d7b8bd
. lei r2 0x632591
. cjmp F .
. mv r2 r1
. muli r2 0x9f006161
. lei r2 0x6160ff
. cjmp F .
. mv r2 r1
. muli r2 0x5e28152d
. lei r2 0x60cdb5
. cjmp F .
. mv r2 r1
. muli r2 0xbfe803
. lei r2 0x5ff401
. cjmp F .
. mv r2 r1
. muli r2 0x9e907c7b
. lei r2 0x5ed79e
. cjmp F .
. mv r2 r1
. muli r2 0x76528895
. lei r2 0x5d7d42
. cjmp F .
. mv r2 r1
. muli r2 0x1ce2c0d
. lei r2 0x5c6f35
. cjmp F .
. mv r2 r1
. muli r2 0xbed7c42f
. lei r2 0x5b2618
. cjmp F .
. mv r2 r1
. muli r2 0xd4b010e7
. lei r2 0x5a2553
. cjmp F .
. mv r2 r1
. muli r2 0x1ebbe575
. lei r2 0x59686c
. cjmp F .
. mv r2 r1
. muli r2 0xb47b52cb
. lei r2 0x58ae97
. cjmp F .
. mv r2 r1
. muli r2 0x64f3f0d7
. lei r2 0x58345f
. cjmp F .
. mv r2 r1
. muli r2 0x316d6c0f
. lei r2 0x5743d5
. cjmp F .
. mv r2 r1
. muli r2 0x91c1195d
. lei r2 0x5692c4
. cjmp F .
. mv r2 r1
. muli r2 0xa27b1f49
. lei r2 0x561e46
. cjmp F .
. mv r2 r1
. muli r2 0xe508fd01
. lei r2 0x5538ed
. cjmp F .
. mv r2 r1
. muli r2 0x133551cd
. lei r2 0x54c807
. cjmp F .
. mv r2 r1
. muli r2 0x2d8a3f1b
. lei r2 0x5345ef
. cjmp F .
. mv r2 r1
. muli r2 0xc34ad735
. lei r2 0x523a75
. cjmp F .
. mv r2 r1
. muli r2 0xa714919
. lei r2 0x510237
. cjmp F .
. mv r2 r1
. muli r2 0x24eea383
. lei r2 0x50cf12
. cjmp F .
. mv r2 r1
. muli r2 0x42ba771d
. lei r2 0x4fd319
. cjmp F .
. mv r2 r1
. muli r2 0x7772287
. lei r2 0x4fa170
. cjmp F .
. mv r2 r1
. muli r2 0x5e69ddf3
. lei r2 0x4f3ed6
. cjmp F .
. mv r2 r1
. muli r2 0x3b4a6c15
. lei r2 0x4f0de5
. cjmp F .
. mv r2 r1
. muli r2 0xc606b677
. lei r2 0x4e1cae
. cjmp F .
. mv r2 r1
. muli r2 0x46d3e1fd
. lei r2 0x4cd47b
. cjmp F .
. mv r2 r1
. muli r2 0x484a14e9
. lei r2 0x4c78ae
. cjmp F .
. mv r2 r1
. muli r2 0x1ce874d3
. lei r2 0x4c4b19
. cjmp F .
. mv r2 r1
. muli r2 0x473189f
. lei r2 0x4bf093
. cjmp F .
. mv r2 r1
. muli r2 0x372b7e65
. lei r2 0x4aba3c
. cjmp F .
. mv r2 r1
. muli r2 0x4f9e5d91
. lei r2 0x4a6360
. cjmp F .
. mv r2 r1
. muli r2 0x446bd9bb
. lei r2 0x4a383e
. cjmp F .
. mv r2 r1
. muli r2 0xe777c647
. lei r2 0x49e28f
. cjmp F .
. mv r2 r1
. muli r2 0xf61f0c23
. lei r2 0x48417b
. cjmp F .
. mv r2 r1
. muli r2 0xa5cbbb6f
. lei r2 0x47f043
. cjmp F .
. mv r2 r1
. muli r2 0x69daac27
. lei r2 0x474ff2
. cjmp F .
. mv r2 r1
. muli r2 0x637aa061
. lei r2 0x468b6f
. cjmp F .
. mv r2 r1
. muli r2 0x1fb15099
. lei r2 0x45f13f
. cjmp F .
. mv r2 r1
. muli r2 0x712c5825
. lei r2 0x45a522
. cjmp F .
. mv r2 r1
. muli r2 0xff30637b
. lei r2 0x45342c
. cjmp F .
. mv r2 r1
. muli r2 0x1131289
. lei r2 0x44c4a2
. cjmp F .
. mv r2 r1
. muli r2 0xf5acdf7
. lei r2 0x43c5c2
. cjmp F .
. mv r2 r1
. muli r2 0x4d3f89e3
. lei r2 0x437e49
. cjmp F .
. mv r2 r1
. muli r2 0xd2253531
. lei r2 0x43142d
. cjmp F .
. mv r2 r1
. muli r2 0x7bf69fe7
. lei r2 0x42ab5c
. cjmp F .
. mv r2 r1
. muli r2 0xcfb1781f
. lei r2 0x422195
. cjmp F .
. mv r2 r1
. muli r2 0x318e81ed
. lei r2 0x41bbb2
. cjmp F .
. mv r2 r1
. muli r2 0x9f148d11
. lei r2 0x40f391
. cjmp F .
. mv r2 r1
. muli r2 0x2c7a505d
. lei r2 0x40b1e9
. cjmp F .
. mv r2 r1
. muli r2 0x28728f33
. lei r2 0x405064
. cjmp F .
. mv r2 r1
. muli r2 0xe5ec7155
. lei r2 0x403024
. cjmp F .
. mv r2 r1
. muli r2 0x9fe829b7
. lei r2 0x3f90c2
. cjmp F .
. mv r2 r1
. muli r2 0x6a50ca39
. lei r2 0x3f7141
. cjmp F .
. mv r2 r1
. muli r2 0xb6d26aef
. lei r2 0x3f1377
. cjmp F .
. mv r2 r1
. muli r2 0xa8251829
. lei r2 0x3e7988
. cjmp F .
. mv r2 r1
. muli r2 0x1b863613
. lei r2 0x3e5b19
. cjmp F .
. mv r2 r1
. muli r2 0x20d077ad
. lei r2 0x3dc4a5
. cjmp F .
. mv r2 r1
. muli r2 0x2e3d2b97
. lei r2 0x3da6e4
. cjmp F .
. mv r2 r1
. muli r2 0x3dc8eba5
. lei r2 0x3d4e4f
. cjmp F .
. mv r2 r1
. muli r2 0x3229ebbf
. lei r2 0x3c4a6b
. cjmp F .
. mv r2 r1
. muli r2 0x7e01686b
. lei r2 0x3c11d5
. cjmp F .
. mv r2 r1
. muli r2 0x2c086e8d
. lei r2 0x3bf5b1
. cjmp F .
. mv r2 r1
. muli r2 0x9f632df9
. lei r2 0x3bbdb9
. cjmp F .
. mv r2 r1
. muli r2 0xdff892af
. lei r2 0x3b6a88
. cjmp F .
. mv r2 r1
. muli r2 0x3f04d8fd
. lei r2 0x3b183c
. cjmp F .
. mv r2 r1
. muli r2 0x9cfdeff5
. lei r2 0x3aabe3
. cjmp F .
. mv r2 r1
. muli r2 0xbda9d4b
. lei r2 0x3a5ba3
. cjmp F .
. mv r2 r1
. muli r2 0x24f5cbd9
. lei r2 0x3a0c3e
. cjmp F .
. mv r2 r1
. muli r2 0x94cbbb7f
. lei r2 0x38f035
. cjmp F .
. mv r2 r1
. muli r2 0xb4f43b81
. lei r2 0x38d6ec
. cjmp F .
. mv r2 r1
. muli r2 0x34d4323
. lei r2 0x3859cf
. cjmp F .
. mv r2 r1
. muli r2 0x74f5b99b
. lei r2 0x37f741
. cjmp F .
. mv r2 r1
. muli r2 0xc68ea1b5
. lei r2 0x377df0
. cjmp F .
. mv r2 r1
. muli r2 0x96c0cf0b
. lei r2 0x373622
. cjmp F .
. mv r2 r1
. muli r2 0xe33edf99
. lei r2 0x36ef0c
. cjmp F .
. mv r2 r1
. muli r2 0xb897c451
. lei r2 0x36915f
. cjmp F .
. mv r2 r1
. muli r2 0x8fb91695
. lei r2 0x36072c
. cjmp F .
. mv r2 r1
. muli r2 0xe5ea8b41
. lei r2 0x35d9b7
. cjmp F .
. mv r2 r1
. muli r2 0x93fd7cf7
. lei r2 0x359615
. cjmp F .
. mv r2 r1
. muli r2 0xb3f8805
. lei r2 0x35531c
. cjmp F .
. mv r2 r1
. muli r2 0xa912822f
. lei r2 0x353cee
. cjmp F .
. mv r2 r1
. muli r2 0x13a9147d
. lei r2 0x34fad3
. cjmp F .
. mv r2 r1
. muli r2 0xc4c3f21
. lei r2 0x347884
. cjmp F .
. mv r2 r1
. muli r2 0x7a6883c3
. lei r2 0x340dd3
. cjmp F .
. mv r2 r1
. muli r2 0x2ab33855
. lei r2 0x3351fd
. cjmp F .
. mv r2 r1
. muli r2 0x82e6faff
. lei r2 0x333d72
. cjmp F .
. mv r2 r1
. muli r2 0x17be8dab
. lei r2 0x33148d
. cjmp F .
. mv r2 r1
. muli r2 0x7cb91939
. lei r2 0x32d7ae
. cjmp F .
. mv r2 r1
. muli r2 0x42a09ea3
. lei r2 0x32c385
. cjmp F .
. mv r2 r1
. muli r2 0x6d8b8bf1
. lei r2 0x328766
. cjmp F .
. mv r2 r1
. muli r2 0xba8a223d
. lei r2 0x325fa1
. cjmp F .
. mv r2 r1
. muli r2 0x9c3182a7
. lei r2 0x324bd6
. cjmp F .
. mv r2 r1
. muli r2 0x474bcd13
. lei r2 0x32246e
. cjmp F .
. mv r2 r1
. muli r2 0xc5311a97
. lei r2 0x31afa5
. cjmp F .
. mv r2 r1
. muli r2 0xc00c6719
. lei r2 0x319c63
. cjmp F .
. mv r2 r1
. muli r2 0x4b0b61cf
. lei r2 0x3162f7
. cjmp F .
. mv r2 r1
. muli r2 0x9b8e63b1
. lei r2 0x30271f
. cjmp F .
. mv r2 r1
. muli r2 0x41eb667
. lei r2 0x2ff104
. cjmp F .
. mv r2 r1
. muli r2 0x896a76f5
. lei r2 0x2fbb62
. cjmp F .
. mv r2 r1
. muli r2 0x4a55a46d
. lei r2 0x2f7499
. cjmp F .
. mv r2 r1
. muli r2 0x58046447
. lei r2 0x2ed84a
. cjmp F .
. mv r2 r1
. muli r2 0x69be3a81
. lei r2 0x2e832d
. cjmp F .
. mvi r3 1423
L mv r2 r3
. mul r2 r2
. gt r2 r1
. cjmp T .
. mv r2 r1
. div r2 r3
. lnot r0 .
. cjmp F .
. addi r3 2
. jmp L .
T not r4 .
F outd r4 .
. end . .

```

And this is the Python script used to generate the code, which actually steals a bit of optimized output from `gcc`.

```
import sympy
import os

p = []
m = []
c = []
M = sympy.sqrt(2000000)
i = 3
while i < M:
    if (sympy.isprime(i)):
        p.append(i)
    i += 2
f = open("prime.c", "w")
f.write("int main() {}\n")
for i in range(len(p)):
    f.write("unsigned d" + str(p[i]) + "(unsigned a) {return !(a % " +
    str(p[i]) + ");}\n")
f.close()
os.system("gcc -S -masm=intel -O3 -oprime.s prime.c")
f = open("prime.s", "r")
s = f.read()
f.close()

def h(d):
    d = int(d)
    if d < 0:
        return str(hex(d + (1 << 32)))
    else:
        return str(hex(d))

def g(s):
    for i in range(len(s)):
        if s[i] == '-':
            s = s[i:]
            break;
        if s[i].isdigit():
            s = s[i:]
            break;
    d = ""
    i = 0
    while i < len(s):
        if s[i] == '-' or s[i].isdigit():
            d += s[i]
        else:
            break
        i += 1
    return h(d), s[i:]

for i in range(len(p)):
    s = s[s.find("d" + str(p[i]) + ":"):]
    s = s[s.find("imul"):]
    n, s = g(s)
    m.append(n)
    n, s = g(s)
    c.append(n)
f = open("prime.s", "w")
f.write(". ind r1 .\n. lti r1 2\n. cjmp F .\n. eqi r1 2\n. cjmp T .\n" +
". mv r0 r1\n. andi r0 1\n. lnot r0 .\n. cjmp F .\n. lti r1 9\n. cjmp T .\n")
l = 9
for i in range(len(p)):
    if p[i] > l:
        l = p[i] * p[i]
        f.write(". lti r1 " + str(l) + "\n. cjmp T .\n")
    f.write(". mv r2 r1\n. muli r2 " + m[i] + "\n. lei r2 " + c[i] +
    "\n. cjmp F .\n")
f.write(". mvi r3 1423\nL mv r2 r3\n. mul r2 r2\n. gt r2 r1\n. cjmp T .\n" +
". mv r2 r1\n. div r2 r3\n. lnot r0 .\n. cjmp F .\n. addi r3 2\n. jmp L .\n" +
"T not r4 .\nF outd r4 .\n. end . .\n")
f.close()

```

---
Tags: number-theory, primes, fastest-code, assembly
---


title: Play the Fruit Box Game

text:
# Question
Title: Play the Fruit Box Game
# Play the Fruit Box Game

## Intro

Fruit Box is a game consisting of a 10x17 grid of numbers, each between 1 and 9, where the goal is to clear as many numbers as possible in a two-minute time window. In order to clear numbers, one selects a rectangle aligned with the grid, and if the numbers inside of it sum to 10, they are cleared off the field. At the start of the game, the grid is randomly populated, with the only requirement being that the sum of all numbers in the field is a multiple of 10. Several examples are shown below:

This is an example starting field, with several, but not all, valid possible clears shown.

This is a field partway through the game, with new possible clears being opened as a result of previous numbers being taken off the field. Notice that, for example, if the 6-3-1 rectangle in the bottom left were cleared, it would open the possibility to clear two 9-1 pairs horizontally which are currently blocked.

Perhaps the easiest way to familiarize yourself with the game is to play several rounds, which can be done here: Fruit Box

## The Challenge

If you haven't guessed by now, the challenge is to write a program which plays the above game as optimally as possible, where optimal means clearing the most numbers.

### Input

The input will be the starting grid of numbers. It can be taken in any *reasonable* representation, meaning you can take it in as a string, an array of 10 17-length integers, a 2D array of 170 integers, or any other similar form. Use your best judgement as to what *reasonable* means, but in the spirit of the challenge, it should be some representation of the starting grid of numbers. Please specify in your answer exactly how input should be passed.

### Output

The output should be the final score achieved (numbers cleared), as well as the list of moves to achieve this score. Again, the exact form of this output is up to you, but it should be such that given the list of moves, one can unambiguously replay the game from the same starting configuration to end up at the given final score. For example, one could output the top left and bottom right coordinate of each rectangle cleared in order.

Beyond the above, the normal input/output rules, as well as forbidden loopholes apply. If you are unsure about any of the specifications, leave a comment and I will clarify.

## Scoring

The score on a particular board is given by how many numbers are cleared over the course of the game. For example, if there are 14 numbers left at the end of the game, regardless of their values, the final score will be 170-14 = 156.

Since each starting board will have a different optimal score, all answers will be run on the same set of 10 boards for evaluation, which I will keep hidden. At the bottom of this post, I will maintain a leaderboard of the current top submissions, based on their average performance across these 10 boards. The answer which is at the top of the leaderboard one month after the first submission will be accepted.

Edit: If the algorithm is not deterministic, the average-of-5 will be used for each of the 10 boards.

## Other Rules

* Since the original game gives you 2 minutes, the submission must run in under 2 minutes on my machine (a 4 core, 2017 MacBook Pro with 16GB of RAM). A small amount of leeway will be given to account for typical variations.
* You must use a language which is free to use and can be found online. (This should not disqualify any typically-used languages)

# Leaderboard

## One month has passed, and the leaderboard is now closed. Congratulations to dingledooper for taking the win!

1. dingledooper: **147.2 Points**
2. M Virts: **129.0 Points**
3. Luis Mendo: **126.0 Points**
4. Ajax1234: **119.6 Points**
5. Richard Neumann: **118.0 Points**

### Example Boards

Here are 3 valid example boards. Each board also includes the score achieved by naively clearing rectangles in order until none remain, as a lower bound on the possible score.

```
Board 1: Optimal Score >= 104
---------------------------------
7 8 3 8 4 4 3 1 4 5 3 2 7 7 4 6 7
6 4 3 3 3 7 1 5 1 9 2 3 4 5 5 4 6
9 7 5 5 4 2 2 9 1 9 1 1 1 7 2 2 4
3 3 7 5 5 8 9 3 6 8 5 3 5 3 2 8 7
7 3 5 8 7 8 6 3 5 6 8 9 9 9 8 5 3
5 8 3 9 9 7 6 7 3 6 9 1 6 8 3 2 5
4 9 5 7 7 5 7 8 4 4 4 2 9 8 7 3 5
8 2 1 7 9 1 7 9 6 5 4 1 3 7 6 9 6
2 3 5 6 5 6 3 9 6 6 3 6 9 7 8 8 1
1 8 5 2 2 3 1 9 3 3 3 3 7 8 7 4 8

Board 2: Optimal Score >= 113
---------------------------------
5 4 3 6 7 2 3 5 1 2 8 6 2 3 8 1 7
3 8 7 5 4 6 6 1 6 5 7 5 4 3 8 8 1
7 9 9 3 1 7 1 8 9 1 8 4 9 8 7 1 7
5 4 6 3 1 3 1 5 4 7 4 1 5 8 1 1 5
3 3 4 3 8 7 6 5 8 6 3 2 8 4 6 6 6
7 2 2 8 9 9 7 7 7 7 3 9 1 2 7 2 4
4 1 1 5 7 7 9 2 3 6 9 2 7 5 7 7 1
9 6 7 1 7 9 8 7 3 2 8 9 8 6 1 6 8
1 3 9 6 4 5 5 3 4 9 4 1 9 2 6 9 1
6 9 6 3 1 5 8 2 3 5 4 2 6 4 5 3 5

Board 3: Optimal Score >= 116
---------------------------------
9 2 2 7 6 6 1 7 1 9 7 6 9 3 8 8 3
2 2 4 8 6 9 8 4 8 3 8 1 1 2 7 4 9
8 5 1 8 9 5 5 1 7 7 5 1 3 4 6 5 1
5 2 9 2 2 1 7 5 4 5 9 5 6 4 2 9 7
4 9 6 3 6 2 3 9 2 1 2 8 8 7 9 4 7
1 9 7 2 2 2 6 2 1 2 5 6 2 5 6 7 8
8 8 4 4 9 5 7 2 3 8 2 4 8 1 4 7 3
9 4 7 2 3 7 2 8 4 6 9 8 3 8 5 2 9
4 8 1 3 9 1 6 6 6 7 2 1 4 5 2 6 2
3 7 3 8 1 2 1 8 1 8 3 3 2 3 2 7 4

```

# Answer
> 6 votes
# C++ (gcc)

Performs a brute force search. Its strategy is to greedily choose rectangles that yield the least amount of points. Although counter-intuitive, this strategy is seemingly effective. To give the search more variation, the branch size is also limited to 4. Memoization is used to prevent the same board state from re-occurring (due to applying the same operations in a different order). As for calculating the rectangle sums, a two-pointer approach is taken to remove a linear factor from the time complexity.

It outputs a chain of length-4 tuples `(r0,c0,r1,c1)`, where `r0,c0` and `r1,c1` are the top-left and bottom-right row-column coordinates.

Compiled with `g++ -std=c++17 -O2`.

```
#include <chrono>
#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>

constexpr int ROWS = 10, COLS = 17;

// Program auto-exits by default after two minutes
constexpr int TIMEOUT = 120;

using Grid = std::array<std::array<int, COLS + 1>, ROWS + 1>;

struct Move { int cleared = 256, r0, c0, r1, c1; };

struct Sol {
    int score = 0;
    std::vector<Move> moves;
    Grid grid;
};

__gnu_pbds::gp_hash_table<long long, __gnu_pbds::null_type> cache;
std::vector<Move> moves;

const auto start = std::chrono::system_clock::now();

long long get_hash(Grid &grid) {
    long long hsh = 0;
    for (int r = 1; r <= ROWS; r++)
        for (int c = 1; c <= COLS; c++)
            hsh = hsh * 33 + grid[r][c] + 1;
    return hsh;
}

void print_solution(Sol &sol) {
    std::cout << sol.score << ": ";
    bool begin = true;
    for (auto &[_, r0, c0, r1, c1] : sol.moves) {
        if (!begin) std::cout << " -> ";
        begin = false;
        std::cout << "(" << r0 << ',' << c0 << ',' << r1 << ',' << c1 << ")";
    }
    std::cout << "\n";
}

void search(Grid grid, Sol &sol, int score = 0) {
    const auto now = std::chrono::system_clock::now();
    if (std::chrono::duration<double>(now - start).count() > TIMEOUT) {
        std::cout << TIMEOUT << " seconds elapsed. Exiting...\n";
        print_solution(sol);
        exit(EXIT_SUCCESS);
    }

    const long long hsh = get_hash(grid);
    if (cache.find(hsh) != cache.end())
        return;
    cache.insert(hsh);

    if (score > sol.score)
        sol = {score, moves, grid};

    Grid csum;
    for (int c = 1; c <= COLS; c++) csum[0][c] = 0;
    for (int r = 1; r <= ROWS; r++)
        for (int c = 1; c <= COLS; c++)
            csum[r][c] = csum[r - 1][c] + grid[r][c];

    Move mv0, mv1, mv2, mv3;
    for (int r0 = 1; r0 <= ROWS; r0++) {
        const auto &p0 = csum[r0 - 1];
        for (int r1 = r0; r1 <= ROWS; r1++) {
            const auto &p1 = csum[r1];

            int sum = 0;
            for (int c0 = 1, c1 = 0; c0 <= COLS; c0++) {
                while (c1 < COLS && sum < 10)
                    ++c1, sum += p1[c1] - p0[c1];

                if (sum == 10) {
                    int cleared = 0;
                    for (int r = r0; r <= r1; r++)
                        for (int c = c0; c <= c1; c++)
                            cleared += grid[r][c] != 0;

                    if (cleared < mv0.cleared)
                        mv3 = mv2, mv2 = mv1, mv1 = mv0, mv0 = {cleared, r0, c0, r1, c1};
                    else if (cleared < mv1.cleared)
                        mv3 = mv2, mv2 = mv1, mv1 = {cleared, r0, c0, r1, c1};
                    else if (cleared < mv2.cleared)
                        mv3 = mv2, mv2 = {cleared, r0, c0, r1, c1};
                    else if (cleared < mv3.cleared)
                        mv3 = {cleared, r0, c0, r1, c1};
                }
                sum -= p1[c0] - p0[c0];
            }
        }
    }

    for (const auto &m : {mv0, mv1, mv2, mv3}) {
        const auto &[cleared, r0, c0, r1, c1] = m;
        if (cleared == 256) break;

        auto ngrid = grid;
        for (int r = r0; r <= r1; r++)
            for (int c = c0; c <= c1; c++)
                ngrid[r][c] = 0;

        moves.push_back(m);
        search(ngrid, sol, score + cleared);
        moves.pop_back();
    }
}

int main() {
    // comment out this line to input via STDIN
    freopen("input.txt", "r", stdin);

    Grid grid;
    for (int r = 1; r <= ROWS; r++)
        for (int c = 1; c <= COLS; c++)
            std::cin >> grid[r][c];

    Sol sol;
    search(grid, sol);

    auto end = std::chrono::system_clock::now();
    print_solution(sol);
    std::cout << "Time elapsed: " << std::chrono::duration<double>(end - start).count() << "s\n";

    return 0;
}

```

Try it online!

# Answer
> 6 votes
# Python3, 659 bytes:

```
from time import*
r,l=range,len
s=lambda v:[(t,x,y)for x in r(l(v))for y in r(x+1,l(v)+1)if(t:=sum(v[x:y]))<=10 and any(v[x:y])]
def f(b,p=[]):
 u=[]
 for x in r(l(b)):
  for q,w,e in s(b[x]):
   if q==10:u+=[(x,x+1,w,e)]
   elif n:=next((y for y in r(l(b)+1)if y>x and sum(sum(m[w:e])for m in b[x:y])==10),0):u+=[(x,n,w,e)]
 for g in sorted(u,key=lambda x:(x[1]-x[0])*(x[3]-x[2])):
  yield from f(b[:g[0]]+[d[:g[2]]+([0]*(g[3]-g[2]))+d[g[3]:] for d in b[g[0]:g[1]]]+b[g[1]:],p+[g])
 if not u:
  yield sum(sum(not i for i in j)for j in b),p
def e(b,s=120):
 t,r,w=time(),[],f(b)
 while time()-t<s and(n:=next(w,0)):r.append(n)
 return max(r,key=lambda x:x[0])

```

Try it online! (with a 50 second maximum time limit)

### Input

This solution takes in a list of lists with the integers representing the board (i.e `[[9, 2, 2, 7, 6, 6, 1, 7, 1, 9, 7, 6, 9, 3, 8, 8, 3], ..., [3, 7, 3, 8, 1, 2, 1, 8, 1, 8, 3, 3, 2, 3, 2, 7, 4]]` for the last example). In the TIO link, I have included in the footer a Python function to convert a string representation of the board to the required list of lists (see `to_board`).

The input is passed to the function `e`, along with an optional time limit, set to the maximum for this challenge (two minutes). After running for the maximum period of time, or until all possible boards have been produced, the optimal result is returned.

### Output

`e` returns a tuple containing the score (the first element), and the path to produce the score. The path contains each move (the area of the input that sums to 10), which is represented as a tuple. The first two elements form the vertical range, and the last two elements comprise the horizontal range. For example, the move `(0, 1, 8, 10)` selects the `1` and `9` from the first row of the input board (rows `0` to `1`, noninclusive, with indices `8` to `10`, noninclusive).

### Note

The use of the time limit is solely to produce as high a score as possible. Without a time limit, the maximum score of the first `100` iterations of the generator will still result in a value above the optimal cutoff.

# Answer
> 5 votes
# Octave. Purely random approach

This applies moves randomly until no further moves are possible. Then tries a new sequence of moves until a time limit is reached. The best sequence of moves is chosen output.

Pseudo-code:

1. Generate all possible rectangle sizes.
2. Permute the list of rectangle sizes randomly with uniform distribution. Set `s` to `0`.
3. Increase `s`. If `s` exceeds the number of possible rectangle sizes (no further moves are possible): compute score and go to step **6**. Else: continue normally.
4. Perform 2D convolution with the `s`-th size. This computes all sums in a sliding rectangle of that size.
5. If there are sums that equal `10`: choose one randomly with uniform distribution. Set the corresponding entries in the board to `0`, store the move, and go to step **2**. Else: go to step **3**.
6. If the current score is better than the best so far: update best score and list of moves.
7. If time allows: go to step **2** (to try a new sequence of moves). Else: output best score and list of moves.

The code is a function that takes the board and time limit as inputs, and produces the score and sequence of moves as outputs (a third, optional output gives the number of tries).

The board is defined as an Octave matrix. The sequence of moves is a 4-column matrix,

```
[ up1 down1 left1 right1
  up2 down2 left2 right2
   ··· ]

```

`up1` to `down1` is the 1-based, inclusive range that defines the vertical span of the first rectangle in matrix coordinates; and similarly `left1` and `right1` define its horizontal span. `up2` etc refer to the second move, and so on.

```
function [score, moves, num_tries] = fruit_box(board_input, time_limit)

tic % start timer

target_sum = 10;

sizes_rect = {[], []};
[sizes_rect{:}] = ndgrid(1:size(board_input, 1), 1:size(board_input, 2));
sizes_rect = reshape(cat(3, sizes_rect{:}), [], 2).'; % each column defines a rectangle size
sizes_rect = sizes_rect(:, 2:end); % remove first column: [1; 1], which never gives a valid move

score = 0;
moves = [];
num_tries = 0;
while toc < time_limit
    num_tries = num_tries + 1;
    board_try = board_input; % initiallize board for current try
    moves_try = []; % initiallize moves for current try
    done = false;
    while ~done
        done = true;
        for size_rect = sizes_rect(:,randperm(end))
            sums = conv2(board_try, ones(size_rect.'), 'valid');
            [up, left] = find(sums==target_sum);
            if up % at least one move is possible
                ind = randi(numel(up));
                moves_try(end+1, :) = [up(ind) up(ind)+size_rect(1)-1 left(ind) left(ind)+size_rect(2)-1]; % store move
                board_try(moves_try(end,1):moves_try(end,2), moves_try(end,3):moves_try(end,4)) = 0; % set to zero
                done = false; % further moves may be possible in current try
                break
            end
        end
    end
    score_try = nnz(board_try==0); % the score is the number of zeros
    if score_try > score % update solution if better
        score = score_try;
        moves = moves_try;
    end
end

```

**Try it online!** (with 55-second limit).

# Answer
> 5 votes
# Python, 2013 bytes

Uses numpy and ffts to generate moves by convolution, then starts a depth first search of all possible moves, with a timeout to limit the search (definitely not terminating any time soon without that). Caches move generation and step results based on the input board.

Prefers small moves first to knock out large numbers. I also tried random weights but it doesn't seem to do well consistently.

I'm using a list of rows (lists) as input, should also work with tuples and other iterables.

```
import time
import random
import numpy as np
import sys
sys.setrecursionlimit(10000)

def go(b):
    timeout=115 # seconds, set to 5 on ATO

    r = len(b)
    c = len(b[0])

    fftshape = (2*r,2*c)
    shapes = [(i,j) for i in range(1,r) for j in range(1,c) if i*j!=1]
    kernels = [np.ones(s) for s in shapes]
    ffts = np.stack([np.conj(np.fft.fft2(k,fftshape)) for k in kernels],axis=2)

    def _getmoves(b):
        ba = np.asarray(b)
        kres = np.real(np.fft.ifft2(((np.fft.fft2(ba,fftshape)[:,:,np.newaxis]*ffts)),axes=(0,1)))
        res = [kres[:,:,i] for i in range(kres.shape[2])]
        ix = [np.argwhere(np.all(np.stack((r>9.5,r<10.5),axis=2),axis=2)) for r in res]
        moves = [((i[0],i[0]+s[0]),(i[1],i[1]+s[1])) for s,ix in zip(shapes,ix) for i in ix if i[0]+s[0] <= ba.shape[0] and i[1]+s[1] <= ba.shape[1] ]
        return moves

    movec = {}
    def getmoves(b):
        if b not in movec:
            movec[b] = _getmoves(b)
    #         print("miss")

        return movec[b]

    def _step(b):
        nonlocal timeout
        nonlocal start_time
        moves = getmoves(b)
        ba = np.asarray(b)
        if moves and not time.time() - start_time  > timeout:
            rl=[]
            best=(0,)
            for m in sorted(moves,key=lambda m:(m[0][1]-m[0][0])*(m[1][1]-m[1][0])):
                bac = ba.copy()
                bac[m[0][0]:m[0][1],m[1][0]:m[1][1]]=0;
                score,bar,ml=step((*map(tuple,bac.tolist()),));
                if score > best[0]:
                    best = (score,bar,[m]+ml)
            return best
        else:
            score = (ba.shape[0]*ba.shape[1])-(ba>0).sum()
            return score,ba,[]

    stepc = {}
    def step(b):
        if b not in stepc:
            stepc[b] = _step(b)
        return stepc[b]

    start_time = time.time()
    score,baf,movelist = step((*map(tuple,b),))
    print(f"Score: {score}")
    print(movelist)
    print(baf)
    return score,movelist,baf
```

Attempt This Online!

# Answer
> 4 votes
# C++

```
#include <algorithm>
using std::sort;

#include <functional>
using std::reference_wrapper;

#include <initializer_list>
using std::initializer_list;

#include <iostream>
using std::cout;
using std::ostream;

#include <numeric>
using std::accumulate;

#include <vector>
using std::vector;

struct Cell {
    unsigned short number;

    explicit Cell(unsigned short number)
        : number(number)
    {
    }

    friend unsigned short operator+(unsigned short lhs, Cell const & cell)
    {
        return lhs + cell.number;
    }

    friend ostream & operator<<(ostream & out, Cell const & cell)
    {
        out << cell.number;
        return out;
    }
};

struct Point {
    size_t x, y;

    Point(size_t x, size_t y)
        : x(x), y(y)
    {
    }

    friend ostream & operator<<(ostream & out, Point const & point)
    {
        out << point.x << "x" << point.y;
        return out;
    }
};

struct Frame {
    Point start, end;

    Frame(Point start, Point end)
        : start(start), end(end)
    {
    }

    friend ostream & operator<<(ostream & out, Frame const & step)
    {
        out << step.start << " -> " << step.end;
        return out;
    }
};

struct Result {
    vector<Frame> steps;
    unsigned short score;

    Result(vector<Frame> const & steps, unsigned short score)
        : steps(steps), score(score)
    {
    }

    friend ostream & operator<<(ostream & out, Result const & result)
    {
        for (auto const & step : result.steps)
            out << step << "\n";

        out << "Score: " << result.score;
        return out;
    }
};

auto sum(vector<reference_wrapper<Cell>> const & selection)
{
    return accumulate(selection.begin(), selection.end(), 0);
}

auto getWeight(vector<reference_wrapper<Cell>> const & selection)
{
    unsigned int weight = 0;

    for (Cell const & cell : selection)
        weight += cell.number << cell.number;

    return weight / selection.size();
}

class Grid {
private:
    vector<vector<Cell>> cells;
    unsigned short targetValue;
public:
    Grid(initializer_list<initializer_list<unsigned short>> list, unsigned short targetValue)
        : targetValue(targetValue)
    {
        for (auto const & inner : list) {
            vector<Cell> row;

            for (auto const &  number : inner)
                row.emplace_back(number);

            cells.push_back(row);
        }
    }
    Grid(initializer_list<initializer_list<unsigned short>> list)
        : Grid(list, 10)
    {
    }

    [[nodiscard]] auto size() const
    {
        return cells.size() * cells.at(0).size();
    }

    [[nodiscard]] auto startPoints() const
    {
        vector<Point> points;

        for (auto y = 0; y < cells.size(); y++)
            for (auto x = 0; x < cells.at(y).size(); x++)
                points.emplace_back(x, y);

        return points;
    }

    [[nodiscard]] auto endPoints(Point const & startPoint) const
    {
        vector<Point> points;

        for (auto y = startPoint.y; y < cells.size(); y++)
            for (auto x = startPoint.x; x < cells.at(y).size(); x++)
                points.emplace_back(x, y);

        return points;
    }

    [[nodiscard]] auto getFrames() const
    {
        vector<Frame> frames;

        for (auto const & start : startPoints())
            for (auto const & end : endPoints(start))
                frames.emplace_back(start, end);

        return frames;
    }

    auto getCells(Frame const & step)
    {
        vector<reference_wrapper<Cell>> selection;

        for (unsigned short y = step.start.y; y <= step.end.y; y++)
            for (unsigned short x = step.start.x; x <= step.end.x; x++)
                selection.emplace_back(cells.at(y).at(x));

        return selection;
    }

    [[nodiscard]] auto filterFrames(vector<Frame> const & frames)
    {
        vector<Frame> result;

        for (auto const & frame : frames)
            if (sum(getCells(frame)) == targetValue)
                result.push_back(frame);

        return result;
    }

    [[nodiscard]] unsigned short numbersLeft() const
    {
        unsigned short counter = 0;

        for (auto const & row : cells)
            for (auto const & cell : row)
                if (cell.number != 0)
                    counter++;

        return counter;
    }

    void sortFrames(vector<Frame> & frames)
    {
        sort(frames.begin(), frames.end(), [this] (Frame const & lhs, Frame const & rhs) {
            return getWeight(getCells(lhs)) > getWeight(getCells(rhs));
        });
    }

    bool reduceCells(vector<reference_wrapper<Cell>> const & selection)
    {
        if (sum(selection) == targetValue) {
            for (Cell & cell : selection)
                cell.number = 0;

            return true;
        }

        return false;
    }

    auto reduce(Frame const & frame)
    {
        return reduceCells(getCells(frame));
    }

    friend ostream & operator<<(ostream & out, Grid const & grid)
    {
        for (auto const & row : grid.cells) {
            for (auto const & cell : row)
                out << cell << " ";

            out << " \n";
        }

        return out;
    }
};

auto resolve(Grid & grid)
{
    vector<Frame> log, steps;

    while (true) {
        auto frames = grid.getFrames();
        auto candidates = grid.filterFrames(frames);

        if (candidates.empty())
            break;

        grid.sortFrames(candidates);
        auto candidate = candidates.at(0);

        if (grid.reduce(candidate))
            log.push_back(candidate);
    }

    return Result(log, grid.size() - grid.numbersLeft());
}

int main() {
    Grid grid1 = {
        {7, 8, 3, 8, 4, 4, 3, 1, 4, 5, 3, 2, 7, 7, 4, 6, 7},
        {6, 4, 3, 3, 3, 7, 1, 5, 1, 9, 2, 3, 4, 5, 5, 4, 6},
        {9, 7, 5, 5, 4, 2, 2, 9, 1, 9, 1, 1, 1, 7, 2, 2, 4},
        {3, 3, 7, 5, 5, 8, 9, 3, 6, 8, 5, 3, 5, 3, 2, 8, 7},
        {7, 3, 5, 8, 7, 8, 6, 3, 5, 6, 8, 9, 9, 9, 8, 5, 3},
        {5, 8, 3, 9, 9, 7, 6, 7, 3, 6, 9, 1, 6, 8, 3, 2, 5},
        {4, 9, 5, 7, 7, 5, 7, 8, 4, 4, 4, 2, 9, 8, 7, 3, 5},
        {8, 2, 1, 7, 9, 1, 7, 9, 6, 5, 4, 1, 3, 7, 6, 9, 6},
        {2, 3, 5, 6, 5, 6, 3, 9, 6, 6, 3, 6, 9, 7, 8, 8, 1},
        {1, 8, 5, 2, 2, 3, 1, 9, 3, 3, 3, 3, 7, 8, 7, 4, 8}
    };
    Grid grid2 ={
        {5, 4, 3, 6, 7, 2, 3, 5, 1, 2, 8, 6, 2, 3, 8, 1, 7},
        {3, 8, 7, 5, 4, 6, 6, 1, 6, 5, 7, 5, 4, 3, 8, 8, 1},
        {7, 9, 9, 3, 1, 7, 1, 8, 9, 1, 8, 4, 9, 8, 7, 1, 7},
        {5, 4, 6, 3, 1, 3, 1, 5, 4, 7, 4, 1, 5, 8, 1, 1, 5},
        {3, 3, 4, 3, 8, 7, 6, 5, 8, 6, 3, 2, 8, 4, 6, 6, 6},
        {7, 2, 2, 8, 9, 9, 7, 7, 7, 7, 3, 9, 1, 2, 7, 2, 4},
        {4, 1, 1, 5, 7, 7, 9, 2, 3, 6, 9, 2, 7, 5, 7, 7, 1},
        {9, 6, 7, 1, 7, 9, 8, 7, 3, 2, 8, 9, 8, 6, 1, 6, 8},
        {1, 3, 9, 6, 4, 5, 5, 3, 4, 9, 4, 1, 9, 2, 6, 9, 1},
        {6, 9, 6, 3, 1, 5, 8, 2, 3, 5, 4, 2, 6, 4, 5, 3, 5}
    };
    Grid grid3 = {
        {9, 2, 2, 7, 6, 6, 1, 7, 1, 9, 7, 6, 9, 3, 8, 8, 3},
        {2, 2, 4, 8, 6, 9, 8, 4, 8, 3, 8, 1, 1, 2, 7, 4, 9},
        {8, 5, 1, 8, 9, 5, 5, 1, 7, 7, 5, 1, 3, 4, 6, 5, 1},
        {5, 2, 9, 2, 2, 1, 7, 5, 4, 5, 9, 5, 6, 4, 2, 9, 7},
        {4, 9, 6, 3, 6, 2, 3, 9, 2, 1, 2, 8, 8, 7, 9, 4, 7},
        {1, 9, 7, 2, 2, 2, 6, 2, 1, 2, 5, 6, 2, 5, 6, 7, 8},
        {8, 8, 4, 4, 9, 5, 7, 2, 3, 8, 2, 4, 8, 1, 4, 7, 3},
        {9, 4, 7, 2, 3, 7, 2, 8, 4, 6, 9, 8, 3, 8, 5, 2, 9},
        {4, 8, 1, 3, 9, 1, 6, 6, 6, 7, 2, 1, 4, 5, 2, 6, 2},
        {3, 7, 3, 8, 1, 2, 1, 8, 1, 8, 3, 3, 2, 3, 2, 7, 4}
    };
    vector<reference_wrapper<Grid>> grids = {grid1, grid2, grid3};
    unsigned short gridNumber = 0;

    for (auto & grid : grids) {
        cout << "Grid #" << ++gridNumber << "\n";
        auto result = resolve(grid);
        cout << result << "\n";
        cout << grid << "\n";
    }
}

```

Try it online

The algorithm weighs the selections based on their amount of high numbers and size.

# Answer
> 2 votes
# Rust

Uses breadth-first beam search, with a heuristic evaluation based on greedily eliminating as many entries as possible while ignoring newly-created boxes. Solves each board in parallel. You can reduce `beam_size` in `solve` if you need to in order to meet the time budget (I know it should really be a command-line flag).

### `src/main.rs`

```
use fnv::FnvHashMap;
use rayon::prelude::*;

type Fruit = [[i16; 17]; 10];
type Rect = [u8; 4];
type ClearedMask = [u8; 22];

fn check_entry(mask: &ClearedMask, i: usize, j: usize) -> bool {
    let k = 17 * i + j;
    return (mask[k / 8] & (1 << (k % 8))) == 0
}

fn remove_entry(mask: &mut ClearedMask, i: usize, j: usize) {
    let k = 17 * i + j;
    mask[k / 8] |= 1 << (k % 8);
}

fn find_rects(output_rects: &mut Vec<(Rect, u8)>, mask: &ClearedMask, fruit: &Fruit, cum_sums: &mut [[i16; 18]; 11]) {
    for i in 0..11 {
        cum_sums[i][0] = 0;
    }
    for j in 0..18 {
        cum_sums[0][j] = 0;
    }
    for i in 0..10 {
        for j in 0..17 {
            cum_sums[i + 1][j + 1] = if check_entry(mask, i, j) {fruit[i][j]} else {0};
        }
    }
    for i in 0..10 {
        for j in 0..17 {
            cum_sums[i + 1][j + 1] += cum_sums[i][j + 1];
        }
    }
    let mut table = [0u16; 1530];
    for i0 in 0..10 {
        for i1 in i0..10 {
            let mut s = 0i16;
            let k = ((i0 << 4) | i1) as u16;
            for j1 in 0..17 {
                table[s as usize] = (k << 8) | (j1 as u16);
                unsafe {
                    s += cum_sums.get_unchecked(i1 + 1).get_unchecked(j1 + 1) -
                         cum_sums.get_unchecked(i0).get_unchecked(j1 + 1);
                }
                if s < 10 {
                    continue;
                }
                let j0 = unsafe {
                    *table.get_unchecked((s - 10) as usize) as usize
                };
                if (j0 >> 8) as u16 != k {
                    continue;
                }
                let j0 = j0 & 255;
                let r = [i0 as u8, j0 as u8, i1 as u8, j1 as u8];
                let mut a = 0;
                for i2 in i0..=i1 {
                    for j2 in j0..=j1 {
                        if check_entry(mask, i2, j2) {
                            a += 1;
                        }
                    }
                }
                output_rects.push((r, a))
            }
        }
    }
}

fn heuristic(rects: &Vec<(Rect, u8)>) -> u16 {
    let mut collision_info = Vec::with_capacity(rects.len());
    for _ in 0..rects.len() {
        collision_info.push((0u128, 0u16));
    }
    let mut s = 0;
    for idx0 in 0..rects.len() {
        let [_, j00, i10, j10] = rects[idx0].0;
        for idx1 in (idx0 + 1)..rects.len() {
            let [i01, j01, _, j11] = rects[idx1].0;
            if i01 > i10 {
                break;
            }
            if (j00 <= j11) & (j10 >= j01) {
                collision_info[idx0].0 |= 1 << idx1;
                collision_info[idx1].0 |= 1 << idx0;
                collision_info[idx0].1 += 1;
                collision_info[idx1].1 += 1;
            }
        }
    }
    let mut used = 0u128;
    let mut sort_idx: Vec<(u32, usize)> = (0..rects.len()).map(|i| (((collision_info[i].1 as u32) << 8) | (255 - rects[i].1) as u32, i)).collect();
    sort_idx.sort();
    for &(_, i) in sort_idx.iter() {
        if used & (1 << i) != 0 {
            continue;
        }
        used |= collision_info[i].0;
        s += rects[i].1 as u16;
    }
    return s;
}

fn solve(fruit: &Fruit) -> (Vec<Rect>, u16) {
    let mut cum_sums = [[0i16; 18]; 11];
    let mut output_rects = Vec::new();
    let mut heuristic_rects = Vec::new();
    let mut queue = Vec::new();
    let mut next_queue = Vec::new();
    let mut parent_map: FnvHashMap<ClearedMask, (ClearedMask, Rect)> = FnvHashMap::default();
    let rng = 18;
    queue.push((0, 0, rng, [0u8; 22]));
    let mut max_cleared = 0;
    let beam_size = 6500;
    let mut best_mask = [0u8; 22];
    while !queue.is_empty() {
        for (_, cleared, _, mask) in queue.iter() {
            find_rects(&mut output_rects, &mask, &fruit, &mut cum_sums);
            for (r, a) in output_rects.iter() {
                let mut mask1 = mask.clone();
                for i in r[0]..=r[2] {
                    for j in r[1]..=r[3] {
                        remove_entry(&mut mask1, i as usize, j as usize);
                    }
                }
                if parent_map.contains_key(&mask1) {
                    continue;
                }
                parent_map.insert(mask1, (*mask, *r));
                let cleared1 = cleared + (*a as u16);
                find_rects(&mut heuristic_rects, &mask1, &fruit, &mut cum_sums);
                let h = heuristic(&heuristic_rects);
                heuristic_rects.clear();
                next_queue.push((cleared1 + h, cleared1, rng, mask1));
                if cleared1 > max_cleared {
                    max_cleared = cleared1;
                    best_mask = mask1;
                }
            }
            output_rects.clear();
        }
        std::mem::swap(&mut queue, &mut next_queue);
        if queue.len() > beam_size {
            queue.sort_by(|p, q| q.cmp(p));
            queue.truncate(beam_size);
        }
        next_queue.clear();
    }
    let mut moves = Vec::new();
    let mut mask = best_mask;
    while let Some((parent_mask, r)) = parent_map.get(&mask) {
        moves.push(*r);
        mask = *parent_mask;
    }
    return (moves, max_cleared)
}

fn main() {
    let fruit0 = [
        [7, 8, 3, 8, 4, 4, 3, 1, 4, 5, 3, 2, 7, 7, 4, 6, 7],
        [6, 4, 3, 3, 3, 7, 1, 5, 1, 9, 2, 3, 4, 5, 5, 4, 6],
        [9, 7, 5, 5, 4, 2, 2, 9, 1, 9, 1, 1, 1, 7, 2, 2, 4],
        [3, 3, 7, 5, 5, 8, 9, 3, 6, 8, 5, 3, 5, 3, 2, 8, 7],
        [7, 3, 5, 8, 7, 8, 6, 3, 5, 6, 8, 9, 9, 9, 8, 5, 3],
        [5, 8, 3, 9, 9, 7, 6, 7, 3, 6, 9, 1, 6, 8, 3, 2, 5],
        [4, 9, 5, 7, 7, 5, 7, 8, 4, 4, 4, 2, 9, 8, 7, 3, 5],
        [8, 2, 1, 7, 9, 1, 7, 9, 6, 5, 4, 1, 3, 7, 6, 9, 6],
        [2, 3, 5, 6, 5, 6, 3, 9, 6, 6, 3, 6, 9, 7, 8, 8, 1],
        [1, 8, 5, 2, 2, 3, 1, 9, 3, 3, 3, 3, 7, 8, 7, 4, 8],
    ];
    let fruit1 = [
        [5, 4, 3, 6, 7, 2, 3, 5, 1, 2, 8, 6, 2, 3, 8, 1, 7],
        [3, 8, 7, 5, 4, 6, 6, 1, 6, 5, 7, 5, 4, 3, 8, 8, 1],
        [7, 9, 9, 3, 1, 7, 1, 8, 9, 1, 8, 4, 9, 8, 7, 1, 7],
        [5, 4, 6, 3, 1, 3, 1, 5, 4, 7, 4, 1, 5, 8, 1, 1, 5],
        [3, 3, 4, 3, 8, 7, 6, 5, 8, 6, 3, 2, 8, 4, 6, 6, 6],
        [7, 2, 2, 8, 9, 9, 7, 7, 7, 7, 3, 9, 1, 2, 7, 2, 4],
        [4, 1, 1, 5, 7, 7, 9, 2, 3, 6, 9, 2, 7, 5, 7, 7, 1],
        [9, 6, 7, 1, 7, 9, 8, 7, 3, 2, 8, 9, 8, 6, 1, 6, 8],
        [1, 3, 9, 6, 4, 5, 5, 3, 4, 9, 4, 1, 9, 2, 6, 9, 1],
        [6, 9, 6, 3, 1, 5, 8, 2, 3, 5, 4, 2, 6, 4, 5, 3, 5],
    ];
    let fruit2 = [
        [9, 2, 2, 7, 6, 6, 1, 7, 1, 9, 7, 6, 9, 3, 8, 8, 3],
        [2, 2, 4, 8, 6, 9, 8, 4, 8, 3, 8, 1, 1, 2, 7, 4, 9],
        [8, 5, 1, 8, 9, 5, 5, 1, 7, 7, 5, 1, 3, 4, 6, 5, 1],
        [5, 2, 9, 2, 2, 1, 7, 5, 4, 5, 9, 5, 6, 4, 2, 9, 7],
        [4, 9, 6, 3, 6, 2, 3, 9, 2, 1, 2, 8, 8, 7, 9, 4, 7],
        [1, 9, 7, 2, 2, 2, 6, 2, 1, 2, 5, 6, 2, 5, 6, 7, 8],
        [8, 8, 4, 4, 9, 5, 7, 2, 3, 8, 2, 4, 8, 1, 4, 7, 3],
        [9, 4, 7, 2, 3, 7, 2, 8, 4, 6, 9, 8, 3, 8, 5, 2, 9],
        [4, 8, 1, 3, 9, 1, 6, 6, 6, 7, 2, 1, 4, 5, 2, 6, 2],
        [3, 7, 3, 8, 1, 2, 1, 8, 1, 8, 3, 3, 2, 3, 2, 7, 4],
    ];
    let boards = [&fruit0, &fruit1, &fruit2];
    let results: Vec<(Vec<Rect>, u16)> = boards.into_par_iter().map(solve).collect();
    for (board_index, (fruit, (moves, score))) in boards.iter().zip(results.iter()).enumerate() {
        println!("Board {:?}: {:?} fruit cleared!\n\n", board_index, score);
        let mut mask1 = [0; 22];
        for r in moves.iter().rev() {
            for i in r[0]..=r[2] {
                for j in r[1]..=r[3] {
                    remove_entry(&mut mask1, i as usize, j as usize);
                }
            }
            println!("({:?}, {:?}), ({:?}, {:?})\n\n", r[0], r[1], r[2], r[3]);
            for i in 0..10 {
                for j in 0..17 {
                    let s = if check_entry(&mask1, i, j) {fruit[i][j]} else {0};
                    print!("{:?} ", s);
                }
                println!("");
            }
        }
    }
    println!("");
    for (board_index, (_, score)) in results.iter().enumerate() {
        println!("Board {:?}: {:?} fruit cleared!\n", board_index, score);
    }
}

```

### `Cargo.toml`

```
[package]
name = "fruitbox"
version = "0.1.0"
edition = "2018"

[dependencies]
rayon = "1.5.1"
fnv = "1.0.3"

```

---
Tags: code-challenge, array, grid, game, puzzle-solver
---


title: Identify a "reverse checkers" position

text:
# Question
Title: Identify a "reverse checkers" position
### Task

A *reverse checkers* position is a chess position where every piece for one player is on one colour and every piece for the other player is on the other colour. Your task is to find if the given (valid) position meets these criteria.

For example, this position does (click for larger images). Every white piece is on a light square, while every black piece is on a dark square:

This position is also a reverse checkers position. Every white piece is on a dark square, while every black piece is on a light square:

### Input

Your input will be a ***valid*** chess position. You choose whether it'll be a FEN (for the purpose of this challenge, we'll only consider the first field, piece placement), or an 8x8 grid (with spaces or not between). If the latter, mention in your answer what characters you used to denote empty squares and the pieces.

---

The examples below will use upper-case letters for white pieces and lower-case for black. Empty squares are represented by dots (`.`).

1. The first position above:

```
5r1k/2p3b1/1p1p1r2/p2PpBp1/P1P3Pp/qP1Q1P1P/4R1K1/7R

. . . . . r . k
. . p . . . b .
. p . p . r . .
p . . P p B p .
P . P . . . P p
q P . Q . P . P
. . . . R . K .
. . . . . . . R

```

*is* a reverse checkers position.
2. The second position above:

```
r3r3/5pBk/p3nPp1/1p1pP2p/2pPb1p1/P1P1N1P1/1P3R1P/R5K1

r...r...
.....pBk
p...nPp.
.p.pP..p
..pPb.p.
P.P.N.P.
.P...R.P
R.....K.

```

is a reverse checkers position as well.
3. The starting position:

```
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR

bbbbbbbb
bbbbbbbb
........
........
........
........
wwwwwwww
wwwwwwww

```

*is **not*** a reverse checkers position.

### Rules

* The chess position will *always* be valid.
* You may use two characters for the pieces, one for white pieces and one for black pieces (i.e. you don't have to use a different character for every piece).
* You can receive input through any of the standard IO methods.
* This is , so shortest code in bytes wins!

# Answer
# Jelly, 9 bytes

```
ŒJ§ḂṬƙFṀḊ

```

Try it online!

Takes input as an \\$8 \times 8\\$ matrix, with `0` being empty space, `1` being white and `2` being black. Outputs an empty list `[]` for truthy, and a non-empty list `[1]` for falsey.

Additionally, if we *really* want to stretch the output format, we can have this 8 byter

```
ŒJ§ḂṬƙFṀ

```

Try it online!

which outputs `[1]` for truthy, and `[1, 1]` for falsey.

## How it works

```
ŒJ§ḂṬƙFṀḊ - Main link. Takes a matrix M on the left
ŒJ        - 8x8 grid of coordinates [x, y] between 1 and 8
  §       - Sum of each coordinate
   Ḃ      - Bit
      F   - Flatten M
     ƙ    - Over the lists formed by grouping the flattened M by the bit of the coordinate:
    Ṭ     -   Yield a boolean list, with 1s at the indices in the list
       Ṁ  - Maximum
        Ḋ - Dequeue, remove the first element

```
> 6 votes

# Answer
# Python, 34 bytes

```
lambda p:{*p[::2]}<{*p}>{*p[1::2]}
```

Attempt This Online!

Accepts a single string. Works for any distinct 4 characters for empty,black,white,newline.

### How?

Uses the fact that including the linebreak lines have odd length, hence going over the entire string skipping every other character separates black and white squares. Both subsets must contain newlines and empty squares (we can't legally put all 32 initial pieces on the same colour squares because of the bishops). Iff there are pieces of both players on the same kind of square that subset will be the full set and the corresponding inequality fail.

#### Old Python, 40 bytes

```
lambda p:{*p[::2]}<{*"bw.\n"}>{*p[1::2]}
```

Attempt This Online!

Accepts a single string. ".bw\n" for empty,black,white,newline.

#### Wrong Python, 36 bytes

```
lambda p:len({*p[::2]}&{*p[1::2]})<3
```

Attempt This Online!

Accepts a single string. Works for any distinct 4 characters for empty,black,white,newline.
> 16 votes

# Answer
# , ~~68~~ ~~50~~ 40 bytes

```
function(x)sd((z=rbind(x,0)*.5:-1)[!!z])

```

Try it online!

Input is 8x8 matrix with `1`s and `-1`s representing black and white pieces (or the other way around), and `0`s representing empty positions. Outputs zero (falsy) for not-reverse-checkers positions, non-zero (truthy) for reverse-checkers positions (or +2 bytes for single-character input `0`, `2` & `1` as black, white & empty).

Multiplies black squares by `-0.5` and white squares by `0.5`, and then uses the standard deviation (`sd`) to check if all the resulting nonzero `[!!z]` values are the same (in which case the standard deviation is zero). In many challenges, the `sd` approach could fail for inputs with zero or one items (which would yield a standard deviation of `NA`), but luckily this can't happen here for a valid chess position.
> 7 votes

# Answer
# , 23 22 21 16 15 bytes

```
6 e.]*.//.~2|#\

```

Try it online!

Test cases taken from caird's Jelly answer

*Input:* Single list with space & newline = 1, black = 2, white = 3.

*Output:* 0 for valid, 1 for invalid.

## how

* `2|#\` Creates list `1 0 1 0 1 0 ...`  to length of input.
* `]*.//.~` Partitions input according to that, taking LCM of each partition. Only an invalid board will have a partition containing both `2` and `3`, and hence an LCM of `42`.
* `6 e.` Is `6` an element of that? Only possible on invalid boards.
> 3 votes

# Answer
# Factor, 43 bytes

```
[ 2 group unzip [ cardinality 3 = ] both? ]

```

Try it online!

Takes input as a string with any three distinct values representing black pieces, white pieces, and empty spaces and relies on the trick from @loopy walt's Python answer: namely, that because of newlines, even and odd indices of the string correspond to black and white squares. However, all we need to do is check if the cardinality of both groups is three.
> 3 votes

# Answer
# JavaScript (Node.js), 66 bytes

```
a=>a.map(t=r=>r.map(c=>t|=5+(g=-g)*(c>{}?-1:c>'@'),g=-g),g=3)^15^t

```

Try it online!

Input 2d array of characters in `rnbqpRNBQP.`. Output truthy vs falsy. 52 bytes if input as 2d array of `+1, 0, -1`.
> 2 votes

# Answer
# Python3, 245 bytes:

```
lambda b:g({(x,y):b[x][y]for x in r(8)for y in r(8)})
r=range
g=lambda p:len(set(w:=[(x%2==0 and y%2==0)or(x%2 and y%2)for x,y in p if p[(x,y)]==1]))==1 and len(set(b:=[(x%2==0 and y%2==0)or(x%2 and y%2)for x,y in p if p[(x,y)]==0]))==1 and w!=b

```

Try it online!
> 1 votes

# Answer
# Pari/GP, 50 bytes

```
a->sum(n=0,1,!matrix(8,,i,j,(i+j+n+t=a[i,j])%2*t))

```

Try it online!

Takes input as an 8x8 matrix of `0`s (empty), `1`s (black), `2`s (white).
> 1 votes

# Answer
# Perl 5, 48 bytes

```
y,/2468,1,d;$_=/^(([w\d][b\d])+|([b\d][w\d])+)$/

```

Try it online!

Takes preprosessed FEN-input: blacks becomes `b` and whites `w`. Deletes 2, 4, 6 and 8 empty squares since they don't change the result, odd empties 1, 3, 5 and 7 are treated as 1 (no difference in result). Flattens the board so the newlines `/` become one invisible empty square. The regex tests if all 36 pairs (9x8/2) of the flattened board consist of either white|empty then black|empty or the opposite. Returns `1` for truthy and `""` (empty string) for falsey.
> 1 votes

# Answer
# Retina 0.8.2, ~~35~~ 32 bytes

```
T`L`0
T`l`1
s`(\d).(..)*(?!\1)\d

```

Try it online! Takes input as a board but link is to test suite which converts from FEN to a compatible board, so if you want to test board input then delete the contents of the header first. Outputs `0` for a reverse draughts position and non-zero if not (+1 byte to always output `1`). Explanation: Maps pieces to `0` or `1` depending on their colour (-12 bytes for a custom input format) and then checks whether opposite colour pieces are on two squares of the same colour.
> 0 votes

# Answer
# Charcoal, 32 bytes

```
Ｆ²⊞υ⟦⟧Ｆ⁸ＵＭＳ⊞Ｏ§υ⁺ιλ⁻№ακ№βκ⊙υ×⌈ι⌊ι

```

Try it online! Takes input as a board and outputs nothing for a reverse draughts position and `-` if not. Explanation:

```
Ｆ²⊞υ⟦⟧

```

Start collecting the colour of pieces on squares of each colour.

```
Ｆ⁸

```

Loop over the rows.

```
ＵＭＳ⊞Ｏ§υ⁺ιλ⁻№ακ№βκ

```

Push `1`, `0`, or `-1` to the appropriate square colour list depending on the colour of the piece or `0` if there is no piece.

```
⊙υ×⌈ι⌊ι

```

See whether any square colours contain pieces of both colours. Since there can only be 15 pieces of the same colour on squares of one colour, there will be at least one zero in the array, but this will not be the minimum or the maximum if this is not a reverse draughts position.
> 0 votes

---
Tags: code-golf, decision-problem, grid, chess
---


title: How far should I sum?

text:
# Question
Title: How far should I sum?
The *harmonic series* is the "infinite sum" of all the fractions of the form \\$\frac1n\\$ for \\$n\\$ positive integer. I.e. the harmonic series is

$$\frac11 + \frac12 + \frac13 + \frac14 + \cdots$$

It is well-known that this sum diverges, which means that if you define

$$ H\_n = \frac11 + \frac12 + \cdots + \frac1n$$

Then the value of \\$H\_n\\$ goes to infinity. This can also be stated in a different way: for any positive value \\$x\\$ you pick, there is some value \\$N\\$ such that, to the right of \\$N\\$, the \\$H\\$ values are bigger than \\$x\\$:

$$\forall\ x\ \exists\ N: n \> N \implies H\_n \> x $$

# Your task

Write a program/function that takes as input a positive number `x` (not necessarily an integer) and outputs the first integer `n` for which

$$H\_n \geq x$$

In theory your program must work for arbitrary `x`, even if in practice you are limited by the memory and/or precision of your programming language/computer.

# Test cases

```
1.5 -> 2
2 -> 4
3 -> 11
3.1415 -> 13
4 -> 31
5 -> 83
7.5 -> 1015
10 -> 12367

```

This is so shortest solution wins! Standard loopholes are forbidden by default. Happy golfing.

# Answer
# APL (Dyalog), 13 bytes

*-1 bytes thanks to ngn*

```
{⊃⍸⍵≤+\÷⍳⌈*⍵}

```

Try it online!

A dfn solution that takes a right argument.

### Explanation:

```
{           }   ⍝ dfn
 ⊃              ⍝ Take the first of
  ⍸             ⍝ The indexes of the truthy values of
   ⍵≤           ⍝ The right argument is smaller than or equal to
     \+         ⍝ The cumulative sum
       ÷        ⍝ The reciprocal of each of
        ⍳       ⍝ The range 1 to
         ⌈      ⍝ The ceiling of
          *⍵    ⍝ e to the power of the right argument

```
> 7 votes

# Answer
# Python 3, 35 bytes

```
f=lambda x,n=1:x>0and-~f(x-1/n,n+1)

```

Try it online!
> 7 votes

# Answer
# JavaScript (ES6),  ~~32~~  29 bytes

*Saved 3 bytes thanks to @Shaggy*

```
f=(n,k=0)=>n>0?f(n-1/++k,k):k

```

Try it online!

---

# Non-recursive version, 35 bytes

```
n=>eval("for(k=0;(n-=1/++k)>0;);k")

```

Try it online!

---

### Approximation (25 bytes, not fully working)

This gives the correct result for all but the first test case.

```
n=>Math.exp(n-.5772)+.5|0

```

Try it online!
> 6 votes

# Answer
# Perl 6, 27 bytes

```
{+([\+](1 X/1..*)...*>=$_)}

```

Try it online!

### Explanation:

```
{                         } # Anonymous code block taking one argument
 +(                      )  # Return the length of
   [\+](        )             # The cumulative sum
        1 X/                    # Of the reciprocal of all of
            1..*                  # 1 to infinity
                 ...          # Take from this until
                    *>=$_     # It is larger than or equal to the input

```
> 6 votes

# Answer
# 05AB1E, 8 bytes

```
∞.ΔLzOI@

```

Try it online!

```
∞.Δ        # first integer y such that:
   L       #  range [1..y]
    z      #  invert each [1, 1/2, .., 1/y]
     O     #  sum
      I@   #  >= input

```
> 5 votes

# Answer
# Octave / MATLAB, 31 bytes

*Thanks to @Giuseppe (based on @John's answer) for making a correction and saving 1 byte at the same time.*

```
@(n)sum(cumsum(1./(1:3^n))<n)+1

```

**Try it online!**

### Explanation

The code uses the fact that `1+1/2+···+1/m` is lower-bounded by `log(m)`. Therefore, given `n` the solution to the challenge is less than `exp(n)`, or less than `3^n` (to save bytes).

So the code computes the cumulative sum of the vector `[1, 1/2, 1/3, ..., 1/(3^n)]`, and the solution is `1` plus the number of entries that are less than `n`.
> 5 votes

# Answer
# , ~~39~~ 33 bytes

```
x=scan();sum(cumsum(1/1:x^x)<x)+1

```

Try it online!

For a more limited x:

# 29 bytes

```
sum(cumsum(1/1:9^8)<scan())+1

```

Try it online!
> 5 votes

# Answer
# Wolfram Language (Mathematica), 29 bytes

```
(i=0;#//.x_/;x>0:>x-1/++i;i)&

```

Try it online!
> 5 votes

# Answer
# C (gcc), 45 bytes

*Some inspiration taken from @Noodle9; go upvote their answer!*

```
i;g(x,s)float x,s;{for(s=i=0;s<x;s+=1./++i);}

```
* `i;g(x,s)float x,s;`: Old-style function definition. Abuses the fact that old-style function definition don't require all the arguments to be passed (so old-style variadic functions would work) to declare an extra local variable. Having the `i` as a global variable causes the exploit below to work.
* `for(s=i=0;s<x;s+=1./++i);`: same old stuff as before, harmonic function, yada yada. Note that `s=i=0` is allowed; the `i=0` is an integer that is converted to a `float` and assigned to `s`.
* The `i` variable is stored in the `%eax` (return) register, so nothing is required to initialize it. (thanks @Cody Gray!)

Try it online!

# C (gcc), 72 bytes

Recursive solution.

```
i;float h(n){return n?h(n-1)+1./n:0;}g(float x){for(i=0;h(i++)<x;);--i;}

```

Explanation:

* `i;`: counter for finding the first integer `n` where `h(n) >= x`.
* `float h(n)`: recursive function taking an `int` parameter and returning the term of the Harmonic series for `n`.
* `return n?h(n-1)+1./n:0;` \- recursive function calculating the Harmonic series and stopping at `0`.
* `g(float x)`: function finding the first `i` where `h(i) >= x`.
* `for(i=0;`: start loop and initialize `i` to `0` (functions must be reusable).
* `h(i++)<x`: loop while `h(i) < x`.
* `--i;` returns `i-1` by exploiting GCC's behavior when compiling without optimization; intermediate results are all stored in the `eax`/`rax` register.

Try it online!

# C (gcc), 83 bytes

Non-recursive solution.

```
i;float h(n){float r=0;for(;n;)r+=1./n--;r=r++;}g(float x){for(i=0;h(i++)<x;);--i;}

```

Explaining the part that's different from the previous solution:

* `float r=0;`: this is our result. Initialize it to `0`.
* `for(;n;)`: Loop until `n` is `0`.
* `r+=1./n--;`: Add the next iteration of the Harmonic series. Also decrement `n` so we don't have to do that in the last part of the `for` loop.
* `r=r++;` is like `return n;` but shorter. It's similar to the fake `return` in the previous solution but does it with the floating-point return register instead of the integer return register. We have to have the `++` just so GCC doesn't optimize it out as redundant (and yes, some optimizations are enabled without a flag).

Try it online!
> 4 votes

# Answer
# C (gcc), ~~52~~ ~~51~~ 49 bytes

Saved a bytes thanks to @ceilingcat!!!
Saved 2 bytes thanks to @S.S.Anne!!!

```
i;f(n,s)float n,s;{for(s=i=0;s<n;s+=1./++i);n=i;}

```

Try it online!
> 4 votes

# Answer
# Python 3, ~~49~~ 40 bytes

Saved 9 bytes thanks to @JoKing!!!

```
lambda n,s=0,i=1:s<n and-~f(n,s+1/i,i+1)

```

Try it online!
> 4 votes

# Answer
# Ruby, ~~31~~ 30 bytes

```
->x{b=0;x-=1r/b+=1while x>0;b}

```

Try it online!
> 4 votes

# Answer
# K (Kona), ~~21~~ 20 bytes

```
{1+*&~x>+\1.%1+!3^x}

```

Try it online!

Inspired by Jo King's APL solution

Switched from oK to Kona, as it has `power`
> 4 votes

# Answer
# Jelly, 9 bytes

```
1İ€S<¬ʋ1#

```

A monadic Link accepting a number which yields a list containing one integer; as a full program it prints that integer.

**Try it online!**

### How?

```
1İ€S<¬ʋ1# - Link: number, x
1         - set left to one
       1# - count up (from n=left) finding the first (1) n such that:
      ʋ   -   last four links as a dyad - f(n, x)
 İ€       -     inverse each (of [1..n])
   S      -     sum
    <     -     less than (x)?
     ¬    -     logical NOT

```

---

```
‘!İ€Ä<⁸S‘

```

Is another 9 but it's much less efficient as \\$x\\$ gets bigger since it builds a list of the first \\$(x+1)!\\$ harmonic numbers.
> 3 votes

# Answer
# Haskell, 34 bytes

```
(#1)
x#n|x>0=(x-1/n)#(n+1)|1>0=n-1

```

Try it online!
> 3 votes

# Answer
# Java 8, ~~71~~ 43 bytes

```
x->{int n=0;for(;(x-=1d/++n)>0;);return n;}

```

-28 bytes by porting *@Arnauld*'s non-recursive JavaScript answer.

Try it online.

**Explanation:**

```
x->{                // Method with double as both parameter and integer as return-type
  int n=0;          //  Result-integer `n`, starting at 0
  for(;(x-=1d/++n)  //  Decrease `x` by 1/(n+1), by first increasing `n` by 1 with `++n`
       >0;);        //  And continue doing this until `x` is 0
  return n;}        //  Then return `n` as result

```
> 3 votes

# Answer
# Pyth, 11 10 9 bytes

```
fgZ=-Qc1T

```

Try it online!

Explaination:

```
            # Implicit Q=eval(input())
f           # The first element T of [1,2,3,...] where
 gZ         # 0 >=
   =-Qc1T   # Q = Q - (1/T)
            # Implicit print

```

-1 -2 bytes thanks to @issacg
> 3 votes

# Answer
# GolfScript, 21 20 \[bytes\]

New Solution TIO
Old Solution TIO

The new solution takes our input and recursively subtracts the inverses from it until we get the solution. Very messy stack management, could probably be done cleaner.

### New Solution (20)

```
0{).-1?@\-.@\0>}do\;

```

### New Solution Explanation

```
0{).-1?@\-.@\0>}do\; #Take in a number c as input, and output the lowest n s.t. Hn<x
0                    # The stack is now [c n=0]. We're just using n here for clarity.
 {             }do   # Until we pop a TRUE, loop the following
 {)            }do   # Increment n by 1
 {  .           }do   # Then duplicate it
 {  -1?        }do   # Raise the dupe to the power of 1 (inverse)
 {     @\      }do   # Move our c to the second element of the stack, between n and 1/n
 {       -     }do   # Subtract. Stack is now [n c-(1/n)]
 {        .    }do   # Duplicate c-(1/n)
 {         @\  }do   # Move n back to the second element of the stack
 {           0>}do   # Check if our c-(1/n) is less than zero. If so, leave the loop.
 {             }do   # If not, repeat, but with c-(1/n) as our new c.
                  \; # Remove c once it's below 0, leaving our tally. This gets outputted.

```

### Old Solution (21)

```
:c;0.{\).-1?@+.c<}do;

```

### Old Solution Explanation

```
:c;0.{\).-1?@+.c<}do; # Take in a number c and find the lowest n s.t. Hn>c
:c;                   # Set c to our goal number, then pop it from our stack.
   0.                 # Make our stack [0 0]. Let will be our n, right will be our running sum.
     {           }do  # At the end of each loop, if the top of the stack isn't 0, repeat.
     {\)         }do  # Move the n to the top of the stack and increment it by 1.
     {  .-1?     }do  # Duplicate it, then inverse it.
     {      @    }do  # Bring our running total to the top (now third in the stack behind 1/n and n)
     {       +   }do  # Add the top two elements (running total + 1/n)
     {        .  }do  # Duplicate the running total
     {         c<}do  # If it's less than c, print 1 (repeat do), else 0 (stop do)
                    ; # Pop our running total, leaving behind just our n.

```

Shouldn't be too hard to shave a char off somewhere.

Got one.
> 3 votes

# Answer
# Burlesque, 27 bytes

```
rds1@1moiT{1j?/g1++cm0>=}fi

```

Try it online!

For some reason save/load seems to be working a bit funny with this one on TIO. To test the code, use the following:

# Burlesque, 28 bytes

```
rd@1moiT{1j?/++cm0>=}x/4iafi

```

Try it online!

```
rd    # Read input as double
[s1]  # Save slot 1
@1    # 1.0
mo    # Infinite multiples of {1.0, 2.0, 3.0...}
iT    # All tails of {{}, {1.0}, {1.0,2.0}, {1.0,2.0,3.0},...}}
{
 1j?/ # Reciprocal
 ++   # Sum
 [g1] # Get slot 1 (not working)
 cm   # UFO operator (-1 on <, 0 on ==, 1 on >)
 -1.> # 0 or 1
}
x/   # Reorder stack
3ia  # Insert input at position 3 of array (before compare)
fi   # Find first index

```
> 2 votes

# Answer
# Japt, ~~12~~ ~~11~~ 10 bytes

```
>0©ÒßUÉ/°T

```

Try it
> 2 votes

# Answer
# Red, 53 bytes

```
f: func[n][i: 0 until[0 >= n: n -(1.0 /(i: i + 1))]i]

```

Try it online!

Simple iterative solution.

# Red, 78 bytes

```
f: func[n /a i][either a[either n > 0[f/a n -(1.0 / i)i + 1][i - 1]][f/a n 1]]

```

Try it online!

I know this is way longer than other recursive solutions, but I wanted to post it because of the fact that Red functions have fixed arity. In order to simulate default values for the additional parameters, we need to use a `refinement` \- here it's `/a`\- whenever we need the value of the `i` parameter.
> 2 votes

# Answer
# , 29 28 bytes

*-1 byte thanks to RGS*

Shameless translation of Jo King's APL answer.

```
3 :'>:1 i.~y&<:+/\%}.i.<.^y'

```

Probably a lot of room for improvement, but I couldn't find a shorter tacit way.

Try it online!
> 2 votes

# Answer
# bc, 52 bytes

```
define f(x){
scale=999
for(s=i=0;s<x;s=s+1/i)i=i+1
}

```

Try it online!

If you need more precision, change the 999 to 9E3 or 9E9. Expect memory usage to skyrocket and performance to plummet.

I'm testing a variant that prints as it passes integers. It matches OEIS A004080 so far (23 -\> 5471312310). With scale=9, it is correct to 11 -\> 33617 but is off by 4 for 12. With scale=99, it is so far accurate to 25 -\> 40427833596. Since scale=99 can't be extended without adding another byte, I'm not going to claim it.
> 2 votes

# Answer
## `d`, ~~11~~ 9 bytes

```
╪ª4PÄ½┌∙×

```

Uncompressed:

```
i1ak/+rb<!W

```

## Explanation

```
i         W % Find the first number from 1 to positive infinity
            % That satisfies this condition
  ak        % Generate a range from 1 to the number
 1  /       % Find the reciprocal of every item (automatically vectorises)
     +r     % Reduce by addition
       b<!  % Is this number greater than or equal to the input?

```
> 2 votes

# Answer
## `d`, 8 bytes

Let's see if I can come tied with 05AB1E ...

```
♠wⁿ=^φ→§

```

Uncompressed:

```
kJrJb<!iX

```

Explanation

```
       iX % Foreach in [1 .. +inf],
          % find first number that satisfies:
k         % Range of 1 .. number
 Jr       % Reciprocal each
   J      % Summation of entire list
    b<!   % Is that >= the input?

```
> 2 votes

# Answer
# Charcoal, 19 bytes

```
⊞υ¹Ｗ‹ΣυＩθ⊞υ∕¹⊕ＬυＩＬυ

```

Try it online! Link is to verbose version of code. Explanation:

```
⊞υ¹

```

Start off with `n=1`, pushing `1/1` to the predefined list.

```
Ｗ‹ΣυＩθ

```

Repeat while the list sums to less than the target...

```
⊞υ∕¹⊕Ｌυ

```

... push the next Egyptian fraction to the list.

```
ＩＬυ

```

Output the length of the list, i.e. `n`.

It might be possible to reduce the floating-point inaccuracy slightly by adding a `Reverse` after the `Sum`.
> 1 votes

# Answer
# Keg, `-hr`, 12 bytes

```
0&0{¿⑻>|:⑨⑱⑼

```

Uses the most recent Keg interpreter, so no TIO thus far.

## Explained

```
0&

```

We store `0` in the register as this will be the means of storing the total sum of the series.

```
0

```

We then push `0` onto the stack, as this will be what keeps track of the term number (`n`)

```
{¿⑻>|

```

The condition of the while loop is that it will repeat while the input (which is automatically filled if no input is given -- the reason why this doesn't have a TIO link) is greater than the value in the register.

We then increment the top of the stack to get to the next term. This is done before the reciprocal is taken so that we avoid an "off-by-one" error.

```
:⑱⑼

```

We then take the reciprocal of the top of the stack and add it to the register ( = `1/x` and  = `register += t.o.s`). `-hr` will automatically print the top of the stack at end of execution as an integer.

Here is a Try it online version that uses a variable to keep track of the input. This is mainly just so that y'all can see that the algorithm works, as the variables can be replaced with the above 12 byter.
> 1 votes

# Answer
# Scratch 3.0, 15 blocks / 127 bytes

```
when gf clicked
ask()and wait
set[n v]to(0
set[t v]to(0
repeat until<(t)>(answer
change[n v]by(1
change[t v]by((1)/(n
end
say(n

```

Just a port of my Keg answer, so Try it on~~line~~ Scratch!
> 1 votes

# Answer
# Julia 1.0, ~~27~~ 24 bytes

```
>(x,i=1)=1+(0<x-1/i>i+1)

```

Try it online!

-3 bytes thanks to H.PWiz

the same approach as xnor
> 1 votes

# Answer
# Python 3, 39 bytes

```
lambda n:sum(1/x for x in range(1,n+1))

```

Try it online!

Pretty simple.
> 1 votes

# Answer
# Perl 5 `-p`, 22 bytes

```
$i+=1/++$\while$_>$i}{

```

Try it online!
> 0 votes

---
Tags: code-golf, math, floating-point
---