The Prisoner of Benda - new problem idea
Back to General discussions forum
Hellow friends!
I would like to suggest new problem idea. As some codeabbey tasks puzzled me a lot my mind was actually distracted and today I remembered one fascinating problem that was introduced in one silly cartoon called "Futurama" which I used to watch few years ago.
The episode called "The Prisoner of Benda" was about swapping minds in some kind of "science" machine. Two people (or robot) could swap their minds (or consciousness) in this machine but after they did so, they could not swap back, therefore if 2 people wanted to reverse this change, they needed third person. At the end of the episode there were a lot of people despair and wanted their bodies back. The professor came with mathematical approach how to get everybody back and the episode ended happily.
If the explanation wasn't good enough, I found Wikipedia article with some more sauce to it. I know this post is quite shorter than it should be, check the article or watch the episode (you can find it in your native language online for sure!) maybe you can refer to this video as well for further explanation.
Sincerely Radovan.
Radovan, Hi!
So the problem should be like this - we are given set of persons with interchanged personalities, and we want to find the sequence of swaps to return them each one to one's self body?
BTW, article you referenced itself references at some point curious web-site Cut-the-Knot which seemingly may inspire puzzles, but it seems to have tons of materials... :o
So the problem should be like this - we are given set of persons with interchanged personalities, and we want to find the sequence of swaps to return them each one to one's self body? It is up to you :) I just wanted to provide some relevant material to begin with.
BTW, article you referenced itself references at some point curious web-site Cut-the-Knot which seemingly may inspire puzzles, but it seems to have tons of materials... :o Well it could be, maybe there are far more better problem ideas I just wanted you to push a little and provide some inspiration. To be honest I did not go through all the wiki and the Cut-the-knot :D Hope you can use it. My idea is not to add what I suggest all the time, but to add new stuff generally, so if you think it has more potential just share your thoughts with us! :D :)
Update: Oh I see there is literally a ton of materials. I would be glad if you could also add a ton of new tasks but after all it is up to you what will you use. If you could add all those task it could shake the ranking list of all those cardinals he-he.
But I see there is at least one problem I put down to my notes. I wanted to suggest also hanoi towers puzzle. Seeing it in cut-the-knot reminds me of that.
I wanted to suggest also hanoi towers puzzle
Ah, right, I also thought about it several times (and perhaps someone... you? - already suggested it). The matter is I'm not sure how to make problem of it. E.g. We know there are three towers and there is strategy to do all transfers... Well, what should be the problem? That puzzles me a bit. Feel free to hint :)
It is up to you :)
Cunning! but it is so hard - to think! :) I'll try to figure out how we solve it in this variant!
I recall seeing a video about this problem in the past: https://www.youtube.com/watch?v=J65GNFfL94c
I think it does a good job outlining a procedure that does the trick, given two additional bodies to sort out the mess.
Ah, Vadim, Radovan - thanks for patient explanations! At last I have got that we have limitation - swap doesn't work for the second time for the same pair of people. Otherwise any sorting algorithm with swaps would work.
All right, I believe we can have it quickly. I'll try my best, thanks!
UPD: problem is accessible in the problem list, so you are welcome to test!
I'm a bit confused while testing it myself, so don't frustrate if it will not work correctly - just tell, so we can investigate!
Solved. Pretty much went with the procedure outlined in the Mathologer video.
By the way, what does "UPD" stand for?
what does "UPD" stand for
"update" - sorry for confusion, it was slightly past midnight here and I felt somewhat clumsy already, especially after manual testing some simple cases being lazy enough to watch the video. Though it helped me to get feeling that without hints the problem makes puzzle enough, at least for average person :)
Thanks for confirmation! BTW, how much time it took to implement this in java? I understand that you probably wasn't looking at the clock - but at least according to your general sense of time?
"Laziness is the the most valuable virtue among programmers." Said some of our professors altough I still feel entertained when hearing someone saying that he was too lazy to do something. Maybe I could finally solve some of the freshly added problems as I find klotzki and cracking RNG too difficult (at least for now), this problem might be of average difficulty. I will let you know once I will solve it. Thanks for adding it and also thanks for highlighting the video, I have seen it (thumbnail) on youtube but I was just too lazy (ha-ha) to watch it at first. I hope I can solve this in upcoming few days. I will tell you my thoughs and feelings after solving it.
BTW, how much time it took to implement this in java?
Based on my chrome browsing history for when I opened the page for the problem description, and the last edit I made in my IDE for the problem, it seems I took 87 minutes to do the problem.
The code I wrote right away was almost correct, but I did have to spend a fair amount of time debugging it and I manually did some examples by hand as well.