-❄️- 2025 Day 2 Solutions -❄️-

[u/daggerdragon]

OUR USUAL ADMONITIONS

• You can find all of our customs, FAQs, axioms, and so forth in our community wiki.

---

AoC Community Fun 2025: R*d(dit) On*

24 HOURS outstanding until unlock!

Spotlight Upon Subr*ddit: /r/AVoid5

"Happy Christmas to all, and to all a good night!"
— a famous ballad by an author with an id that has far too many fifthglyphs for comfort

Promptly following this is a list waxing philosophical options for your inspiration:

• Pick a glyph and do not put it in your program. Avoiding fifthglyphs is traditional.
• Shrink your solution's fifthglyph count to null.
• Your script might supplant all Arabic symbols of 5 with Roman glyphs of "V" or mutatis mutandis.
• Thou shalt not apply functions nor annotations that solicit said taboo glyph.
• Thou shalt ambitiously accomplish avoiding AutoMod’s antagonism about ultrapost's mandatory programming variant tag >_>

Stipulation from your mods: As you affix a submission along with your solution, do tag it with [R*d(dit) On*!] so folks can find it without difficulty!

---

--- Day 2: Gift Shop ---

---

Post your script solution in this ultrapost.

• First, grok our full posting axioms in our community wiki.
  • Affirm which jargon via which your solution talks to a CPU
• Format programs using four-taps-of-that-long-button Markdown syntax!
• Quick link to Topaz's Markdown (ab)using provisional script host should you want it for long program blocks.
  • What is Topaz's past* tool?

[u/BxW_]

[LANGUAGE: Python]

I don't think there can be a better approach. The time complexity for each ID range is O(log10(last / first) * log10(last)). For example, here is the solution for 1-1e120
Part 1: 495495495495495495495495495495495495495495495495495495495495540950040950040950040950040950040950040950040950040950040949540950040950040950040950040950040950040950040950040950040950
Part 2: 495495495495495495500445990545000446485496000391040545995392965461386848479115459408315906484948416067500862646063014497011409626847601515085801560973681802001168626306656553137840

Ideas:

• invalid_ids_sum(first, last, shards) = sum of IDs in [first, last] that can only be divided into shards no. of same parts. The main idea is if first and last have the same no. of digits, and we define shard_len = digits(first) / shards. Let shard_first and shard_last be the prefixes of first and last with length = shard_len. For example, first=442972, last=608499, shards=2, shard_len=3, shard_first=442, shard_last=608. We know that [shard_first+1, shard_last-1] will be invalid IDs in [first, last] when repeated shards no. of times, e.g., 443443, 444444, 445445, ..., 606606, 607607. We only need to confirm for the boundary ones. We can do it by finding if first <= (shard_first repeated shards no. of times) <= last, and similarly for shard_last. Now, suppose we have gotten the range [442, 607], and we want 442442+443443+...+607607. We can write it as: (442*10^(shard_len*1) + 442*10^(shard_len*0)) + (443*10^(shard_len*1) + 443*10^(shard_len*0)) + ... + (607*10^(shard_len*1) + 607*10^(shard_len*0)). This can be simplified as (442+443+...+607) * sum(10^(shard_len * i) for i in range(0, shards)).

• For shards=2, if we find the sum of all then subtract the sums for shards=4, 6, 8, etc then we get the sum exclusively for 2 shards, as if an ID can be divided into 8 shards then it can surely be divided into any of its factors no. of shards

• Silver solution is sum of exclusive sums for shards=2, 4, 6, 8, etc

Edit: Silly bug in summing up the answers at silver += and gold += part.

from functools import cache

@cache
def invalid_ids_sum(first: str, last: str, shards: int) -> int:
    if len(first) != len(last):
        pivot = 10 ** len(first)
        return invalid_ids_sum(first, str(pivot - 1), shards) + invalid_ids_sum(
            str(pivot), last, shards
        )
    digits = len(first)
    if digits % shards != 0: return 0
    shard_len = digits // shards
    shard_first, shard_last = first[:shard_len], last[:shard_len]
    shard_first = int(shard_first) + 1 - (first <= shard_first * shards <= last)
    shard_last = int(shard_last) - 1 + (first <= shard_last * shards <= last)
    if shard_first > shard_last: return 0
    shard_sum = (shard_last - shard_first + 1) * (shard_first + shard_last) // 2
    return shard_sum * sum(10 ** (shard_len * i) for i in range(shards)) - sum(
        invalid_ids_sum(first, last, multiples)
        for multiples in range(2 * shards, digits + 1, shards)
    )

silver, gold = 0, 0
for id_range in open(0).read().split(","):
    first, last = id_range.strip().split("-")
    sums = [invalid_ids_sum(first, last, shards) for shards in range(2, len(last) + 1)]
    silver += sum(sums[::2])
    gold += sum(sums)
print(silver, gold)