Optimizing search algorithm to narrow down possibilities for hidden numbers based on consecutive guesses

Viewed 34

The problem

Computer A picks 3 random numbers between 1 and 18 (inclusively) without duplicates.

eg: Chosen Numbers = 2, 5, 14

Computer B makes random guesses to try and find out what the secret numbers are.

Computer B has to make a random guess of 3 numbers at a time. The guess will always include one random number between 1 and 6 (inclusively), another random between 7 and 12 (inclusively) and another random number between 13 and 18 (inclusively).

We can only see Computer B's guesses which have at least one correctly guessed number. We will not see Computer B's failed guesses and Computer B will not use the failed guesses to influence future guesses, it will continue to guess randomly. We also have no other interaction with either Computer A or B in which we could try and gain any other information from.

eg:  First Guess = 1,  8, 14
    Second Guess = 2,  7, 17
     Third Guess = 5, 10, 16

What I am looking for is an algorithm to narrow down which numbers are still possible after each guess.

Examples

In the example shown above, Computer B has made three guesses. Because we know each guess must contain at least one correct number and - in this simple case - each guess does not overlap with another guess, and since we know there are 3 numbers to find and 3 non overlapping guesses we are able to conclude that every other number which was not guessed is impossible to be a correct number.

If we plot the guesses on a table we get:

Possible Numbers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Guess 1 + + +
Guess 2 + + +
Guess 3 + + +
Impossible Numbers: x x x x x x x x

The algorithm needs to be able to determine when it is able to start excluding possibilities, find the maximum numbers to exclude, and also handle more complex situations.

A more complex situation:

Chosen Numbers = 2,  8, 10

   First Guess = 1, 10, 17
  Second Guess = 2,  9, 16
   Third Guess = 2, 10, 13
  Fourth Guess = 4,  8, 16
   Fifth Guess = 2,  9, 14
   Sixth Guess = 5,  8, 18

In this case: Guesses 1, 2, and 6 don't overlap. Guesses 1, 4, and 5 don't overlap. And guesses 1, 5, and 6 don't overlap. So for each non overlapping set of 3 we can rule out the numbers outside of that set. Then combine the 3 sets of impossible numbers to narrow down the remaining possible correct numbers:

Possible Numbers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Guess 1 + + +
Guess 2 + + +
Guess 3 + + +
Guess 4 + + +
Guess 5 + + +
Guess 6 + + +
Impossible 1x2x6: x x x x x x x x x
Impossible 1x4x5: x x x x x x x x x
Impossible 1x5x6: x x x x x x x x x
Combined Impossible: x x x x x x x x x x x x

Using the combined set of newly found impossible numbers we can look back at the existing guesses and compare them to see if they contain any ruled out numbers. After doing this you will notice Guess 6 has 2 out of 3 guessed numbers which have now been ruled out by the new impossible set of numbers. And because it must contain a correct number in the guess the remaining number has to be one of the numbers chosen by Computer A. Therefore, in this case, we find that 8 must be a correct number.

My Attempt

Here is a JFiddle of the algorithm if anyone wants to play around with what I have so far.

Is there any further analysis we can do to find out more impossible numbers or correct numbers in less amount of guesses? And is there a way to simplify the guesses down so that we only have to store the least amount of information needed to deduce the numbers.

Also I am considering what it would look like if Computer A chooses more than 3 numbers while keeping the same requirements for Computer B's guesses.

Tips appreciated.

0 Answers
Related