Ich habe vor kurzem ein wirklich seltsames unregelmäßiges Schachbrett bekommen. Die Plätze sind überall und nicht einmal alle miteinander verbunden. Zumindest sind sie noch in einem regelmäßigen Raster angeordnet. Ich möchte die Schachregeln anpassen, um auf dem Brett spielen zu können, aber zunächst brauche ich eine Figur, die eigentlich überall auf dem Brett eingesetzt werden kann, und es scheint, als wäre ein Sprung meine beste Wahl dafür.

Leapers sind die feenhafte Verallgemeinerung von Rittern. Leapers werden durch zwei ganze Zahlen m und n parametrisiert und können m Quadrate in eine Richtung und dann weitere n Quadrate in jede senkrechte Richtung bewegen . Für den Standardritter gilt (m, n) = (2, 1) . Die gesamte Bewegung wird als ein einziger Sprung betrachtet, sodass keines der Felder auf dem Weg zum Ziel leer sein muss oder überhaupt existiert.

Die Herausforderung

Sie erhalten ein "Schachbrett" in Form einer Liste von positiven 2D-Ganzzahlkoordinaten, die die Quadrate darstellen, die Teil des Brettes sind. Ihre Aufgabe ist es, einen Springer zu finden, der bei ausreichenden Zügen ein beliebiges Feld auf dem Brett erreichen kann.

Schauen wir uns einige Beispiele an. Das Standardschachbrett verwendet ein regelmäßiges Raster von 8x8 Feldern (beachten Sie, dass wir bei dieser Herausforderung nicht zwischen weißen und schwarzen Feldern unterscheiden):

########
########
########
########
########
########
########
########

Der Standardritter kann alle erreichen, (2, 1)wäre also eine gültige Ausgabe. Allerdings (1, 1)würde beispielsweise nicht gültig sein, da ein solches Stück nur die Hälfte der Plätze erreichen kann , egal wo es beginnt. (1, 0)Andererseits wäre auch eine gültige Ausgabe, da alle Quadrate orthogonal verbunden sind.

Wenn wir nun ein unregelmäßiges Board haben, wie:

#   #
 # # #
  # # #
 # #
    #

Dann sind mögliche Lösungen (1, 1)und (3, 1). Wir können auch ein Board mit völlig getrennten Regionen haben, wie:

#### ####
#### ####
#### ####
#### ####

Der Standardritter (2, 1)kann hier immer noch alle Felder erreichen, was in der Tat die einzige Lösung ist.

Und schließlich kann die folgende einfache Tafel von keinem Springer vollständig erreicht werden:

#
 ##

Beachten Sie, dass das Eingabeformat keine ASCII-Darstellung ist, sondern eine Liste von Koordinaten. ZB könnte das zweite obige Beispiel wie folgt lauten:

[[1, 1], [5, 1], [2, 2], [4, 2], [6, 2], [3, 3], [5, 3], [7, 3], [2, 4], [4, 4], [5, 5]]

Regeln

Sie können ein Programm oder eine Funktion schreiben, indem Sie eine Eingabe über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) ausgeben.

Die Eingabekoordinaten können in jedem geeigneten Listenformat (flache Liste, Liste von Paaren, Liste komplexer Ganzzahlen, Zeichenfolge mit konsistenten Trennzeichen usw.) eingegeben werden.

Die Ausgabe sollte die zwei Ganzzahlen m und n sein , die den Leaper identifizieren, wenn eine Lösung vorhanden ist (als zwei separate Ganzzahlen, eine Liste, eine Zeichenfolge mit nicht numerischem Trennzeichen usw.). Wenn keine Lösung vorhanden ist, können Sie einen beliebigen konsistenten Wert ausgeben, der möglicherweise kein gültiger Anhaltspunkt sein kann. Dies schließt das Paar von Ganzzahlen (0, 0)in Ihrem normalen Format sowie alles ein, was kein Paar von nicht negativen Ganzzahlen ist.

Ihr Programm muss alle Testfälle innerhalb einer Minute bearbeiten . Dies ist eine etwas unscharfe Einschränkung, aber verwenden Sie den gesunden Menschenverstand: Wenn es auf Ihrem Computer 2 Minuten dauert, können wir davon ausgehen, dass es auf einem anderen Computer innerhalb von 1 ausgeführt wird, aber wenn es 20 Minuten dauert, ist dies weniger wahrscheinlich. Es sollte nicht schwer sein, jeden Testfall in Sekundenschnelle zu lösen. Diese Regel schließt also nur naive Gewalt aus.

Es gelten die Standardregeln für Code-Golf .

Testfälle

Jeder Testfall hat die Form board => all valid leapers. Denken Sie daran, dass Sie nur einen davon ausgeben müssen. Wenn die Liste der Leaper leer ist, stellen Sie sicher, dass Sie etwas zurückgeben, das kein gültiger Leaper ist.

Examples above:
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [3, 7], [3, 8], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [4, 7], [4, 8], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [5, 8], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6], [6, 7], [6, 8], [7, 1], [7, 2], [7, 3], [7, 4], [7, 5], [7, 6], [7, 7], [7, 8], [8, 1], [8, 2], [8, 3], [8, 4], [8, 5], [8, 6], [8, 7], [8, 8]] => [[0, 1], [1, 2], [1, 4], [2, 3], [3, 4]]
[[1, 1], [5, 1], [2, 2], [4, 2], [6, 2], [3, 3], [5, 3], [7, 3], [2, 4], [4, 4], [5, 5]] => [[1, 1], [1, 3]]
[[1, 1], [2, 2], [3, 2]] => []
[[1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [3, 1], [3, 2], [3, 3], [3, 4], [4, 1], [4, 2], [4, 3], [4, 4], [6, 1], [6, 2], [6, 3], [6, 4], [7, 1], [7, 2], [7, 3], [7, 4], [8, 1], [8, 2], [8, 3], [8, 4], [9, 1], [9, 2], [9, 3], [9, 4]] => [[1, 2]]

Square boards:
[[1, 1], [1, 2], [2, 1], [2, 2]] => [[0, 1]]
[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]] => [[0, 1]]
[[1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [3, 1], [3, 2], [3, 3], [3, 4], [4, 1], [4, 2], [4, 3], [4, 4]] => [[0, 1], [1, 2]]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5]] => [[0, 1], [1, 2]]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6]] => [[0, 1], [1, 2], [2, 3]]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [3, 7], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [4, 7], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6], [6, 7], [7, 1], [7, 2], [7, 3], [7, 4], [7, 5], [7, 6], [7, 7]] => [[0, 1], [1, 2], [2, 3]]

Miscellaneous:
[[1, 1], [2, 1]] => [[0, 1]]
[[1, 1], [1, 2]] => [[0, 1]]
[[1, 1], [12, 35]] => [[11, 34]]
[[1, 1], [1, 2], [2, 1], [2, 2], [6, 1], [6, 2], [6, 3], [6, 4], [7, 1], [7, 2], [7, 3], [7, 4], [8, 1], [8, 2], [8, 3], [8, 4], [9, 1], [9, 2], [9, 3], [9, 4]] => []
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [3, 1], [3, 2], [3, 5], [3, 6], [4, 1], [4, 2], [4, 5], [4, 6], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6]] => [[0, 1], [1, 2], [1, 4]]
[[2, 2], [2, 4], [2, 6], [2, 8], [4, 2], [4, 4], [4, 6], [4, 8], [6, 2], [6, 4], [6, 6], [6, 8], [8, 2], [8, 4], [8, 6], [8, 8]] => [[0, 2], [2, 4]]

Random boards:
[[1, 5], [1, 9], [2, 6], [2, 8], [2, 10], [2, 12], [3, 5], [3, 7], [3, 9], [3, 11], [3, 13], [4, 2], [4, 4], [4, 6], [4, 8], [4, 14], [5, 1], [5, 3], [5, 5], [5, 7], [6, 2], [6, 4], [7, 1], [8, 2]] => [[1, 1], [1, 3]]
[[1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 1], [2, 2], [2, 3], [2, 4], [2, 7], [3, 1], [3, 2], [3, 3], [3, 4], [3, 6], [3, 7], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [5, 3], [5, 4], [5, 6]] => [[0, 1], [1, 2]]
[[1, 8], [2, 6], [2, 10], [3, 3], [3, 4], [3, 8], [4, 1], [4, 11], [5, 3], [5, 9], [6, 12], [8, 11], [10, 10], [11, 12], [12, 6], [12, 8], [13, 6], [13, 8], [13, 10], [13, 11], [14, 5], [14, 7], [14, 8], [14, 13], [14, 14], [15, 7], [15, 9], [15, 11], [15, 12], [16, 6], [16, 7], [16, 9], [16, 13], [16, 14], [17, 10], [17, 12], [18, 8], [18, 12], [20, 9], [21, 11], [22, 13], [23, 10], [23, 11], [23, 15], [24, 12]] => [[1, 2]]
[[1, 17], [1, 21], [3, 11], [3, 15], [3, 19], [3, 23], [5, 13], [5, 21], [7, 11], [7, 15], [7, 19], [9, 1], [9, 13], [9, 17], [11, 3], [11, 7], [11, 15], [11, 19], [13, 5], [13, 9], [13, 13], [13, 17], [13, 21], [15, 11], [15, 15], [15, 19], [17, 13], [17, 17]] => [[2, 2], [2, 6], [2, 10]]
[[1, 3], [2, 4], [2, 5], [3, 6], [4, 1], [5, 3], [5, 6], [5, 7], [6, 12], [6, 14], [6, 21], [7, 9], [7, 19], [8, 9], [8, 15], [8, 17], [8, 18], [8, 24], [9, 12], [9, 19], [10, 12], [10, 14], [10, 17], [10, 21], [11, 22], [12, 15], [12, 17], [12, 24], [13, 16], [14, 20], [14, 21], [14, 26], [15, 13], [15, 19], [16, 18], [16, 23], [17, 16], [17, 24]] => [[2, 3]]
[[1, 11], [3, 13], [4, 10], [6, 14], [8, 12], [9, 9], [9, 15], [12, 8], [13, 5], [13, 19], [13, 21], [14, 8], [15, 1], [15, 17], [16, 4], [16, 14], [16, 18], [16, 20], [17, 21], [18, 2], [18, 16], [18, 18], [19, 9], [19, 13], [19, 15], [20, 12], [21, 1], [21, 17], [22, 4], [22, 10], [23, 7]] => [[1, 3]]
[[1, 39], [6, 37], [8, 32], [10, 27], [11, 31], [11, 35], [12, 22], [16, 21], [16, 29], [16, 33], [18, 34], [21, 3], [21, 9], [21, 19], [23, 8], [23, 14], [23, 22], [23, 24], [23, 36], [24, 6], [25, 13], [25, 17], [26, 1], [26, 11], [28, 6], [28, 20], [28, 26], [28, 30], [28, 34], [30, 11], [30, 15], [30, 21], [32, 6], [33, 28], [33, 32], [35, 13], [35, 23]] => [[2, 5]]

Beachten Sie als Sonderfall, dass für eine Karte, die nur aus einer Zelle besteht, ein beliebiger Leaper funktioniert, Ihre Ausgabe jedoch einem tatsächlichen Leaper entsprechen muss und daher [0, 0]keine gültige Ausgabe ist.

Pyth, 41 35

hfqQu@+G+VM*s_BM*F_BMTGQ]hQ)maVhQdt

Wird bei einem Fehler beendet, wenn keine gültigen Leaper vorhanden sind, und gibt die leere Zeichenfolge an, wenn STDERR ignoriert wird.

Probieren Sie es hier aus oder führen Sie eine Test Suite aus

6 Bytes gespart dank isaacg ! Grundsätzlich werden nur alle Leaper-Kandidaten gefunden, indem jeder gültige Leaper von der ersten Kachel zur anderen Kachel ausgewählt wird. Dann werden für jedes dieser Elemente alle acht Konfigurationen von [x, y]Offsets erstellt, die der Leaper annehmen könnte. Es findet dann alle Züge ab dem ersten Feld, das nach dem Zug folgt, und verwirft diejenigen, die nicht in der Eingabe enthalten sind. Dies geschieht so lange, bis sich das Ergebnis nicht mehr ändert. Wenn diese endgültige Liste mit der Eingabe identisch ist, war der Leaper gültig.

Das Standard-Schachbrett hat beim Testen am längsten gedauert, auf meinem nicht sehr beeindruckenden Computer dauerte es ungefähr 3 Sekunden.