You probably know the game mastermind:
The player tries to guess a code of 4 slots, with 8 possible colors - no duplicates this time. Let's call those colors A through H, so possible solutions could be ABCD or BCHD.
Each time you place a guess, the game master will respond with two information: how many slots you got right, and how many colors you got right but in the wrong place.
If the code is ABCD
and your guess is ACHB
the response 12: the color A is correctly placed, the two colors B&C are in the wrong place.
Code is ABCD
you guess EFGH
response is 00
Code is ABCD
you guess ABCD
response is 40
A full representation would be:
A partial game does not contain the final solution,
nor necessarily enough data to define a unique solution.
An example for an invalid partial game would be:
ABCD03,EFGH02: This would require that 5 colors are present
In essence, all games that cannot have a solution are invalid. The gamemaster made a mistake.
Never trust a game master. Your task is to write a program that takes a partial or full game description and validates whether such a game state is possible.
- Expect that no game description is longer than 8 attempts.
- Expect that the gamemaster can make a mistake on the very first turn, e.g. ABCD41
- The player can make an "invalid" guess to gain further information, e.g. AAAA to check if there is an A at all. Such a game is still valid, you only evaluate the gamemaster's responses. In such a case, exact hit takes precedence over near-misses, for code ABCD it's AAAA10, not AAAA14.
- You can format the input and output in whatever way you see fit, including replacing the colors by digits etc.
- Any pre-generated hashtable counts towards the total number of bytes.
- You know the loophole thing.
The shortest code wins.
Additional test cases:
- ABCD11,ACEG02,HGFE11,CCCC10,CDGH01 => valid
- ABCD01,EFGH03,CGGH11,HGFE21 => valid
- ABCD22,EFGH01,ACDE11 => invalid
- ABCD02,EFGH01,AABB21,AEDH30 => invalid
- ABCD03,DCBA02 => invalid
- ABCD32 => invalid
You can generate any number of valid cases by playing the game. Invalid solutions are hard to come up with. If you find invalid combinations that first slipped through your code, please comment it below for your fellow golfers.
Bonus: Bonus points if you come up with a solution that uses a significantly different approach than generating and traversing all possible permutations.