Robert Mion

Posted on

# Rucksack Reorganization

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

``````'A'.charCodeAt()
``````

Going from number to string in JavaScript:

``````String.fromCharCode(65)
``````

Creating an array with slots for one alphabet casing:

``````new Array(26)
``````

Leveraging each slot's index to populate items with letters:

``````new Array(26)
.fill(null)
.map(
// Uppercase
(,i) => String.fromCharCode(i + 65)
)
``````

Generating both alphabets and merging into a single array:

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

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

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

``````let priorities = ['a','b','c',]
.reduce((types, sack) => {
// Split
// Walk
return types += priorities.indexOf(char) + 1
}, 0)
``````

### My full algorithm in JavaScript

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

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

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

``````let total = 0

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

### My full algorithm in JavaScript

``````() => {
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
}
}
``````

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