# A game of locks and keys

There are n boxes, numbered 1-n. Each box is locked, such that it can be opened by only one corresponding type of key (also numbered 1-n). These keys are randomly scattered in the boxes (one box may have any number of keys, one key may have any number of duplicates), and then all boxes are shut. A treasure (numbered 0) has also been locked in many of the boxes.

You have hired a locksmith to retrieve all the treasure. He charges for each box he cracks open. There is no charge for opening a box for which the key is already available.

Input is the contents of each box. You can decide the format of the input.

Output the minimum cost required to get the treasures.

Notes

1. Your algorithm may take a long time, but that is irrelevant.
2. Shortest code wins.
3. No need to bother about invalid input.

Sample data

Here line i represents the keys present in box i.

Input

2 0
3
4 0
5 6 0
6
0


Output

1


Input

2 0
3 0

4 0
6
5 0


Output

3


Input

2 4 0
3 0

1 0
6
5 0


Output

2


Input

1
3 4

2 6
5


Output

0

• Is this perhaps related to this? Nov 19 '15 at 15:51
• Also related: puzzling.stackexchange.com/questions/23150/… Nov 19 '15 at 16:10
• @VoteToClose Nice video. It is similar, except that it talks of a mathematical puzzle and specific algorithm, rather than a generalised one. Nov 19 '15 at 17:47
• This seems related to this puzzle about 100 locked boxes of wood and steel: puzzling.stackexchange.com/q/17852/4551
– xnor
Nov 20 '15 at 4:31
• @ghosts_in_the_code It's not about simplicity but about flexibility. Commonly, challenges that require structured input allow any convenient list format, as long as the data is not preprocessed. Depending on the language that could mean a whitespace separated file like you have, or it could mean [[1] [3 4] [] [] [2 6] [5]] or maybe {{1},{3,4},{},{},{2,6},{5}}. This way, most languages can reduce reading the input to something as trivial as i=eval(read()) and focus on the fun part of the challenge. Nov 20 '15 at 16:55

# CJam, 595250494543 42 bytes

qN/ee::~e!{_0+{0a&}#>W%_{1$|(z@-},,\;}%:e<  Thanks to @MartinBüttner for golfing off 3 bytes and paving the way for 4 more! Try it online in the CJam interpreter. ### How it works qN/ e# Read all input and split it at linefeeds. ee e# Enumerate the lines. e# STACK: [[0 "i0 i1 ..."] [1 "j0 j1 ..."] ...] ::~ e# Apply ~ (bitwise NOT/evaluate) to each item of the pairs. e# STACK: [[-1 i0 i1 ...] [-2 j0 j1 ...] ...] e! e# Push all unique permutations of the resulting array. { e# For each permutation: _0+ e# Push a copy and append 0 to it. {0a&}# e# Find the first index of an element that contains 0. > e# Discard all previous elements of the array. W% e# Reverse the resulting array. e# We now have a (partial) permutation that contains e# all treasures and ends with a treasure. _ e# Push a copy. The original (which contains lists, but no numbers) will serve as accumulator. { e# Filter; for each list in the array: 1$|  e#     Push a copy of the accumulator and perform set union.
(    e#     Shift out the first element (bitwise NOT of 0-based index).
z    e#     Apply absolute value to push the 1-based index.
@-   e#     Perform set difference with the former state of the
e#     accumulator. This pushes an empty list iff the 1-based
},     e#   Keep the element if we did not have the key.
,      e#   Count the kept elements.
\;     e#   Discard the accumulator from the stack.
}%       e#
:e<      e# Get the minimum of all results.

• Could you add an explanation for us without the gift of CJam understanding? :D I'd like to know how this works. Nov 20 '15 at 9:09
• @VoteToClose Look at this CJAM101 Nov 20 '15 at 17:18
• array long & works, so you can remove the a from 0a&. Sadly this makes it slightly harder to catch you. Nov 20 '15 at 23:16
• @PeterTaylor Unfortunately, if I replace 0a& with 0&, I also have to replace 0+ with 0aa+, since 0 0& is falsy. Nov 21 '15 at 0:42
• @VoteToClose I've edited my answer. Nov 21 '15 at 4:24

## CJam (53 bytes)

Nq+N/:a::~:A,_m*_.&{,}$_{{_Af=e_|}:PA,*A,,^0-P0&!}#=,  This is rather too slow for the online interpreter. ### Dissection Nq+N/:a::~:A e# Parse the input into arrays and store in A ,_m*_.& e# Generate (with duplicates) a powerset of [0 1 ... n] {,}$              e# Sort by size
_{                e# Create a copy and search for first index satisfying...
{_Af=e_|}:P     e#   Store in P a block which does a reachability expansion
A,*             e#   Apply it n times (no path can be longer than n)
A,,^0-          e#   Invert to get the unreached nodes (except 0)
P               e#   Apply P again to see what's reached from the unreached nodes
0&!             e#   Check that it doesn't include [0]
}#
=,                e# Look up the powerset element at that index and find length

• I received java.lang.OutOfMemoryError: Java heap space with your program. Nov 23 '15 at 6:06
• @qumonio, it's not particularly scalable. I haven't tested it with inputs larger than the test inputs in the question, so I'm not sure how far it can go on a standard 1GB heap. Nov 23 '15 at 7:14
• I was trying the 6 line here shown as an array in JS: [ [4,0], [1,3,4], [0], [6,0], [3,0], [5]] of course with the input style as shown in the original post. Nov 23 '15 at 7:16
• @qumonio, on my computer it handles that input fine with only 128MB of heap, which is less than it has by default. Nov 23 '15 at 22:22

l is the one you wanna call.
Not sure whether I shouldn't use a pseudo-Map instead ([(Int,[Int])] instead of [[Int]]).
l=o[].map(map read).map words.lines
o[]b|0notElemconcat b=0|0<1=1+minimum[o[n]b|n<-[1..length b],b!!(n-1)/=[]]