ExUnit.start()

defmodule HandheldHaltingTest do
  use ExUnit.Case
  doctest HandheldHalting
  test "new machine has ip 0" do
    assert Machine.init().ip == 0
  end
  test "new machine has acc 0" do
    assert Machine.init().acc == 0
  end
  test "operation NOP" do
    next = Machine.init() |> Machine.apply({:nop})
    assert next.ip == 1
    assert next.acc == 0
  end
  test "operation ACC" do
    next = Machine.init() |> Machine.apply({:acc, 23})
    assert next.ip == 1
    assert next.acc == 23
  end
  test "operation JMP" do
    next = Machine.init() |> Machine.apply({:jmp, 22})
    assert next.ip == 22
    assert next.acc == 0
  end
  test "parse operation" do
    assert HandheldHalting.parse_operation("nop +0") == {:nop}
    assert HandheldHalting.parse_operation("acc +1") == {:acc, 1}
    assert HandheldHalting.parse_operation("jmp +4") == {:jmp, 4}
    assert HandheldHalting.parse_operation("jmp -3") == {:jmp, -3}
  end
  test "parse program" do
    example_string = File.read!("example")
    parsed_program =
      String.split(example_string, "\n", trim: true)
      |> Enum.map(&HandheldHalting.parse_operation/1)
    assert HandheldHalting.parse_program(example_string) == parsed_program
  end
  test "init machine with program" do
    example_program = HandheldHalting.parse_program(File.read!("example"))
    machine = Machine.init(example_program)
    assert machine.program == example_program
  end
  test "visited instructions" do
    machine = Machine.init()
    assert machine.visited == []
    machine_2 = machine |> Machine.apply({:nop})
    assert machine_2.visited == [0]
    machine_3 = machine_2 |> Machine.apply({:nop})
    assert machine_3.visited == [1, 0]
  end
  test "stepping through program" do
    machine = [{:nop}, {:acc, 4}, {:acc, -10}] |> Machine.init()
    assert machine.ip == 0
    assert machine.acc == 0
    assert machine.visited == []
    machine = machine |> Machine.step()
    assert machine.ip == 1
    assert machine.acc == 0
    assert machine.visited == [0]
    machine = machine |> Machine.step()
    assert machine.ip == 2
    assert machine.acc == 4
    assert machine.visited == [1, 0]
    machine = machine |> Machine.step()
    assert machine.ip == 3
    assert machine.acc == -6
    assert machine.visited == [2, 1, 0]
  end
  test "halt when reveisiting instruction" do
    machine = [{:nop}, {:acc, 4}, {:jmp, -1}, {:acc, 9}] |> Machine.init()
    assert machine.ip == 0
    assert machine.acc == 0
    assert machine.visited == []
    assert machine.halt == false
    machine = machine |> Machine.step()
    assert machine.ip == 1
    assert machine.acc == 0
    assert machine.visited == [0]
    assert machine.halt == false
    machine = machine |> Machine.step()
    assert machine.ip == 2
    assert machine.acc == 4
    assert machine.visited == [1, 0]
    assert machine.halt == false
    machine = machine |> Machine.step()
    assert machine.ip == 1
    assert machine.acc == 4
    assert machine.visited == [2, 1, 0]
    assert machine.halt == false
    machine = machine |> Machine.step()
    assert machine.ip == 1
    assert machine.acc == 4
    assert machine.visited == [2, 1, 0]
    assert machine.halt == true
  end
  test "run program" do
    machine = [{:nop}, {:acc, 4}, {:jmp, -1}, {:acc, 9}] |> Machine.init() |> Machine.run()
    assert machine.ip == 1
    assert machine.acc == 4
    assert machine.visited == [2, 1, 0]
    assert machine.halt == true
  end
  test "part 1" do
    machine = File.read!("input") |> HandheldHalting.parse_program() |> Machine.init()
    halted = machine |> Machine.run()
    IO.inspect(halted.acc, label: "Part 1")
  end
end

%{
  "file_system": {:hex, :file_system, "0.2.10", "fb082005a9cd1711c05b5248710f8826b02d7d1784e7c3451f9c1231d4fc162d", [:mix], [], "hexpm", "41195edbfb562a593726eda3b3e8b103a309b733ad25f3d642ba49696bf715dc"},
  "mix_test_watch": {:hex, :mix_test_watch, "1.0.2", "34900184cbbbc6b6ed616ed3a8ea9b791f9fd2088419352a6d3200525637f785", [:mix], [{:file_system, "~> 0.2.1 or ~> 0.3", [hex: :file_system, repo: "hexpm", optional: false]}], "hexpm", "47ac558d8b06f684773972c6d04fcc15590abdb97aeb7666da19fcbfdc441a07"},
}

defmodule HandheldHalting.MixProject do
  use Mix.Project
  def project do
    [
      app: :handheld_halting,
      version: "0.1.0",
      elixir: "~> 1.10",
      start_permanent: Mix.env() == :prod,
      deps: deps()
    ]
  end
  # Run "mix help compile.app" to learn about applications.
  def application do
    [
      extra_applications: [:logger]
    ]
  end
  # Run "mix help deps" to learn about dependencies.
  defp deps do
    [
      {:mix_test_watch, "~> 1.0", only: :dev, runtime: false}
    ]
  end
end

defmodule Machine do
  defstruct ip: 0, acc: 0, program: [], visited: [], halt: false
  def init() do
    %Machine{}
  end
  def init(program) do
    %Machine{program: program}
  end
  def apply(%Machine{} = machine, {:nop}) do
    %Machine{machine | ip: machine.ip + 1, visited: [machine.ip | machine.visited]}
  end
  def apply(%Machine{} = machine, {:acc, n}) when is_integer(n) do
    %Machine{
      machine
      | ip: machine.ip + 1,
        acc: machine.acc + n,
        visited: [machine.ip | machine.visited]
    }
  end
  def apply(%Machine{} = machine, {:jmp, n}) when is_integer(n) do
    %Machine{machine | ip: machine.ip + n, visited: [machine.ip | machine.visited]}
  end
  def step(%Machine{} = machine) do
    if Enum.member?(machine.visited, machine.ip) do
      %Machine{machine | halt: true}
    else
      operation = machine.program |> Enum.at(machine.ip)
      machine |> Machine.apply(operation)
    end
  end
  def run(%Machine{} = machine) do
    machine |> inner_run()
  end
  defp inner_run(machine) do
    if(machine.halt) do
      machine
    else
      machine |> step() |> inner_run
    end
  end
end

defmodule HandheldHalting do
  def parse_operation("nop" <> _) do
    {:nop}
  end
  def parse_operation("acc " <> n) do
    {:acc, String.to_integer(n)}
  end
  def parse_operation("jmp " <> n) do
    {:jmp, String.to_integer(n)}
  end
  def parse_program(program_string) do
    program_string |> String.split("\n", trim: true) |> Enum.map(&parse_operation/1)
  end
end

jmp +1
acc -18
acc +19
acc +19
jmp +202
acc +15
acc +42
acc +30
acc -7
jmp +535
acc +31
acc +9
jmp +581
nop +501
acc +44
acc +18
acc -4
jmp +545
acc +9
acc +5
nop -2
acc +3
jmp +475
acc -10
acc +14
acc +29
nop +471
jmp +470
acc +2
nop +375
acc +31
acc +6
jmp +420
acc -1
acc +2
nop +185
jmp +490
acc +2
jmp +317
nop +282
jmp +457
acc +37
jmp +254
acc +19
jmp +436
jmp +458
acc -7
acc -2
acc -17
jmp +454
acc +37
jmp +212
acc +6
acc +5
acc -7
jmp +104
acc +5
nop +134
acc +46
jmp +541
acc +4
acc +46
acc +18
jmp -53
acc +10
jmp +285
acc +39
acc +34
nop +109
acc +47
jmp +32
jmp +1
jmp +143
acc +36
jmp +429
acc +45
acc +22
jmp -59
acc +0
acc +23
acc +30
acc -7
jmp -45
acc +46
acc +31
jmp +164
acc +37
acc +34
acc +40
acc -1
jmp +246
nop -46
acc +2
acc +31
jmp +221
nop +413
jmp -51
acc -14
jmp +145
acc +1
nop +77
jmp +131
jmp +370
nop +513
acc +7
jmp +476
acc +22
acc +37
acc +44
jmp +334
acc +9
acc -1
acc +5
acc +27
jmp +351
acc +31
jmp +220
nop -61
acc +34
jmp +504
nop +471
acc +6
acc +48
jmp -17
jmp +217
acc +13
acc +0
acc +25
jmp +144
acc -5
acc +17
nop +341
jmp -26
acc -10
acc +34
jmp +168
nop -16
acc -6
acc -10
acc +38
jmp +30
acc -2
acc -14
jmp +419
acc +40
acc -17
acc +27
acc +8
jmp +101
nop +370
acc +2
acc -10
acc -7
jmp +224
nop +437
acc +42
acc +50
acc +39
jmp +81
jmp +11
jmp +143
acc +6
acc +46
jmp -107
acc +13
jmp -109
acc +5
jmp +1
jmp +467
jmp -159
nop +421
jmp +243
acc +44
nop +412
acc -6
acc +13
jmp +56
acc -12
acc +18
jmp +313
nop +151
acc +5
acc +49
jmp +120
acc +46
acc +23
nop -122
acc +21
jmp -55
acc -15
jmp -115
acc +19
nop +116
acc +32
acc +21
jmp +16
acc +27
acc +32
jmp +359
acc +16
acc +18
acc +15
jmp +54
nop +182
acc +4
jmp +361
acc +4
acc +38
acc +49
jmp -94
jmp +428
acc +0
acc +9
jmp +224
jmp +82
nop +57
acc +6
jmp +1
jmp +144
jmp +20
jmp +265
jmp +402
nop +114
acc -12
acc -11
acc +1
jmp +412
nop -163
acc +50
acc +1
acc -9
jmp -20
acc +10
acc +6
jmp +323
acc +10
jmp +1
acc +42
jmp +46
acc +35
acc +31
jmp -139
jmp +129
jmp -193
acc -4
nop +247
nop -163
acc +25
jmp -26
acc +34
acc +26
acc +40
jmp +220
acc -6
acc +6
jmp +311
acc +0
acc +14
acc +41
acc +6
jmp +284
acc +32
jmp -13
nop +157
acc -4
acc +47
jmp -146
acc +34
acc +6
nop +196
acc +5
jmp +268
acc -8
jmp -176
acc +34
acc +17
jmp +1
jmp +114
acc +32
acc +39
nop +313
acc +38
jmp -237
jmp -273
acc +21
acc +26
acc +31
jmp -231
acc +17
jmp -105
nop +333
nop +17
jmp +11
acc -9
acc +2
jmp -162
acc +3
acc +0
nop +318
jmp +215
acc +14
acc +32
jmp -196
jmp +33
acc -6
acc +45
acc +27
jmp -166
acc -1
jmp -25
acc +0
acc +4
acc -14
acc +0
jmp -115
nop +118
acc +28
nop +175
acc +45
jmp -97
jmp +78
jmp -284
acc +35
nop -248
acc -18
acc -6
jmp -308
jmp -95
acc -2
acc +0
jmp +255
acc +7
jmp -24
acc +17
acc +20
jmp -220
jmp +172
acc +40
acc +39
acc +19
jmp -238
nop +44
nop -99
nop +238
jmp +195
acc -14
acc +36
acc +40
acc -11
jmp -65
nop -54
nop +47
acc -11
jmp +18
jmp +98
jmp +252
nop -1
acc +1
acc +10
jmp -4
jmp -319
jmp -46
acc -8
acc +50
acc +43
jmp -174
acc +22
acc +4
acc +32
acc -6
jmp +73
acc +8
jmp -31
acc +16
nop +11
acc +26
jmp -98
acc -11
acc +40
jmp +101
acc +28
acc +30
acc -16
acc +7
jmp +239
jmp -179
acc +47
acc +15
acc +42
acc +26
jmp +30
acc +17
acc +3
acc -5
nop -98
jmp -236
acc +2
jmp +196
acc +39
acc -14
acc +36
acc +49
jmp +189
jmp +235
acc +27
acc -2
acc +16
acc +40
jmp -81
acc -5
acc +17
acc -1
jmp +1
jmp -129
nop -171
acc +47
jmp +169
acc -16
acc -5
jmp +172
nop -84
acc +8
acc +40
acc +43
jmp -33
acc +39
nop -12
jmp +53
acc +36
jmp -270
acc +17
acc -1
jmp -255
acc +0
acc -12
jmp -371
jmp -216
acc +45
acc -18
acc +23
acc -17
jmp -37
jmp -386
nop -302
acc -19
acc -16
jmp -297
acc -18
acc -7
acc +17
acc +17
jmp -173
jmp +114
acc +4
acc +19
nop -296
jmp -36
acc -18
acc -14
acc +6
nop -27
jmp -101
acc +15
nop -407
jmp +44
acc -18
acc -6
acc +33
acc +36
jmp +80
acc +43
jmp +73
acc -2
acc +7
acc +4
jmp -10
acc +46
nop -49
acc +7
jmp +65
acc +24
jmp +144
acc +13
acc +26
jmp -351
jmp +1
acc +34
nop +62
jmp -363
acc -4
acc -5
jmp +23
jmp +82
acc -7
acc -7
acc +15
jmp -468
acc +7
nop -423
jmp -178
nop -425
acc +23
jmp -181
acc +6
acc -11
jmp -321
acc +3
jmp -122
acc +12
jmp +44
acc -5
acc -16
acc +16
jmp -281
acc +33
acc -4
acc +15
jmp +9
jmp +63
acc +35
nop -12
acc +25
acc -10
jmp -452
acc +1
jmp -148
acc +8
acc +40
acc +48
jmp +2
jmp -315
nop -325
acc -4
acc +16
acc -4
jmp -369
acc +21
acc +3
jmp -153
nop -25
acc +0
jmp -84
acc +32
jmp +19
acc -18
acc -1
jmp -385
jmp +1
jmp -357
acc -13
acc -13
jmp -360
jmp -393
acc +4
nop -102
jmp -316
jmp -248
acc +4
nop -487
jmp -339
acc +3
jmp -190
acc +24
acc +31
jmp -166
jmp -482
acc +22
acc +32
jmp -290
acc +22
acc +48
acc +5
acc -6
jmp -330
nop -203
acc +7
acc +1
jmp -287
acc +15
acc +3
jmp -230
acc +37
nop -162
jmp +33
jmp -147
acc +16
acc +39
acc +49
jmp -560
acc +26
jmp +26
jmp -283
jmp -486
acc -9
jmp +1
acc +25
acc +1
jmp -514
acc +46
jmp -166
acc -5
acc +35
nop -204
jmp -175
nop -30
nop +11
jmp -400
acc +15
acc -7
acc -1
jmp +18
acc +31
acc +16
acc +43
acc +33
jmp -260
acc +1
acc +23
acc +25
acc -1
jmp -200
acc -15
jmp -314
jmp -238
jmp -75
jmp -192
acc +30
jmp -525
acc -14
jmp +17
acc +7
acc +9
acc -6
nop -312
jmp -559
acc +28
jmp -305
jmp -239
acc +0
acc -5
acc +9
jmp -471
nop -327
acc -5
acc -19
jmp -496
acc +17
jmp +1
jmp +1
acc +29
jmp +1

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

--- Day 8: Handheld Halting ---
Your flight to the major airline hub reaches cruising altitude without incident. While you consider checking the in-flight menu for one of those drinks that come with a little umbrella, you are interrupted by the kid sitting next to you.
Their handheld game console won't turn on! They ask if you can take a look.
You narrow the problem down to a strange infinite loop in the boot code (your puzzle input) of the device. You should be able to fix it, but first you need to be able to run the code in isolation.
The boot code is represented as a text file with one instruction per line of text. Each instruction consists of an operation (acc, jmp, or nop) and an argument (a signed number like +4 or -20).
    acc increases or decreases a single global value called the accumulator by the value given in the argument. For example, acc +7 would increase the accumulator by 7. The accumulator starts at 0. After an acc instruction, the instruction immediately below it is executed next.
    jmp jumps to a new instruction relative to itself. The next instruction to execute is found using the argument as an offset from the jmp instruction; for example, jmp +2 would skip the next instruction, jmp +1 would continue to the instruction immediately below it, and jmp -20 would cause the instruction 20 lines above to be executed next.
    nop stands for No OPeration - it does nothing. The instruction immediately below it is executed next.
For example, consider the following program:
nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
jmp -4
acc +6
These instructions are visited in this order:
nop +0  | 1
acc +1  | 2, 8(!)
jmp +4  | 3
acc +3  | 6
jmp -3  | 7
acc -99 |
acc +1  | 4
jmp -4  | 5
acc +6  |
First, the nop +0 does nothing. Then, the accumulator is increased from 0 to 1 (acc +1) and jmp +4 sets the next instruction to the other acc +1 near the bottom. After it increases the accumulator from 1 to 2, jmp -4 executes, setting the next instruction to the only acc +3. It sets the accumulator to 5, and jmp -3 causes the program to continue back at the first acc +1.
This is an infinite loop: with this sequence of jumps, the program will run forever. The moment the program tries to run any instruction a second time, you know it will never terminate.
Immediately before the program would run an instruction a second time, the value in the accumulator is 5.
Run your copy of the boot code. Immediately before any instruction is executed a second time, what value is in the accumulator?
--- Part Two ---
After some careful analysis, you believe that exactly one instruction is corrupted.
Somewhere in the program, either a jmp is supposed to be a nop, or a nop is supposed to be a jmp. (No acc instructions were harmed in the corruption of this boot code.)
The program is supposed to terminate by attempting to execute an instruction immediately after the last instruction in the file. By changing exactly one jmp or nop, you can repair the boot code and make it terminate correctly.
For example, consider the same program from above:
nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
jmp -4
acc +6
If you change the first instruction from nop +0 to jmp +0, it would create a single-instruction infinite loop, never leaving that instruction. If you change almost any of the jmp instructions, the program will still eventually find another jmp instruction and loop forever.
However, if you change the second-to-last instruction (from jmp -4 to nop -4), the program terminates! The instructions are visited in this order:
nop +0  | 1
acc +1  | 2
jmp +4  | 3
acc +3  |
jmp -3  |
acc -99 |
acc +1  | 4
nop -4  | 5
acc +6  | 6
After the last instruction (acc +6), the program terminates by attempting to run the instruction below the last instruction in the file. With this change, after the program terminates, the accumulator contains the value 8 (acc +1, acc +1, acc +6).
Fix the program so that it terminates normally by changing exactly one jmp (to nop) or nop (to jmp). What is the value of the accumulator after the program terminates?

# HandheldHalting
**TODO: Add description**
## Installation
If [available in Hex](https://hex.pm/docs/publish), the package can be installed
by adding `handheld_halting` to your list of dependencies in `mix.exs`:
```elixir
def deps do
  [
    {:handheld_halting, "~> 0.1.0"}
  ]
end
```
Documentation can be generated with [ExDoc](https://github.com/elixir-lang/ex_doc)
and published on [HexDocs](https://hexdocs.pm). Once published, the docs can
be found at [https://hexdocs.pm/handheld_halting](https://hexdocs.pm/handheld_halting).