Hacker News Reader

Comment by alex_smart | Hacker News Reader

Assuming the score is 100-Euclidean distance, you should be able to triangulate to the correct answer after three random guesses. Triangulation will give you two candidates for the correct colour, so if you choose between them randomly you should get the correct colour in 4.5 tries on average.

View on HN

The score is floor(100*(1-distance/max_distance)) where max_distance is the greatest distance to the target from any point in the cube. This means that the spheres used in triangulation look funny. Rounding also gets in the way, but you can do it in 5 guesses starting with #B74, #448, #B8B and #4B7 (the first 3 are enough in to uniquely identify it in 3911 out of 4096 cases, and the first 2 are enough in 735; giving an average of less than 4 tries).

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.

I 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).

There's a way to do it in 4 guesses, I described it here: https://news.ycombinator.com/item?id=39888130

I meant 3 tries in total, not just the random guesses.

Because the space is bounded and discrete, you can further optimize by triangulating smartly. If you always pick a triangulation point on the boundary, you will always end up with a single candidate as the other candidate will be out of bounds. (Due to discreteness, you can only pick a point near the boundary, but this will still work in a vast majority of cases.) That reduces the average to ~4.

Reply on news.ycombinator.com