Rucksack Reorganization
Tags: adventofcode, algorithms, javascript, programming
Published: 2022-12-03 18:46:54

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

## Part 1
1. Divide (in half) and conquer
2. Setting my priorities
3. Split, Walk and Sum
4. My full algorithm in JavaScript

### Divide (in half) and conquer
- Slice each string in half
- Use the first half as a control
- Check only as many characters as needed
- Until the second half contains the current character

For example:
```
ttgJtRGJQctTZtZT
```

Cut in half gets:
```
ttgJtRGJ
QctTZtZT
```

Starting with the first half's first character:
```
*
ttgJtRGJ

Got any 't's?
QctTZtZT
  *
```

Same-type identified!

Another example:
```
vJrwpWtwJgWrhcsFMMfFFhFp
```

Cut in half:
```
vJrwpWtwJgWr
hcsFMMfFFhFp
```

Starting with the first half's first character:
```
*
vJrwpWtwJgWr

Got any 'v's?
hcsFMMfFFhFp
```

Moving to the next character:
```
 *
vJrwpWtwJgWr

Got any 'J's?
hcsFMMfFFhFp
```

Skipping ahead to the first same character:
```
    *
vJrwpWtwJgWr

Got any 'p's?
hcsFMMfFFhFp
           *
```

Same-type identified!

### Setting my priorities
- `a - z` are `1 - 26`
- `A - Z` are `27 - 52`

Sure, I could manually create, say:
- A dictionary mapping letter to number
- Array with each letter occupying the appropriate index

But I want to do this programmatically!

Thankfully, I can use character codes!

Some examples:
- `A` is 65
- `a` is 97

Going from string to number in JavaScript:
```js
'A'.charCodeAt()
```

Going from number to string in JavaScript:
```js
String.fromCharCode(65)
```

Creating an array with slots for one alphabet casing:
```js
new Array(26)
```

Leveraging each slot's index to populate items with letters:
```js
new Array(26)
  .fill(null)
  .map(
    // Uppercase
    (,i) => String.fromCharCode(i + 65)
  )
```

Generating both alphabets and merging into a single array:
```js
new Array(26)
  .fill(null)
  .map(
    (,i) => String.fromCharCode(i + 65 + 32)
  )
  .concat(
    new Array(26)
      .fill(null)
      .map(
        (,i) => String.fromCharCode(i + 65)
      )
  )
```

My array is 0-based. I'll need to account for that by adding one in my main algorithm.

### Split, Walk and Sum
#### Split
I need to extract two equal length substrings from each string:
```js
let [s1, s2] = [
  sack.slice(0, sack.length / 2), 
  sack.slice(sack.length / 2)
]
```

#### Walk
I need to identify the single duplicated letter, checking only as many letters as needed:
```js
let i = 0
let char = null
while (char == null) {
  char = s2.includes(s1[i]) ? s1[i] : null
  i++
}
```

#### Sum
I need to accumulate a total score derived from the priority amounts of each identified letter:
```js
let priorities = ['a','b','c',]
.reduce((types, sack) => {
  // Split
  // Walk
  return types += priorities.indexOf(char) + 1
}, 0)
```

### My full algorithm in JavaScript
```js
const priorities = new Array(26)
  .fill(null)
  .map(
    (,i) => String.fromCharCode(i + 65 + 32)
  )
  .concat(
    new Array(26)
      .fill(null)
      .map(
        (,i) => String.fromCharCode(i + 65)
      )
  )
return input
  .split('\n')
  .reduce((types, sack) => {
    let [s1, s2] = [
      sack.slice(0, sack.length / 2),
      sack.slice(sack.length / 2)
    ]
    let i = 0
    let char = null
    while (char == null) {
      char = s2.includes(s1[i]) ? s1[i] : null
      i++
    }
    return types += priorities.indexOf(char) + 1
  }, 0)
```

## Part 2
1. `reduce()` is out? Oh `for` Pete's sake!
2. My full algorithm in JavaScript

### `reduce()` is out? Oh `for` Pete's sake!
I need to review every three lines in a batch:
```js
for (let s = 0; s < sacks.length; s += 3) { }
```

I need to walk the first of three lines and check each of the other lines for a matching character:
```js
let i = 0
let char = null
while (char == null) {
  char = sacks[s + 1].includes(sacks[s][i]) 
      && sacks[s + 2].includes(sacks[s][i])
       ? sacks[s][i] : null
  i++
}
```

I need to track a total and increment it with each group's priority amount:
```js
let total = 0

// Inside the loop
total += priorities.indexOf(char) + 1
```

### My full algorithm in JavaScript
```js
() => {
  let total = 0
  let sacks = input.split('\n')
  for (let s = 0; s < sacks.length; s += 3) {
    let i = 0
    let char = null
    while (char == null) {
      char = sacks[s + 1].includes(sacks[s][i]) 
          && sacks[s + 2].includes(sacks[s][i])
           ? sacks[s][i] : null
      i++
    }
    total += priorities.indexOf(char) + 1
  }
  return total
}
```

## I did it!!
- I solved both parts!
- I scratched my head once during Part 1 because I was unknowingly chopping off the first letter of the second sack!
- I reused most of my code from Part 1 in Part 2!

Lots of fun with strings and arrays today!