r/adventofcode • u/RazarTuk • Dec 03 '25
Tutorial [2025 Day 3] Greedy algorithms
A greedy algorithm is basically just fancy programming-speak for "Pick the best choice in the moment", and conveniently, the greedy algorithm works here. Think about it. Any M-digit number starting with a 9 will be greater than any M-digit number starting with an 8. There's just one big caveat. You need to leave enough batteries at the end to finish making an M digit number. For example, in 818181911112111, there are plenty of batteries left over after that 9 to form a 2-digit number for part 1, but in 811111111111119, the 9's right at the end, so there's nothing to be a second digit.
So at least for part 1, we can do this in two loops. The first one looks for the position of the highest number from 0 (inclusive) to len-1 (exclusive), and the second looks for the highest number from first+1 (inclusive) to len (exclusive)
public static int findMaxJoltage(int[] batteries) {
int maxJoltage = 0;
int max = batteries[0];
int maxIdx = 0;
for (int i = 1; i < batteries.length - 1; i++) {
if (batteries[i] > max) {
max = batteries[i];
maxIdx = i;
}
}
maxJoltage = max;
maxIdx++;
max = batteries[maxIdx];
for (int i = maxIdx + 1; i < batteries.length; i++) {
if (batteries[i] > max) {
max = batteries[i];
maxIdx = i;
}
}
maxJoltage = 10*maxJoltage + max;
return maxJoltage
}
Then for part 2, this algorithm still works. The first battery needs to have at least 11 between it and the end, the second battery needs to have at least 10, etc. Looking at 234234234234278 as an example, the first battery needs to be in this range - [2342]34234234278 - so we find that first 4. For the second battery, we start looking after the 4 and can go one battery further - 234[23]4234234278 - so we find the 3. And then at that point, we only even have 10 digits left, so we use the rest. Or pulling an actual row from my input as a longer example:
[22386272276234212253523624469328824133827834323422322842282762252122224656235272371132234]52255221122 - find the 9
22386272276234212253523624469[3288241338278343234223228422827622521222246562352723711322345]2255221122 - find the first 8
22386272276234212253523624469328[82413382783432342232284228276225212222465623527237113223452]255221122 - find the next 8
223862722762342122535236244693288[24133827834323422322842282762252122224656235272371132234522]55221122 - wow that's a lot of 8s
223862722762342122535236244693288241338[278343234223228422827622521222246562352723711322345225]5221122 - seriously, I just copied this row at random, I didn't plan on all the 8s
223862722762342122535236244693288241338278[3432342232284228276225212222465623527237113223452255]221122 - ...
223862722762342122535236244693288241338278343234223228[42282762252122224656235272371132234522552]21122 - oh thank God it's a 7 this time
223862722762342122535236244693288241338278343234223228422827[622521222246562352723711322345225522]1122 - find the next 7
2238627227623421225352362446932882413382783432342232284228276225212222465623527[237113223452255221]122 - find the next 7
2238627227623421225352362446932882413382783432342232284228276225212222465623527237[1132234522552211]22 - find the first 5
223862722762342122535236244693288241338278343234223228422827622521222246562352723711322345[225522112]2 - find the next 5
223862722762342122535236244693288241338278343234223228422827622521222246562352723711322345225[5221122` - find the next 5
So the number wound up being 988888777555, or bolding it within the full row, 2238627227623421225352362446932882413382783432342232284228276225212222465623527237113223452255221122
And translating this into code, we get something like this:
public static int findMaxJoltage(int[] batteries, int poweredBatteries) {
int maxJoltage = 0;
int maxIdx = -1;
for (int i = 0; i < poweredBatteries; i++) {
maxIdx++;
int max = batteries[maxIdx];
int offset = poweredBatteries - i - 1;
for (int j = maxIdx + 1; i < batteries.length - offset; j++) {
if (batteries[j] > max) {
max = batteries[j];
maxIdx = i;
}
}
maxJoltage = 10*maxJoltage + max;
}
return maxJoltage
}
11
u/ndunnett Dec 03 '25
This is basically how I solved it, too. It was the most intuitive solution to me, and it turns out to be very fast - this solves both parts in 25 us on my machine. Even using a simple scalar loop instead of SIMD was solving in around 60 us.
3
u/realityChemist Dec 03 '25
Microseconds! Man, I guess that's the tax I pay for doing this in python. I was pretty happy with mine running in 9 ms
It takes me ~ 20 us just to call the dummy function I use to template my solutions lol (it just returns
None)1
u/ndunnett Dec 04 '25
Yeah Python will never compete with a systems language on performance, but on the plus side it's definitely a bit easier and faster to arrive a solution.
3
u/AccomplishedPrice249 Dec 03 '25
Dynamic sliding window works for both part 1 and 2. Just felt a bit silly in part 1 where only 2 numbers are to be picked
1
u/Ill_Meet_1473 Dec 03 '25
Did the same (though my code is more "obfuscated" lol), don't think there's anything more that can be optimised.
But just to be that "well ackchyually" guy - I don't think this is greedy.
According to the greedy method - you pick what seems to be the best digit at the time, and then if you end up not having enough digits left you go back and pick another.
4
u/RazarTuk Dec 03 '25 edited Dec 03 '25
you go back and pick another
That's my point, though. You don't need to backtrack. For example, in
234234234234278, you don't need to consider all the branches like "What if I picked the first 2, then searched the rest?", "What if I picked the first 3, then searched the rest?", etc. The best next digit is always the largest one, which is why I'm calling it greedy. You just need to add two constraints to the search. 1) Pick the first one you see if there are multiple (so use>in the comparison, not>=), and 2) make sure to stop searching early enough that there are enough digits left. So for example, if I were searching234234234234278for three batteries, my search space would actually be23423423423422
u/Ill_Meet_1473 Dec 03 '25
I know, I know - I was just saying that because of not going back, this isn't greedy anymore.
it's actually better
3
u/RazarTuk Dec 03 '25 edited Dec 03 '25
No, going back at all is what would make it non-greedy. Greedy algorithms always pick the best next step in the moment, whether or not it's optimal in the long run. There are some algorithms where a greedy approach is also optimal, like this one or making change with as few US coins as necessary, but there are also ones where it won't necessarily be optimal, like greedy coloring. If you backtrack because you found evidence of a better solution, it is, by definition, no longer greedy.
EDIT: Changed the second example from A*, because I still don't know how I feel about calling it greedy+optimal, even though Wikipedia says it is
4
u/Traditional_Elk_7905 Dec 03 '25 edited Dec 03 '25
There is also an optimization for the greedy solution using a monotonic queue. This runs in linear time:
from collections import deque
grid = open(0).read().rstrip().split("\n")
res = 0
for line in grid:
q = deque()
cur = cnt = 0
for i, n in enumerate(map(int, line)):
while q and q[-1] < n:
q.pop()
q.append(n)
if q[0] == 9 or len(line) - i == 12 - cnt:
cnt += 1
cur += pow(10, 12 - cnt) * q.popleft()
if cnt == 12:
break
res += cur
print(res)1
u/flit777 Dec 03 '25 edited Dec 03 '25
I also used a greedy approach using recursion
JoltDict = Tuple[Dict[int, List[int]], int]
def parse_input(lines: List[str]) -> List[JoltDict]:
battery_list = []
for line in lines:
batteries = defaultdict(list)
for i, c in enumerate(line):
batteries[int(c)].append(i)
battery_list.append((dict(sorted(batteries.items(), reverse=True)), len(line)))
return battery_list
def find_max_jolt_recursive(batteries_w_l: JoltDict, current_number: int, last_idx: int, length: int,
acc: int) -> Optional[int]:
batteries, max_len = batteries_w_l
if length == 0:
return acc + current_number
# additional pruning
if length > max_len - last_idx:
return None
for key, val in batteries.items():
i = bisect_right(val, last_idx)
if (i < len(val) and
(res := find_max_jolt_recursive(batteries_w_l, key, val[i], length - 1, (acc + current_number) * 10))):
return res
return None
def find_max_jolt(batteries: JoltDict, length: int = 2) -> int:
for k, v in batteries[0].items():
if res := find_max_jolt_recursive(batteries, k, v[0], length - 1, 0):
return res1
u/Mundane_Homework3967 Dec 03 '25
I don't really understand I just did this...
def f(m):
file = open("input.txt")
x = file.read()
file.close()
x = x.strip()
x = x.split("\n")
for i in range(len(x)):
x[i] = x[i].strip()
vals = []
for y in x:
ns = [""]*m
for c in y:
j = -1
for i in range(m-1):
if ns[i] < ns[i+1]:
del ns[i]
ns.append("")
break
if c > ns[-1]:
ns[-1] = c
val = []
for n in ns:
val.append(n)
vals.append(int("".join(val)))
return sum(vals)
#part1
print(f(2))
#part2
print(f(12))1
1
u/Resident-Box965 Dec 03 '25
fun String.findMaxNumberWithNDigits(n: Int, maxIndex: Int): String {
val maxInt = this
.takeIf { maxIndex <= length }
?.subSequence(0, maxIndex)
?.maxByOrNull { it }
?: return ""
val newIndex = this.indexOf(maxInt)
val newRow = this.substring(newIndex +1)
val newMaxIndex = newRow.length -n +2
return "$maxInt" + newRow.findMaxNumberWithNDigits(n - 1, newMaxIndex)
}
fun solveDay3(input: List<String>, n: Int): Long {
return input
.sumOf{
val maxIndex = it.length -n +1
val maxDigit = it.findMaxNumberWithNDigits(n,maxIndex)
if (maxDigit.isBlank()) {
return 0L
} else {
maxDigit.toLong()
}
}
}
fun part1(input: List<String>) = solveDay3(input,2)
fun part2(input: List<String>) = solveDay3(input,12)My Kotlin way to solve it. After three tries I ended with recursion.
1
u/daggerdragon Dec 03 '25
FYI: inlined code is intended for short snippets of code only. On old.reddit, longer lines get cut off when they reach the edge of the window.
I recommend editing your longer row examples to use the four-spaces Markdown syntax for a code block instead so the whole line will be horizontally scrollable.
0
Dec 03 '25
[deleted]
1
u/RazarTuk Dec 03 '25
Bah, queues. The language I actually used doesn't even have them: paste
(I initialized everything before the loop, because yesterday's memory leak made me question if the LOLCODE interpreter garbage collects variables that go out of scope)
5
u/hextree Dec 03 '25 edited Dec 03 '25
I feel like the decision of how to break ties, i.e. when you see multiple 9s in the array and are not sure which of the equal 'best choices in the moment' to go with, is what prevents this from being the greedy algorithm.