# AoC '23 1B

## Problem

This problem is similar to problem 1A. We have this big list of numbers:

```
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
```

Each group is separated by the blank line. But now, instead of the sum of all the numbers in the *largest* group, we are asked to find the sum of the largest 3 groups.

## Initial Approach

This complicates our cumsum approach from part 1 (devious puzzle makers), because rather than having a single variable, we will need 3 variables if we want to keep our top 3 elves. We also need lots of comparison logic to make sure we shuffle the top 3 around as we build the list. This might be tractable for our top 3 elves, but it becomes brutal quickly for our top *k* elves

My first intuition for this problem is to reach for something like bisect here. Rather than maintaining a single variable and considering whether the current sum is greater than it (like we did in part 1, we will maintain a list of calorie sums; when we are finished summing the current set of calories, we’ll bisect our existing list to determine where to insert the current sum before moving onto the next one.

We can maintain the sort order of the list as we build it instead of re-sorting on each insert, which is expensive. Then, once we are finished building the sorted list, we can simply take the last three items (or last *k* items) to obtain the top three calorie counts.

I keep saying “*list*” here, because I come from Pythonland where *list* means like… wait, what the heck is a *list* in Python anyway? _{Is this why Python is slow?}

In order to perform all of this bisection and insertion efficiently, we will need a datastructure that will balance both. Rather than an array, I’m reaching for a binary search tree for this one. This is probably not necessary (I can definitely just use some built-in sorting) but I think it will be fun, and I’ve heard that whiteboard binary tree questions were common Google interview question 15 years ago.

With Rust’s more assiduous approach to memory management this should be a fun exercise.

Our initial approach looks like this:

```
def topThreeElves(file):
elf_packs: new Btree
current_pack: new Bnode
for snack in file:
if l is "\n":
insert(elf_packs, current_pack)
current_pack = new Bnode
else:
current_pack.store(snack)
current_pack.sum += snack
calorie_sums = elf_packs.traverse_in_order()
top_three = calorie_sums[-3:]
return topThree
```

I won’t go through Binary Trees here – there are much better guides out here.

See binary search tree – insertion for more details.