Advent of Code 2015 - Day 20 - Infinite Elves and Infinite Houses

On the twentieth day of Advent of Code 2015, we are asked to help work out how many presents the Elves will deliver to specific houses.

Part 1

To keep the Elves busy, Santa has them deliver some presents by hand, door-to-door. He sends them down a street with infinite houses numbered sequentially: 1, 2, 3, 4, 5, and so on. Each Elf is assigned a number, too, and delivers presents to houses based on that number. There are infinitely many Elves, numbered starting with 1. Each Elf delivers presents equal to ten times his or her number at each house.

For part one, we are asked to determine what is the lowest house number that will receive at least 29,000,000 presents. To tackle this problem, we could opt for a brute-force approach, storing each house in memory and iterating through each Elf’s deliveries. However, upon closer inspection, we see that each house is visited by the Elves that share its factors. As such, we can devise a Factors function which optimally determines which Elves visited a given house number.

const elvesWhoVisited = (houseNo: number): number[] => {
  const elves = houseNo > 1 ? [1, houseNo] : [1];

  for (let elf = 2; elf <= Math.sqrt(houseNo); elf++) {
    if (houseNo % elf === 0) {
      elves.push(elf);
      if (elf ** 2 !== houseNo) elves.push(houseNo / elf);
    }
  }

  return elves;
};

With the ability to determine which Elves visited a given house, we can increment through each house number (starting at 1) until we reach a house where the presents the Elves delivered (10 times their own number) is greater than the supplied input. We can then return this house number to answer part one 🌟.

const part1 = (input: string): number => {
  const numOfPresents = toInt(input);
  const presentsPerHouse = 10;

  let houseNo = 1;
  while (true) {
    const elves = elvesWhoVisited(houseNo);
    if (elves.reduce(sum) * presentsPerHouse >= numOfPresents) break;
    houseNo += 1;
  }

  return houseNo;
};

Part 2

For part two, there is an imposed limit on the number of houses a given Elf can deliver presents to, which is now 50. Along with this restriction, the total presents per house an Elf delivers is now 11. We are now asked to determine what the new lowest house number is that will receive at least 29,000,000 presents.

To achieve this, we can borrow a lot of the logic implemented for part one, except now we must filter out only the Elves that have not exceeded the 50-house quota. In doing this, we can return the desired answer 🌟.

const part2 = (input: string): number => {
  const numOfPresents = toInt(input);
  const presentsPerHouse = 11;
  const maxDeliveriesPerElf = 50;

  let houseNo = 1;
  while (true) {
    const elves = elvesWhoVisited(houseNo).filter(
      elf => houseNo / elf <= maxDeliveriesPerElf
    );
    if (elves.reduce(sum) * presentsPerHouse >= numOfPresents) break;
    houseNo += 1;
  }

  return houseNo;
};