Docking Data
Tags: adventofcode, programming, algorithms, computerscience
Published: 2022-03-28 20:18:30

## [Advent of Code 2020 Day 14](https://adventofcode.com/2020/day/14)

## [Try the simulator!](https://aocdockingdata.rmion.repl.co/)
![Simulation of Part 1's algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/108uwj2bpsjqnx5kasxf.gif)

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

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

#### 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
```js
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!](https://aocdockingdata.rmion.repl.co/)
![Simulation of Part 1's algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/108uwj2bpsjqnx5kasxf.gif)

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

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:
![Visualization of Part 2 algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4l1t0ycmq7y4pw50f4bu.gif)

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!