Verbessere die Lösung für das Rätselrätsel
Ich habe versucht, das folgende Problem zu lösen:
Es gibt einen Affen, der auf einem planaren Gitter herumlaufen kann. Der Affe kann ein Leerzeichen nach links, rechts, oben oder unten verschieben. Das heißt, von (x, y) kann der Affe zu (x + 1, y), (x-1, y), (x, y + 1) und (x, y-1). Punkte, bei denen die Summe der Ziffern des absoluten Wertes der x Koordinate plus die Summe der Ziffern des absoluten Wertes von y Koordinaten sind kleiner als oder gleich 19 sind zugänglich für die Affe. Zum Beispiel ist der Punkt (59, 79) nicht zugänglich, weil 5 + 9 + 7 + 9 = 30, was größer als 19 ist. Ein anderes Beispiel: Der Punkt (-5, -7) ist zugänglich, weil abs (-5) + abs (-7) = 5 + 7 = 12, was ist kleiner als 19. Wie viele Punkte kann der Affe zugreifen, wenn er beginnt? (0, 0), einschließlich (0, 0) selbst?
Ich habe die folgende Brute-Force-Lösung (Pseudocode) entwickelt:
%Vor%Dies ist eine sehr brutale Lösung. Eine der Optimierungen, die ich verwendete, bestand darin, einen Quadranten zu scannen, anstatt ihn vier zu betrachten. Ein anderer war, die Punkte zu ignorieren, die wir schon vorher gesehen haben.
Bei den letzten Punkten habe ich versucht, ein Muster zu finden, vielleicht eine mathematische Lösung oder einen anderen Ansatz, der besser wäre als das, was ich gefunden habe.Irgendwelche Gedanken?
PS: Wenn du willst, kann ich die Daten irgendwo posten. Es ist interessant, es mit einer beliebigen Achse sortiert zu betrachten.
Erster Quadrant visuell:
4 Antworten
Hier sehen Sie, wie das ganze Raster als Bild aussieht:
Die schwarzen Quadrate sind nicht zugänglich, weiß zugänglich, grau zugänglich und durch Bewegung von der Mitte aus erreichbar. Es gibt eine 600x600 Bounding Box von Schwarz, weil die Ziffern von 299 zu 20 addiert werden, also müssen wir das nur berücksichtigen.
Diese Übung ist im Grunde genommen eine "Flutfüllung", mit einer Form, die für eine Flutfüllung im schlimmsten Fall möglich ist. Sie können die Symmetrie beschleunigen, wenn Sie möchten, aber das ist nicht wirklich, wo das Problem liegt - meine Lösung läuft in 160 ms ohne es (unter 50ms damit).
Die großen Geschwindigkeitsgewinne sind (1) eine füllende Flut machen, also müssen Sie nicht jeden Punkt auf den Stapel legen und (2) Ihren eigenen Stapel verwalten, anstatt Rekursion zu tun. Ich baute meinen Stack als zwei dynamisch zugewiesene Vektoren von ints (für x und y), und sie wachsen auf etwa 16k, so dass der Aufbau ganzer Stack-Frames, die tief sind, definitiv ein großer Verlust wäre.
Ohne nach der idealen Lösung zu suchen, hatte ich etwas Ähnliches. Für jeden Punkt, den der Affe hat, fügte ich die nächsten 4 Möglichkeiten zu einer Liste hinzu und machte dasselbe für die nächsten vier rekursiv nur, wenn sie nicht besucht worden waren. Dies kann auch mit Multiprocessing durchgeführt werden, um den Prozess zu beschleunigen.
Ich bin mir nicht sicher, wie anders das von der Idee von brainydexter sein könnte ... Ich habe in dem einen Quadranten einen einzelnen Array-Hash (index = 299 * y + x) eingerichtet und das Ergebnis mit einem anderen Array erstellt, wobei jeder Index nur die Punkte speichert, die sich erweitern der vorherige Index, zum Beispiel:
Auf einem alten IBM Thinkpad in JavaScript schien die Geschwindigkeit von 35-120 Millisekunden ( Geige hier ) zu variieren.
Tags und Links algorithm