Steine und Stabilität definiert
Diese Frage verwendet dieselbe Definition von Ziegeln und Stabilität wie Ist die Ziegelstruktur stabil?
Stellen wir [__]einen Mauerziegel dar und
.
.
.
BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK? . . .
BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK?
stellen eine beliebige Anordnung oder Struktur dieser Ziegel dar, wobei jede zweite Reihe um einen halben Ziegel versetzt ist, wie es bei der Ziegelkonstruktion üblich ist. Die Struktur kann sich unbegrenzt nach oben und rechts erstrecken, aber die Zeichenfolgendarstellung ist immer ein perfekt rechteckiger Textblock (mit erforderlichen Leerzeichen), dessen Breite durch 4 teilbar ist.
Jedes BRK?in der Struktur kann entweder ein Ziegelstein ( [__]) oder ein leerer Raum (4 Räume) sein.
Eine mögliche (instabile - weiterlesbare) Struktur ist beispielsweise
[__] [__] [__]
[__] [__]
[__][__] [__]
Die Stabilität einer Struktur ist wichtig, und eine Struktur ist nur dann stabil, wenn jeder einzelne ihrer Steine stabil ist.
Es gibt drei Möglichkeiten, wie ein einzelner Stein stabil sein kann:
- Jeder Ziegelstein auf dem Boden (die unterste Ziegellinie) ist stabil.
Jeder Stein, der zwei Steine direkt darunter hat, ist stabil:
[__] <- this brick is stable [__][__] <- because these bricks hold it upJeder Stein, auf dem sich auf derselben Seite ein Stein darüber und darunter befindet, ist stabil:
[__] [__] [__] [__] <- these middle bricks are stable [__] [__] because the upper and lower bricks clamp them in [__] [__] [__] [__] <- these middle bricks are NOT stable [__] [__]
(Ja, ich weiß, dass diese Regeln physikalisch nicht korrekt sind.)
Die letzte Herausforderung bestand darin, festzustellen, ob eine Struktur stabil war. Hier geht es darum, diejenigen zu stabilisieren, die es nicht sind.
Herausforderung
Schreiben Sie ein Programm, das eine möglicherweise instabile Anordnung von Steinen aufnimmt und neue Steine in leere Ziegelräume einfügt, um alles stabil zu machen und das Ergebnis zu drucken. Dies erfolgt ohne Vergrößerung der Gesamtabmessungen des Eingabetextblocks.
Ziel ist es, einen Algorithmus zu erstellen, der die Struktur stabil macht, indem so wenig Steine wie möglich hinzugefügt werden.
Mit dieser JSFiddle ( Quelle ) können Sie zufällige Anordnungen von Steinen generieren, die beim Testen Ihres Programms verwendet werden. (Ich wünschte, ich könnte stattdessen Schnipsel stapeln .) IstWidth die Anzahl der Steine auf der Basisschicht, Heightist die Anzahl der Steinschichten und Densityist der Anteil der gefüllten Steinflächen.
Zum Beispiel mit Width = 5, Height = 3, Density = 0.6einer möglichen Ausgabe ist
....[__]....[__]....
..[__]....[__]......
[__]............[__]
Eine Möglichkeit, dies mit 4 neuen Steinen zu stabilisieren, ist
....[__]....[__]....
..[__][__][__][__]..
[__][__]....[__][__]
Ihr Programm muss in der Lage sein, jede von JSFiddle erzeugte Ziegelstruktur zu stabilisieren.
- Dies schließt die leere Zeichenfolge ein (die als stabil angesehen wird).
- Der Ziegel wird immer sein
[__]. Punkte (.) werden nur zur Verdeutlichung verwendet. Ihr Programm verwendet möglicherweise Punkte oder Leerzeichen für Leerzeichen. - Die Struktur ist möglicherweise bereits stabil. In diesem Fall muss nichts getan werden (außer sie zu drucken).
- Die JSFiddle generiert immer Strukturen, die stabilisiert werden können (durch Vermeiden
Width = 1und Ziegel in den oberen Ecken). Darauf können Sie sich verlassen. (Das Füllen aller außer den oberen Ecken wird die Dinge sicher stabilisieren, aber dies ist eindeutig nicht optimal.) - Nehmen Sie keine ungültige Eingabe an. Nehmen Sie die Eingabe als Zeichenfolge, wie Sie möchten. Drucken Sie die stabilisierte Struktur auf Standard oder ähnliches.
- Denken Sie daran, dass die Größe der Textblöcke die Größe nicht ändern sollte.
- Bereits vorhandene Steine können nicht verschoben oder entfernt werden. Das Platzieren neuer Steine muss dem Rastermuster für jede zweite Reihe folgen. Alle Steine müssen vollständig in Grenzen sein.
- Es wird empfohlen (aber nicht erforderlich), dass Sie die bereits vorhandenen Bausteine
[XX]anstelle von drucken, damit die Benutzer[__]besser sehen können, wie Ihre Lösung funktioniert.
Wertung
Am unteren Rand der JSFiddle befinden sich 8 vordefinierte instabile Ziegelanordnungen . (Sie verwenden [__]und .und sollten dies auch bleiben, es sei denn, Sie verwenden [XX]und / oder stattdessen.) Einige sind zufällig und andere habe ich selbst erstellt. Um Ihre Punktzahl zu berechnen, führen Sie Ihr Programm nacheinander auf jedem aus und addieren Sie die Anzahl der neuen Steine, die zu jedem hinzugefügt wurden.
Je weniger neue Steine Sie hinzugefügt haben, desto besser. Die Einreichung mit der niedrigsten Punktzahl gewinnt. Bei Gleichstand gewinnt die älteste Antwort.
Wenn die Dinge umstritten werden, kann ich einige weitere vordefinierte Fälle hinzufügen und den Gewinner anhand dieser beurteilen.
Weitere Hinweise
- Ihr Programm muss auf einem modernen Computer in der Größenordnung von Minuten ausgeführt werden, wenn die Breite und Höhe des Ziegelgitters weniger als 100 beträgt. (Maximal 10 Minuten auf einem Computer wie diesem .)
- Sie dürfen Ihre Ausgabe für die 8 vordefinierten Strukturen nicht fest codieren. Ihr Programm muss sie wie jede andere Vereinbarung behandeln.
- Bitte fügen Sie ein oder zwei Beispielausgaben oder interessante Strukturen hinzu, die Sie teilen möchten. :) :)
- Dieses Problem hängt etwas mit dem Finden eines minimalen Spannbaums zusammen .
quelle
Antworten:
Java - 5.056 Steine
Der Quellcode kann hier angezeigt werden .
Der Code wird in wenigen Millisekunden für eine der 8 Bewertungseingaben ausgeführt. Es gibt einige merklich suboptimale Ergebnisse, insbesondere im Criss-Cross-Tower- und 99x99-Fall. Ich habe mehrere Ideen, wie ich die Routine verbessern kann, aber sie ist so wie sie ist ziemlich sperrig, und daher werde ich sie vorerst in Ruhe lassen.
Die Ergebnisse massakrieren die Gesetze der Physik in komödiantischem Ausmaß. : D.
Einige Beispiele sind unten gezeigt.
20x20, 0,03 Ausgabe
Einfache Hausausgabe
quelle
Python, 18992
Dies ist die einfachste Lösung und die schlechteste Punktzahl. Es ist nur als Referenz; das Ding zu schlagen. Es füllt jeden leeren Raum mit Ausnahme der beiden oberen Ecken mit Ziegeln und garantiert so Stabilität.
Kopieren Sie die ursprüngliche Struktur in die dreifachen Anführungszeichen oben im Programm.
Hier wird es auf dem Haus ausgeführt und 609 Steine hinzugefügt:
Die Anzahl der Steine, die für jede der 8 vordefinierten Strukturen in der angegebenen Reihenfolge hinzugefügt werden, ist
quelle