Advent of Code 2021 - Day 3

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.

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))

Here is my solution:

https://github.com/bjorng/advent-of-code-2021/blob/b011b56f37056af67581df31a5ae6ab38fb82c23/day03/lib/day03.ex

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

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.

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))

– 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

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

Thanks for the feedback!

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