## DEV Community # Docking Data

## 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 = 11
mem = 101
mem = 0
``````

It represents

• 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
``````
• 36 characters long
• Comprised of `X`s, `0`s and `1`s
• `X`s signify a transparent mask: don't overwrite the value below
• `0`s and `1`s signify an opaque mask: overwrite the value below with either a `0` or `1`

The first instruction is:

``````mem = 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

000000000000000000000000000001001001

1001001

converted to decimal:
73
``````

### 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
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 `X`s `0`s or `1`s
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
``````

#### 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:

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
``````

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'
``````

#### 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
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

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

``````mask:
000000000000000000000000000000X1001X

changing the 100 in
mem = 100:
000000000000000000000000000001100100

to:
000000000000000000000000000000110010
``````

It works like this:

``````mask:
000000000000000000000000000000X1001X

changing the 42 in
mem = 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
``````

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! 