Docking Data

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 and 1s
Xs signify a transparent mask: don't overwrite the value below
0s and 1s signify an opaque mask: overwrite the value below with either a 0 or 1

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 containing Xs 0s or 1s
mem then 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

Try the simulator!

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 X signified transparency: keep the character from the padded, binary-converted decimal
Now, an X signifies 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!

Blog

Robert Mion

Advent of Code 2020 Day 14

Try the simulator!

Task: Solve for X where...

Example input

Part 1

Understanding how the bitmask works

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

Overwriting characters in a string where appropriate

Altogether now: Writing a working algorithm

Building a simulator

Part 2

Understanding how the bitmask works this time

Building the floating bit algorithm

Join Our Newsletter. No Spam, Only the good stuff.

Related