/*
already in 2014, Michael (I have no further id) wrote to me:

%% while stepping through the code of palmtree.pl in 'The First 10
%% Prolog Programming Contests' I recognized the first clause of
%% time_from_well/3 never holds. The list checked for being empty
%% always has at least one member.

He was right. He suggested a fix with which I was not happy,
hence, after so many years (now 2020) a new version
*/

:- use_module(library(lists),[select/3, sum_list/2]).

palmtree(LongestVisit) :-
	setof(Tree,palm(Tree),Trees),
	setof(Duration-Visit,visit(Trees,Duration,Visit),AllVisits),
	AllVisits = [_-LongestVisit|_].

visit(Trees,Duration,Visit) :-
	permute(Trees,Visit),
	bucket(FullBucket),
	time_for_visit(Visit,FullBucket,Duration).

% Visit must consist of parts whose palm_needs add up to FullBucket
% except for the last part
% each part begins and ends with a trip from/to the well

time_for_visit(Visit,FullBucket,Duration) :-
	makeparts(Visit,FullBucket,Parts),
	findall(Cost,(member(Part,Parts), append(_,[X,Y|_],Part),
		      p2p(X,Y,Cost)),BetweenTrees),
	findall(WellCost,(member(Part,Parts),
			  append(A,[X|B],Part),
			  (A == [] ; B == []),
			  palm2well(X,WellCost)),WellCosts),
	append(BetweenTrees,WellCosts,AllCosts),
	sum_list(AllCosts,Duration1),
	Duration is -Duration1.

makeparts([],_,_) :- !, Parts = [].
makeparts(Trees,FullBucket,[Part|Parts]) :-
	once((append(Part,RestTrees,Trees),
	      sum_needs(Part,FullBucket,Remains),
	      (RestTrees == [] ; Remains = 0)
	      )),
	makeparts(RestTrees,FullBucket,Parts).

sum_needs([],F,F).
sum_needs([A|As],Full,Remains) :-
	palm_needs(A,Cap),
	Full1 is Full - Cap,
	Full1 >= 0,
	sum_needs(As,Full1,Remains).

palm(X) :- palm2palm(X,_,_) ; palm2palm(_,X,_) ; palm2well(X,_).

p2p(X,Y,T) :- once((palm2palm(X,Y,T) ; palm2palm(Y,X,T))).

permute([],[]).
permute([X|R],O) :- permute(R,RP), select(X,O,RP).