Rucksack Reorganization

Advent of Code 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:

'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
  }
  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!