12
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ Is this perhaps related to this? \$\endgroup\$ – Addison Crump Nov 19 '15 at 15:51
  • \$\begingroup\$ Also related: puzzling.stackexchange.com/questions/23150/… \$\endgroup\$ – Leif Willerts Nov 19 '15 at 16:10
  • \$\begingroup\$ @VoteToClose Nice video. It is similar, except that it talks of a mathematical puzzle and specific algorithm, rather than a generalised one. \$\endgroup\$ – ghosts_in_the_code Nov 19 '15 at 17:47
  • 1
    \$\begingroup\$ This seems related to this puzzle about 100 locked boxes of wood and steel: puzzling.stackexchange.com/q/17852/4551 \$\endgroup\$ – xnor Nov 20 '15 at 4:31
  • 4
    \$\begingroup\$ @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. \$\endgroup\$ – Martin Ender Nov 20 '15 at 16:55
6
\$\begingroup\$

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.
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ Could you add an explanation for us without the gift of CJam understanding? :D I'd like to know how this works. \$\endgroup\$ – Addison Crump Nov 20 '15 at 9:09
  • 2
    \$\begingroup\$ @VoteToClose Look at this CJAM101 \$\endgroup\$ – user41805 Nov 20 '15 at 17:18
  • \$\begingroup\$ array long & works, so you can remove the a from 0a&. Sadly this makes it slightly harder to catch you. \$\endgroup\$ – Peter Taylor Nov 20 '15 at 23:16
  • \$\begingroup\$ @PeterTaylor Unfortunately, if I replace 0a& with 0&, I also have to replace 0+ with 0aa+, since 0 0& is falsy. \$\endgroup\$ – Dennis Nov 21 '15 at 0:42
  • \$\begingroup\$ @VoteToClose I've edited my answer. \$\endgroup\$ – Dennis Nov 21 '15 at 4:24
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I received java.lang.OutOfMemoryError: Java heap space with your program. \$\endgroup\$ – ŽaMan Nov 23 '15 at 6:06
  • \$\begingroup\$ @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. \$\endgroup\$ – Peter Taylor Nov 23 '15 at 7:14
  • \$\begingroup\$ 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. \$\endgroup\$ – ŽaMan Nov 23 '15 at 7:16
  • \$\begingroup\$ @qumonio, on my computer it handles that input fine with only 128MB of heap, which is less than it has by default. \$\endgroup\$ – Peter Taylor Nov 23 '15 at 22:22
0
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.