[2024 Day 5] In Review (Print Queue)

[u/terje_wiig_mathisen]

The story this day is that we need to print a bunch of manuals, all consisting of a small number of pages from a master list, but there are also lots of rules about the printing order between pairs of pages, stating that if <N> and <M> are part of the same manual, N must always be printed before M.

Before the list of manuals to print we have a long list of these rules.

We know that for any given manual with its list of pages, these rules lead to a single unique legal ordering.

However, it is both possible according to the rules, and as far I know, also true that:

There exist at least one ring of rules (A<B, B<C,...X<Y,Y<Z, Z<A), which means that there cannot be any complete ordering of all the pages, so the order has to be determined for each set of manual pages, otherwise we could just have sorted the page numbers once and be done with it.

In Perl it felt natural to store these rules as hashes, each possible page number from 1 to 99 gets a list of the pages it must be before or after.

The code ran in 5.5 ms so fast enough for an interpreted language.

In my Rust version I noticed that 100 pages is less than 128 so I stored those lists as u128 bitmaps, this allowed all the checks to be done with logic AND operations.

For Part1 just iterate over the pages:

    fn is_ordered(&self, pagelist:&Vec<u8>) -> bool {
        let mut prev = pagelist[0];
        for p in 1..pagelist.len() {
            let curr = pagelist[p];
            if self.pages[prev as usize].infront & (1 << curr) != 0 {
                return false;
            }
            prev = curr;
        }
        true

If there is no rule for prev vs curr then that implies any ordering is OK for that pair of pages.

Part2 is a little bit (grin) more complicated, but the same bitmap logic determines which page must be first, second, third etc.

I start by generating a pagelist bitmap, with 1 bits for each page in that particular list, then I iterate over the pages, from the end forwards, until I find a page that has no other pages behind it (i.e., its "behind" bitmap ANDed with the pagelist bitmap is zero).

This page can then be exchanged with the original last page. After placing it, I remove it from the pagelist bitmap, step forward one position and repeat the process until all pages are ordered.

Total runtime was 10.867 us (average over 1000 runs) vs the 18 us given by u/maneatingape, so more than fast enough for me.

(While writing this I realized that I only needed one of the two bitmaps per page, that would have saved a little bit of the setup time, as well as 1600 bytes of memory, but since the total working set is less than 4kB, everything fits easily in $L1 cache.

I thought this was an interesting puzzle, with some similarities to classic problems like managing free space in a file system using bitmaps.

PS. I am posting this just before 0100 Oslo time on Oct 5th, I'll keep the tradition going as long as I can or until u/musifter returns!

[u/ednl]

What we need is an overloaded "smaller than" operator! I did that more or less like so:

bool before[100][100];  // fill from parsing first part of input
bool smaller(int a, int b) {  // function to replace operator
    return before[a][b];
}
if (smaller(page[i], page[i - 1])
    // out of order, do part 2 here

A helpful insight was that you don't need to check every pair in the reports because a) "smaller than" is transitive: if x<y and y<z then x<z, and b) if there is a middle element then the rules have to be complete and consistent and there can't be any loops. Technically there could be smaller loops before or after not including the middle element, but that doesn't happen in any input, I think.

I got about the same time as /u/maneatingape because my program was essentially the same. But I had highly specialised parsing, so why was it not faster? Turns out the "k'th smallest" or Quickselect algorithm makes all the difference. It's the same as QuickSort but doesn't sort the whole list, only the part with the requested index. On average, that should take about half the time, I think. I'm sure the library version of QuickSort (and k'th-smallest, if your library has that) has some safeguard checks and a strategy for picking a good pivot while I don't do any of that in my custom implementation; another few µs gained. Timing: M4 4.46 µs, M1 6.44 µs, Pi5 16.4 µs. Source code in C

[u/terje_wiig_mathisen → u/ednl]

u/ednl I do of course know about the k'th element algorithm and how it is related to quick sort pivot operations: You only iterate over the partition which must contain the target.

However, when I implemented my own quicksort() function 40 years ago, I also tested out the break-even point between deeper recursion (on the smaller partition only, with the larger handled with looping) and switching to something else like selection sort (which is basically what my Rust code uses), and found that anywhere between 4 and 10 remaining elements were more or less the same.

In my input the number of pages vary between 5 and around 20, so I did not see a critical need for a pivot based search, but I guess I'll have to try it just to verify!

EDIT: Quickselect or k'th element is not just twice as fast, it is O(n) instead of O(n*log(n)), at least for randomly-ordered inputs, since there is just a single path through 1 + 1/2 + 1/4 + ... parts of the input. The sum of that series is 2, so not dependent on N.

[u/ednl → u/terje_wiig_mathisen]

On the M4, I went from 12 to 4.5 µs after switching from the C standard library's qsort to my own Quickselect. It probably also helped that I don't pass a custom comparison function but just straight up inserted the rule array:

static int partition(int *const arr, const int left, const int right)
{
    const int pivot = arr[right];
    int pivix = left;
    for (int i = left; i < right; ++i)
        if (rule[ arr[i] ][pivot])  // order by the rules
            swap(&arr[pivix++], &arr[i]);
    swap(&arr[pivix], &arr[right]);
    return pivix;
}

Maybe more importantly: the stdlib qsort doesn't seem to be very performant for small AoC tasks.

Yes I saw the O(n) vs. O(n log n), I linked to the wikipedia page after all which I wouldn't do without reading it. I still think "about twice as fast" is a good first guess for small arrays.

[u/terje_wiig_mathisen → u/ednl]

I did not consider using Rust sort() or sort_unstable() with a custom comparator function,

I always wanted to write as much of the solution myself as possible, but your timings means that I have to try to implement the pivot select algorithm.

[u/ednl → u/terje_wiig_mathisen]

I did not consider using Rust sort() or sort_unstable() with a custom comparator function,

Oh? Isn't that the only way to use a standard sort function? How else would you have it use the custom order from the rule set? For the C stdlib qsort you have to supply a comparator function always: https://cppreference.com/c/algorithm/qsort

[u/terje_wiig_mathisen → u/ednl]

Sorry, that was not clear: Since the number of elements in each manual was so low I expected an inline selection sort algorithm to be faster than a sort like the C qsort which needs a function call per comparison. However, thinking about it now, Rust sort_unstable() has no explicit compare function, the compiler will instead synthesize Ord/PartialOrd based on the Vec<> element type, so it is possible that the overhead is much less.

EDIT: My first attempt to write a median() function using pivots, on the Surface, seems to improve the time a little, but still far from your benchmark.

[u/musifter]

I remember trying a topological sort (probably just tsort) on the input and discovering it wasn't a DAG. But you don't need a non-transitive relation when writing a comparator function for a sort (although it could throw your sort into an infinite loop (or produce a randomish order if the algorithm is robust against that)... but we're given that these can be sorted, so it won't).

For this one, just putting the values in a set and testing for existence was a good for a comparator for Smalltalk (which wants it to return boolean). Perl comparators want a number (neg/0/pos). And so I threw the input into a hash (using $; = '|' to make that the separator) with the values equal to -1. Then the sort block is just {$order{$a,$b} // 1} .

[u/e_blake]

My m4 runtime was 145ms with a full-blown O(n²) insertion sort (with a max n of 23, this wasn't too bad). I'd love to have time to revisit this to do quickselect, since that averages O(n) on sufficiently random pivots. I also did not notice the loop in the overall ordering until reading the megathread, because I just focused on the relations needed per line.

It is interesting that quickselect is still worst case O(n²) on adversarial inputs, unless you use the deterministic median-of-median approach of dividing the work into groups of 5 . But n in this puzzle is so small that there aren't many groups of 5, and the median of median approach has much more overhead, where you need several thousand elements before the deterministic but high overhead algorithm can start to overtake the simpler but degraded worst case algorithms.

I did golf this one to 472 bytes but 20 second runtime:

eval(translit(_(include(I)00),define(_,`ifelse(k,`k',`define(k,$1)_(2,(,substr(
k,5880)),,_(^$@))',$2,(,0),`) eval(',$1,2,`_(len($5),_(~,$3,$4,_$2),_(*,$@))',
$1,4,`_(%,_(&,_(~,$3,eval($4/100),_$2))eval($4%100),_(*,$@))',$1,~,`(,_($,$2,
index(k,$4|$3),_(_(^$@)))',$1$5,$,`$4),1',$1$3,$-1,`$5,_($,1,index(k,$6|$4),$4,
_(_(*,$@)))',$1,$,`_(*,,$@)),$2',$1,&,`0$3*substr($2,eval(len($2)/2),3)',$1,%,
`+!$2_(2,(,$3),,_(*,,$@))+$2',$1,*,`_(_(_(^_(^_(^$@)))))',`shift($@)')')
))

[u/terje_wiig_mathisen → u/e_blake]

Interestingly enough, I did not actually verify that there was a loop (loops?) in the rules, my naturally suspicious mind just read the description and decided that it would be too easy if the input defined a total order. :-)

[u/DelightfulCodeWeasel]

The cycle in the ordering for the full rule set was an interesting wrinkle for an early day puzzle, and one that I completely bypassed due to sheer chance. I was still very much in programmer-see-programmer-do mode for this one: find the first page out of order, put it after the last page it's supposed to be after, repeat until no pages are out of order.

Going onto the forum I saw a lot of people talking about struggling with ordering the full rule set, and my immediate thought was "oh yes, that would have been a smarter way to tackle it". Followed up later, after finding mention of the cycle, by being grateful that by picking the 'dumb' option I'd completely avoided the rake in the grass :)

[u/ednl → u/DelightfulCodeWeasel]

Oh ha, I didn't even remember the cycle in the full rule set until now. Yeah apart from avoiding that problem by the way you (and I) implemented the sort, there is also the fact that the rules only apply to a small, carefully picked subset of the numbers for each "report". So for each individual report, there is no loop or else there could never be a middle element.

[u/Boojum → u/DelightfulCodeWeasel]

Yes, that one bit me! I had assumed, this being a book (or manual), that there would be a total ordering on the pages. So my idea had been that I could solve for that up front with a topological sort on all the pages, and then each of the manuals would just be the order-preserving subset of that. Nope!