Advent of Code 2021 - Day 3

Learning Questions & Discussions Coding Challenges
1

Just did part 1. Part 2 seems to be demanding too much of my reading time so will get to that after I am done with some chores.

Oh here is the repository just in case someone wants the template generator.

I just did the dumbest path - read > transpose each > get most and least common > multiply :smiley: I am sure folks will come up with super smart solutions any time now :wink:

defmodule AdventOfCode.Y2021.Day03 do
  @moduledoc """
  --- Day 3: Binary Diagnostic ---
  Problem Link: https://adventofcode.com/2021/day/3
  """
  use AdventOfCode.Helpers.InputReader, year: 2021, day: 3

  def run_1 do
    input!()
    |> parse()
    |> transpose()
    |> bit_frequencies()
    |> get_min_max()
    |> Tuple.product()
  end

  def run_2, do: {:not_implemented, 2}
  def parse(data), do: data |> String.split("\n", trim: true) |> Enum.map(&String.graphemes/1)
  defp transpose(data), do: data |> Enum.zip() |> Enum.map(&Tuple.to_list/1)

  defp bit_frequencies(data) do
    data
    |> Enum.map(&Enum.frequencies/1)
    |> Enum.reduce([], fn
      %{"0" => lo, "1" => hi}, acc when lo > hi -> [{0, 1} | acc]
      _, acc -> [{1, 0} | acc]
    end)
  end

  defp to_integer_by(encoded_data, index) do
    encoded_data
    |> Enum.map_join(&elem(&1, index))
    |> String.reverse()
    |> String.to_integer(2)
  end

  defp get_min_max(encoded_data) do
    {to_integer_by(encoded_data, 0), to_integer_by(encoded_data, 1)}
  end
end
3 Likes
2

There’s a little bit faster solution for part 1, you only need to calculate gamma or epsilon, not both.

Suppose we calculated gamma, then epsilon is just (~~~gamma) &&& 0b111111111111, or (1 <<< 12) - 1 - gamma.

3 Likes
3

Again, my solution:

Part 1

#!/usr/bin/env elixir

use Bitwise

max = ((1 <<< 12) - 1)

gamma =
  File.stream!("input.txt")
  |> Stream.map(&String.trim/1)
  |> Stream.map(&String.split(&1, "", trim: true))
  |> Enum.zip()
  |> Enum.map(&Tuple.to_list/1)
  |> Stream.map(&Enum.frequencies/1)
  |> Stream.map(&Enum.max_by(&1, fn {_, f} -> f end))
  |> Stream.map(&elem(&1, 0))
  |> Enum.join("")
  |> String.to_integer(2)

epsilon = max - gamma

IO.inspect(epsilon * gamma)

Part 2

#!/usr/bin/env elixir

defmodule P2 do
  def o2([elem], _pos), do: to_i(elem)

  def o2(list, pos) do
    groups = Enum.group_by(list, &elem(&1, pos))
    group0 = groups["0"] || []
    group1 = groups["1"] || []
    if length(group0) > length(group1) do
      o2(group0, pos + 1)
    else
      o2(group1, pos + 1)
    end
  end

  def co2([elem], _pos), do: to_i(elem)

  def co2(list, pos) do
    groups = Enum.group_by(list, &elem(&1, pos))
    group0 = groups["0"] || []
    group1 = groups["1"] || []
    if length(group1) < length(group0) do
      co2(group1, pos + 1)
    else
      co2(group0, pos + 1)
    end
  end

  defp to_i(tuple), do:
    tuple
    |> Tuple.to_list()
    |> Enum.join("")
    |> String.to_integer(2)
end

input =
  File.stream!("input.txt")
  |> Stream.map(&String.trim/1)
  |> Stream.map(&String.split(&1, "", trim: true))
  |> Enum.map(&List.to_tuple/1)

IO.inspect(P2.o2(input, 0) * P2.co2(input, 0))
4 Likes
4

Here is my solution:

2 Likes
5

Took me longer than I’d expected for part 2, although it literally had recursion all over it. I misunderstood the question and thought the frequency map was constant (instead of being recomputed per filter).

Anyways, here’s the second part:

defmodule AdventOfCode.Y2021.Day03 do
  @moduledoc """
  --- Day 3: Binary Diagnostic ---
  Problem Link: https://adventofcode.com/2021/day/3
  """
  use AdventOfCode.Helpers.InputReader, year: 2021, day: 3

  def run_2 do
    data = input!() |> parse()
    o2(data, 0) * co2(data, 0)
  end

  def parse(data), do: data |> String.split("\n") |> Enum.map(&String.graphemes/1)

  def o2([result], _), do: to_integer(result)

  def o2(data, idx) do
    value = frequent_by(data, idx, :lo)

    o2(
      Enum.filter(data, &(Enum.at(&1, idx) == value)),
      idx + 1
    )
  end

  def co2([result], _), do: to_integer(result)

  def co2(data, idx) do
    value = frequent_by(data, idx, :hi)

    co2(
      Enum.filter(data, &(Enum.at(&1, idx) == value)),
      idx + 1
    )
  end

  defp frequent_by(data, idx, strategy) do
    data
    |> Enum.map(&Enum.at(&1, idx))
    |> Enum.frequencies()
    |> then(fn
      %{"0" => lo, "1" => hi} when lo > hi -> (strategy == :lo && "0") || "1"
      _ -> (strategy == :lo && "1") || "0"
    end)
  end

  defp to_integer(result), do: result |> Enum.join() |> String.to_integer(2)
end
6

A rough idea, is there a way we can mathematics our way our of Part 2? Like maybe, get the frequencies based on whether the base 10 converted numbers are odd or even?

Update: Naah, that would create more nuance than simple.

7

Feel my solution is kind of ugly; however, I think I took a different approach to determine most common bits, so figured I’d post.

I reduced each bit sequence into a list of the same size. If a bit was 1, increment its position; if 0, decrement. At the end, if the value is > 0, most common was 1, < 0 means 0, and 0 is a tie, represented by -1.

So think my recursion in part 2 is similar to others, I just used Stream.unfold.

defmodule Advent.Y2021.D03 do
  use Bitwise

  @spec part_one(Enumerable.t()) :: integer()
  def part_one(input) do
    mcb = most_common_bits(input)

    max_val = (1 <<< length(mcb)) - 1
    gamma = Integer.undigits(mcb, 2)
    epsilon = max_val - gamma

    gamma * epsilon
  end

  @spec part_two(Enumerable.t()) :: integer()
  def part_two(input) do
    find_o2(input) * find_co2(input)
  end

  @spec most_common_bits(Enumerable.t()) :: [0 | 1]
  defp most_common_bits(input) do
    input
    |> Stream.map(fn bits ->
      Enum.map(bits, fn
        1 -> 1
        0 -> -1
      end)
    end)
    |> Enum.reduce(fn bin, acc ->
      Enum.zip_with(acc, bin, &+/2)
    end)
    |> Enum.map(fn
      b when b > 0 -> 1
      b when b < 0 -> 0
      0 -> -1
    end)
  end

  defp find_o2(input), do: find_life_support(input, :o2)

  defp find_co2(input), do: find_life_support(input, :co2)

  @spec find_life_support(Enumerable.t(), :o2 | :co2) :: integer()
  defp find_life_support(values, strat) do
    Stream.unfold({values, 0}, fn
      {[], _} ->
        nil

      {[final], _} ->
        {[final], {[], nil}}

      {values, idx} ->
        mcb = most_common_bits(values)
        cb = Enum.at(mcb, idx)

        remaining =
          Enum.filter(values, fn v ->
            b = Enum.at(v, idx)

            # ugly
            case strat do
              :o2 -> b == cb || (cb == -1 && b == 1)
              :co2 -> (b != cb && cb != -1) || (cb == -1 && b == 0)
            end
          end)

        {values, {remaining, idx + 1}}
    end)
    |> Enum.reduce_while(nil, fn
      [final], _ -> {:halt, final}
      _, _ -> {:cont, nil}
    end)
    |> Integer.undigits(2)
  end
end

input =
  File.stream!("d03_input.txt")
  |> Stream.map(&String.trim/1)
  |> Stream.map(&String.to_charlist/1)
  |> Stream.map(fn bits ->
    Enum.map(bits, fn
      ?1 -> 1
      ?0 -> 0
    end)
  end)

IO.inspect(Advent.Y2021.D03.part_one(input))
IO.inspect(Advent.Y2021.D03.part_two(input))
1 Like
8

– edited after hauleth’s suggestion below, and also made a single function for the recursion

Here’s mine for Part 2 - didn’t write any function for Part1 - just chained some Enum functions together.

defmodule Day3 do
  def sort_fn_max({k1, v1}, {k2, v2}) when v1 == v2, do: k1 > k2 # Use "1"
  def sort_fn_max({_k1, v1}, {_k2, v2}), do: v1 > v2 
  def sort_fn_min({k1, v1}, {k2, v2}) when v1 == v2, do: k1 < k2 # Use "0"
  def sort_fn_min({_k1, v1}, {_k2, v2}), do: v1 < v2

  def bit_criteria(list, bit_loc, max?) do
    list
    |> Enum.zip
    |> Enum.at(bit_loc)
    |> Tuple.to_list
    |> Enum.frequencies
    |> Map.to_list
    |> Enum.sort(if max?, do: &sort_fn_max/2, else: &sort_fn_min/2)
    |> Enum.at(0)
    |> elem(0)
  end

  def bit_filter(list, bit_loc, max?) do
    x = bit_criteria(list, bit_loc, max?)
    Enum.filter(list, fn bits -> Enum.at(bits, bit_loc) == x end)
  end

  def recurse(list, bit_loc, flag) do
    list = bit_filter(list, bit_loc, flag)
    case list do
      [elem] -> elem
      _ -> recurse(list, bit_loc + 1, flag)
    end
  end
end

contents = String.split(contents) |> Enum.map(&String.graphemes/1)

oxy_rating = Day3.recurse(contents, 0, true)
|> Enum.join
|> String.to_integer(2)

co2_rating = Day3.recurse(contents, 0, false)
|> Enum.join
|> String.to_integer(2)

oxy_rating * co2_rating
1 Like
9 
if length(list) == 1 do
  Enum.at(list, 0)
else
  # …
end

Is slower way of writing:

case list do
  [elem] -> Elem
  _ -> # …
end

My solution, again as a LiveBook:

Day 3

Input

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

Task 1

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

Task 2

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
1 Like
10

Thanks for the feedback!

11

Just remember that length/1 is linear wrt the length of the list passed as an argument. Pattern matching against [elem] is constant.

2 Likes
12

Thanks a lot. I too missed the fact, that I have to recompute the frequency map for each iteration. :slight_smile:

2 Likes
13

My solution: y2021/d3.ex

1 Like
14

Here is my solution: 0x76/aoc2021 - lib/day03.ex at main - aoc2021 - Gitea: Git with a cup of tea
I tried my hand at using Nx for part 1 but I didn’t know to effectively use it for the filter part of part 2

1 Like
15

Here’s mine: y2021/day_03.ex

1 Like
16

My solution basically revolves around

defp count_ones_per_index(tuple, counts) do
  Enum.reduce(0..11, counts, fn idx, acc ->
    Map.update!(acc, idx, &(&1 + elem(tuple, idx)))
  end)
end
1 Like
17

Livebook again :wave: I don’t know why I keep working just with anonymous functions but it was kinda fun (pun intended).

Turns out that anonymous functions don’t support recursion but I found José mentioning Elixir will support it in the future (2014). Does anyone know what happened? I hacked around it using by passing fun.

Somehow my Part 2 ended much shorter than Part 1. Mostly thanks to pattern matching and the recursion logic.

As always, just copy the code and you can import it directly into the Livebook :pray:

# Day 2

## Input

<!-- livebook:{"livebook_object":"cell_input","name":"input","type":"text","value":"00100 11110 10110 10111 10101 01111 00111 11100 10000 11001 00010 01010"} -->

```elixir
processed =
  IO.gets(:input)
  |> String.split(~r{\s}, trim: true)
```

## Part 1

```elixir
# helpers
ind_len = String.length(Enum.at(processed, 0))
convert = fn data_list -> Enum.join(data_list) |> String.to_integer(2) end
###

gamma =
  processed
  |> Enum.reduce(
    List.duplicate(0, ind_len),
    fn bits, stats ->
      bits
      |> String.graphemes()
      |> Enum.with_index()
      |> Enum.map(fn {c, index} ->
        Enum.at(stats, index) + String.to_integer(c)
      end)
    end
  )
  |> Enum.map(fn n_ones ->
    if n_ones > div(length(processed), 2), do: 1, else: 0
  end)
  |> convert.()

epsilon =
  gamma
  |> Bitwise.~~~()
  |> Bitwise.&&&(String.duplicate("1", ind_len) |> String.to_integer(2))

gamma * epsilon
```

## Part 2

```elixir
# helpers
convert = fn data -> Enum.join(data) |> String.to_integer(2) end
###

converted_entries =
  processed
  |> Enum.map(fn bits ->
    String.graphemes(bits) |> Enum.map(&String.to_integer/1)
  end)

# Expects:
# list -> list of split converted bits eq.: [[0,1,0],[1,0,1]]
# index -> starting index eq.: 0
# sorter -> which value takes precendence when comparing eq.: &>/2
b_reduce = fn list, index, sorter ->
  Enum.group_by(list, &Enum.at(&1, index))
  |> Enum.max_by(fn {_k, v} -> length(v) end, sorter)
  |> elem(1)
end

slvr = fn
  [final], _, _, _ -> convert.(final)
  list, i, sorter, fun -> b_reduce.(list, i, sorter) |> fun.(i + 1, sorter, fun)
end

slvr.(converted_entries, 0, &>/2, slvr) * slvr.(converted_entries, 0, &<=/2, slvr)
```
1 Like
18

AFAIK Core lost interest in it as the use case for that was mostly the shell and in IEx you can generate modules on the fly, which is not easily doable in Erlang Shell. However if you want to achieve the same thing, then you can use power of macros for that:

defmodule Foo do
  defmacro fn_rec(do: body) do
    {name, argc, body} =
      body
      |> Enum.map(fn
        {:'->', e1, [[{:when, e2, [{name, _, args}, guard]}], body]} ->
          {name, length(args), {:'->', e1, [[{:when, e2, args ++ [guard]}], body]}}

        {:'->', e1, [[{name, _, args}], body]} ->
          {name, length(args), {:'->', e1, [args, body]}}
      end)
      |> Enum.reduce(fn {name, argc, body}, {name, argc, acc} ->
        {name, argc, List.wrap(acc) ++ [body]}
      end)

    args = Macro.generate_arguments(argc, __CALLER__.module)
    func = {:fn, [], body}
    name = {name, [], Elixir}

    quote do
      tmp =
        fn f ->
          var!(unquote(name)) = fn unquote_splicing(args) -> f.(f).(unquote_splicing(args)) end
          unquote(func)
        end

      tmp.(tmp)
    end
  end

  def run do
    ack =
      fn_rec do
        a(0, n) -> n + 1
        a(m, 0) -> a.(m - 1, 1)
        a(m, n) -> a.(m - 1, a.(m, n - 1))
      end

    ack.(3, 4)
  end
end

IO.puts Foo.run
2 Likes
19

And mine.
Part 2 revolves around

  def group_by_position(matrix, position) do
    Enum.group_by(
      matrix,
      fn row -> Enum.at(row, position) end
    )
  end

  def find_most_common([row], _, _) do
    row
  end

  def find_most_common(matrix, position, sorter) do
    grouped = group_by_position(matrix, position)
    {_, max_matrix} = Enum.max_by(grouped, fn {k, v} -> {length(v), k} end, sorter)
    find_most_common(max_matrix, position + 1, sorter)
  end

and then called as

oxigen_generator_rating =
  Support.input()
  |> Support.find_most_common(:gte)
  |> Support.row_to_number()

co2_scrubber_rating =
  Support.input()
  |> Support.find_most_common(:lte)
  |> Support.row_to_number()
2 Likes
20

Late to the party…

defmodule Day3 do
  def part1 do
    frequencies = load_data()
    |> reshape()
    |> to_frequencies()

    gamma_rate = get_rate(frequencies, &most_common_reducer/2)
    epsilon_rate = get_rate(frequencies, &least_common_reducer/2)
    gamma_rate * epsilon_rate
  end

  def part2 do
    oxygen_generator_rating = filter_and_pop(load_data(), <<>>, :most)
    co2_scrubber_rating = filter_and_pop(load_data(), <<>>, :least)

    oxygen_generator_rating * co2_scrubber_rating
  end

  defp filter_and_pop([el], result, _mode) do
    String.to_integer(result <> el, 2)
  end

  defp filter_and_pop(list, result, mode) do
    freq = first_position_frequencies(list)
    {zero, one} = {freq["0"], freq["1"]}

    char = case  mode do
      :most -> if zero > one, do: "0", else: "1"
      :least -> if zero <= one, do: "0", else: "1"
    end

    popped = list
    |> Enum.filter(&String.starts_with?(&1, char))
    |> Enum.map(fn <<_::utf8, rest::binary>> -> rest end)

    filter_and_pop(popped, result <> char, mode)
  end

  defp first_position_frequencies(list) do
    list
    |> Enum.map(&String.first(&1))
    |> Enum.frequencies()
  end

  def load_data do
    "input.txt"
    |> File.read!()
    |> String.split("\n", trim: true)
  end

  defp reshape([h|_] = list) do
    initial = List.duplicate(<<>>, String.length(h))

    Enum.reduce(list, initial, fn x, acc ->
      record = String.split(x, "", trim: true)

      acc
      |> Enum.zip(record)
      |> Enum.map(fn {full, add} ->
        full <> add
      end)
    end)
  end

  defp to_frequencies(list) when is_list(list),
    do: Enum.map(list, &to_frequency(&1))

  defp to_frequency(string) when is_binary(string) do
    string
    |> String.split("", trim: true)
    |> Enum.frequencies()
  end

  def get_rate(frequencies, reducer) do
    frequencies
    |> Enum.reduce(<<>>, reducer)
    |> String.to_integer(2)
  end

  defp most_common_reducer(%{"0"=>zero, "1"=>one}, acc),
    do: if zero > one, do: acc <> "0", else: acc <> "1"

  defp least_common_reducer(%{"0"=>zero, "1"=>one}, acc),
    do: if zero < one, do: acc <> "0", else: acc <> "1"
end
1 Like