Day 5: Cafeteria

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • Jayjader
    link
    fedilink
    English
    arrow-up
    3
    ·
    3 days ago

    (Browser-based) Javascript

    The good ol’ range merge is back! I’ve done the past few years in Rust, which has first-class “support” for inclusive ranges, so I was dreading having to re-implement things. Turns out when you can ignore lifetimes things get simpler.

    Code
    function part1(inputText) {
      const [freshRangeDefs, availableIds] = inputText.trim().split('\n\n');
      const parsedIds = new Set(availableIds.trim().split('\n').map(strId => Number.parseInt(strId, 10)));
      const parsedRanges = freshRangeDefs.trim().split('\n').map(rangeDef => rangeDef.split('-').map(strBound => Number.parseInt(strBound, 10)));
    
      for (const id of parsedIds) {
        let fresh = false;
        for (const [lowerBound, upperBound] of parsedRanges) {
          if (lowerBound <= id && id <= upperBound) {
            fresh = true;
            break;
          }
        }
        if (!fresh) {
          parsedIds.delete(id)
        }
      }
      return parsedIds.size;
    }
    
    {
      const start = performance.now();
      const result = part1(document.body.textContent);
      const end = performance.now();
      console.info({
        day: 5,
        part: 1,
        time: end - start,
        result
      });
    }
    
    function part2(inputText) {
      const [freshRangeDefs] = inputText.trim().split('\n\n');
      const parsedRanges = freshRangeDefs.trim().split('\n').map(rangeDef => rangeDef.split('-').map(strBound => Number.parseInt(strBound, 10)));
      parsedRanges.sort(([lowerA, upperA], [lowerB, upperB]) => lowerA - lowerB);
      const merged = [parsedRanges[0]];
      for (const [parsedLower, parsedUpper] of parsedRanges) {
        let inserted = false;
        for (let mIndex = 0; mIndex < merged.length; mIndex++) {
          const [mLower, mUpper] = merged[mIndex];
          if (mUpper < parsedLower) {
            // parsed is completely "above" merged
            continue
          } else if (parsedUpper < mLower) {
            // parsed is completely "below" merged
            merged.splice(mIndex, 0, [parsedLower, parsedUpper]);
            inserted = true;
            break;
          } else {
            // parsed and merged intersect somehow/somewhere)
            merged[mIndex][0] = Math.min(parsedLower, mLower)
            merged[mIndex][1] = Math.max(parsedUpper, mUpper)
            inserted = true;
            break;
          }
        }
        if (!inserted) {
          // parsed is completely "above" ALL already-merged ranges
          merged.push([parsedLower, parsedUpper]);
        }
      }
      return merged.reduce((accu, [lower, upper]) => accu + upper - lower + 1, 0)
    }
    {
      const exampleText = `3-5
    10-14
    16-20
    12-18
    
    1
    5
    8
    11
    17
    32
    `
      const start = performance.now();
      //   const result = part2(exampleText);
      const result = part2(document.body.textContent);
      const end = performance.now();
      console.info({
        day: 5,
        part: 2,
        time: end - start,
        result
      });
    }