Short Deadfish Challenge

[aarroyoc]

I came across this challenge

I copy-paste:

Deadfish is one of the best known non Turing-complete programming languages.
It has only one accumulator (which starts at 0) to store data, and only four commands:

i - Increment the accumulator
s - Square the accumulator
d - Decrement the accumulator
o - Output the accumulator

Create a program that will input a number and output the shortest Deadfish
code to display the number. It must work for any integer from 0 to 255.

On the answers I'll post my answer, which I surely know some people would improve!

[aarroyoc]

Naive version. It doesn't create the shortest code because it just outputs one time at the end:

:- use_module(library(clpz)).
:- use_module(library(dcgs)).
:- use_module(library(lists)).

% Increment the accumulator
ops(i, X0, X) :-
    X #= X0 + 1.

% Square the accumulator
ops(s, X0, X) :-
    X #= X0 * X0.

% Decrement the accumulator
ops(d, X0, X) :-
    X #= X0 - 1.

deadfish(N, Code) :-
    length(Code, _),
    phrase(deadfish_(0, N), Code).

deadfish_(X, X) --> [o]. % Output always at the end
deadfish_(X0, X) -->
    { ops(Op, X0, X1) },
    [Op],
    deadfish_(X1, X).

[aarroyoc]

My current version. It does the shortest Deadfish program. It also does some checks to reduce the number of iterations. I use freeze/2 to allow bidirectional work (also execute code) but it adds a significant overhead. I tried tabling on deadfish/3 but it didn't improve:

:- use_module(library(clpz)).
:- use_module(library(lists)).
:- use_module(library(dif)).
:- use_module(library(freeze)).

% Increment the accumulator
ops(i, X0, X, S, S) :-
    X0 #< 255,
    X #= X0 + 1.

% Square the accumulator
ops(s, X0, X, S, S) :-
    X0 #< 16,
    X #= X0 * X0.

% Decrement the accumulator
ops(d, X0, X, S, S) :-
    X0 #> 0,
    X #= X0 - 1.

% Output the accumulator
ops(o, X, X, Screen0, Screen) :-
    dif(Str, ""),
    append(Screen0, Str, Screen),
    freeze(X, number_chars(X, Str)).

deadfish(Str, Code) :-
    length(Code, _),
    deadfish(_, Str, Code).

deadfish(0, "", []).
deadfish(N, Str, Code) :-
    ops(Op, N0, N, Str0, Str),
    append(Code0, [Op], Code),
    restrict_code(Code0, Op),
    deadfish(N0, Str0, Code0).

restrict_code([], _).
restrict_code(Code, o) :- append(_, [_], Code).
restrict_code(Code, s) :- append(_, [_], Code).
restrict_code(Code, d) :- member(Op, [s, o, d]), append(_, [Op], Code).
restrict_code(Code, i) :- member(Op, [s, o, i]), append(_, [Op], Code). 

[triska]

Very interesting, thank you a lot for sharing this!

One small thing I noticed regarding:

restrict_code(Code, d) :- member(Op, "sod"), append(_, [Op], Code).

With "sod" being so short, it may be worth considering writing this as:

restrict_code(Code, d) :- append(_, [Op], Code), member(Op, "sod").

In this way, the last element Op has only to be derived once, instead of 3 times repeatedly on backtracking over "sod".

As a small test, I get:

?- length(Ls, 1_000_000),
   time((restrict_code(Ls,d),false)).
   % CPU time: 1.503s
   false.

vs.:

?- length(Ls, 1_000_000),
   time((restrict_code(Ls,d),false)).
   % CPU time: 0.504s
   false.

So, indeed the expected speedup of roughly 3 times. Chances are it won't matter much in this use case, but it's maybe still worth considering.