Notebook

Day 21 - boolean logic¶

For part 1, I can see from the springscript example that the robot can jump across three holes (NOT D J). Given that it only has sensors for the next 4 locations, that's quite helpful, and we do not want to jump if there is a hole at D.

So we need it to instruct to jump if a) there is a hole ahead, and b) we can land again. That's

$$ (\lnot A \lor \lnot B \lor \lnot C) \land D $$

So at least one of A, B or C is false (not ground, so a hole), and D is true (there is ground). We can use the T temporary register to record the required NOT outcomes, then OR those with the J register, then finally AND the outcome of those with D. Remember that J and T start out false:

NOT A J   # if A is a hole perhaps jump
NOT B T   # or if B is a hole
OR  T J   # perhaps jump
NOT C T   # or if C is a hole
OR  T J   # perhaps jump
AND D J   # but only if D is ground

That's 6 instructions. Using De Morgan's laws we can transform a group of $(\lnot R_1 \lor \lnot R_2 \lor \lnot \cdots)$ to $\lnot(R_1 \land R_2 \land \ldots)$ and so save an instruction:

OR  A T   # copy A to T, if A is ground
AND B T   # and if B is ground
AND C T   # and C is ground
NOT T J   # if none of that is true, jump
AND D J   # but only if D is ground

In [1]:

from __future__ import annotations

from typing import List, Sequence, Union

from intcode import CPU, ioset


def exec_springscript(
    memory: List[int], script: Sequence[Union[bytes, str]], exec: bytes = b"WALK"
) -> int:
    """Accepts springscript lines with extra whitespace and comments after #"""
    if isinstance(exec, str):
        exec = exec.encode("ASCII")
    lines = []
    for line in script:
        if isinstance(line, str):
            line = line.encode("ASCII")
        if b"#" in line:
            line = line.partition(b"#")[0]
        # normalise whitespace
        line = b" ".join(line.split())
        if line:
            lines.append(line)
    if lines[-1] != exec:
        lines.append(exec)
    springscript = b"\n".join(lines) + b"\n"
    outputs, opcodes = ioset(*springscript)
    CPU(opcodes).reset(memory).execute()

    if 0 <= outputs[-1] < 256:
        raise ValueError(bytes(outputs).decode("ASCII"))
    return outputs[-1]

In [2]:

import aocd

data = aocd.get_data(day=21, year=2019)
memory = list(map(int, data.split(",")))

In [3]:

part1_springscript = """\
OR  A T   # copy A to T, if A is ground
AND B T   # and if B is ground
AND C T   # and C is ground
NOT T J   # if none of that is true, jump
AND D J   # but only if D is ground
""".splitlines()
print("Part 1:", exec_springscript(memory, part1_springscript))

Part 1: 19352720

Part 2¶

Now we are told we can look further. I'm going to assume this means we only want to enter an area if we know we can cross the next 9 positions. From experiments it appears that the bot will walk one step after a jump that we can jump twice and so can test the options for 2 different positions after the second jump (H and I), we need to make sure we can make those jumps. Given that the bot will re-evaluate, on landing on D, how to proceed from there, we want to avaid jumping into a situation we can't handle from that point.

Here's the first such situation we can handle; we can jump across to D, and we can jump across to H, so we are fine, and presumably we can jump from H onwards if I is a hole:

@
##???#???#?
^ ABCDEFGHI
|
We are here, to jump from the next tile, distance 4, to D

We can also handle walking a single step, then evaluate if we need to jump again:

@
##???##????
  ABCDEFGHI

Together with the logic of part 1, that's:

$$ (\lnot A \lor \lnot B \lor \lnot C) \land D \land (H \lor E) $$

which turns into the following springscript:

OR  A T   # copy A to T, if A is ground
AND B T   # and if B is ground
AND C T   # and C is ground
NOT T J   # if none of that is true, jump
AND D J   # but only if D is ground
# we need to copy H to T to ignore
# the previous value of T
NOT H T   # not H is the inverse of H
NOT T T   # not T is now equal to H, true if H is ground
OR  E T   # or if E is ground
AND T J   # then confirm the jump

9 instructions, so well within the limit.

In [4]:

part2_springscript = """\
OR  A T   # copy A to T, if A is ground
AND B T   # and if B is ground
AND C T   # and C is ground
NOT T J   # if none of that is true, jump
AND D J   # but only if D is ground
# we need to copy H to T to ignore
# the previous value of T
NOT H T   # not H is the inverse of H
NOT T T   # not T is now equal to H, true if H is ground
OR  E T   # or if E is ground
AND T J   # then confirm the jump
""".splitlines()
print("Part 2:", exec_springscript(memory, part2_springscript, "RUN"))

Part 2: 1143652885