Advent of Code 2020 - Day 8

Loved part 2 today.

My solution, not clean but working. Everytime a branch fails (returns false) it tries another branch interpreting jmp as nop or vice versa – but only once tracked by the changed bool - finishes as soon as a valid branch has been found:

#!/usr/bin/env elixir

defmodule Day8 do
  def reduce(instr, ptr, state, changed) do
    case Map.pop(instr, ptr) do
      {{"nop", n}, instr} -> reduce(instr, ptr + 1, state, changed) || (unless changed, do: reduce(instr, ptr + n, state, true))
      {{"jmp", n}, instr} -> reduce(instr, ptr + n, state, changed) || (unless changed, do: reduce(instr, ptr + 1, state, true))
      {{"acc", n}, instr} -> reduce(instr, ptr + 1, state + n, changed)
      {nil, _instr} -> false
      {:fin, _instr} -> state
    end
  end
end

instr = File.read!("8.csv")
|> String.split("\n", trim: true)
|> Enum.with_index()
|> Enum.map(fn {row, idx} ->
  [op, num] = String.split(row)
  num = String.to_integer(num)
  {idx, {op, num}}
end)
|> Map.new()

instr = Map.put(instr, map_size(instr), :fin)
Day8.reduce(instr, 0, 0, false)
|> IO.inspect()

My solution for today. I think there might be some trick to the second part, but I went with the brute force approach.. change one instruction and check if the program terminates

defmodule Aoc2020.Day08 do
  def part1(program) do
    program
    |> Enum.into(%{})
    |> run_program()
  end

  def part2(input) do
    program =
      input
      |> Enum.into(%{})

    fix_program(program)
  end

  defp fix_program(program), do: fix_program(program, 0, program)

  defp fix_program(modified, address, original) do
    case run_program(modified) do
      {:crash, _} ->
        case original[address] do
          {"acc", _} ->
            fix_program(original, address + 1, original)

          instruction ->
            fix_program(Map.put(original, address, swap(instruction)), address + 1, original)
        end

      code ->
        code
    end
  end

  defp swap({"jmp", value}), do: {"nop", value}
  defp swap({"nop", value}), do: {"jmp", value}

  def run_program(program) do
    run_program(program, {0, 0, MapSet.new()})
  end

  defp run_program(program, {pc, acc, seen}) do
    if MapSet.member?(seen, pc) do
      {:crash, acc}
    else
      case program[pc] do
        nil ->
          {:exit, acc}

        instruction ->
          {next_pc, acc} = execute({pc, acc}, instruction)
          run_program(program, {next_pc, acc, MapSet.put(seen, pc)})
      end
    end
  end

  def execute({pc, acc}, {"nop", _}), do: {pc + 1, acc}
  def execute({pc, acc}, {"acc", value}), do: {pc + 1, acc + value}
  def execute({pc, acc}, {"jmp", offset}), do: {pc + offset, acc}

  def input_stream(path) do
    File.stream!(path)
    |> Stream.with_index()
    |> Stream.map(&parse/1)
  end

  def parse({line, index}) do
    [instruction, number] =
      line
      |> String.trim()
      |> String.split(" ", parts: 2)

    {index, {instruction, String.to_integer(number)}}
  end
end

input = Aoc2020.Day08.input_stream("input.txt")

Aoc2020.Day08.part1(input)
|> IO.inspect(label: "part1")

Aoc2020.Day08.part2(input)
|> IO.inspect(label: "part2")

Here’s mine. I used brute force for the second one too.

https://github.com/code-shoily/advent_of_code/blob/master/lib/2020/day_8.ex

I half brute forced it trying to fix only already ran instructions starting from the last fixable.

Edit: Thinking about it a bit more, and this may be very close to optimal solution. In test example it modifies code only once and in puzzle 10 times before finding correct one.

https://github.com/Damirados/AoC/blob/master/lib/event8.ex

Nothing exciting here!

defmodule Day08.Console do
  def run(program, acc \\ 0, pc \\ 0, seenpc \\ MapSet.new())

  # ran off the end
  def run(program, acc, pc, _seenpc) when pc == length(program), do: {acc, true}

  def run(program, acc, pc, seenpc) do
    {instruction, moveorinc} = Enum.at(program, pc)

    {nextpc, newacc} =
      case instruction do
        "nop" -> {pc + 1, acc}
        "acc" -> {pc + 1, acc + moveorinc}
        "jmp" -> {pc + moveorinc, acc}
      end

    if nextpc in seenpc do
      {acc, false}
    else
      run(program, newacc, nextpc, MapSet.put(seenpc, nextpc))
    end
  end
end

defmodule Day08 do
  alias Day08.Console

  def readinput() do
    File.read!("8.input.txt")
    |> String.split("\n", trim: true)
    |> Enum.map(fn line ->
      [instruction, moveorinc] =
        line
        |> String.replace("+", "")
        |> String.split()

      {instruction, String.to_integer(moveorinc)}
    end)
  end

  def part1(program \\ readinput()) do
    Console.run(program)
    |> elem(0)
  end

  def part2(program \\ readinput()) do
    modify(program)
  end

  def modify(program, start \\ 0)

  def modify(program, start) when start == length(program), do: :error

  def modify(program, start) do
    # find first nop or jmp after start
    # if moveorinc is not 0, modify it
    # run the program
    # repeat until it ends with {_, true}

    searchprogram = Enum.slice(program, start, length(program))

    changepos =
      Enum.find_index(searchprogram, fn {instruction, moveorinc} ->
        instruction in ["nop", "jmp"] and moveorinc != 0
      end)

    {instruction, moveorinc} = Enum.at(program, changepos + start)

    newinstruction =
      case instruction do
        "jmp" -> "nop"
        "nop" -> "jmp"
      end

    newprogram = List.replace_at(program, changepos + start, {newinstruction, moveorinc})

    case Console.run(newprogram) do
      {acc, true} -> acc
      {_, false} -> modify(program, changepos + start + 1)
    end
  end
end

I build a struct + proper API for the bootloader today, before even trying to get to the answers – the goal being someone should be able to understand the code even without knowing the problem. This approach made part two quite simple because all I needed to add was brute-forcing the intended instruction changes and attempting to run the bootloader for each attempt like for part 1.

https://github.com/LostKobrakai/aoc2020/commit/586e5ef8b3bf00697ddbc5f563c936d9e1506600

You have all data in place to not brute force it, just run it to first prevent infinite and attempt fixes only on visited instructions.

Today was fun
Run until find an error, change the first instruction, run again, change next instruction…
https://github.com/raerkeer/AdventOfCode_2020_Erlang/blob/main/day8.erl

This might be an option, but I’d need to change how bootloaders are run, which was nothing I wanted to do. Sure it’s more expensive this way, but the exception (a broken instruction set) should not result in a change for the norm (a fully functioning bootloader runner). It’s questionable how worthwhile those considerations are, but I’m trying to apply them like I might do in the realworld. If being able to run broken instructions would become a responsibility for the bootloader, then it might make sense to go with your approach.

Here’s part of my solution:

  def boot(program), do: run_program(program, 0, 0, [])

  def run_program(program, pointer, acc, history \\ []) do
    if pointer in history do
      {:started_loop, acc}
    else
      case Enum.at(program, pointer) do
        {:nop, _} -> run_program(program, pointer + 1, acc, [pointer | history])
        {:acc, arg} -> run_program(program, pointer + 1, acc + arg, [pointer | history])
        {:jmp, arg} -> run_program(program, pointer + arg, acc, [pointer | history])
        nil -> {:program_exited, acc}
      end
    end
  end

Any opinions on whether the if statement in my run_program is a code smell? I had wanted to use a guard but I don’t think this is possible.