CCO '96 P2 - SafeBreaker

View as PDF
Submit solution
Points: 10
Time limit: 1.0s
Memory limit: 64M
Problem type
Canadian Computing Competition: 1996 Stage 2, Day 1, Problem 2

We are observing someone playing a game similar to Mastermind™. The object of this game is to find a secret code by intelligent guesswork, assisted by some clues. In this case the secret code is a 4-digit number in the inclusive range from 0000 to 9999, say 3321. The player makes a first random guess, say 1223 and then, as for each of the future guesses, gets a clue telling how close the guess is. A clue consists of two numbers: the number of correct digits (in this case, one: the 2 at the third position) and the additional number of digits guessed correctly but in the wrong place (in this case, two: the 1 and the 3). The clue would in this case be 1/2. For the guess 1110, the clue would be 0/1, since there are no correct digits and only one misplaced digit. (Notice that there is only one digit 1 misplaced.)

Write a program that, given a set of guesses and corresponding clues, tries to find the secret code.

Input Specification

The first line of input specifies the number of test cases N your program has to process. Each test case consists of a first line containing the number of guesses G (0 \le G \le 10), and G subsequent lines consisting of exactly 8 characters: a code of four digits, a blank, a digit indicating the number of correct digits, a /, and a digit indicating the number of correct but misplaced digits.

Output Specification

For each test case, the output contains a single line saying either:

impossible if there is no code consistent with all guesses.

n, where n is the secret code, if there is exactly one code consistent with all guesses.

indeterminate if there is more than one code which is consistent with all guesses.

Sample Input

4
6
9793 0/1
2384 0/2
6264 0/1
3383 1/0
2795 0/0
0218 1/0
1
1234 4/0
1
1234 2/2
2
6428 3/0
1357 3/0

Sample Output

3411
1234
indeterminate
impossible

Comments


  • 1
    MrWoon2010  commented on Feb. 27, 2024, 10:33 a.m. ← edited

    Can someone pls explain when are guesses indeterminate and when are they impossible, with examples? I don't understand this part. Thks


    • 0
      MrWoon2010  commented on Feb. 28, 2024, 2:59 a.m. ← edited

      It's "impossible" if the clues given are not consistent across guesses e.g. the guess of "6428" has 3 in correct positions and yet the next guess of "1357" has also 3 in correct positions with no duplicate numbers across both answers. This is impossible as there must be at least 1 similar digit in both answers for this to happen. So the clues given are "incorrect" and therefore it is impossible to guess the answer. Indeterminate just means there are not enough clues given to solve the puzzle.


  • 0
    mikoSingle  commented on July 6, 2022, 11:52 a.m. ← edited

    not sure how to list out all possibilities given a guess and hints....


  • 0
    Jzaragoza98  commented on June 28, 2022, 5:32 p.m.

    Couldn't 3416 be a possibility for the first example? When writing it out, I see that 6 at index 1 and 3 is a possibility.


    • 0
      MrWoon2010  commented on Feb. 22, 2024, 3:36 a.m. ← edit 2

      Jzaragoza98. 3416 is not a possibility as '6' has been ruled out in line 3, where 4 is the possible answer (based on line 2 and line 5)