2022 - Day 3 - Rucksack Reorganization

Day three of our coding advent brought us to a sorting dilemma with the elves’ rucksacks. Not all items were packed correctly, and it was up to us to find the inconsistencies and reorganize. In this post, we will break down the JavaScript functions that helped us sift through the items efficiently.

Table of Contents

Challenge Overview

Each elf’s rucksack is divided into two compartments, and due to a packing error, exactly one item type was placed in both compartments. Our task was to identify these items and calculate their priority sum for reorganization. Furthermore, we needed to find a common item type in each group of three rucksacks, which represented their badges, and sum their priorities as well.

Our Solution

Using JavaScript, we created functions to parse through the rucksack contents and identify the misplaced items. Here’s how we tackled it:

1. Read the input file and split it into individual rucksack descriptions.
2. Execute partOne function to find duplicated items within each rucksack.
3. Execute partTwo function to find the common badge item for each group of three elves.
4. Log the sum of priorities for both parts and the execution time for the script.

The JavaScript code is as follows:

const fs = require("fs");
const FILE_PATH = "./input.txt";
const input = fs.readFileSync(FILE_PATH, "utf8").trim();

const start = Date.now();
const rucksacks = input.split("\n");
const individualSums = partOne(rucksacks);
const groupSums = partTwo(rucksacks);
const end = Date.now();

console.log(`🎄 Part 1: ${individualSums.toLocaleString()}`);
console.log(`🎄 Part 2: ${groupSums.toLocaleString()}`);
console.log(`⏰ The script took ${end - start}ms to run.`);

The implementation details for partOne and partTwo can be read in the full code.

Part One: Identifying Individual Errors

In partOne, we approached the problem by splitting each rucksack’s items into two halves, creating sets for each half, and then identifying the duplicate items. Each duplicate’s priority is calculated based on its ASCII value, with different ranges for uppercase and lowercase letters.

function partOne(rucksacks) {
  const duplicates = [];

  rucksacks.forEach(rucksack => {
    // Split the string into two halves
    const left = rucksack.slice(0, rucksack.length / 2);
    const right = rucksack.slice(rucksack.length / 2);

    // For each character in the left half, add it to a set
    const leftSet = new Set();
    for (let i = 0; i < left.length; i++) {
      leftSet.add(left[i]);
    }

    // For each character in the right half, add it to a set
    const rightSet = new Set();
    for (let i = 0; i < right.length; i++) {
      rightSet.add(right[i]);
    }

    // For each character in the left set, check if it is in the right set
    leftSet.forEach(char => {
      if (rightSet.has(char)) {
        duplicates.push(char);
      }
    });
  });

  // Return the sum of the priorities of the duplicates
  return duplicates.reduce((sum, character) => {
    if (character >= "A" && character <= "Z") {
      return sum + character.charCodeAt(0) - 38;
    } else {
      return sum + character.charCodeAt(0) - 96;
    }
  }, 0);
}

Part Two: Group Consistency Check

partTwo required us to work with groups of three rucksacks. We looped through every three rucksacks, identified the common item (the badge), and calculated its priority similarly to part one.

function partTwo(rucksacks) {
  // Separate the rucksacks into groups of 3
  const groups = [];

  for (let i = 0; i < rucksacks.length; i += 3) {
    groups.push(rucksacks.slice(i, i + 3));
  }

  // For each group, find the common characters
  const commonCharacters = groups.map(group => {
    const elf0 = group[0];
    const elf1 = group[1];
    const elf2 = group[2];

    for (let i = 0; i < elf0.length; i++) {
      if (elf1.includes(elf0[i]) && elf2.includes(elf0[i])) {
        return elf0[i];
      }
    }
  });

  return commonCharacters.reduce((sum, character) => {
    if (character >= "A" && character <= "Z") {
      return sum + character.charCodeAt(0) - 38;
    } else {
      return sum + character.charCodeAt(0) - 96;
    }
  }, 0);
}

Complexity Analysis

The functions run with a time complexity of O(n × m) where n is the number of rucksacks and m is the number of items in each rucksack for partOne, and O(g × k) for partTwo, where g is the number of groups and k is the number of items per group. The space complexity is O(u + v) where u is the number of unique items in partOne and v is the number of groups in partTwo.

Conclusion

Our JavaScript functions proved to be an effective solution to the organizational challenge posed by the elves’ rucksack debacle. Not only did we reorganize the items, but we also streamlined the process for future packing endeavors.

Stay tuned as we continue to solve the Advent of Code puzzles with the power of programming!