Oh my goodness, I did it. What a day!
I spent the entire day to solve "Playground" - Day 8 of AdventOfCode in #TurboPascal on the #Xi8088 and I had a blast!
I got all the logic right on first try for both parts, but the big question was: How do you sort up to a million entries on a machine that can't even store ten times less in memory, in a language where your arrays are less than 64KiB ? 🤯
Obvious answer is "you don't", but then what? 😅
So happy!
The answer is: when you can't keep all your results in memory, work with the subset you need, then recompute things, to get the next subset, and so on.
Part 1 was all fine, I used an array of 1000 junctions, and did an insertion sort, keeping only the 1000 smallest lengths.
For part 2, I re-computed all the lengths, and inserted in my array only the smallest 1000 that were larger than the previous ones. Then did it again, until the net was complete.
Funny thing is, I played with various sizes for the array of junctions for part 2.
A smaller array means quicker insertions (less data to move around) but calculating all the lengths more times.
With a larger array, we loop fewer times through the lengths computations, but insertions become more and more expensive.
The sweet spot appears to be applying sets of 1000 connections at a time, the same amount than required for part 1.
@root42 Probably, yes. Although running a sort over so many EMS pages could prove... fun 😅
But alas, I don't have an EMS expansion board. And I would need at least a 12MB one!
@root42 @alrj
For over 40 years a have the same problem: sorting data that doesn't fit in the RAM. I used a similar technique called multipled tape sorting with 3 sequential files: two for input, internal sorting and one for out (Multiway Merging).
Donald E Knuth explained in the third Volume of The Art of Computer Programming in Section 5.4 many algorithms for sorting with low memory. The term called "External Sorting".
see also
https://en.wikipedia.org/wiki/External_sorting
Amand Tihon
root42
Uwe Brinkhoff
Kata 📎
Sasha