Goal
In this coding challenge, you are tasked with deciphering a series of Mastermind riddles. Mastermind is a classic board game where players deduce a hidden color code through a process of elimination. In this digital version, your task is to efficiently determine the correct color combination based on the provided clues.
Develop an algorithm that accurately deduces the unique solution for each riddle with minimal computational effort.
Brute force solutions may struggle to meet performance requirements.
Rules:
The game involves a grid of nColumns columns and nLines lines of color code guesses.
Each line contains a guess on what the color code is, as nColumns colors represented each by an integer between 0 to nColors – 1.
Next to each guess are the numbers of clues:
- nBlackClues indicates the number of color matches in the correct position (black clues).
- nWhiteClues indicates the number of color matches in incorrect positions (white clues).
Check out the rules of Mastermind if needed: https://en.wikipedia.org/wiki/Mastermind_(board_game)#Gameplay_and_rules
It is guaranteed that there is always one unique solution.
Input
Line 1 nColors: Number of available colors.
Line 2 nColumns: Number of colors in each guess.
Line 3 nLines: Number of guesses.
Next nLines lines each containing, separated by a space:
- colors: a string of nColumns integers ( from 0 to nColors – 1) representing a guess
- nBlackClues: Number of black clues received for that guess.
- nWhiteClues: Number of white clues received for that guess.
Output
Output a string of nColumns integers (0 to nColors – 1) representing the unique solution that satisfies the provided clues.
Constraints
3 ≤ nColors ≤10
3 ≤ nLColumns ≤7
2 ≤ nLines ≤11
Example
Input
3
3
2
002 0 2
101 1 1
