View Single Post
Old 2021-06-02, 21:32   #10
uau
 
Jan 2017

12010 Posts
Default

Trying something that could be the correct answer given all previous ones (which I believe is what Walter's code does) is not always the optimal answer, either for average or worst-case behavior (at least worst case for remaining tries in a particular situation, I don't show this to necessarily affect the global worst case):

Suppose that n = 1000000. Your first random guess gets 999998 matches right (quite lucky). Now, if you keep trying guesses that could be the correct answer, they can only swap one pair from your initial guess. Since you can only change two places at once, you'd expect to need around 146000 tries to even try changing one of the incorrect positions (you'd try changing twice that number of places, and 50% chance that both the incorrect positions are outside that set). Some kind of bisection strategy should be able to do much better than that.

Last fiddled with by uau on 2021-06-02 at 21:35
uau is offline   Reply With Quote