Matchstick-Komprimierung

Wöchentliche Herausforderung 296

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

Aufgabe 1: String-Komprimierung

Aufgabe

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.

Meine Lösung

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)

Beispiele

$ ./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

Aufgabe 2: Streichholzquadrat

Aufgabe

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.

Meine Lösung

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ückgeben

Ich 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.

Versuch zwei

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)

Versuch drei

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.

• 4 4 3 1 2 1 1
• 9 5 4 3 3 3 3 3 3
• 9 6 3 5 4 3 3 3
• 9 6 3 5 4 3 3 2 1

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.

Versuch vier

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).

Der endgültige Code

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:

• Wenn der Stock länger als die erforderliche Länge ist, lasse ich ihn weg.
• Wenn es die erforderliche Länge hat, schicke ich es zurück.
• Wenn es kurz ist, verwende ich es und rufe die Funktion erneut auf, um einen anderen Stick zu verwenden. Der Aufruf entfernt den verwendeten Stick und reduziert die erforderliche Länge um die Länge des verwendeten Sticks.

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)

Beispiele

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!