There are 5 hints provided to solve the puzzle and we understand that the answer is going to be a 3 digit number. There are a few assumptions that we can make.
- The solution will not have any digits repeat
- The length of solution is 3 digits
Let us represent the problem input using multi-dimension string array as problemData
.
[ 6 8 2 ] // Hint 1: One Number is correct and well placed
[ 6 1 4 ] // Hint 2:One number is correct and wrongly placed
problemData = [ 2 0 6 ] // Hint 3: 2 numbers are correct and wrongly placed
[ 7 3 8 ] // Hint 4: Nothing is correct
[ 7 8 0 ] // Hint 5: One number is correct and wrongly placed
The picture provides hints for solving the puzzle. If you see I ted to do the below steps to get the answer.
Step 1: Get Unique digits Step 2: Get all the possibilities of the all 3-digit numbers Step 3: Filter the possibilities based on hints
Now from the above list we will have these unique digits part of the answers. This will reduce the possibility list from 1000
to 512
. We save almost 49%
in the search of the answers. Account to the input it will be [0, 1, 2, 3, 4, 6, 7, 8]
. The public static String[] findUniqueDigits(String[][] input)
function should do the work. All it does is it runs through the array and stores them into a list and returns them as array of unit array.
Note: Generally java streams are slower than the normal for-loop solutions as the induce a significant overhead by wrapping everything into a wrapper object. In small code this is dismissable but in performant-critical code it may be the best to just use 2 nested for-loop
Now that we have a distinct list of digits we need get the list all possible combinations that could potentially have a solution. The public static void findPossibilities(int maxLength, String[] cell, String curr, Set<String> result)
is a recursive function that will give me all possible combination with the available uniqe digits. This creates 3 digit numbers and adds them to a java.util.Set
so that we don't store duplicates.
When run we have a <Set>
of 512
values that is having potential answer.
Here we are now having 512 possibilities that is having the answer. It is time to apply the rules provided in the hint to get the answer. Before we can run the rules. I had to write couple of utility methods that can apply the rule and give us a boolean response. With these boolean responses we can filter
the results. If you observe the hints and try to convert to functions we get the following assertions.
- How many digits are correct and wrongly positioned
isCorrectWrongPosition
? Can be used for validating Hints 2, 3 and 5 - How many digits are correct and correctly placed
isCorrectWithPosition
? Can be used for Hint 1 - Nothing match
isNothingMatch
. Can be used for Hint 4
Here our objective is to count the number of digits that are common between the given input.
In our problem, the hint for ["6", "8", "2"]
is One Number is correct and well placed and we use isCorrectWrongPosition
method. This takes the following input.
item = "812"
row = [6, 1, 4]
For the above input, this will result in 0
. Even if 1
is common it is in the same position. Thus will not be considered for count.
item = "081"
row = [2, 0, 6]
For the above input, this will result in 1
. As, 0
is a common digit that is present in item
and row
.
The objective for us it to match the digit and the position.
item = "812"
row = [6, 1, 4]
For the above input, this will result in 1
. That is because the digit 1
is in correct position and correct match.
item = "081"
row = [2, 0, 6]
For the above input, this will result in 0
. even if, 0
is a common digit it does not match the position.
Now using java Streams
I am running through the list and applying the hints. This gives me the answer.
Note : I could have potentially used Hint 4 and removed the digits before doing Step 4. I took it to solve in an algorithmic way of applying rules in sequence. That is something I thought about when describing the problem and din't while doing the problem. This is possible suggestion for more aggressive approach.
I have given a try by adding solution description. Please let me know if this makes sense for you. Thanks for your suggestion.