Module aoc::year2018::day19

Go With The Flow

There are two parts to this problem:

• Reverse engineering the assembly in order to figure out what the program is doing.
• Implementing the program more efficiently in Rust.

Reverse Engineering

    Raw              | Pseudo-Assembly                  | Pseudo-Rust
    -----------------+----------------------------------+-----------------------------------
    #ip 1            | # a = 0 b = 2 c = 3 d = 4 e = 5  |
    addi 1 16 1      |           goto hotel             |
    seti 1 8 2       | alfa:     b = 1                  | for b in 1..=e {
    seti 1 5 4       | bravo:    d = 1                  |     for d in 1..=e {
    mulr 2 4 3       | charlie:  c = b * d              |
    eqrr 3 5 3       |           c = (c == e) ? 1: 0    |
    addr 3 1 1       |           if c == 1 goto delta   |         if b * d == e {
    addi 1 1 1       |           goto echo              |
    addr 2 0 0       | delta:    a += b                 |             a += b
    addi 4 1 4       | echo:     d += 1                 |
    gtrr 4 5 3       |           c = (d > e) ? 1: 0     |         }
    addr 1 3 1       |           if c == 1 goto foxtrot |
    seti 2 8 1       |           goto charlie           |     }
    addi 2 1 2       | foxtrot:  b += 1                 |
    gtrr 2 5 3       |           c = (b > e) ? 1: 0     |
    addr 3 1 1       |           if c == 1 goto golf    |
    seti 1 8 1       |           goto bravo             | }
    mulr 1 1 1       | golf:     goto end               |
    addi 5 2 5       | hotel:    e = 2                  |
    mulr 5 5 5       |           e = e * e              |
    mulr 1 5 5       |           e *= 19                |
    muli 5 11 5      |           e *= 11                |
    addi 3 $FIRST 3  |           c = $FIRST             |
    mulr 3 1 3       |           c *= 22                |
    addi 3 $SECOND 3 |           c += $SECOND           |
    addr 5 3 5       |           e += c                 | e = (22 * $FIRST + $SECOND) + 836
    addr 1 0 1       |           if a == 1 goto india   |
    seti 0 7 1       |           goto alfa              |
    setr 1 1 3       | india:    c = 27                 |
    mulr 3 1 3       |           c *= 28                |
    addr 1 3 3       |           c += 29                |
    mulr 1 3 3       |           c *= 30                |
    muli 3 14 3      |           c *= 14                |
    mulr 3 1 3       |           c *= 32                |
    addr 5 3 5       |           e += c                 | if a == 1 { e += 10550400 }
    seti 0 9 0       |           a = 0                  |
    seti 0 0 1       |           goto alfa              |
                     | end:                             |

The decoded assembly shows that the program is computing the sum of the divisors of a number n, using two nested loops for a total complexity in part two of O(n²) = O(10¹⁴).

Clearly there is some room for performance improvements. The interesting part is that we only need the two numbers $FIRST and $SECOND and can discard the rest of the input.

Rust Implementation

We compute the divisor sum using trial division. As we want the prime factors (instead of checking that n is prime) the asymptotic complexity is slightly lower in practice, being the square root of the largest prime factor of n instead of the square root of n itself.

As n is on the order of 10,000,000 this gives a worst case upper bound of √10000000 = 3162 when n is prime. However for most composite numbers the largest prime factor will be much smaller, on the order of 100,000 for an approximate complexity of √100000 = 316.

Functions

• divisor_sum 🔒
  Returns the sum of the divisors of an integer n, including 1 and n itself. For example 20 => 1 + 2 + 4 + 5 + 10 + 20 = 42.
• parse
  Extracts the two unique numbers from the input then calculates the composite numbers needed for both parts.
• part1
• part2

Type Aliases

• Input 🔒