How to merge the elements in a list in a simpler way? Prolog

user_1420056 0
Viewed 160

I am trying to merge the elements in a list, the rules are as follows:

1. Merge a list in a way that if 2 consecutive numbers in a list are a same number they should merge into one by summing them (i.e. [4,4,0,0] -> [8,0,0,0]).

2. A newly merged tile cannot be combined with another tile in the same turn (Example: [4,4,8,0] ->[8,8,0,0] True, but [16,0,0,0] False)

3. List length should be 4. Which adds a zero to the tail if list decreases after merging. (Example: [4,4,0,2] -> [8,0,2,0]).

4. Note in case of zeros: [0,0,2,2] -> [0,4,0,0].

I have been able to create the code, however I want to find a simpler approach explained in detail.

My approach:

merge([H|T],L):-
   merge2([H|T],J),
    (
    length(J,2)->  
    append(J,[0,0],L);
    length(J,3)->  
    append(J,[0],L);length(J,4)-> J=L).

merge2(_,[]).
merge2([X],[X|_]).
merge2([H1,H2|T],[W|L]):-
    H1=H2,
    W is H1+H2,
    merge2(T,L).
merge2([H1,H2|T],[H1|L]):-
    H1\=H2,
    merge2([H2|T],L).
prolog merge list
2 Answers

Length 4 is not long enough to not just write out the cases:

merge( [A,B,C,D], Y) :-
  ( A=B -> ( C=D -> X=[A+B,C+D,0,0] 
                 ;  X=[A+B,C,D,0] )
        ;  ( B=C -> X=[A,B+C,D,0]
                 ;  ( C=D -> X=[A,B,C+D,0]
                          ;  X=[A,B,C,D] ))),
  maplist(is,Y,X).

This just writes out the cases according to your specification. We spare ourselves having to manually call is each time we add two variables by instead writing the sums down symbolically, with +, and call is for each element of the result at once in the end, via maplist.

user_8498910

Here is a solution for arbitrary-length lists and in a single pass without append. (But as a rare occasion for me, with a cut!)

The main predicate dispatches to a helper that counts the number of zeros to add at the end:

merge(List, Merged) :-
    merge(List, 0, Merged).

The important clause of the helper merges two adjacent equal values. It also increments the counter of zeros to be added at the end:

merge([X, X | Xs], ExtraZeros, [Sum | MergedRest]) :-
    !,
    Sum is X + X,
    merge(Xs, s(ExtraZeros), MergedRest).

Otherwise, copy elements until we reach the end of the list:

merge([X | Xs], ExtraZeros, [X | Ys]) :-
    merge(Xs, ExtraZeros, Ys).

At the end of the list, generate zeros as needed:

merge([], ExtraZeros, ZeroList) :-
    length_zerolist(ExtraZeros, ZeroList).

length_zerolist(0, []).
length_zerolist(s(N), [0 | Zeros]) :-
    length_zerolist(N, Zeros).

Tests from the question:

?- merge([4, 4, 0, 0], Merged).
Merged = [8, 0, 0, 0].

?- merge([4, 4, 8, 0], Merged).
Merged = [8, 8, 0, 0].

?- merge([4, 4, 0, 2], Merged).
Merged = [8, 0, 2, 0].

?- merge([0, 0, 2, 2], Merged).
Merged = [0, 4, 0, 0].

A longer list:

?- merge([0, 1, 1, 2, 3, 3, 4, 4, 5], Merged).
Merged = [0, 2, 2, 6, 8, 5, 0, 0, 0].
user_43917430
Related