Advent of Code 2020 - Day 14

Hello, everyone. I’m back. This year I didn’t want to do every AOC puzzle the minute it was posted every day for 25 straight days as I did the last two years. Two weeks in I realized that I missed this yearly opportunity to learn some more Elixir, so I will drop in here now and then, probably doing some of the puzzles out of order.

Today’s puzzle was a fun one. Here is my solution.

I did not use bitwise operators. The input is sufficiently small so I just set X bits one by one for part 2

The parse_input! is piped into part_one and part_two by external runner code or unit tests.

defmodule Aoe.Y20.Day14 do
  alias Aoe.Input, warn: false

  @type input_path :: binary
  @type file :: input_path | %Aoe.Input.FakeFile{}
  @type part :: :part_one | :part_two
  @type input :: binary | File.Stream.t()
  @type problem :: any

  @spec read_file!(file, part) :: input
  def read_file!(file, _part) do
    Input.stream_file_lines(file, trim: true)
  end

  @spec parse_input!(input, part) :: problem
  def parse_input!(input, _part) do
    input
    |> Stream.map(&parse_line/1)
  end

  defp parse_line("mask = " <> line) do
    mask =
      line
      |> String.to_charlist()
      |> :lists.reverse()
      |> Enum.map(fn
        ?X -> :X
        ?0 -> 0
        ?1 -> 1
      end)
      |> Enum.with_index()

    {:mask, mask}
  end

  @re_op ~r/^mem\[(\d+)\] = (\d+)$/

  defp parse_line(op) do
    [addr, val] = Regex.run(@re_op, op, capture: :all_but_first)
    {:value, {String.to_integer(addr), String.to_integer(val)}}
  end

  def initial() do
    %{}
  end

  def part_one(stream) do
    stream
    |> Enum.reduce({initial(), nil}, &handle_input_p1/2)
    |> elem(0)
    |> Enum.reduce(0, fn {_, val}, acc -> val + acc end)
  end

  defp handle_input_p1({:mask, mask}, {map, _old_mask}) do
    mask = Enum.reject(mask, fn {bit, _} -> bit == :X end)
    {map, mask}
  end

  defp handle_input_p1({:value, {addr, value}}, {map, mask}) do
    map = Map.put(map, addr, mask_value(value, mask))
    {map, mask}
  end

  defp mask_value(value, mask) do
    masked =
      Enum.reduce(mask, <<value::integer-36>>, fn {bit, pos}, bin ->
        left_bits = 36 - pos - 1
        right_bits = pos
        <<left::size(left_bits), _::size(1), right::size(right_bits)>> = bin
        <<left::size(left_bits), bit::size(1), right::size(right_bits)>>
      end)

    <<masked::integer-36>> = masked
    masked
  end

  def part_two(stream) do
    stream
    |> Enum.reduce({initial(), nil}, &handle_input_p2/2)
    |> elem(0)
    |> Enum.reduce(0, fn {_, val}, acc -> val + acc end)
  end

  defp handle_input_p2({:mask, mask}, {map, _old_mask}) do
    {map, mask}
  end

  defp handle_input_p2({:value, {addr, value}}, {map, mask}) do
    addresses = mask_addrs([addr], mask) |> :lists.flatten()
    map = Enum.reduce(addresses, map, &Map.put(&2, &1, value))
    {map, mask}
  end

  defp mask_addrs(addrs, [{0, _} | mask]) do
    mask_addrs(addrs, mask)
  end

  defp mask_addrs(addrs, [{1, pos} | mask]) do
    addrs = Enum.map(addrs, &set_bit(&1, pos, 1))
    mask_addrs(addrs, mask)
  end

  defp mask_addrs(addrs, [{:X, pos} | mask]) do
    [
      mask_addrs(Enum.map(addrs, &set_bit(&1, pos, 0)), mask),
      mask_addrs(Enum.map(addrs, &set_bit(&1, pos, 1)), mask)
    ]
  end

  defp mask_addrs(addrs, []) do
    addrs
  end

  defp set_bit(addr, pos, v) do
    left_bits = 36 - pos - 1
    right_bits = pos
    <<left::size(left_bits), _::size(1), right::size(right_bits)>> = <<addr::integer-36>>
    <<masked::integer-36>> = <<left::size(left_bits), v::size(1), right::size(right_bits)>>
    masked
  end
end

It is not fast (the part_two function terminates in 150ms) but the code is simple to reason about so it is fine to me

Today I reinstalled the operating system on my laptop, and I just finished recovering my GitHub account, so it’s a bit late to post my solutions to today’s quizzes.

I didn’t use bitwise operations, either, because I couldn’t find a neat one. I hope to see some smart solutions.

Anyway, here’s my solution:

Part 1

#!/usr/bin/env elixir

initial_state = %{
  mem: %{},
  mask: ""
}

parse_mem_set = fn line ->
  [address, value] = Regex.run(~r/^mem\[(\d+)\] = (\d+)$/, line, capture: :all_but_first)
  {address, value}
end

apply_mask = fn value, mask ->
  value = value
          |> String.to_integer()
          |> Integer.to_string(2)
          |> String.pad_leading(36, "0")
          |> :binary.bin_to_list()

  mask
  |> :binary.bin_to_list()
  |> Enum.zip(value)
  |> Enum.map(fn
    {?0, _} -> ?0
    {?1, _} -> ?1
    {?X, v} -> v
  end)
  |> List.to_integer(2)
end

"day14.txt"
|> File.stream!()
|> Stream.map(&String.trim/1)
|> Enum.reduce(initial_state, fn
  "mask = " <> mask, state -> %{state | mask: mask}
  "mem" <> _ = line, state ->
    {address, value} = parse_mem_set.(line)
    masked_value = apply_mask.(value, state.mask)
    put_in(state, [:mem, String.to_integer(address)], masked_value)
end)
|> Map.get(:mem)
|> Map.values()
|> Enum.sum()
|> IO.inspect()

Part 2

#!/usr/bin/env elixir

initial_state = %{
  mem: %{},
  mask: ""
}

parse_mem_set = fn line ->
  [address, value] = Regex.run(~r/^mem\[(\d+)\] = (\d+)$/, line, capture: :all_but_first)
  {address, value}
end

do_mask = fn zipped ->
  # acc is a list of lists of codepoints.
  zipped
  |> Enum.reduce([[]], fn
    {?0, v}, acc -> Enum.map(acc, &[v  | &1])
    {?1, _}, acc -> Enum.map(acc, &[?1 | &1])
    {?X, _}, acc -> Enum.map(acc, &[?0 | &1]) ++ Enum.map(acc, &[?1 | &1])
  end)
  |> Enum.map(&Enum.reverse/1)
  |> Enum.map(&List.to_integer(&1, 2))
end

apply_mask = fn address, mask ->
  address = address
            |> String.to_integer()
            |> Integer.to_string(2)
            |> String.pad_leading(36, "0")
            |> :binary.bin_to_list()

  mask
  |> :binary.bin_to_list()
  |> Enum.zip(address)
  |> do_mask.()
end

"day14.txt"
|> File.stream!()
|> Stream.map(&String.trim/1)
|> Enum.reduce(initial_state, fn
  "mask = " <> mask, state -> %{state | mask: mask}
  "mem" <> _ = line, state ->
    {address, value} = parse_mem_set.(line)
    masked_addresses = apply_mask.(address, state.mask)
    for address <- masked_addresses, reduce: state do
      st -> put_in(st, [:mem, address], String.to_integer(value))
    end
end)
|> Map.get(:mem)
|> Map.values()
|> Enum.sum()
|> IO.inspect()

Hi there

Part1 was easy to me (used Bitwise operator), but I struggled with recursion for Part2 until I found out that I could manage without recursion

My code here :

Part1 / Part2

  def run_program_chunk({mask, instructions}, memory) do
    {or_mask, _} = mask |> String.replace("X", "0") |> Integer.parse(2)
    {and_mask, _} = mask |> String.replace("X", "1") |> Integer.parse(2)

    Enum.reduce(instructions, memory, fn {address, value}, memory ->
      Map.put(memory, address, (value ||| or_mask) &&& and_mask)
    end)
  end

EDIT : simplified my Part 2 code, to remove a lot of string manipulations

  def find_addresses(address_and_mask) do
    Enum.reduce(address_and_mask, [0], fn
      {_, "X"}, acc -> fork(acc)
      {_, "1"}, acc -> add_bit(acc, 1)
      {"1", _}, acc -> add_bit(acc, 1)
      _, acc -> add_bit(acc, 0)
    end)
  end

  def add_bit(acc, bit), do: Enum.map(acc, &(&1 * 2 + bit))
  def fork(acc), do: Enum.flat_map(acc, &[&1 * 2, &1 * 2 + 1])

Mostly straightforward bitwise operations, nothing interesting I guess.

Main section from part two:

    defp recur_x_bits(addr, [], mem, value), do: Map.put(mem, addr, value)

    defp recur_x_bits(addr, [pos | x_bits], mem, value) do
      mem = recur_x_bits(addr, x_bits, mem, value)
      recur_x_bits(addr ||| 1 <<< pos, x_bits, mem, value)
    end

    defp process({:mem, addr, value}, %{mask: mask, mem: mem} = state) do
      {or_mask, and_mask, x_bits} = mask
      addr = (addr ||| or_mask) &&& and_mask
      %{state | mem: recur_x_bits(addr, x_bits, mem, value)}
    end

Part 1: simple, pretty straightforward. Part 2: ugly. So ugly.

defmodule Day14 do
  def readinput() do
    File.read!("14.input.txt")
    |> String.split("\n", trim: true)
    |> Enum.map(&String.split/1)
    |> Enum.map(&parse/1)
  end

  def parse(["mask", "=", maskstr]), do: {:setmask, String.graphemes(maskstr)}

  def parse([memstr, "=", value]) do
    addr =
      Regex.run(~r/\[(\d+)\]/, memstr, capture: :all_but_first)
      |> hd()

    {:setmem, String.to_integer(addr), String.to_integer(value)}
  end

  def tobinlist(number) do
    number
    |> Integer.to_string(2)
    |> String.pad_leading(36, "0")
    |> String.graphemes()
  end

  def part1(program \\ readinput()) do
    run(program, &run1/2)
  end

  def part2(program \\ readinput()) do
    run(program, &run2/2)
  end

  def run(program, reducer) do
    Enum.reduce(program, %{}, reducer)
    |> Map.drop([:mask])
    |> Map.values()
    |> Enum.reduce(&Kernel.+/2)
  end

  def run1({:setmask, mask}, memory), do: Map.put(memory, :mask, mask)

  def run1({:setmem, location, value}, memory) do
    maskedval = applymask1(tobinlist(value), Map.get(memory, :mask), [])
    Map.put(memory, location, maskedval)
  end

  def applymask1([], [], sofar) do
    sofar
    |> Enum.reverse()
    |> Enum.join("")
    |> String.to_integer(2)
  end

  def applymask1([digit | num], [m | mask], sofar) do
    case m do
      "X" -> applymask1(num, mask, [digit | sofar])
      "0" -> applymask1(num, mask, ["0" | sofar])
      "1" -> applymask1(num, mask, ["1" | sofar])
    end
  end

  def run2({:setmask, mask}, memory), do: Map.put(memory, :mask, mask)

  def run2({:setmem, location, value}, memory) do
    location
    |> tobinlist()
    |> mask2(Map.get(memory, :mask), [])
    |> Enum.reduce(memory, fn addr, memory -> Map.put(memory, addr, value) end)
  end

  # argh
  # bad code below

  def exp2(0), do: 1
  def exp2(n) when n > 0, do: 2 * exp2(n - 1)

  def mask2([], [], sofar) do
    addrmask = Enum.reverse(sofar)

    # find the "X" indexes in the mask, will return something like [30, 35]
    xs =
      Enum.with_index(addrmask)
      |> Enum.filter(fn {a, _} -> a == "X" end)
      |> Enum.map(&elem(&1, 1))

    numxs = Enum.count(xs)

    # for numxs = 4, this will return ["00", "01", "10", "11"] with indexes, as
    # [{"0", 0}, {"0", 1}],
    # [{"0", 0}, {"1", 1}],
    # [{"1", 0}, {"0", 1}],
    # [{"1", 0}, {"1", 1}]
    # the second digit indexes into xs
    # the first digit is what we replace into that position
    for i <- 0..(exp2(numxs) - 1) do
      Integer.to_string(i, 2)
      |> String.pad_leading(numxs, "0")
      |> String.graphemes()
      |> Enum.with_index()
    end
    |> Enum.map(fn v1 ->
      replace(addrmask, xs, v1)
      |> Enum.join()
      |> String.to_integer(2)
    end)
  end

  def mask2([digit | num], [m | mask], sofar) do
    case m do
      "X" -> mask2(num, mask, ["X" | sofar])
      "0" -> mask2(num, mask, [digit | sofar])
      "1" -> mask2(num, mask, ["1" | sofar])
    end
  end

  def replace(sofar, _xs, []), do: sofar

  def replace(sofar, xs, [{v, i} | rest]) do
    List.replace_at(sofar, Enum.at(xs, i), v)
    |> replace(xs, rest)
  end
end

Part 1 was pretty simple.

For part 2 I’ve tried to used some stuff I made for part one : what a mistake. I spend a lot time figuring out that the way mask is applied in part 2 is not the same as part 1.

At the end, it works, but it’s a bit ugly. Since I convert everything to ints, I use a floating bit mask where each floating point is set to 1. And a recursion to find address combinations :

def permutations(base, fbits) do
    permutations(base, fbits, 64)
  end

  # the recursion halts when there is no more floating bits to check
  def permutations(addr, _fbits, shift) when shift < 0 do
    [addr]
  end

  # while there is floating bits
  def permutations(addr, fbits, shift) do
    # check if current bit is a floating one
    if (fbits &&& 1 <<< shift) >>> shift == 1 do
      # and_mask is like setting the current floating bit to 0
      and_mask = (1 <<< 65) - 1 - (1 <<< shift)
      # or_mask is like setting the current floating bit to 1
      or_mask = 1 <<< shift

      # the recursive call collects all sub solutions
      permutations(addr &&& and_mask, fbits, shift - 1) ++
        permutations(addr ||| or_mask, fbits, shift - 1)
    else
      permutations(addr, fbits, shift - 1)
    end
  end

Full code for part 1 and 2

Edit, after some clean up and refacto, it’s quite nice in fact !

Bitwise FTW.

defmodule Aoc2020.Day14 do
  use Bitwise
  import String, only: [replace: 3, to_integer: 2]
  @length 36
  @max_addr round(:math.pow(2, @length) - 1)

  def part1(input) do
    for instruction <- Enum.to_list(input), reduce: {%{}, {0, {0, 0}}} do
      {mem, {m1, m2}} ->
        case instruction do
          {:mask, mask} ->
            {mem,
             {mask
              |> replace("1", "0")
              |> replace("X", "1")
              |> to_integer(2),
              mask
              |> replace("X", "0")
              |> to_integer(2)}}

          {:mem, addr, value} ->
            new_value = bxor(m1 &&& value, m2)
            {Map.put(mem, addr, new_value), {m1, m2}}
        end
    end
    |> elem(0)
    |> Map.values()
    |> Enum.sum()
  end

  def part2(input) do
    for instruction <- Enum.to_list(input), reduce: {%{}, {0, 0}} do
      {mem, {x_mask, one_mask}} ->
        case instruction do
          {:mask, mask} ->
            x_mask =
              mask
              |> replace("1", "0")
              |> replace("X", "1")
              |> to_integer(2)

            one_mask =
              mask
              |> replace("X", "0")
              |> to_integer(2)

            {mem,
             {
               x_mask,
               one_mask
             }}

          {:mem, addr, value} ->
            base_addr = bxor(one_mask, bxor(@max_addr, one_mask ||| x_mask) &&& addr)
            {write_mem(mem, base_addr, value, flips(x_mask)), {x_mask, one_mask}}
        end
    end
    |> elem(0)
    |> Map.values()
    |> Enum.sum()
  end

  def write_mem(mem, _base_addr, _value, []), do: mem

  def write_mem(mem, base_addr, value, [mask | rest]) do
    flipped_addr = bxor(base_addr, mask)

    mem
    |> Map.put(base_addr, value)
    |> write_mem(base_addr, value, rest)
    |> Map.put(flipped_addr, value)
    |> write_mem(flipped_addr, value, rest)
  end

  def flips(x_mask), do: flips(x_mask, 1)
  def flips(0, _), do: []

  def flips(x_mask, x) when (x_mask &&& 1) === 1 do
    [x | flips(x_mask >>> 1, x <<< 1)]
  end

  def flips(x_mask, x) do
    flips(x_mask >>> 1, x <<< 1)
  end

  def input(path) do
    path
    |> File.stream!()
    |> Stream.map(&parse/1)
  end

  def parse(line) do
    line
    |> String.trim()
    |> String.split(" = ")
    |> case do
      ["mask", mask] ->
        {:mask, mask}

      ["mem[" <> pos, value] ->
        {:mem, String.to_integer(String.slice(pos, 0..-2)), String.to_integer(value)}
    end
  end
end

input = Aoc2020.Day14.input("input.txt")

Aoc2020.Day14.part1(input)
|> IO.inspect(label: "part1")

Aoc2020.Day14.part2(input)
|> IO.inspect(label: "part2")

part 1 and 2

was not concerned with clean code or performance today
just to win +2 gold stars

defmodule Advent.Day14 do

  def start(part \\ :part1, file \\ "/tmp/input.txt"), do:
    file |> File.read!() |> String.split(["\n"]) |> Enum.reduce({part, nil, %{}}, &process_command/2) |> elem(2) |> Map.values() |> Enum.sum()

  defp process_command(["mask", _, mask], {part, _, mem}), do: {part, mask |> to_charlist() |> Enum.reverse(), mem}
  defp process_command([mem_addr, _, value_str], {:part1, mask, mem}), do:
    value_str |> String.to_integer() |> Integer.to_string(2) |> to_charlist() |> Enum.reverse() |> apply_mask(mask, "", :part1) |> store_mem(mem, mem_addr, mask, :part1)
  defp process_command([mem_addr, _, value_str], {:part2, mask, mem}), do:
    mem_addr |> get_mem_addr() |> Integer.to_string(2) |> to_charlist() |> Enum.reverse() |> apply_mask(mask, "", :part2) |> to_charlist()
    |> generate_mask([[]]) |> store_mem(mask, mem, String.to_integer(value_str), :part2)
  defp process_command("", acc), do: acc
  defp process_command(line, acc), do: process_command(String.split(line), acc)

  defp store_mem(new_value, mem, mem_addr, mask, :part1), do: {:part1, mask, Map.put(mem, mem_addr, new_value)}
  defp store_mem(mem_addrs, mask, mem, new_value, :part2), do: {:part2, mask, mem_addrs |> Enum.reduce(mem, fn addr, acc -> Map.put(acc, addr, new_value) end) }

  defp apply_mask(_, [], acc, :part2), do: acc
  defp apply_mask(_, [], acc, _), do: String.to_integer(acc, 2)
  defp apply_mask([], [49|t2], acc, part), do: apply_mask([], t2, <<49>> <> acc, part)
  defp apply_mask([], [_v|t2], acc, :part1), do: apply_mask([], t2, <<48>> <> acc, :part1)
  defp apply_mask([], [v|t2], acc, :part2), do: apply_mask([], t2, <<v>> <> acc, :part2)
  defp apply_mask([h|t], [?X|t2], acc, :part1), do: apply_mask(t, t2, <<h>> <> acc, :part1)
  defp apply_mask([_h|t], [?X|t2], acc, :part2), do: apply_mask(t, t2, <<?X>> <> acc, :part2)
  defp apply_mask([h|t], [h2|t2], acc, :part2), do: apply_mask(t, t2, <<max(h, h2)>> <> acc, :part2)
  defp apply_mask([_h|t], [h2|t2], acc, part), do: apply_mask(t, t2, <<h2>> <> acc, part)

  defp get_mem_addr(v), do: String.replace(v, ["mem[", "]"], "") |> String.to_integer()

  defp generate_mask([], acc), do: acc
  defp generate_mask([?X|t], acc), do: generate_mask(t, Enum.map(acc, &[?1 | &1])) ++ generate_mask(t, Enum.map(acc, &[?0 | &1]))
  defp generate_mask([n|t], acc), do: generate_mask(t, Enum.map(acc, &[n | &1]))

end

I decided to create an account here just to show my hacky, bitwise-less implementation.

Couldn’t figure out the more optimal ways of fiddling with bits (especially when it seems pretty native to Elixir/Erlang), so I slugged it out with pure String manipulation. As long as the day’s solution take less than a second for both parts on my mid-range laptop, it’s fast enough for me.

defmodule AdventOfCode.Day14 do
  @moduledoc "Day 14"

  defp convert(value), do: String.graphemes(String.pad_leading(Integer.to_string(value, 2), 36, "0"))

  defp process(program, processor), do: Enum.reduce(
    Enum.reduce(
      program,
      %{mask: ""},
      fn line, mem ->
        case Regex.named_captures(~r/^(mask = (?<mask>.*)|mem\[(?<k>\d+)\] = (?<v>\d+))$/, line) do
          %{"mask" => "", "k" => k, "v" => v} ->
            Map.merge(mem, processor.(String.to_integer(k), String.to_integer(v), mem.mask))
          %{"mask" => mask, "k" => _, "v" => _} ->
            %{mem | mask: String.graphemes(mask)}
        end
      end
    ),
    0,
    fn {_, v}, acc -> if is_integer(v), do: acc + v, else: acc end
  )

  def part1(program), do: process(
    program,
    fn key, value, mask ->
      mapper = fn
        {_, "1"} -> "1"
        {_, "0"} -> "0"
        {v, "X"} -> v
      end
      Enum.map(Enum.zip(convert(value), mask), mapper)
      |> (fn masked -> [Enum.join(masked)] end).()
      |> Map.new(&({key, String.to_integer(&1, 2)}))
    end
  )

  def part2(program), do: process(
    program,
    fn key, value, mask ->
      mapper = fn
        {_, "1"} -> ["1"]
        {v, "0"} -> [v]
        {_, "X"} -> ["0", "1"]
      end
      Enum.map(Enum.zip(convert(key), mask), mapper)
      |> Enum.reduce(fn x, acc -> Enum.flat_map(acc, fn v -> Enum.map(x, &(v <> &1)) end) end)
      |> Map.new(&({String.to_integer(&1, 2), value}))
    end
  )
end