Hacker News new | ask | show | jobs
by function_seven 2969 days ago
If no cycle is longer than 50 boxes (~30% chance of that being true), then by starting with the box that matches your number, you have a 100% chance of navigating to the box containing your number before your 50-box limit is reached. It’s impossible to start in the wrong cycle, because that cycle contains neither the pointer or the value.

You have to find your pointer in a circular linked list. But it’s only singly-linked, so you start just in front of it and work around the links the long way. 30% of the time, all the lists are 50 elements or shorter, meaning everyone is guaranteed to succeed.

1 comments

But what if your name is in box #51, which you aren't allowed to open?
Then there's a cycle of length > 50 and everyone loses.
Like sibling says, this only happens when there’s a cycle longer than 50. In that case, you’re all doomed.