Advent of Code 2020: "Handheld Halting" - Day 8

You fixed the colours of the bags yesterday) and security allowed you to leave the baggage section and go get your ice cream before you board your next flight. On the flight the kid next to you recognizes you as the great hacker you are, and asks you to fix a problem with the handheld game console. Go and hack the bootloader while no documentation is available because the mobile internet is off. Turns out someone coded an infinite loop into the bootloader, and missed that fact during testing. What testing, do you ask? Well, let’s not jump too deep into details, you have to hack a bootloader and make a kid happy. It’s Christmas soon, after all! And your cocktail is waiting!

Task 1: The assembler instructions are easy to read, to make the kid happy you just have to figure out the state of the accumulator before the bootloader repeats its set of instructions into another great infinite loop. Not sure how that fixes the problem, but ok.

Task 2: The instruction list is corrupt. But not in the way you think. The code is supposed to produce a buffer overrun, jump outside of the instruction list and stop. Modern operating systems would prevent this and abort the program, here that is “normal termination”. Change exactly one jmp into a nop or vice versa, but do not change the operand. Whichever change aborts the program by jumping outside the code - the accumulator state is what we are looking for. Hopefully the number is high enough to pay for all the cocktails!

Preparation

Today’s data is a list of opcodes and operands, specified line by line. Like previous days I load that into a TEXT field:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
DROP TABLE IF EXISTS day8;

CREATE TABLE day8 (
    id      SERIAL NOT NULL PRIMARY KEY,
    value   TEXT
);

COPY day8 (value) FROM STDIN;
acc -7
acc +6
acc +4
nop +191
jmp +199
acc +44
acc -9
jmp +505
acc -12
acc +45
...
\.

Verify that I have data:

1
2
3
4
5
SELECT COUNT(*) FROM day8;
 count
-------
   624
(1 row)

In order to do something useful with the input, I need to split the instructions into opcode and operator. That’s easy, they are always separated by a space. A similar way was used yesterday to split the text into parts.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
WITH RECURSIVE _day8_split_data AS (
    SELECT id,
           REGEXP_MATCHES(value, '^([^ ]+) (.*)') AS split
      FROM day8
),
day8_split_data AS (
    SELECT id,
           split[1] AS opcode,
           split[2] AS operand
      FROM _day8_split_data
)
SELECT * FROM day8_split_data;

The CTE is similar to what I used yesterday: loop over the data in the table, and split it by the space. The _day8_split_data CTE does the split, the day8_split_data extracts the data from the array and presents a clean result. Again, that can be combined into a single query, but this way the processing is better shown, The resulting data:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
 id  | opcode | operand
-----+--------+---------
   1 | acc    | -7
   2 | acc    | +6
   3 | acc    | +4
   4 | nop    | +191
   5 | jmp    | +199
   6 | acc    | +44
   7 | acc    | -9
   8 | jmp    | +505
   9 | acc    | -12
  10 | acc    | +45
  11 | jmp    | +204
  12 | jmp    | +129
  13 | acc    | +17
  14 | nop    | +287
  15 | jmp    | +584
  16 | acc    | +16
  17 | jmp    | +363

Task 1

The instruction set reminds me when I first started programming, a 6502 CPU in a CBM Model 4032. Basic was too slow, but assembler documentation for the 6502 CPU was available (mostly for the C64 though, but the 6502 and 6510 CPUs are almost identical). Using the one accumulator and two index registers along with the program counter was quite a thing back then. And it was fast, compared to the basic programs on the same machine!

The task at hand is to find out when the next iteration of an infinite loop starts. For this I need to know how many instructions are in the list:

1
2
3
4
num_instructions AS (
    SELECT COUNT(*) AS count
      FROM day8_split_data
)

And then “emulate” what the CPU is doing. There are only three commands in the list:

nop: No Op - does nothing
jmp: Jump forward or backward, depending on the operand
acc: Add or deduct to/from the accumulator, depending on the operand

The “nop” command can be ignored. The jmp command then changes the program counter, and the acc program the state of the accumulator. What’s not checked here: out of bound. The jmp command could possibly jump to a position before the start, or after the end of the list. And the accumulator could overrun or underrun its data type. These are typical scenarious for buffer overflow errors, and modern systems should detect this and then abort.

The funny thing: nothing ever happens, at all. The accumulator is changed, but there are no checks, or other instructions. It’s just shifting bits around in the accumulator.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
run AS (
    SELECT 1 AS tick,
           0 AS accumulator,
           1 AS program_counter
     UNION ALL
    SELECT run.tick + 1 AS tick,
           run.accumulator + CASE WHEN opcode = 'acc'
                                  THEN CAST(sd.operand AS INT4)
                                  ELSE 0 END AS accumulator,
           run.program_counter + CASE WHEN opcode = 'jmp'
                                 THEN CAST(sd.operand AS INT4)
                                 ELSE 1 END AS program_counter
      FROM run,
           day8_split_data sd
     WHERE run.program_counter = sd.id
       AND run.tick < (SELECT count
                         FROM num_instructions)
)

Above code starts at position 1, with the accumulator set to 0. It then uses the acc and jmp commands to modify the program counter and the accumulator.

Pour all of this together, keep a state for the program_counter, which is the position which was “executed” in the list. Once it repeats the job is done and accumulator holds the result:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
WITH RECURSIVE _day8_split_data AS (
    SELECT id,
           REGEXP_MATCHES(value, '^([^ ]+) (.*)') AS split
      FROM day8
),
day8_split_data AS (
    SELECT id,
           split[1] AS opcode,
           split[2] AS operand
      FROM _day8_split_data
),
num_instructions AS (
    SELECT COUNT(*) AS count
      FROM day8_split_data
),
run AS (
    SELECT 1 AS tick,
           0 AS accumulator,
           1 AS program_counter
     UNION ALL
    SELECT run.tick + 1 AS tick,
           run.accumulator + CASE WHEN opcode = 'acc'
                                  THEN CAST(sd.operand AS INT4)
                                  ELSE 0 END AS accumulator,
           run.program_counter + CASE WHEN opcode = 'jmp'
                                 THEN CAST(sd.operand AS INT4)
                                 ELSE 1 END AS program_counter
      FROM run,
           day8_split_data sd
     WHERE run.program_counter = sd.id
       AND run.tick < (SELECT count
                         FROM num_instructions)
)
SELECT accumulator
  FROM run
 WHERE EXISTS (
       SELECT
         FROM run AS previous_run
        WHERE run.program_counter = previous_run.program_counter
          AND run.tick > previous_run.tick
              )
LIMIT 1;

This loops quite a few times, but only the first run is what we are looking for:

1
2
3
4
 accumulator
-------------
        2058
(1 row)

Task 2

Let’s do opcode switching on the fly, because, you know, emulating a CPU in another CPU …

1
2
3
4
5
           run.program_counter + CASE WHEN (opcode = 'jmp' AND
                                            new_opcode <> program_counter) OR
                                           (opcode = 'nop' AND
                                            new_opcode = program_counter)

When I encounter a jmp or a nop I switch them. Otherwise the run CTE function for task 2 is pretty much similar to task 1. I need to run recursive over the instructions to find the missing one, the INNER JOIN changes into a LEFT OUTER JOIN for that. And the “other” instruction is stored in $new_opcode. The first part of the CTE also excludes acc instructions from evaluation by listing the two opcodes which should be switched. $outside is a flag which shows if the program counter goes outside of the instruction list. According to the instructions there is only one possibility for this.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
WITH RECURSIVE _day8_split_data AS (
    SELECT id,
           REGEXP_MATCHES(value, '^([^ ]+) (.*)') AS split
      FROM day8
),
day8_split_data AS (
    SELECT id,
           split[1] AS opcode,
           split[2] AS operand
      FROM _day8_split_data
),
num_instructions AS (
    SELECT COUNT(*) AS count
      FROM day8_split_data
),
run AS (
    SELECT 1 AS tick,
           0 AS accumulator,
           1 AS program_counter,
           id AS new_opcode,
           FALSE AS outside
      FROM day8_split_data
     WHERE opcode IN ('nop', 'jmp')
     UNION ALL
    SELECT run.tick + 1 AS tick,
           run.accumulator + CASE WHEN opcode = 'acc'
                                  THEN CAST(sd.operand AS INT4)
                                  ELSE 0 END AS accumulator,
           run.program_counter + CASE WHEN (opcode = 'jmp' AND
                                            new_opcode <> program_counter) OR
                                           (opcode = 'nop' AND
                                            new_opcode = program_counter)
                                 THEN CAST(sd.operand AS INT4)
                                 ELSE 1 END AS program_counter,
           new_opcode AS new_opcode,
           opcode IS NULL AS outside
      FROM run
      LEFT OUTER JOIN day8_split_data sd ON run.program_counter = sd.id
     WHERE run.tick < (SELECT count
                         FROM num_instructions)
       AND NOT outside
)
SELECT accumulator
  FROM run
 WHERE outside IS TRUE;

The accumulator state once the code overruns:

1
2
3
4
 accumulator
-------------
        1000
(1 row)

Categories: [Sql]

Tags: [Advent] [Advent-of-Code] [Challenge] [Ice-Cream] [Icecream] [Postgresql] [Psql] [Sql]

Preparation

Task 1

Task 2

Friends