Hintergrund

Ich habe einen einfachen Hindernisparcours konstruiert, indem ich Kisten in einen rechteckigen Raum gestellt habe. Jetzt möchte ich die Anzahl der wesentlich unterschiedlichen Arten zählen, auf die es gelöst werden kann. Du musst mir dafür ein Programm schreiben.

Eingang

Ihre Eingabe ist eine nicht leere rechteckige Anordnung der Zeichen .#. Die Punkte .sind ein leerer Raum und #Hindernisse.

Ein Weg durch den Hindernisparcours beginnt in der oberen linken Ecke und endet in der unteren rechten Ecke und führt nur nach rechts oder unten. Ein gültiger Pfad kann auch kein Hindernis passieren. Hier einige Beispiele, die mit +-Zeichen gezeichnet wurden :

Valid path  Invalid path  Invalid path  Invalid path
++........   ++........    +++++.....    ..+.......
.++++++#..   .+.....#..    ....+++#++    ..++...#..
......+#..   .+.++++#..    .......#.+    ...+++.#..
....#.++++   .+++#.++++    ....#....+    ....#+....

Zwei Pfade sind im Wesentlichen gleich ^1, wenn einer nach dem anderen verschoben werden +kann. Die Zwischenpfade müssen ebenfalls gültig sein, damit Sie einen Pfad nicht über ein Hindernis biegen können. Zum Beispiel sind die ersten beiden Pfade hier im Wesentlichen ähnlich, aber der dritte unterscheidet sich im Wesentlichen von ihnen, da er nicht über die beiden Hindernisse gewackelt werden kann:

++........   +.........   +++++++++.
.+++++.#..   ++.....#..   .......#+.
.....+.#..   .++++++#..   .......#++
....#+++++   ....#.++++   ....#....+

Ausgabe

Ihre Ausgabe ist die Anzahl der wesentlich unterschiedlichen Pfade durch den Hindernisparcours. Mit anderen Worten, wenn alle gültigen Pfade in Klassen von im Wesentlichen ähnlichen Pfaden unterteilt sind, ist die Ausgabe die Anzahl der Klassen. Beachten Sie, dass diese Zahl 0 sein kann, wenn keine gültigen Pfade vorhanden sind.

Regeln und Wertung

Sie können ein vollständiges Programm oder eine Funktion schreiben. Die niedrigste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig. Es gibt keine zeitlichen Beschränkungen, außer dass Sie Ihr Programm in jedem Testfall evaluieren sollten, bevor Sie es einreichen.

Testfälle

....
....
.... => 1

...#
....
...# => 0

#..#
..#.
.... => 0

......
......
..##..
......
...... => 2

......
...#..
......
..#...
#..... => 3

......
..#...
......
....#.
#..... => 4

.......
##.....
....###
...#...
..##.#.
#....#.
..#.... => 0

......#.
..##....
...#....
.......#
....#...
.##...#.
....#...
##...... => 7

.........
.#.#.#.#.
.........
#.#...#.#
.........
.#.#.#.#.
......... => 17

..........
.#........
..........
.....#....
#.........
........#.
......#...
.......... => 10

.........
.#.......
.........
...#.....
.........
.....#...
.........
.......#.
......... => 16

_{1 Der korrekte Fachbegriff lautet "homotopisch" .}

Schnecken , 53 49 Bytes

A^
\.+d!{.l\.+a3(.|~c!~}\.+r!(.u\.+e(.|~},\.,=~d~

Diesmal musste ich tdie gefürchtete Teleportanweisung nicht benutzen . Infolgedessen werden die Testfälle sofort beendet, anstatt Äonen in Anspruch zu nehmen.

Ungolfed:

A^
r\.+
{
    d\.+
    !{ r\.u \.+ a3 (.|~)}
    r\.+
    !{ d\.l \.+ a3 (.|~)}
},
d\.,
!(dr .)

Die Optionen A^beginnen in der oberen linken Ecke und zählen alle übereinstimmenden Pfade. Die Hauptidee besteht darin, einen Kanonizitätszustand für die Pfade zu überprüfen. Ich habe ehrlich gesagt nicht damit gerechnet, dass es funktioniert, aber es hat die Testfälle getroffen, also ... Was es zu überprüfen versucht, ist, dass auf dem aktuellen Pfad die gierigste Route ausgewählt wurde, dh so oft wie möglich richtig , so oft wie möglich runter usw., ohne irgendwelche Hindernisse zu überqueren. Dies geschieht, indem nach ein- oder mehrmaliger Rechtsbewegung und ein oder mehrmaliger Abwärtsbewegung überprüft wird, ob das nächste Feld (das sich rechts befinden muss) nicht erreicht werden konnte, indem im vorherigen rechten Segment ein weiteres Mal nach rechts gegangen wird. Der analoge Zustand wird auch geprüft, nachdem Sie nach rechts und dann nach unten gefahren sind.

Python 2, 170 131 112 Bytes

def f(C,t=1):i="#".join(C).find("#")+1;return([]<C)*(i<1or(i<t
and f([r[i:]for r in C],t-i))+(i>1)*f(C[1:],i-1))

Eine Funktion, fdie den Hindernislauf als eine Liste von Zeilen aufnimmt und die Anzahl der im Wesentlichen unterschiedlichen Pfade zurückgibt.

Erläuterung

Das Grundkonzept ist das Folgende: Wir wählen ein bestimmtes Hindernis aus, o , so dass es keine anderen Hindernisse in der Box gibt, die o und die linke obere Ecke begrenzt.

+--+....
|..|....  
+--#<==== o
.....#..
.#......
........

Wir betrachten dann die beiden Unterkurse östlich und südlich von o . Wir betrachten nur eine dieser Teilstrecken, wenn o tatsächlich von einer Richtung, die zu ihnen führt, gekreuzt werden kann, dh von Norden nach Osten und von Westen nach Süden. Wir lösen das Problem für jeden der ausgewählten Unterkurse und geben die Summe der Ergebnisse zurück. Diese Zahlen entsprechen die Anzahl von im Wesentlichen unterschiedlicher Pfade beim Überschreiten o von links und von rechts, die jeweils damit die beiden resultierenden Sätze von Pfaden sind wesentlich verschieden. Da gibt es keine Hindernisse zwischen dem Startpunkt und ogibt es einen Pfad zwischen dem Startpunkt und einem beliebigen Eintrittspunkt in jede dieser Regionen, und alle derartigen Pfade, die zu demselben Punkt führen, sind im Wesentlichen ähnlich, daher ist die obige Summe die vollständige Anzahl von im Wesentlichen unterschiedlichen Pfaden im gesamten Verlauf.

                               A
_
........       ...|////      |....
........       ...|////      |....
...#....  -->  ...#////  -->  ....
.#....#.       .#..//#/       ..#.
........       ....////       ....

   |                           |
   v                           v
                  B
........       ___
........       .#....#.
___#....  -->  ........  -->   +
/#////#/       
////////       

Etwas kompliziert wird es dadurch, dass der Hindernisparcours allein nicht alle benötigten Informationen vermittelt. Betrachten Sie beispielsweise den Kurs B in der obigen Abbildung. Wir können allein nicht feststellen, ob jedes der Hindernisse von Norden her überquert werden kann. Wenn B waren natürlich die Eingabe, dann, da alle Wege in der oberen linken Ecke beginnen, weder Hindernis aus dem Norden überquert worden sein könnte, aber da wir erreichen können , B von beiden Seiten des linken Hindernisses beim Überqueren o aus dem Osten Wir sollten dieses Hindernis so behandeln, als könne es bei der Lösung des Kurses von Norden her überquert werden. Das gleiche gilt jedoch nicht für das richtige Hindernis, das aus dieser Richtung nicht überwunden werden kann.

Wir konvergieren diese zusätzlichen Informationen, indem wir zusammen mit dem Hindernislauf die Anzahl der Zeichen in der ersten Zeile angeben, beginnend von links, an der der Pfad beginnen kann. In der obigen Abbildung ist dies als durchgezogene Linie neben jedem Kurs dargestellt. Technisch gesehen müssen wir auch die entsprechende Anzahl von Zeichen in der ersten Spalte angeben, ab der der Pfad beginnen kann, wie im Fall von Teilkurs A. In der Praxis haben wir immer das höchste Hindernis ausgewählt, sodass diese Informationen nicht erforderlich sind .

Die tatsächliche Auswahl von o lautet wie folgt: Wir geben vor, dass auf jede andere Zeile als die letzte ein Hindernis folgt (dh mit einem #angehängten Hindernis), und wählen das erste Hindernis im resultierenden Kurs in Lesereihenfolge aus. Für Zeilen (mit Ausnahme der letzten), die ursprünglich kein Hindernis hatten, bedeutet dies effektiv, dass wir sie überspringen (wobei angemerkt wird, dass der Pfad unten bei einem beliebigen Zeichen in der oberen Zeile beginnen kann). Am Ende haben wir einen Kurs mit einer einzigen Reihe ohne Hindernisse, für den es nur einen möglichen Weg gibt.

CJam, 85 84 82 81 80 79 Bytes

qN/:Q,(Qz,(:R_T]2/e~e!{'#Qs@{\(\@>}%s-},{_}{(a\L{@+_@\-_{2$\f.=0fe=2&},}h;}w;],

Probieren Sie es online aus. Oder führen Sie die gesamte Testsuite aus.

Die Effizienz dieser Lösung ist wahrscheinlich ziemlich schrecklich, aber sie löst jeden Testfall innerhalb weniger Sekunden.

Erläuterung

Ich werde später eine vollständige Aufschlüsselung des Codes hinzufügen müssen, aber die algorithmische Idee ist folgende:

• Lassen Sie die Breite und Höhe des Gitters sein Wund H, respectively.
• Wir erzeugen alle möglichen Pfade als die unterschiedlichen Permutationen von W-1Kopien 0und H-1Kopien von W-1(wobei 0ein horizontaler Schritt und W-1ein vertikaler Schritt dargestellt werden). Wir gehen all diese Pfade, indem wir wiederholt das erste Element des Rasters nehmen und dann stepZellen in der Lesereihenfolge (wo stepist 0oder W-1) überspringen . Wir verwerfen alle Pfade, die a enthalten #.
• Dann entfernen wir wiederholt eine Gruppe ähnlicher Pfade (dies sind alle Pfade, die dem ersten der verbleibenden Pfade ähnlich sind). Das Prüfen auf ähnliche Pfade wird ein bisschen einfacher, indem die Bedingung für sie leicht gelockert wird: Anstatt zu prüfen, ob einer xsich bewegt hat, prüfen wir, ob sich die Pfade an genau zwei Stellen unterscheiden. In diesem Fall werden die vertikalen und horizontalen Bewegungen dieser beiden Orte vertauscht. Dies bewirkt, dass das gesamte Segment zwischen diesen Bewegungen um eine Zelle diagonal verschoben wird. Wenn jedoch beide Pfade gültig sind, kann eine diagonale Verschiebung eines Teils des Pfades um eine Zelle ein Hindernis nicht überqueren, sodass sie ähnlich sind. Wir müssen immer noch den transitiven Abschluss finden, also machen wir das so lange, bis wir keine ähnlichen Pfade mehr finden, bevor wir zur nächsten Gruppe übergehen.
• Schließlich zählen wir die Gruppen, die wir gefunden haben und die wir unten im Stapel gelassen haben.