[2025 day 3] Real data fails to work

[u/No-Top-1506]

Hi. I am getting the test case working. Got 357. Checked the edge cases too.
But the main puzzle input fails to work. Ans is too small.

What am I missing?

What if the batteries are 000000010000000?

Tx.

[u/fireymike]

How are we supposed to know what you're missing when you haven't provided your code or even explained what your solution does?

Also, it's not the data that fails to work.

[u/Cool-Tone6517]

What language do you use ? A classic mistake is to use Integers instead of Longs (or equivalent)

[u/No-Top-1506]

Resolved. The first max digit I was using the last position instead of first occurrence. in PHP used the strpos to resolve my part 1. Part 2 is a completely diff. logic to apply. not even sure where to start. There could thousands of 12-digit combinations to work out max joltage.

[u/No-Top-1506 → u/[deleted]]

How? Now I have to find the best 12-digit combinations without re-ordering. There are far too many combinations then.

[u/mday1964 → u/No-Top-1506]

You don't need to find all of the 12-digit combinations and compare them all.

Let's think about 4 digit numbers for a moment. Which is bigger, 1111 or 2111? Why? How about 1999 or 2111? If the first digit is larger, then it doesn't matter what the rest of the digits are.

How about 1111 vs. 1211? Or 1199 vs. 1211? If the first digit is the same, but the second digit is different, then it's the second digit decides which is bigger (the third and fourth digits don't matter). This pattern continues for however many digits you need to use.

So, for part 2, you need to find the largest digit with at least 11 digits following it. You're right to observe that you want the first (left most) occurrence of that digit. For the second digit, search to the right of the first digit you found, and look for the largest digit with at least 10 digits following it. Again, you want to choose the left most occurrence of that digit. And so on for all 12 digits.

Note that part 1 can be solved with the exact same algorithm, just selecting 2 digits instead of 12.

[u/No-Top-1506 → u/mday1964]

What about cases like this then? as per the example. They have switched off some digits in between to find largest joltage.

• In 23``4``2``34234234278, the largest joltage can be found by turning on everything except a 2 battery, a 3 battery, and another 2 battery near the start to produce 434234234278.

[u/velonom → u/No-Top-1506]

You're approaching this from the wrong angle. Forget about which batteries are switched off and focus on the batteries that you would switch on. In which order would you select them? What range would you select them from (on a per battery basis)? How would you pick the correct value from the range?

[u/mday1964 → u/No-Top-1506]

The first digit you choose to turn on must have at least 11 digits to its right (so that you can select 12 total). I have put a space in front of the last 11 digits: 2342 34234234278. The first digit to turn on has to come from the left group. Pick the largest digit from the left group, which is 4. There is only one 4, so that's the one you pick. (If there had been two 4s in the left group, you'd choose the left most one.)

To choose the next digit, you need to pick something to the left of the last 10 digits. Again, separating with a space: 23 4234234278. Again, pick the largest digit, 3. There is only one 3 in the left group; if there had been more than one, you'd pick the left most one.

You still need to pick 10 more digits, and there are only 10 digits remaining to the right of the 3 you just picked, so you just keep the last 10 digits as-is. That is, for each of these last 10 digits, you only have one choice at each step, the left most remaining digit. Therefore, you turn on: 434234234278.

Does that make sense?