<aside> đź’¬ Comment on Mastodon!
</aside>
The Advent of Code 2023 Day 1 challenge is to find the first and last digits in a series of strings, treat them as a two-digit number, and add all those two-digit numbers up.
Dusa is not really the best programming language to do this kind of task in — I wouldn’t recommend it for this purpose — but it’s an interesting exercise to see what it does well and not-so-well.
I used new JSON import features I still need to document to do the full solution, but for purposes of explaining the solution I am going to assume I’ve already exploded everything into val Line Col is Char facts, so the first test line “1abc2” is represented as:
**val 0 0 is "1".
val 0 1 is "a".
val 0 2 is "b".
val 0 3 is "c".
val 0 4 is "2".**
Some simple builtins:
**#builtin INT_MINUS minus
#builtin INT_PLUS plus
#builtin STRING_CONCAT concat**
It’s easy to say what characters are digits:
**digit "0" is 0.
digit "1" is 1.
digit "2" is 2.
digit "3" is 3.
digit "4" is 4.
digit "5" is 5.
digit "6" is 6.
digit "7" is 7.
digit "8" is 8.
digit "9" is 9.**
BUT! I need to know not just whether a thing is a digit, some of my logic is going to depend on what characters AREN’T digits. It’s easy to figure out all of the characters I care about: if I have a val _ _ is Ch then that’s a character I need to know the digit-ness of, and I don’t care about any other digitness.
In stratified Datalog, this would be no problem, I could just use negation and !digit Ch straightforwardly. But Dusa doesn’t have stratified negation at present, and I’m not sure it needs it because of the ASP-derived trick I can use instead.
The “defaults pattern” is to say that, for every character I care about, isDigit Ch is potentially false, but then also derive isDigit Ch is true for every digit character. Dusa derives positive facts first, so it’ll end up deriving isDight Ch is false only after it’s derived all the isDigit Ch is true facts it possibly can.
**isDigit Ch is { false? } :-
val _ _ is Ch.
isDigit Ch is true :-
digit Ch is _.**
Here I used a pure-datalog strategy: I derive facts findFirst Line Col to represent the fact that “I want to find the first digit on line Line, and that first fact does not occur before position Col.
By this definition, the fact findFirst Line 0 is automatically true for every line that exists.