4 ms·
Since there's a password article on the front page too... This problem is very clever, and there is a very clever way to solve this, assuming everyone plays ni
by sophacles 13y ago
Since there's a password article on the front page too...
This problem is very clever, and there is a very clever way to solve this, assuming everyone plays nice. However, that solution assumes perfect collusion. These are prisoners we're talking about, so at least in some cases, we have to assume there may be bad actors involved. I mean this is a cute problem assuming the following:
1. All the prisoners have perfect memory (for this problem)
2. All the prisoners actually want to live.
3. The warden is telling the truth
4. The guards are all honest.
These are all the type of assumption that gets websites hacked. So what is the attack surface here?
* One of the prisoners decides this is a fun way to suicide
* One of the prisoners is in gang A, and one is in gang B. They value gang honor above their own life, and need to take out the other.
* A guard has decided that this is a great way to off some "scum"
* A prisoner forgets the algorithm, or hits the wrong switch, or other form of human error.
* As if_by_whisky points out: someone dies before the full run.
* The warden just wants to mess with people before feeding them to alligators, and just states "wrong" whenever someone declares all have visited.
* A prisoner can't handle the stakes, and cracks and makes the declaration early.
* The leader messes up the count.
There are probably a lot more.
Further, the warden is making assumptions that we can't be sure are true. Prisons are notorious for being bad at doing the actual security thing. Are there ways for prisoners to collude and do extra error checking on their end? Can a guard be bribed to help share state? Is there a way to get other prisoners involved in message passing, even if they manage to prevent direct collusion between the selected 23?
I don't know a way around all of these. In fact I'm pretty sure there a some combinations where everyone is just fucked. But, what can be done to add robustness to this problem? It seems pretty silly for prisoners (likely malicious actors as a generalization) will follow the rules and stay within the constraints the warden sets out.
I ask, because I've solved plenty of things in a nice elegant way, that were trivially broken by not assuming everything will play nicely in the environment. Similarly I've broken plenty of "awesome solutions" by asking questions about assumptions. The difference between the algorithmic solution and the real world is sometimes surprisingly large. Just some food for thought :)
- garrettgrimsley 13y agoYou are really overthinking this. The Car Talk puzzlers are straight forward and should be taken at face value.
- sophacles 13y agoSince this problem comes around a lot as a programmer interview question, it seems like a good idea to discuss actual systems stuff associated with it. I mean, if I'm hiring a programmer I want them to be good at useful software, not at perfect condition algorithms.
- maxerickson 13y agoThe warden lying is in the same category as the universe exploding (I.e., the universe might explode next week, should I still get a coffee?). It's fine if you think games are stupid, maybe try to get to the point a little quicker though.
- sophacles 13y agoI don't think games are stupid. I just like them to be a bit in depth. Why would I spend time looking at a more interesting version of the game, how to cheat it, and how to add twists otherwise? Also, if you want to take a game theory approach, you're wrong about the warden. If the warden is just playing a sadistic mind game, and wants to fuck with the players before feeding them to the alligators, the correct "solution" to the game for the players (should they catch on to the warden), is to never declare, thus extending the game infinitely, or barring that maximally, before the warden bores of the game and offs them.
- vacri 13y agotrivially broken by not assuming everything will play nicely in the environment. "In theory, there is no difference between theory and practice. In practice, there is"
- aaron695 13y agoPretty much you've failed this on an intelligence level. Give current society and the normal constraints on these popular games the answer to all the above are incredibly obvious, the answers you ask can be deducted. (No prisoner can die, if they could it would have been hinted at) It's like claiming you can't do cryptic crosswords because the questions are not clear or don't follow proper English. Although I imagine you are just trying to be difficult :)
- sophacles 13y agoOr maybe, since this is used as a "hire a programmer" question often, and has been for years, perhaps I just like discussing the very real difference between toy algorithm problems and the fact that algorithms don't exist in toy environments ever. In fact, I literally acknowledged the constraints and toy environment you're talking about in my post. Perhaps you should take a try at actually reading it, rather than insulting me because you think you're a clever person. Oh almost forgot the smiley to indicate something or another sarcastic... :)