%edge(source,a).
%edge(source,b).
%edge(b,c).
%edge(a,c).
%edge(c,e).
%edge(c,d).
%edge(c,sink).
%edge(d,sink).


pebble_eater(N) :-
	findall(edge(A,B), edge(A,B), Edges),
	length(Ps, N),
	length(As, N),
	maplist(=(source), Ps),
	maplist(=(sink), As),
	pebble_eater(Ps, As, Edges, _).

member_rest(M, [M|Rest], Rest).
member_rest(M, [X|Xs], [X|Rest]) :-
	member_rest(M, Xs, Rest).

pebble_eater([], [], Edges, Edges).
pebble_eater(Ps0, As0, Edges0, Edges) :- 
	( member(sink, Ps0) ->
		fail
	;
		true
	),
	( member(source, As0) ->
		fail
	;
		true
	),
	annihilate_same_node(Ps0, As0, Ps1, As1),
	move_propebbles(Ps1, EdgePs, Edges0, _),
	move_antipebbles(As1, EdgeAs, Edges0, _),
	annihilate_same_edge(EdgePs, EdgeAs, EdgePs1, EdgeAs1, Edges0, Edges1),
	maplist(eps_to_propebble, EdgePs1, Ps2),
	maplist(eas_to_antipebble, EdgeAs1, As2),
	pebble_eater(Ps2, As2, Edges1, Edges).

annihilate_same_node(Ps0, As0, Ps, As) :-
	( annihilate_same_node_(Ps0, As0, Ps1, As1) ->
		annihilate_same_node(Ps1, As1, Ps, As)
	;
		Ps0 = Ps,
		As0 = As
	).

annihilate_same_node_(Ps0, As0, Ps, As) :-
	member_rest(P, Ps0, Ps),
	member_rest(P, As0, As).
	
move_propebbles([], [], Es, Es).
move_propebbles([P0|Ps0], Ps, Es0, Es) :-
	( member_rest(edge(P0, To), Es0, Es1) *->
		Ps = [edge(P0,To)|PsRest],
		move_propebbles(Ps0, PsRest, Es1, Es)
	;
		move_propebbles(Ps0, Ps, Es0, Es) % no edge left for pebble
	).

move_antipebbles([], [], Es, Es).
move_antipebbles([A0|As0], As, Es0, Es) :-
	( member_rest(edge(To, A0), Es0, Es1) *->
		As = [edge(To,A0)|AsRest],
		move_antipebbles(As0, AsRest, Es1, Es)
	;
		move_antipebbles(As0, As, Es0, Es) % no edge left for pebble
	).

annihilate_same_edge([], As, [], As, Es, Es).
annihilate_same_edge([P0|Ps0], As0, Ps, As, Es0, Es) :-
	( member_rest(P0, As0, As1) ->
		delete_first(Es0, P0, Es1),
		annihilate_same_edge(Ps0, As1, Ps, As, Es1, Es)
	;	
		Ps = [P0|PsRest],
		annihilate_same_edge(Ps0, As0, PsRest, As, Es0, Es)
	).
	
delete_first([D|Rest], D, Rest) :- !.
delete_first([E|List], D, [E|Rest]) :-
	delete_first(List, D, Rest).

eps_to_propebble(edge(_,To), To).

eas_to_antipebble(edge(To,_), To).