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

This time the puzzle is to identify which of the given numbers is within any of the given ranges. This means there are effectively two inputs:

1. The number ranges (inclusively)

0-2
5-7

2. The numbers to match to the ranges

1
2
8

In this example the set of valid numbers is 0,1,2,5,6,7 which means that we can quickly check each number in the second input against this list giving:

1 - Valid
2 - Valid
8 - Invalid

Solution

Parsing the input

I mentioned before that there are effectively two inputs, but in reality they are supplied as a single input that is separated by two line breaks. The easiest option in my mind is to first split it to the two separate parts, and then parse those parts individually.

For this puzzle I am going to use functional programming principals to change things up a little. Here is an example of the first step in the parsing using some composable functions, and the pipe utility to combine them.

From here on I will hide away some of the extra functions that I create in a separate file to stay focused, but you can see them by moving to the utility file if you are interested in them.

---

The rest of the parsing is similar, but it will need to occur over an array rather than a single element. To do this a utility called Map can be used to run a function over every item in an array.

This is combined with Pipe to take a single string, and process it into an array of ranges.

Using function composition here means that each step is done as a standalone block that can be combined together to create the complex functionality we need.

Processing

The simple part is to now iterate all ranges and all values to see which ones fit. Continuing the use of the functional style, there are a few small chunks of logic I can make:

1. The check for if a value is between a range.
2. Iterating the ranges
3. Mapping the values to a true of false value based on that check.

const inRange = (start, end) =>
  value => value >= start && value <= end;
const inAnyRange = ranges =>
  value => ranges.some(([start, end]) => inRange(start, end)(value));
const mapValueInRange = map(inAnyRange(ranges));

const results = mapValueInRange(values);
console.log(results);
/*
 * Output:
 * [ true, true, false ]
 */

Showing the results

This solution was used to make the interactive widget below. You can change the inputs to anything you like.

Run

Part 2

For part 2 there is no longer a need to count the matches, but rather the total number of unique ids within the ranges.

This one is a little harder as there is a lot of overlap between the ranges which means we need to find a way to only count unique values.

The ranges can also be so large that it is not realistic to expand them all out into individual values.

Solution

My idea for this is to only count the first instance a range is used to cover a number, and to alter the current range to remove any already counted numbers. This can mean that a single provided range will need to be split multiple times if it overlaps with multiple other ranges.

The scenarios that will need to be catered for are:

1. The ranges are completely separate
2. The first range completely covers the second range
3. The first range partially overlaps the start of the second range
4. The first range partially overlaps the end of the second range
5. The first range is completely inside the second range

Parts 1 and 2

Parts 1 and 2 are easy to handle, as they just mean we can keep the range as is or discard it completely.

Note: you can hover over the examples to get a split view

No Overlap - Both ranges are kept as there is no overlapping number

Complete Overlap - The second range is completely covered by the first and is discarded

Parts 3 and 4

Parts 3 and 4 are also reasonably simple, as only one part of the second range needs to be adjusted.

End Overlap - The overlapping part of the second range is adjusted

Start Overlap - The overlapping part of the second range is adjusted

Part 5

Part 5 is the hardest, as it means the second range needs to be split into two non-overlapping parts.

Complete Overlap - The second range is split into two ranges

---

So we have the scenarios, now to implement them. These are fortunately fairly simple one liner functions to do each check.

// Check for rule 1
const isOverlapping = ([a_start, a_end], [b_start, b_end]) =>
    a_start <= b_end && a_end >= b_start;

// Check for rule 2
const isCompleteOverlap = ([a_start, a_end], [b_start, b_end]) =>
    a_start <= b_start && a_end >= b_end;

// Check for rule 3
const isStartOverlap = ([a_start, a_end], [b_start, b_end]) =>
    a_start <= b_start && a_end >= b_start && a_end < b_end;

// Check for rule 4
const isEndOverlap = ([a_start, a_end], [b_start, b_end]) =>
    isStartOverlap([b_start, b_end], [a_start, a_end]);

// Check for rule 5
const isInverseOverlap = ([a_start, a_end], [b_start, b_end]) =>
    isCompleteOverlap([b_start, b_end], [a_start, a_end]);

With these checks in place it is then a matter of applying them in order. When a match is found the appropriate action is taken to either discard, adjust or split the range as needed. The required actions are:

1. Do nothing
2. Discard the range
3. Adjust the start of the range
4. Adjust the end of the range
5. Split the range into two new ranges

const keptRanges = [];
do {
    const range = ranges.shift();

    for (const acceptedRange of keptRanges) {
        const [acceptedStart, acceptedEnd] = acceptedRange;
        const [currentStart, currentEnd] = range;

        if (!isOverlapping([acceptedStart, acceptedEnd], [currentStart, currentEnd])) {
            // No overlap so try the next one
            continue;
        }
        if (isCompleteOverlap([acceptedStart, acceptedEnd],[currentStart, currentEnd])) {
            // Complete overlap, so discard the range
            // This means it isn't added to the processed list
            break;
        }
        if (isStartOverlap([acceptedStart, acceptedEnd],[currentStart, currentEnd])) {
            // Adjust the start of the range
            range = [acceptedEnd + 1, currentEnd];
        } else if (isEndOverlap([acceptedStart, acceptedEnd],[currentStart, currentEnd])) {
            // Adjust the end of the range
            range = [currentStart, acceptedStart - 1];
        } else if (isInverseOverlap([acceptedStart, acceptedEnd],[currentStart, currentEnd])) {
            // Create two new ranges, and start the process again
            const newRangeBefore = [currentStart, acceptedStart - 1];
            const newRangeAfter = [acceptedEnd + 1, currentEnd];

            // When having an exact overlap at the start or end
            // and invalid range can be created, so only add valid ones
            if (newRangeBefore[0] <= newRangeBefore[1]) {
                ranges.unshift(newRangeBefore);
            }
            if (newRangeAfter[0] <= newRangeAfter[1]) {
                ranges.unshift(newRangeAfter);
            }
            break;
        }
    }
    keptRanges.push({ ...range });
} while (ranges.length > 0);

While this looks complex, it is really 5 small simple steps combined into one script.

Showing the results

For ranges moved with rule 3 or 4, I have highlighted the change in the output to make it clear what has happened.

For rule 5 I have indented the split ranges to make it clear they came from a single original range.

Run

---

Want to read more? Check out more posts below!

---