Advent of Code 2025 - Python - Day 2
Day 2 of the 2025 Advent of Code sees us helping Santa's elves remove some invalid product IDs from their gift shop's product database - a kid was playing on the gift shop computer and added a bunch by accident. There are some product ID ranges we need to check:
11-22,95-115,998-1012,1188511880-1188511890,222220-222224,1698522-1698528,446443-446449,38593856-38593862,565653-565659,824824821-824824827,2121212118-2121212124
The IDs are encoded as a set of ranges with a starting ID and an ending ID separated by a dash. Subsequent ranges are separated by a comma.
Part 1
Invalid IDs are those which have some sequence of digits repeated inside them twice - examples given are 55 (5 twice), 6464 (64 twice), and 123123 (123 twice). You get the idea. Of note is that the problem specifies that things are repeated twice - something repeated three times is no problem.
To complete the first part of the puzzle, we need to identify all the invalid IDs in the provided ranges and add them up. If we get the correct sum, we pass and can move on to the second part of the puzzle.
I'll work through the given example ranges to build up my Python script, but my real puzzle input is very large and is randomized per-user - I won't bother sharing it here since it doesn't matter as long as my solution works correctly.
As always, I'll start with reading the text data from file. Since the ranges are all separated by commas, I'll split on commas in the readlines comprehension to get a list where each entry is its own range:
# Read data from file
rawRanges = []
with open("data/2.short", "r") as f:
rawRanges = [line.split(",") for line in f.readlines()]
# Unpack the nested loop and clear remaining `\n`s
rawRanges = rawRanges[0]
cleanRanges = [line.strip() for line in rawRanges]
print(cleanRanges)
The comments do a good job of walking through this, but the rawRanges = rawRanges[0] is a little weird; because my source data is on a single line, and readlines() reads lines of text into their own list entry, and then my comprehension splits that list entry, I end up with a nested list where the outer list only has one entry - the inner list, and the inner list has all my data:
[['11-22', '95-115', '998-1012', '1188511880-1188511890', '222220-222224', '1698522-1698528', '446443-446449', '38593856-38593862', '565653-565659', '824824821-824824827', '2121212118-2121212124\n']]
By setting rawRanges to the 0th index of that list, we essentially "unwrap" the nested list and just get the inner one, which is what we want since it has our data.
Also notice the \n at the end of the last entry - readlines() doesn't strip newlines, and since that entry was at the end of our text file it had the \n character after we split by commas.
The cleanRanges comprehension resolves this, and we end up with our "clean" ranges:
['11-22', '95-115', '998-1012', '1188511880-1188511890', '222220-222224', '1698522-1698528', '446443-446449', '38593856-38593862', '565653-565659', '824824821-824824827', '2121212118-2121212124']
Next, let's break these up into tuples where the first element is the start and the second is the end:
# Parse ranges into tuples
ranges = []
for idRange in cleanRanges:
items = idRange.split("-")
ranges.append((int(items[0]), int(items[1])))
There's probably a list comprehension that does this, but I have trouble parsing comprehensions more than one "layer" deep. To me, this loop is very readable and it's obvious what's happening. I convert the text to integers because, while the problem we're trying to solve does rely on checking for textual repetition, we also know we need to check every integer value between the two range ends. It seems like having the values already as integers will be convenient. We now have, in ranges:
[(11, 22), (95, 115), (998, 1012), (1188511880, 1188511890), (222220, 222224), (1698522, 1698528), (446443, 446449), (38593856, 38593862), (565653, 565659), (824824821, 824824827), (2121212118, 2121212124)]
My thinking is that this will be the easiest way to store the range information. When we actually check for repetition, we'll start at the starting value and check to see if it's composed of two repeated strings of characters. Then we'll check the next, and the next, and so on, until we reach the final value. One of the examples in the prompt shows that the range to check is inclusive of the starting and ending values.
Because we only have to check if some series of digits is repeated twice, we know that:
- Any ID with an odd number of digits is automatically valid
- For any ID with an even number of digits, we can split it down the middle and compare the two halves; if they match, the ID is invalid
This makes the next step fairly clear:
# Check each ID in each range for validity
invalidSum = 0
for idRange in ranges:
for id in range(idRange[0], idRange[1]+1):
strId = str(id)
strIdLen = len(strId)
# If the ID has an odd number of digits, it's always valid
# Move on to the next ID
if strIdLen % 2 != 0:
continue
# Otherwise, check to see if the two halves of the ID are the same
halfStrLen = int(strIdLen/2)
firstHalf = strId[:halfStrLen]
secondHalf = strId[halfStrLen:]
# If they are, the ID is invalid. Add it to our accumulator.
if firstHalf == secondHalf:
invalidSum += id
This loop is straightforward, but is complicated a bit by some precomputation and casting. It's two nested loops: the outer loops over each range in my list of ranges (so the first iteration loops over the range 11-22, the second over the range 95-115, and son on), and the inner loop loops over each valid in that range. Note that range is itself a Python keyword, and one we have to use here - it just gives us a list of values from the starting point to the ending point we've defined. Also note that we have to add one to the end point, because Python's range() doesn't include the ending value by default.
Inside the loop, we cast the ID to a string and put it in strId, and get its length and put that in strIdLen. These values will need to be used later, so it makes sense to put them in a variable to avoid recomputing them.
Then we check if the string version of the ID has an odd number of characters in it. If it does, then it can't be made of two repeated halves so it's automatically valid. We continue to the next iteration of the inner loop, and go to check the next ID.
If the ID has an even number of digits, we first compute what half of the string's length is (casting it to an integer so we can use it as a list index - I was surprised that python complained about me using 1.0 as a loop index and didn't automatically cast that to an integer; obviously fractional values should cause an error but I figured this would work since Python is usually so permissive). Then we take the first half and stick it in firstHalf, take the second half and stick it in secondHalf, and compare the two. If they're identical, then the ID is invalid and we add the original numerical ID value to our invalidSum accumulator variable.
In the end, we get an answer of 1227775554, which is the correct answer for the sample input we've been looking at.
To run my code against the "real" input - which I said I won't be posting here since it's long and not super relevant - all I need to do is change what file I'm reading from initially:
with open("data/2.long", "r") as f:
I now get an answer of 30323879646, which is the correct answer for me, and we can move on to Part 2. For the longer input this takes a noticeable amount of time but is still fairly quick - time says it was 0.305s of userspace time. Hopefully Part 2 doesn't dramatically increase our complexity or anything....
Part 2
Here, our complexity dramatically increases. Instead of only looking for IDs made up of some set of digits that repeats twice, we now have to look for IDs made up of any set of digits that repeat any number of times. So IDs like 123123123 (123 three times), 1212121212 (12 five times), and 1111111 (1 seven times) are all now invalid.
Notably, this means values with an odd number of digits can now also be invalid. We can't just automatically disqualify them anymore.
We'll go back to examining our "short" input. The input parsing logic seems like it's still just as valid as it was, so we can leave that unchanged. But we need to re-examine our ID-checking loop:
# Check each ID in each range for validity
invalidSum = 0
for idRange in ranges:
for id in range(idRange[0], idRange[1]+1):
strId = str(id)
strIdLen = len(strId)
# If the ID has an odd number of digits, it's always valid
# Move on to the next ID
if strIdLen % 2 != 0:
continue
# Otherwise, check to see if the two halves of the ID are the same
halfStrLen = int(strIdLen/2)
firstHalf = strId[:halfStrLen]
secondHalf = strId[halfStrLen:]
# If they are, the ID is invalid. Add it to our accumulator.
if firstHalf == secondHalf:
invalidSum += id
First, we definitely don't care if the value has an odd number of digits anymore. Let's remove that check:
# Check each ID in each range for validity
invalidSum = 0
for idRange in ranges:
for id in range(idRange[0], idRange[1]+1):
strId = str(id)
strIdLen = len(strId)
# Otherwise, check to see if the two halves of the ID are the same
halfStrLen = int(strIdLen/2)
firstHalf = strId[:halfStrLen]
secondHalf = strId[halfStrLen:]
# If they are, the ID is invalid. Add it to our accumulator.
if firstHalf == secondHalf:
invalidSum += id
But now we have to think a little more carefully about how we solve this. We clearly still have to check if IDs are just made of an identical first half and second half, but we also need to check if they're made of the same number repeating a bunch, or two numbers repeating if they're even, or three numbers repeating if they're divisible by three, and so on.
In other words, we need to check if the ID is made of repeated substrings of length n, where n is the list of factors of the total length of the substring. If some ID had a length of 24 digits, we'd have to check for repeated substrings of length 1, 2, 3, 4, 6, 8, and 12 (we don't check 24 because that's not really repetition is it). Our existing logic only checks for, in this example, 12. We need to expand that and check for all of them. But first, we have to compute them. We're going to need another loop:
# Check each ID in each range for validity
invalidSum = 0
for idRange in ranges:
for id in range(idRange[0], idRange[1]+1):
# Compute the factors of the ID's length
strId = str(id)
strIdLen = len(strId)
factors = []
for factor in range(1, int((strIdLen/2)+1)):
if strIdLen % factor == 0:
factors.append(factor)
Now we have a list of the factors of the length of the ID. We need to loop through those, check if the ID is made of repeated substrings of that length, and if so mark the ID as invalid. Once we find proof that an ID is invalid we don't need to check the rest of the factors and can just move on to the next ID. This logic was surprisingly straightforward. I'll highlight just this final check:
# Check if this ID is made of repeated substrings of length <factor>
for factor in factors:
numRepeats = int(strIdLen / factor)
trialString = strId[:factor] * numRepeats
if trialString == strId:
invalidSum += id
break
For every factor, we compute how many times that factor goes into the string. We know this value will be an integer because that's how we selected our factors in the first place - the factors are the values which evenly divide into the ID's length. We then take the first factor values of the string - the first 1 value if the factor is 1, the first 2 values if the factor is 2, and so on - and construct a string made entirely of that substring repeated. The substring is repeated numRepeats times - that's how many times factor divides into strIdLen - so it has the same length as the ID we're checking. Finally, if the string we're testing and the original ID are identical, we mark it as invalid. The break tells Python not to keep checking other factors once we've identified that an ID is invalid.
This gives us with the final code:
# Read data from file
rawRanges = []
with open("data/2.short", "r") as f:
rawRanges = [line.split(",") for line in f.readlines()]
# Unpack the nested loop and clear remaining `\n`s
rawRanges = rawRanges[0]
cleanRanges = [line.strip() for line in rawRanges]
# Parse ranges into tuples
ranges = []
for idRange in cleanRanges:
items = idRange.split("-")
ranges.append((int(items[0]), int(items[1])))
# Check each ID in each range for validity
invalidSum = 0
for idRange in ranges:
for id in range(idRange[0], idRange[1]+1):
# Compute the factors of the ID's length
strId = str(id)
strIdLen = len(strId)
factors = []
for factor in range(1, int((strIdLen/2)+1)):
if strIdLen % factor == 0:
factors.append(factor)
# Check if this ID is made of repeated substrings of length <factor>
for factor in factors:
numRepeats = int(strIdLen / factor)
trialString = strId[:factor] * numRepeats
if trialString == strId:
invalidSum += id
break
print(invalidSum)
This gives me the correct answer of 4174379265 for the sample input we've been looking at, and the correct answer of 43872163557 for the longer "real" input. This takes 1.140 seconds in userspace.
Optimization
While writing the factor computation, I thought of a potential optimization. In the existing code, we compute a new set of factors for every unique ID - in reality, factors are a fixed product of the number of digits an ID has. Surely there's some way to compute factors once for each strIdLen and just reference already-computed values if we've already done the work?
This can be accomplished pretty easily with a dict:
# Check each ID in each range for validity
invalidSum = 0
factorCache = {}
for idRange in ranges:
for id in range(idRange[0], idRange[1]+1):
# Compute the factors of the ID's length
strId = str(id)
strIdLen = len(strId)
# Compute factors for this ID length, if not already known
if strIdLen not in factorCache:
factorCache[strIdLen] = []
for factor in range(1, int((strIdLen/2)+1)):
if strIdLen % factor == 0:
factorCache[strIdLen].append(factor)
# Check if this ID is made of repeated substrings of length <factor>
for factor in factorCache[strIdLen]:
numRepeats = int(strIdLen / factor)
trialString = strId[:factor] * numRepeats
if trialString == strId:
invalidSum += id
break
We initialize an empty dictionary (factorCache, a place to cache our factors) before looping through the ranges. Once we've identified the strIdLen of the ID we're checking, we quickly check if the dictionary has a key matching that value. If so, we already have a set of computed factors for this ID length and can move right to checking the ID's validity. If not, we compute the factors and store them in the factor cache.
This gives us the same result, but did it improve runtime? Yes! This improved script now takes 0.718 seconds in userspace. That's a 37% reduction in runtime for a pretty straightforward optimization.
I'm sure there are many more optimizations - I bet with some clever division/modulus you could avoid string comparisons entirely. But this one seemed clear to me and I wanted to see what effect it had. My intuition was that computing factors was fairly computationally intensive (as we're running through every value to check if it's a factor), and that cutting out that extra work in the vast majority of cases would save us a ton of time. It's nice to see that hunch play out.
This puzzle was a little more involved than the last one but didn't pose too much of a challenge. Presumably they'll only get harder from here.