Code Challenge – Codewars: The Observed Pin


Verbreitet die Message!

Problemstellung

http://www.codewars.com/kata/5263c6999e0f40dee200059d/train/javascript

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 1it 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 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). 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 count on you!

Analyse

  1. Wir brauchen in jedem Fall eine Funktion, die die Nachbarn zu jeder Zahl zurückgibt – ein relativ einfacher switch -Case.
  2. Man kann jede Ziffer von observed (dem mitgegebenen String, der die Beobachteten Werte repräsentiert) einzeln betrachten und dazu dann über die Funktion aus 1. die Teilmengen/Listen/Arrays der möglichen Zahlen zurückbekommen
  3. Jetzt muss man diese Teilmengen irgendwie so verheiraten, dass dort alle Kombinationen enstehen.
  4. Wie sieht es mit Dopplungen aus? Wie filtern wir doppelte Schlüsselkombination heraus? Kann das in unserem Problem eigentlich auftreten?
    Nein, denn die Reihenfolge unserer Kombination ist wichtig – bei einem iterativen Ansatz wird also immer eine eindeutige Kombination erzeugt.

Beispielrechnung und Vorüberlegung

Vereinfachen wir das Problem also mal auf einen PIN der Länge 2.. Am besten die Ziffern „01“.
Unsere Funktion aus 1. liefert ja alle Nachbarn von 0, inkl. der 0 selbst.

Es entstehen also die Mengen {0,8}, sowie {1,2,4}.

Kombinationen für Keypad-Nachbarn

function getKeyPadNeighbours(observedDigit) {
 switch(observedDigit){
   case "1":
   return ["1","2","4"];
   case "2":
   return ["1","2","3","5"];
   case "3":
   return ["2","3","6"];
   case "4":
   return ["1","4","5","7"];
   case "5":
   return ["2","4","5","6","8"];
   case "6":
   return ["3","5","6","9"];
   case "7":
   return ["4","7","8"];
   case "8":
   return ["5","7","8","9","0"];
   case "9":
   return ["6","8","9"];
   case "0":
   return ["0","8"];
 }
}

Kreuzprodukt

Die Erste Ziffer wurde als 0 betrachtet, hätte aber auch eine 8 sein können. Die Zweite Ziffer wurde als 1 betrachtet, hätte aber auch eine 2 oder 4 sein können. So ergeben sich also die Kombinationen: 01, 02, 04, 81,82,84 als alle Möglichen Codes.
Mathematisch kann man das ausdrücken mit dem Kreuzprodukt.

{0,8} x {1,2,4} = {(0,1),(0,2),(0,4),(8,1),(8,2),(8,4)}.

Dieses Kreuzprodukt müssen wir also implementieren – da es in javascript keine Tupel gibt nehmen wir Arrays daher.

function crossProduct(setA, setB){
  var result = [];
  for (var i =0 ; i<setA.length; i++){
    for (var j=0; j<setB.length; j++){
      result.push([setA[i],setB[j]]);
    }
  }
  return result;
} 
// crossProduct([1,2],[3,4]) => [[1, 3], [1, 4], [2, 3], [2, 4]]

Hier iterieren wir über jedes Element der Arrays und fügen dem Ergebnis jede Kombination hinzu.

Doch diese Funktion erzeugt nur Kreuzprodukte für zwei Mengen. Wir brauchen aber eine Funktion die beliebig viele Mengen an Ziffermöglichkeiten annimmt, da wir die genaue Länge des PINS nicht wissen.

Wir könnten aber die Mengen in einem Array speichern und folgenden Iterativen Aufruf programmieren:

  for (var i = 0; i< observed.length; i++){
     currentDigit = observed.charAt(i);
     // Call Function (1) to get the possible Digits as Array
     digitPossibilities.push(getKeyPadNeighbours(currentDigit));
  }

  var iterationSet = [];
  digitPossibilities.forEach(set => {
    iterationSet = crossProduct(iterationSet, set);
  }); 

Wir erwarten: crossProduct ([1,2],[3,4],[5,6] ) = [[1,3,5],[1,3,6],[2,3,5],..,[2,4,6]]

  • In der ersten Iteration müsste gelten:
    • crossProduct ([], [1,2]) = [1,2]
  • In der zweiten Iteration müsste gelten:
    • crossProduct([1,2],[3,4] = [[1, 3], [1, 4], [2, 3], [2, 4]]
  • In der dritten Iteration müsste gelten
    • crossProduct([[1,3], [1,4], [2,3], [2,4]] , [5,6]) = [[1, 3, 5], [1, 4, 5], [2, 3, 5], [2, 4, 5], [1, 3, 6], [1, 4, 6], [2, 3, 6], [2, 4, 6]]

Hier sehen wir bereits, dass der bisherige Algorithmus das nicht leistet. Bisher würde hier ein Array entstehen, dass so aussieht: [[[1, 3], 5], [[1, 4], 5] ,.., [[2, 4], 6]].

Wir müssen also dafür sorgen, dass das innere Array richtig aufgelöst wird. Wenn wir das immer tun, also höchstens eine Verschachtelung haben, können wir das auch bei jeder weiteren Iteration annehmen.

Stattdessen könnten wir aber auch gleich den gewünschten Ausgabe Typ hernehmen und unsere Funktion etwas umschreiben. Statt Arrays als Tupelersatz herzunehmen, generieren wir Strings mit den einzelnen Ziffern.

function crossProduct(setA, setB){
  if  (setA.length===0){
    return setB;
  }
  var result = [];
  for (var i =0 ; i<setA.length; i++){
    for (var j=0; j<setB.length; j++){
      result.push("" + setA[i] + setB[j]);
    }
  }
  return result;
}

Wir merken: Wir haben uns auf dem Weg mit den Arrays etwas selbst Steine in den Weg gelegt, sind aber jetzt fast fertig. Wir können nämlich noch das befüllen der digitPossibilities sparen und die entstehenden Mengen, wie vorher durch digitPossibilities gleich mit verarbeiten.

function getPINs(observed) {
  if (observed.length===1){
    return getKeyPadNeighbours(observed);
  }

  var currentDigit;
  var iterationSet = [];
  for (var i = 0; i < observed.length; i++){
     currentDigit = observed.charAt(i);
     iterationSet = crossProduct(iterationSet, getKeyPadNeighbours(currentDigit));
  }
  return iterationSet;
}

function crossProduct(setA, setB){
  if  (setA.length===0){
    return setB;
  }
  var result = [];
  for (var i =0 ; i<setA.length; i++){
    for (var j=0; j<setB.length; j++){
      result.push(""+setA[i] + setB[j]);
    }
  }
  return result;
}

function getKeyPadNeighbours(observedDigit){
  switch(observedDigit){
    case "1":
    return ["1","2","4"];
    case "2":
    return ["1","2","3","5"];
    case "3":
    return ["2","3","6"];
    case "4":
    return ["1","4","5","7"];
    case "5":
    return ["2","4","5","6","8"];
    case "6":
    return ["3","5","6","9"];
    case "7":
    return ["4","7","8"];
    case "8":
    return ["5","7","8","9","0"];
    case "9":
    return ["6","8","9"];
    case "0":
    return ["0","8"];
  }
}

Wir könnten noch currentDigit löschen, aber es ist besser dies für die Lesbarkeit stehen zu lassen, das kostet uns ohnehin nur konstanten Speicher.

Verbreitet die Message!

Schreiben Sie einen Kommentar