DEVHIDE
Login Or Sign up

Even and odd cases for the pivot/2 predicate aren't running properly when placed together

161 Views Asked by At

My goal is to implement the pivot(Before,After) predicate that returns true when Before's first half is equal to After's second half and Before's second half is equal to After's first half.

  1. With an even number of elements in input list, the lengths of the two halves are same.
  2. With an odd number of elements, the lengths of the two halves are same with the center element doesn't change.

I tried to implement the predicate and it is working but not perfectly. Below is my predicate.

pivot(Before,After) :-
    append(A,B,Before),
    length(A,N),
    length(B,N),
    append(B,A,After).
pivot(Before,After) :-
    append(A,B,Before),
    length(A,N),
    N1 is N + 1,
    length(B,N1),
    append(C,Tail,B),
    length(C,1),
    append(Tail,C,F),
    append(F,A,After).

The pivot(A,[1,2,3,4,5]) is running, but I do not get output.
I am expecting A = [4,5,3,1,2].

prolog failure-slice
Original Q&A
6

There are 6 best solutions below

4
slago On BEST ANSWER

A possible solution is:

pivot(In, Out) :-
    pivot(In, In, Left, Middle, Right),
    prepend(Middle, Left, New),
    append(Right, New, Out).

pivot([], Ys, [], [], Ys).
pivot([_], [Y|Ys], [], [Y], Ys).
pivot([_,_|Xs], [Y|Ys], [Y|Left], Middle, Right) :-
    pivot(Xs, Ys, Left, Middle, Right).

prepend([], Xs, Xs).
prepend([X], Xs, [X|Xs]).

How does the predicate work?

?- trace(pivot,+all), pivot([1,2,3,4], L), trace(pivot,-all).
%         pivot/2: [all]
%         pivot/5: [all]
 T [11] Call: pivot([1, 2, 3, 4], _15324)
 T [20] Call: pivot([1, 2, 3, 4], [1, 2, 3, 4], _19198, _19200, _19202)
 T [29] Call: pivot([3, 4], [2, 3, 4], _20104, _19200, _19202)
 T [38] Call: pivot([], [3, 4], _21006, _19200, _19202)
 T [38] Exit: pivot([], [3, 4], [], [], [3, 4])
 T [29] Exit: pivot([3, 4], [2, 3, 4], [2], [], [3, 4])
 T [20] Exit: pivot([1, 2, 3, 4], [1, 2, 3, 4], [1, 2], [], [3, 4])
 T [11] Exit: pivot([1, 2, 3, 4], [3, 4, 1, 2])
%         pivot/2: Not tracing
%         pivot/5: Not tracing
L = [3, 4, 1, 2].

?- trace(pivot,+all), pivot([1,2,3,4,5], L), trace(pivot,-all).
%         pivot/2: [all]
%         pivot/5: [all]
 T [11] Call: pivot([1, 2, 3, 4, 5], _27180)
 T [20] Call: pivot([1, 2, 3, 4, 5], [1, 2, 3, 4, 5], _222, _224, _226)
 T [29] Call: pivot([3, 4, 5], [2, 3, 4, 5], _778, _224, _226)
 T [38] Call: pivot([5], [3, 4, 5], _1680, _224, _226)
 T [38] Exit: pivot([5], [3, 4, 5], [], [3], [4, 5])
 T [29] Exit: pivot([3, 4, 5], [2, 3, 4, 5], [2], [3], [4, 5])
 T [20] Exit: pivot([1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2], [3], [4, 5])
 T [11] Exit: pivot([1, 2, 3, 4, 5], [4, 5, 3, 1, 2])
%         pivot/2: Not tracing
%         pivot/5: Not tracing
L = [4, 5, 3, 1, 2].

Another examples:

?- length(In, _), pivot(In, Out).
In = Out, Out = [] ;
In = Out, Out = [_] ;
In = [_A, _B],
Out = [_B, _A] ;
In = [_A, _B, _C],
Out = [_C, _B, _A] ;
In = [_A, _B, _C, _D],
Out = [_C, _D, _A, _B] ;
In = [_A, _B, _C, _D, _E],
Out = [_D, _E, _C, _A, _B] ;
In = [_A, _B, _C, _D, _E, _F],
Out = [_D, _E, _F, _A, _B, _C] ;
In = [_A, _B, _C, _D, _E, _F, _G],
Out = [_E, _F, _G, _D, _A, _B, _C]

A comparison of the various suggested solutions for this problem, using SWI-Prolog 8.4.3.

slago(In, Out) :-
    pivot(In, In, Left, Middle, Right),
    prepend(Middle, Left, New),
    append(Right, New, Out).

pivot([], Ys, [], [], Ys).
pivot([_], [Y|Ys], [], [Y], Ys).
pivot([_,_|Xs], [Y|Ys], [Y|Left], Middle, Right) :-
    pivot(Xs, Ys, Left, Middle, Right).

prepend([], Xs, Xs).
prepend([X], Xs, [X|Xs]).


brebs([A,B|T], LstPivot) :-
    same_length([A,B|T], LstPivot),
    pivot_list_half_([A,B|T], [A,B|T], Half1, Half2),
    append(Half2, Half1, LstPivot).

pivot_list_half_([], H2, [], H2).
pivot_list_half_([_|T], [H|Sgl], H1, H2) :-
    pivot_list_half_dbl_(T, H, Sgl, H1, H2).

pivot_list_half_dbl_([], H, H2, [], H2Full) :-
    append(H2, [H], H2Full).
pivot_list_half_dbl_([_|T], H, Sgl, [H|H1], H2) :-
    pivot_list_half_(T, Sgl, H1, H2).


gusbro(Before, After):-
 pivot_df(Before, Before, Before, LAcc-LAcc, LAcc2-LAcc2, After, After, After, RAcc-RAcc, RAcc2-RAcc2).

pivot_df([], _, Before, Before-RightFirstHalf, LeftFirstHalf-[], [], _, After, After-LeftFirstHalf, RightFirstHalf-[]).
pivot_df([_], _, Before, Before-[Middle|RightFirstHalf], LeftFirstHalf-[], [_], _, After, After-[Middle|LeftFirstHalf], RightFirstHalf-[]).
pivot_df([_,_|L1], [A|L2], Before, LAcc-LTail, LAcc2-LTail2, [_,_|L3], [B|L4], After, RAcc-RTail, RAcc2-RTail2):-
  LTail=[A|LTail1], RTail=[B|RTail1],
  LTail2=[A|LTail21], RTail2=[B|RTail21],
  pivot_df(L1, L2, Before, LAcc-LTail1, LAcc2-LTail21, L3, L4, After, RAcc-RTail1, RAcc2-RTail21).


damiano(L,LP):-
    length(L,N),
    N2 is div(N,2),
    findall(E, (nth1(I, L, E), I >= 1, I =< N2), S1),
    (   0 is N mod 2 ->
            findall(E, (nth1(I, L, E), I > N2, I =< N), S2),
            append(S2,S1,LP) ;
            N21 is N2 + 2,
            findall(E, (nth1(I, L, E), I >= N21, I =< N), S2),
            N11 is N2 + 1,
            nth1(N11,L,El),
            append([El],S1,S11),
            append(S2,S11,LP)
    ).


comparison :-
    format('  Length  Slago    Brebs    Gusbro   Damiano\n', []),
    forall(between(1, 8, I),
           (   N is 10^6*I,
               length(L, N),
               findall(T,
                       ( member(P, [slago, brebs, gusbro, damiano]),
                         runtime(P, L, T)),
                       Ts),
               format('~|~t~w~8+ ~|~t~5f~8+ ~|~t~5f~8+ ~|~t~5f~8+ ~|~t~5f~8+\n', [N|Ts]) )).


runtime(P, L, T) :-
    garbage_collect,
    T0 is cputime,
    call(P, L, _),
    T is cputime - T0.

Results:

?- comparison.
  Length  Slago    Brebs    Gusbro   Damiano
 1000000  0.04688  0.07812  0.68750  0.60938
 2000000  0.09375  0.17188  0.92188  1.23438
 3000000  0.15625  0.26562  0.67188  1.92188
 4000000  0.21875  0.35938  1.84375  2.60938
 5000000  0.28125  0.46875  1.10938  3.35938
 6000000  0.32812  0.56250  1.35938  3.87500
 7000000  0.39062  0.64062  3.21875  4.67188
 8000000  0.45312  0.70312  3.51562  5.20312
true.

Gusbro's solution caused stack overflow for list with length 9000000.

0
false On

(Assuming you meant pivot not Pivot).

First of all, it is necessary to understand why your current program loops. To understand this, I used a . I thus inserted some goals false at a fitting position:

pivot(Before, After) :-
    append(A,B,Before), false,
    length(A, N),
    length(B, N),
    append(B,A,After).
pivot(Before,After) :-
    append(A,B,Before), false,
    length(A, N),
    N1 is N + 1,
    length(B, N1),
    append(C,Tail,B),
    length(C,1),
    append(Tail,C,F),
    append(F,A,After).

?- pivot(A, [1,2,3,4,5]), false.
   loops.

No need to read any further! In the goal append(A,B,Before) the variables A and B occur for the first time, so they cannot influence termination. Only Before may influence it. But in your query that very argument is a variable. If this fragment does not terminate, then the original program does not terminate. And thus in this case, you will always face non-termination. You need to modify this first goal somehow. This example seems to be a good candidate for using a .

0
damianodamiano On

Here is a possibly cumbersome solution (using SWI prolog), inspired by this question/answer

pivot(L,LP):-
    length(L,N),
    N2 is div(N,2),
    findall(E, (nth1(I, L, E), I >= 1, I =< N2), S1),
    (   0 is N mod 2 ->
            findall(E, (nth1(I, L, E), I > N2, I =< N), S2),
            append(S2,S1,LP) ;
            N21 is N2 + 2,
            findall(E, (nth1(I, L, E), I >= N21, I =< N), S2),
            N11 is N2 + 1,
            nth1(N11,L,El),
            append([El],S1,S11),
            append(S2,S11,LP)
    ).
        
?- pivot([1,2,3,4,5],L).
L = [4, 5, 3, 1, 2]
?- pivot([1,2,3,4],L).
L = [3, 4, 1, 2]
?- pivot([],L).
L = []
0
gusbro On

Here goes a solution using difference lists which does not require to use append and the like:

pivot(Before, After):-
 pivot(Before, Before, Before, LAcc-LAcc, LAcc2-LAcc2, After, After, After, RAcc-RAcc, RAcc2-RAcc2).

pivot([], _, Before, Before-RightFirstHalf, LeftFirstHalf-[], [], _, After, After-LeftFirstHalf, RightFirstHalf-[]).
pivot([_], _, Before, Before-[Middle|RightFirstHalf], LeftFirstHalf-[], [_], _, After, After-[Middle|LeftFirstHalf], RightFirstHalf-[]).
pivot([_,_|L1], [A|L2], Before, LAcc-LTail, LAcc2-LTail2, [_,_|L3], [B|L4], After, RAcc-RTail, RAcc2-RTail2):-
  LTail=[A|LTail1], RTail=[B|RTail1],
  LTail2=[A|LTail21], RTail2=[B|RTail21],
  pivot(L1, L2, Before, LAcc-LTail1, LAcc2-LTail21, L3, L4, After, RAcc-RTail1, RAcc2-RTail21).

Sample runs:

?- pivot([1,2,3,4,5], After).
After = [4, 5, 3, 1, 2] ;
false.

?- pivot([1,2,3,4], After).
After = [3, 4, 1, 2] ;
false.

General query:

?- pivot(Before, After).
Before = After, After = [] ;
Before = After, After = [_] ;
Before = [_A, _B],
After = [_B, _A] ;
Before = [_A, _B, _C],
After = [_C, _B, _A] ;
Before = [_A, _B, _C, _D],
After = [_C, _D, _A, _B] ;
Before = [_A, _B, _C, _D, _E],
After = [_D, _E, _C, _A, _B] ;
Before = [_A, _B, _C, _D, _E, _F],
After = [_D, _E, _F, _A, _B, _C] ;
Before = [_A, _B, _C, _D, _E, _F, _G],
After = [_E, _F, _G, _D, _A, _B, _C] .
0
brebs On

Similar to https://stackoverflow.com/a/74130437/

Edited to use same_length only when necessary, to improve performance.

Edited again to use list_to_dl instead of append, for a tiny performance improvement.

pivot_list_half([A,B|T], LstPivot) :-
    (   is_list([A,B|T]) -> true
        % Preventing infinity with: pivot_list_half(L, [a, b])
        % whilst keeping performance for usual usage
    ;   same_length([A,B|T], LstPivot)
    ),
    pivot_list_half_([A,B|T], [A,B|T], Half1, Middle, Half2),
    list_to_dl(Half2, LstPivot, Half2Tail),
    list_to_dl(Middle, MiddleDL, MiddleTail),
    % Join the tails
    (Half2Tail, MiddleTail) = (MiddleDL, Half1).

pivot_list_half_([], H2, [], [], H2).
pivot_list_half_([_|T], [H|Sgl], H1, Mid, H2) :-
    pivot_list_half_dbl_(T, H, Sgl, H1, Mid, H2).
    
pivot_list_half_dbl_([], H, H2, [], [H], H2).
pivot_list_half_dbl_([_|T], H, Sgl, [H|H1], Mid, H2) :-
    pivot_list_half_(T, Sgl, H1, Mid, H2).

list_to_dl([], T, T).
list_to_dl([H|T], [H|T2], Tail) :-
    list_to_dl(T, T2, Tail).

Results in swi-prolog:

% Deterministic, with both arguments
?- pivot_list_half([a, b, c, d, e], P).
P = [d, e, c, a, b].

?- pivot_list_half(L, [a, b]).
L = [b, a].

?- pivot_list_half(L, P).
L = [_A, _B],
P = [_B, _A] ;
L = [_A, _B, _C],
P = [_C, _B, _A] ;
L = [_A, _B, _C, _D],
P = [_C, _D, _A, _B] ;
L = [_A, _B, _C, _D, _E],
P = [_D, _E, _C, _A, _B] ;
L = [_A, _B, _C, _D, _E, _F],
P = [_D, _E, _F, _A, _B, _C] ;
0
Nicholas Carey On

Here's a solution using difference lists. We walk the source list at two different speeds:

  • 2 elements at a time. This tells us when we've found the middle of the list:

    • if the list is reduced to the empty list ([]), the list is of even length and there is no middle element: we just reconstruct the list with the left and right halves swapped.

    • if the list is reduced to a list of length 1, we've found the middle element: we reconstruct the list with the left and right halves swapped about the middle element.

  • 1 element at a time. This provides the elements to construct the left half of the list as we go, and ultimately provides the middle element (if their is one), and the right half.

https://swish.swi-prolog.org/p/WjOUnQjJ.pl

pivot( Bs , As ) :- var(Bs), var(As), !, fail .
pivot( Bs , As ) :- var(Bs),          !, pivot(As,Bs) .
pivot( Bs , As ) :-                      pivot(Bs,Bs,L-L,As) . 

pivot( []       ,    Rs  , Ls-[]     , Ps ) :- append(Rs,Ls,Ps) .      % even length list
pivot( [_]      , [M|Rs] , Ls-[]     , Ps ) :- append(Rs,[M|Ls],Ps) .  % odd length list
pivot( [_,_|Xs] , [L|Rs] , Ls-[L|Lx] , Ps ) :- pivot(Xs,Rs,Ls-Lx,Ps) . % take 2 and take 1 and recurse down, building the left half as we go

Related Questions in PROLOG

Related Questions in FAILURE-SLICE

Trending Questions

Popular # Hahtags

javascript python java c# php android html jquery c++ css ios sql mysql r reactjs node.js arrays c asp.net json

Popular Questions

.

Copyright © 2021 Jogjafile Inc.