Advent of Code 2020 - Day 8

Power BI / DAX / Power Query / Advent of Code 2020

In day 8 we find a some weird infinite loop on a handheld device. To fix this problem we are asked to create a program that goes trough a stack of instructions.

nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
jmp -4
acc +6

And after we find where the infinite loop is located we replace the bad command with the correct instruction.

If you want to follow along please download AdventOfCode2020.pbit and check Day 1 post for instructions.

Part 1

To start we need to develop a way of returning the value of the accumulator right before the infinite loop starts. If you haven’t read the instructions on the page here’s a quick recap:

  • acc – Increases or decreases the accumulator with it’s argument
  • jmp – Jump to the instruction relative to it’s argument
  • nop – No Operation, the stack pointer is incremented by 1 and the next operation is executed

After some basic transformations we get to this step:

I have added an index so we can keep track of the visited positions. If we return to an already visited position we will be in the start of a infinite loop. Here’s my Power Query function that returns the value right after we find the infinite loop:

(t as table) =>
let
    maxInstruction = Table.RowCount(t) - 1,
    listOfInstructions = List.Buffer(t[Instruction]),
    listOfValues = List.Buffer(t[Value]),
    runInstructions =
        List.Generate(
            () => [CurrentRow=0, Visited={}, Acc=0],
            each not List.Contains([Visited], [CurrentRow]) and [CurrentRow] <= maxInstruction,
            each [
                    CurrentRow =
                            if listOfInstructions{[CurrentRow]} = "jmp"
                            then  [CurrentRow] + listOfValues{[CurrentRow]}
                            else  [CurrentRow] + 1,
                    Visited = [Visited] & { [CurrentRow] },
                    Acc = if listOfInstructions{CurrentRow} = "acc"
                            then [Acc] + listOfValues{CurrentRow}
                            else [Acc]
                ]
        ),
    lastLine = List.Last(runInstructions)
in
    [
        Value = lastLine[Acc],
        RanToTheEnd = maxInstruction = lastLine[CurrentRow]
    ]

We use the List.Generate to loop each instruction storing the visited postions in the Visited list. In each position we check the instruction and act accordingly adding the current value to the Acc and adjusting the next visited position.

The return value is a record on which the first position is the value of the accumulator and the second a boolean. If this last value is TRUE we know that we were able to get to the last instruction of code, consequently there are no infinite loops present.

Part 2

Apparently there is exactly one instruction corrupted. Somewhere in the program, either a jmp is supposed to be a nop, or a nop is supposed to be a jmp.

And what this means is that we need to generate all the possible list of instructions replacing just one instruction on each.

The general idea seems to be:

  1. Replace one instruction on the original list
  2. Check if we get to the end

To make a substitution we can use a function like this:

(tt as table, x as number) =>
let
    t = Table.Buffer(tt),
    res = Table.ReplaceValue(t,
            each [Instruction],
            each if [Index] = x and [Instruction] = "jmp"
                    then "nop"
                    else if [Index] = x and [Instruction] = "nop"
                        then "jmp"
                        else [Instruction],
            Replacer.ReplaceText,
            {"Instruction"})
in
    res

We receive a table of instructions and the index of the position we want to replace and return the new set of instructions.

Getting the positions of the instructions to replace:

instructionsToReplace =
     List.Buffer(Table.SelectRows(buffer, each List.Contains({"jmp", "nop"}, [Instruction]))[Index])

And the master loop:

p2Value =
        List.Generate(
            () => [
                Iterator = 0,
                CurrentTable = fnRunInstructions(
                                   fnReplaceInstruction(buffer,instructionsToReplace{0})),
                Stop = false
            ],
            each not [Stop],
            each [
                Iterator = [Iterator] + 1,
                CurrentTable = fnRunInstructions(
                                  fnReplaceInstruction(buffer,instructionsToReplace{[Iterator]})),
                Stop = [CurrentTable][RanToTheEnd]
            ],
        each [CurrentTable]
        )

We replace one instruction in the code and run the code. If we get to the end we stop and return the result, otherwise we keep looping.

Conclusion

Another interesting problem with techniques we can reuse when working with tables of list of movements, e.g. stocks. We can generate aggregate tables with the values of the stock on the end of month so that our DAX is faster. Instead of summing all the movements since the beginning of times we can just sum since the last aggregate checkpoint.

Have fun!!

 Share!