15
$\begingroup$

This question asks about a strange vending machine in which coins can fall out as well as being deposited in, and all the coins it asks for must be deposited before the machine will accept them.

That got me thinking, what would happen if you couldn't see inside the machine to know which switches would be affected and which coins would fall out or stay in?

Thus, consider the following problem:

Consider an Oskar van Deventer vending machine with seven switches. These seven switches are in some unknown position, and it's not known which position the switches are currently in, or which switches have coins in them. It's only known that at least one switch does not have a coin in it.

This machine is also rather finicky in that it only accepts one denomination of coin, so all the coins are indistinguishable.

Devise an algorithm of inserting coins that will be sure of inserting coins into all of the switches in the fewest number of moves, regardless of the starting position.

Improve this question
$\endgroup$
14
  • $\begingroup$ I presume we are able to use the coins falling out the bottom as inputs? $\endgroup$
    – GrahamTheDev
    Commented Jun 16, 2014 at 11:17
  • $\begingroup$ You can reuse them or use new coins; it doesn't matter. $\endgroup$
    – user88
    Commented Jun 16, 2014 at 12:39
  • 1
    $\begingroup$ In the previous question it seemed that you could tell from which slot the coin left. I think Mr. Ritchie meant: do we know this information? can we incorporate that output as feedback for our algorithm? $\endgroup$
    – kaine
    Commented Jun 16, 2014 at 12:43
  • $\begingroup$ Yes, you are allowed to do so. I don't see how you could ever figure out what positions the switches are in otherwise. $\endgroup$
    – user88
    Commented Jun 16, 2014 at 12:45
  • 1
    $\begingroup$ @justhalf: I can only agree with you that it's not very explicit or informative and that the fact that it's a real strategy is a bit philosophical. I don't really know what it means to prove that brute force is or is not the only way -if you do please tell me. As you said on the original post there are only few configurations -16384- so it looks feasible and might be interesting to have a look at what optimal strategies look like. $\endgroup$
    – Ara
    Commented Aug 18, 2014 at 11:03

1 Answer 1

Reset to default
3
+50
$\begingroup$

For clarity, I label the switches and output slots as follows: Switches are labeled from left to right, top to bottom as 1-7. Slots are labeled left to right as A-F.

If we keep dropping coins down slot 1, eventually a coin will come out slot A. At that point we know switch 1 is facing out without coin and switch 3 is facing in without coin. This takes at most 5 drops.

We repeat with slot 4 until a coin comes out slot F. At that point we know switch 2 is facing out without coin and switch 5 is facing in without coin. This also takes at most 5 coins. Total: $\leq 10$.

If we dropped fewer than four coins down slot 4, we drop four more coins down slot 4. This yields another coin out slot F and leaves switches 2 and 5 in place. It also ensures at least two coins fell on the right side of switch 4, guaranteeing that switch now points to the right. Total: $\leq 12$.

We next drop a coin down slot 2. If a coin came out slot C, but not B, we know switch 6 is now empty and facing in. If nothing came out, we know switch 6 is now full, facing in. If two coins came out, we know switch 6 is now empty, but don't know which direction it's facing.

We next drop a coin down slot 3. Likewise, if a coin came out D, we know switch 7 is now empty facing in. If nothing came out, it's full facing in. If two coins came out, it's empty, facing one direction or other.

If we don't know the direction of switch 6, we drop a coin down slot 1, then another down slot 2. (This leaves switch 3 with a coin on it). We now know switch 6 is facing in. If a coin came out slot C, switch 6 is now empty; if not, it is now full. Likewise, if we don't know the direction of switch 7, we drop a coin down slot 4 then another down slot 3. Total: $\leq 18$.

We now know all switches are facing in and we know which way switch 4 is facing. Switches 3, 5, 6, and 7 might be holding coins, depending on above details.

We then follow an algorithm for adding coins when we know what's going on. We first ensure switches 6 and 7 have coins, then 3, 4, and 5, then 1 and 2. The worst case would be if switches 3, 5, and 6 now have coins, but 7 doesn't, in which case, it would take 10 more coins to finish.

Total: $\leq 28$ coins.

Is this plan optimal? No. In the interest of writing a simple algorithm, I ignored a lot of other information we could have gathered. Keeping track of all that information could allow for shortcuts requiring fewer coins.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Post an optimal plan please $\endgroup$
    – warspyking
    Commented Oct 21, 2014 at 23:43
  • $\begingroup$ @warspyking: I'm working on it but the delay seems a bit short ;) $\endgroup$
    – Ara
    Commented Oct 26, 2014 at 13:02
  • $\begingroup$ @Ara There's only 2 days before bounty is gone... $\endgroup$
    – warspyking
    Commented Oct 26, 2014 at 13:56
  • $\begingroup$ An optimal plan would be much more complicated and require a much longer answer. For example, dropping a coin down slot 1 could yield no output coins, or one out slot A, or B, C, AB, AC, ABC, ABBC, ABCD, ABCCD, BBCD, ABCDE, etc. Each of those branches would require a separate plan for the next coin. An optimal plan is simply too complicated. $\endgroup$
    – user3294068
    Commented Oct 27, 2014 at 14:04
  • 1
    $\begingroup$ @user3294068: what you describe is wat I am aiming for. It is not completly ready yet (I guess in a way it's good that warspyking didn't wait to give the bounty: I can take my time), but I have already some results to share and it is false that you can have switch 1 facing out and 3 facing in with dropping 5 or less coins in slot 1. "Switch 1 empty facing out and switches 3 with a coin facing out" are counter example positions that take 8 coins in slot 1 to get to your position. Moreover at the 2nd coin this output a coin on slot 1, as it would have done if switch 3 started facing in. $\endgroup$
    – Ara
    Commented Oct 28, 2014 at 12:05