Stimmen sie mit einem Muster, das eine Liste von Längen darstellt, und einer Zeichenfolge, die diese Längen darstellt, überein?
Für Interessenten ist diese Frage gleichbedeutend mit der Überprüfung, ob eine Zeile oder Spalte eines Nonogramms korrekt ist. Ich habe jedoch alle Sprachen, die sich auf Nonogramme beziehen, weggelassen, um die Frage für diejenigen, die mit diesen Rätseln nicht vertraut sind, weniger verwirrend zu machen.
Eingang
Zwei Datenzeilen, durch eine neue Zeile getrennt.
Die erste Zeile ist eine durch Leerzeichen getrennte Liste von Ganzzahlen. Beispiel:
3 6 1 4 6Diese Zeile beschreibt ein Muster von gefüllten Räumen mit einer Größe, die der Ganzzahlliste entspricht, getrennt durch leere Räume unbekannter , positiver Länge, mit denen die zweite Zeile übereinstimmen muss. Am Anfang und am Ende der übereinstimmenden Zeichenfolge können auch Leerzeichen stehen.
Die zweite Zeile ist eine Zeile, die mit dem Muster in Zeile 1 übereinstimmt oder nicht. Es besteht vollständig aus
#,xund_. Es ist garantiert , dass diese Zeile mindestens so lang ist wie die Summe der Ganzzahlen in der ersten Zeile plus der Anzahl der eindeutigen Ganzzahlen minus 1, und sie kann länger sein. In diesem Fall muss die zweite Zeile mindestens(3+6+1+4+6) + (5) - 124 Zeichen lang sein. Hier ist eine 24-stellige Beispielzeile, die dem Muster in der ersten Zeile entspricht:###_######_#_####_######
Bedeutung der Symbole:
#Dies stellt eine gefüllte Box darxDies stellt ein Feld dar, das als "garantiert leer" gekennzeichnet ist._Dies stellt ein unbekanntes / nicht markiertes Kästchen dar.
Tor
Die Idee ist:
- Stellen Sie sicher, dass die zweite Zeile eine gültige Zeile ist, die dem Muster der ersten Zeile entspricht.
- Sie müssen eine eindeutige Fehlermeldung ausgeben (wie Sie sich dafür entscheiden, liegt bei Ihnen; die folgenden Beispiele
ERRORmüssen diese 5 Zeichen nicht enthalten), wenn die unbekannten Leerzeichen entweder nicht ausgefüllt werden können#oderxmit den ersten übereinstimmen Linie.
- Sie müssen eine eindeutige Fehlermeldung ausgeben (wie Sie sich dafür entscheiden, liegt bei Ihnen; die folgenden Beispiele
- Gibt die Indexe mit dem Index Null der Ganzzahlen aus, die vollständig in der Zeile platziert wurden, wobei das Leerzeichen begrenzt ist. Bei Unklarheiten den Index nicht ausdrucken .
Beispiele:
Input: | Output: | Reason:
--------------------------------------------------------------------------
3 6 1 4 6 | 0 1 2 3 4 | This is a complete string that
###x######x#x####x###### | | matches perfectly.
--------------------------------------------------------------------------
1 2 1 | 0 1 2 | There is no ambiguity which filled cells
#____xx___##__x_# | | correspond to which parts of the pattern.
--------------------------------------------------------------------------
1 2 1 | | I don't know whether the filled block is
____#___x | | part of the 1, 2, or 1, so output nothing.
--------------------------------------------------------------------------
1 2 1 | ERROR | The first unknown cell will create a block that
#_#x_# | | matches either 1 1 or 3, but not 1 2.
--------------------------------------------------------------------------
1 2 1 | 0 2 | Even though we know where all the filled cells
#____# | | must be, only 0 and 2 are actually filled here.
--------------------------------------------------------------------------
1 1 1 1 | | There are so many possible ways to do fill this,
__#_______#____ | | we don't know which indices are actually matched.
--------------------------------------------------------------------------
4 4 | | Again, we don't know WHICH 4 is matched here,
______x####________ | | so output nothing.
--------------------------------------------------------------------------
4 4 | 0 | However, here, there's no room for a previous 4,
__x####________ | | so the displayed 4 must be index 0.
--------------------------------------------------------------------------
3 | ERROR | We can't fit a 3 into a space before or after
__x__ | | the x, so this is impossible to match.
--------------------------------------------------------------------------
5 1 3 | 0 | While we can match the 5, we don't know whether
x#####x____#____ | | the single block matches the 1 or the 3.
--------------------------------------------------------------------------
3 2 3 | 1 | The two has been completely placed,
____##x##____ | | even though we don't know which it is.
Regeln:
Sie können ein Programm oder eine Funktion schreiben , die die Eingabe als durch Zeilenumbrüche begrenzte Zeichenfolge oder von STDIN (oder der nächstgelegenen Alternative) empfängt und die Ausgabe als durch Leerzeichen begrenzte Zeichenfolge zurückgibt oder an STDOUT (oder die nächstgelegene Alternative) ausgibt. Optional können Sie eine einzelne nachgestellte Newline in die Ausgabe aufnehmen.
Außerdem sind Standard-Lücken, die nicht mehr lustig sind, verboten .
quelle
Antworten:
Perl, 134 Bytes
(beinhaltet 1 Schalter)
Nimmt zwei Eingabezeilen von STDIN auf. Muss für jede Eingabe erneut ausgeführt werden.
Die Idee ist, zuerst alle möglichen Muster zu extrahieren, die mit den angegebenen Längen übereinstimmen. Wenn wir zum Beispiel die Längen
1 2und das Muster haben#_x_#_, dann sind die passenden Muster(#, _#)und(#, #_). Verketten Sie dann die übereinstimmenden Muster für jeden Index - im Beispiel ist das Ergebnis die Liste(##, _##_). Drucken Sie nun die Indizes aller Zeichenfolgen in der Liste, die nur '#' Zeichen enthalten.Ich habe die Methode, um alle möglichen Übereinstimmungen aus einem regulären Ausdruck in Perl hier zu extrahieren .
quelle