How to resolve the algorithm Look-and-say sequence step by step in the Prolog programming language

Published on 12 May 2024 09:40 PM
#Prolog

How to resolve the algorithm Look-and-say sequence step by step in the Prolog programming language

Table of Contents

Problem Statement

The   Look and say sequence   is a recursively defined sequence of numbers studied most notably by   John Conway.

The   look-and-say sequence   is also known as the   Morris Number Sequence,   after cryptographer Robert Morris,   and the puzzle   What is the next number in the sequence 1,   11,   21,   1211,   111221?   is sometimes referred to as the Cuckoo's Egg,   from a description of Morris in Clifford Stoll's book   The Cuckoo's Egg.

Sequence Definition

An example:

Write a program to generate successive members of the look-and-say sequence.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Look-and-say sequence step by step in the Prolog programming language

Source code in the prolog programming language

look_and_say(L) :-
	maplist(write, L), nl,
	encode(L, L1),
	look_and_say(L1).

% This code is almost identical to the code of "run-length-encoding" 
encode(In, Out) :-
	packList(In, R1),
	append(R1,Out).


% use of library clpfd allows packList(?In, ?Out) to works
% in both ways In --> Out and In <-- Out.

:- use_module(library(clpfd)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% ?- packList([a,a,a,b,c,c,c,d,d,e], L).
%  L = [[3,a],[1,b],[3,c],[2,d],[1,e]] .
% ?- packList(R,  [[3,a],[1,b],[3,c],[2,d],[1,e]]).
% R = [a,a,a,b,c,c,c,d,d,e] .
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
packList([],[]).

packList([X],[[1,X]]) :- !.


packList([X|Rest],[XRun|Packed]):-
    run(X,Rest, XRun,RRest),
    packList(RRest,Packed).


run(Var,[],[1,Var],[]).

run(Var,[Var|LRest],[N1, Var],RRest):-
    N #> 0,
    N1 #= N + 1,
    run(Var,LRest,[N, Var],RRest).


run(Var,[Other|RRest], [1,Var],[Other|RRest]):-
    dif(Var,Other).

You may also check:How to resolve the algorithm Pentomino tiling step by step in the Picat programming language
You may also check:How to resolve the algorithm Multiplicative order step by step in the ALGOL 68 programming language
You may also check:How to resolve the algorithm Last letter-first letter step by step in the BBC BASIC programming language
You may also check:How to resolve the algorithm Count occurrences of a substring step by step in the PARI/GP programming language
You may also check:How to resolve the algorithm Integer sequence step by step in the DWScript programming language