Skip to content

Instantly share code, notes, and snippets.

@mwilliamson

mwilliamson/gist:7378428

Last active Dec 27, 2015
Embed
What would you like to do?
Different ways of implementing run-length encoding in Prolog. Only encode3 seems to work both ways (encoding and decoding) with large inputs, but has the disadvantage that inefficient encodings are listed first.
encode([], []).
encode([X|XT], [[Count, X] | RestEncoded]) :-
consume([X|XT], X, Count, Rest),
encode(Rest, RestEncoded).
consume([], _, 0, []).
consume([X|XT], X, Count, Rest) :-
consume(XT, X, SubCount, Rest),
succ(SubCount, Count).
consume([X|XT], Y, 0, [X|XT]) :- X \= Y.
encode2([], []).
encode2([X], [[1, X]]).
encode2([X|XT], [[Count, X]|RestEncoded]) :-
encode2(XT, [[SubCount, X]|RestEncoded]),
succ(SubCount, Count).
encode2([X|XT], [[1, X], [SubCount, Y] | RestEncoded]) :-
encode2(XT, [[SubCount, Y]|RestEncoded]),
X \= Y.
encode3([], []).
encode3(XS, [E|ES]) :-
append(XLeft, XRight, XS),
XLeft \= [],
expand(XLeft, E),
encode3(XRight, ES).
expand([X|XT], [Count, X]) :- expand(XT, [SubCount, X]), succ(SubCount, Count).
expand([], [0, _]).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment