Herzlichen Glückwunsch an @kuroineko. Gewinnt das Kopfgeld für exzellentes Tempo (672 Züge) auf der Gauntlet-Strecke.
ANFÜHRER: * Nimi erzielt eine leichte 2129. Andere Einträge sind größer, zeigen aber eine ernsthafte Geschwindigkeit.
* Der Anführer kann sich aufgrund späterer Einträge ändern.
Ihre Aufgabe ist es, ein kleines Programm zu schreiben, das einen Rennwagen schnell fahren kann.
Regeln
Ihr Programm liest ein Bild des Titels ein. Sie können Ihr Auto auf einem beliebigen gelben Pixel starten und müssen zum Abschluss ein beliebiges schwarzes Pixel kreuzen. Der Weg Ihres Autos darf nur auf der grauen Spur ((c, c, c) mit 30 <= c <= 220) verlaufen.
Ihr Auto bewegt sich in jeder Kurve in einer geraden Linie mit der Geschwindigkeit v, die sich aus den ganzen Zahlen vx und vy zusammensetzt (beginnend mit (0,0)). Zu Beginn jeder Runde kann Ihr Programm vx und vy so ändern, dass:
abs(vx2-vx1) + abs(vy2-vy1) <= 15
Aktualisieren: maximale Beschleunigung wurde auf 15 erhöht.
Ihr Programm zeichnet dann eine gerade Linie von Ihrem aktuellen Standort zu (Standort + v) in Weiß mit einem blauen Punkt am Anfang. Wenn ein Pixel unter dieser Linie schwarz ist, haben Sie das Rennen beendet. Andernfalls können Sie mit der nächsten Abbiegung fortfahren, wenn alle Pixel unter dieser Linie grau oder gelb sind.
Ihr Programm muss das Titelbild mit dem Pfad in Weiß und Blau ausgeben.
Zusätzliche Ausgabe (hinzugefügt am 15.01.2015):
Wenn Sie um den Gewinn oder den Bonus kämpfen möchten , sollte Ihr Programm auch Ihre Punkteliste (die blauen Punkte) für die Stadt bzw. den Handschuh ausgeben. Fügen Sie Ihrer Antwort die Liste der Punkte bei (zur Verifizierung). Die Punkte sollten folgendermaßen aussehen: (x0,y0), (x1,y1), ... (xn,yn)
. Sie können Leerzeichen frei verwenden, einschließlich'\n'
Zeichen verwenden, um die Daten auf der Seite anzupassen.
Sie können das Lesen und Schreiben von Bildern von Drittanbietern, Strichzeichnen und Pixelzugriffsbibliotheken verwenden. Pfadfindungsbibliotheken können nicht verwendet werden. Wenn Sie möchten, können Sie die PNG-Bilder bei Bedarf in andere Grafikformate (wie GIF, JPG, BMP) konvertieren.
Ein paar Spuren zum Weiterfahren
Ein einfacher Weg, um anzufangen:
Eine Rennstrecke:
Ein Hindernisparcours:
Die Stadt:
Nightmare Track: The Gauntlet (wenn die anderen zu einfach sind)
Wertung
Ihre Punktzahl basiert auf Ihrem Ergebnis auf der City-Strecke. Punkte entsprechen Ihrer Programmlänge in Bytes plus 10 Punkte für jede Runde, die Ihr Rennwagen bis zum Ende absolviert hat. Die niedrigste Punktzahl gewinnt. Bitte fügen Sie Ihrer Antwort Ihr City-Streckenbild bei - wir möchten Ihren Fahrstil sehen.
Bitte verwenden Sie einen Titel für Ihre Antwort im Format:
<Racing Driver or Team Name> <Language> <Score>
Beispiel: Slowpoke Perl 5329
Ihr Programm muss in der Lage sein, auf einem beliebigen Titelbild zu fahren, wobei die obigen Regeln zu beachten sind. Sie dürfen weder den optimalen Pfad noch Parameter der Teststrecken fest codieren. Es gelten die anderen Standardlücken.
Ähnliche Herausforderungen
Dies ist ein ähnliches Puzzle wie das von Martin: To Vectory! - Der Vector Racing Grand Prix . Dieses Puzzle hat eine Reihe von Unterschieden:
- Das Durchfahren von Wänden ist nicht gestattet.
- Sie können unbegrenzten Speicher und Zeit verwenden.
- Sie müssen nicht den Code eines anderen Benutzers auf Ihrem Computer ausführen.
- Sie müssen nur ein Bild herunterladen.
- Die Größe Ihres Codes zählt bei der Bewertung. Kleiner ist besser.
- Sie zeichnen Ihre Lösung auf dem Gleisbild.
- Mit einem Malpaket können Sie ganz einfach eigene Spuren erstellen.
- Die höhere Auflösung fördert ein realistischeres Bremsen und Kurvenfahren.
- Eine Beschleunigung von 15 schafft ungefähr 450 Möglichkeiten pro Umdrehung. Dies macht BFS weniger machbar und ermutigt zu neuen interessanten Algorithmen.
Dieses Rätsel soll eine neue Runde von Programmierern dazu anregen, Lösungen auszuprobieren, und es Programmierern mit alten Lösungen ermöglichen, diese in der neuen Umgebung zu überdenken.
quelle
Antworten:
TS # 1 - Haskell - 1699 + 430 = 2129
Tutu Geschwister # 1
Sehr ähnlich wie der ursprüngliche Tutu-Renner, mit der Ausnahme, dass er eine Dicke von 3 für den aufgeblähten Pfad verwendet und das 2. A * (Geschwindigkeits-Positionsraum) mit einer konstanten Heuristik von übereinstimmt
1
. Das Eingabebild wird nicht mehr als Kommandozeilenargument übergeben, es muss benannt werdeni
. Der Name des Ausgabebildes lauteto
. Das Programm druckt die berechneten Punkte auf dem Pfad als eine Liste von x, y-Paaren (die ursprüngliche Ausgabe ist eine einzelne Zeile):Ich könnte eine Menge Bytes sparen, wenn ich anfange, die gesamte Karte zu entfernen und Datenstrukturen festzulegen und sie durch einfache verknüpfte Listen zu ersetzen. Allein die beiden Import-Anweisungen würden 60 Bytes einsparen. Es würde jedoch das Programm verlangsamen, so dass das Warten auf ein Ergebnis purer Schmerz ist. Diese Version benötigt für The City mehr als 45 Minuten im Vergleich zu den 7er-Versionen des Originals. Ich werde hier aufhören, Bytes zu tauschen, um Geschwindigkeit auszuführen.
Der Code benötigt zum Kompilieren das Flag -XNoMonomorphismRestriction.
Die Stadt - TS # 1 - 43 Stufen
quelle
FirstRacer Java (5825 + 305 * 10 = 8875)
Nur um einen Anfang zu machen. Benötigt 305 Segmente auf Stadt.
Dieses Java-Programm führt folgende Pipelines aus:
Ich denke, die Rennstrecke gibt Ihnen einen besseren Eindruck davon, wie FirstRacer funktioniert.
quelle
pighead PHP (5950 + 470 = 6420)
Noch eine weitere (mit Pigheading versehene) BFS-Variation, mit einer gewissen Vorverarbeitung, um den Suchraum zu verkleinern.
Sprachauswahl
PHP ist ziemlich gut im Umgang mit Bildern.
Der native assoziative Speicher macht das Programmieren der BFS-Knotensuche zum Kinderspiel.
Der Nachteil ist, dass das Hashing der Knotenkennungen nicht sonderlich zeiteffizient ist, sodass das Ergebnis alles andere als schnell ist.
Aus meinen Experimenten mit der vorherigen Rennherausforderung habe ich keinen Zweifel, dass C ++ 11 und seine Hash-Tabellen viel besser abschneiden würden, aber der Quellcode würde sich mindestens verdoppeln, plus der Notwendigkeit für irgendeine externe PNG-Bibliothek (sogar LodePNG) Machen Sie für einen chaotischen Build.
Perl und seine fortschrittlicheren Nachkommen ermöglichen wahrscheinlich einen kompakteren und effizienteren Code (aufgrund der besseren Hash-Leistung), aber ich kenne mich mit keinem dieser Programme aus, um einen Port auszuprobieren.
BFS-Kern
Die Suche wird auf einem Positions- + Geschwindigkeitsraum ausgeführt, dh ein Knoten repräsentiert einen bestimmten mit einer bestimmten Geschwindigkeit besuchten Ort.
Dies ergibt natürlich einen ziemlich großen Suchraum, liefert jedoch optimale Ergebnisse, vorausgesetzt, alle möglichen Track-Positionen werden untersucht.
Angesichts der Anzahl der Pixel auf einem kleinen Bild kommt eine umfassende Suche natürlich nicht in Frage.
Schnitte
Ich entschied mich, den Positionsraum zu durchtrennen, indem ich nur eine Teilmenge von Spurpixeln auswählte.
Der Löser berücksichtigt alle erreichbaren Positionen, die nur durch die Beschleunigung begrenzt sind.
Die Spur ist mit Quadraten gekachelt, deren maximale Größe so berechnet wird, dass zwei benachbarte Quadrate mit der maximal zulässigen Beschleunigung erreicht werden können (dh 14 x 14 Pixel mit dem aktuellen Tempolimit).
Nachdem die Strecke mit großen Quadraten gefüllt wurde, werden zunehmend kleinere Kacheln verwendet, um den verbleibenden Raum zu füllen.
Nur die Mitte jeder Kachel wird als mögliches Ziel angesehen.
Hier ist ein Beispiel:
Diese heuristische Auswahl reicht aus, um den Solver auf der Albtraumkarte zum Scheitern zu bringen. Ich nehme an, man könnte versuchen, die maximale Kachelgröße zu reduzieren, bis eine Lösung gefunden ist, aber mit den aktuellen Einstellungen läuft der Solver etwa eine Stunde und verwendet 600 MB, sodass genauere Ergebnisse eine unangemessene Menge an Zeit und Speicher erfordern würden.
Bei einem zweiten Schnitt werden möglicherweise Quadrate von nur 1 Pixel weggelassen.
Dies wird natürlich die Lösung verschlechtern oder sogar verhindern, dass der Löser welche findet, aber es verbessert die Rechenzeit erheblich und liefert normalerweise ziemlich nahe Ergebnisse auf "einfachen" Karten.
Wenn Sie beispielsweise in der Stadt 1x1-Pixel-Quadrate weglassen, werden die erkundeten BFS-Baumknoten von 660 KB auf etwa 90 KB für 47-gegen-53-Zug-Lösungen reduziert.
BFS gegen A *
Ein * benötigt mehr Code und liefert im Positions- / Geschwindigkeitsbereich nicht einmal garantiert schnellere Ergebnisse, da die Bewertung des besten nächsten Kandidaten nicht so einfach ist wie im klassischen Positionsbereich (der leicht mit zweckgebundener Kulisse besiegt werden kann). de-sacs sowieso).
Außerdem, obwohl PHP einige vorrangige Warteschlangen hat, die im Gegensatz zu ihren C ++ - Verwandten die dynamische Neuordnung unterstützen, bezweifle ich, dass sie für eine effiziente A * -Implementierung und das Umschreiben eines binären Heaps oder einer beliebigen dedizierten A * -Warteschlangenstruktur ausreichen würden erfordern viel zu viele Codezeilen.
Wandcheck
Ich habe keinen Bresenham-Algorithmus verwendet, um nach Wandkollisionen zu suchen, sodass die Flugbahn möglicherweise das ungerade Wandpixel abschneidet. Es sollte jedoch nicht erlaubt sein, eine Mauer zu durchqueren.
Vorstellungen
Dieser Löser ist sicher kein sechsbeiniger Hase.
Ohne den zusätzlichen Schnitt kann das Lösen einer Karte auf meinem PC mit mittlerer Reichweite über 10 Minuten dauern.
Ich empfehle, die minimale Kachelgröße auf 2 oder 3 zu setzen, wenn Sie mit dem Code experimentieren möchten, ohne lange auf ein Ergebnis zu warten.
Der Speicherverbrauch ist für diese Art von Algorithmus und Sprache angemessen: etwa 100 MB oder weniger, mit Ausnahme von Alptraumsituationen, die über 600 MB liegen.
Ergebnisse und Wertung
Die Bewertungen werden ohne den Schnitt "minimale Fliesengröße" angegeben.
Wie ein aufmerksamer Leser aus meinen allgemeinen Kommentaren ableiten mag, ist mir der Golf-Teil dieser Herausforderung nicht besonders wichtig. Ich sehe nicht, wie das Ausführen meines Codes durch einen Verschleierer oder das Löschen einiger Optimierungen und / oder Debug-Routinen, um die Quelle zu verkleinern, das noch mehr Spaß machen würde.
Sei nur S die Größe des Quellbytes für den Moment:
Spur S + 1020
Stadt S + 470
Hindernisse S + 280
Albtraum -> scheitert
quelle
SecondRacer Java (1788 + 72 * 10 = 2508)
(2708) (2887) (3088) (3382) (4109 + 72 * 10 = 4839) (4290 + 86 * 10 = 5150)Ähnlich wie FirstRacer. In den Schritten 2.2 und 3. ist dies jedoch anders, wodurch vorausschauend gefahren und der Gang benutzt wird.
Performance
Keine dieser Spuren ist ein Problem für A *. Nur ein paar Sekunden (<10) (sogar der "Nightmare Track: The Gauntlet") auf meinem PC mit mittlerer Reichweite.
Pfadstil
Ich nenne es Octopussy. Bei weitem nicht so elegant wie die Pighead-Lösung (von kuroi neko).
Code-Stil
Ich bin in einen moderaten Kampfmodus eingetreten, der die Lesbarkeit beibehält. Fügte aber eine Golf-Version hinzu.
golfed -> ACHTUNG: Ersetzt die Originaldatei!
Alle Bilder werden in ihrer A * -Gradientenlandschaft angezeigt. Ausgehend von hellgelb bis braun (= dunkelgelb). Während - gemäß A * - der resultierende Pfad rückwärts verfolgt wird (hier von braun nach hellgelb).
Rennstrecke S + 175
Hindernislauf S + 47
Stadt S + 72
Gauntlet S + 1133
quelle
Tutu - Haskell - (
3460265424762221206019921900 + 50 x 10 = 2400)Strategie:
Golf:
Ich bin kein Haskell-Golfer, daher weiß ich nicht, wie viel weiter gespart werden kann (Bearbeiten: Es stellte sich heraus, dass dies eine Menge ist).
Performance:
Das Gauntlet läuft auf meinem 1,7 GHz Core i5 von 2011 in 9: 21 Minuten. Die City dauert 7,2 Sekunden. (verwendet -O1 mit ghc, -O2 macht das Programm furchtbar langsam)
Optimierungsoptionen sind die Dicke des aufgeblähten Pfads. Bei den kleineren Karten speichert Distanz 3 ein oder zwei Schritte, aber The Gauntlet läuft zu lange, so dass ich bei Distanz 2 bleibe. Das Rennen startet immer beim ersten (dh oben links) gelben Pixel, eine Optimierung von Hand sollte einen zusätzlichen Schritt sparen.
Regelkonformität:
„Pfadfindungsbibliotheken können nicht verwendet werden.“ - Ja, aber die Quelle ist enthalten. Bei den A * -Suchfunktionen handelt es sich um
leichtausgelastete Versionen der Data.Graph.AStar-Bibliothek von Cale Gibbard (siehe http://hackage.haskell.org/package/astar) ).Die Stadt - 50 Stufen
Der Handschuh - 722 Stufen
Ungolfed:
Golf gespielt:
Tutu Geschwister -TS # 1 - (1764 + 43 = 2194)Edit: TS # 1 jetzt separate Antwort.
Edit II: Der Weg für Die Stadt ist
In The Gauntlet bewegt sich Tutu wie folgt
quelle
-O2
das Programm verlangsamt? seltsam. versucht-O3
?Maybe
viel. Vielleicht können Sie durchMaybe
Listen ersetzen :Maybe a
ist[a]
,Nothing
ist[]
undJust x
ist[x]
. DieMaybe
Monade wird der Monade gleichgestelltList
. Sie können dann eine Menge Listenfunktionen für sie benutzennull
,head
,(:[])
,map
und so weiter.Sternenkreuzer - PHP - 4083 + 440 = viel zu schwer
Ok, nach 3 Wochen ohne Internetverbindung (das passiert, wenn einer der schärfsten Konkurrenten Ihres Providers zufällig für die Baustellenbucht zuständig ist, oder zumindest in Paris, Frankreich), kann ich endlich veröffentlichen Mein nächster Versuch.
Diesmal habe ich den A * -Algorithmus und eine effizientere Strategie zur Verteilung von Wegpunkten verwendet.
Als zusätzlichen Bonus habe ich eine Art PHP-Cruncher geschrieben, um den Golf-Teil der Herausforderung anzusprechen.
Und jetzt, da der Solver auf allen vorgeschlagenen Karten funktioniert, wurde der Fehler bei der Linienverfolgung behoben.
Keine Wandbeschneidung mehr (obwohl die Wand immer noch weidet, wie es sollte :)).
Code ausführen
Geben Sie dem Code einen beliebigen Namen (
runner.php
zum Beispiel) und rufen Sie ihn folgendermaßen auf:Nachdem Sie eine Weile still gesessen haben, sollte sich eine
_track.png
Ausgabe ergeben, die die Lösung zeigt.Wie Sie auf den ausgegebenen Bildern sehen können, lautet der Code sehr langsam. Du wurdest gewarnt.
Natürlich ist meine private Version voll von Spuren und liefert nette Darstellungen verschiedener Informationen (einschließlich eines periodischen Bildes, das den A * Fortschritt zeigt, um die Zeit totzuschlagen), aber für das Golfen muss man einen Preis zahlen ...
Golf Code
ungolfed version
Ergebnisse
Die Bilder werden von einer umfangreicheren Version erstellt, die genau dieselbe Lösung mit einigen Statistiken unten ausgibt (und den Pfad mit Antialiasing zeichnet).
Der Stadtplan ist ein ziemlich gutes Beispiel dafür, warum positionsbasierte Algorithmen in vielen Fällen zu unterdurchschnittlichen Ergebnissen führen müssen: Kürzere bedeuten nicht immer schnellere.
(672 Züge, wenn Sie nicht zoomen möchten)
EIN*
Zu meiner Überraschung schneidet A * im Positions-Geschwindigkeits-Raum ziemlich gut ab. Jedenfalls besser als BFS.
Ich musste allerdings ziemlich viel schwitzen, um eine funktionierende heuristische Entfernungsschätzung zu erstellen.
Ich musste es auch etwas optimieren, da die Anzahl der möglichen Zustände im Vergleich zu einer reinen Positionsvariante, die wiederum mehr Code erfordert, sehr groß ist (einige Millionen).
Die Untergrenze für die Anzahl der Züge, die erforderlich sind, um ein Ziel von einer bestimmten Position aus zu erreichen, ist einfach die Zeit, die erforderlich ist, um die Entfernung zum nächsten Ziel in einer geraden Linie mit einer Anfangsgeschwindigkeit von Null zurückzulegen .
Natürlich führt der geradlinige Pfad normalerweise direkt in eine Wand, aber dies ist ungefähr das gleiche Problem wie die Verwendung des euklidischen geraden Abstands für A * -Suche nur im Weltraum.
Genau wie der euklidische Abstand für Nur-Weltraum-Varianten besteht der Hauptvorteil dieser Metrik, abgesehen davon, dass die effizienteste A * -Variante (mit geschlossenen Knoten) verwendet werden kann, darin, dass nur eine sehr geringe topologische Analyse der Strecke erforderlich ist.
Bei einer maximalen Beschleunigung A ist die Anzahl n der Bewegungen, die zum Zurücklegen einer Strecke d erforderlich sind, die kleinste ganze Zahl, die die folgende Beziehung erfüllt:
d <= An (n + 1) / 2
Wenn Sie dies nach n auflösen, erhalten Sie eine Schätzung der verbleibenden Entfernung.
Um dies zu berechnen, wird eine Karte der Entfernung zum nächsten Ziel erstellt, wobei ein Flood-Fill-Algorithmus verwendet wird, der mit Zielpositionen geimpft ist.
Es hat den angenehmen Nebeneffekt, dass Trackpunkte beseitigt werden, von denen aus kein Ziel erreicht werden kann (wie es in einigen Bereichen des Albtraum-Tracks der Fall ist).
Die Anzahl der Bewegungen wird als Gleitkommawert berechnet, so dass näher am Ziel liegende Knoten weiter unterschieden werden können.
Wegpunkte
Wie bei meinem vorherigen Versuch geht es darum, die Anzahl der Trackpunkte auf eine möglichst kleine Untermenge von Wegpunkten zu reduzieren. Der Trick besteht darin, die "nützlichsten" Positionen auf der Strecke zu finden.
Die Heuristik beginnt mit einer regelmäßigen Neuaufteilung über die gesamte Strecke, erhöht jedoch die Dichte in zwei Arten von Bereichen:
Hier ist ein Beispiel.
Bereiche mit hoher Dichte sind rot, Bereiche mit niedriger Dichte grün. Blaue Pixel sind die ausgewählten Wegpunkte.
Beachten Sie die Anhäufungen von Wegpunkten in scharfen Kurven (bei vielen nutzlosen Flecken auf schrägen Kurven aufgrund unzureichender Filterung).
Um die Position der Fahrspuren zu berechnen, wird die gesamte Strecke nach der Entfernung zur nächsten Wand abgesucht. Das Ergebnis ist ein Feld von Vektoren, die auf die nächste Spurgrenze zeigen.
Dieses Vektorfeld wird dann verarbeitet, um eine grobe Abschätzung der lokalen Krümmung zu erzeugen.
Schließlich werden Krümmung und Abstand zur Wand kombiniert, um eine gewünschte lokale Dichte zu erzeugen, und ein ziemlich klobiger Algorithmus versucht, Wegpunkte entsprechend über die Strecke zu streuen.
Eine bemerkenswerte Verbesserung gegenüber der vorherigen Strategie ist, dass schmale Fahrspuren (anscheinend) immer genügend Wegpunkte zum Durchfahren haben, was das Navigieren auf der Albtraumkarte ermöglicht.
Wie immer geht es darum, einen Sweet Spot zwischen Rechenzeit und Effizienz zu finden.
Bei einer Verringerung der Dichte um 50% wird die Rechenzeit durch mehr als 4 geteilt, jedoch mit gröberen Ergebnissen (48 Züge anstelle von 44 in der Stadt, 720 anstelle von 670 im Albtraum).
Golfen
Ich denke immer noch, dass Golfen der Kreativität in diesem speziellen Fall schadet: Das Entfernen von Antialiasing aus der Ausgabe reicht aus, um 30 Punkte zu erzielen, und erfordert viel weniger Aufwand als das Ändern von 47 auf 44 Züge auf dem Stadtplan.
Selbst ein Wechsel von 720 auf 670 in einem Albtraum würde nur 500 Punkte bringen, obwohl ich sehr bezweifle, dass ein A * nur auf Position in der Lage wäre, sich dem anzunähern.
Aus Spaß habe ich beschlossen, trotzdem meinen eigenen PHP-Kompressor zu schreiben.
Wie es scheint, ist das effiziente Umbenennen von Bezeichnern in PHP keine leichte Aufgabe. Tatsächlich glaube ich nicht, dass es überhaupt möglich ist, dies im allgemeinen Fall zu tun. Selbst bei einer vollständigen semantischen Analyse würde die Möglichkeit, Zeichenfolgen oder indirekte Variablen zur Bezeichnung von Objekten zu verwenden, die Kenntnis jeder Funktionssemantik erfordern.
Da der sehr praktische eingebaute Parser es jedoch ermöglicht, sofort auf die semantische Analyse zuzugreifen, habe ich es geschafft, etwas zu produzieren, das auf einer Teilmenge von PHP zu funktionieren scheint, die ausreicht, um "golffähigen" Code zu schreiben (halten Sie sich von $$ fern und tun Sie das nicht Verwenden Sie indirekte Funktionsaufrufe oder anderen String-Zugriff auf Objekte.
Keine praktische Verwendung und nichts mit dem ursprünglichen Problem zu tun, aber dennoch viel Spaß beim Programmieren.
Ich hätte den Code weiter abtöten können, um zusätzliche 500 Zeichen zu erhalten, aber da die Namen der PHP-Grafikbibliothek leider ziemlich lang sind, ist es eine Art harter Kampf.
Weiterentwicklungen
Der Wegpunkt-Auswahlcode ist ein schreckliches Durcheinander, das durch Ausprobieren eingestellt wird. Ich vermute, dass mehr Mathematik (unter Verwendung geeigneter Gradienten- und Lockenoperatoren) den Prozess erheblich verbessern würde.
Ich bin gespannt, ob eine bessere Entfernungsheuristik gefunden werden kann. Ich habe versucht, die Geschwindigkeit auf verschiedene Arten zu berücksichtigen, aber sie hat entweder das A * gebrochen oder langsamere Ergebnisse hervorgebracht.
Es könnte möglich sein, all dies in einer schnelleren Sprache wie C ++ zu rekodieren, aber die PHP-Version verlässt sich stark auf die Garbage Collection, um den Speicherverbrauch in einem vernünftigen Rahmen zu halten. Das Bereinigen geschlossener Knoten in C ++ würde viel Arbeit und eine beträchtliche Menge zusätzlichen Codes erfordern.
Wäre die Wertung auf Performances basiert, hätte ich eifrig versucht, die Algorithmen zu verbessern. Aber da das Golfkriterium so überwältigend ist, gibt es keinen wirklichen Grund, oder?
quelle
ThirdRacer Java (1224 + 93 * 10 = 2154)
Ähnlich wie SecondRacer. Aber den Fokus von Geschwindigkeit auf Codegröße umstellen (aber immer noch Java verwenden). Die Optimierung der Beschleunigung ist jetzt viel einfacher, was leider zu einem langsameren Auto führt.
Performance
Besser als SecondRacer.
Pfadstil
Wie SecondRacer.
Code-Stil
Ich trat in einen schweren Kampfmodus ein.
golfed -> ACHTUNG: Ersetzt die Originaldatei direkt vor Ort!
Stadt S + 93
quelle
Stern gekreuzter Rennläuferweg auf der Albtraumkarte
(laut populärer Anfrage)
(Code nicht aktualisiert, da die Änderungen trivial sind und die Performance-Only-Challenge nicht gespielt wird.)
Es tut mir leid, noch einen Eintrag zu posten, aber ich überschreite die Grenze von 30.000 Zeichen für den vorherigen.
Sagen Sie einfach das Wort und ich werde dieses löschen.
quelle
Sunday Driver, Python 2, 3242
Minimierter Code = 2382 Byte
Leistung: Stadt = 86 Hindernisse = 46 Rennstrecke = 188 Handschuh = 1092
Hier ist mein Proof-of-Concept-Programm, das zeigen soll, dass eine Lösung möglich ist. Es muss optimiert und besser golfen werden.
Operation
Erstellen Sie eine Datenstruktur mit Entfernungsringen, die vom Ziel entfernt sind (einfache Ableitung von A *, wie z. B. Überflutung).
Suchen Sie die kurze Reihe von geraden Linien zum Ziel, die keine Pixel ohne Spur kreuzen.
Beschleunigen und bremsen Sie für jede Gerade, um die Kurven zu minimieren.
Golfed (minified) Code
Beispiele
quelle