JavaScript Anzahl der unterschiedlichen Android Pin Muster berechnen?

[xpad.c]

Wenn es für diese Muster tatsächlich möglich ist, von der 1 zur 6 zu gelangen, wird es natürlich ungleich schwieriger, das Ganze zu testen.

Ansonsten folgende Anmerkungen:
1) Du hast Muster der Länge 1 komplett ignoriert, das kannst Du beheben, indem nach dem Hinzufügen von i direkt auf die erreichte Länge testest und - falls erreicht - die Summe um 1 erhöhst. 3x3 mit Länge 1 ergibt dann bspw. in Summe 9 für einmal alle 9 einzelnen Ziffern. Bei Dir bisher 0.
Nochmal Edith: habe das nur so gemacht, weil da noch eine Testausgabe dabei war. Im Prinzip könnte man auch direkt auf (Länge - 1) testen, und das Hinzufügen/Löschen von i dann einfach weglassen.

2) Tests mit Negation sind generell schwierig zu verstehen, zumal das auch noch 2 Negationen sind. Vorschlag: den Test validMove nennen, und die Prüfung auf Vorhandensein in der Menge gleich mit da rein packen.
Edith sagt: ach so, habe noch deltaX und deltaY für die Prüfung der Diagnole bzw. der Richtung verwendet. Damit könnte man ggf. die Winkel und die möglichen anderen Optionen (1->6) auch abdecken, wenn man sich was Cleveres überlegt. Schwierigkeiten hatte ja der Kollege schon genannt.

3) Im Prinzip läuft ja das Setzen von last darauf hinaus, dass man nur die innere Schleife mit fixiertem i hat.
Ich habe daher in der Variante unten dort auch j statt i genommen für den unteren Teil, weniger Verwirrung.
Man könnte da ggf. auch direkt die äußere "Schleife" so fixieren, dann muss den inneren Teil nur einmal schreiben, dafür ist es mir aber jetzt zu spät.

function calcPatterns1(n, len, last = -1, visited = new Set()) {
  if (visited.size == len) {
    return 1;
  }
  let sum = 0;
  if (last == -1) {
    for (let i = 0; i < n * n; i++) {
      visited.add(i); // Start from each cell
      if (visited.size == len) {
        sum += 1;
        visited.delete(i);
        continue;
      }
      for (let j = 0; j < n * n; j++) {
        if (validMove(i, j, n, visited)) {
          visited.add(j);
          sum += calcPatterns1(n, len, j, visited);
          visited.delete(j);
        }
      }
      visited.delete(i);
    }
    return sum;
  }
  for (let j = 0; j < n * n; j++) {
    if (validMove(last, j, n, visited)) {
      visited.add(j);
      sum += calcPatterns1(n, len, j, visited);
      visited.delete(j);
    }
  }
  return sum;
}

function validMove(from, to, n, visited) {
  if (from == to) return false;
  if (visited.has(to)) return false;
  let x1 = parseInt(from / n);
  let y1 = from % n;
  let x2 = parseInt(to / n);
  let y2 = to % n;
  let deltaX = Math.abs(x1 - x2);
  let deltaY = Math.abs(y1 - y2);
  return (deltaX < 2 && deltaY < 2);
}

Nach dem Lesen des anderen Kommentars:
Wenn man mehr als die Diagonalen will, reicht es wahrscheinlich auch nicht, sich die Menge der schon besuchten Knoten zu merken, sondern man braucht das ggf. als Liste. Dann könnte man sich aber auch last sparen, das wäre dann das letzte Element besagter Liste.

HTH,
xpad.c

 

[simpsonsfan]

Ich meinte in dem Fall, dass man bei beliebig großen Gittern zu möglichen Verbindungslinien kommen wird, die eben nur um bspw. 1° von der Verbindungslinie zu einem anderen Punkt abweichen.
Irgnedwann wäre es da in der Praxis nicht mehr sinnvoll, nur die exakt auf der Linie liegenden Punkte zu betrachten.
Bei 3x3 im Quadrat ist das noch recht übersichtlich, es gibt dort nur 5 Ausrichtungen von Geraden, wovon nur 3 zu einer Verschattung führen können. Bei mehr Punkten wird das eben mehr. So liegen bei einem 5x5 (noch nicht bei 4x4 wie von mir zuletzt behauptet) Gitter eben auch die 30° bzw. 60° Linien auf je 3 Punkten.

Ganz davon ab, sehe ich übrigens auch noch nicht, wie du mit der Funktion hasPredecessor die Verschattung bestimmen willst, ohne jeweils die bereits besuchten Knoten mitzugeben. Ich sage dabei nicht, dass das gar nicht geht, ich hab es mir nur nicht überlegt, ob es gehen kann oder nicht.
Denn du musst ja irgendwo wissen, was in deinem Muster schon vorkam. Denn 1-3-2 oder 6-3-1 gehen ja nicht, während aber 2-3-1 oder 2-6-3-1 gehen, weil die 2 dann schon verwendet wird.
Soweit ich das momentan sehe, musst du daher den kompletten Pfad betrachten. Ich kann aber nicht ausschließen, dass es durch sehr geschickte Kombinatorik möglich sein könnte, das auch mit weniger Rechenaufwand zu erschlagen.

 

[n/a]

ohne jeweils die bereits besuchten Knoten mitzugeben. Ich sage dabei nicht, dass das gar nicht geht, ich hab es mir nur nicht überlegt, ob es gehen kann oder nicht.
Denn du musst ja irgendwo wissen, was in deinem Muster schon vorkam

Ich verstehe, dir sind Sackgassen im Sinn ...

Durchaus denkbar, wenn ich mich selber einkreise (man denke an ein Schneckenhaus), dass es dann entweder nicht weitergeht ... oder es sogar in alle Richtungen möglich wäre

Ich schaue's mir morgen noch mal an, heute schon müde

 

[BeBur]

die Verschattung

den kompletten Pfad betrachten

Was ist diese Verschattung? Also bei mir können sich Pfade auch kreuzen. Nur Punkte die diagonal oder horizintal/vertikal zum zuletzt gewählten Punkt funktionieren nicht, aber ansonsten alle.

 

[simpsonsfan]

@BeBur Das ist meine persönliche Begrifflichkeit für das Verhalten, dass Zwischenpunkte auf einer Linie nicht übersprungen werden können.

Wenn du von der 1 zur 9 willst, geht die Linie über die 5. Wenn jetzt die 5 noch nicht im bisherigen Pfad/Muster enthalten war, dann wird vor der 9 zwangsweise die 5 gewählt.

D.h. das Muster 4-1-9 ist nicht auswählbar, weil es automatisch zu 4-1-5-9 wird.
Ergo: die 5 "verschattet" die 9.
Hast du aber die 5 zuvor bereits ausgewählt, dann kommst du von der 1 direkt zur 9, bspw. 5-4-1-9. Daher muss man (vermutlich) tracken, welche Knoten bereits gewählt wurden.

ggf. als Liste. Dann könnte man sich aber auch last sparen, das wäre dann das letzte Element besagter Liste

Genau so hab ich das in dem Python-Code weiter vorne im Thread auch implementiert.