DEV Community

Cover image for Docking Data
Robert Mion
Robert Mion

Posted on

Docking Data

#adventofcode #programming #algorithms #computerscience

Advent of Code 2020 Day 14

Try the simulator!

Simulation of Part 1's algorithm

Task: Solve for X where... 

X = the sum of all values left in memory after initialization completes
Enter fullscreen mode Exit fullscreen mode

Example input 

mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X mem[8] = 11 mem[7] = 101 mem[8] = 0
Enter fullscreen mode Exit fullscreen mode

It represents

  • A bitmask
  • A series of decimal values to assign to an address in memory

Part 1

  1. Understanding how the bitmask works
  2. Building several small algorithms
  3. Altogether now: Writing a working algorithm
  4. Building a simulator

Understanding how the bitmask works

In the example, the bitmask is:

XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
Enter fullscreen mode Exit fullscreen mode
  • 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
Enter fullscreen mode Exit fullscreen mode
  • 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
Enter fullscreen mode Exit fullscreen mode

Building several small algorithms

  1. Capturing the important parts of each instruction
  2. Converting a decimal into binary
  3. Converting a binary back to decimal
  4. Padding a number at the start to match our mask
  5. Parsing a binary number from a padded string
  6. 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:

  1. mask = then a 36-character string containing Xs 0s or 1s
  2. 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
Enter fullscreen mode Exit fullscreen mode

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'
Enter fullscreen mode Exit fullscreen mode

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:

  1. The binary number as a string
  2. The base of the binary number

We could use it like this:

parseInt('1011', 2) // 11 parseInt('1100101', 2) // 101
Enter fullscreen mode Exit fullscreen mode

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:

  1. The length of the new string
  2. 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'
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Overwriting characters in a string where appropriate

How might we perform this computation?

Start: 000000000000000000000000000000001011 Compare to: XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X End: 000000000000000000000000000001001001
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Here's how that looks in JavaScript

mask = 'XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X' value = '000000000000000000000000000000001011' value = mask.split('').map((c, i) => c == 'X' ? value[i] : c).join('') //. '000000000000000000000000000001001001'
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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!
Simulation of Part 1's algorithm

Part 2

  1. Understanding how the bitmask works this time
  2. 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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode
  • 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
Enter fullscreen mode Exit fullscreen mode

Here's a visualization of my algorithm:
Visualization of Part 2 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)