How to shift elements to the left as much as possible? Prolog

user_1420056 0
Viewed 134

Suppose I have a list with 4 elements [0,4,0,2] (Can be any arrangement). Each element in the list will move towards left. If an elements neighbor is zero so it can easily move towards the left. If the neighbor is a non zero number then it can not move towards left. (Example: [8,0,2,3] will become [8,2,3,0], and [0,4,0,2] will become [4,2,0,0])

Here is my current attempt:

shift_left([],_):-!.
shift_left([H1,H2|T],S):-
    H1=0,
    append(S,[H2|T],L1),
    write(L1),
    shift_left([H2|T],_).
shift_left([H1|T],_):-
    H1\=0,
    shift_left(T,[H1]).

My second attempt after looking at CapelliC's answer. It works great.

shift_left([],[]).
shift_left([H|T],S):-
    shift_left(T,Q),
    H=0,
    append(Q,[0],S).
shift_left([H|T],S):-
    shift_left(T,Q),
    H\=0,
    S=[H|Q].
prolog
3 Answers

This is a simpler solution - in the sense it's less technical - wrt Willem' answer, and make use of append/3, as your original code

shift_left([],[]).
shift_left([H|T],S):-
    shift_left(T,Q),
    (   H=0
    ->  append(Q,[0],S)
    ;   S=[H|Q]
    ).

test

?- maplist(shift_left,[[8,0,2,3],[0,4,0,2]],Ss).
Ss = [[8, 2, 3, 0], [4, 2, 0, 0]].
user_8740240

We can enumerate over the list, and each time we see a zero, we can push it on the list of elements to emit later when we reach the end of the list:

shift_left(L, R) :-
    shift_left(L, [], R).

shift_left([], Zs, Zs).
shift_left([H|T], Zs, [H|R]) :-
    dif(H, 0),
    shift_left(T, Zs, R).
shift_left([0|T], Zs, R) :-
    shift_left(T, [0|Zs], R).

This then give us:

?- shift_left([8,0,2,3], R).
R = [8, 2, 3, 0] ;
false.

?- shift_left([0,4,0,2], R).
R = [4, 2, 0, 0] ;
false.
user_675790

This is a more technical solution. It is basically the same as this answer but uses library predicates and does one extra traversal of the Not Zeros.

bubble_up_zeros(List, Result) :-
    partition(not_zero, List, Not_zeros, Zeros),
    append(Not_zeros, Zeros, Result).

not_zero(X) :- dif(X, 0).
user_144119970
Related