Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

prolog

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].
like image 555
Reema Q Khan Avatar asked Dec 05 '22 08:12

Reema Q Khan


2 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]].
like image 70
CapelliC Avatar answered Jan 12 '23 05:01

CapelliC


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.
like image 22
Willem Van Onsem Avatar answered Jan 12 '23 06:01

Willem Van Onsem