title: Factoring a 64-bit integer

text:
# Question
Title: Factoring a 64-bit integer
Write a *GOLF* assembly program that reads an integer from stdin (followed by a trailing newline), and outputs its prime factors seperated by newlines, followed by a trailing newline on stdout.

The prime factors need not be in a particular order. `1` is not a prime factor.

**Your *GOLF* binary (after assembling) must fit in 8192 bytes.**

---

Your program will be scored by running it 10 times, each with one of the following inputs:

```
8831269065180497
2843901546547359024
6111061272747645669
11554045868611683619
6764921230558061729
16870180535862877896
3778974635503891117
204667546124958269
16927447722109721827
9929766466606501253

```

These numbers are roughly sorted in terms of difficulty. The first one should easily be solvable by trial division.

Optimization towards this set of numbers is against the spirit of the question, I may change the set of numbers at any point. Your program must work for any positive 64-bit input number, not just these.

### Your score is the sum of CPU cycles used to factor the above numbers.

---

Because *GOLF* is very new I'll include some pointers here. You should read the *GOLF* specification with all instructions and cycle costs. In the Github repository example programs can be found. In particular look at the factorial example program, which demonstrates input/output.

Compile your program to a binary by running `python3 assemble.py your_source.golf`. Then run your program using `python3 golf.py your_source.bin`, this should print the cycle count as well. See the values of the register contents at program exit with the `-d` flag - use `--help` to see all flags.

# Answer
> 3 votes
# 2,279,635 cycles—7373 bytes (deterministic)

One-by-one:

```
robert@unity:~/golf-cpu/factor$ ./test.sh
13
23
31
37
41
47
47
59
61
79
Execution terminated after 1088 cycles with exit code 0.
2
2
2
2
3
3
107
164546579
1121707
Execution terminated after 41325 cycles with exit code 0.
3
3
3
7
7
7
13
50759273983933
Execution terminated after 9413 cycles with exit code 0.
7
7
7
13
250250521
2531
4091
Execution terminated after 22282 cycles with exit code 0.
31
89
97
357653
3881
18211
Execution terminated after 47656 cycles with exit code 0.
2
2
2
3
702924188994286579
Execution terminated after 17423 cycles with exit code 0.
7
103
7209485975851
727
Execution terminated after 15973 cycles with exit code 0.
1920043
66449
1604167
Execution terminated after 153683 cycles with exit code 0.
52528036667
322255481
Execution terminated after 1952229 cycles with exit code 0.
9929766466606501253
Execution terminated after 18563 cycles with exit code 0.
robert@unity:~/golf-cpu/factor$

```

Summary:

```
robert@unity:~/golf-cpu/factor$ ./test.py factor.golf factors_testset
binary length: 7373 bytes
10/10 passed in 0:00:08.53 s
2,279,635 cycles (227963.50 average)
(267.14 KCPS average)

       0 ######################################################################
  100000 ########
  200000
  300000
  400000
  500000
  600000
  700000
  800000
  900000
 1000000
 1100000
 1200000
 1300000
 1400000
 1500000
 1600000
 1700000
 1800000
 1900000 ########
robert@unity:~/golf-cpu/factor$

```

I use a combination of trial division and the Brent-Pollard rho algorithm for factorization, and table lookup plus Miller-Rabin for primality testing. I'll add some more explanation tomorrow.

Note that because of the character limit on post length, the second data table is truncated. This gist includes the full table.

```
primes_53 = \
  b'\x03\x05\x07\x0b\x0d\x11\x13\x17\x1d\x1f\x25\x29\x2b\x2f\x35\x3b' \
  b'\x3d\x43\x47\x49\x4f\x53\x59\x61\x65\x67\x6b\x6d\x71\x7f\x83\x89' \
  b'\x8b\x95\x97\x9d\xa3\xa7\xad\xb3\xb5\xbf\xc1\xc5\xc7\xd3\xdf\xe3' \
  b'\xe5\xe9\xef\xf1\xfb'

# for 2**16+1:2:2**17-1, 1 if prime, 0 otherwise
prime_bytes = \
  b'\x8b\x24\x60\x82\x10\x41\x81\x12\x40\x08\x26\x0d\x03\x00\x01\x41' \
  ...
  b'\x41\x30\x20\x10\x00\x00\x80\x00\x40\x50\x24\x00\x83\x00\x01\x8a'

main:
  call input

# check if input is 1
  cmp c, n, 1
  sz c, 3
    mov o, n
    call print
    halt 0

# remove factors of two
  mov o, 2
  div_2_loop:
    and c, n, 1
    snz c, 3
      call print
      shr n, n, 1
      jmp div_2_loop

# check if n is a power of two
  cmp c, n, 1
  sz c, 1
    halt 0

# trial division
  mov d, data(primes_53)
  mov i, 53

  trial_division_loop:
    lbu p, d
    trial_division_check:
      divu q, r, n, p
      snz r, 4
        mov o, p
        call print
        mov n, q
        jmp trial_division_check
    mulu s, t, p, p
    leu c, n, s
    sz c, 5
      cmp c, n, 1
      snz c, 2
        mov o, n
        call print
      halt 0
    sub i, i, 1
    add d, d, 1
    jnz trial_division_loop, i

  # mov g, 0  # initialize factor list pointers
  # mov h, 0  # all registers are zero at program start

  # *g is the next factor to check for primality
  # *h is the last factor we've found so far
  # the first factor is always *0

  sw g, n

prime_test:

  # by this point we know that n has no prime factors less than 256,
  # so if n is less than 256**2, then it must be prime
  lequ c, n, 2**16
  jnz is_prime, c

  geu c, n, 2**17+1
  jnz miller_rabin, c

  sub d, n, 2**16+1  # table starts at 2**16+1 (by above argument)
  shr d, d, 1  # we know n is odd, so we ignore the last bit
  and m, d, 2**3-1  # each byte is 3-bit lookup table
  shr d, d, 3
  add d, d, data(prime_bytes)
  lbu p, d
  shr p, p, m
  and p, p, 1
  jnz is_prime, p

  jmp pollard_rho  # I should probably do trial division here
                   # since we only have around 20 more primes to check

################
# Miller-Rabin primality test; bases from https://miller-rabin.appspot.com/
# Note that this subroutine, as well as most of the ones before the 'utility
# functions' section are not proper functions, as they sometimes jump directly
# to the next step instead of returning!
#
# input: n
# output: n/a
################
miller_rabin:
  shr d, n, 1
  mov b, 1
  mr_rd_loop:  # n - 1 == d * 2**b, d is odd
    and c, d, 1
    snz c, 3
      shr d, d, 1
      inc b
      jmp mr_rd_loop

  geu c, n, 2**32-1  # test if we can use single-precision arithmetic
  jnz miller_rabin_montgomery, c

  sub m, n, 1

  mr_test_1:
    gequ c, n, 0x000000000005361b
    jnz mr_test_2, c

    mov a, 0x81b33f22efdceaa9
    call miller_rabin_test

    jmp is_prime

  mr_test_2:
    gequ c, n, 0x000000003e9de64d
    jnz mr_test_3, c

    mov a, 0x0000004e69b6552d
    call miller_rabin_test

    mov a, 0x00223f5bb83fc553
    call miller_rabin_test

    jmp is_prime

  mr_test_3:
    mov a, 0x3ab4f88ff0cc7c80
    call miller_rabin_test

    mov a, 0xcbee4cdf120c10aa
    call miller_rabin_test

    mov a, 0xe6f1343b0edca8e7
    call miller_rabin_test

    jmp is_prime

miller_rabin_montgomery:
  call montgomery_precompute
  sub m, n, r  # montgomery representation of n-1

  mr_test_mt_3:
    gequ c, n, 0x000000518dafbfd1
    jnz mr_test_mt_4, c

    mov a, 0x3ab4f88ff0cc7c80
    call miller_rabin_test_montgomery

    mov a, 0xcbee4cdf120c10aa
    call miller_rabin_test_montgomery

    mov a, 0xe6f1343b0edca8e7
    call miller_rabin_test_montgomery

    jmp is_prime

  mr_test_mt_4:
    gequ c, n, 0x0000323ee0e55e6b
    jnz mr_test_mt_5, c

    mov a, 0x0000000000000002
    call miller_rabin_test_montgomery

    mov a, 0x0000810c207b08bf
    call miller_rabin_test_montgomery

    mov a, 0x10a42595b01d3765
    call miller_rabin_test_montgomery

    mov a, 0x99fd2b545eab5322
    call miller_rabin_test_montgomery

    jmp is_prime

  mr_test_mt_5:
    gequ c, n, 0x001c6b470864f683
    jnz mr_test_mt_6, c

    mov a, 0x0000000000000002
    call miller_rabin_test_montgomery

    mov a, 0x000003c1c7396f6d
    call miller_rabin_test_montgomery

    mov a, 0x02142e2e3f22de5c
    call miller_rabin_test_montgomery

    mov a, 0x0297105b6b7b29dd
    call miller_rabin_test_montgomery

    mov a, 0x370eb221a5f176dd
    call miller_rabin_test_montgomery

    jmp is_prime

  mr_test_mt_6:
    gequ c, n, 0x081f23f390affe89
    jnz mr_test_mt_7, c

    mov a, 0x0000000000000002
    call miller_rabin_test_montgomery

    mov a, 0x000070722e8f5cd0
    call miller_rabin_test_montgomery

    mov a, 0x0020cd6bd5ace2d1
    call miller_rabin_test_montgomery

    mov a, 0x009bbc940c751630
    call miller_rabin_test_montgomery

    mov a, 0x0a90404784bfcb4d
    call miller_rabin_test_montgomery

    mov a, 0x1189b3f265c2b0c7
    call miller_rabin_test_montgomery

    jmp is_prime

  mr_test_mt_7:
    mov a, 0x0000000000000002
    call miller_rabin_test_montgomery

    mov a, 0x0000000000000145
    call miller_rabin_test_montgomery

    mov a, 0x000000000000249f
    call miller_rabin_test_montgomery

    mov a, 0x0000000000006e12
    call miller_rabin_test_montgomery

    mov a, 0x000000000006e0d7
    call miller_rabin_test_montgomery

    mov a, 0x0000000000953d18
    call miller_rabin_test_montgomery

    mov a, 0x000000006b0191fe
    call miller_rabin_test_montgomery

    jmp is_prime

  is_prime:
    mov o, n
    call print
    cmp c, g, h
    sz c, 1
      halt 0
    add g, g, 8
    lw n, g
    jmp prime_test

  found_factor:
    divu n, b, n, a
    add h, h, 8
    sw h, a
    jmp prime_test

################
# Miller-Rabin primality test subroutine; needs m == n - 1
#
# input: a, n, m
# output: n/a
################
miller_rabin_test:
  divu q, a, a, n  # a = a mod n
  snz a, 1
    ret  # a certifies primality if a == 0 mod n
  call power  # a = a**d mod n
  cmp c, a, 1  # r == 1
  sz c, 1
    ret  # a certifies primality if a**d == 1 mod n
  cmp c, a, m  # m == n-1
  sz c, 1
    ret  # a certifies primality if a**d == -1 mod n

  mov d, 2
  mr_square_loop:
    dec b
    jz pollard_rho, b
    mulu x, y, a, a  # a = a**2 mod n
    divu q, a, x, n  # q is unused
    cmp c, a, 1  # r == 1
    jnz pollard_rho, c  # a witnesses compositeness if a**(d*2**i) == 1 mod n
    cmp c, a, m  # m == n-1
    sz c, 1
      ret  # a certifies primality if a**(d*2**i) == -1 mod n
    jmp mr_square_loop

################
# Miller-Rabin primality test subroutine using Montgomery arithmetic; needs
# the values from the precomputation step as well as m == n - 1
#
# input: a, n, m, (u, v, r, s)
# output: n/a
################
miller_rabin_test_montgomery:
  divu q, a, a, n  # a = a mod n
  snz a, 1
    ret  # a certifies primality if a == 0 mod n
  mulu x, y, a, s
  call montgomery_reduce  # convert a to montgomery form
  mov a, x
  call montgomery_power  # a = a**d mod n
  cmp c, a, r  # r == 1 (mongtomery form)
  sz c, 1
    ret  # a certifies primality if a**d == 1 mod n
  cmp c, a, m  # m == n-1 (montgomery form)
  sz c, 1
    ret  # a certifies primality if a**d == -1 mod n

  mr_mt_square_loop:
    dec b
    jz pollard_rho_montgomery, b
    mulu x, y, a, a  # a = a**2 mod n
    call montgomery_reduce
    mov a, x
    cmp c, a, r  # r == 1 (mongtomery form)
    jnz pollard_rho_montgomery, c  # a witnesses compositeness if a**(d*2**i) == 1 mod n
    cmp c, a, m  # m == n-1 (montgomery form)
    sz c, 1
      ret  # a certifies primality if a**(d*2**i) == -1 mod n
    jmp mr_mt_square_loop

################
# Pollard-Brent rho factorization algorithm
#
# input: n
# output: n/a
################
pollard_rho:

  rho_skip_count = 64

  mov o, 42
  rho_retry:

  mov b, o
  mov j, 1
  mov f, 1
  mov d, 1
  rho_outer_loop:
  mov a, b
    mov i, j
    rho_fast_loop:
      mulu b, y, b, b
      add b, b, 1
      divu y, b, b, n
      #mov o, b
      #call print
      sub i, i, 1
      jnz rho_fast_loop, i
    mov k, 0
    rho_slow_loop:
      mov e, b
      sub i, j, k
      leu c, rho_skip_count, i
      sz c, 1
        mov i, rho_skip_count
      rho_inner_loop:
        mulu b, y, b, b
        add b, b, 1
        divu y, b, b, n
        leu c, a, b
        sz c, 1
          sub x, b, a
        snz c, 1
          sub x, a, b
        mulu f, y, x, f
        divu y, f, f, n
        #add o, f, 1000000000
        #call print
        sub i, i, 1
        jnz rho_inner_loop, i
      mov x, f
      call gcd
      mov d, x
      #mov o, d
      #call print
      add k, k, rho_skip_count
      gequ c, k, j
      snz c, 2
        lequ c, d, 1
        jnz rho_slow_loop, c
    shl j, j, 1
  lequ c, d, 1
  jnz rho_outer_loop, c

  cmp c, d, n
  sz c, 12
    rho_final_loop:
      mulu e, y, e, e
      add e, e, 1
      divu y, e, e, n
      #add o, e, 2000000000
      #call print
      leu c, a, e
      sz c, 1
        sub x, e, a
      snz c, 1
        sub x, a, e
      call gcd
      mov d, x
      #mov o, d
      #call print
      lequ c, d, 1
      jnz rho_final_loop, c

  cmp c, d, n
  sz c, 2
    add o, o, 1
    jmp rho_retry

  mov a, d
  jmp found_factor

################
# Pollard-Brent rho factorization algorithm using Montgomery arithmetic.
# Requires m = n - r
#
# input: n, (u, v, r, s, m)
# output: n/a
################
pollard_rho_montgomery:

  rho_mt_skip_count = 64

  mov o, 42
  rho_mt_retry:

  mulu x, y, o, s
  call montgomery_reduce
  mov b, x
  mov j, 1
  mov f, r
  mov d, 1
  rho_mt_outer_loop:
  mov a, b
    mov i, j
    rho_mt_fast_loop:
      mulu x, y, b, b
      call montgomery_reduce
      mov b, x
      geu c, b, m
      sz c, 1
        sub b, b, m
      snz c, 1
        add b, b, r
      #mov o, b
      #call print
      sub i, i, 1
      jnz rho_mt_fast_loop, i
    mov k, 0
    rho_mt_slow_loop:
      mov e, b
      sub i, j, k
      leu c, rho_mt_skip_count, i
      sz c, 1
        mov i, rho_mt_skip_count
      rho_mt_inner_loop:
        mulu x, y, b, b
        call montgomery_reduce
        mov b, x
        geu c, b, m
        sz c, 1
          sub b, b, m
        snz c, 1
          add b, b, r
        leu c, a, b
        sz c, 1
          sub x, b, a
        snz c, 1
          sub x, a, b
        mulu x, y, x, f
        call montgomery_reduce
        mov f, x
        sub i, i, 1
        jnz rho_mt_inner_loop, i
      mov x, f
      #mov o, x
      #call print
      call gcd
      mov d, x
      #mov o, d
      #call print
      add k, k, rho_mt_skip_count
      gequ c, k, j
      snz c, 2
        lequ c, d, 1
        jnz rho_mt_slow_loop, c
    shl j, j, 1
  lequ c, d, 1
  jnz rho_mt_outer_loop, c

  cmp c, d, n
  sz c, 15
    rho_mt_final_loop:
      mulu x, y, e, e
      call montgomery_reduce
      mov e, x
      geu c, e, m
      sz c, 1
        sub e, e, m
      snz c, 1
        add e, e, r
      leu c, a, e
        sz c, 1
          sub x, e, a
        snz c, 1
          sub x, a, e
      call gcd
      mov d, x
      lequ c, d, 1
      jnz rho_mt_final_loop, c

  cmp c, d, n
  sz c, 2
    add o, o, 1
    jmp rho_mt_retry

  mov a, d
  jmp found_factor

################ UTILITY FUNCTIONS ################

################
# Loads a decimal number terminated by a newline from stdin to register n.
#
# inputs:  none
# outputs: n
################
input:
  lw c, -1
  input_add_digit:
    sub c, c, ord('0')
    mov o, c
    mulu n, h, n, 10
    add n, n, c
    lw c, -1
    cmp q, c, ord('\n')
    jz input_add_digit, q
  ret n

################
# Prints the value of register o to stdout in decimal, followed by a newline.
#
# inputs:  o
# outputs: none
################
print:
  call print_char
  sw -1, ord('\n')
  ret

  print_char:
    divu o, x, o, 10
    sz o, 1
      call print_char
    add x, x, ord('0')
    sw -1, x
    ret

################
# Precomputes values used for Montgomery multiplication:
#  * u = 1/2**64 mod n
#  * v = -1/n mod 2**64
#  * r = 2**64 mod n  (montgomery representation of 1)
#  * s = 2**128 mod n (montgomery representation of 2**64)
#
# inputs: n
# outputs: u, v, s, t
################
montgomery_precompute:
  # first compute the inverses; based on xbinGCD from
  # http://www.hackersdelight.org/MontgomeryMultiplication.pdf
  # This step takes something like an average of 7 cycles per bit in the
  # 'fast' mode, and 8 cycles per bit in 'safe' mode, for a total of around
  # 500 cycles: but we only have to do it once per modulus

  mov u, 1
  mov v, 0
  mov i, 64
  # HD defensively computes (u+beta)/2 to avoid overflow, taking two extra
  # instructions; however, since u < beta overflow is only possible when
  # beta >= 2**63, in most cases we can use a faster version and save
  # 2 * 64 = 128 cycles, at the expense of a couple cycles comparison
  gequ c, n, 2**63
  jz mt_pre_gcd_loop, c
  mt_pre_gcd_loop_safe:
    dec i
    and c, u, 1
    snz c, 3
      shr u, u, 1
      shr v, v, 1
    sz 0, 6
      and c, u, n
      xor u, u, n
      shr u, u, 1
      add u, u, c
      shr v, v, 1
      add v, v, 2**63
    jnz mt_pre_gcd_loop_safe, i
    jmp mt_pre_gcd_end
  mt_pre_gcd_loop:
    dec i
    and c, u, 1
    snz c, 3
      shr u, u, 1
      shr v, v, 1
    sz 0, 4
      add u, u, n
      shr u, u, 1
      shr v, v, 1
      add v, v, 2**63
    jnz mt_pre_gcd_loop, i
  mt_pre_gcd_end:

  # compute 2**64 mod n; since 2**64 is too large to fit in a register, we
  # first calculate r = 2**63 mod n, if it's greater than n/2, r = 2r - n,
  # otherwise just r = 2r

  divu q, r, 2**63, n # q is unused
  shr c, n, 1
  geu c, r, c
  shl r, r, 1
  sz c, 1
    sub r, r, n

  # It would be entirely possible to compute 2**128 mod n by starting with
  # r and using repeated doubling (64 times); this would take something
  # like 4*64 = 256 cycles.  Instead I'll use a doubleword division
  # algorithm from Hacker's Delight (ch. 9-4, fig. 9-3), which takes
  # fewer than 100 cycles.

  mov l, 0
  # normalize the divisor (n)
  and c, n, 2**64 - 2**32
  snz c, 2
    shl n, n, 32
    add l, l, 32
  and c, n, 2**64 - 2**48
  snz c, 2
    shl n, n, 16
    add l, l, 16
  and c, n, 2**64 - 2**56
  snz c, 2
    shl n, n, 8
    add l, l, 8
  and c, n, 2**64 - 2**60
  snz c, 2
    shl n, n, 4
    add l, l, 4
  and c, n, 2**64 - 2**62
  snz c, 2
    shl n, n, 2
    add l, l, 2
  and c, n, 2**64 - 2**63
  snz c, 2
    shl n, n, 1
    add l, l, 1
  # normalize the numerator
  shl a, r, l
  # split the divisor into halfwords
  shr b, n, 32
  and m, n, 2**32 - 1
  # compute first halfword of remainder
  divu q, p, a, b
  mt_pre_div_adjust1: # loop runs at most two times, 035x on average
    gequ c, q, 2**32
    snz c, 4
      mulu d, f, q, m # f is unused
      shl c, p, 32
      geu c, d, c
      sz c, 4
        sub q, q, 1
        add p, p, b
        leu c, p, 2**32
        jnz mt_pre_div_adjust1, c
  shl a, a, 32
  mulu d, f, q, n
  sub a, a, d
  # compute second halfword of remainder
  divu q, p, a, b
  mt_pre_div_adjust2:
    snz c, 4
      mulu d, f, q, m
      shl c, p, 32
      geu c, d, c
      sz c, 4
        sub q, q, 1
        add p, p, b
        leu c, p, 2**32
        jnz mt_pre_div_adjust2, c
  shl a, a, 32
  mulu d, f, q, n
  sub a, a, d
  # de-normalize remainder
  shr s, a, l

  ret u, v, r, s

################
# Performs the Montgomery reduction step, x = [yx]/2**64 mod n
# Requres the u and v calculated in mongomery_precompute.
#
# inputs: x, y, n, (u, v)
# outputs: x
################
montgomery_reduce:
  mulu m, u, x, v  # m = ([yx] mod 2**64) / (-n) mod 2**64
  mulu z, w, m, n  # [wz] = mN
  add x, x, z      # [yx] += [wz]
  leu c, x, z      # this is where I really miss an ADC instruction
  sz c, 1
    inc w
  add x, y, w      # x = [yx] / 2**64 = y (combined with y+w from above)
  leu c, x, y      # x -= n if overflow
  sz c, 1
    sub x, x, n
  gequ c, x, n     # if x >= n
  sz c, 1
    sub x, x, n    # x -= n
  ret x

################
# Computes a = a**d mod n by repeated squaring.
#
# inputs: a, d, n
# outputs: a
################
power:
  mov b, a
  mov a, 1
  mt_pow_loop:
    and c, d, 1
    sz c, 2
      mulu x, y, a, b  # a = a*b mod n
      divu q, a, x, n  # q is unused
    mulu x, y, b, b  # b = b*b mod n
    divu q, b, x, n
    shr d, d, 1
    jnz mt_pow_loop, d
  ret a

################
# Uses Montgomery multiplication to compute a = a**d mod n.  Treats d as an
# ordinary unsigned integer; treats d as an integer in Montgomery form.
# Requres the u, v, and r calculated in mongomery_precompute.
#
# inputs: a, d, n, (u, v, r)
# outputs: a
################
montgomery_power:
  mov b, a
  mov a, r
  pow_loop:
    and c, d, 1
    sz c, 3
      mulu x, y, a, b
      call montgomery_reduce
      mov a, x
    mulu x, y, b, b
    call montgomery_reduce
    mov b, x
    shr d, d, 1
    jnz pow_loop, d
  ret a

################
# Computes x = GCD(x,n) using the binary GCD algorithm.  Assumes that x < n
# and that n is odd.  Note that we don't need a separate Montgomery GCD,
# since, surprisingly, GCD(x*(2**64) mod n, n) == GCD(x, n).
#
# inputs: x, n
# outputs: x
################
gcd:
  snz x, 2  # GCD(0, n) == n
    mov x, n
    ret x

  gcd_loop:
    and c, x, 1  # n is odd, so the GCD has no factors of two
    snz c, 3
    gcd_div_2_loop:
      shr x, x, 1
      and c, x, 1
      jz gcd_div_2_loop, c

    geu c, n, x
    sz c, 5
      sub x, n, x
      sub n, n, x
      jnz gcd_loop, x
        mov x, n
        ret x

    sub x, x, n
    jnz gcd_loop, x
      mov x, n
      ret x

```

# Answer
> 7 votes
# Total 36,757,269,913 cycles

830B assembled

```
Number                Time (s)  Cycles
    8831269065180497       0.1         1148
 2843901546547359024      55.0      9535194
 6111061272747645669     351.4     60559378
11554045868611683619       0.8       135135
 6764921230558061729       1.0       155407
16870180535862877896   43067.5   7126449414
 3778974635503891117     148.7     22823483
  204667546124958269      87.4     13635943
16927447722109721827   16119.0   2739172134
 9929766466606501253  156158.3  26784802677

```

Factorization by trial division, with a few optimizations. Probably not the fastest, but as no one else has posted yet, I'll kick it off.

```
main:
    call read
    call factor
    halt 0

# Prints factors. Pass number to be factored in register `a'.
factor:
    mov n, a # Write routine expects factor in `a', so we'll just keep it there.
    # Handle 2 specially
_factor_twos:               # do {
    geu b, n, 1
    jz _factor_ret, b   #   if (number <= 1) return
    and b, n, 1
    jnz _factor_rest, b #   if (number & 1 != 0) break
    mov a, 2
    call write          #   printf("%llu\n", 2)
    shr n, n, 1         #   number >>= 1
    jmp _factor_twos    # } while (0)
_factor_rest:
    mov a, 3            # factor = 3
_factor_rest_loop:          # do {
    cmp b, n, 1
    jnz _factor_ret, b  #   if (number == 1) return
    divu b, c, n, a     #   (quotient, remainder) = number / factor
    jnz _factor_not_divisible, c # if (remainder == 0) {
    call write                   #   printf("%llu\n", factor)
    mov n, b                     #   number = quotient
    jmp _factor_rest_loop
_factor_not_divisible:               # } else {
    leu c, b, a
    jnz _factor_print_last, c    #   if quotient < a, print n and return.
    add a, a, 2                  #   else a += 2 }
    jmp _factor_rest_loop # } while (0)
_factor_print_last:
    mov a, n
    call write # printf("%llu", n)
_factor_ret:
    ret

# Read stdin. Must be one decimal string, ending with a newline.
# Behavior on invalid input is unspecified.
# Return value stored in a.
read:
    mov a, 0
_read_loop_start:                # do {
    lw c, 0xffffffffffffffff #   c = getchar()
    sub b, c, ord('\n')
    jz _read_ret, b          #   if (c == '\n'), return
    sub c, c, ord('0')       #   c -= '0'
    mulu a, y, a, 10
    add a, a, c              #   a = 10*a + c
    jmp _read_loop_start     # } while (0)
_read_ret:
    ret a

# Write number in register a to stdout, followed by a newline.
# Fortunately, a 64-bit number has at most 20 digits, and we have 25 registers.
# So we can keep them in registers instead of pushing them onto the stack or heap,
# avoiding the fairly expensive read back.
write:
    divu a, b, a, 10
    jz _write_b, a
    divu a, c, a, 10
    jz _write_c, a
    divu a, d, a, 10
    jz _write_d, a
    divu a, e, a, 10
    jz _write_e, a
    divu a, f, a, 10
    jz _write_f, a
    divu a, g, a, 10
    jz _write_g, a
    divu a, h, a, 10
    jz _write_h, a
    divu a, i, a, 10
    jz _write_i, a
    divu a, j, a, 10
    jz _write_j, a
    divu a, k, a, 10
    jz _write_k, a
    divu a, l, a, 10
    jz _write_l, a
    divu a, m, a, 10
    jz _write_m, a
    divu a, n, a, 10
    jz _write_n, a
    divu a, o, a, 10
    jz _write_o, a
    divu a, p, a, 10
    jz _write_p, a
    divu a, q, a, 10
    jz _write_q, a
    divu a, r, a, 10
    jz _write_r, a
    divu a, s, a, 10
    jz _write_s, a
    divu a, t, a, 10
    jz _write_t, a
    add a, a, ord('0')
    sw 0xffffffffffffffff, a
_write_t:
    add t, t, ord('0')
    sw 0xffffffffffffffff, t
_write_s:
    add s, s, ord('0')
    sw 0xffffffffffffffff, s
_write_r:
    add r, r, ord('0')
    sw 0xffffffffffffffff, r
_write_q:
    add q, q, ord('0')
    sw 0xffffffffffffffff, q
_write_p:
    add p, p, ord('0')
    sw 0xffffffffffffffff, p
_write_o:
    add o, o, ord('0')
    sw 0xffffffffffffffff, o
_write_n:
    add n, n, ord('0')
    sw 0xffffffffffffffff, n
_write_m:
    add m, m, ord('0')
    sw 0xffffffffffffffff, m
_write_l:
    add l, l, ord('0')
    sw 0xffffffffffffffff, l
_write_k:
    add k, k, ord('0')
    sw 0xffffffffffffffff, k
_write_j:
    add j, j, ord('0')
    sw 0xffffffffffffffff, j
_write_i:
    add i, i, ord('0')
    sw 0xffffffffffffffff, i
_write_h:
    add h, h, ord('0')
    sw 0xffffffffffffffff, h
_write_g:
    add g, g, ord('0')
    sw 0xffffffffffffffff, g
_write_f:
    add f, f, ord('0')
    sw 0xffffffffffffffff, f
_write_e:
    add e, e, ord('0')
    sw 0xffffffffffffffff, e
_write_d:
    add d, d, ord('0')
    sw 0xffffffffffffffff, d
_write_c:
    add c, c, ord('0')
    sw 0xffffffffffffffff, c
_write_b:
    add b, b, ord('0')
    sw 0xffffffffffffffff, b
    sw 0xffffffffffffffff, ord('\n')
    ret
# End of write.

```

Full output from my timing loop, in case anyone wants to check the results and/or my copy-paste and math.

```
13
23
31
37
41
47
47
59
61
79
Execution terminated after 1148 cycles with exit code 0.
/usr/local/bin/golf.py factor.bin <<< $num  0.09s user 0.02s system 94% cpu 0.115 total
2
2
2
2
3
3
107
1121707
164546579
Execution terminated after 9535194 cycles with exit code 0.
/usr/local/bin/golf.py factor.bin <<< $num  55.03s user 0.07s system 99% cpu 55.136 total
3
3
3
7
7
7
13
50759273983933
Execution terminated after 60559378 cycles with exit code 0.
/usr/local/bin/golf.py factor.bin <<< $num  351.38s user 0.32s system 99% cpu 5:51.89 total
7
7
7
13
2531
4091
250250521
Execution terminated after 135135 cycles with exit code 0.
/usr/local/bin/golf.py factor.bin <<< $num  0.84s user 0.01s system 99% cpu 0.857 total
31
89
97
3881
18211
357653
Execution terminated after 155407 cycles with exit code 0.
/usr/local/bin/golf.py factor.bin <<< $num  0.98s user 0.01s system 99% cpu 0.997 total
2
2
2
3
702924188994286579
Execution terminated after 7126449414 cycles with exit code 0.
/usr/local/bin/golf.py factor.bin <<< $num  43067.49s user 86.38s system 99% cpu 12:04:12.58 total
7
103
727
7209485975851
Execution terminated after 22823483 cycles with exit code 0.
/usr/local/bin/golf.py factor.bin <<< $num  134.60s user 0.13s system 99% cpu 2:14.83 total
66449
1604167
1920043
Execution terminated after 13635943 cycles with exit code 0.
/usr/local/bin/golf.py factor.bin <<< $num  81.02s user 0.06s system 99% cpu 1:21.12 total
322255481
52528036667
Execution terminated after 2739172134 cycles with exit code 0.
/usr/local/bin/golf.py factor.bin <<< $num  16119.02s user 12.31s system 99% cpu 4:29:03.61 total
9929766466606501253
Execution terminated after 26784802677 cycles with exit code 0.
/usr/local/bin/golf.py factor.bin <<< $num  156158.25s user 186.81s system 49% cpu 88:35:03.65 total

```

# Answer
> 5 votes
## score = 378,867,816 cycles

\[randomized - your results may vary\]

Uses the Miller-Rabin primality test (a deterministic version that can handle up to 2^64), a bit of trial factoring, and ECM factoring. All the algebraic operations are in there, including modular addition, subtraction, multiplication, exponentiation, and inversion (mod n\<2^64).

Modular multiplication is suboptimal - it does a binary search for the quotient. Computing the remainder of a 128 by 64 divide is tough without a matching builtin instruction. Speed that up and the whole thing will go faster.

2290 bytes compiled

```
    step = i
    test = j
    tmp  = k

# prints factors of number on stdin, one per line in arbitrary order, to stdout
main:
    call    read_int
    mov a, x
two:
    # remove factors of 2
    and tmp, a, 1
    jnz odd, tmp
    mov x, 2
    call    write_int
    sw  -1, ord('\n')
    shr a, a, 1
    jmp two
odd:
    cmp tmp, a, 1
    jnz done2, tmp
    call    factorodd
done2:
    halt    0

# a = input value >= 3 and odd.  Prints factors of a and returns.
factorodd:
    call    isprime
    jnz prime2, b
    # n is composite.  Try to find a (not necessarily prime) factor.
    call    trial
    jnz split, b
    call    primepower
    jnz split, b
    call    ecm
split:
    # recurse on two parts
    mov a, b
    call    factorodd
    mov a, c
    jmp factorodd
prime2:
    mov x, a
    call    write_int
    sw  -1, ord('\n')
    ret

# a = input value >= 3 and odd.
# b, c = output values, a = b*c, b,c > 1.
# returns b=0 if failure.
trial:
    mov b, 3
loop5:
    divu    c, r, a, b
    jz  found, r
    add b, b, 2
    leu tmp, b, 1001        # TODO: tune max size
    jnz loop5, tmp
    mov b, 0
found:
    ret b, c

# a = input value >= 3.  Must be odd and have >=2 distinct prime factors.
# b, c = output values, a = b*c, b,c > 1.
ecm:
    mov n, a
loop12:
    # choose a random elliptic curve by picking m with 0 <= m < n
    # y^2 = x^3 + mx + 1
    rand    a
    mov b, 1
    mov c, n
    call    mulmod
    mov m, d
    # check that the descriminant is nonzero.  D = 4m^3+27
    mov a, m
    mov b, m
    call    mulmod
    mov a, d
    call    mulmod
    mov a, d
    mov b, 4
    call    mulmod
    mov a, d
    mov b, 27
    call    addmod
    jz  loop12, d
    # try to find factor of n with this elliptic curve
    call    ecmtry
    jz  loop12, b
    divu    c, tmp, n, b
    ret b, c

# n = modulus
# m = curve param
# b = return value - 0 or a factor of n
ecmtry:
    mov p, 0
    mov q, 1

    # multiply by 2
    mov e, p
    mov f, q
    mov g, p
    mov h, q
    call    ellipticadd
    jnz foundfactor2, d
    mov p, b
    mov q, c

    # continue multiplying by odd numbers
    # TODO: just multiply by odd primes
    mov i, 3
loop15:
    mov e, p
    mov f, q
    mov g, i
    call    ellipticmul
    jnz foundfactor3, d
    mov p, b
    mov q, c
    add i, i, 2
    jnz loop15, p
    jnz loop15, q
    mov b, 0
    ret b
foundfactor3:
    mov b, d
    ret b

# multiplication by a constant in the elliptic curve "group"
#   m = input curve parameter
#   n = input modulus
# e,f = input x,y of point
#   g = input multiplier
# b,c = output x,y of sum
#   d = output 0 if successful, factor of n if not.
ellipticmul:
    # compute g*(e,f) by repeated doubling
    mov x, e
    mov y, f
    mov t, g
    mov r, 0
    mov s, 0
loop14:
    jz  done6, t
    and tmp, t, 1
    jz  noadd, tmp
    # r += x
    mov e, r
    mov f, s
    mov g, x
    mov h, y
    call    ellipticadd
    jnz foundfactor2, d
    mov r, b
    mov s, c
noadd:
    # x += x
    mov e, x
    mov f, y
    mov g, x
    mov h, y
    call    ellipticadd
    jnz foundfactor2, d
    mov x, b
    mov y, c

    shr t, t, 1
    jmp loop14
done6:
    mov b, r
    mov c, s
    mov d, 0
    ret b, c, d
foundfactor2:
    ret d

# addition in the elliptic curve "group"
#   m = input curve parameter
#   n = input modulus
# e,f = input x,y of first point (p)
# g,h = input x,y of second point (q)
# b,c = output x,y of sum
#   d = output 0 if successful, factor of n if not.
ellipticadd:
    px = e
    py = f
    qx = g
    qy = h
    rx = b
    ry = c
    gcd = d
    # 0+q=q
    or  tmp, px, py
    jz  retq, tmp

    # p+0=p
    or  tmp, qx, qy
    jz  retp, tmp

    cmp tmp, px, qx
    jz  diffx, tmp
    cmp tmp, py, qy
    jz  inf, tmp    # px == qx, py != qy, return inf
    jz  inf, py     # px == qx, py == qy, py==0, return inf

    # px == qx, py == qy, py != 0.  This is the double-root case

    # u = numerator = 3 px^2 + a
    mov a, px
    mov b, px
    mov c, n
    call    mulmod
    mov a, d
    mov b, 3
    call    mulmod
    mov a, d
    mov b, m
    call    addmod
    mov u, d

    # v = denominator = 2y
    mov a, py
    mov b, py
    call    addmod
    mov v, d
    jmp divide

diffx:
    # px != qx
    mov a, py
    mov b, qy
    call    submod
    mov u, d        # u = numerator = py - qy

    mov a, px
    mov b, qx
    call    submod
    mov v, d        # v = denominator = px - qx

divide:
    mov a, v
    call    inv
    cmp tmp, c, 1   # gcd(v,n)==1?
    jz  foundfactor, tmp
    mov v, d

    # compute s = u/v mod n = u * v^-1 mod n
    mov a, u
    mov b, v
    mov c, n
    call    mulmod
    mov s, d

    # compute x = s*s - px - qx
    mov a, s
    mov b, s
    call    mulmod
    mov a, d
    mov b, px
    call    submod
    mov a, d
    mov b, qx
    call    submod
    mov x, d

    # compute y = s * (px - x) - py
    mov a, px
    mov b, x
    call    submod
    mov a, d
    mov b, s
    call    mulmod
    mov a, d
    mov b, py
    call    submod

    # return [s*s-px-qx, s*(px-x)-py]
    mov rx, x
    mov ry, d
    mov gcd, 0
    ret rx, ry, gcd

retp:
    mov rx, px
    mov ry, py
    mov gcd, 0
    ret rx, ry, gcd
retq:
    mov rx, qx
    mov ry, qy
    mov gcd, 0
    ret rx, ry, gcd
inf:
    mov rx, 0
    mov ry, 0
    mov gcd, 0
    ret rx, ry, gcd
foundfactor:
    mov gcd, c
    ret gcd

# a = input value >= 3.  Must be odd.
# b = output factor of a.
# if a is a prime power, returns a factor of a.
# otherwise, returns 0.
primepower:
    mov e, 2
loop6:
    mov b, e
    call    nthroot
    leu tmp, c, 3
    jnz notprimepower, tmp

    # compute c^e
    mov r, 1
    mov b, e
loop9:
    mulu    r, tmp, r, c
    dec b
    jnz loop9, b

    cmp tmp, r, a
    jnz isprimepower, tmp

    inc e
    cmp tmp, e, 41  # largest odd power in 2^64 is 3^40
    jz  loop6, tmp
    ret

isprimepower:
    mov b, c
    ret

notprimepower:
    mov b, 0
    ret b

# a = input value
# b = input exponent
# c = output floor(a**(1/b))
nthroot:
    # binary search for the root
    mov c, 0
    mov step, 0x80000000

loop7:
    jz  done3, step
    add test, c, step
    shr step, step, 1

    # check if test^b > a
    # test^b might overflow, so we can't just compute that and compare.
    # so we start with e=a, divide by test b times, and check that
    # the result is 0.
    mov d, b
    mov e, a
loop8:
    divu    e, tmp, e, test
    dec d
    jnz loop8, d

    jz  loop7, e    # test is too big, don't change c

    mov c, test     # test is <= floor(a**(1/b)).  Keep it.
    jmp loop7

done3:
    ret c

# a = input number >= 2
# b = ouput 1/0 if a is prime/composite
isprime:
    # small primes (tests below require that we check these first)
    cmp tmp, a, 2
    jnz prime, tmp
    cmp tmp, a, 3
    jnz prime, tmp
    cmp tmp, a, 5
    jnz prime, tmp
    cmp tmp, a, 7
    jnz prime, tmp
    cmp tmp, a, 11
    jnz prime, tmp
    cmp tmp, a, 13
    jnz prime, tmp
    cmp tmp, a, 17
    jnz prime, tmp
    cmp tmp, a, 19
    jnz prime, tmp
    cmp tmp, a, 23
    jnz prime, tmp
    cmp tmp, a, 29
    jnz prime, tmp
    cmp tmp, a, 31
    jnz prime, tmp
    cmp tmp, a, 37
    jnz prime, tmp

    # even numbers
    and tmp, a, 1
    jz  composite, tmp

    # uses Miller-Rabin with enough fixed bases to guarantee the
    # correct result for numbers up to 2^64.
    # see http://oeis.org/A014233
    mov b, 2
    call    miller_rabin
    jz  composite, c
    mov b, 3
    call    miller_rabin
    jz  composite, c
    mov b, 5
    call    miller_rabin
    jz  composite, c
    mov b, 7
    call    miller_rabin
    jz  composite, c
    mov b, 11
    call    miller_rabin
    jz  composite, c
    mov b, 13
    call    miller_rabin
    jz  composite, c
    mov b, 17
    call    miller_rabin
    jz  composite, c
    mov b, 19
    call    miller_rabin
    jz  composite, c
    mov b, 23
    call    miller_rabin
    jz  composite, c
    mov b, 29
    call    miller_rabin
    jz  composite, c
    mov b, 31
    call    miller_rabin
    jz  composite, c
    mov b, 37
    call    miller_rabin
    jz  composite, c
prime:
    mov b, 1
    ret b
composite:
    mov b, 0
    ret b

# a = input number >= 3
# b = input base value (1 < b < a-1)
# c = output 1 = may be prime, 0 = definitely composite
miller_rabin:
    mov p, a
    mov t, b

    sub q, p, 1
    mov s, 0
    sub e, a, 1
loop2:
    and tmp, e, 1
    jnz endloop2, tmp
    add s, s, 1
    shr e, e, 1
    jmp loop2
endloop2:
    mov a, t
    mov b, e
    mov c, p
    call    pow
    cmp tmp, d, 1
    jnz unknown, tmp
    cmp tmp, d, q
    jnz unknown, tmp
    mov x, d

loop4:
    sub s, s, 1
    jz  composite2, s
    mov a, x
    mov b, x
    mov c, p
    call    mulmod
    cmp tmp, d, 1
    jnz composite2, tmp
    cmp tmp, d, q
    jnz unknown, tmp
    mov x, d
    jmp loop4

composite2:
    mov c, 0
    ret c
unknown:
    mov c, 1
    ret c

# a = input value
# n = input modulus
# returns c, d such that
# c = gcd(a,n)
# d * a % n == gcd(a,n)
inv:
    # extended euclidean algorithm, from
    # http://stackoverflow.com/a/14093613/180090
    new = e
    old = f
    pos = g

    mov p, n
    mov new, 1
    mov old, 0
    mov q, p
    mov pos, 0
loop13:
    jz  done5, a
    divu    q, r, q, a
    mulu    h, tmp, q, new
    add h, old, h
    mov old, new
    mov new, h
    mov q, a
    mov a, r
    xor pos, pos, 1
    jmp loop13
done5:
    mov c, q
    jnz positer, pos
    sub old, p, old
positer:
    mov d, old
    ret c, d

# d = a ** b % c
pow:
    mov r, 1
    mov e, b
    mov t, a
    # t ** e % c
loop3:
    jz  endloop3, e
    and tmp, e, 1
    jz  lowbitclear, tmp

    mov a, t
    mov b, r
    call    mulmod  # r = t*r mod c
    mov r, d

lowbitclear:
    shr e, e, 1
    mov a, t
    mov b, t
    call    mulmod  # t = t*t mod c
    mov t, d
    jmp loop3

endloop3:
    mov d, r
    ret d

# d = a * b % c
mulmod:
    # do multiply
    mulu    e, f, a, b

    # binary search for quotient
    mov  q, 0
    mov  step, 0x8000000000000000
loop:
    jz  done, step

    # test = q + step
    add test, q, step
    shr step, step, 1

    # check test*c
    mulu    g, h, test, c
    geu tmp, h, f
    jnz loop, tmp
    leu tmp, h, f
    jnz ok, tmp
    geu tmp, g, e
    jnz loop, tmp
ok:
    # test*c <= a*b.  Use test as the new q.
    mov q, test
    jmp loop

done:
    # q == quotient of (a*b)/c
    mulu    g, h, q, c  # q*c, g+h<<64 should be close to e+f<<64
    sub d, e, g    # remainder
    ret d

# d = (a + b) % n
# requires 0 <= a, b < n
addmod:
    add d, a, b
    leu tmp, d, a   # wrapped 2^64
    jnz overflow, tmp
    leu tmp, d, n   # result less than modulus?
    jnz inrange, tmp
overflow:
    sub d, d, n
inrange:
    ret d

# d = (a - b) % n
# requires 0 <= a, b < n
submod:
    sub d, a, b
    leu tmp, a, b   # below 0?
    jz  nounderflow, tmp
    add d, d, n
nounderflow:
    ret d

read_int:
    mov x, 0
read_int_loop:
    lw c, -1
    cmp q, c, ord("\n")
    jnz read_int_done, q
    sub c, c, ord("0")
    mulu x, d, x, 10
    add x, x, c
    jmp read_int_loop
read_int_done:
    ret x

write_int:
    divu x, m, x, 10
    jz write_int_done, x
    call write_int
write_int_done:
    add m, m, ord("0")
    sw -1, m
    ret

```

Output:

```
13
23
31
37
41
47
47
59
61
79
Execution terminated after 799601 cycles with exit code 0.
2
2
2
2
3
3
107
164546579
1121707
Execution terminated after 216769549 cycles with exit code 0.
3
3
3
7
7
7
13
50759273983933
Execution terminated after 939985 cycles with exit code 0.
7
7
7
13
2531
4091
250250521
Execution terminated after 34213849 cycles with exit code 0.
31
89
97
18211
3881
357653
Execution terminated after 9662357 cycles with exit code 0.
2
2
2
3
702924188994286579
Execution terminated after 748732 cycles with exit code 0.
7
103
727
7209485975851
Execution terminated after 912672 cycles with exit code 0.
66449
1920043
1604167
Execution terminated after 38514477 cycles with exit code 0.
322255481
52528036667
Execution terminated after 75568529 cycles with exit code 0.
9929766466606501253
Execution terminated after 738065 cycles with exit code 0.

```

---
Tags: number-theory, primes, fewest-operations, factoring, golf-cpu
---


title: Program the Cup-Stacking Robot

text:
# Question
Title: Program the Cup-Stacking Robot
I'm sure everyone has seen before that cups can be stacked into pyramids (and other shapes):

```
           A
        A A A
 A     A A A A
A A A A A A A A

```

Yes, `A` is definitely an adequate character to represent a cup.

New cups could be added either on the ground, to the right of the structure, or on top of two adjacent cups. Here is the above structure again, but all available spots for new cups are marked with `_`:

```
         _ A
        A A A
 A _ _ A A A A
A A A A A A A A _ _ _

```

Let's say we want to build a robot which can assemble these cup stacks. The robot will understand two simple instructions to manipulate such a structure:

* `a`: Add a new cup in the first available spot in left-to-right *reading* order (that is, scan the rows from top to bottom, left to right until you find an available spot, then place the cup there). The above example would become:

```
         A A
        A A A
 A     A A A A
A A A A A A A A

```
* `r`: Remove the first cup in left-to-right reading order. The above example would become:

```
        A A A
 A     A A A A
A A A A A A A A

```

It turns out that *any* structure can be constructed from scratch using only these two operations. E.g.

```
      A
 A   A A
A A A A A

```

Can be built with the sequence of instructions

```
aaaaaaaaaaaarrrrraa

```

The larger example above can be built using

```
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrraaaaaaarr

```

Here is an even bigger one:

```
    A
   A A                   A
  A A A     A   A       A A
 A A A A   A A A A     A A A A
A A A A A A A A A A   A A A A A

```

which can be built with

```
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrraaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrraaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrraaaaaaaaaaaaaarrrrrrrrrrraaaaaaaa

```

**Note:** If spots on the ground are freed up by removal instructions they will be reused *before* placing cups to the right of all existing cups. E.g.

```
aaaarrra

```

will yield

```
A   A

```

not

```
    A A

```

You can think of the ground as being on top of a semi-infinite row of cups.

## The Challenge

Given a structure of stacked cups, return a sequence representing the instructions to build this structure. Your primary score is the sum of the numbers of instructions for the test cases provided at the bottom. In the event of a tie (which is likely, because I'm convinced that an efficient optimal solution is possible), the shortest solution wins.

Here are some more details about the rules:

* You may assume that there are no leading spaces on the bottom row of the input, so the left-most ground spot for a cup with always be used.
* You may assume any reasonable amount of trailing spaces (no spaces, one space, padded to a rectangle, padded to a rectangle with a single trailing space).
* You may optionally expect the input to end in a single trailing newline.
* You may choose any two distinct printable ASCII characters (0x20 to 0x7E, inclusive) instead of `A` and spaces (the rules about spaces then transfer to your chosen character).
* Your output should contain only two distinct characters representing the operations (you may choose other characters than `a` and `r`). You may optionally print a single trailing newline.
* Your code must be able to solve **any of the test cases below in less than a minute** on a reasonable desktop PC (if it takes two minutes on mine, I'll give you the benefit of the doubt, but if it takes ten I won't - I believe an optimal algorithm is possible which solves any of them in less than a second).
* You must not optimise your code towards individual test cases (e.g. by hardcoding them). If I suspect anyone of doing so, I reserve the right to change the test cases.

You can use this CJam script for the reverse operation: it will take a string of building instructions and print the resulting stack of cups. (Thanks to Dennis for rewriting the snippet and significantly speeding it up.)

Sp3000 also kindly provided this alternative Python script for the same purpose.

## Test Cases

After each test case, there's a number indicating the optimal number of instructions as per Ell's answer.

```
                                       A
                                      A A
                                     A A A
                                    A A A A
                                   A A A A A
                                  A A A A A A
                                 A A A A A A A
                                A A A A A A A A
                               A A A A A A A A A
                              A A A A A A A A A A
                             A A A A A A A A A A A
                            A A A A A A A A A A A A
                           A A A A A A A A A A A A A
                          A A A A A A A A A A A A A A
                         A A A A A A A A A A A A A A A
                        A A A A A A A A A A A A A A A A
                       A A A A A A A A A A A A A A A A A
                      A A A A A A A A A A A A A A A A A A
                     A A A A A A A A A A A A A A A A A A A
                    A A A A A A A A A A A A A A A A A A A A
                   A A A A A A A A A A A A A A A A A A A A A
                  A A A A A A A A A A A A A A A A A A A A A A
                 A A A A A A A A A A A A A A A A A A A A A A A
                A A A A A A A A A A A A A A A A A A A A A A A A
               A A A A A A A A A A A A A A A A A A A A A A A A A
              A A A A A A A A A A A A A A A A A A A A A A A A A A
             A A A A A A A A A A A A A A A A A A A A A A A A A A A
            A A A A A A A A A A A A A A A A A A A A A A A A A A A A
           A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
          A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
         A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
        A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
       A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
      A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
     A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
    A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
   A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
  A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

820
                                             A
                                            A A
                                           A A A
                                          A A A A
                                         A A A A A
                                        A A A A A A
                                       A A A A A A A
                                      A A A A A A A A
                     A               A A A A A A A A A
                    A A             A A A A A A A A A A
                   A A A           A A A A A A A A A A A
                  A A A A         A A A A A A A A A A A A
         A       A A A A A       A A A A A A A A A A A A A
        A A     A A A A A A     A A A A A A A A A A A A A A
   A   A A A   A A A A A A A   A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

1946

               A
              A A
             A A A
            A A A A
           A A A A A
          A A A A A A
         A A A A A A A
        A A A A A A A A
       A A A A A A A A A               A
      A A A A A A A A A A             A A
     A A A A A A A A A A A           A A A
    A A A A A A A A A A A A         A A A A
   A A A A A A A A A A A A A       A A A A A       A
  A A A A A A A A A A A A A A     A A A A A A     A A
 A A A A A A A A A A A A A A A   A A A A A A A   A A A   A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

2252

                                                         A A
                                                      A A A A
                                                   A A A A A A
                                                A A A A A A A A
                                             A A A A A A A A A A
                                          A A A A A A A A A A A A
                                       A A A A A A A A A A A A A A
                                    A A A A A A A A A A A A A A A A
                                 A A A A A A A A A A A A A A A A A A
                              A A A A A A A A A A A A A A A A A A A A
                           A A A A A A A A A A A A A A A A A A A A A A
                        A A A A A A A A A A A A A A A A A A A A A A A A
                     A A A A A A A A A A A A A A A A A A A A A A A A A A
                  A A A A A A A A A A A A A A A A A A A A A A A A A A A A
               A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
            A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
         A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
      A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
   A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

9958

                   A A
                  A A A A
                 A A A A A A
                A A A A A A A A
               A A A A A A A A A A
              A A A A A A A A A A A A
             A A A A A A A A A A A A A A
            A A A A A A A A A A A A A A A A
           A A A A A A A A A A A A A A A A A A
          A A A A A A A A A A A A A A A A A A A A
         A A A A A A A A A A A A A A A A A A A A A A
        A A A A A A A A A A A A A A A A A A A A A A A A
       A A A A A A A A A A A A A A A A A A A A A A A A A A
      A A A A A A A A A A A A A A A A A A A A A A A A A A A A
     A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
    A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
   A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
  A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

5540

A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A

10280

 A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

10320

   A       A       A       A       A       A       A       A       A       A
  A A     A A     A A     A A     A A     A A     A A     A A     A A     A A
 A A A   A A A   A A A   A A A   A A A   A A A   A A A   A A A   A A A   A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

5794

              A
             A A
            A A A
           A A A A                                               A
          A A A A A                                             A A
         A A A A A A A                                         A A A
        A A A A A A A A               A                       A A A A
       A A A A A A A A A             A A             A       A A A A A   A
      A A A A A A A A A A           A A A           A A     A A A A A A A A
     A A A A A A A A A A A         A A A A         A A A   A A A A A A A A A
    A A A A A A A A A A A A       A A A A A       A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A     A A A A A A     A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A   A A A A A A A   A A A A A A A A A A A A A A A A

3297

                                                   A A
                                                  A A A
                                                 A A A A
                                                A A A A A
                                               A A A A A A
                                              A A A A A A A
                                             A A A A A A A A
                                            A A A A A A A A A
                                           A A A A A A A A A A     A
                                          A A A A A A A A A A A   A A
                                       A A A A A A A A A A A A A A A A
                                      A A A A A A A A A A A A A A A A A
                                     A A A A A A A A A A A A A A A A A A
      A                             A A A A A A A A A A A A A A A A A A A
     A A                           A A A A A A A A A A A A A A A A A A A A
    A A A             A A         A A A A A A A A A A A A A A A A A A A A A
   A A A A           A A A       A A A A A A A A A A A A A A A A A A A A A A
  A A A A A         A A A A     A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A     A A A A A A   A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A   A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

4081

                      A
                     A A       A                     A
                    A A A     A A                   A A A                 A
             A     A A A A   A A A A               A A A A     A         A A
  A         A A   A A A A A A A A A A         A   A A A A A   A A       A A A
 A A       A A A A A A A A A A A A A A       A A A A A A A A A A A     A A A A
A A A   A A A A A A A A A A A A A A A A     A A A A A A A A A A A A   A A A A A

4475

                                                             A
      A           A                       A                 A A A   A       A
     A A         A A   A         A A     A A A   A         A A A A A A     A A
A   A A A A A   A A A A A   A   A A A   A A A A A A   A   A A A A A A A   A A A

5752

```

That means, the best possible score is **64,515** instructions.

# Answer
# Python 2, 64,515

```
import sys

input = map(str.rstrip, sys.stdin.readlines())
width = (len(input[-1]) + 1) / 2
for i in range(len(input)):
    indent = len(input) - i - 1
    input[i] = [c != " " for c in input[i][indent::2]]
    input[i] += [False] * (width - indent - len(input[i]))
input = [[False] * n for n in range(width - len(input) + 1)] + input
working_area = [[False] * n for n in range(width + 1)]

def add():
    sys.stdout.write("a")
    for row in range(width + 1):
        for i in range(row):
            if not working_area[row][i] and (
                row == width or
                (working_area[row + 1][i] and working_area[row + 1][i + 1])
            ):
                working_area[row][i] = True
                return
def remove():
    sys.stdout.write("r")
    for row in range(width + 1):
        if True in working_area[row]:
            working_area[row][working_area[row].index(True)] = False
            return

for row in range(width, -1, -1):
    r = input[row]; R = working_area[row]
    for i in range(len(r) - 1, -1, -1):
        if r[i]:
            while not R[i]: add()
        else:
            while R[i]: remove()

```

## Results

**#1** \- 820 **#2** \- 1,946 **#3** \- 2,252
**#4** \- 9,958 **#5** \- 5,540 **#6** \- 10,280
**#7** \- 10,320 **#8** \- 5,794 **#9** \- 3,297
**#10** \- 4,081 **#11** \- 4,475 **#12** \- 5,752

**Total** 64,515

## Explanation

We start with an empty "working area". We scan the input in *reverse* reading order, i.e., right-to-left and bottom-to-top. If there's a mismatch between the input and the working area at the current location (i.e., a cup is present in the input but not in the working area, or vice versa,) we add, or remove, cups to the working area, according to the rules, until the mismatch is resolved, at which point we continue to the next location.

**Correctness**

To show that this method is correct, i.e., that the resulting sequence generates the input structure, it's enough to show that we never modify (i.e., add or remove cups at) locations we've already visited (since, at each location we visit, we make sure that the working area matches the input.) This is an easy consequence of the fact that we work in the reverse order in which cups are added and removed:

* A cup at location *l* will always be removed before a cup at a location that succeeds *l* in reading order, and therefore, that precedes *l* in scan order, hence there's no danger of removing a cup we've already visited.
* Similarly, a cup at location *l* will always be added before a cup that precedes it in scan order, **given that** there are already two cups below it (or that it's at the bottom); however, since we will have already visited these locations, and hence added the necessary cups, and since, as noted above, there's no danger of later having removed those cups, this condition is met, and so there's no danger of adding a cup at a location we've already visited.

**Optimality**

Note that the effect of adding, or removing, a cup from a structure doesn't depend on the sequence of operations used to generate the structure, only on its current configuration. As a result, given an optimal sequence *Sn* = {*s*1, ..., *sn*} of operations that generate a certain structure, every initial segment of *Sn*, i.e., any sequence *Sm* = {*s*1, ..., *sm*}, where *m**n*, is also an optimal sequence, for the corresponding structure it generates, or else there would be a shorter sequence than *Sn*, generating the same structure.

We can show that our method is optimal by induction on the length of the optimal generating sequence: Our method clearly generates an optimal sequence for any structure whose optimal generating sequence is empty (there's only one such structure—the empty structure.) Suppose that our method generates an optimal sequence for all structures whose optimal sequence (or sequences) is of length *n*, and consider a structure generated by an optimal sequence *S**n*+1. We want to show that, given the structure generated by *S**n*+1 as input, our method produces the same sequence (or, at least, a sequence of the same length.)

As noted above, *Sn* is also an optimal sequence, and so, by hypothesis, our method produces an optimal sequence given the structure generated by *Sn* as input. Suppose, without loss of generality, that *Sn* is the sequence produced by our method (if it isn't, we can always replace the first *n* elements of *S**n*+1 with the said sequence, and get a sequence of length *n* \+ 1 that generates the same structure.) Let *l* be the location modified by the last operation in *S**n*+1 (namely, *s**n*+1), and let *Sm* be the initial segment of *Sn*, that our program will have produced once it reaches *l* (but before processing *l*). Note that, since the structures generated by *Sn* and *S**n*+1 agree in all locations that follow *l*, in reading order, *Sm* is the same given either structure as input.

If *s**n*+1 is `a` (i.e., cup addition), then there must not be any location preceding *l*, in reading order, where a cup can be added to the structure generated by *Sn*. As a result, the subsequence of *Sn* following *Sm* must be all `a` (since an `r` would imply that either there's an empty space before *l*, or that *Sn* is not optimal.) When we come to process *l*, we'll need to add exactly *n - m* cups before we can add a cup at *l*, hence the resulting sequence will be *Sm*, followed by *n - m* \+ 1 `a` elements, which equals *S**n*+1 (there won't be any mismatch after this point, hence this is the complete sequence produced.)

Likewise, if *s**n*+1 is `r`, then there must not be any cup at a location preceding *l*, in reading order, in the structure generated by *Sn*. As a result, the subsequence of *Sn* following *Sm* must be all `r`. When we come to process *l*, we'll need to remove exactly *n - m* cups before we can remove the cup at *l*, hence the resulting sequence will be *Sm*, followed by *n - m* \+ 1 `r` elements, which again equals *S**n*+1.

In other words, our method produces an optimal sequence for the said input structure, and therefore, by induction, for any input structure.

Note that this doesn't mean that this implementation is the most efficient one. It's definitely possible, for example, to calculate the number of cups that has to be added, or removed, at each point directly, instead of actually performing these operations.

**Uniqueness**

We can use the optimality of our method to show that optimal sequences are, in fact, unique (that is, that no two distinct optimal sequences generate the same structure.) We use, again, induction on the size of the optimal generating sequence: The empty sequence is obviously the unique optimal generating sequence of the empty structure. Suppose that all optimal generating sequences of length *n* are unique, and consider a structure, Σ, generated by the two optimal sequences *S**n*+1 and *T**n*+1.

Recall that *Sn* and *Tn* are themselves optimal, and therefore, by hypothesis, unique. Since our method produces optimal sequences, *Sn* and *Tn* can be thought of as generated by our method. Let *lS* and *lT* be the locations modified by the last operation in *S**n*+1 and *T**n*+1, respectively, and suppose, without loss of generality, that *lS* follows, or equals, *lT* in reading order. Since the structures generated by *Sn* and *Tn* agree in all locations following *lS*, in reading order, the sequence produced by our method, given either structure as input, once it reaches *lS* (but before processing it), is the same for both; call this sequence *U*.

Since the last action of *S**n*+1 modifies *lS*, if Σ has a cup at *lS* then there must not be any vacancy before *lS*, and if Σ doesn't have a cup at *lS* then there must not be any cup before *lS*, in reading order. Therefore, the rest of the sequence generating Σ, following *U*, must consist of repeated application of the same instruction, dictated by the presence or absence of a cup at *lS* (or else it wouldn't be optimal). In other words, *S**n*+1 and *T**n*+1 are equal (they both start with *U*, and end with the said sequence of repeated instructions,) that is, the optimal generating sequence of Σ is unique, and so, by induction, all optimal generating sequences are unique.
> 32 votes

---
Tags: metagolf, hexagonal-grid
---


title: What's my math assignment?

text:
# Question
Title: What's my math assignment?
# The Challenge

I always write my math assignments down in the same way. For example:

```
pg. 420: #25, 50-56, 90
pg. 26: #50-60 evens, 70-80 odds, 90-99 3s
pg. 69: #12, 16, 18, 37

```

But I need you to tell me the individual problem numbers. For example:

```
input:
pg. 420: #25, 50-56, 90

output:
25, 50, 51, 52, 53, 54, 55, 56, 90

```

Here are the rules for telling me my problem numbers:

The assignment always starts with `pg. (number): #`, feel free to discard it.

Each group of problems is separated by a comma, and different patterns mean different things.

A single number (`4, 6, 7438, 698236`) just means that one problem is in the assignment.

Two numbers with a dash between them means those two numbers and all integers between. For example, `1-6` would become `1, 2, 3, 4, 5, 6`

If two numbers have a dash between them, then there's a word, there is a special rule for the numbers.

If the word is `evens`, then all even numbers between the two are included (`1-6 evens -> 2, 4, 6`).

If the word is `odds`, then all odd numbers between the two are included (`1-6 odds -> 1, 3, 5`).

If the word is `3s`, then all numbers where `n mod 3 = 0` between the two are included (`1-6 3s -> 3, 6`);

## Test Examples: (inputs then outputs)

```
pg. 1: #1, 2, 3
1, 2, 3

pg. 82: #76, 84-87, 91, 94-100 evens, 103-112 3s
76, 84, 85, 86, 87, 91, 94, 96, 98, 100, 103, 106, 109, 112

pg. 9001: #9000-9002 odds
9001

```

This is code-golf, so your score is the number of bytes.

# Answer
# JavaScript (ES7), 138 bytes

```
F=s=>s.replace(/.*#|(\d+)-?(\d+)? ?(\d|\w*)s?/g,(_,a,b,c)=>b?[for(i of Array(b-a--+1))if(++a*c?(b-a)%c<1:!c||a%2==c>'f')a].join`, `:a||'')

```

```
F=s=>s.replace(/.*#|(\d+)-?(\d+)? ?(\d|\w*)s?/g,(_,a,b,c)=>b?[for(i of Array(b-a--+1))if(++a*c?(b-a)%c<1:!c||a%2==c>'f')a].join`, `:a||'')
button.onclick=()=>output.innerHTML=F(range.value)
```

```
button, textarea {
  display: block;
  width: 100%;
  margin-bottom: 0.5em;
  box-sizing: border-box;
}
```

```
<textarea id="range"></textarea>
<button id="button">submit</button>
<div id="output"></div>
```
> 1 votes

---
Tags: code-golf
---


# Question
Title: Given a list of lengths, and a string representing those lengths, do they match?
Given a pattern representing a list of lengths, and a string representing those lengths, do they match?

For those interested, this is question equivalent to verifying if a row or column of a Nonogram may be correct. However, I have omitted all language relating to Nonograms to make the question less confusing for those unfamiliar with these puzzles.

## Input

Two lines of data, separated by a newline.

1. The first line will be a space separated list of integers, example:

```
3 6 1 4 6

```

This line **describes a pattern** of filled spaces of size equal to the integer list, separated by empty spaces of **unknown**, positive length that the second line must match. There may also be empty spaces at the beginning and end of the matched string.
2. The second line will be a line that that may or may not match the pattern in line one. It consists entirely of `#`, `x`, and `_`. This line is **guaranteed** to be **at least** as long as the *sum of the integers in the first line, plus the number of distinct integers, minus 1,* and can be longer. So the second line in this case is guaranteed to be at least `(3+6+1+4+6) + (5) - 1`, or 24 characters long. Here is an example 24 character line that matches the pattern in the first line:

```
###_######_#_####_######

```

### Meaning of symbols:

* `#` This represents a filled box
* `x` This represents a box marked as "guaranteed to be empty"
* `_` This represents an unknown / unmarked box.

## Goal

The idea is to:

1. Validate that the second line could be a valid row that meets the pattern of the first line.
    * You must print an unambiguous error message (how you choose to do this is up to you; the examples below write `ERROR` but it doesn't need to be those 5 characters) if the unknown spaces cannot be filled out with either `#` or `x` to match the first line.
2. Print the **zero-indexed indices** of the integers that have been **completely placed** in the row, space delimited. *If there is ambiguity, **do not** print the index*.

## Examples:

```
Input:                    |  Output:    |  Reason:
--------------------------------------------------------------------------
3 6 1 4 6                 | 0 1 2 3 4   |  This is a complete string that
###x######x#x####x######  |             |  matches perfectly.
--------------------------------------------------------------------------
1 2 1                     | 0 1 2       |  There is no ambiguity which filled cells
#____xx___##__x_#         |             |  correspond to which parts of the pattern.
--------------------------------------------------------------------------
1 2 1                     |             |  I don't know whether the filled block is
____#___x                 |             |  part of the 1, 2, or 1, so output nothing.
--------------------------------------------------------------------------
1 2 1                     | ERROR       | The first unknown cell will create a block that
#_#x_#                    |             | matches either 1 1 or 3, but not 1 2.
--------------------------------------------------------------------------
1 2 1                     | 0 2         | Even though we know where all the filled cells
#____#                    |             | must be, only 0 and 2 are actually filled here.
--------------------------------------------------------------------------
1 1 1 1                   |             | There are so many possible ways to do fill this,
__#_______#____           |             | we don't know which indices are actually matched.
--------------------------------------------------------------------------
4 4                       |             | Again, we don't know WHICH 4 is matched here,
______x####________       |             | so output nothing.
--------------------------------------------------------------------------
4 4                       | 0           | However, here, there's no room for a previous 4,
__x####________           |             | so the displayed 4 must be index 0.
--------------------------------------------------------------------------
3                         | ERROR       | We can't fit a 3 into a space before or after
__x__                     |             | the x, so this is impossible to match.
--------------------------------------------------------------------------
5 1 3                     | 0           | While we can match the 5, we don't know whether
x#####x____#____          |             | the single block matches the 1 or the 3.
--------------------------------------------------------------------------
3 2 3                     | 1           | The two has been completely placed,
____##x##____             |             | even though we don't know which it is.

```

## Rules:

You may write a program or function, which receives the input as a newline delimited String or from STDIN (or closest alternative), and returns the output as an space delimited String or printing it to STDOUT (or closest alternative). You may optionally include a single trailing newline in the output.

Additionally, standard loopholes which are no longer funny are **banned**.

# Answer
# Perl, 134 bytes

(includes 1 switch)

```
perl -pe '$p.="([#_]{$_})[x_]+"for@l=split;chop$p,$_=<>;/^[x_]*$p*$(?{$h[$_-1].=$$_ for 1..@l})(?!)/;$_=@h?join$",grep{$h[$_]!~/_/}0..$#l:ERROR'

```

Takes two lines of input from STDIN. Must be re-executed for every input.

The idea is to first extract all possible patterns that match the given lengths. For example, if we have the lengths `1 2` and the pattern `#_x_#_`, then the matching patterns are `(#, _#)` and `(#, #_)`. Then, concatenate the matched patterns for every index - for the example the result is the list `(##, _##_)`. Now, print the indices of all the strings in the list which have only '#' characters.

I got the method to extract all possible matches from a regex in Perl here.
> 4 votes

---
Tags: code-golf, string, puzzle-solver
---


# Question
Title: Monday Mini-Golf #5: <s>Don't</s> DO try this at home
**Monday Mini-Golf:** A series of short questions, posted (hopefully!) every Monday.

Sometimes folks get tired of life's rules: "don't do this", "you can't do that", "we won't let you do this". It can seem really restricting at times! But every now and then, it's good to have a little fun, so let's write some code to modify these rules. And while we're at it, might as well modify other negativity as well. (Of course, these modifications ~~won't~~ WILL be only temporary, so we'll leave the original wording too.)

# Challenge

Your challenge is to write a program or function that puts HTML `<s>`~~strikethroughs~~`</s>` around restrictive words—that is, words ending in `n't` or followed by `not`—and after each of these, inserts its positive equivalent in ALL CAPS. At the end, after a space, the number of replacements made should be included. For example:

```
Please don't jump into the pool.

```

becomes

```
Please <s>don't</s> DO jump into the pool. 1

```

For words ending in `n't` or followed by `not` (as well as `cannot`), the positive equivalent is everything up to the aforementioned `not` (excluding spaces). Here's what I mean:

* `do not speak` becomes `<s>do not</s> DO speak`
* `it doesn't work` becomes `it <s>doesn't</s> DOES work`
* `we cannot` becomes `we <s>cannot</s> CAN`

However, there are a few exceptions. Make sure these are handled properly.

```
can't -> <s>can't</s> CAN
won't -> <s>won't</s> WILL
ain't -> <s>ain't</s> AM
shan't -> <s>shan't</s> SHALL
I'm not -> <s>I'm not</s> I AM
you're not -> <s>you're not</s> YOU ARE

```

## Details

* The input will never contain any whitespace except normal spaces (no tabs, newlines, etc.).
* The input will never contain any double negatives (e.g. `we can't not do this`).
* If a `not` appears immediately after a punctuation mark, or as part of another word, leave it be.
* Be sure to preserve the original text, including upper/lowercase, between the `<s></s>` tags.
* If you wish, you may use `<strike></strike>` in place of `<s></s>`.

# Test-cases

**Inputs:**

```
I'm sorry, but you can't do that.
Driving on the beach isn't allowed.
Driving on the beach is not allowed.
Please don't jump in; I cannot imagine what might come of that.
Don't worry; we won't get into trouble.
I'm not perfect, but you're not either.
You shan't do it 'cause I ain't doin' it!
Can't we capitalize special cases?
I don't like the words can't, shan't, won't, don't, ain't, or ppcgn't.
Oh, this? It's nothing.
Tie a slipknot in the rope.
Would you like Pinot Noir?
This sentence contains none of the replacement words. Not even knot or ca't.
This sentence doesn't contain one of the replacement words.

```

**Outputs:**

```
I'm sorry, but you <s>can't</s> CAN do that. 1
Driving on the beach <s>isn't</s> IS allowed. 1
Driving on the beach <s>is not</s> IS allowed. 1
Please <s>don't</s> DO jump in; I <s>cannot</s> CAN imagine what might come of that. 2
<s>Don't</s> DO worry; we <s>won't</s> WILL get into trouble. 2
<s>I'm not</s> I AM perfect, but <s>you're not</s> YOU ARE either. 2
You <s>shan't</s> SHALL do it 'cause I <s>ain't</s> AM doin' it! 2
<s>Can't</s> CAN we capitalize special cases? 1
I <s>don't</s> DO like the words <s>can't</s> CAN, <s>shan't</s> SHALL, <s>won't</s> WILL, <s>don't</s> DO, <s>ain't</s> AM, or <s>ppcgn't</s> PPCG. 7
Oh, this? It's nothing. 0
Tie a slipknot in the rope. 0
Would you like Pinot Noir? 0
This sentence contains none of the replacement words. Not even knot or ca't. 0
This sentence <s>doesn't</s> DOES contain one of the replacement words. 1

```

# Scoring

This is , so shortest valid code in bytes wins. Tiebreaker goes to submission that reached its final byte count first. The winner ~~will not~~ WILL be chosen next Monday, Oct 26. Good luck!

# Answer
# Pip, ~~138~~ 140 bytes

Yeesh, that `cannot`/`knot` distinction is tricky.

```
x:"ca wo ai sha i'm you're"^sY"CAN0WILL0AM0SHALL0I AM0YOU ARE"^0OqR-`([\w']+)( no|n'|(?<=can)no)t\b`{++i"<s>".a."</s>".s.((yx@?LCb)|UCb)}s.i

```

Reads a line from stdin, outputs to stdout. The regex:

```
`([\w']+)( no|n'|(?<=can)no)t\b`

```

matches a word (including apostrophes) followed by one of three things:

* `not`
* `n't`
* `not` without a space, provided the first half of the word was `can`

The `-` operator on a regex makes it case-insensitive.

Matches are replaced with the result of the following function. (Note: within the function, `a` is the whole match and `b` is capture group 1.)

```
{++i"<s>".a."</s>".s.((yx@?LCb)|UCb)}
 ++i                                   Increment counter
    "<s>".a."</s>"                     Return entire match wrapped in HTML tags...
                  .s.(             )   plus space, plus the following:
                           LCb         Lowercase first capture group
                        x@?            Find its index in list x of special cases (nil if
                                         not in list)
                      (y      )        Use that as index into list y of replacements
                               |UCb    If it wasn't a special case, this is nil, and we
                                         instead use uppercase(b)

```

Once the modified string is done, we also output a space and the number of replacements `i`.
> 7 votes

# Answer
# GNU Sed, 321 bytes

(including +1 for `-r`)

```
:
s!(can('|no)t)([^<])!<s>\1</s> CAN\3!i
s!(won't)([^<])!<s>\1</s> WILL\2!i
s!(ain't)([^<])!<s>\1</s> AM\2!i
s!(shan't)([^<])!<s>\1</s> SHALL\2!i
s!(I'm not)([^<])!<s>\1</s> I AM\2!i
s!(you're not)([^<])!<s>\1</s> YOU ARE\2!i
t
s!(([^ .!?]+)(n't| not))([^<])!<s>\1</s> \U\2\4!i
t
h
s/1//g
s/<s>/1/g
s/[^1]//g
x
G
s/\n/ /

```

"String replacement - a job for sed!" I thought. But this was surprisingly hard, and I kept inflooping with the substitution of the original text. And the counting! At least there's no prohibition on unary in the question...
> 3 votes

# Answer
## Perl, 153 bytes

**150 script + 3 for `-p`**

```
$c=0|s!\b((ca)nnot|([\w']+)(?: not|n't))\b!"<s>$&</s> ".uc({ai,AM,ca,CAN,wo,WILL,sha,SHALL,"i'm","I AM","you're","YOU ARE"}->{lc$+}||$+)!egi;s/
/ $c
/

```

So whilst I match all the test cases now but that regex has cost me dearly... I'll think on it!

### Example output:

```
$perl -p can.pl <<< "I'm sorry, but you can't do that.
Driving on the beach isn't allowed.
Driving on the beach is not allowed.
Please don't jump in; I cannot imagine what might come of that.
Don't worry; we won't get into trouble.
I'm not perfect, but you're not either.
You shan't do it 'cause I ain't doin' it!
Can't we capitalize special cases?
I don't like the words can't, shan't, won't, don't, ain't, or ppcgn't.
Oh, this? It's nothing.
This sentence contains none of the replacement words. Not even knot or ca't.
This sentence doesn't contain one of the replacement words.
Tie a slipknot in the rope.
Would you like Pinot Noir?
You cannot be serious\!"

```

```
I'm sorry, but you <s>can't</s> CAN do that. 1
Driving on the beach <s>isn't</s> IS allowed. 1
Driving on the beach <s>is not</s> IS allowed. 1
Please <s>don't</s> DO jump in; I <s>cannot</s> CAN imagine what might come of that. 2
<s>Don't</s> DO worry; we <s>won't</s> WILL get into trouble. 2
<s>I'm not</s> I AM perfect, but <s>you're not</s> YOU ARE either. 2
You <s>shan't</s> SHALL do it 'cause I <s>ain't</s> AM doin' it! 2
<s>Can't</s> CAN we capitalize special cases? 1
I <s>don't</s> DO like the words <s>can't</s> CAN, <s>shan't</s> SHALL, <s>won't</s> WILL, <s>don't</s> DO, <s>ain't</s> AM, or <s>ppcgn't</s> PPCG. 7
Oh, this? It's nothing. 0
This sentence contains none of the replacement words. Not even knot or ca't. 0
This sentence <s>doesn't</s> DOES contain one of the replacement words. 1
Tie a slipknot in the rope. 0
Would you like Pinot Noir? 0
You <s>cannot</s> CAN be serious\! 1

```
> 2 votes

---
Tags: code-golf, string
---


# Question
Title: Print a cube's vertices and its covering triangles
Output coordinates of the vertices of a cube. Then, output a list of twelve triangles that will cover the cube, each triangle being a list of three vertex-indexes, consistently oriented. Output must be an ASCII string of distinct decimal numbers. This golf has no input. Winner is the fewest characters, where the character set is Unicode.

For an example, consider a 1x1x1 cube cornered at 0,0,0. The eight vertices of the cube can be described by the following xyz coordinates on a 3d Cartesian grid:

```
x y z = (0,0,1) (1,0,1) (1,1,1) (0,1,1) (0,0,0) (1,0,0) (1,1,0) (0,1,0)

```

Each vertex can be given an index: `x y z->index: 0 0 1->0, 1 0 1->1, 1 1 1->2, 0 1 1->3, 0 0 0->4, 1 0 0->5, 1 1 0->6, 0 1 0->7`

Now consider the top face, vertexes indexed zero to three. The two covering triangles can be described by three indices each:

```
[0,1,2] [2,3,0]

```

Here is a picture of this top face, viewed from above the cube:

```
 3_____2
 |    /|
 |   / |
 |  /  |
 | /   |
 0_____1

```

And here is a view from an angle.

```
    3____2
   / __-/|
 0/_`__1 |
  |    | /6
  |____|/
 4     5

```

Note the orientation, or 'winding', of both of these triangles is 'counterclockwise' when viewed from 'outside' the cube directly looking at the face in question (imagine visiting each vertex as listed, it goes counterclockwise). Now imagine this done for all six sides of the cube.

```
vertices: (0,0,1) (1,0,1) (1,1,1) (0,1,1) (0,0,0) (1,0,0) (1,1,0) (0,1,0)
triangles as indices: [0,1,2], [2,3,0], [6,5,4], [4,7,6],
  [5,2,1], [2,5,6], [0,3,4], [4,3,7], [2,6,3], [3,6,7], [0,4,1], [1,4,5]

```

You can output any size of cube located at any coordinates. You can number and order the vertex coordinates however you wish. Indices can be 0 based or 1 based. The triangle's orientation can be either clockwise or counterclockwise when viewed from outside the cube as long as it is consistent for all triangles.

The output can be formatted however you wish, as long as each ASCII decimal number is separated by at least one non-numeric ASCII character. For instance the above example could also be output as follows:

```
0 0 1 1 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0
0 1 2 2 3 0 6 5 4 4 7 6 5 2 1 2 5 6 0 3 4 4 3 7 2 6 3 3 6 7 0 4 1 1 4 5

```

This golf is inspired by various 3d graphics systems and formats, including OpenGL, OBJ, OFF, AMF, CGAL, etc. This golf is similar to the golf by Calvin's Hobbies named Output a Face on a Numbered Cube , the big difference being you need to output the x y z coordinates of the vertices yourself and output triangle indices. Thanks for reading.

Per user inspiration here is a "helper" validation program in python2 (non-golfy) that will print 'ok' or 'not ok' for test output data in variables vertstr and idxstr. It doesn't work perfectly... but it can catch some errors.

Edit: fixed typo in example and bugs in validation code.

```

#vertstr = '0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1'
#idxstr = '1 2 0 2 1 3 7 5 6 4 6 5 2 4 0 4 2 6 7 3 5 1 5 3 4 1 0 1 4 5 7 6 3 2 3 6'
vertstr = '0 0 1 1 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0'
idxstr = '0 1 2 2 3 0 6 5 4 4 7 6 5 2 1 2 5 6 0 3 4 4 3 7 2 6 3 3 6 7 0 4 1 1 4 5'

class Vector:
    def __init__(self,v):
        self.x,self.y,self.z=v[0],v[1],v[2]
    def __add__(self,v):
        return Vector([self.x+v.x,self.y+v.y,self.z+v.z])
    def __sub__(self,v):
        return Vector([self.x-v.x,self.y-v.y,self.z-v.z])
    def __str__(self):
        return str(self.x)+','+str(self.y)+','+str(self.z)

def cross(v1,v2):
    x = v1.y*v2.z-v2.y*v1.z
    z = v1.x*v2.y-v2.x*v1.y
    y = v1.z*v2.x-v2.z*v1.x
    return Vector([x,y,z])

# http://mathforum.org/library/drmath/view/55343.html & http://sympy.org
def winding(v1,v2,v3,obs):
    x1,y1,z1,x2,y2,z2,x3,y3,z3,x4,y4,z4=v1.x,v1.y,v1.z,v2.x,v2.y,v2.z,v3.x,v3.y,v3.z,obs.x,obs.y,obs.z
    d =     x1*(y2*z3 - y2*z4 - y3*z2 + y3*z4 + y4*z2 - y4*z3)
    d = d + y1*(-x2*z3 + x2*z4 + x3*z2 - x3*z4 - x4*z2 + x4*z3)
    d = d + z1*(x2*y3 - x2*y4 - x3*y2 + x3*y4 + x4*y2 - x4*y3)
    d = d - x2*y3*z4 + x2*y4*z3 + x3*y2*z4 - x3*y4*z2 - x4*y2*z3 + x4*y3*z2
    return d

def normals(v1,v2,v3):
    va = v2-v1
    vb = v3-v2
    vc = v1-v3
    n1 = cross(va,vb)
    n2 = cross(vb,vc)
    n3 = cross(vc,va)
    return [n1,n2,n3]

def triplify(str):
    nums,triples=[],[]
    for num in str.split(' '): nums+=[int(num)]
    for i in range(0,len(nums),3):
        triples += [[nums[i],nums[i+1],nums[i+2]]]
    return triples

verts = triplify(vertstr)
indices = triplify(idxstr)
nsum = Vector([0,0,0])
windsum = 0
xs,ys,zs=[],[],[]
for v in verts:
    xs+=[v[0]]
    ys+=[v[1]]
    zs+=[v[2]]
#print xs,ys,zs,len(xs)
center=Vector([float(sum(xs))/len(xs),float(sum(ys))/len(ys),float(sum(zs))/len(zs)])
for triangle in indices:
    v1 = Vector(verts[triangle[0]])
    v2 = Vector(verts[triangle[1]])
    v3 = Vector(verts[triangle[2]])
    norms = normals(v1,v2,v3)
    print v1,v2,v3,norms[0],norms[1],norms[2]
    for n in norms:
        nsum += n
    w = winding(v1,v2,v3,center)
    print 'winding',w
    if w<0: windsum-=1
    elif w>0: windsum+=1
if abs(windsum)==12: print 'winding ok'
else: print 'winding not ok'
if (nsum.x==0 and nsum.y==0 and nsum.z==0): print 'normal sum ok'
else: print 'normal sum not ok'

```

# Answer
# Pyth, 18 characters

```
j`CM"⭧勛囃勦⾽仵ᶌﻘꚱ쥎➡˻ì

```

Same idea as my Haskell answer; prints:

```
[
1
1
1
1
1
,

2
1
2
1
1
...

```
> 1 votes

# Answer
# CJam, 35 bytes

```
YZm*`3{[XY4]m<)\0+_:+1$f-+_@f+W%}%`

```

Try it online

The output is:

> \[\[0 0 0\] \[0 0 1\] \[0 1 0\] \[0 1 1\] \[1 0 0\] \[1 0 1\] \[1 1 0\] \[1 1 1\]\]\[\[1 2 0 2 1 3\] \[7 5 6 4 6 5\] \[2 4 0 4 2 6\] \[7 3 5 1 5 3\] \[4 1 0 1 4 5\] \[7 6 3 2 3 6\]\]

Triangle orientation is clockwise from the outside. I checked this manually, and it looks correct to me.

Explanation:

```
YZ      Push 2 and 3 on stack.
m*      Cartesian power, creates the coordinates of the 8 vertices.
`       Convert to string for output. Done with vertices.
3{      Start loop over 3 coordinate directions.
  [XY4]   Push [1 2 4], which are the vertex index offsets for the 3 directions.
  m<      Rotate by loop counter. So the remaining loop body will be executed once
          with [1 2 4], once with [2 4 1], once with [4 1 2].
  )       Pop off last offset. Will use this as index offset between the two
          parallel faces.
  \       Swap pair of remaining two offsets to top. These are the index offsets
          within the face.
  0+      Add a 0 to the list. These 3 indices define the first triangle.
  _:+     Calculate the sum. This is the vertex index of the opposite corner.
  1$      Copy first triangle to the top.
  f-      Subtract all indices from the index of the opposite corner, producing
          the second triangle of the face.
  +       Concatenate the indices of the two triangles, resulting in a list with
          the 6 vertex indices for the face.
  _       Copy the list.
  @       Bring the offset between the two faces to the top.
  f+      Add the offset to each index in the copied list.
  W%      Revert the order, resulting in the properly oriented list of the 6 vertex
          indices for the parallel face.
}%      End of loop over 3 coordinate directions.
`       Convert to string for output. Done with triangles.

```
> 2 votes

# Answer
# Ruby, ~~98~~106

Fixed error spotted by Reto Koradi.

```
s=sprintf'%024b',342391
6.times{|i|t='15462315'[i,3];t+=t.reverse;t[1+i%2*3]='07'[i%2];s+=t}
p s.split(//)

```

Given that coordinates are required, the only corner numbering scheme that made sense seemed to be the one where each corner is the binary representation of its coordinates. That's quite different from the linked question, where various different numbering schemes were tried. In the end I decided to print the coordinates with a dirty hardcode: `s` is initialised to the string version of 24-bit number`000001010011100101110111` whose decimal representation is 342391. Actually with this method of printing coordinates, the numbering of the vertices is flexible, so I may do another answer.

Going round the equator of the cube, we find the vertices 1,5,4,6,2,3 and we can define one triangle for each face from any 3 consecutive numbers on this list (wrapping back to the beginning at the end.) The other triangle on each face is defined by reversing the digits, and substituting the middle digit with 0 or 7 as appropriate.

This gives all the required output, but without any separating characters. To achieve that, I simply convert to an array of characters and print the array, like this (linebreaks inserted to prevent scrolling):

```
["0", "0", "0", "0", "0", "1", "0", "1", "0", "0", "1", "1", "1", "0", "0",
 "1", "0", "1", "1", "1", "0", "1", "1", "1", "1", "0", "4", "4", "5", "1",
 "5", "4", "6", "6", "7", "5", "4", "0", "2", "2", "6", "4", "6", "2", "3",
 "3", "7", "6", "2", "0", "1", "1", "3", "2", "3", "1", "5", "5", "7", "3"]

```
> 1 votes

# Answer
# JavaScript (ES6) 78

```
alert([...'1010011100101110111:120213756465240426735153410145763236'].join` `)

```

Sorry but I really don't understand these challenges with no input.
> 1 votes

# Answer
# Haskell, 38 characters

```
f=mapM(mapM print.show)"⭧勛囃勦⾽仵ᶌﻘꚱ쥎➡˻ì"

```

Prints the right numbers, separated by a whole lot of junk:

```
'\''
'\\'
'1'
'1'
'1'
'1'
'1'
'\''
'\''
'\\'
'2'
'1'
'2'
'1'
'1'
...

```

The cube's diagonal is from (1, 1, 1) to (2, 2, 2).
> 1 votes

# Answer
# CJam, 20 characters

```
"⭧勛囃勦⾽仵ᶌﻘꚱ쥎➡˻ì":isS*

```

Same idea as my Haskell answer; prints:

```
1 1 1 1 1 2 1 2 1 1 2 2 2 1 1 2 1 2 2 2 1 2 2 2 1 2 0 2 1 3 7 5 6 4 6 5 2 4 0 4 2 6 7 3 5 1 5 3 4 1 0 1 4 5 7 6 3 2 3 6

```
> 1 votes

# Answer
# Ruby, Rev 1 62

```
29.downto(0){|c|p c>5?73888640>>c&1:[c,c^1,c|6,c|6,(c+3)%6,c]}

```

Got rid of the `c-6` by multiplying the magic number by 64.

The assignment of coordinates is below. It's odd that I assigned `100` to number 1. I could have saved a byte in rev 0 by exchanging the axes and assigning `001` to number 1. The reason it was that way was because originally I had up counting in the loop, which would have meant I had to put everything in reverse in the magic string. Anyway, with the change I've made now, there's no additional saving to be made, so i'll leave the coordinates as they are

```
Cube rotated with 0163 face at back
Top layer from above
01   000 100
74   010 110
Bottom layer from above
36   001 101
25   011 111

```

# Ruby, Rev 0 63

```
29.downto(0){|c|p c>5?1154510>>c-6&1:[c,c^1,c|6,c|6,(c+3)%6,c]}

```

Using hardcoding of the coordinates data to give flexibility in picking the corners. There are 54 digits in the output, meaning that the naive solution would have 63-54=9 bytes available for code. As I can't think of a way to insert spaces in 9 bytes, I believe this is shorter than the naive solution.

**Numbering scheme** (adapted from my Ruby answer to the linked question https://codegolf.stackexchange.com/a/48867/15599)

```
4---7
|  /|
| / |
|/  |
1---0---7
|  /|  /|
| / | / |
|/  |/  |
6---3---2---7
    |  /|  /|
    | / | / |
    |/  |/  |
    6---5---4
        |  /|
        | / |
        |/  |
        6---1

```

Output

```
0
0
0
1
0
0
0
1
1
0
0
1
1
1
0
1
1
1
0
0
1
1
1
0
[5, 4, 7, 7, 2, 5]
[4, 5, 6, 6, 1, 4]
[3, 2, 7, 7, 0, 3]
[2, 3, 6, 6, 5, 2]
[1, 0, 7, 7, 4, 1]
[0, 1, 6, 6, 3, 0]

```
> 1 votes

---
Tags: code-golf, geometry
---


title: The Light Up Game

text:
# Question
Title: The Light Up Game
## **The Challenge**

The game *Light Up!* is a simple puzzle game where the objective is to light up every cell in an *n*-by-*n* array with light bulbs. However, there are blocks in the way that will prevent light from traveling, and no lightbulb can be places such that another lightbulb shines light on it. Each light bulb has light coming from it in only the **horizontal** and **vertical** directions.

You must make a program that takes in an array of 5 numbers. Your program must convert each numbers into a 5-bit binary number, which will define at what places in the array there are blocks. If there is a 1, there is a block at the spot, but if there is a 0, there is not a block. Each number converted to binary defines a row, like:

`[5,6,5,6,5] -> [00101, 00110, 00101, 00110, 00101] ->`

```
. . B . B
. . B B .
. . B . B
. . B B .
. . B . B

```

Where B = blocks that block light

Your program must take this array and find the solutions (places where you need to put light) and give it back as an array of 5 numbers.

## **Example:**

Input: `[1,5,9,13,17]`

Which translates to `[00001, 00101, 01001, 01101, 10001]`

Making the array:

```
. . . . B
. . B . B
. B . . B
. B B . B
B . . . B

```

A solution for this array is

```
L ~ ~ ~ B
~ L B ~ B
~ B ~ L B
~ B B ~ B
B L ~ ~ B

```

~ = Light L = Lightbulb

Which gives the binary array of lights `[10000, 01000, 00010, 00000, 01000]`

And translates back to `[16, 8, 2, 0, 8]`

Output: `[16, 8, 2, 0, 8]`

## **Rules**

* Two lightbulbs can not be in the same row or column if there is no block between them.
* A lightbulb's light can only travel horizontally and vertically, and will stop if there is a block in the way
* Your program must take in an array `[a,b,c,d,e]` and output in the same form
* If there are no way the array can be solved, your program must not give output or state "No Output."
* This is a \[code-golf\] challenge, lowest amount in bytes wins!

# Answer
> 6 votes
# CJam, ~~79~~ ~~73~~ 68 bytes

```
32q~:Q,m*{Q.&:|!},{Q]{2b5Ue[}f%~..-_z]{Wa/_1fb.f|1a*}f%~z..|:|1a=}=p

```

This will work only using the Java interpreter. It should terminate *eventually* with default switches, but it becomes reasonably fast by increasing the maximum heap size.

At the cost of 7 more bytes (for a total of **75 bytes**), we can speed up the code significantly.

```
q~32b:Q;Y25#{Q&!},{Q]{2b25Ue[}/.m5/_z]{Wa/_1fb.f|1a*}f%~z..|:|1a=}=32bU5e[p

```

It still requires a little patience, but you can this version online in the CJam interpreter.

### Test run

```
$ alias='java -jar -Xmx4G /usr/local/share/cjam/cjam-0.6.5.jar'
$ time cjam lights-short.cjam <<< '[1 5 9 13 17]'
[2 8 4 16 4]

real    0m44.287s
user    3m47.426s
sys     0m1.821s
$ time cjam lights-fast.cjam <<< '[1 5 9 13 17]'
[2 8 4 16 4]

real    0m1.926s
user    0m2.383s
sys     0m0.098s

```

This gives us the following solution for the test case:

```
. . . L B
. L B . B
. B L . B
L B B . B
B . L . B

```

### Idea

For a given vector of wall placements, we iterate over all **33,554,432** vectors of light bulb placements, searching for one that satisfies the criteria.

If the bitwise AND of any pair of corresponding integers is non-zero, the spot is occupied by both a wall and a light bulb. We immediately discard such vectors.

We now convert the integers of wall and bulb placements to binary and subtract the resulting two-dimensional arrays. The result is a single 5 × 5 array, where **0** indices an empty space, **1** indicates a light bulb and **-1** indicates a wall.

We take this array and its transpose, and do the following for each row of each of them:

* For all runs of non-walls, we replace each **0** or **1** with the number of **1**s in this run.
* Then, we replace the **-1**s with **1**s.

We transpose the second array again (effectively applying the above to its *columns*) and take the element-wise bitwise OR of both arrays.

If there is any **0** left, the corresponding spot is not reached by light. Likewise, if there is any number greater than **1**, the are two non-separated light bulbs in the same row or column. Thus, a valid solution with produce an array that consists entirely of **1**s.

### Code

```
32q~:Q   e# Push 32, evaluate the input, and store the result in Q.
,m*      e# Get the length of Q (5) and push the vectors of {0, ..., 31}^5.
{        e# Filter; for each vector V:
  Q.&    e#   Take the bitwise and of the elements of V and Q.
  :|!    e#   Bitwise OR the results, and apply logical NOT.
},       e# Keep V if the result was 1.
{        e# Find; for each vector V:
  Q]     e#   Push Q and wrap V and Q in a array.
  {      e#   Map the following block over each of them:
    2b   e#     Convert the component to base 2.
    5Ue[ e#     Left-pad with 0s to a length of 5.
  }f%    e#
  ~      e#   Dump the modified V and Q on the stack.
  ..-    e#   Apply doubly vectorized subtraction.
  _z]    e#   Push a transposed copy of the result. Wrap both in an array.
  {      e#   Map the following block over each of them:
    Wa/  e#     Split at -1.
    _1fb e#     Add the integers of each chunk to count the number of 1s.
    .f|  e#     Vectorized mapped bitwise OR to replace each integer with the
         e#     number of 1s (possibly incremented).
    1a*  e#     Rejoin the chunks, separating by 1s.
  }f%    e#
  ~      e#   Dump both results on the stack.
  z      e#   Transpose the second one.
  ..|    e#   Doubly vectorized bitwise OR.
  :|     e#   Reduce the array by set union.
  1a=    e#   Check if the result is [1].
}=       e# If it is, push the vector and terminate the loop.
p        e# Print the item on the stack.

```

If there is no solution, `p` will be called on an empty stack, throwing an error and producing no output.

---
Tags: code-golf, puzzle-solver
---