|
|
Go to page [Previous] 1~2 | ||||||||||
Nir Dahan Inner circle Munich, Germany 1390 Posts |
I would like to correct this.
the question as is - has one corner case that is impossible to solve. I, personally think that it is very easy to show that if this is the case then it is trivially non solvable nor interesting. the special case is where you have a loop pointing to room number 1. the workaround, in case this was unclear is to add door 0 - where you enter the whole complex from and it has a note with the number 1 inside... Nir p.s. sorry for the mess |
|||||||||
TomasB Inner circle Sweden 1144 Posts |
"THE special case"? [emphasis added by me] There are as many cases like that as any other case.
To be clear, Nir's and Caféinst's solutions, if they look at the following floors 2,3,1,3 (real solution is that 3 appears more than once) or 2,3,1,2 (real solution is that 2 appears more than once) or 2,1,2,2 (real solution is that 2 obviously appears more than once) or 2,1,3,3 (real solution is that 3 appears more than once) they'd still think that 1 is the solution in each of those cases. I call bad puzzle or bad solutions. /Tomas |
|||||||||
Nir Dahan Inner circle Munich, Germany 1390 Posts |
Let's get the excitement down here Tomas...
ok now that we took a deeper breath, let's think clearly. your 2nd and 3rd cases are irrelevant. if you have a loop and whatever configuration happening outside of the loop - i.e. you can't reach it - then it is VERY easy to show you could not find it so the problem as it is has simply no solution. you could then implicitly assume you have a pointer to door 1 (marking the start) or have the entrance marked as 0 - nothing can point to 0 and the entrance points to 1 and the problem is solved. I still think it is a good puzzle - but this is just my opinion... |
|||||||||
TomasB Inner circle Sweden 1144 Posts |
Bad analogy, since you _can_ find any of the doors. They are there in a line for you to go up to any of them and open it. You _know_ that you will find a number on the floor in any door you open. So it's quite not the same as if you loose a pointer to a linked list. Here you have every object in the list in front of you and can access any of them immediately.
Hence I can show that I _can_ find the entrance to the cycle but it'd be interesting to see your proof that I can't open the door that leads into the cycle. So you chose to rephrase the puzzle to this: - imagine a long corridor full of doors numbered 0 to N+1. - each door is leading to a room where a number is written on the floor (the number can be in the range 1 to N) - inside room 0 there is a "1" on the floor. - obviously since there are N+2 doors/rooms and only N numbers, at least three rooms or two pairs of rooms share the same numbers. - you have a writing pad, where only a few numbers can be written on and no other memory element. - you would like to identify A number which is appearing twice in the rooms. - you can only visit each room a small constant amount of times - say 1,2,3 (but not dependent on N!!!) Just doesn't read like a good puzzle. /Tomas |
|||||||||
Nir Dahan Inner circle Munich, Germany 1390 Posts |
Tomas,
it might need better phrasing but the puzzle itself is IMHO good. if it really bothered you having it the original way - it should have also turned on a little red flashing light that the problem so is not possible. the door 0 workaround need not point to door 1 really but any of the N doors. the numbering is irrelevant really just the 'pointer' as you say. the puzzle was originally borrowed from a CS question with linked lists. there you MUST have an initial pointer to the start - if you wouldn't it would be immediately pointed out by anyone trying to solve it. here it was implicit - could have been worded differently I agree. puzzle is still good - and was understood correctly by at least one other person. so I am probably not the only crazy one around... N |
|||||||||
TomasB Inner circle Sweden 1144 Posts |
I agree it is a good problem with CS linked lists. It just didn't make sense in the example of doors where you can access any object among the linked lists without going through other doors first.
I didn't see the red light since I thought that there actually was a solution. The closest I came to a solution was this: 0. Write down R=1 1. Visit room R and find out where the path loops back onto itself. 2. Does it loop back to R? Then this is not the entrance to the cycle so you have to increase R by one and goto step 1. 3. The room it looped back on is the number you seek. I'm not sure how to prove that the problem as originally posed has no solution so if you have such a proof, Nir, it'd be cool to see. /Tomas |
|||||||||
Nir Dahan Inner circle Munich, Germany 1390 Posts |
Here is an non formal proof or rather a counter example for you off the top of my head -
- assume a loop which is 'circle' like - some element points to the FIRST element - now have EXTRA SINGLE nodes pointing to some place within the loop - since those SINGLE rooms can not be reached from anywhere else you would have to SAVE their room/node number in order to check for double pointers - since those singles can be of the order N --> done. non-formal but I bet you get what I mean N |
|||||||||
TomasB Inner circle Sweden 1144 Posts |
If the EXTRA SINGLE node is door 18 and the element that points at the first element is door 7 I can still open door 18, close it, then go and open door 7.
So no, that doesn't work for the constallation with the doors here. I understand how it'd work if I _had_ to visit the door whose number I find on the floor. But of course I don't have to do that. /Tomas |
|||||||||
Nir Dahan Inner circle Munich, Germany 1390 Posts |
I think I see now why you have such a big problem with it. you didn't see those as pointers.
as for you example - you need to guarantee(!!) finding the double pointer. if you open and close the door you can't be sure that it points to a door you visited and/or already remember! this is why you would need to remember N numbers... that was the whole point. so it is not about finding a possible way where you could find it in less steps but rather show that in order to guarantee finding the double you will need to remember according to your procedure N numbers. |
|||||||||
TomasB Inner circle Sweden 1144 Posts |
I'm not sure I understand the proof but I am happy that you have proved to yourself that the original problem is unsolvable.
Bad problem. Baaad problem. /Tomas |
|||||||||
Nir Dahan Inner circle Munich, Germany 1390 Posts |
Tomas,
I suggest you drink a cup of tea - just to relax. it won't help if you write even 10 more times it is a bad problem. It was solved by others (not only on this forum) and people liked it. you didn't solve it - tough... you also didn't like it - also tough... just wait for the next one maybe it will be better. and just for the record I didn't say it is not solvable - that was cheeky of you rephrasing it like this... I said that I understand why you got confused, and YES the problem could have been rephrased better in order to avoid the corner case. peace. Nir |
|||||||||
TomasB Inner circle Sweden 1144 Posts |
Oh, I _love_ that algorithm that you think solves the problem. It just doesn't apply to the problem as stated but is used to solve another problem.
If the problem was phrased the same way for others that solved it, they simply didn't solve it. The solution seems to be that there is no solution. Perhaps you can, in the next post, write how you'd like to rephrase the problem so that it's solvable by that nice algorithm? /Tomas |
|||||||||
cafeinst Elite user 489 Posts |
Tomas,
I am not sure I understand your concern about this puzzle. Could you please explain. Craig |
|||||||||
TomasB Inner circle Sweden 1144 Posts |
I have no concern at all now after a PM from Caféinst. Turns out that Caféinst solved this one first of us all, Nir included.
There is a solution to the problem exactly as Nir phrased it, without introducing a room 0. *hits forehead* /Tomas |
|||||||||
Nir Dahan Inner circle Munich, Germany 1390 Posts |
Did you mean *hits under the belt* rather than forehead?
|
|||||||||
TomasB Inner circle Sweden 1144 Posts |
I meant my forehead, not yours. GREAT puzzle, Nir.
/Tomas |
|||||||||
Nir Dahan Inner circle Munich, Germany 1390 Posts |
It was also my fault for confusing you in the PMs
but you still owe me a drink for the unjustified bashing |
|||||||||
TomasB Inner circle Sweden 1144 Posts |
I quote
"I am sorry for my initial mistake, and feel free to bash me on the forum " So there. I'm still sorry. But how was your proof again that at least two of the four cases I presented can't be solved? /Tomas |
|||||||||
Nir Dahan Inner circle Munich, Germany 1390 Posts |
Don't push it Tomas...
|
|||||||||
TomasB Inner circle Sweden 1144 Posts |
Oh crap, just as I was falling asleep, I realized that you'll often have to visit a room a number of times dependant of N. Sorry about that.
But there are N! different ways to link the rooms in a long chain where the last room has its own number in it. That last room will unfortunately be visited way more than N times. If there are 6 rooms (N=5) I think the last room will be visited 17 times. There are also N! different way it ends with a two room cycle, where the last room points to the second last room in the chain. Again, way more than N visits to one of the last two rooms, but a bit fewer. There are also N! different ways it ends with a three room cycle. Again more than N re-visits. Same if it ends with a four room cycle, etc, etc, up to a point where you reach the special cases where the number of revisits is down to the desired 2 or 3. Also if there are, let's say M rooms outside of this path, there are (N-M)! different ways to form all the paths described above _times_ the number of ways the M rooms outside this path can be formed in one or many different paths themselves. A lot in other words. The number of revisits then is of course a function of (N-M) which of course is a function of N. I actually hope I'm wrong since I started to like this puzzle a lot, but it seems like special cases where the number of re-vists is _not_ dependant of N. Not sure how to go around this fact. If indeed I'm not misunderstanding something again. /Tomas |
|||||||||
The Magic Cafe Forum Index » » Puzzle me this... » » A new tough one (0 Likes) | ||||||||||
Go to page [Previous] 1~2 |
[ Top of Page ] |
All content & postings Copyright © 2001-2024 Steve Brooks. All Rights Reserved. This page was created in 0.03 seconds requiring 5 database queries. |
The views and comments expressed on The Magic Café are not necessarily those of The Magic Café, Steve Brooks, or Steve Brooks Magic. > Privacy Statement < |