Advent of Code 2020 Day 14
Try the simulator!
Task: Solve for X where...
X = the sum of all values left in memory after initialization completes
Example input
mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
mem[8] = 11
mem[7] = 101
mem[8] = 0
It represents
- A bitmask
- A series of decimal values to assign to an address in memory
Part 1
- Understanding how the bitmask works
- Building several small algorithms
- Altogether now: Writing a working algorithm
- Building a simulator
Understanding how the bitmask works
In the example, the bitmask is:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
- 36 characters long
- Comprised of
Xs,0s and1s -
Xs signify a transparent mask: don't overwrite the value below -
0s and1s signify an opaque mask: overwrite the value below with either a0or1
The first instruction is:
mem[8] = 11
- Assign the integer 11 to address 8 in memory
As the example demonstrates:
mask:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
decimal 11 as bits:
1011
decimal 11 as bits, padded with 0s to be 36 characters long:
000000000000000000000000000000001011
areas of overlap:
1 0
decimal 11 as bits, masked:
000000000000000000000000000001001001
new bits without padding:
1001001
converted to decimal:
73
Building several small algorithms
- Capturing the important parts of each instruction
- Converting a decimal into binary
- Converting a binary back to decimal
- Padding a number at the start to match our mask
- Parsing a binary number from a padded string
- Overwriting characters in a string where appropriate
Capturing the important parts of each instruction
Among the stream of input are one of two line templates:
-
mask =then a 36-character string containingXs0s or1s -
memthen a bracket-enclosed integer, then=, then another integer
This regular expression matches either template and captures one or both of the important elements
/mask = ([01X]+)|mem\[(\d+)\] = (\d+)/g
Converting a decimal into binary
How might we turn 11 into 1011, or 101 into 1100101?
In JavaScript, we can leverage the toString() method built-in to the Number object prototype.
Invoking toString() on a number, and passing a number as argument, will attempt to return the calling number in the provided base, or radix.
Therefore, calling toString() with argument 2 will convert our decimal to binary, like this:
(11).toString(2) // '1011'
(101).toString(2) // '1100101'
Converting a binary back to decimal
How might we do the reverse: 1011 into 11?
In JavaScript, we can use the parseInt() Number method, passing two arguments:
- The binary number as a string
- The base of the binary number
We could use it like this:
parseInt('1011', 2) // 11
parseInt('1100101', 2) // 101
Padding a number at the start to match our mask
How might we get '000000000000000000000000000000001011' from 1011?
In JavaScript, we can use the padStart() string method, passing two arguments:
- The length of the new string
- The character used to fill in each new space
Therefore, calling padStart() on our string-ified binary number, with arguments 36 and 0, we can match our mask string length:
'1011'.padStart(36,0) // '000000000000000000000000000000001011'
'1100101'.padStart(36,0) // '000000000000000000000000000001100101'
Parsing a binary number from a padded string
How might we get 11 from '000000000000000000000000000000001011'?
Thankfully, we can use parseInt() the same way as earlier, like this:
parseInt('000000000000000000000000000000001011', 2) // 11
parseInt('000000000000000000000000000001100101', 2) // 101
Overwriting characters in a string where appropriate
How might we perform this computation?
Start:
000000000000000000000000000000001011
Compare to:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
End:
000000000000000000000000000001001001
Overwriting characters in a string where appropriate
Split the mask into an array of characters
For each character in the mask
If the character is an 'X'
Change it to the character at the same location in the padded, binary-represented decimal
Else - the character is a '0' or '1'
Keep the character
Join each character together to form a string again
Here's how that looks in JavaScript
mask = 'XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X'
value = '000000000000000000000000000000001011'
value = mask.split('').map((c, i) => c == 'X' ? value[i] : c).join('')
//. '000000000000000000000000000001001001'
Altogether now: Writing a working algorithm
Store the input as one long string of text
Find all matches within the string from the regular expression
Create a new object, mem
Create an empty string, mask
For each match
If there is a match for the first of the three capture groups
Re-assign mask the string from the first capture group
Else
Create or re-assign to the key in mem equivalent to the number from the second capture group the result of processing the number from the second capture group as follows:
Convert the captured string to a number
Convert it to a string from the number in base 2
Extend the string from the start to become 36 characters long, filling in any spaces with 0s
Create a copy of the string currently assigned to mask, such that:
For each character an array containing the characters from the current string assigned to mask:
If the character is an X
Change it to the character in the same location from the padded binary version of the number
Else - if the character is a 1 or 0
Keep that character
Join all characters to form a string again
Parse the string as a number in base 2 to convert it to a decimal
Extract an array containing all values from mem
For each value in that array
Accumulate a sum - starting at 0
Return the sum
Building a simulator
- My intent with this simulator was to display each part of the conversion process: from original to final decimal
- And to display the accumulating sum of all decimals
- I built it to allow for the data entry of a single decimal and mask, or for the processing of some unique puzzle input
Part 2
- Understanding how the bitmask works this time
- Building the floating bit algorithm
Understanding how the bitmask works this time
- In Part 1, an
Xsignified transparency: keep the character from the padded, binary-converted decimal - Now, an
Xsignifies one additional branch of possible values for the address in memory to store a newly unchanged decimal
Instead of working like this:
mask:
000000000000000000000000000000X1001X
changing the 100 in
mem[42] = 100:
000000000000000000000000000001100100
to:
000000000000000000000000000000110010
It works like this:
mask:
000000000000000000000000000000X1001X
changing the 42 in
mem[42] = 100:
000000000000000000000000000001100100
to storing 100 to the following addresses:
000000000000000000000000000000011010
000000000000000000000000000000011011
000000000000000000000000000000111010
000000000000000000000000000000111011
The instruction I see is:
Count the number of X's
Multiply 2 by the number of X's in the mask to determine the number of permutations
For each permutation
Overwrite each character whose location corresponds to an 'X' in the mask with a 0 or 1
The challenge is:
- What pattern exists to generate the full range of permutations of 0s and 1s?
I noticed this pattern:
For 2 X's, the values are:
0..0
0..1
1..0
1..1
For 3 X's, the values are:
0..0..0
0..0..1
0..1..0
0..1..1
1..0..0
1..0..1
1..1..0
1..1..1
- Those are the binary numbers 0 to (2 * N - 1) - where N = number of Xs - padded with 0s to the same number of characters as the largest number, 7
Building the floating bit algorithm
Split the mask into an array of characters
Accumulate an array of indices - starting as empty
If the value is an 'X', add its index to the accumulating list
Multiply 2 by N number of X's and store in permutations
For i from 0 to permutations
Convert the number to binary
Pad it from the start with 0s to the length equivalent to the number of characters in the binary-converted number one less than permutations
Split that number into an array of numbers
Create a copy of the string currently assigned to mask, such that:
For each character in an array containing the characters from the current string assigned to mask:
If the character is an X
Change it to the number in the array of numbers generated from i who's index matches that of the index of this character in the accumulated list of indices of only X characters
Join all characters to form a string again
Parse the string as a number in base 2 to convert it to a decimal
Store in this new decimal address the value to the right side of the = on the same line from the input string
Here's a visualization of my algorithm:
Much to my delightful surprise, that algorithm generated a correct answer for my puzzle input!
I'm not interested in updating the simulator to show each of these permutations, given how much time I've already spent on this puzzle.
- Both parts completed
- Simulator created
- GIF created
Time to move on!
Top comments (0)