Day 10, Part 2

[bjrowlett2]

Hey, nice job on 10.2! I think that was the hardest one so far.
Just curious if you get the same results as I do for this input and how long it takes?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

Part 1: 30
Part 2: 53798080

🙂

[dkwgit]

Yup, that's what I got! My solution was not exactly performant for this. It took 10 minutes and guzzled RAM.

[bjrowlett2]

Cool, thanks! I saw some people on the subreddit with the same, fast for the examples and actual input, but slow for all consecutive numbers.

[dkwgit]

Now that I've understood it as a tree, I might have a chance of doing it somewhat like the way you did it. I was trying to get there--I knew it was calculable via combinatorics, but I was adrift. So I went with the tree. Now I could use the tree as a way of figuring out how to correct what was muddled in my thinking about just doing it as tracking permutations. Didn't realize what a performance penalty the tree would impose, but compared to yours there is so much more processing. Lots of node allocation and traversal.

[dkwgit]

@bjrowlett2 Hey, if you feel like it, would you be willing to give Arthur a code for the leaderboard? He's been doing AOC.

[bjrowlett2]

Of course, I'll email it

[dkwgit]

Thanks!