DEV Community

Cover image for Rucksack Reorganization
Robert Mion
Robert Mion

Posted on

4 2

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!

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay