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.

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

The changes are replacements and replacing a bit means you need multiple steps. Consider this:

value = 0b001
mask_str = "X10"
mask = 0b110

How would you make sure the 0 in bit 3 stays a 0, while at the same time the 0 in bit 2 will be converted into a 1?

One way to do this is to unset whatever shall be replaced (current &&& unset_mask) and then set the bit to the value it should be replaced with using a bitwise OR (unset ||| replacement)

So

import Bitwise
value = 0b10101010
replacement_str = "XXXXX110"
replacements = 0b00000110 
# From the replacement alone it's not possible to know 
# that all of the first 3 bits are to be replaced.
unset_mask = 0b11111000 # Only operate on first 3 bits

unset = value &&& unset_mask
# 0b10101000
# every bit 1 in the unset_mask is retained from the value
# every bit 0 in the unset_mask becomes 0
new = value ||| replacements
# 0b10101110
# Given all not to be changed bits are 0 in the replacement
# only the first 3 bits are changed if necessary

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