Autum Challenge: Short Deadfish Numbers

General
20

Planning is a big word. You can view the problem as a graph
problem. You have a graph with vertices 1…255 or even more,
and the edges are labeled with “i”, “d” and “s”.

The problem can now be cast as:

  • For each number n in the range 1…255 find the
    shortest path back to zero.

I am pretty sure you can massively bring down the 1.8 seconds
if you look up one of the shortest path algorithms that are around,
and even have some Prolog realization.

If there is also a “o” step then the vertices are pairs if numbes,
the output so far and the accumulator. In an other forum post
for shortest path something like mode directed tabling:

%:- table(path(_, _, _, min)).

Find the shortest path in between nodes
https://swi-prolog.discourse.group/t/find-the-shortest-path-in-between-nodes/2315/4

Was suggested. So SWI-Prolog should have everything, yes or no?
I don’t know why @jamesnvc didn’t stick to tabling and then used
order_by. tabling would sure have the advantage that

it computes all solution together, as is required for this problem.

Edit 07.10.2023
The SWI-Prolog mode directed tabling lists this generic algorithm:

:- table
    connection(_,_,lattice(shortest/3)).

shortest(P1, P2, P):-
    length(P1, L1),
    length(P2, L2),
    (   L1 < L2
    ->  P = P1
    ;   P = P2
    ).

connection(X, Y, [X,Y]) :-
    connection(X, Y).
connection(X, Y, P) :-
    connection(X, Z, P0),
    connection(Z, Y),
    append(P0, [Y], P).

But maybe we can get rid of the append?