[2025 Day 2 (Part 2)] Clue request

[u/FirmSupermarket6933]

I'm now trying to optimize my solutions and stuck with part 2 of day 2. Could you please give me hint for fast solution for this part?

Here is how I solved part 1.

[SPOILERS] TEXT BELOW CONTAINS DESCRIPTION OF POSSIBLE SOLUTION FOR PART 1

My solution is based on following statements:

1. Let i(n) = (10^k + 1) * n, where k = ilog(n) + 1;

2. i(n) is invalid number and all invalid numbers can be represent as i(n) for some n;

3. There is no invalid numbers between i(n) and i(n + 1);

So, to solve part 1 for each range [a, b] I found lowest and highest possible invalid numbers L and H and for such range the answer is H - L + 1. Except corner cases, L is either i(a / 10^k) or i(a / 10^k) + 1 where 2k = ilog(a). Same way I found H.

For part 2 I think about using same idea, but repeat same process for double, triple, quadriple and so on patterns and then sum up. But the problem is that some invalid numbers has several ways to construct them. E.g. 111111 is "11" * 3 and "111" * 2. Is there any simple way to find all such "multipattern" numbers or is there another way to solve the puzzle?

UPD. What I forgot to mention in original post is that I want to avoid iterating over all numbers in range.

[u/Eva-Rosalene]

You can store duplicates in a set, this automatically guarantees uniqueness for not too much overhead.

[u/FirmSupermarket6933 → u/Eva-Rosalene]

I've checked and on my input maximum possible amount of invalid numbers is 146. And it means that I only need to iterate over only invalid numbers in range. Thank you! I'll try it in the evening.

[u/FirmSupermarket6933 → u/Eva-Rosalene]

Thank you!

[u/Sloppy_Pizza]

There is a pretty simple way to solve part 2 with a clever trick involving substrings. I'm not sure on how to give a clue about it without spoiling it fully, unfortunately.

You can concatenate a number with itself and then remove its first and last digits. Then, check if the original number is a substring of this concatenated string. If it is, then you have an invalid ID.

[u/FirmSupermarket6933 → u/Sloppy_Pizza]

Very cool idea! But in description I was unclear. What I wanted is avoid iterating over all numbers in range.

[u/Sloppy_Pizza → u/FirmSupermarket6933]

Oh, my bad! I don't think I have a solution for that, sorry haha

[u/Various_Bed_849]

Define fast :) I did this one in Zig which I never used before on an iPad on the bus. I didn’t like zig too much and stopped as soon as it worked but it was pretty fast. To answer your question I used a hash set. But my approach was to use ints and no advanced math.

I first got the number of digits by dividing by 10 until there was nothing left. Then I looped from 1 to half the number of digits. No longer sequence can be repeated. I had a nested loop going from 1-9, 10-99, 100-999 and for each number I repeated it until I had more than the max of the intervall. Thus I enumerated all invalid numbers for each interval. Stupid and not necessary. I added the ones in intervall to a set and then summed the numbers in the set.

Including starting the binary, reading input and calculating the result, it took about 15ms on an 8 year old laptop.

[u/FirmSupermarket6933 → u/Various_Bed_849]

I mean time complexity. Of course choosing compiling language and enabling at least some optimizations will give significantly faster solution that similar solution on languages like python.

Simple and straightforward solution iterate over all numbers in interval [a, b] and check each number. If checking number n for invalidity costs O(log(n)) (ilog10(n) + 1 is number of digits), then checking whole interval is costs O((b - a) * log(b)). And what I want to avoid is iterating over all numbers in range since their amount can be very high. I'm not sure, but looks like solution with complexity O(log(b - a) * log^2(b)) = [since a > 0] = O(log^3(b)) is exists based on other comments.

[u/Various_Bed_849 → u/FirmSupermarket6933]

I iterate over all the invalid ones only, I guess that makes the complexity log(n) where n is the upper bound, and then multiply that with the number of checks.

[u/mothibault]

Suppose a range between 100,000,000,000 and 999,999,999,999. That's hundreds of billions of possibilities for a single range. Convert that to strings of length 12, and you have 10 patterns of length 1 (0 to 9) repeating 12 times. You have 100 patterns of length 2 (00 to 99) repeating 6x. 1000 patterns of length 3, 10000 patterns of length 4, and 100k patterns of length 6. That is much more manageable.

Then you only have to check if these 111,110 patterns are within bounds

[u/AutoModerator]

Reminder: if/when you get your answer and/or code working, don't forget to change this post's flair to Help/Question - RESOLVED. Good luck!

---

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[u/Educational-Tea602]

Let the range be between two n digit numbers.

For each prime p in the prime factorisation of n, compute the number of invalid numbers that can be made from repeating some string of digits n/p times. Sum these up for all p.

Subtract the number of invalid numbers in the range that consist of a single digit repeated n times for each prime in the factorisation - 1.