prologfailure-slice

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

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].

Solution

  • 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.