treasure
``` ```
% treasure.pi (in Picat)
% by N.F. Zhou, March 25, 2015
% Qualification Round 2013
% Problem D. Treasure
%
% to use: picat treasure < input_file > output_file
%
% Keys held in hand and keys contained in each chest are represented as
% ordered lists of pairs, where in each pair the first element is a type
% number and the second is a quantity.

import planner.

main =>
foreach (Case_num in 1..C)
KeyList = [read_int() : _ in 1..K].sort(),
TypeList = KeyList.sort_remove_dups(),
TypeQtPairs = [(Type,Qt) : Type in TypeList,
Qt = sum([1 : Type in KeyList])],
initialize_table,
once do_case(Case_num, TypeQtPairs, Chests)
end.

KeyList = [read_int() : _ in 1..Ki].sort(),
TypeList = KeyList.sort_remove_dups(),
TypeQtPairs = [(Type,Qt) : Type in TypeList,
Qt = sum([1 : Type in KeyList])],
Chests = [\$chest(Ti,TypeQtPairs)|Chests1],

do_case(Case_num,Keys,Chests),
plan_unbounded({Keys,Chests},Plan)
=>
chest_to_index(Plan,Chests,[],Is),
printf("Case #%w: ", Case_num),
foreach (I in Is)
printf("%w ", I)
end,
nl.
do_case(Case_num,_Keys,_Chests) =>
printf("Case #%w: IMPOSSIBLE\n", Case_num).

chest_to_index([],_Chests,Is0,Is) => Is = reverse(Is0).
chest_to_index([Chest|Plan],Chests,Is0,Is) =>
nth(I,Chests,Chest),
not member(I,Is0),
chest_to_index(Plan,Chests,[I|Is0],Is).

final({_,[]}) => true.    % done when all chests have been opened

action({Keys,Chests},NewS,Action,Cost) =>
Action = Chest, Cost = 1,
select(Chest,Chests,ChestsRest),      % select a chest to open
Chest = \$chest(KeyType,ChestKeys),
select((KeyType,Qt),Keys,KeysRest),   % select a key to open the chest
NewQt = Qt-1,
(NewQt == 0 ->
KeysRest1 = KeysRest
;
KeysRest1 = insert_ordered(KeysRest,(KeyType,NewQt))
),
possible(NewKeys,ChestsRest),
NewS = {NewKeys,ChestsRest}.

%% merge two sets (ordered lists)
NewKeys = [(Type,Qt1+Qt2)|NewKeysR],
NewKeys = [Key1|NewKeysR],
NewKeys = [Key2|NewKeysR],

% For each key type, the available quantity should not be less than
% the needed quantity.It's possible to open a chest if there is a key
% in hand that can open it or a key is inside another chest and that
% chest is possible to be opened.
table
possible(_,[]) => true.
possible([],Chests) => fail.
possible(Keys,Chests) =>
count_keys(Chests,NeededKeys),
foreach((NeededType,NeededQt) in NeededKeys)
sum([Qt : \$chest(_,ChestKeys) in Chests, (NeededType,Qt) in ChestKeys]) +
sum([Qt : (NeededType,Qt) in Keys]) >= NeededQt
end,
foreach (\$chest(KeyType,_) in Chests)
possible(Keys,KeyType,Chests)
end.

table
count_keys(Chests,NeededKeys) =>
Keys = [Key : \$chest(Key,_) in Chests],
KeyTypes = sort_remove_dups(Keys),
NeededKeys = [(KeyType,Qt) : KeyType in KeyTypes,
Qt = sum([1 : KeyType in Keys])].

table
possible(Keys,KeyType,_Chests),
member((KeyType,_),Keys)
=>
true.
possible(Keys,KeyType,Chests) =>
member(Chest1,Chests),
Chest1 = \$chest(KeyType1,ChestKeys),
once member((KeyType,_),ChestKeys),
possible(Keys,KeyType1,Chests).
``````