Day 3: Binary Diagnostic

2021/03.livemd

Roy Veshovda

@royveshovda

aoc

More notebooks

Day 3: Binary Diagnostic

Intro

https://adventofcode.com/2021/day/3

Input - common

input_test =
  """
  00100
  11110
  10110
  10111
  10101
  01111
  00111
  11100
  10000
  11001
  00010
  01010
  """
  |> String.split("\n", trim: true)

["00100", "11110", "10110", "10111", "10101", "01111", "00111", "11100", "10000", "11001", "00010",
 "01010"]

input =
  File.read!("input03.txt")
  |> String.split("\n", trim: true)

["111010111011", "001011110010", "000110111100", "110101110001", "101110011111", "110011111001",
 "100000110011", "011100101100", "111111000111", "010100001000", "010111000100", "100001000110",
 "110000011011", "011001101110", "001010001101", "010001010010", "000011011101", "000110100001",
 "000100111000", "011101000100", "011000101001", "110111000110", "011001010111", "011110101110",
 "010001111111", "010110001011", "001110010111", "000110000101", "110011110000", "010010101000",
 "101010011001", "010000000000", "101110000001", "001111101010", "000011000110", "101100100001",
 "000001110011", "100110011111", "111011111000", "010010001101", "000000001111", "101011100011",
 "010110001001", "101101101001", "101000001101", "100111111100", "100001011101", "110100111101",
 "010110000111", "110000001010", ...]

Part 1

ones =
  input_test
  |> Enum.map(&amp;String.graphemes/1)
  |> Enum.map(fn x -> Enum.map(x, &amp;String.to_integer/1) end)

[
  [0, 0, 1, 0, 0],
  [1, 1, 1, 1, 0],
  [1, 0, 1, 1, 0],
  [1, 0, 1, 1, 1],
  [1, 0, 1, 0, 1],
  [0, 1, 1, 1, 1],
  [0, 0, 1, 1, 1],
  [1, 1, 1, 0, 0],
  [1, 0, 0, 0, 0],
  [1, 1, 0, 0, 1],
  [0, 0, 0, 1, 0],
  [0, 1, 0, 1, 0]
]

acc = for _n <- hd(ones), do: 0

[0, 0, 0, 0, 0]

count = length(ones)

sums =
  Enum.reduce(ones, acc, fn x, acc -> Enum.zip(acc, x) |> Enum.map(fn {a, b} -> a + b end) end)

[7, 5, 8, 7, 5]

gamma =
  Enum.map(sums, fn x ->
    case x > count / 2,
      do:
        (
          true -> 1
          false -> 0
        )
  end)

[1, 0, 1, 1, 0]

epsilon =
  Enum.map(gamma, fn x ->
    case x,
      do:
        (
          1 -> 0
          0 -> 1
        )
  end)

[0, 1, 0, 0, 1]

defmodule Math do
  def pow(num, power) do
    do_pow(num, power, 1)
  end

  defp do_pow(_num, 0, acc) do
    acc
  end

  defp do_pow(num, power, acc) when power > 0 do
    do_pow(num, power - 1, acc * num)
  end
end

defmodule Convert do
  def binary_list_to_integer(list) do
    do_binary_list_to_integer(Enum.reverse(list), 0, 0)
  end

  defp do_binary_list_to_integer([], _power, acc) do
    acc
  end

  defp do_binary_list_to_integer([head | tail], power, acc) do
    do_binary_list_to_integer(tail, power + 1, acc + head * Math.pow(2, power))
  end
end

{:module, Convert, <<70, 79, 82, 49, 0, 0, 7, ...>>, {:do_binary_list_to_integer, 3}}

g = Convert.binary_list_to_integer(gamma)
e = Convert.binary_list_to_integer(epsilon)
sum = g * e

Correct: 198

Part 1 - run

ones =
  input
  |> Enum.map(&amp;String.graphemes/1)
  |> Enum.map(fn x -> Enum.map(x, &amp;String.to_integer/1) end)

acc = for _n <- hd(ones), do: 0
count = length(ones)

sums =
  Enum.reduce(ones, acc, fn x, acc -> Enum.zip(acc, x) |> Enum.map(fn {a, b} -> a + b end) end)

[487, 512, 502, 505, 481, 501, 483, 497, 514, 508, 490, 533]

gamma =
  Enum.map(sums, fn x ->
    case x > count / 2,
      do:
        (
          true -> 1
          false -> 0
        )
  end)

epsilon =
  Enum.map(gamma, fn x ->
    case x,
      do:
        (
          1 -> 0
          0 -> 1
        )
  end)

[1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0]

g = Convert.binary_list_to_integer(gamma)
e = Convert.binary_list_to_integer(epsilon)
sum = g * e

Correct: 4160394

Part 2 - testing

ones =
  input_test
  |> Enum.map(&amp;String.graphemes/1)
  |> Enum.map(fn x -> Enum.map(x, &amp;String.to_integer/1) end)

[
  [0, 0, 1, 0, 0],
  [1, 1, 1, 1, 0],
  [1, 0, 1, 1, 0],
  [1, 0, 1, 1, 1],
  [1, 0, 1, 0, 1],
  [0, 1, 1, 1, 1],
  [0, 0, 1, 1, 1],
  [1, 1, 1, 0, 0],
  [1, 0, 0, 0, 0],
  [1, 1, 0, 0, 1],
  [0, 0, 0, 1, 0],
  [0, 1, 0, 1, 0]
]

defmodule Filter do
  def run_o2(pos, list) do
    total = length(list)

    counted =
      list
      |> Enum.reduce(0, fn x, acc -> acc + Enum.fetch!(x, pos) end)

    filter = if counted >= total / 2, do: 1, else: 0

    Enum.filter(list, fn x -> Enum.fetch!(x, pos) == filter end)
  end

  def run_co2(pos, list) do
    total = length(list)

    counted =
      list
      |> Enum.reduce(0, fn x, acc -> acc + Enum.fetch!(x, pos) end)

    filter = if counted < total / 2, do: 1, else: 0

    Enum.filter(list, fn x -> Enum.fetch!(x, pos) == filter end)
  end

  def run_o2_with_stop(pos, list) do
    new_list = run_o2(pos, list)

    case length(new_list) do
      1 -> {:halt, new_list}
      _ -> {:cont, new_list}
    end
  end

  def run_co2_with_stop(pos, list) do
    new_list = run_co2(pos, list)

    case length(new_list) do
      1 -> {:halt, new_list}
      _ -> {:cont, new_list}
    end
  end
end

{:module, Filter, <<70, 79, 82, 49, 0, 0, 13, ...>>, {:run_co2_with_stop, 2}}

total = length(ones)
[o2] = Enum.reduce_while(0..(total - 1), ones, fn pos, l -> Filter.run_o2_with_stop(pos, l) end)
o2 = Convert.binary_list_to_integer(o2)

[co2] = Enum.reduce_while(0..(total - 1), ones, fn pos, l -> Filter.run_co2_with_stop(pos, l) end)
co2 = Convert.binary_list_to_integer(co2)
o2 * co2

Part 2 - run

ones =
  input
  |> Enum.map(&amp;String.graphemes/1)
  |> Enum.map(fn x -> Enum.map(x, &amp;String.to_integer/1) end)

[
  [1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1],
  [0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0],
  [0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0],
  [1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1],
  [1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1],
  [1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1],
  [1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1],
  [0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0],
  [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1],
  [0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0],
  [0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0],
  [1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0],
  [1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1],
  [0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0],
  [0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1],
  [0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0],
  [0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1],
  [0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1],
  [0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0],
  [0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0],
  [0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
  [1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0],
  [0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1],
  [0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0],
  [0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1],
  [0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1],
  [0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1],
  [0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1],
  [1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0],
  [0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0],
  [1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1],
  [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1],
  [0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0],
  [0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0],
  [1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1],
  [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1],
  [1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1],
  [1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, ...],
  [0, 1, 0, 0, 1, 0, 0, 0, 1, 1, ...],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, ...],
  [1, 0, 1, 0, 1, 1, 1, 0, ...],
  [0, 1, 0, 1, 1, 0, 0, ...],
  [1, 0, 1, 1, 0, 1, ...],
  [1, 0, 1, 0, 0, ...],
  [1, 0, 0, 1, ...],
  [1, 0, 0, ...],
  [1, 1, ...],
  [0, ...],
  [...],
  ...
]

total = length(ones)
[o2] = Enum.reduce_while(0..(total - 1), ones, fn pos, l -> Filter.run_o2_with_stop(pos, l) end)
o2 = Convert.binary_list_to_integer(o2)

[co2] = Enum.reduce_while(0..(total - 1), ones, fn pos, l -> Filter.run_co2_with_stop(pos, l) end)
co2 = Convert.binary_list_to_integer(co2)
o2 * co2

Correct: 4125600

Back