99 problems - pack a list

156 views
Skip to first unread message

Terrence Brannon

unread,
Jun 1, 2010, 4:57:11 PM6/1/10
to
My pack program is almost correct, except it does not handle the final
list in the input correctly. I would appreciate some input on how to
fix my problem:

%% https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/
%% Pack consecutive duplicates of list elements into sublists.
%% If a list contains repeated elements they should be placed in
separate sublists.
%% Example:
%% ?- pack([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
%% X = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]]

% pack $INPUTLIST into $OUTPUTLIST

pack([], []).
pack([X], [[X]]).

pack([X,X|Zs], [[X,X|AllX] |NewPack]) :- packAll(X, Zs, AllX, Rest),
pack(Rest, NewPack).
pack([X,Y|Zs], [[X],[Y|AllY]|NewPack]) :- packAll(Y, Zs, AllY, Rest),
pack(Rest, NewPack).


% packAll $X from $LIST into $OUTPUT and any non-X goes into $NEWPACK

packAll(X, [], [], []).
packAll(X, [X|Zs], [X|Xp], NewPack) :- packAll(X, Zs , Xp, NewPack).
packAll(X, [Y|Zs], [], [Y|Zs]).

Pascal J. Bourguignon

unread,
Jun 1, 2010, 6:28:34 PM6/1/10
to
Terrence Brannon <meta...@gmail.com> writes:

> My pack program is almost correct, except it does not handle the final
> list in the input correctly. I would appreciate some input on how to
> fix my problem:
>
> %% https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/
> %% Pack consecutive duplicates of list elements into sublists.
> %% If a list contains repeated elements they should be placed in
> separate sublists.
> %% Example:
> %% ?- pack([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
> %% X = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]]
>
> % pack $INPUTLIST into $OUTPUTLIST

You need to add calls to dif(X,Y) to ensure that X and Y do not unify,
in both pack and packAll:


> pack([], []).
> pack([X], [[X]]).
>
> pack([X,X|Zs], [[X,X|AllX] |NewPack]) :- packAll(X, Zs, AllX, Rest),
> pack(Rest, NewPack).
> pack([X,Y|Zs], [[X],[Y|AllY]|NewPack]) :-

dif(X,Y),

> packAll(Y, Zs, AllY, Rest),
> pack(Rest, NewPack).
>
> % packAll $X from $LIST into $OUTPUT and any non-X goes into $NEWPACK
>
> packAll(X, [], [], []).
> packAll(X, [X|Zs], [X|Xp], NewPack) :- packAll(X, Zs , Xp, NewPack).

> packAll(X, [Y|Zs], [], [Y|Zs]) :-

dif(X,Y).


?- pack([a,a,a,a,b,b,b,a,a,a,c,d,d,d,e,e,e,e,e],X),print(X).
[[a, a, a, a], [b, b, b], [a, a, a], [c], [d, d, d], [e, e, e, e, e]]
X = [[a, a, a, a], [b, b, b], [a, a, a], [c], [d, d, d], [e, e, e|...]] ;
false.

Here is how I would do it:

packRuns([],[]).

packRuns([X],[[X]]).

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


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

run(Var,[Var|LRest],[Var|VRest],RRest):-
run(Var,LRest,VRest,RRest).

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

?- packRuns([a,a,a,a,b,b,b,a,a,a,c,d,d,d,e,e,e,e,e],X),print(X).
[[a, a, a, a], [b, b, b], [a, a, a], [c], [d, d, d], [e, e, e, e, e]]
X = [[a, a, a, a], [b, b, b], [a, a, a], [c], [d, d, d], [e, e, e|...]] ;
false.

--
__Pascal Bourguignon__ http://www.informatimago.com/

Mats Carlsson

unread,
Jun 2, 2010, 8:30:08 AM6/2/10
to
On Jun 1, 10:57 pm, Terrence Brannon <metap...@gmail.com> wrote:
> My pack program is almost correct, except it does not handle the final
> list in the input correctly. I would appreciate some input on how to
> fix my problem:
>
> %%https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/

> %% Pack consecutive duplicates of list elements into sublists.
> %%    If a list contains repeated elements they should be placed in
> separate sublists.
> %%    Example:
> %%    ?- pack([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
> %%    X = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]]

Here is how I would do it:

:- use_module(library(lists), [keyclumped/2]).

pack(List, Packed) :-
( foreach(X,List),
foreach(X-X,Tagged)
do true
),
keyclumped(Tagged, Keyclumped),
( foreach(_-Clump,Keyclumped),
foreach(Clump,Packed)
do true
).

Paulo Moura

unread,
Jun 2, 2010, 9:15:42 AM6/2/10
to
On Jun 1, 9:57 pm, Terrence Brannon <metap...@gmail.com> wrote:
> My pack program is almost correct, except it does not handle the final
> list in the input correctly. I would appreciate some input on how to
> fix my problem:
> ...

How about:

pack([], []).
pack([X], [[X]]).

pack([X, X| L], [[X| Xs]| R]) :-
pack([X| L], [Xs| R]).
pack([X, Y| L], [[X]| R]) :-
X \= Y,
pack([Y| L], R).

This solution assumes that the original list contains no variables. On
the other hand, it will run on any Prolog compiler, as it doesn't
depend on proprietary predicates (such as dif/2 or do/2), which seems
more fit for someone learning Prolog programming.

Cheers,

Paulo

Bart Demoen

unread,
Jun 2, 2010, 9:49:04 AM6/2/10
to
On Wed, 02 Jun 2010 06:15:42 -0700, Paulo Moura wrote:


> How about:
>
> pack([], []).
> pack([X], [[X]]).
> pack([X, X| L], [[X| Xs]| R]) :-
> pack([X| L], [Xs| R]).
> pack([X, Y| L], [[X]| R]) :-
> X \= Y,
> pack([Y| L], R).

Just for fun ... how about


pack([],[]).
pack([X|R],Out) :-
pack(R,ROut),
(ROut = [[X|A]|B] ->
Out = [[X,X|A]|B]
;
Out = [[X]|ROut]
).

Cheers

Bart Demoen

Terrence Brannon

unread,
Jun 2, 2010, 9:56:37 AM6/2/10
to
On Jun 1, 6:28 pm, p...@informatimago.com (Pascal J. Bourguignon)
wrote:

>
> You need to add calls to dif(X,Y) to ensure that X and Y do not unify,
> in both pack and packAll:

Actually I do not. Because the first clause requires that they are
equal, the second clause will only fire when they fail to be equal.

My problem was misreading the output [e,e,e|...] as being non-
terminating when it wasnt.

But thanks for the input... also note X \= Y is another way to check
for non-equality.

Bart Demoen

unread,
Jun 3, 2010, 3:21:17 AM6/3/10
to
On Wed, 02 Jun 2010 06:56:37 -0700, Terrence Brannon wrote:

> On Jun 1, 6:28 pm, p...@informatimago.com (Pascal J. Bourguignon) wrote:
>
>
>> You need to add calls to dif(X,Y) to ensure that X and Y do not unify,
>> in both pack and packAll:
>
> Actually I do not. Because the first clause requires that they are
> equal, the second clause will only fire when they fail to be equal.

On backtracking the last clause will "fire" even if X and Y do unify.
So the \= is needed, unless you prevent backtracking in some other way.
That gives rise to extra and incorrect solutions to the query.

Cheers

Bart Demoen

Reply all
Reply to author
Forward
0 new messages