مساله:
بسیار خوب، کارآگاه، یکی از همکاران ما با موفقیت توانست شخص هدف ما، رابی دزد را مشاهده کند. ما به دنبال او به یک انبار مخفی رفتیم ، جایی که فرض می کنیم همه چیزهای دزدیده شده را در آن پیدا می کنیم. درب این انبار توسط قفل ترکیبی الکترونیکی محکم می شود. متاسفانه، جاسوس ما هنگامی که رابی داشته PIN را وارد می کرده به درستی ندیده است.
صفحه کلید به صورت طرح زیر است:
او PIN که دیده است عدد 1357 است ولی همچنین گفت که ممکن است هر یک از ارقام مشاهده شده، رقم مجاور آن باشد(به صورت افقی و عمودی نه به صورت مورب). به عنوان مثال. به جای 1 می تواند 2 یا 4 باشد. و به جای 5 نیز می تواند 2 ، 4 ، 6 یا 8 باشد.
او همچنین گفت که این قفل ها را میشناسد، شما می توانید مقدار نامحدودی PIN اشتباه را وارد کنید، آنها هرگز سیستم را قفل نمی کنند و یا آژیر خطر را به صدا در نمی آورند. به همین دلیل است که می توانیم همه تغییرات ممکن (*) را امتحان کنیم.
از نظر ممکن*: PIN مشاهده شده خود و همه تغییرات با توجه به ارقام مجاور
آیا می توانید به ما کمک کنید تا همه این تغییرات را پیدا کنیم؟ خوب است که تابعی داشته باشید که یک آرایه (یا لیستی در جاوا و C #) از همه تغییرات را برای یک پین مشاهده شده به طول 1 تا 8 رقم بازگرداند. ما می توانیم از تابع getPIN استفاده کنیم (get_pins در پایتون ، GetPIN ها در #C ). اما لطفا توجه داشته باشید که همه پین ها ، یک مشاهده و همچنین نتایج ، باید رشته باشند ، زیرا به طور بالقوه منجر به “0” می شود. ما قبلاً موارد آزمایشی را برای شما آماده کردیم.
کارآگاه ، ما روی شما حساب می کنیم!
Alright, detective, one of our colleagues successfully observed our target person, Robby the robber. We followed him to a secret warehouse, where we assume to find all the stolen stuff. The door to this warehouse is secured by an electronic combination lock. Unfortunately our spy isn’t sure about the PIN he saw, when Robby entered it.
The keypad has the following layout:
He noted the PIN 1357, but he also said, it is possible that each of the digits he saw could actually be another adjacent digit (horizontally or vertically, but not diagonally). E.g. instead of the 1 it could also be the 2 or 4. And instead of the 5 it could also be the 2, 4, 6 or 8.
He also mentioned, he knows this kind of locks. You can enter an unlimited amount of wrong PINs, they never finally lock the system or sound the alarm. That’s why we can try out all possible (*) variations.
* possible in sense of: the observed PIN itself and all variations considering the adjacent digits
Can you help us to find all those variations? It would be nice to have a function, that returns an array (or a list in Java and C#) of all variations for an observed PIN with a length of 1 to 8 digits. We could name the function getPINs (get_pins in python, GetPINs in C#). But please note that all PINs, the observed one and also the results, must be strings, because of potentially leading ‘0’s. We already prepared some test cases for you.
Detective, we are counting on you!
For C# user: Do not use Mono. Mono is too slower when run your code.
import java.util.*;
public class ObservedPin {
private static final Map<Character,String> ADJACENTS = new HashMap<Character,String>() {{
put('1', "124");
put('2', "2135");
put('3', "326");
put('4', "4157");
put('5', "54268");
put('6', "6953");
put('7', "748");
put('8', "87590");
put('9', "986");
put('0', "08");
}};
public static List<String> getPINs(String observed) {
List<String> ans = Arrays.asList("");
for (char c: observed.toCharArray()) {
List<String> tmp = new ArrayList<String>();
for (char cc: ADJACENTS.get(c).toCharArray()) {
for (String s: ans) tmp.add(s+cc);
}
ans = tmp;
}
return ans;
}
}import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class ObservedPin {
static Map<Character,String> map = new HashMap<>();
public static List<String> getPINs(String observed) {
List<String> pins = new ArrayList<>();
map.put('1',"124");
map.put('2',"1235");
map.put('3',"236");
map.put('4',"1457");
map.put('5',"24568");
map.put('6',"3569");
map.put('7',"478");
map.put('8',"05789");
map.put('9',"689");
map.put('0',"08");
fillPins(observed,"",0,pins);
return pins;
}
public static void fillPins (String observed, String current, int index, List<String> pins){
String possibilities = map.get(observed.charAt(index));
for (char c : possibilities.toCharArray()
) {
if(index<observed.length()-1){
fillPins(observed,current+c,index+1,pins);
} else {
pins.add(current+c);
}
}
}
} // ObservedPin
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class ObservedPin {
public static List<String> getPINs(String observed) {
return Arrays.stream(observed.split(""))
.map(Integer::parseInt)
.map(ObservedPin::neighbors)
.reduce(ObservedPin::product).get();
}
private static List<String> product(List<String> lefts, List<String> rights) {
return lefts.stream()
.flatMap(s -> rights.stream().map(j -> s + j))
.collect(Collectors.toList());
}
private static List<String> neighbors(int i) {
switch (i) {
case 1: return Arrays.asList("1", "2", "4");
case 2: return Arrays.asList("1", "2", "3", "5");
case 3: return Arrays.asList("2", "3", "6");
case 4: return Arrays.asList("1", "4", "5", "7");
case 5: return Arrays.asList("2", "4", "5", "6", "8");
case 6: return Arrays.asList("3", "5", "6", "9");
case 7: return Arrays.asList("4", "7", "8");
case 8: return Arrays.asList("5", "7", "8", "9", "0");
case 9: return Arrays.asList("6", "8", "9");
case 0: return Arrays.asList("8", "0");
}
return null;
}
}import java.util.*;
import java.util.stream.*;
public class ObservedPin {
private static Map<String, String[]> adjacentMap = new HashMap<>();
static {
adjacentMap.put("1", new String[]{"1", "2", "4"});
adjacentMap.put("2", new String[]{"1", "2", "3", "5"});
adjacentMap.put("3", new String[]{"2", "3", "6"});
adjacentMap.put("4", new String[]{"1", "4", "5", "7"});
adjacentMap.put("5", new String[]{"2", "4", "5", "6", "8"});
adjacentMap.put("6", new String[]{"3", "5", "6", "9"});
adjacentMap.put("7", new String[]{"4", "7","8"});
adjacentMap.put("8", new String[]{"5", "7", "8", "9", "0"});
adjacentMap.put("9", new String[]{"6", "8", "9"});
adjacentMap.put("0", new String[]{"8", "0"});
}
public static List<String> getPINs(String observed) {
List<String> combinations = new ArrayList<>();
combinations.add("");
for(char c : observed.toCharArray()){
combinations = cartesianProductOfStrings(combinations.toArray(new String[combinations.size()]), adjacentMap.get(Character.toString(c)));
}
return combinations.stream().collect(Collectors.toList());
} // getPINs
private static List<String> cartesianProductOfStrings(String[] strings1, String[] strings2){
List<String> result = new ArrayList<>();
for(String s1 : strings1){
for(String s2 : strings2){
result.add(s1+s2);
}
}
return result;
}
} // ObservedPin
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;
public class ObservedPin {
private static final Map<Character, Set<Character>> adjacent = new HashMap<>();
static {
adjacent.put('1', new HashSet<>(Arrays.asList('1', '2', '4')));
adjacent.put('2', new HashSet<>(Arrays.asList('1', '2', '3', '5')));
adjacent.put('3', new HashSet<>(Arrays.asList('2', '3', '6')));
adjacent.put('4', new HashSet<>(Arrays.asList('1', '4', '5', '7')));
adjacent.put('5', new HashSet<>(Arrays.asList('2', '4', '5', '6', '8')));
adjacent.put('6', new HashSet<>(Arrays.asList('3', '5', '6', '9')));
adjacent.put('7', new HashSet<>(Arrays.asList('4', '7', '8')));
adjacent.put('8', new HashSet<>(Arrays.asList('5', '7', '8', '9', '0')));
adjacent.put('9', new HashSet<>(Arrays.asList('6', '8', '9')));
adjacent.put('0', new HashSet<>(Arrays.asList('8', '0')));
}
public static List<String> getPINs(String observed) {
List<Set<Character>> possibles = observed.chars()
.mapToObj(c -> (char) c)
.map(adjacent::get)
.collect(Collectors.toList());
Set<List<Character>> allCombinations = getAllCombinations(possibles);
return allCombinations.stream()
.map(ObservedPin::convertToString)
.collect(Collectors.toList());
}
private static Set<List<Character>> getAllCombinations(List<Set<Character>> listOfCharSets) {
Set<List<Character>> result = new HashSet<>();
getAllCombinationsHelper(listOfCharSets, result, 0, new ArrayList<>());
return result;
}
private static void getAllCombinationsHelper(List<Set<Character>> listOfCharSets,
Set<List<Character>> result, int depth, List<Character> current) {
if (depth == listOfCharSets.size()) {
result.add(current);
return;
}
for (Character c : listOfCharSets.get(depth)) {
List<Character> forNextRecursion = new ArrayList<>(current);
forNextRecursion.add(c);
getAllCombinationsHelper(listOfCharSets, result, depth + 1, forNextRecursion);
}
}
private static String convertToString(List<Character> characters) {
return characters.stream().map(Object::toString).collect(Collectors.joining());
}
}import java.util.ArrayList;
import java.util.List;
public class ObservedPin {
public static final String[] numbres= new String[]{"8","24","531","26","157","2648","359","48","5790","68"};
public static List<String> getPINs(String observed) {
List<String> list=new ArrayList<>();
list.add(observed);
return observed==null||observed.isEmpty() ? null : generate(list,observed.length()-1);
}
private static List<String> generate(List<String> list,int i){
if(i<0)
return list;
ArrayList<String> list1=new ArrayList<>();
for(String s:list){
char [] chars=s.toCharArray();
char [] chars1=numbres[Integer.parseInt(String.valueOf(chars[i]))].toCharArray();
for(char c:chars1) {
chars[i] = c;
list1.add(String.valueOf(chars));
}}
for(String s:list1)
list.add(s);
return generate(list,i-1);
}
}
import java.util.*;
import java.util.stream.IntStream;
public class ObservedPin {
private static final char[][] VARIATIONS = new char[10][];
static {
IntStream.range(0, 10)
.forEach(i -> VARIATIONS[i] = IntStream.range(0, 10).filter(j -> adjacent(i, j))
.mapToObj(Integer::toString).reduce("", String::concat).toCharArray());
}
private static boolean adjacent(int i, int j) {
if (i == j)
return true;
if (i == 0 || j == 0)
return i + j == 8;
int d = Math.abs(i - j);
return d == 3 || d == 1 && Math.min(i, j) % 3 != 0;
}
public static List<String> getPINs(String observed) {
int n = observed.length();
if (n == 0)
return Collections.singletonList("");
List<String> partialPINs = getPINs(observed.substring(0, n - 1));
char[] lastDgtVars = VARIATIONS[observed.charAt(n - 1) - '0'];
List<String> result = new ArrayList<>(partialPINs.size() * lastDgtVars.length);
for (String pin : partialPINs)
for (char d : lastDgtVars)
result.add(pin + d);
return result;
}
}import java.util.*;
public class ObservedPin {
public static ArrayList<String> combinations;
public static List<String> getPINs(String observed) {
combinations = new ArrayList<>();
String[] digits = observed.split("");
// print(digits, "digits ");
populateCombinations("", digits);
// print(combinations, "result");
return combinations;
}
public static void populateCombinations(String prefix, String[] digits) {
if (digits.length == 0) {
combinations.add(prefix);
return;
}
String t = digits[0];
String[] alternatives = alternatives(t);
// print(alternatives, "Alternative of " + t);
digits = Arrays.copyOfRange(digits, 1, digits.length);
for (int i = 0; i < alternatives.length; i++) {
populateCombinations(prefix + alternatives[i], digits);
}
}
public static String[] alternatives(String digit) {
int d = Integer.parseInt(digit);
int[][] m = {{8}, {2, 4}, {1, 5, 3}, {2, 6}, {1, 5, 7}, {2, 4, 6, 8}, {3, 5, 9}, {4, 8}, {7, 5, 0, 9}, {6, 8}};
int[] digits = m[d];
String[] res = new String[digits.length + 1];
res[0] = String.valueOf(d);
for (int i = 1; i < res.length; i++)
res[i] = String.valueOf(digits[i - 1]);
return res;
}
public static void print(ArrayList<String> arr) {
print(arr.toArray(), "");
}
public static void print(ArrayList<String> arr, String s) {
print(arr.toArray(), s);
}
public static void print(Object[] arr) {
print(arr, "");
}
public static void print(Object[] arr, String s) {
System.out.print(s + ": ");
for (Object el : arr) {
System.out.print(el + ", ");
}
System.out.println();
}
}
import java.util.List;
import java.util.ArrayList;
public class ObservedPin {
public static ArrayList<String> getOption(int value) {
ArrayList<String> outList = new ArrayList<>();
switch (value) {
case 1:
outList.add("1");
outList.add("2");
outList.add("4");
break;
case 2:
outList.add("1");
outList.add("2");
outList.add("3");
outList.add("5");
break;
case 3:
outList.add("2");
outList.add("3");
outList.add("6");
break;
case 4:
outList.add("1");
outList.add("4");
outList.add("5");
outList.add("7");
break;
case 5:
outList.add("2");
outList.add("4");
outList.add("5");
outList.add("6");
outList.add("8");
break;
case 6:
outList.add("3");
outList.add("5");
outList.add("6");
outList.add("9");
break;
case 7:
outList.add("4");
outList.add("7");
outList.add("8");
break;
case 8:
outList.add("5");
outList.add("7");
outList.add("8");
outList.add("9");
outList.add("0");
break;
case 9:
outList.add("6");
outList.add("8");
outList.add("9");
break;
case 0:
outList.add("8");
outList.add("0");
break;
}
return outList;
}
public static List<String> getPINs(String observed) {
ArrayList<ArrayList<String>> data = new ArrayList<ArrayList<String>>();
ArrayList<String> first = new ArrayList<String>();
ArrayList<String> outString = new ArrayList<String>();
for (int i = 0; i < observed.length(); i++) {
data.add(getOption(Integer.parseInt(observed.substring(i, i+1))));
}
first = data.get(0);
for (int i = 1; i < data.size(); i++) {
for (String j : first) {
for (String k : data.get(i)) {
outString.add(j + k);
}
}
first.clear();
first = (ArrayList<String>) outString.clone();
outString.clear();
}
return first;
}
}
