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!

Image of Datadog

The Future of AI, LLMs, and Observability on Google Cloud

Datadog sat down with Google’s Director of AI to discuss the current and future states of AI, ML, and LLMs on Google Cloud. Discover 7 key insights for technical leaders, covering everything from upskilling teams to observability best practices

Learn More

Top comments (0)

👋 Kindness is contagious

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

Okay