Hintergrund:
Jack ist ein Kürbis, der es genießt, die Bürger der Dörfer in der Nähe seines Kürbisbeetes an jedem Halloween zu erschrecken. Jedes Jahr, nachdem jemand die Kerze in ihm angezündet hat, hat er eine begrenzte Zeit, um alle zu erschrecken, bevor die Kerze ausgebrannt ist. Dadurch kann er keine Dorfbewohner mehr erschrecken, weil ihn niemand sehen kann. In den vergangenen Jahren konnte er aufgrund seiner schlechten Entscheidungsfindung nur eine kleine Anzahl von Dörfern erschrecken, aber jetzt, wo er Sie zur Hilfe hat, wird er in der Lage sein, so viele Dörfer wie möglich zu erschrecken!
Aufgabe:
Geben Sie die maximale Anzahl der Dörfer aus, die Jack besuchen kann, wenn Sie eine Liste mit Orten im Dorf und eine Kerzenlebensdauer angegeben haben. Sie müssen den Pfad nicht selbst drucken.
Eingang:
Die Lebensdauer der Kerze und eine Liste der Orte in einem kartesischen Koordinatensystem. Das Kürbisfeld, aus dem Jack stammt, wird immer bei 0,0 liegen. Sie können die Eingabe beliebig formatieren. Um Jacks Bewegungen zu vereinfachen, kann er sich nur horizontal, vertikal oder diagonal bewegen, was bedeutet, dass seine Kerze bei jeder Bewegung entweder 1 oder 1,5 Lebenseinheiten verliert (diagonal dauert er etwas länger). Die Kerze brennt aus, wenn die Lebensdauer kleiner oder gleich 0 ist.
Ausgabe:
Eine ganze Zahl, die der maximalen Anzahl von Dörfern entspricht, die Jack besuchen kann, bevor die Kerze ausbrennt.
Regeln:
Das ist Code-Golf , also gewinnt der kürzeste Code in Bytes. Standardlücken sind nicht erlaubt.
Testfälle:
// Format [lifespan] [list of village coordinates] -> [maximum visit-able villages]
4 -1,0 1,0 2,0 3,0 4,0 5,0 -> 3
4 1,1 2,2 3,3 -> 2
5 1,1 2,1 3,1 4,1 5,0 5,1 -> 4
quelle
Antworten:
Jelly,
30292725 BytesProbieren Sie es online!
Anscheinend ignoriert Jellys Skalarprodukt nur die Nichtübereinstimmung der Listengröße und multipliziert die zusätzlichen Elemente des anderen Arrays nicht, sondern fügt sie nur hinzu. Spart 2 Bytes.
Erläuterung
quelle
Java 7,
206201 BytesVielen Dank an @KevinCruijssen für das Speichern von 5 Bytes
Ungolfed
quelle
i-x
zweimal undb[c]-y
zweimal, so dass Sie,t
zu den Ints hinzufügen können, und verwenden Sie dann diese:Math.sqrt((t=i-x)*t+(t=b[c]-y)*t)*1
anstelle vonMath.sqrt((i-x)*(i-x)+(b[c]-y)*(b[c]-y))*1
.Scala, 196 Bytes
Ungolfed:
Erklärung:
quelle
JavaScript (ES6), 145
Anonyme rekursive Funktion, Parameter
s
ist die Kerzenlebensdauer, Parameterl
ist die Dorfkoordinatenliste.Eine Tiefensuche , zu stoppen , wenn der Abstand reachs die Kerze Lebensdauer
Weniger Golfspieler finden Sie im folgenden Ausschnitt
Prüfung
quelle
MATL , 27 Bytes
BEARBEITEN (26.11.2016): Aufgrund von Änderungen in der
Xl
Funktion muss diese im obigen Code durch ersetzt werden2$X>
. Die folgenden Links übernehmen diese Änderung.Probieren Sie es online! Oder überprüfen Sie alle Testfälle .
Erläuterung
Die Kürbisentfernung zwischen zwei Städten, die in jeder Koordinate Δ x und Δ y voneinander getrennt sind, kann als (| Δ x | + | Δ y | + max (| Δ x |, | Δ y |)) / 2 erhalten werden.
Der Code folgt diesen Schritten:
Kommentierter Code:
quelle
Python 2.7 , 422 Bytes
danke an NoOneIsHere für den Hinweis auf weitere Verbesserungen!
danke an edc65 für die notierung, die liste nicht zu speichern, sondern iteratoren zu verwenden!
Probieren Sie es online!
Erläuterung:
Die Funktion berechnet den Abstand zwischen zwei Punkten nach den vorgegebenen Regeln, die Schleife durchläuft alle vom Generator der Eingabe erzeugten Permutationen und berechnet den Abstand, wenn der Abstand geringer als die Kerzenlebensdauer ist, subtrahiert sie ihn und addiert den Platz zum Zähler, wenn dieser Zähler größer als das aktuelle Maximum ist, wird er ersetzt.
ungolfed:
quelle
current
c
, undll
m
.PHP, 309 Bytes
Absolut brachiale Kraft und nicht einmal sehr kurz. Verwenden Sie wie:
Mit mehr Leerzeichen und in einer Datei gespeichert:
quelle
Python, 175 Bytes
c
ist die Lebensdauer der Kerze,l
ist eine Liste von Tupeln - Dorfkoordinaten,v
ist die Anzahl der besuchten Dörfer,(x,y)
ist ein Koordinatenpaar des Dorfes, in dem sich Jack gerade befindet.r(t)
ist eine Funktion, die die Entfernung zur aktuellen Position berechnet und verwendet wird, um die Liste so zu sortieren, dass die nächstgelegene Position erreicht wirdl[0]
. Die verwendete Formel lautet | Δx | + | Δy | - min (| Δx |, | Δy |) / 2.Probieren Sie es hier aus!
quelle
Schläger
Testen:
Ausgabe:
Der obige Code funktioniert jedoch nicht für negative Werte von x und y.
quelle