Jede Woche verschickt Mohammad S. Anwar die Weekly Challenge, eine Chance für uns alle, Lösungen für zwei wöchentliche Aufgaben zu finden. Meine Lösungen werden zunächst in Python geschrieben und dann in Perl konvertiert. Es ist eine großartige Möglichkeit für uns alle, etwas Codierung zu üben.
Herausforderung, meine Lösungen
Sie erhalten eine Zeichenfolge aus alphabetischen Zeichen, $chars.
Schreiben Sie ein Skript, um die Zeichenfolge mit Lauflängenkodierung zu komprimieren, wie in den Beispielen gezeigt.
Eine komprimierte Einheit kann entweder ein einzelnes Zeichen oder eine Anzahl gefolgt von einem Zeichen sein.
BONUS: Schreiben Sie eine Dekomprimierungsfunktion.
Dank der Leistungsfähigkeit regulärer Ausdrücke ist dies eine ziemlich einfache Aufgabe. Sowohl Python als auch Perl erlauben, dass der Ersatzwert eine Funktion ist. Deshalb habe ich eine Funktion namens sc, die mehrere Buchstaben in eine Zahl und den Buchstaben umwandelt. Wenn die Eingabe beispielsweise aaa wäre, würde 3a zurückgegeben.
def sc(match):
m = match.group(0)
return str(len(m)) + m[0]
Dann geht es darum, diese Funktion je nach Bedarf aufzurufen.
def string_compress(s: str) -> str:
return re.sub(r'(([a-z])+)', sc, s)
Die Dekomprimierungsfunktion (nur Python) funktioniert auf ähnliche Weise. Es nimmt ein Muster aus einer Zahl, gefolgt von einem Buchstaben, und wandelt es in den Buchstaben um, der die angegebene Anzahl von Vorkommen wiederholt.
def usc(match):
m = match.group(0)
return m[-1] * int (m[:-1])
def string_decompress(s: str) -> str:
return re.sub(r'(\d+[a-z])', usc, s)
Für die Ausführung über die Befehlszeile verwende ich das argparse-Modul, um zu sehen, ob die Option --decompress angegeben ist.
def main():
parser = argparse.ArgumentParser()
parser.add_argument("--decompress", help="decompress the input", action='store_true')
parser.add_argument("str", help="the string to compress/decompress")
args = parser.parse_args()
if args.decompress:
result = string_decompress(args.str)
else:
result = string_compress(args.str)
print(result)
$ ./ch-1.py abbc a2bc $ ./ch-1.py aaabccc 3ab3c $ ./ch-1.py abcc ab2c $ ./ch-1.py --decompress a2bc abbc $ ./ch-1.py --decompress 3ab3c aaabccc $ ./ch-1.py --decompress ab2c abcc
Sie erhalten ein Array von Ganzzahlen, @ints.
Schreiben Sie ein Skript, um herauszufinden, ob es möglich ist, ein Quadrat mit den Stäben wie im angegebenen Array @ints zu bilden, wobei $ints[ì] die Länge des i-ten Stäbchens ist.
Das wird etwas lang, also schnallen Sie sich an. Das erste, was ich überprüfe, ist, dass die Summe der Stöcke durch vier teilbar ist. Wenn dies nicht der Fall ist, gibt es keine mögliche Lösung und ich kann false
zurückgebenIch kann auch überprüfen, dass kein einzelner Stock länger als eine Seite ist. In diesem Fall gebe ich auch false zurück.
Mit diesen beiden Prüfungen würden alle Beispiele das richtige Ergebnis liefern. Allerdings wird fälschlicherweise berichtet, dass 4 3 3 3 3 wahr ist, obwohl dies in Wirklichkeit nicht der Fall ist.
Als ich mir die Beispiele und meine eigenen Gedanken ansah, dachte ich, dass die Lösung darin bestünde, ein Wertepaar zuzuordnen, das jeder Seite entspricht. Für das Beispiel 3 4 1 4 3 1 haben wir also zwei Paare von 3- und 1-Stäbchen, was vier ergibt. Dies würde das 4 3 3 3 3-Problem lösen, da es bei drei keine passende Eins gibt.
Aber das würde nicht funktionieren, wenn die Stöcke 4 4 3 1 2 1 1 wären, da eine Seite drei Stöcke verwendet (einen 2 und zwei 1er)
Also war mein nächster Versuch etwas komplizierter und ich dachte, es wäre eine gute Lösung ... bis es nicht so war. Bei diesem Versuch habe ich mit dem längsten Stock begonnen. Wenn es nicht die Länge der Seite war, nahm ich den nächstlängsten Stock, der zur Vervollständigung der Seite erforderlich war, und wiederholte den Vorgang, bis keine Lösung mehr möglich war. Mit dieser Methode waren die folgenden Lösungen wahr.
Ich dachte, das wäre die Lösung, bis mir klar wurde, dass 9 5 3 1 5 2 2 3 3 3 nicht funktionieren würde. Die erste Seite ist 9, die nächste Seite ist 5 3 1 und die dritte Seite würde mit 5 3 und keiner 1 scheitern.
An diesem Punkt begann ich mich zu fragen, ob es überhaupt möglich war, eine Lösung zu finden, die ohne rohe Gewalt auskam. Also schlief ich darauf, kritzelte viele Dinge auf mein Tablet (ich bin im Urlaub und kann daher mein Whiteboard nicht benutzen) und schlief wieder darauf. Mein Fazit ist, dass die Verwendung einer rekursiven Funktion die einzige Lösung ist.
Vielleicht überdenke ich das alles nur, oder vielleicht gibt es eine wirklich einfache Lösung, die mir gerade eingefallen ist (wie es letzte Woche der Fall war).
Lesen Sie noch? Gut gemacht :)
Für diese Aufgabe habe ich eine rekursive Funktion namens make_side. Es benötigt eine Liste (arrayref in Perl) der verbleibenden Sticks und der erforderlichen Länge. Anschließend geht es durch die verbleibenden Stöcke (höchste zuerst). Dann passiert eines von drei Dingen:
Die Funktion gibt eine Liste der verwendeten Sticks zurück oder None (undef in Perl), wenn keine gültige Kombination von Sticks gefunden wird.
def sc(match):
m = match.group(0)
return str(len(m)) + m[0]
Als letztes Teil des Puzzles führe ich die im ersten Teil erwähnten Prüfungen durch (Summe ist durch vier teilbar, kein Stab länger als eine Seite) und rufe dann die obige Funktion auf. Wenn das None zurückgibt, gebe ich false zurück. Wenn alle Stöcke verwendet werden, gebe ich true zurück.
def string_compress(s: str) -> str:
return re.sub(r'(([a-z])+)', sc, s)
def usc(match):
m = match.group(0)
return m[-1] * int (m[:-1])
def string_decompress(s: str) -> str:
return re.sub(r'(\d+[a-z])', usc, s)
Das obige ist der detaillierte Inhalt vonMatchstick-Komprimierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
