Wow, great explanation. Thank you so much.
I learned a lot from the discussions in this thread 
thank you everyone.
Seems the link was broken. Take two:
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?
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
You can try, ((address ||| one_mask) &&& ~~~x_mask) ||| x_mask
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.
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.
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"]
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’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: https://gist.github.com/stevensonmt/348e60393b0195369137da5237e99e59
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.
