DEV Community

Cover image for Rucksack Reorganization
Robert Mion
Robert Mion

Posted on

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
Enter fullscreen mode Exit fullscreen mode

Cut in half gets:

ttgJtRGJ
QctTZtZT
Enter fullscreen mode Exit fullscreen mode

Starting with the first half's first character:

*
ttgJtRGJ

Got any 't's?
QctTZtZT
  *
Enter fullscreen mode Exit fullscreen mode

Same-type identified!

Another example:

vJrwpWtwJgWrhcsFMMfFFhFp
Enter fullscreen mode Exit fullscreen mode

Cut in half:

vJrwpWtwJgWr
hcsFMMfFFhFp
Enter fullscreen mode Exit fullscreen mode

Starting with the first half's first character:

*
vJrwpWtwJgWr

Got any 'v's?
hcsFMMfFFhFp
Enter fullscreen mode Exit fullscreen mode

Moving to the next character:

 *
vJrwpWtwJgWr

Got any 'J's?
hcsFMMfFFhFp
Enter fullscreen mode Exit fullscreen mode

Skipping ahead to the first same character:

    *
vJrwpWtwJgWr

Got any 'p's?
hcsFMMfFFhFp
           *
Enter fullscreen mode Exit fullscreen mode

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()
Enter fullscreen mode Exit fullscreen mode

Going from number to string in JavaScript:

String.fromCharCode(65)
Enter fullscreen mode Exit fullscreen mode

Creating an array with slots for one alphabet casing:

new Array(26)
Enter fullscreen mode Exit fullscreen mode

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

new Array(26)
  .fill(null)
  .map(
    // Uppercase
    (,i) => String.fromCharCode(i + 65)
  )
Enter fullscreen mode Exit fullscreen mode

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)
      )
  )
Enter fullscreen mode Exit fullscreen mode

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)
]
Enter fullscreen mode Exit fullscreen mode

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++
}
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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) { }
Enter fullscreen mode Exit fullscreen mode

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++
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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!

Top comments (0)