Problem description

The objective of this problem is to find integers made of a sequence of digits repeated twice (part 1), or at least twice (part 2), included in integer ranges.

For example, 55 (5 twice), 6464 (64 twice), and 123123 (123 twice) can be invalid IDs in both parts, and 232323 can be invalid in Part 2.

Part 1

To solve this puzzle, I chose to use an “arithmetic” method, instead of using a method involving string manipulations, for performance reasons.

First, I needed some small mathematical functions. The first one counts the number of digits of an integer :

private def digitCount(n: Long): Int =
  var count = 0
  var m = n
  while m > 0 do
    m /= 10
    count += 1
  count

The second calculates n raised to the power of m :

private def pow(n: Long, m: Int): Long =
  var a = 1L
  for i <- 1 to m do
    a *= n
  a

The final one builds a number made of a sequence of digits n, repeated r times :

private def repeat(n: Long, r: Int): Long =
  var m = n
  for i <- 2 to r do
    m = m * pow(10, digitCount(n)) + n
  m

Input data parsing, to get an array of integer ranges (encoded as 2-element tuples) is a simple one-liner :

val ranges = input.head.split(",").map(x => x.split("-").map(y => y.toLong)).map(x => (x(0), x(1)))

On this base, I could calculate the set of “invalid IDs”, made of a sequence of digits repeated a given number of times. For each integer range, I searched the lowest number that could give an invalid ID included in the range. Then I incremented until I reached the end of the range.

When I solved the first half of the puzzle, the argument repeats was always equal to 2. I wrote the final version of this method when I solved the second part.

private def invalidIds(ranges: Array[(Long, Long)], repeats: Int): Set[Long] =
  var invalid: Set[Long] = Set()
  for (start, end) <- ranges do
    val d = digitCount(start)
    var n = if d % repeats == 0 then
      start / pow(10, d * (repeats - 1) / repeats)
    else
      pow(10, d/repeats)
    while repeat(n, repeats) <= end do
      var m = repeat(n, repeats)
      if m >= start then
        invalid += m
      n += 1
  invalid

The result comes by summing the integers returned by the invalidIds() method.

def solvePart1(input: List[String]): Long =
  val ranges = input.head.split(",").map(x => x.split("-").map(y => y.toLong)).map(x => (x(0), x(1)))
  invalidIds(ranges, 2).sum

Part 2

For the second half, I ran the invalidIds() method for every value of repeats from 2 to the length of the highest range end, I computed the union of the returned integer sets, and I returned the sum of this final set.

def solvePart2(input: List[String]): Long =
  val ranges = input.head.split(",").map(x => x.split("-").map(y => y.toLong)).map(x => (x(0), x(1)))
  val maxRepeats = digitCount(ranges.map((start, end) => end).max)
  (2 to maxRepeats).map(i => invalidIds(ranges, i)).reduce((x, y) => x ++ y).sum

Performances

Both parts run in 1 millisecond on my laptop (An ASUS TUF Gaming A15 with Debian 13).