<!--
 vim:ft=markdown --!>
 livebook:{"persist_outputs":true} 
-->

<!-- livebook:{"persist_outputs":true} -->

# Advent of Code 2021

## Setup

```elixir
Mix.install([
  {:nx, github: "elixir-nx/nx", sparse: "nx"},
  {:kino, github: "livebook-dev/kino"}
])
```

```output
* Getting nx (https://github.com/elixir-nx/nx.git)
remote: Enumerating objects: 10786, done.        
remote: Counting objects: 100% (2841/2841), done.        
remote: Compressing objects: 100% (635/635), done.        
remote: Total 10786 (delta 2376), reused 2515 (delta 2195), pack-reused 7945        
origin/HEAD set to main
* Getting kino (https://github.com/livebook-dev/kino.git)
remote: Enumerating objects: 488, done.        
remote: Counting objects: 100% (488/488), done.        
remote: Compressing objects: 100% (351/351), done.        
remote: Total 488 (delta 269), reused 274 (delta 118), pack-reused 0        
origin/HEAD set to main
==> kino
Compiling 19 files (.ex)
Generated kino app
==> nx
Compiling 23 files (.ex)
Generated nx app
```

```output
:ok
```

## Day 1

### Load input

```elixir
stream =
  File.stream!("day1.txt")
  |> Stream.map(&String.to_integer(String.trim(&1)))
```

```output
#Stream<[
  enum: %File.Stream{
    line_or_bytes: :line,
    modes: [:raw, :read_ahead, :binary],
    path: "day1.txt",
    raw: true
  },
  funs: [#Function<47.58486609/1 in Stream.map/2>]
]>
```

### Task 1

<!-- livebook:{"break_markdown":true} -->

Compute count of consecutive increases

```elixir
stream
|> Stream.chunk_every(2, 1, :discard)
|> Enum.count(fn [a, b] -> a < b end)
```

```output
1688
```

### Task 2

<!-- livebook:{"break_markdown":true} -->

Compute count of consecutive increases of sums of trigrams.

However we can notice, that if we have list like:

$$
[a, b, c, d]
$$

Then when we want to compare consecutive trigrams then we compare:

$$
a + b + c < b + c + d \\
a < d
$$

So we can traverse each 4 elements and then just compare first and last one
instead of summing and then traversing it again.

```elixir
stream
|> Stream.chunk_every(4, 1, :discard)
|> Enum.count(fn [a, _, _, b] -> a < b end)
```

```output
1728
```

## Day 2

### Load input

We do parsing there, as it will help us with the latter tasks. Pattern matching
is the simplest approach there, as input is in form of:

```
forward 10
up 20
down 30
```

We need to `trim/1` input to make sure that the last newline will not interrupt
`String.to_integer/1` calls.

```elixir
stream =
  File.stream!("day2.txt")
  |> Stream.map(fn input ->
    case String.trim(input) do
      "forward " <> n -> {:forward, String.to_integer(n)}
      "up " <> n -> {:up, String.to_integer(n)}
      "down " <> n -> {:down, String.to_integer(n)}
    end
  end)
```

```output
#Stream<[
  enum: %File.Stream{
    line_or_bytes: :line,
    modes: [:raw, :read_ahead, :binary],
    path: "day2.txt",
    raw: true
  },
  funs: [#Function<47.58486609/1 in Stream.map/2>]
]>
```

### Task 1

```elixir
{h, d} =
  stream
  |> Enum.reduce({0, 0}, fn
    {:forward, n}, {h, d} -> {h + n, d}
    {:up, n}, {h, d} -> {h, d - n}
    {:down, n}, {h, d} -> {h, d + n}
  end)

h * d
```

```output
1499229
```

### Task 2

```elixir
{h, d, _} =
  stream
  |> Enum.reduce({0, 0, 0}, fn
    {:forward, n}, {h, d, a} -> {h + n, d + a * n, a}
    {:up, n}, {h, d, a} -> {h, d, a - n}
    {:down, n}, {h, d, a} -> {h, d, a + n}
  end)

h * d
```

```output
1340836560
```

## Day 3

### Input

```elixir
stream =
  File.stream!("day3.txt")
  |> Enum.map(&String.trim/1)
  |> Enum.map(&String.to_charlist/1)

defmodule Day3 do
  def count(list) do
    Enum.reduce(list, List.duplicate(0, 12), fn input, acc ->
      for {value, counter} <- Enum.zip(input, acc) do
        case value do
          ?1 -> counter + 1
          ?0 -> counter
        end
      end
    end)
  end
end
```

```output
{:module, Day3, <<70, 79, 82, 49, 0, 0, 7, ...>>, {:count, 1}}
```

### Task 1

```elixir
half = div(length(stream), 2)

{a, b} =
  stream
  |> Day3.count()
  |> Enum.reduce({0, 0}, fn elem, {a, b} ->
    if elem > half do
      {a * 2 + 1, b * 2}
    else
      {a * 2, b * 2 + 1}
    end
  end)

a * b
```

```output
3847100
```

### Task 2

```elixir
defmodule Day3.Task2 do
  def reduce(list, cb), do: reduce(list, 0, cb)

  defp reduce([elem], _, _), do: elem

  defp reduce(list, at, cb) do
    counts = Day3.count(list)

    half = div(length(list), 2)
    count = Enum.at(counts, at)

    bit =
      cond do
        count == half and cb.(count + 1, half) -> ?1
        count != half and cb.(count, half) -> ?1
        true -> ?0
      end

    reduce(Enum.filter(list, &(Enum.at(&1, at) == bit)), at + 1, cb)
  end
end

co2 = List.to_integer(Day3.Task2.reduce(stream, &</2), 2)
o2 = List.to_integer(Day3.Task2.reduce(stream, &>/2), 2)

co2 * o2
```

```output
4105235
```

## Day 4

### Input

This time it is a little bit more convoluted, as there are 2 parts of the input.
Fortunately we can easily disect the parts via pattern matching.

Technically the conversion to the numbers is not needed, but it does no harm
and provides additional layer of safety against some whitespace characters left there
and here.

The `Day4.win/2` function is manually unrolled, as it is easier to write than some
random jumping in the list.

<!-- livebook:{"disable_formatting":true} -->

```elixir
[numbers | bingos] =
  File.read!("day4.txt")
  |> String.split("\n\n", trim: true)

numbers =
  numbers
  |> String.trim()
  |> String.split(",")
  |> Enum.map(&String.to_integer/1)

bingos =
  bingos
  |> Enum.map(fn bingo ->
    bingo
    |> String.split(~r/\s+/, trim: true)
    |> Enum.map(&String.to_integer/1)
  end)

defmodule Day4 do
  def win(
        [
          a1, a2, a3, a4, a5,
          b1, b2, b3, b4, b5,
          c1, c2, c3, c4, c5,
          d1, d2, d3, d4, d5,
          e1, e2, e3, e4, e5
        ],
        nums
      ) do
    # Rows
    all_in([a1, a2, a3, a4, a5], nums) or
    all_in([b1, b3, b3, b4, b5], nums) or
    all_in([c1, c2, c3, c4, c5], nums) or
    all_in([d1, d2, d3, d4, d5], nums) or
    all_in([e1, e2, e3, e4, e5], nums) or
    # Columns
    all_in([a1, b1, c1, d1, e1], nums) or
    all_in([a2, b2, c2, d2, e2], nums) or
    all_in([a3, b3, c3, d3, e3], nums) or
    all_in([a4, b4, c4, d4, e4], nums) or
    all_in([a5, b5, c5, d5, e5], nums)
  end

  def not_matched(bingo, nums) do
    Enum.reject(bingo, &(&1 in nums))
  end

  defp all_in(list, nums) do
    Enum.all?(list, &(&1 in nums))
  end
end
```

```output
{:module, Day4, <<70, 79, 82, 49, 0, 0, 15, ...>>, {:all_in, 2}}
```

### Task 1

We simply traverse the `numbers` list aggregating the numbers (order doesn't really matter,
here we aggregate them in reverse order to speedup the code). When we have enough numbers
that any of the `bingos` is winning one, then we halt the reduction and return computed
result.

```elixir
numbers
|> Enum.reduce_while([], fn elem, acc ->
  matches = [elem | acc]

  case Enum.find(bingos, &Day4.win(&1, matches)) do
    nil -> {:cont, matches}
    bingo -> {:halt, Enum.sum(Day4.not_matched(bingo, matches)) * elem}
  end
end)
```

```output
34506
```

### Task 2

```elixir
numbers
|> Enum.reduce_while({bingos, []}, fn elem, {bingos, acc} ->
  matches = [elem | acc]

  case bingos do
    [bingo] ->
      if Day4.win(bingo, matches) do
        {:halt, Enum.sum(Day4.not_matched(bingo, matches)) * elem}
      else
        {:cont, {bingos, matches}}
      end

    _ ->
      {:cont, {Enum.reject(bingos, &Day4.win(&1, matches)), matches}}
  end
end)
```

```output
7686
```

## Day 5

```elixir
defmodule Day5 do
  defmodule Point do
    defstruct [:x, :y]

    def parse(input) do
      [x, y] = String.split(input, ",")

      %__MODULE__{x: String.to_integer(x), y: String.to_integer(y)}
    end
  end

  defmodule Line do
    defstruct [:start, :finish]

    def new(a, b) do
      {start, finish} =
        cond do
          a.x < b.x -> {a, b}
          a.y < b.y -> {a, b}
          true -> {b, a}
        end

      %__MODULE__{start: start, finish: finish}
    end

    def horizontal?(a), do: a.start.y == a.finish.y
    def vertical?(a), do: a.start.x == a.finish.x

    def points(a) do
      case {sign(a.finish.x - a.start.x), sign(a.finish.y - a.start.y)} do
        {0, dy} -> for y <- a.start.y..a.finish.y//dy, do: {a.start.x, y}
        {dx, 0} -> for x <- a.start.x..a.finish.x//dx, do: {x, a.start.y}
        {dx, dy} -> Enum.zip(a.start.x..a.finish.x//dx, a.start.y..a.finish.y//dy)
      end
    end

    def orientation(a) do
      cond do
        horizontal?(a) -> :horizontal
        vertical?(a) -> :vertical
        true -> :diagonal
      end
    end

    defp sign(0), do: 0
    defp sign(x) when x < 0, do: -1
    defp sign(x) when x > 0, do: 1
  end
end

lines =
  File.stream!("day5.txt")
  |> Stream.map(&String.trim/1)
  |> Stream.map(fn input ->
    [a, b] = String.split(input, " -> ")

    pa = Day5.Point.parse(a)
    pb = Day5.Point.parse(b)

    Day5.Line.new(pa, pb)
  end)
```

```output
#Stream<[
  enum: %File.Stream{
    line_or_bytes: :line,
    modes: [:raw, :read_ahead, :binary],
    path: "day5.txt",
    raw: true
  },
  funs: [#Function<47.58486609/1 in Stream.map/2>, #Function<47.58486609/1 in Stream.map/2>]
]>
```

### Task 1

```elixir
lines
|> Stream.filter(&(Day5.Line.orientation(&1) != :diagonal))
|> Stream.flat_map(&Day5.Line.points/1)
|> Enum.frequencies()
|> Enum.count(fn {_k, v} -> v > 1 end)
```

```output
5197
```

### Task 2

```elixir
lines
|> Stream.flat_map(&Day5.Line.points/1)
|> Enum.frequencies()
|> Enum.count(fn {_k, v} -> v > 1 end)
```

```output
18605
```

## Day 6

```elixir
initial = for i <- 0..8, into: %{}, do: {i, 0}

counts =
  File.read!("day6.txt")
  |> String.trim()
  |> String.split(",")
  |> Enum.map(&String.to_integer/1)
  |> Enum.frequencies()
  |> Map.merge(initial, fn _, a, _ -> a end)

defmodule Day6 do
  def next(%{0 => next} = population) do
    1..8
    |> Map.new(&{&1 - 1, population[&1]})
    |> Map.merge(%{6 => next, 8 => next}, fn _, v1, v2 -> v1 + v2 end)
  end
end
```

```output
{:module, Day6, <<70, 79, 82, 49, 0, 0, 7, ...>>, {:next, 1}}
```

### Task 1

```elixir
1..80
|> Enum.reduce(counts, fn _, acc -> Day6.next(acc) end)
|> Map.values()
|> Enum.sum()
```

```output
343441
```

### Task 2

```elixir
1..256
|> Enum.reduce(counts, fn _, acc -> Day6.next(acc) end)
|> Map.values()
|> Enum.sum()
```

```output
1569108373832
```

## Day 7

```elixir
input =
  File.read!("day7.txt")
  |> String.trim()
  |> String.split(",")
  |> Enum.map(&String.to_integer/1)
```

```output
[1101, 1, 29, 67, 1102, 0, 1, 65, 1008, 65, 35, 66, 1005, 66, 28, 1, 67, 65, 20, 4, 0, 1001, 65, 1,
 65, 1106, 0, 8, 99, 35, 67, 101, 99, 105, 32, 110, 39, 101, 115, 116, 32, 112, 97, 115, 32, 117,
 110, 101, 32, 105, ...]
```

### Task 1

```elixir
mean = Enum.at(Enum.sort(input), div(length(input), 2))

input
|> Enum.map(&abs(&1 - mean))
|> Enum.sum()
```

```output
336721
```

### Task 2

```elixir
arith_sum = fn n -> div(n * n + n, 2) end

max = Enum.max(input)

mean = Enum.sum(input) / length(input)

[floor(mean), ceil(mean)]
|> Enum.map(fn n ->
  input
  |> Enum.map(&arith_sum.(abs(&1 - n)))
  |> Enum.sum()
end)
|> Enum.min()
```

```output
91638945
```

## Day 8

```elixir
input =
  File.stream!("day8.txt")
  |> Stream.map(fn line ->
    line
    |> String.split(" | ")
    |> Enum.map(fn part ->
      part
      |> String.trim()
      |> String.split(" ")
      |> Enum.map(fn disp ->
        # Sort characters in each entry to simplify later work
        disp
        |> String.to_charlist()
        |> Enum.sort()
        |> List.to_string()
      end)
    end)
    |> List.to_tuple()
  end)
```

```output
#Stream<[
  enum: %File.Stream{
    line_or_bytes: :line,
    modes: [:raw, :read_ahead, :binary],
    path: "day8.txt",
    raw: true
  },
  funs: [#Function<47.58486609/1 in Stream.map/2>]
]>
```

### Task 1

We simply need to count all occurences of the values that have 2, 3, 4, or 7 highlighted
segments.

```elixir
input
|> Enum.map(fn {_, output} ->
  Enum.count(output, &(byte_size(&1) in [2, 3, 4, 7]))
end)
|> Enum.sum()
```

```output
390
```

### Task 2

```elixir
defmodule Day8.Task2 do
  defp a --- b, do: MapSet.difference(a, b)

  defp a +++ b, do: MapSet.union(a, b)

  defp a <~> b, do: MapSet.intersection(a, b)

  #            1.   7.    4. 2|3|5. 2|3|5. 2|3|5.  6|9|0.  6|9|0.  6|9|0.       8.
  def deduce([cf, acf, bcdf, acdeg, acdfg, abdfg, abdefg, abcdfg, abcefg, abcdefg]) do
    eg = abcdefg --- (acf +++ bcdf)
    bd = bcdf --- cf
    adg = acdeg <~> acdfg <~> abdfg
    abfg = abdefg <~> abcdfg <~> abcefg
    a = acf --- cf
    b = abfg <~> bd
    f = abfg <~> cf
    g = adg <~> eg
    d = adg <~> bd
    c = cf --- f
    e = eg --- g

    [a, b, c, d, e, f, g] =
      [a, b, c, d, e, f, g]
      |> Enum.map(&extract/1)

    [
      # 0
      [a, b, c, e, f, g],
      # 1
      [c, f],
      # 2
      [a, c, d, e, g],
      # 3
      [a, c, d, f, g],
      # 4
      [b, c, d, f],
      # 5
      [a, b, d, f, g],
      # 6
      [a, b, d, e, f, g],
      # 7
      [a, c, f],
      # 8
      [a, b, c, d, e, f, g],
      # 9
      [a, b, c, d, f, g]
    ]
    |> Enum.map(&List.to_string(Enum.sort(&1)))
    |> Enum.with_index()
    |> Map.new()
  end

  defp extract(a) do
    # Just additional sanity check
    [v] = MapSet.to_list(a)

    v
  end

  def decode(matches, output) do
    output
    |> Enum.map(&matches[&1])
    |> Integer.undigits()
  end
end

input
|> Enum.map(fn {input, output} ->
  input
  |> Enum.sort_by(&byte_size/1)
  |> Enum.map(&MapSet.new(String.to_charlist(&1)))
  |> Day8.Task2.deduce()
  |> Day8.Task2.decode(output)
end)
|> Enum.sum()
```

```output
1011785
```

## Day 9

```elixir
input =
  File.read!("day9.txt")
  # ~S[110
  #   101
  #   110]
  |> String.split("\n", trim: true)
  |> Enum.map(&String.to_charlist(String.trim(&1)))
  |> Nx.tensor(names: [:y, :x])
  |> Nx.subtract(?0)
  |> Nx.add(1)

{width, height} = shape = Nx.shape(input)
```

```output
{100, 100}
```

### Task 1

```elixir
padded = Nx.pad(input, 99, [{0, 0, 0}, {1, 1, 0}])

shifted = Nx.slice_axis(padded, 0, height, :x)

x1 = Nx.less(input, shifted)

shifted = Nx.slice_axis(padded, 2, height, :x)

x2 = Nx.less(input, shifted)

x = Nx.logical_and(x1, x2)

padded = Nx.pad(input, 99, [{1, 1, 0}, {0, 0, 0}])

shifted = Nx.slice_axis(padded, 0, width, :y)

y1 = Nx.less(input, shifted)

shifted = Nx.slice_axis(padded, 2, width, :y)

y2 = Nx.less(input, shifted)

y = Nx.logical_and(y1, y2)

minimas = Nx.logical_and(x, y)

input
|> Nx.multiply(minimas)
|> Nx.sum()
|> Nx.to_number()
```

```output
452
```

### Task 2

```elixir
input
|> Nx.equal(10)
|> Nx.logical_not()
|> Nx.select(Nx.iota(shape), 9999)
|> Nx.to_flat_list()
|> Enum.reject(&(&1 == 9999))
|> Enum.map(fn point -> {div(point, width), rem(point, width)} end)
|> Enum.reduce([], fn {y, x} = point, basins ->
  basin_left = Enum.find_index(basins, &({y, x - 1} in &1))
  basin_up = Enum.find_index(basins, &({y - 1, x} in &1))

  case {basin_left, basin_up} do
    {nil, nil} ->
      [MapSet.new([point]) | basins]

    {idx, nil} ->
      List.update_at(basins, idx, &MapSet.put(&1, point))

    {nil, idx} ->
      List.update_at(basins, idx, &MapSet.put(&1, point))

    {idx, idx} ->
      List.update_at(basins, idx, &MapSet.put(&1, point))

    {idx1, idx2} ->
      {old, basins} = List.pop_at(basins, max(idx1, idx2))

      List.update_at(basins, min(idx1, idx2), &(&1 |> MapSet.union(old) |> MapSet.put(point)))
  end
end)
|> Enum.map(&MapSet.size/1)
|> Enum.sort(:desc)
|> Enum.take(3)
|> Enum.reduce(&*/2)
```

```output
1263735
```