Crack the Code

Description.md

Solution Overview

Problem Statement

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.

1. The solution will not have any digits repeat
2. 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

Solution overview

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

Step 1: Get Unique digits

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

Step 2: Get all the possibilities of the all 3-digit numbers

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.

Step 3: Filter the possibilities based on hints

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.

1. How many digits are correct and wrongly positioned isCorrectWrongPosition? Can be used for validating Hints 2, 3 and 5
2. How many digits are correct and correctly placed isCorrectWithPosition? Can be used for Hint 1
3. Nothing match isNothingMatch. Can be used for Hint 4

isCorrectWrongPosition

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.

Case 1

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.

Case 2

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.

isCorrectWithPosition

The objective for us it to match the digit and the position.

Case 1

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.

Case 2

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.

puzzle.jpg

SolveMMPuzzle.java

import static java.lang.String.format;

import java.util.HashSet;
import java.util.Set;

public class SolveMMPuzzle {
	private static String[][] problemData = { { "6", "8", "2" }, { "6", "1", "4" }, { "2", "0", "6" },
			{ "7", "3", "8" }, { "7", "8", "0" } };

	public static void main(String args[]) {

		// Step 1: Get Unique digits
		String[] uniqueDigits = findUniqueDigits(problemData);

		// Step 2: Get all the possibilities of the all 3-digit numbers
		Set<String> possibilities = new HashSet<>();
		findPossibilities(3, uniqueDigits, "", possibilities);
		System.out.println(format("Found %d unique possibilities", possibilities.size()));

		System.out.print("The final answer is:");
		// Step 3: Filter the possibilities based on hints
		possibilities.stream().filter(item -> isCorrectWithPosition(item, problemData[0]) == 1)
				.filter(item -> isCorrectWrongPosition(item, problemData[1]) == 1)
				.filter(item -> isCorrectWrongPosition(item, problemData[2]) == 2)
				.filter(item -> isNothingMatch(item, problemData[3]))
				.filter(item -> isCorrectWrongPosition(item, problemData[4]) == 1).forEach(System.out::println);
	}

	private static int isCorrectWrongPosition(String item, String[] row) {
		int counter = 0;
		for (int i = 0; i < row.length; i++) {
			if (item.contains("" + row[i].charAt(0)) && item.charAt(i) != row[i].charAt(0)) {
				++counter;
			}
		}

		return counter;
	}

	private static int isCorrectWithPosition(String item, String[] row) {
		int counter = 0;
		for (int i = 0; i < row.length; i++) {
			if (item.charAt(i) == row[i].charAt(0)) {
				++counter;
			}
		}
		return counter;
	}

	private static boolean isNothingMatch(String item, String[] row) {
		return isCorrectWithPosition(item, row) == 0 && isCorrectWrongPosition(item, row) == 0;
	}

	public static String[] findUniqueDigits(String[][] input) {
		Set<String> uniq = new HashSet<>();
		for (String[] row : input) {
			for (String cell : row) {
				uniq.add(cell);
			}
		}

		return uniq.toArray(new String[uniq.size()]);
	}

	public static void findPossibilities(int maxLength, String[] cell, String curr, Set<String> result) {
		if (curr.length() == maxLength) {
			result.add(curr);
		} else {
			for (int i = 0; i < cell.length; i++) {
				String oldCurr = curr;
				curr += cell[i];
				findPossibilities(maxLength, cell, curr, result);
				curr = oldCurr;
			}
		}
	}

}
/* ****************************
Output:
Found 512 unique possibilities
The final answer is:042
**************************** */

I didn't understand the Stream part.

possibilities.stream().filter(item -> isCorrectWithPosition(item, problemData[0]) == 1) .filter(item -> isCorrectWrongPosition(item, problemData[1]) == 1) .filter(item -> isCorrectWrongPosition(item, problemData[2]) == 2) .filter(item -> isNothingMatch(item, problemData[3])) .filter(item -> isCorrectWrongPosition(item, problemData[4]) == 1).forEach(System.out::println);

If you can explain.

When does it have to be true?
possibilities.stream().filter(item -> isCorrectWithPosition(item, problemData[0]) == 1)

When does it have to be true?
possibilities.stream().filter(item -> isCorrectWithPosition(item, problemData[0]) == 1)

Please see the description for isCorrectWithPosition to the notes. I have added more details.

I didn't understand the Stream part.

possibilities.stream().filter(item -> isCorrectWithPosition(item, problemData[0]) == 1) .filter(item -> isCorrectWrongPosition(item, problemData[1]) == 1) .filter(item -> isCorrectWrongPosition(item, problemData[2]) == 2) .filter(item -> isNothingMatch(item, problemData[3])) .filter(item -> isCorrectWrongPosition(item, problemData[4]) == 1).forEach(System.out::println);

If you can explain.

Please see description. It is updated.

I like your efforts, but, some help may be useful:

1. originally you have 720 numbers: 012 to 987, without repeating digits, not 1000 as you stated in "Step 1: Get Unique digits";
2. there a cases when the secret code can contain a digit outside from the set of digits taken from the questions, so it is too early
   to shrink searching area based on how many digits you find in the questions.

I can gladly give you 2 such examples. You can study them, try to crack the code and/or write a program to crack it for you.

Here is the first one (the two-digit answer can be interpreted as two separate digits - for right place and for wrong place):
A 106-10 1 correct digit, 1 right place (0 correct digits in wrong place)
B 184-10 1 correct digit, 1 right place
C 152-00 nothing is correct
D 386-20 2 correct digits, 2 right place
E 786-20 2 correct digits, 2 right place
The secret code is 986. As you see there aren't any questions where 9 takes place.

And the second one: 

A 415-01 1 correct digit, 1 wrong place
B 571-02 2 correct digits, 2 wrong place
C 953-00 nothing is correct
D 168-10 1 correct digit, 1 right place
E 840-00 nothing is correct
The secret code is 127. You can see that 2 was not used in the questions.
These two examples show that it may help if you keep and update statistics
about the usage and eliminations of the digits 0,1,2,3,4,5,6,7,8,9.
I hope this helps.