Module day02 

Gift Shop

We solve efficiently by inverting the problem and avoiding slow string manipulation. Instead of checking every possible id within each range for invalid patterns, we generate a list of invalid patterns numerically then check how many overlap the range given by each pair of ids.

Let (n,k) denote the set of patterns k wide in a number n digits long, where k must divide n evenly. For example some (6,3) patterns are 123123, 456456 and 789789.

Part One

The input contains ids ranging from 2 to 10 digits, so we check for patterns where k is half of n, that are (2, 1), (4, 2), (6, 3), (8, 4), and (10, 5).

Part Two

We also consider the remaining patterns where n is evenly divisible by k. However we need to be careful to avoid double counting. We notice that pattern sets with the same n contain other sets when the second k is a factor of the first. For example (8,4) contains (8,2), as a number such as 23232323 can be split into either two fours or four twos. All sets (n, k) contain (n, 1), for example 22222222 could be split into four, two or one.

Our high level approach is then:

• Count ids in part one
• Count the extra ids in part two, subtracting those that overlap.

Generating ranges

Let’s use a concrete example of (9,3). This range starts at 100100100 and we can generate the next number in the set by adding 001001001. The step value is given mathematically as (10ⁿ - 1) / (10ᵏ - 1), that is 999999999 / 999 = 1001001. The start value is then 10ᵏ⁻¹ times the step (100 * 1001001 = 100100100) and the end value is 10ᵏ - 1 times the step (999 * 1001001 = 999999999).

We then check each range of ids for the minimum and maximum multiple of the step value that it contains, clamping at the start and end values. For example, the id range 50-70 contains 55 and 66 from the set (2,1) with a step of 11. A second id range of 100-130 also contains multiples of 11 but these are ignored as they are outside the start and end values.

To sum the set values within each range we use the triangular number formula (n * (n + 1)) / 2 that sums the numbers from 1 to n. For example:

• 44 + 55 + 66 + 77
• (4 * 44) + 11 + 22 + 33
• (4 * 44) + 11 * (1 + 2 + 3),
• Replace 1 + 2 + 3 with the formula.

Constants

FIRST 🔒

Sets in part one.

SECOND 🔒

Sets in part two.

THIRD 🔒

Overlap between sets in part one and part two.

Functions

parse

part1

part2

sum 🔒

Generate the start and end values for a set, then sum the number of values contained in the given id range.

Type Aliases

Pair 🔒

Range 🔒