Day 2: Gift Shop

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

you are viewing a single comment's thread
view the rest of the comments
[โ€“] 2 points 11 months ago

(Browser-based) Javascript

This year I'm tired of dealing with reading from files and setting up IDEs, so I'm attempting to solve each day directly in my web browser's console: after opening my problem input in a new tab I can do mySolutionFunction(document.body.textContent) in that tab's console. Thankfully the browser I use (ff) has a mode that lets me write several lines and then run them, otherwise this would not be simpler. Unfortunately, this means I lost my code for day1 when I closed the tab a bit too quickly.

I didn't want to use regex for today; you need backreferences and those are impossible to optimize if they blow up (computationally speaking). I'm not so sure my solution for part 2 actually does run in more linear time than a regex with a single backreference does...

function part1(input) {
  let sumOfValidIds = 0;
  for (const rangeDef of input.split(',')) {
    const [start, stop] = rangeDef.split('-').map(s => Number.parseInt(s, 10));
    const rangeLength = stop - start + 1;
    for (let id = start; id <= stop; id++) {
      const idLength = id.toString().length;
      if (idLength % 2 === 1) {
        continue
      }
      const halfLength = idLength / 2;
      const topHalf = Math.floor(id / Math.pow(10, halfLength));
      const bottomHalf = id - topHalf * Math.pow(10, halfLength);
      if (topHalf === bottomHalf) {
        sumOfValidIds += id;
      }
    }
  }
  return sumOfValidIds;
}
part1(document.body.textContent);

function extendsPattern(containerString, pattern) {
  let container = containerString;
  while (container.length > pattern.length) {
    if (!container.startsWith(pattern)) {
      return false;
    }
    container = container.slice(pattern.length)
  }
  return pattern.startsWith(container);
}
function findContainedPatterns(containerString) {
  const patterns = [];
  for (let i = 0; i < containerString.length; i++) {
    const upTillNow = containerString.substring(0, i+1);
    for (let j = 0; j < patterns.length; j++) {
      if (!extendsPattern(upTillNow, patterns[j])) {
        patterns.splice(j, 1);
        j--;
      }
    }
    patterns.push(upTillNow);
  }
  return patterns;
}
function part2(input) {
  let sumOfValidIds = 0;
  for (const rangeDef of input.split(',')) {
    const [start, stop] = rangeDef.split('-').map(s => Number.parseInt(s, 10));
    const rangeLength = stop - start + 1;
    for (let id = start; id <
      const idString = id.toString();
      const patterns = findContainedPatterns(idString);
      if (patterns.length > 1) {
        const shortestPatternCandidate = patterns[0];
        if (idString.length % shortestPatternCandidate.length === 0) {
          sumOfValidIds += id;
        }
      }
    }
  }
  return sumOfValidIds;
}
//part2(`11-22,95-115,998-1012,1188511880-1188511890,222220-222224,1698522-1698528,446443-446449,38593856-38593862,565653-565659,824824821-824824827,2121212118-2121212124`)
part2(document.body.textContent);
  • source