Advent of Code 2020 - Day 8

This one was tough for me.
https://github.com/Introduction-to-Functional-Programming/simple_exercises/blob/main/adolfont/adventofcode/2020/day_08/lib/day08.ex

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

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.

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

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

https://github.com/JEG2/advent_of_code_2020/blob/main/day_08/handheld.exs

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

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

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…

https://github.com/al2o3cr/advent-of-code-2020/blob/main/day8/part1.exs

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.

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.