Advent of Code 2020 - Day 8

dominicletz · December 8, 2020, 6:09am

This topic is about Day 8 of the Advent of Code 2020 .

Thanks to @egze, we have a private leaderboard:
https://adventofcode.com/2020/leaderboard/private/view/39276

The join code is:
39276-eeb74f9a

dominicletz · December 8, 2020, 6:12am

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()

kwando · December 8, 2020, 6:39am

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")

code-shoily · December 8, 2020, 6:50am

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

github.com

code-shoily/advent_of_code/blob/master/lib/2020/day_8.ex

defmodule AdventOfCode.Y2020.Day8 do
  @moduledoc """
  Problem Link: https://adventofcode.com/2020/day/8
  """
  use AdventOfCode.Helpers.InputReader, year: 2020, day: 8

  def run_1, do: input!() |> process() |> exec() |> elem(1)
  def run_2, do: input!() |> process() |> fix()
  def run, do: {run_1(), run_2()}

  def process(input), do: Enum.map(String.split(input, "\n"), &parse/1)

  defp exec(prog), do: exec(prog, 0, 0, %{})
  defp exec(_, cur, acc, hist) when is_map_key(hist, cur), do: {:cont, acc}
  defp exec(prog, cur, acc, _) when cur >= length(prog), do: {:halt, acc}

  defp exec(prog, cur, acc, hist) do
    case Enum.at(prog, cur) do
      {:acc, val} -> exec(prog, cur + 1, acc + val, Map.put(hist, cur, true))
      {:nop, _} -> exec(prog, cur + 1, acc, Map.put(hist, cur, true))

This file has been truncated. show original

Damirados · December 8, 2020, 7:01am

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.

github.com

Damirados/AoC/blob/master/lib/event8.ex

defmodule Event8 do
  def run do
    IO.puts("Test part1: #{part1("input/event8/test.txt")}")
    IO.puts("Puzzle part1: #{part1("input/event8/puzzle.txt")}")
    IO.puts("Test part2: #{part2("input/event8/test.txt")}")
    IO.puts("Puzzle part2: #{part2("input/event8/puzzle.txt")}")
  end

  def part1(path) do
    input_stream(path)
    |> Enum.into([])
    |> run_code()
    |> elem(1)
  end

  def part2(path) do
    input_stream(path)
    |> Enum.into([])
    |> run_code2()
  end

This file has been truncated. show original

faried · December 8, 2020, 7:08am

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

LostKobrakai · December 8, 2020, 8:28am

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.

Damirados · December 8, 2020, 8:36am

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.

Rainer · December 8, 2020, 8:41am

Today was fun
Run until find an error, change the first instruction, run again, change next instruction…

github.com

raerkeer/AdventOfCode_2020_Erlang/blob/main/day8.erl

-module(day8).
-export([run/0]).

run()->
    Instructions = load_file("day8input.txt"),
    {part1(Instructions, [], 0, 1), part2(Instructions, 1)}.

part1(Instructions, PositionsVisited, Acc, Pos)->
    case lists:member(Pos, PositionsVisited) of
        true -> {infiniteloop, Acc};
        false ->
            {Instr, Val} = lists:nth(Pos, Instructions),
            case Instr of
                "nop" -> part1(Instructions, [Pos | PositionsVisited], Acc, Pos + 1);
                "acc" -> part1(Instructions, [Pos | PositionsVisited], Acc + Val, Pos + 1);
                "jmp" -> part1(Instructions, [Pos | PositionsVisited], Acc, Pos + Val);
                endofcode -> {finished, Acc}
            end
        end.

This file has been truncated. show original

LostKobrakai · December 8, 2020, 8:47am

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.

michaelvigor · December 8, 2020, 11:57am

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.

adamu · December 8, 2020, 12:45pm

Your answer is freakishly similar to mine…

defmodule Day8Part2 do
  def find_corrupted(instrs), do: find_corrupted(Map.to_list(instrs), instrs, :loop)
  def find_corrupted(_rest, _instrs, {:terminated, acc}), do: acc
  def find_corrupted([{idx, {op, arg}} | rest], instrs, :loop) do
    result =
      instrs
      |> Map.put(idx, toggle_op(op, arg))
      |> try_boot()

    find_corrupted(rest, instrs, result)
  end

  def try_boot(instrs), do: try_boot(instrs, 0, 0, MapSet.new())
  def try_boot(instrs, idx, acc, _seen) when idx == map_size(instrs), do: {:terminated, acc}
  def try_boot(instrs, idx, acc, seen) do
    if MapSet.member?(seen, idx) do
      :loop
    else
      seen = MapSet.put(seen, idx)
      {idx, acc} = execute(instrs[idx], idx, acc)
      try_boot(instrs, idx, acc, seen)
    end
  end

  def execute({"nop", _arg}, idx, acc), do: {idx + 1, acc}
  def execute({"jmp", arg}, idx, acc), do: {idx + arg, acc}
  def execute({"acc", arg}, idx, acc), do: {idx + 1, acc + arg}

  def toggle_op("acc", arg), do: {"acc", arg}
  def toggle_op("nop", arg), do: {"jmp", arg}
  def toggle_op("jmp", arg), do: {"nop", arg}

  def input_to_instrs(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.map(&String.split/1)
    |> Enum.with_index()
    |> Map.new(fn {[op, arg], idx} -> {idx, {op, String.to_integer(arg)}} end)
  end

  def run do
    File.read!("input")
    |> input_to_instrs()
    |> find_corrupted()
    |> IO.puts()
  end
end

Day8Part2.run()

Full code.

al2o3cr · December 8, 2020, 4:47pm

Stream made this problem pretty nice, since it’s possible to work with “infinite” output without actually computing it all. In particular, they allowed the “execute” logic to be entirely independent of the “check for loop” code - that would have come in handy if part2 was “what’s in the accumulator the third time through the loop” or something…

github.com

al2o3cr/advent-of-code-2020/blob/main/day8/part1.exs

defmodule GameConsole do
  def read(stream) do
    stream
    |> Stream.map(&GameConsole.parse/1)
    |> Stream.with_index()
    |> Map.new(fn {v, k} -> {k, v} end)
  end

  def parse(line) do
    [instruction_s, offset_s] = Regex.run(~r/^(nop|jmp|acc) ([+-]\d+)/, line, capture: :all_but_first)

    case {instruction_s, String.to_integer(offset_s)} do
      {"nop", _} -> :nop
      {"jmp", offset} -> {:jmp, offset}
      {"acc", operand} -> {:acc, operand}
    end
  end

  def execute(program, {pc, acc}) do
    case program[pc] do

This file has been truncated. show original

kwando · December 8, 2020, 5:17pm

This one is really clever, it completes in 38 microseconds instead of 28ms which my brute force method does

ricardo-h · December 9, 2020, 2:37am

part 2

defmodule Advent.Day8b do

  def start(file \\ "/tmp/input.txt") do
    File.read!(file)
    |> String.split()
    |> load_program([])
    |> fix_program(0)
  end

  defp fix_program(program, replace_cmd), do:
  fix_program(program, replace_cmd, tuple_size(program) - 1)

  defp fix_program(program, replace_cmd, last_line) do
    {line, acc} = execute_program(program, replace_cmd, 0, 0, %{}, last_line)
    case line - 1 == last_line do
      true -> acc
      false -> fix_program(program, replace_cmd + 1, last_line)
    end
  end

  defp execute_program(_, _, line, acc, _, last_line) when last_line < line, do: {line, acc}
  defp execute_program(program, replace_cmd, line, acc, executed, last_line), do:
    execute_line(program |> elem(line), replace_cmd, program, line, acc, Map.put(executed, line, 1), Map.get(executed, line) != nil, last_line)

  defp execute_line(_, _, _, line, acc, _, true, _), do: {line, acc}
  defp execute_line({"nop", 0}, replace_cmd, program, line, acc, executed, _, last_line), do:
    execute_program(program, replace_cmd, line + 1, acc, executed, last_line)
  defp execute_line({"nop", v}, 0, program, line, acc, executed, _, last_line), do:
    execute_program(program, -1, line + v, acc, executed, last_line)
  defp execute_line({"nop", _}, replace_cmd, program, line, acc, executed, _, last_line), do:
    execute_program(program, replace_cmd - 1, line + 1, acc, executed, last_line)
  defp execute_line({"acc", v}, replace_cmd, program, line, acc, executed, _, last_line), do:
    execute_program(program, replace_cmd, line + 1, acc + v, executed, last_line)
  defp execute_line({"jmp", _}, 0, program, line, acc, executed, _, last_line), do:
    execute_program(program, -1, line + 1, acc, executed, last_line)
  defp execute_line({"jmp", v}, replace_cmd, program, line, acc, executed, _, last_line), do:
    execute_program(program, replace_cmd - 1, line + v, acc, executed, last_line)

  defp load_program([], program), do: program |> Enum.reverse() |> List.to_tuple()
  defp load_program([cmd, vl | t], program), do: load_program(t, [{cmd, String.to_integer(vl)} | program])

end

JEG2 · December 9, 2020, 4:22am

I got to use some cool Stream functions to solve this one:

github.com

JEG2/advent_of_code_2020/blob/main/day_08/handheld.exs

defmodule Handheld do
  defmodule Operation do
    def parse("acc " <> arg), do: {:acc, String.to_integer(arg)}
    def parse("jmp " <> arg), do: {:jmp, String.to_integer(arg)}
    def parse("nop " <> arg), do: {:nop, String.to_integer(arg)}
  end

  defmodule Program do
    def parse(path) do
      path
      |> File.stream!()
      |> Stream.map(&String.trim/1)
      |> Enum.with_index()
      |> Enum.into(Map.new(), fn {line, i} -> {i, Operation.parse(line)} end)
    end
  end

  defmodule VM do
    def new(program), do: {program, 0, 0}

This file has been truncated. show original

aaronnamba · December 9, 2020, 4:25am

I keep forgetting you can do that. Thanks for the reminder!

stevensonmt · December 9, 2020, 6:45am

Part 1 was easy peasy but then I made some dumb errors on Part 2 that kept me in an infinite loop. Had a hard time tracking it down. Felt very meta. Anyway, fun problem.

defmodule Day8 do
  import NimbleParsec

  @input File.read!("lib/input.txt")

  defmodule ParsingHelp do
    defparsec(
      :command_lexer,
      ascii_string([?a..?z], 3)
      |> ignore(string(" "))
      |> choice([
        string("+"),
        string("-")
      ])
      |> integer(min: 1, max: 4)
    )
  end

  def lex_input() do
    @input
    |> String.split("\n", trim: true)
    |> Enum.map(&ParsingHelp.command_lexer(&1))
    |> Enum.map(&elem(&1, 1))
    |> Enum.with_index()
  end

  def parse() do
    lex_input()
    |> parse()
    |> elem(1)
  end

  def parse([]) do
    0
  end

  def parse([h | _rest] = list) do
    parse(h, list, {0, []})
  end

  #handles case of last command progressing beyond last command
  def parse(nil, _, {acc, _}) do
    {:ok, acc}
  end

  def parse({[cmd, sign, val], curr_ndx}, list, {acc, visited}) do
    sign =
      case sign do
        "-" -> -1
        "+" -> 1
      end

    cond do
      Enum.member?(visited, curr_ndx) ->
        {:error, acc}

      curr_ndx >= Enum.count(list) ->
        {:ok, acc}

      cmd == "nop" ->
        parse(Enum.at(list, curr_ndx + 1), list, {acc, [curr_ndx | visited]})

      cmd == "jmp" ->
        parse(Enum.at(list, curr_ndx + sign * val), list, {acc, [curr_ndx | visited]})

      cmd == "acc" ->
        parse(
          Enum.at(list, curr_ndx + 1),
          list,
          {acc + sign * val, [curr_ndx | visited]}
        )
    end
  end

  def try_fix() do
    lexed = lex_input()
    try_fix(List.first(lexed), lexed, {0, []})
  end

  def try_fix([], _, {acc, _}) do
    acc
  end

  def try_fix({[cmd, sign, val], ndx}, list, {acc, visited}) do
    multiplier =
      case sign do
        "-" -> -1
        "+" -> 1
      end

    case cmd do
      "nop" ->
        case parse({["jmp", sign, val], ndx}, list, {acc, visited}) do
          {:error, _} ->
            try_fix(Enum.at(list, ndx + 1), list, {acc, [ndx | visited]})

          {:ok, n} ->
            n
        end

      "jmp" ->
        case parse({["nop", sign, val], ndx}, list, {acc, visited}) do
          {:error, _} ->
            try_fix(Enum.at(list, multiplier * val + ndx), list, {acc, [ndx | visited]})

          {:ok, n} ->
            n
        end

      "acc" ->
        try_fix(Enum.at(list, ndx + 1), list, {acc + multiplier * val, [ndx | visited]})
    end
  end
end

IO.inspect(Day8.parse())
IO.inspect(Day8.try_fix())

As the saying goes, old ugly is better than old nothing.

egze · December 13, 2020, 10:05am

Finally got around to finishing day 8

GitHub

defmodule Aoc.Y2020.D8 do
  use Aoc.Boilerplate,
    transform: fn raw ->
      raw
      |> String.split("\n")
      |> Enum.map(fn line ->
        [instruction, value] = line |> String.split(" ")
        {instruction, String.to_integer(value)}
      end)
      |> Enum.with_index()
      |> Enum.map(fn {v, i} -> {i, v} end)
      |> Enum.into(%{})
    end

  def part1(input \\ processed()) do
    Stream.iterate(0, &(&1 + 1))
    |> Enum.reduce_while({0, 0, input}, fn _i, {index, sum, instructions} ->
      case Map.get(instructions, index) do
        {"nop", _} -> {:cont, {index + 1, sum, Map.delete(instructions, index)}}
        {"jmp", jmp} -> {:cont, {index + jmp, sum, Map.delete(instructions, index)}}
        {"acc", i} -> {:cont, {index + 1, sum + i, Map.delete(instructions, index)}}
        nil -> {:halt, sum}
      end
    end)
  end

  def part2(input \\ processed()) do
    key = (input |> Map.keys() |> Enum.sort() |> List.last()) + 1
    instructions = Map.put(input, key, :end)

    instructions
    |> run(0, 0, [], nil)
    |> List.flatten()
    |> Enum.find(&(&1 != :infinite_loop))
  end

  defp run(instructions, sum, index, visited, corrected_index) do
    case {Map.get(instructions, index), corrected_index, index in visited} do
      {:end, _, false} ->
        sum

      {_, _, true} ->
        :infinite_loop

      {{"nop", i}, nil, false} ->
        [
          run(instructions, sum, index + i, [index | visited], index),
          run(instructions, sum, index + 1, [index | visited], nil)
        ]

      {{"nop", _}, ^corrected_index, false} ->
        run(instructions, sum, index + 1, [index | visited], corrected_index)

      {{"jmp", jmp}, nil, false} ->
        [
          run(instructions, sum, index + 1, [index | visited], index),
          run(instructions, sum, index + jmp, [index | visited], nil)
        ]

      {{"jmp", jmp}, ^corrected_index, false} ->
        run(instructions, sum, index + jmp, [index | visited], corrected_index)

      {{"acc", i}, ^corrected_index, false} ->
        run(instructions, sum + i, index + 1, [index | visited], corrected_index)
    end
  end
end

adolfont · December 16, 2020, 12:07am

This one was tough for me.

github.com

Introduction-to-Functional-Programming/simple_exercises/blob/main/adolfont/adventofcode/2020/day_08/lib/day08.ex

defmodule Day08 do
  @moduledoc """
  Advent of Code - Day 8: Handheld Halting https://adventofcode.com/2020/day/8
  """

  def parse_instructions(string) do
    string
    |> String.split("\n", trim: true)
    |> Enum.map(&parse_instruction/1)
  end

  defp parse_instruction("acc " <> value) do
    {:acc, String.to_integer(value)}
  end

  defp parse_instruction("jmp " <> value) do
    {:jmp, String.to_integer(value)}
  end

  defp parse_instruction("nop " <> value) do

This file has been truncated. show original