Advent of Code 2020 - Day 14

FINALLY GOT IT

defmodule Day14Part2Only do
  use Bitwise
  @moduledoc false

  @input File.read!("lib/input")

  defmodule MyParser do
    import NimbleParsec

    mask =
      ignore(string("mask = "))
      |> ascii_string([?1, ?0, ?X], 36)
      |> ignore(string("\n"))

    mem =
      ignore(string("mem["))
      |> integer(min: 1)
      |> ignore(string("] = "))
      |> integer(min: 1)
      |> ignore(string("\n"))
      |> reduce({List, :to_tuple, []})

    group =
      mask
      |> repeat(mem)
      |> reduce({List, :wrap, []})

    defparsec(:nimble_parse, repeat(group))
  end

  def nimble_parse do
    MyParser.nimble_parse(@input)
    |> elem(1)
    |> Enum.map(fn [mask | assignments] -> {mask, assignments} end)
  end

  def initialize(version \\ 1) do
    nimble_parse()
    |> build_mem_map(version)
  end

  def build_mem_map(processed_lines, version \\ 1) do
    processed_lines
    |> Enum.reduce(%{}, fn {mask, assignments}, memory ->
      assign_memory(mask, assignments, memory, version)
    end)
  end

  def assign_memory(mask, assignments, memory, 2 = version) do
    assignments
    |> Enum.map(&apply_mask(&1, mask, version))
    |> Enum.reduce(memory, fn {addresses, val}, acc ->
      update_memory({addresses, val}, acc, version)
    end)
  end

  def apply_mask({address, value}, mask, 2) do
    {address
     |> Integer.to_string(2)
     |> String.pad_leading(36, "0")
     |> String.codepoints()
     |> Enum.zip(String.codepoints(mask))
     |> Enum.reduce([0], fn {a, b}, acc ->
       case b do
         "0" -> Enum.map(acc, fn addr -> addr * 2 + String.to_integer(a) end)
         "1" -> Enum.map(acc, fn addr -> addr * 2 + 1 end)
         "X" -> fork(acc)
       end
     end), value}
  end

  def fork(acc) do
    acc
    |> Enum.flat_map(fn addr -> [addr * 2, addr * 2 + 1] end)
  end

  def update_memory({addresses, val}, memory, 2) do
    addresses
    |> Enum.reduce(memory, fn address, acc ->
      Map.put(acc, address, val)
    end)
  end

  def run2 do
    initialize(2)
    |> sum_memory()
    |> IO.puts()
  end

  def sum_memory(mem_map) do
    mem_map
    |> Map.values()
    |> Enum.sum()
  end
end

Day14Part2Only.run2()

I’ve done a half dozen approaches to the branching/flat mapping portion of applying the mask, but in the end there was something squirrelly about how I was processing the input. Once I broke down and used Nimble Parsec it just worked. UGGGGH.

I’ve narrowed down the error (at least I think so) but still don’t know why it’s happening. For the dataset:

mask = 1XX010X01110X110100000X11101X10X0X11
mem[3513] = 1787222
mem[11652] = 13761
mem[25508] = 235920
mem[49386] = 7440645
mem[51287] = 197564380
mem[9697] = 1812
mem[62638] = 5207143

I get a sum that is off by the sum of values of the 4th memory entry (mem[49386] = 7440645) after the mask is applied. Applying the mask generates a correct value (I checked using successful algorithms posted in this thread). For some reason this address is being duplicated by my algorithm. I really suspect it is in this bit:

  def flip_bits(acc, []), do: acc

  def flip_bits(acc, [x | rest]) do
    acc
    |> Enum.flat_map(fn digits ->
      [List.update_at(digits, x, fn _ -> 1 end), List.update_at(digits, x, fn _ -> 0 end)]
    end)
    |> flip_bits(rest)
  end

The initial value for acc is a list containing the list of digits of the original address in binary after applying the one mask and padding to length 36. The argument [x | rest] is a list of indices in the mask at which an “X” was identified.

I cannot understand what is special about this one memory address that it gets duplicated. If I remove that one address I get the same answer as the successful algorithm. When I use the entire dataset my solution is off by more than just the value of this one entry, so it is clearly not JUST this value that is problematic. My hope is that someone can help me identify why this entry is problematic so that I can understand the flaw in my logic that generates what currently seems to me a random error.

Full code here: flawed Advent of Code 2020 day 14 part 2 · GitHub

Thanks for taking the time to review the code. I really appreciate it. For some reason I remember struggling to pattern match on process_masks([head | []], acc) but I guess I need a case statement to handle that. The trim issue is a true brain fart. Thank you for pointing that out.

I took a look at your code, I think your approach is mostly correct, but there seems to be few issues with the code for generating the masks.

  def process_masks([part | rest], []) do
    process_masks(rest, [part <> "0", part <> "1"])
  end

  def process_masks([part | rest], masks) do
    masks =
      masks
      |> Enum.flat_map(fn digits -> [digits <> "0" <> part, digits <> "1" <> part] end)

    process_masks(rest, masks)
  end

  def process_masks([], masks) do
    masks
    |> Enum.map(&String.to_integer(&1, 2))
  end

Let’s consider generating masks for 0X0, expected 000, 010

mask: 0X0 -> parts: [0, 0]

process_masks([0,0], []) => 
   process_masks([0], [00, 01]) => 
      # Now we are at the second function, `def process_masks([part | rest], masks)`
      # 
      # here are creating new permutation by considering part=0, which is wrong 
      # because there is only one "X" in the input. 
      #    length(part) != number of x
      # 
      # after `flat_map`, masks = [0000, 0010, 0100, 0110] which is  [0, 2, 4, 6] 

Also, there is another issue, you are using trim: true,

iex(1)> String.split("0X", "X", trim: true)
["0"]

I made the same mistake originally. You are substituting the Xs in the mask, but what you need to do is substitute the Xs in the masked value.

Step 1: Apply mask to address, to produce result.
Step 2: Permute all the Xs in the result, which produces:

000000000000000000000000000000011010  (decimal 26)
000000000000000000000000000000011011  (decimal 27)
000000000000000000000000000000111010  (decimal 58)
000000000000000000000000000000111011  (decimal 59)

So you need to make sure your mask operation preserves the Xs.

no dice. I’m going to have to re-organize the masking to branch at the apply step rather than at the processing input step. Thanks for your explanation.

This problem is going to haunt me forever, but I just can’t get it to work.

You can try, ((address ||| one_mask) &&& ~~~x_mask) ||| x_mask

Like you said, you can’t use &&& to set a bit value to 1.

Basically what you want is an ability to set bit to either 0 or 1 irrespective of other value X. You can’t do that with just one operator.

For setting 0: x &&& 0
For setting 1: x ||| 1

There are many ways to express this logic with different combination of bitwise operators.

Specific to this problem, one way to do it is to set all x bits to zero explicitly at the beginning and do lll with your generated mask

This horse is dead but I’m going to continue to beat it.
For part 2 I’m trying this to generate the permutations of masks in a tuple with a one_mask that sets all the Xs to zero:

def process_mask(mask, 2) do
    one_mask = mask |> String.replace("X", "0") |> String.to_integer(2)
    parts = mask |> String.replace("1", "0") |> String.split("X", trim: true)

    {one_mask, process_masks(parts, [])}
  end

  def process_masks([part | rest], []) do
    process_masks(rest, [part <> "0", part <> "1"])
  end

  def process_masks([part | rest], masks) do
    masks =
      masks
      |> Enum.flat_map(fn digits -> [digits <> "0" <> part, digits <> "1" <> part] end)

    process_masks(rest, masks)
  end

  def process_masks([], masks) do
    masks
    |> Enum.map(&String.to_integer(&1, 2))
  end

To apply the masks and build the memory map I’m doing this:

  def build_mem_map(processed_lines, version \\ 1) do
    processed_lines
    |> Enum.reduce(%{}, fn {mask, assignments}, memory ->
      assign_memory(mask, assignments, memory, version)
    end)
  end

  def assign_memory(masks, assignments, memory, 2 = version) do
    assignments
    |> Enum.map(&apply_mask(&1, masks, version))
    |> Enum.reduce(memory, fn assign, acc -> update_memory(assign, acc, version) end)

    # |> Enum.reduce(%{}, fn map, acc -> Map.merge(acc, map) end)
  end
  def apply_mask({address, value}, {one_mask, x_masks}, 2) do
    x_masks
    |> Enum.map(fn x_mask -> (address ||| one_mask) &&& x_mask end)
    |> Enum.map(fn address -> {address, value} end)
  end

  def update_memory(assignments, memory, 2) do
    assignments
    |> Enum.reduce(memory, fn assign, acc -> update_memory(assign, acc, 1) end)
  end

I’m guessing my bitmask operations are a misunderstanding of the prompts rules again because I keep getting it wrong. From the prompt:

address: 000000000000000000000000000000101010  (decimal 42)
mask:    000000000000000000000000000000X1001X
result:  000000000000000000000000000000X1101X

which looks to me like an ||| operation for one bits. I think I’m getting it wrong by doing the next &&& operation. But it seems like a mask of 000000000000000000000000000000X1001X would become four masks of

000000000000000000000000000000100000
000000000000000000000000000000100001
000000000000000000000000000000000000
000000000000000000000000000000000001

which I think is the problem. Applying an &&& to the all zero mask will be zero, which is incorrect. Inverting the order and applying the x_mask first and then doing an ||| for the one_mask is also wrong though. What’s the concept I’m missing here?

Seems the link was broken. Take two:

https://github.com/adamu/AdventOfCode2020/blob/main/day14/README