4 ms·
Excellent work! We can also probably prove that 3 guesses are not enough by some sort of adversarial argument. That is, instead of having the color be fixed at
by alex_smart 3y ago
Excellent work!
We can also probably prove that 3 guesses are not enough by some sort of adversarial argument. That is, instead of having the color be fixed at the start, imagine that the game picks the colors adversarially to try to make the job of the guesser as difficult as possible, while remaining consistent with the answers it has already given. If we can pick a function for the adversary that does not fully disambiguate the color completely for any sequence of three guesses, we will be done.
- penteract 3y agoI wouldn't be surprised if there is a way of doing it in 4 guesses (3 to identify and a 4th that's known to be right), although you probably need to adjust the later guesses based on the results of the first. It wouldn't be impossible to search the space of strategies exhaustively. Precomputing the score function (and storing it as 4096*101 4096-bit bitstrings for efficient set intersection) would speed things up, and it could be a chance to use the 3D texture handling features of a GPU (I've done very little GPU programming so take my enthusiasm with a pinch of salt).
- n2d4 3y agoThere's a way to do it in 4 guesses, I described it here: https://news.ycombinator.com/item?id=39888130 https://news.ycombinator.com/item?id=39888130
- alex_smart 3y agoI meant 3 tries in total, not just the random guesses.