:- use_module(library(lists),[member/2, select/3]).
:- use_module(contestlib,[numlist/3]).

shop(Shop) :-
	numberofcubes(N),
	numlist(1,N,Ns),
	milieus(Milieus),
	shop(Ns,Milieus,[],Shop),
	\+ has_obstructed_shortcut(Shop).

shop([],[],Shop,Shop) :-
	Shop = [ExitI-_|_],
	outerwall(ExitI).
shop(Ns,[Mil|Mils],ShopIn,ShopOut) :-
	select(N,Ns,NewNs),
	check_passage(ShopIn,N),
	NewShopIn = [N-Mil|ShopIn],
	shop(NewNs,Mils,NewShopIn,ShopOut).

check_passage([],I) :- outerwall(I).
check_passage([J-_|_],I) :- no_wall_between(I,J).
	
no_wall_between(X,Y) :- nextto(X,Y).
no_wall_between(X,Y) :- nextto(Y,X).

has_obstructed_shortcut(Shop) :-
	shortcut(MI,MJ),
	member(I-MI,Shop), member(J-MJ,Shop),
	\+(no_wall_between(I,J)).