15

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.

Community
  • 1
  • I presume we are able to use the coins falling out the bottom as inputs? – GrahamTheDev Jun 16 '14 at 11:17
  • You can reuse them or use new coins; it doesn't matter. –  Jun 16 '14 at 12:39
  • 1
    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? – kaine Jun 16 '14 at 12:43
  • Yes, you are allowed to do so. I don't see how you could ever figure out what positions the switches are in otherwise. –  Jun 16 '14 at 12:45
  • Just making sure the problem is well defined. There are situations where one could feasibly cause an input in one column to cause a coin to drop out in another. But if the channels join you could still feasiblly solve it by just noting that a coin left though you don't know from where! – kaine Jun 16 '14 at 13:00
  • @kaine: we can also make use of the number of coins coming out. :) – justhalf Jun 26 '14 at 04:53
  • I think this is doable, it's just too many cases to be handled. – justhalf Jun 26 '14 at 04:54
  • @justhalf: Not just the number of coins, also their positions. –  Jun 26 '14 at 05:04
  • @JoeZ.: I'm referring to kaine's comment in the case the channels are joined. :) – justhalf Jun 26 '14 at 05:45
  • There exists a strategy (for instance go to the all green switch without coins then fill them) therefore there exist at least one minimal strategy, however I don't think you can do anything better than brute force. Therefore your strategies goes like that: find all possible configurations given the previous results; find a coin entrance that minimize the maximum number of remaining moves; put a coin there; repeat until you know that the current position is the desired one. Not very attractive. – Ara Aug 17 '14 at 10:20
  • @Ara: what you've described is not a strategy to insert the coins, it's a strategy to find a minimum strategy to insert coins such that all switches have a coin. Therefore I don't agree in saying that the minimum strategy is a brute force. You just described a brute force way to find the answer to this question, which might not be the only way. That's why this question is interesting. Unless you can prove that brute force is the only way, which I think is impossible to prove. – justhalf Aug 18 '14 at 01:33
  • 1
    @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. – Ara Aug 18 '14 at 11:03
  • it is sometimes possible to drop 2 coins onto the same switch simultaneously, when it already has a coin on it. For example, numbering the switches from left-right, top-bottom as 0-6, 0 is on the right with a coin, and 2,3,5 are on the left with a coin. if you drop a coin in 0-left, what happens in switch 5? A coin will come in both switch 5 left and right, and it already has one. will it stay on the same side with a coin (dropping a coin from each side), or will it switch sides and drop a total of 3 coins? (ascii art describing question: http://pastebin.com/N1MARraT) – YenTheFirst Oct 22 '14 at 00:32
  • Also, is any arbitrary starting position possible, or only positions that could be reached by dropping coins into the top? e.g., could the machine start with the middle-left switch on the outside, with a coin on top? – YenTheFirst Oct 22 '14 at 23:00

1 Answers1

3

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.

user3294068
  • 7,498
  • 23
  • 32
  • Post an optimal plan please – warspyking Oct 21 '14 at 23:43
  • @warspyking: I'm working on it but the delay seems a bit short ;) – Ara Oct 26 '14 at 13:02
  • @Ara There's only 2 days before bounty is gone... – warspyking Oct 26 '14 at 13:56
  • 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. – user3294068 Oct 27 '14 at 14:04
  • 1
    @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. – Ara Oct 28 '14 at 12:05