Advent of Code 2021 - Day 3

I wanted to keep it pipeline-y. I feel like there has to be a way to do something similar in one pass, but I couldn’t figure it out before Day 4.

# Part 1
"day3.txt"
|> File.stream!
|> Enum.map(fn line -> String.split(line, "", trim: true) end)
|> Enum.zip_with(&Enum.frequencies/1)
|> Enum.map(fn counts -> if counts["0"] > counts["1"], do: ["0", "1"], else: ["1", "0"] end)
|> Enum.zip_with(&Enum.join/1)
|> Enum.reduce(1, fn number, product -> String.to_integer(number, 2) * product end)

# Part 2
defmodule Day3 do
  def input() do
    "day3.txt"
    |> File.stream!
    |> Enum.map(&String.trim/1)
  end

  def oxygen([final_value], _position) do
    String.to_integer(final_value, 2)
  end

  def oxygen(data, position) do
    data
    |> Enum.group_by(fn num -> String.at(num, position) end)
    |> Enum.max_by(&number_sorter/1)
    |> elem(1)
    |> oxygen(position + 1)
  end

  def carbon([final_value], _position) do
    String.to_integer(final_value, 2)
  end

  def carbon(data, position) do
    data
    |> Enum.group_by(fn num -> String.at(num, position) end)
    |> Enum.min_by(&number_sorter/1)
    |> elem(1)
    |> carbon(position + 1)
  end

  defp number_sorter({target_bit, bit_list}) do
    length(bit_list) + 0.1 * String.to_integer(target_bit)
  end
end

data = Day3.input()
Day3.oxygen(data, 0) * Day3.carbon(data, 0)
1 Like

how do you know to do the bitwise NOT and then AND with 0b111111111111? I thought of negation using the NOT operator but it gives this crazy negative number. What’s that about?

I noticed that for each bit in the binary numbers, if the majority is 1, then the minority is definitely 0, and vice versa. So if the corresponding bit in gamma is 1, then that bit in epsilon is definitely 0.

1 Like

No, I get that. I mean, why doesn’t the ~~~ operator work without the &&& 0b111111111111?

I added &&& 0b111111111111 just for safety. I don’t know how many bits does an integer contain by default, but probably more than 12 bits.

1 Like

The ~~~ operator when given a positive number always returns a negative number. It does that simulate that an integer holds an infinite number of bits. If the number starts with an infinite number of ones, the number is negative. If it starts with an infinite number of zeroes, it is positive.

When I first learned Erlang, it took me a while to figure out why that’s make sense.

Yes, an infinite number of bits. Fortunately the runtime system is smart enough to not store all them explicitly. :wink:

5 Likes

My solution: aoc/day-03.livemd at main · josevalim/aoc · GitHub

Live streaming: Twitch - we also solved part 1 with Nx and had a bit of fun with Livebook. :slight_smile:

4 Likes

Did you put that <!-- vim: syntax=markdown --> on top of your livemd file manualy or is that some setting in the Livebook?

Manually. Livebook will preserve it though (but maybe it requires latest).

1 Like

so negation in erlang flips all the infinite preceding zeroes? Is there a practical reason for that? Is it just to avoid the need for distinct sized integer types like u8, u16, i32, etc? Would you always get an accurate answer by masking with ones in all places up to the bitsize you need? Would it be safe to just mask by 4294967295 unless your values exceed u32 max size?

Sure we are at Day 4 now and nobody will read it, but still my solution for the Day 3, part one + tests.
Kind of ugly solution, but I was trying to use pattern matching as much as I can and was trying to avoid iteration all the way.

defmodule AOC_2021.Day3 do
  @input "input_3.txt"

  @initial_list_of_tuples [{"0", 0}, {"1", 0}]
  @acc [
    @initial_list_of_tuples,
    @initial_list_of_tuples,
    @initial_list_of_tuples,
    @initial_list_of_tuples,
    @initial_list_of_tuples,
    @initial_list_of_tuples,
    @initial_list_of_tuples,
    @initial_list_of_tuples,
    @initial_list_of_tuples,
    @initial_list_of_tuples,
    @initial_list_of_tuples,
    @initial_list_of_tuples
  ]

  def part_one do
    @input
    |> read_file()
    |> find_max_min_occ()
    |> to_gamma_epsilon()
    |> count()
  end

  defp find_max_min_occ(list_of_strings) do
    Enum.reduce(
      list_of_strings,
      @acc,
      fn <<first::binary-size(1)>> <>
           <<second::binary-size(1)>> <>
           <<third::binary-size(1)>> <>
           <<fourth::binary-size(1)>> <>
           <<fifth::binary-size(1)>> <>
           <<six::binary-size(1)>> <>
           <<seven::binary-size(1)>> <>
           <<eight::binary-size(1)>> <>
           <<nine::binary-size(1)>> <>
           <<ten::binary-size(1)>> <>
           <<eleven::binary-size(1)>> <>
           <<twelve::binary-size(1)>>,
         [
           o,
           t,
           th,
           fo,
           fi,
           si,
           se,
           ei,
           ni,
           te,
           el,
           tw
         ] ->
        [
          form_in_order(o, first),
          form_in_order(t, second),
          form_in_order(th, third),
          form_in_order(fo, fourth),
          form_in_order(fi, fifth),
          form_in_order(si, six),
          form_in_order(se, seven),
          form_in_order(ei, eight),
          form_in_order(ni, nine),
          form_in_order(te, ten),
          form_in_order(el, eleven),
          form_in_order(tw, twelve)
        ]
      end
    )
  end

  defp form_in_order([{k1, v1}, {k2, v2}], item) when k1 == item do
    t = [{k1, v1 + 1}, {k2, v2}]
    [{k1, v1}, {k2, v2}] = t
    if v1 > v2, do: [{k1, v1}, {k2, v2}], else: [{k2, v2}, {k1, v1}]
  end

  defp form_in_order([{k1, v1}, {k2, v2}], _item), do: [{k1, v1}, {k2, v2 + 1}]

  defp to_gamma_epsilon(list_of_maps) do
    Enum.reduce(list_of_maps, {"", ""}, fn [{k1, _}, {k2, _}], {gm, ep} ->
      {gm <> k1, ep <> k2}
    end)
  end

  defp count({gm, ep}) do
    gm = Integer.parse(gm, 2) |> elem(0)
    ep = Integer.parse(ep, 2) |> elem(0)
    gm * ep
  end

  defp read_file(input) do
    input
    |> File.read!()
    |> String.trim()
    |> String.split(["\n"])
  end
end

case System.argv() do
  ["--test"] ->
    ExUnit.start()

    defmodule AOC_2021.Day3Test do
      use ExUnit.Case

      @expected_part_one 3_901_196

      test "tests" do
        response = fn _ ->
          [
            AOC_2021.Day3.part_one()
          ]
        end

        assert [@expected_part_one] ==
                 response.(3_901_196)
      end
    end

  ["--run"] ->
    AOC_2021.Day3.part_one()
    |> IO.inspect(label: "\npart_one \n")

  _ ->
    IO.puts(:stderr, "\nplease specify --run or --test flag")
end

Yes, that is the reason. Since Erlang has no static types, it seems to be the only reasonable way to implement integers of arbitrary size.

Yes. No. You must mask with a mask of the correct size.

1 Like

Many thanks for the kind explanation.

1 Like

Hey all, for those that want to watch a recap of Jose’s Day 3 stream, I edited something together in a shorter format: José Valim and Twitch Chat Solves Advent of Code 2021 (Day 3) - YouTube. I’ve done this for the first 2 days, and I’m also doing this for all the upcoming AoC days!

Each video has:

  • Chapter markers for every single one so you could get a rough overview of the video and can skip to different parts if you wish.
  • Twitch chat screenshots for additional context
  • Jose’s planning process
  • Errors Jose runs into with explanations (if available) on how to resolve it. He’s a good speaker so usually more context is provided.

Let me know what you want to be added/improved to make this easier to digest. I hope these will be useful!

2 Likes

part 1:

part 2:

I did it with bitstrings. But I wasn’t clever enough to notice you can skip calculating eplison.

Also, yes I know it’s 2022. Had submarine problems.

  def part2(input) do
    oxygen_generator_rating = find_rating2(input, 0, :most)
    co2_scrubber_rating = find_rating2(input, 0, :least)
    oxygen_generator_rating * co2_scrubber_rating
  end

  defp find_rating2([bits], _bits_seen, _mode) do
    <<value::size(bit_size(bits))>> = bits
    value
  end

  defp find_rating2(values, bits_seen, mode) do
    bit = find_common(values, bits_seen, mode)

    values
    |> filter_by_bit(bits_seen, bit)
    |> find_rating2(bits_seen + 1, mode)
  end

  defp find_common(values, bits_seen, mode) do
    {zeros, ones} =
      values
      |> Enum.map(fn <<_::size(bits_seen), bit::1, _rest::bits>> -> bit end)
      |> Enum.reduce({_zeros = 0, _ones = 0}, fn
        0, {zeros, ones} -> {zeros + 1, ones}
        1, {zeros, ones} -> {zeros, ones + 1}
      end)

    case mode do
      :most -> if zeros <= ones, do: 1, else: 0
      :least -> if zeros <= ones, do: 0, else: 1
    end
  end

  defp filter_by_bit(values, num_prev_bits, bit) do
    Enum.filter(values, &match?(<<_::size(num_prev_bits), ^bit::1, _rest::bits>>, &1))
  end