Powered by AppSignal & Oban Pro
Notesclub
Sign in with GitHub
created by hec & contributors
terms privacy

AoC 2019

AoC.2019.livemd

avatar
avatar
avatar
Share to X
Share to Bluesky
More notebooks

AoC 2019

Mix.install([
  {:kino_aoc, "~> 0.1.6"},
  {:kino_vega_lite, "~> 0.1.11"}
])

ALL

DAY 01

— Day 1: The Tyranny of the Rocket Equation —

Santa has become stranded at the edge of the Solar System while delivering presents to other planets! To accurately calculate his position in space, safely align his warp drive, and return to Earth in time to save Christmas, he needs you to bring him measurements from fifty stars.

Collect stars by solving puzzles. Two puzzles will be made available on each day in the Advent calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants one star. Good luck!

The Elves quickly load you into a spacecraft and prepare to launch.

At the first Go / No Go poll, every Elf is Go until the Fuel Counter-Upper. They haven’t determined the amount of fuel required yet.

Fuel required to launch a given module is based on its mass. Specifically, to find the fuel required for a module, take its mass, divide by three, round down, and subtract 2.

For example:

For a mass of 12, divide by 3 and round down to get 4, then subtract 2 to get 2. For a mass of 14, dividing by 3 and rounding down still yields 4, so the fuel required is also 2. For a mass of 1969, the fuel required is 654. For a mass of 100756, the fuel required is 33583. The Fuel Counter-Upper needs to know the total fuel requirement. To find it, individually calculate the fuel needed for the mass of each module (your puzzle input), then add together all the fuel values.

What is the sum of the fuel requirements for all of the modules on your spacecraft?

{:ok, puzzle_input_1} =
  KinoAOC.download_puzzle("2019", "1", System.fetch_env!("LB_AOC_SESSION"))
  • For a mass of 12, divide by 3 and round down to get 4, then subtract 2 to get 2.
  • For a mass of 14, dividing by 3 and rounding down still yields 4, so the fuel required is also 2.
  • For a mass of 1969, the fuel required is 654.
  • For a mass of 100756, the fuel required is 33583.

take its mass, divide by three, round down, and subtract 2

defmodule Day01 do
  def p1(number),
    do:
      (number / 3)
      |> floor()
      |> Kernel.-(2)

  def p2(number) when number > 6 do
    p1 = Day01.p1(number)
    ans = Day01.p1(number) + p2(p1)
    ans
  end

  def p2(number) when number <= 6, do: 0
end

example_input = "12\n14\n1969\n100756"
example_output = [2,2,654,33_583]
String.split(example_input)
|> Enum.map(fn s -> String.to_integer(s) end)
|> Enum.map(fn number -> Day01.p1(number) end)
|> Enum.zip(example_output)
|> Enum.map(fn {a, b} -> if a == b, do: {true, a, b}, else: {false, a, b} end)
|> dbg()
|> Enum.all?(fn {v, _, _} -> v end)

String.split(puzzle_input_1)
|> Enum.map(fn s -> String.to_integer(s) end)
|> Enum.map(fn number -> Day01.p1(number) end)
|> Enum.reduce(fn n, acc -> acc + n end)
example_output = [2, 2, 966, 50346]
String.split(example_input)
|> Enum.map(fn s -> String.to_integer(s) end)
|> Enum.map(fn number -> Day01.p2(number) end)
|> Enum.zip(example_output)
|> Enum.map(fn {a, b} -> if a == b, do: {true, a, b}, else: {false, a, b} end)
|> dbg()
|> Enum.all?(fn {v, _, _} -> v end)

So, for each module mass, calculate its fuel and add it to the total. Then, treat the fuel amount you just calculated as the input mass and repeat the process, continuing until a fuel requirement is zero or negative. For example:

  • A module of mass 14 requires 2 fuel. This fuel requires no further fuel (2 divided by 3 and rounded down is 0, which would call for a negative fuel), so the total fuel required is still just 2.
  • At first, a module of mass 1969 requires 654 fuel. Then, this fuel requires 216 more fuel (654 / 3 - 2). 216 then requires 70 more fuel, which requires 21 fuel, which requires 5 fuel, which requires no further fuel. So, the total fuel required for a module of mass 1969 is 654 + 216 + 70 + 21 + 5 = 966.
  • The fuel required by a module of mass 100756 and its fuel is: 33583 + 11192 + 3728 + 1240 + 411 + 135 + 43 + 12 + 2 = 50346.

What is the sum of the fuel requirements

if String.split(example_input)
   |> Enum.map(fn s -> String.to_integer(s) end)
   |> Enum.map(fn number -> Day01.p2(number) end)
   |> Enum.zip(example_output)
   |> Enum.map(fn {a, b} ->
     if a == b do
       {true, a, b}
     else
       {false, a, b}
     end
   end)
   |> dbg()
   |> Enum.all?(fn {v, _, _} -> v end) do
  String.split(puzzle_input_1)
  |> Enum.map(fn s -> String.to_integer(s) end)
  |> Enum.map(fn number -> Day01.p2(number) end)
  |> Enum.reduce(fn n, acc -> acc + n end)
else
  IO.puts("meow")
end

DAY 02

— Day 2: 1202 Program Alarm —

On the way to your gravity assist around the Moon, your ship computer beeps angrily about a “1202 program alarm“. On the radio, an Elf is already explaining how to handle the situation: “Don’t worry, that’s perfectly norma–“ The ship computer bursts into flames.

You notify the Elves that the computer’s magic smoke seems to have escaped. “That computer ran Intcode programs like the gravity assist program it was working on; surely there are enough spare parts up there to build a new Intcode computer!”

An Intcode program is a list of integers separated by commas (like 1,0,0,3,99). To run one, start by looking at the first integer (called position 0). Here, you will find an opcode - either 1, 2, or 99. The opcode indicates what to do; for example, 99 means that the program is finished and should immediately halt. Encountering an unknown opcode means something went wrong.

Opcode 1 adds together numbers read from two positions and stores the result in a third position. The three integers immediately after the opcode tell you these three positions - the first two indicate the positions from which you should read the input values, and the third indicates the position at which the output should be stored.

For example, if your Intcode computer encounters 1,10,20,30, it should read the values at positions 10 and 20, add those values, and then overwrite the value at position 30 with their sum.

Opcode 2 works exactly like opcode 1, except it multiplies the two inputs instead of adding them. Again, the three integers after the opcode indicate where the inputs and outputs are, not their values.

Once you’re done processing an opcode, move to the next one by stepping forward 4 positions.

For example, suppose you have the following program:

1,9,10,3,2,3,11,0,99,30,40,50

For the purposes of illustration, here is the same program split into multiple lines:

1,9,10,3,2,3,11,0,99,30,40,50

The first four integers, 1,9,10,3, are at positions 0, 1, 2, and 3. Together, they represent the first opcode (1, addition), the positions of the two inputs (9 and 10), and the position of the output (3). To handle this opcode, you first need to get the values at the input positions: position 9 contains 30, and position 10 contains 40. Add these numbers together to get 70. Then, store this value at the output position; here, the output position (3) is at position 3, so it overwrites itself. Afterward, the program looks like this:

1,9,10,70,2,3,11,0,99,30,40,50

Step forward 4 positions to reach the next opcode, 2. This opcode works just like the previous, but it multiplies instead of adding. The inputs are at positions 3 and 11; these positions contain 70 and 50 respectively. Multiplying these produces 3500; this is stored at position 0:

3500,9,10,70,2,3,11,0,99,30,40,50

Stepping forward 4 more positions arrives at opcode 99, halting the program.

Here are the initial and final states of a few more small programs:

  • 1,0,0,0,99 becomes 2,0,0,0,99 (1 + 1 = 2).
  • 2,3,0,3,99 becomes 2,3,0,6,99 (3 * 2 = 6).
  • 2,4,4,5,99,0 becomes 2,4,4,5,99,9801 (99 * 99 = 9801).
  • 1,1,1,4,99,5,6,0,99 becomes 30,1,1,4,2,5,6,0,99.

Once you have a working computer, the first step is to restore the gravity assist program (your puzzle input) to the “1202 program alarm” state it had just before the last computer caught fire. To do this, before running the program, replace position 1 with the value 12 and replace position 2 with the value 2. What value is left at position 0 after the program halts?

defmodule PC do
  defstruct memory: [], ip: 0

  def parse_inst(%PC{memory: memory, ip: ip}) do
    case Enum.at(memory, ip) do
      1 -> :add
      2 -> :mult
      99 -> :halt
      _ -> :unknown
    end
  end

  def load(%PC{memory: memory, ip: ip}, offset) do
    addr = Enum.at(memory, ip + offset)
    Enum.at(memory, addr)
  end

  def store(%PC{memory: memory, ip: ip}, addr, val) do
    %PC{memory: List.replace_at(memory, addr, val), ip: ip}
  end

  def inc_ip(%PC{memory: memory, ip: ip}), do: %PC{memory: memory, ip: ip + 4}

  def load_load_store(%PC{memory: memory, ip: ip}, op) do
    a = load(%PC{memory: memory, ip: ip}, 1)
    b = load(%PC{memory: memory, ip: ip}, 2)
    addr = Enum.at(memory, ip + 3)
    val = op.(a, b)
    store(%PC{memory: memory, ip: ip}, addr, val)
  end

  def execute(%PC{memory: memory, ip: _ip}, inst) when :halt == inst, do: memory

  def execute(%PC{memory: memory, ip: ip}, inst) when :halt != inst do
    case inst do
      :add -> load_load_store(%PC{memory: memory, ip: ip}, fn a, b -> a + b end)
      :mult -> load_load_store(%PC{memory: memory, ip: ip}, fn a, b -> a * b end)
    end
  end

  def execute(%PC{memory: memory, ip: ip}) do
    inst = parse_inst(%PC{memory: memory, ip: ip})

    updated = execute(%PC{memory: memory, ip: ip}, inst)

    if is_list(updated) do
      updated
    else
      inc_ip(updated) |> execute()
    end
  end
end

defmodule Day02 do 
  def unstr(str) do
    str
    |> String.split(",")
    |> Enum.map(&amp;(String.to_integer(&amp;1)))
  end
end
example_input = "1,0,0,0,99\n2,3,0,3,99\n2,4,4,5,99,0\n1,1,1,4,99,5,6,0,99\n1,9,10,3,2,3,11,0,99,30,40,50"
example_output =
  [
    "2,0,0,0,99",
    "2,3,0,6,99",
    "2,4,4,5,99,9801",
    "30,1,1,4,2,5,6,0,99",
    "3500,9,10,70,2,3,11,0,99,30,40,50"
  ]
  |> Enum.map(&amp;Day02.unstr(&amp;1))

op_correct = 
  example_input
  |> String.split()
  |> Enum.map(&amp;(Day02.unstr(&amp;1)))
  |> Enum.map(fn memory -> %PC{memory: memory, ip: 0} end)
  |> Enum.map(fn pc -> PC.execute(pc) end)
  |> Enum.zip(example_output)
  |> Enum.map(fn {a, b} -> {a == b, a, b} end)
  |> Enum.map(fn {v, _, _} -> v end)
  |> Enum.all?()
  |> dbg()
{:ok, puzzle_input} =
  KinoAOC.download_puzzle("2019", "2", System.fetch_env!("LB_AOC_SESSION"))
input =
  puzzle_input
  |> String.split(",")
  |> Enum.map(&amp;String.to_integer(&amp;1))

pc =
  %PC{memory: input, ip: 0}
  |> PC.store(1, 12)
  |> PC.store(2, 2)

List.first(PC.execute(pc))

— Part Two —

“Good, the new computer seems to be working correctly! Keep it nearby during this mission - you’ll probably use it again. Real Intcode computers support many more features than your new one, but we’ll let you know what they are as you need them.”

“However, your current priority should be to complete your gravity assist around the Moon. For this mission to succeed, we should settle on some terminology for the parts you’ve already built.”

Intcode programs are given as a list of integers; these values are used as the initial state for the computer’s memory. When you run an Intcode program, make sure to start by initializing memory to the program’s values. A position in memory is called an address (for example, the first value in memory is at “address 0”).

Opcodes (like 1, 2, or 99) mark the beginning of an instruction. The values used immediately after an opcode, if any, are called the instruction’s parameters. For example, in the instruction 1,2,3,4, 1 is the opcode; 2, 3, and 4 are the parameters. The instruction 99 contains only an opcode and has no parameters.

The address of the current instruction is called the instruction pointer; it starts at 0. After an instruction finishes, the instruction pointer increases by the number of values in the instruction; until you add more instructions to the computer, this is always 4 (1 opcode + 3 parameters) for the add and multiply instructions. (The halt instruction would increase the instruction pointer by 1, but it halts the program instead.)

“With terminology out of the way, we’re ready to proceed. To complete the gravity assist, you need to determine what pair of inputs produces the output 19690720.”

The inputs should still be provided to the program by replacing the values at addresses 1 and 2, just like before. In this program, the value placed in address 1 is called the noun, and the value placed in address 2 is called the verb. Each of the two input values will be between 0 and 99, inclusive.

Once the program has halted, its output is available at address 0, also just like before. Each time you try a pair of inputs, make sure you first reset the computer’s memory to the values in the program (your puzzle input) - in other words, don’t reuse memory from a previous attempt.

Find the input noun and verb that cause the program to produce the output 19690720. What is 100 * noun + verb? (For example, if noun=12 and verb=2, the answer would be 1202.)

start = Time.utc_now()

combinations = Enum.flat_map(0..99, fn noun -> Enum.map(0..99, fn verb -> [noun, verb] end) end)

ans =
  Enum.map(
    combinations,
    fn [noun, verb] ->
      pc =
        %PC{memory: input, ip: 0}
        |> PC.store(1, noun)
        |> PC.store(2, verb)

      ans = PC.execute(pc) |> List.first()

      [ans, noun, verb]
    end
  )

[_, noun, verb] = Enum.find(ans, fn [ans, _, _] -> ans == 19_690_720 end)

IO.puts(Time.diff(Time.utc_now(), start, :microsecond) / 1_000_000)

100 * noun + verb

start = Time.utc_now()

combinations = Enum.flat_map(0..99, fn noun -> Enum.map(0..99, fn verb -> [noun, verb] end) end)

mother = Process.alias()

Enum.each(combinations, fn [noun, verb] ->
  spawn(fn ->
    pc =
      %PC{memory: input, ip: 0}
      |> PC.store(1, noun)
      |> PC.store(2, verb)

    ans = PC.execute(pc) |> List.first()

    if ans == 19_690_720 do
      send(mother, [noun, verb])
    end
  end)
end)

receive do
  [noun, verb] ->
    IO.puts(Time.diff(Time.utc_now(), start, :microsecond) / 1_000_000)
    100 * noun + verb
end

DAY 03

— Day 3: Crossed Wires —

The gravity assist was successful, and you’re well on your way to the Venus refuelling station. During the rush back on Earth, the fuel management system wasn’t completely installed, so that’s next on the priority list.

Opening the front panel reveals a jumble of wires. Specifically, two wires are connected to a central port and extend outward on a grid. You trace the path each wire takes as it leaves the central port, one wire per line of text (your puzzle input).

The wires twist and turn, but the two wires occasionally cross paths. To fix the circuit, you need to find the intersection point closest to the central port. Because the wires are on a grid, use the Manhattan distance for this measurement. While the wires do technically cross right at the central port where they both start, this point does not count, nor does a wire count as crossing with itself.

For example, if the first wire’s path is R8,U5,L5,D3, then starting from the central port (o), it goes right 8, up 5, left 5, and finally down 3:

……….. ……….. ……….. ….+—-+. ….|….|. ….|….|. ….|….|. ………|. .o——-+. ……….. Then, if the second wire’s path is U7,R6,D4,L4, it goes up 7, right 6, down 4, and left 4:

……….. .+—–+… .|…..|… .|..+–X-+. .|..|..|.|. .|.-X–+.|. .|..|….|. .|…….|. .o——-+. ……….. These wires cross at two locations (marked X), but the lower-left one is closer to the central port: its distance is 3 + 3 = 6.

Here are a few more examples:

R75,D30,R83,U83,L12,D49,R71,U7,L72 U62,R66,U55,R34,D71,R55,D58,R83 = distance 159 R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51 U98,R91,D20,R16,D67,R40,U7,R15,U6,R7 = distance 135 What is the Manhattan distance from the central port to the closest intersection?

example_input =
  [
    "R8,U5,L5,D3\nU7,R6,D4,L4",
    "R75,D30,R83,U83,L12,D49,R71,U7,L72\nU62,R66,U55,R34,D71,R55,D58,R83",
    "R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51\nU98,R91,D20,R16,D67,R40,U7,R15,U6,R7"
  ]
  |> Enum.map(&amp;String.split/1)
  |> Enum.map(fn arr -> Enum.map(arr, fn str -> String.split(str, ",") end) end)
  |> Enum.map(fn arr ->
    Enum.map(arr, fn strs -> Enum.map(strs, fn s -> Command.from(s) end) end)
  end)
  |> dbg()

defmodule Vec2 do
  defstruct x: 0, y: 0
end

defmodule Command do
  defstruct dir: :default, amt: 0

  def from(str) do
    dir = String.at(str, 0)

    dir =
      case dir do
        "U" -> :up
        "D" -> :down
        "L" -> :left
        "R" -> :right
        u -> IO.puts("Unknown direction: " <> u)
      end

    amt = String.slice(str, 1..(String.length(str) - 1))
    amt = String.to_integer(amt)

    %Command{dir: dir, amt: amt}
  end
end

defmodule Array2D do
  defstruct grid: %{%Vec2{x: 0, y: 0} => {1, []}}

  def inc(%Array2D{grid: grid}, %Vec2{x: x, y: y}, idx, dist) do
    key = %Vec2{x: x, y: y}
    grid = Map.put_new(grid, key, {1, [{idx, dist}]})

    grid =
      Map.update!(grid, key, fn {v, ids} ->
        if Enum.any?(ids |> Enum.map(fn {id, _} -> id == idx end)),
          do: {v, ids},
          else: {v + 1, [{idx, dist}] ++ ids}
      end)

    %Array2D{grid: grid}
  end

  def print(%Array2D{grid: grid}) do
    {{%Vec2{x: min_x, y: _}, _}, {%Vec2{x: max_x, y: _}, _}} =
      Enum.min_max_by(grid, fn {%Vec2{x: x, y: _}, _} -> x end)

    {{%Vec2{x: _, y: min_y}, _}, {%Vec2{x: _, y: max_y}, _}} =
      Enum.min_max_by(grid, fn {%Vec2{x: _, y: y}, _} -> y end)

    for y <- max_y..min_y//-1 do
      for x <- min_x..max_x do
        key = %Vec2{x: x, y: y}

        IO.write(
          if x == 0 and y == 0
            do "o"
            else 
              case Map.get(grid, key) do
                nil -> "."
                {_, l} -> l |> Enum.map(fn {_, v} -> v end) |> List.foldl(0, fn a, b -> a + b end)
              end
            end
              
        )
      end

      IO.write("\n")
    end

    %Array2D{grid: grid}
  end
end

defmodule Day03 do
  defstruct turtle: %Vec2{x: 0, y: 0}, world: %Array2D{}

  def move(%Day03{turtle: %Vec2{x: x, y: y}, world: world}, %Command{dir: dir, amt: amt}, idx, dist) do
    world =
      1..amt
      |> Enum.reduce(world, fn offset, world ->
        case dir do
          :up -> Array2D.inc(world, %Vec2{x: x, y: y + offset}, idx, dist + offset)
          :down -> Array2D.inc(world, %Vec2{x: x, y: y - offset}, idx, dist + offset)
          :left -> Array2D.inc(world, %Vec2{x: x - offset, y: y}, idx, dist + offset)
          :right -> Array2D.inc(world, %Vec2{x: x + offset, y: y}, idx, dist + offset)
          _ -> IO.puts("meow")
        end
      end)

    case dir do
      :up -> {%Day03{turtle: %Vec2{x: x, y: y + amt}, world: world}, dist + amt}
      :down -> {%Day03{turtle: %Vec2{x: x, y: y - amt}, world: world}, dist + amt}
      :left -> {%Day03{turtle: %Vec2{x: x - amt, y: y}, world: world}, dist + amt}
      :right -> {%Day03{turtle: %Vec2{x: x + amt, y: y}, world: world}, dist + amt}
    end
  end

  def reset_turtle(%Day03{turtle: _final, world: world}) do
    %Day03{turtle: %Vec2{}, world: world}
  end

  def apply_commands(this, commands, idx),
    do: commands |> List.foldl({this, 0}, fn command, {this, dist} -> Day03.move(this, command, idx, dist) end) |> Kernel.elem(0)

  def apply_wires(this, wires) do
    wires
    |> List.foldl(
      {this, 0},
      fn commands, {this, w} ->
        {
          this |> Day03.apply_commands(commands, w) |> Day03.reset_turtle(),
          w + 1,
        }
      end
    )
    |> Kernel.elem(0)
  end
end

wires = example_input |> Enum.at(1)

sim =
  %Day03{}
  |> Day03.apply_wires(wires)

sim.world |> Array2D.print()

%Vec2{x: x, y: y} =
  sim.world.grid
  |> Enum.filter(fn {_, {v, _}} -> v > 1 end)
  |> Enum.map(fn {v, _} -> v end)
  |> Enum.min_by(fn %Vec2{x: x  , y: y} -> abs(x) + abs(y) end)

{x, y, abs(x) + abs(y)}

{:ok, puzzle_input} =
  KinoAOC.download_puzzle("2019", "3", System.fetch_env!("LB_AOC_SESSION"))
wires =
  puzzle_input
  |> String.split()
  |> Enum.map(fn str -> str |> String.split(",") |> Enum.map(&amp;Command.from/1) end)

sim =
  %Day03{}
  |> Day03.apply_wires(wires)

%Vec2{x: x, y: y} =
  sim.world.grid
  |> Enum.filter(fn {_, {v, _}} -> v > 1 end)
  |> Enum.map(fn {pos, _} -> pos end)
  |> Enum.min_by(fn %Vec2{x: x, y: y} -> abs(x) + abs(y) end)

abs(x) + abs(y)
wires = example_input |> Enum.at(1)

sim =
  %Day03{}
  |> Day03.apply_wires(wires)


sim.world |> Array2D.print()


[{_, a}, {_, b}] = sim.world.grid
|> Enum.filter(fn {_, {v, _}} -> v > 1 end)
|> Enum.map(fn {_, {_, l}} -> l end)
|> Enum.min_by(fn [{_, a}, {_, b}] -> a + b end)

a + b
wires =
  puzzle_input
  |> String.split()
  |> Enum.map(fn str -> str |> String.split(",") |> Enum.map(&amp;Command.from/1) end)

sim =
  %Day03{}
  |> Day03.apply_wires(wires)


[{_, a}, {_, b}] = sim.world.grid
|> Enum.filter(fn {_, {v, _}} -> v > 1 end)
|> Enum.map(fn {_, {_, l}} -> l end)
|> Enum.min_by(fn [{_, a}, {_, b}] -> a + b end)

a + b

Other notebooks:

Back