Advent of Code is a yearly puzzle that runs through December where each day a new puzzle is released that gets progressively harder. The goal is to take the text input and create an algorithm in any language to solve the puzzle.

For this year I decided to make my solutions into interactive widgets on the web.

Spoilers

WARNING - Below is a spoiler. If you want to figure it out yourself have a look at the puzzle on Advent of Code and come back after you have solved it.

The Puzzle

Puzzle 2’s concept is very easy: it is to add a few numbers together. Simple right!

Input

The input this time is a single comma separated line, where each item is a range of numbers that should be checked. For example, 10-12,15-16 means that you need to check 10, 11 and 12 for the first group; and 15 and 16 for the second group.

The only constraint to which of these number is added is that the first half of the number is the same as the second half. In the example above only 11 meets this criteria. That means the answer to the input 10-12 is 11.

Solution

Parsing the input

Parsing the input is pretty simple. It can be split first by the comma to find the number ranges, and then by the hyphen to find the start and end of each range.

const ranges = input.split(",").map(range => {
    const [start, end] = range.split("-").map(Number);
    return { start, end };
});

Processing the ranges

The first thing that pops into mind looking at this puzzle is that only number of even length can possibly meet the criteria. This will short circuit any known invalid inputs.

function isEvenLength(num) {
    return num.toString().length % 2 === 0;
}

Next in order to get each half of the number we can convert it to a string and split it in half. Then we can compare the two halves to see if they are the same*.*

function halvesAreEqual(num) {
    const str = num.toString();
    const mid = str.length / 2;
    const firstHalf = str.slice(0, mid);
    const secondHalf = str.slice(mid);
    return firstHalf === secondHalf;
}

Lastly these two functions need to be combined in a loop to check each number, and if they meet the criteria they can be added to a total.

function calculateTotal(ranges) {
    let total = 0;
    for (const { start, end } of ranges) {
        for (let i = start; i <= end; i++) {
            if (isEvenLength(i) && halvesAreEqual(i)) {
                total += i;
            }
        }
    }
    return total;
}

Showing the Result

This solution was used to make the interactive widget below. You can change the inputs to anything you like (although be warned, large number ranges may take a very long time to compute).

Run

Part 2

For the second part of the puzzle, it turns out that repeats of any length are allowed. The good news is again that this is so similar to part 1 that only a few more lines are required. The first is that the short circuit for even length numbers must now be removed as odd lengths can always be repeats of odd length substrings, eg. 123123123 has 123 repeated even though it is 9 characters long.

I think the easiest approach to this is to get all divisors of the number length, get each of those as substrings, and check if they are all the same. To get the divisors of a number we can loop from 1 to n/2 and check if each number wholly divides into n. If it does, it is a divisor.

function getDivisors(n) {
    // 1 is always a divisor of an integer
    const divisors = [1];

    // Only look for divisors up to half the number size
    for (let i = 2; i <= Math.floor(n / 2); i++) {
        if (n % i === 0) {
            divisors.push(i);
        }
    }
    return divisors;
}

With the divisors in hand we can now check each one to see if the substrings are all the same. For this puzzle single digit numbers are ignored as they cannot have repeated substrings.

function hasRepeatedSubstring(num) {
    const str = num.toString();
    const length = str.length;

    // For this puzzle, ignore single digits
    if (length === 1) return false;

    const divisors = getDivisors(length);

    // Only one divisor needs to match for it to be valid
    return divisors.some(divisor => {
        const substring = str.slice(0, divisor);
        for (let i = divisor; i < length; i += divisor) {
            // Check each substring against the first, and
            // if it doesn't match this divisor fails
            if (str.slice(i, i + divisor) !== substring) {
                return false;
            }
        }
        return true;
    });
}

Run

---

Want to read more? Check out more posts below!

---