/***********************************************************************

	       Solution to Boston Phoenix Puzzle # 681

			  Stuart M. Shieber

***********************************************************************/


:- op(300, xfx, before).

/* least(List, Least)    Least is the least element in the list in the
 * ==================    before/2 ordering.
 */
least(List, Least) :-
	member(Least, List),
	\+((member(Other, List),
	    (Other before Least))).

/* top_sort(List, Sorted)   Sorted is a topological sort of List
 * ======================   according to the before/2 ordering.
 */
top_sort([], []).
top_sort(List, [Least|SortedRest]) :-
	least(List, Least),
	remove(Least, List, Rest),
	top_sort(Rest, SortedRest).


/*----------------------------------------------------------------------
			      Utilities
----------------------------------------------------------------------*/

/* member(Element, List)   Element is an element of List.
 * =====================
 */
member(A, [A|_Rest]).
member(A, [_B|Rest]) :- 
	!,
	member(A, Rest).

/* remove(Element, List, Shorter)   Shorter is List with all
 * ==============================   occurrences of Element removed. 
 */
remove(_A, [], []).
remove(A, [A|Rest], RemRest) :- 
	!,
	remove(A, Rest, RemRest).
remove(A, [B|Rest], [B|RemRest]) :-
	remove(A, Rest, RemRest).

/*----------------------------------------------------------------------
		    Base Ordering on Bullet Holes

Labeling of bullet holes is as follows:

	a

		b	e

	c		f

		d	g	i
	
			h	j

----------------------------------------------------------------------*/

a before b.
a before c.
a before e.
c before b.
e before b.
f before b.
f before e.
c before f.
f before d.
c before d.
e before d.
h before g.
j before h.
d before j.
d before i.
i before j.

/*----------------------------------------------------------------------
		       Execution of the Program
------------------------------------------------------------------------

	:-  top_sort([a,b,c,d,e,f,g,h,i,j], S).

	S = [a,c,f,e,b,d,i,j,h,g] ;

	S = [a,c,f,e,d,b,i,j,h,g] ;

	S = [a,c,f,e,d,i,b,j,h,g] ;

	S = [a,c,f,e,d,i,j,b,h,g] ;

	S = [a,c,f,e,d,i,j,h,b,g] ;

	S = [a,c,f,e,d,i,j,h,g,b] ;

	no

Using the first ordering to connect the bullet holes:

	a
	|
	|	b-------e
	|	|	:
	c-------+-------f		"LEO"
		|
		d-------g-------i
			|	|
			h-------j


*/