A game of locks and keys

Question

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

Answer 1

CJam, 59 52 50 49 45 43 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#     index was already in the accumulator, i.e., iff we already
         e#     had a key.
  },     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.

Answer 2

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

Answer 3

Haskell, 173 bytes

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|0`notElem`concat b=0|0<1=1+minimum[o[n]b|n<-[1..length b],b!!(n-1)/=[]]
o(n:k)b=o(filter(/=0)(k++b!!(n-1)))(take(n-1)b++[]:drop n b)

Answer 4

Python3, 286 bytes

def f(b):
 q,m=[(b,[],0)],-1
 for b,k,c in q:
  if m!=-1 and c>=m:continue
  if all(0 not in j for j in b):m=[c,min(m,c)][m!=-1];continue
  for K in k:
   if K and b[K-1]:q+=[(b[:K-1]+[[]]+b[K:],k+b[K-1],c)]
  for i,a in enumerate(b):
   if a:q+=[(b[:i]+[[]]+b[i+1:],k+a,c+1)]
 return m

Try it online!

Answer 5

JavaScript (Node.js), 112 bytes

f=(x,...z)=>/,0/.test([,x])?Math.min(...x.map((t,i)=>t?!z.includes(i+1)+f(x.map(u=>u!=t?u:''),...z,...t):1/0)):0

Try it online!

Open till no treasure (number with a leading 0). With key opening is free, while without key it costs