Pancake, Prolog - rextester

Pancake

%Pancake Sorting Algorithm
%adapted into Prolog from geeksforgeeks.org/pancake-sorting/
%(c) 2020 Ryan Eisele
%find the list starting with the maximum key and running to the tail
% of the list, put in arg 2
% accumulate the start of the list running until the maximum key, and
% store in arg 3
maxpair([Key-Val],[Key-Val],[]):- !.
maxpair([Key-Val|T],[Key-Val|T],[]):-
  maxpair(T,[Key2-_|_],_),
  Key > Key2, !.
maxpair([H|T],Max,[H|T2]):-
  maxpair(T,Max,T2).

%trivial case
pancake([Key-Val], [Key-Val]):- !.
%run pancake on the rest of the list,
%then find the max to tail and flip it, call that Max2
%then append the start of the list running up to Max2, call that T2
%then flip [H|T2] arriving at the result
pancake(A,[H|T5]):-
  maxpair(A,Max,Fst),     %find max to tail, keeping pre-max
  reverse(Max,Max2),      %flip max to tail, call Max2
  append(Fst,Max2,T2),    %append pre-max to Max2, call T2
  reverse(T2,T3),         %flips whole thing
  T3=[H|T4],              %decrement size by taking off head, head is head of result
  pancake(T4,T5).         %pancake the tail, is tail or result


run \| edit \| history \| help	0

Please log in to post a comment.