Defeated!

I did in fact implement Quicksort in Dusa (sloppy unorganized code on dusa.rocks here), actually I think I correctly implemented it in two different ways, but I ran into performance issues when I ventured that far out of the tested use cases of this language.

Defining a comparison operation in Dusa

However, while still quite sluggish, I was able to get by with only moving the “sort a list” logic out into JavaScript, in a way that is on its own interesting and pleasing:

const hands = INPUT.map((_, hand) => BigInt(hand));
hands.sort((hand1, hand2) => {
  dusa.assert({ name: 'needWinner', args: [hand1, hand2] });
  const winner = [...dusa.solution.lookup('winner', hand1, hand2)][0][0];
  return winner === hand1 ? 1 : winner === hand2 ? -1 : 0;
});

So what is happening here is that the hands are all indexed in Dusa with their original line numbers, integers in [0…length), so the array hands = [0,1,2,3,…] acts as an array of all the hands, and I can sort that array with a custom sort.

That custom sort makes very pleasing use of demand-driven computation in Dusa: it adds the fact needWinner H1 H2, for some specific H1 and H2, which will cause Dusa to derive either winner H1 H2 is H1 or winner H1 H2 is H2, so the comparison function can immediately query that fact. lt X Y is the transitive closure of the “strength” both for cards and hand types — ”3” is less than (weaker than) “9”, and twoPair is less than (weaker than) fullHouse.

**winner H1 H2 is H1 :-
    needWinner H1 H2,
    type H1 is X,
    type H2 is Y, lt Y X.
winner H1 H2 is H2 :-
    needWinner H1 H2,
    type H1 is X,
    type H2 is Y, lt X Y.
needTiedWinner H1 H2 0 :-
    needWinner H1 H2,
    type H1 is X,
    type H2 is X.
winner H1 H2 is H1 :-
    needTiedWinner H1 H2 N,
    hand H1 N is X,
    hand H2 N is Y,
    lt Y X.
winner H1 H2 is H2 :-
    needTiedWinner H1 H2 N,
    hand H1 N is X,
    hand H2 N is Y,
    lt X Y.
needTiedWinner H1 H2 (plus N 1) :-
    needTiedWinner H1 H2 N,
    hand H1 N is X,
    hand H2 N is X.**

I think this is a pretty straightforward and pleasing calculation, though it involves a bit of repeating onesself. The computation of what type a hand is (highCard, twoOfAKind, threeOfAKind, etc…) is comparatively verbose and messy in my opinion especailly, but after some struggles with having non-mutually-exclusive-type computations (so I’d derive a hand as both fullHouse and threeOfAKind) it worked… alright.

After computing the ranks from the sorted list, I still used Dusa to add up the values to get the ultimate answer.

Code

DISCLAIMER: I needed to add an optimization that isn’t present in Dusa 0.0.10 in order for this to work in a reasonable amount of time for the full solution.

Part 1 (partial) on dusa.rocks

Part 2 (partial) on dusa.rocks

Both parts on StackBlitz

Notes

I really need to implement “if a value conflict is derived on this predicate, it’s actually an error and you should raise an exception” (#19)