numberofboxes(120).

container_capacity(15000).

validcontainerweight(X) :-
	container_capacity(C),
	X =< C.

box_weight(0, 4200).				% weight in kilogram
box_weight(1, 6900).
box_weight(2, 6700).
box_weight(3, 5700).
box_weight(4, 9300).
box_weight(5, 9000).
box_weight(6, 3800).
box_weight(7, 3600).
box_weight(8, 4500).
box_weight(9, 4200).
box_weight(10, 3300).
box_weight(11, 7900).
box_weight(12, 2700).
box_weight(13, 5700).
box_weight(14, 4400).
box_weight(15, 8400).
box_weight(16, 8600).
box_weight(17, 9200).
box_weight(18, 4600).
box_weight(19, 3800).
box_weight(20, 8500).
box_weight(21, 3300).
box_weight(22, 8200).
box_weight(23, 7300).
box_weight(24, 4900).
box_weight(25, 7000).
box_weight(26, 5900).
box_weight(27, 2300).
box_weight(28, 5700).
box_weight(29, 7200).
box_weight(30, 7400).
box_weight(31, 6900).
box_weight(32, 3300).
box_weight(33, 4200).
box_weight(34, 2800).
box_weight(35, 4600).
box_weight(36, 3000).
box_weight(37, 6400).
box_weight(38, 2900).
box_weight(39, 7400).
box_weight(40, 4100).
box_weight(41, 4900).
box_weight(42, 5500).
box_weight(43, 9800).
box_weight(44, 8000).
box_weight(45, 3200).
box_weight(46, 2500).
box_weight(47, 3800).
box_weight(48, 8200).
box_weight(49, 3000).
box_weight(50, 3500).
box_weight(51, 3900).
box_weight(52, 5700).
box_weight(53, 8400).
box_weight(54, 6200).
box_weight(55, 5000).
box_weight(56, 5500).
box_weight(57, 2700).
box_weight(58, 3000).
box_weight(59, 3600).
box_weight(60, 2000).
box_weight(61, 7800).
box_weight(62, 4700).
box_weight(63, 2600).
box_weight(64, 4500).
box_weight(65, 4100).
box_weight(66, 5800).
box_weight(67, 9800).
box_weight(68, 9100).
box_weight(69, 9600).
box_weight(70, 7300).
box_weight(71, 8400).
box_weight(72, 3700).
box_weight(73, 9300).
box_weight(74, 9100).
box_weight(75, 4300).
box_weight(76, 7300).
box_weight(77, 8500).
box_weight(78, 8100).
box_weight(79, 7900).
box_weight(80, 7100).
box_weight(81, 8000).
box_weight(82, 7600).
box_weight(83, 8300).
box_weight(84, 4100).
box_weight(85, 7800).
box_weight(86, 7000).
box_weight(87, 2300).
box_weight(88, 4200).
box_weight(89, 8700).
box_weight(90, 4300).
box_weight(91, 8400).
box_weight(92, 6000).
box_weight(93, 5500).
box_weight(94, 4900).
box_weight(95, 7800).
box_weight(96, 7300).
box_weight(97, 6200).
box_weight(98, 3600).
box_weight(99, 4400).
box_weight(100, 9400).
box_weight(101, 6900).
box_weight(102, 3200).
box_weight(103, 9600).
box_weight(104, 7000).
box_weight(105, 8400).
box_weight(106, 5800).
box_weight(107, 7800).
box_weight(108, 2500).
box_weight(109, 8000).
box_weight(110, 5800).
box_weight(111, 6600).
box_weight(112, 8300).
box_weight(113, 2400).
box_weight(114, 9800).
box_weight(115, 6000).
box_weight(116, 4200).
box_weight(117, 4300).
box_weight(118, 4300).
box_weight(119, 3900).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


untag(_-U, U).

first_fit_decreasing(Knaps) :-
	numberofboxes(N),
	length(Knaps0, N),
	maplist(=(0-[]), Knaps0),
	findall(Size-ID, box_weight(ID, Size), Boxes0),
	keysort(Boxes0, Boxes1),
	reverse(Boxes1, Boxes2),
	maplist(untag, Boxes2, Boxes3),
	first_fit_decreasing(Boxes3, Knaps0, Knaps1),
	sublist(filled, Knaps1, Knaps2),
	maplist(untag, Knaps2, Knaps).

filled(Volume-_) :- Volume > 0.

first_fit_decreasing([], Knaps, Knaps).
first_fit_decreasing([B|Bs], Knaps0, Knaps) :-
	box_weight(B, Weight),
	fit_box(Knaps0, B-Weight, Knaps1),
	first_fit_decreasing(Bs, Knaps1, Knaps).

fit_box([Volume0-IDs0|Knaps], Box-Weight, [Volume-IDs|Rest]) :-
	Volume1 is Volume0 + Weight,
	( validcontainerweight(Volume1) ->
		Volume = Volume1,
		IDs = [Box|IDs0],
		Rest = Knaps
	;
		Volume = Volume0,
		IDs = IDs0,
		fit_box(Knaps, Box-Weight, Rest)
	).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

best_fit_decreasing(Knaps) :-
	findall(Size-ID, box_weight(ID, Size), Boxes0),
	keysort(Boxes0, Boxes1),
	reverse(Boxes1, Boxes2),
	maplist(untag, Boxes2, Boxes3),
	best_fit_decreasing(Boxes3, [], Knaps0),
	maplist(untag, Knaps0, Knaps).

best_fit_decreasing([], Knaps, Knaps).
best_fit_decreasing([B|Bs], Knaps0, Knaps) :-
	box_weight(B, Weight),
	best_fit_box(Knaps0, B-Weight, none, Best),
	( Best == none ->
		Knaps2 = [Weight-[B]|Knaps0]
	;
		delete(Knaps0, Best, Knaps1),
		Best = KV0-Items0,
		KV is KV0 + Weight,
		Knaps2 = [KV-[B|Items0]|Knaps1]
	),
	best_fit_decreasing(Bs, Knaps2, Knaps).


best_fit_box([], _, Best, Best).
best_fit_box([Volume0-IDs0|Knaps], Box-Weight, SoFar, Best) :-
	Volume1 is Volume0 + Weight,
	( validcontainerweight(Volume1) ->
		( SoFar == none ->
			best_fit_box(Knaps, Box-Weight, Volume0-IDs0, Best)
		; SoFar = V-_ ->
			( Volume0 > V ->
				best_fit_box(Knaps, Box-Weight, Volume0-IDs0, Best)
			;
				best_fit_box(Knaps, Box-Weight, SoFar, Best)
			)
		)
	;
		best_fit_box(Knaps, Box-Weight, SoFar, Best)
	).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

worst_fit_decreasing(Knaps) :-
	findall(Size-ID, box_weight(ID, Size), Boxes0),
	keysort(Boxes0, Boxes1),
	reverse(Boxes1, Boxes2),
	maplist(untag, Boxes2, Boxes3),
	worst_fit_decreasing(Boxes3, [], Knaps0),
	maplist(untag, Knaps0, Knaps).

worst_fit_decreasing([], Knaps, Knaps).
worst_fit_decreasing([B|Bs], Knaps0, Knaps) :-
	box_weight(B, Weight),
	worst_fit_box(Knaps0, B-Weight, none, Best),
	( Best == none ->
		Knaps2 = [Weight-[B]|Knaps0]
	;
		delete(Knaps0, Best, Knaps1),
		Best = KV0-Items0,
		KV is KV0 + Weight,
		Knaps2 = [KV-[B|Items0]|Knaps1]
	),
	worst_fit_decreasing(Bs, Knaps2, Knaps).


worst_fit_box([], _, Best, Best).
worst_fit_box([Volume0-IDs0|Knaps], Box-Weight, SoFar, Best) :-
	Volume1 is Volume0 + Weight,
	( validcontainerweight(Volume1) ->
		( SoFar == none ->
			worst_fit_box(Knaps, Box-Weight, Volume0-IDs0, Best)
		; SoFar = V-_ ->
			( Volume0 < V ->
				worst_fit_box(Knaps, Box-Weight, Volume0-IDs0, Best)
			;
				worst_fit_box(Knaps, Box-Weight, SoFar, Best)
			)
		)
	;
		worst_fit_box(Knaps, Box-Weight, SoFar, Best)
	).