Hintergrund
Schleimpilze sind fantastisch. Wenn Sie sie auf eine Oberfläche mit Nahrungsquellen legen, breiten sie ihre Ranken aus, um die Nahrung zu finden. Danach bilden sie ein Netzwerk von Verbindungen zwischen den Quellen. Bei dieser Herausforderung simulieren Sie einen Schleimpilz, der nach Nahrung sucht. Darüber hinaus stoppt diese spezielle Form, sobald sie genug gefunden hat.
Eingang
Ihre Eingaben müssen eine Liste L
von 2D-Ganzzahlkoordinaten im nativen Format Ihrer Sprache und eine nichtnegative Ganzzahl sein N
. Die Liste L
ist garantiert duplikationsfrei, kann jedoch nicht sortiert werden. Die Eingabe N
liegt zwischen 0 und der Länge von L
einschließlich.
Die Liste enthält L
eine Reihe von Koordinaten für Nahrungsquellen. Zum Beispiel die Liste
[(0,0),(2,-1),(3,1),(0,4),(5,5)]
könnte visuell interpretiert werden als
o
o
o
o
o
Ausgabe
Ihre Ausgabe ist eine weitere duplikationsfreie Liste K
von 2D-Ganzzahlkoordinaten im selben Format wie die Eingabe. Es stellt das durch die Schleimpilz gebildete Netzwerk dar und muss die folgenden Bedingungen erfüllen:
- Der Schnittpunkt von
L
undK
hat genau die GrößeN
. - Die Menge
K
ist als Teilmenge des ganzzahligen Gitters verbunden (über orthogonale oder diagonale Nachbarschaften). - Wenn eine Koordinate von
K
entfernt wird, erfüllt sie die ersten beiden Bedingungen nicht mehr.
Beachten Sie, dass N = 0
die Ausgabe eine leere Liste sein muss.
Ein Beispiel für eine akzeptable Ausgabe für die obige Liste L
und N = 4
wäre
[(0,0),(0,1),(0,2),(0,3),(0,4),(1,4),(2,4),(3,3),(3,2),(3,1),(3,5),(4,5),(5,5)]
die als visualisiert werden kann
xxO
Oxx
x x
x x
x O
O
o
wobei jedes O
eine Koordinate in beiden L
und darstellt K
und jedes x
eine Koordinate in K
aber nicht in darstellt L
. Andere Ausgänge sind ebenfalls akzeptabel, und die "Ranken" müssen nicht so kurz wie möglich sein. Dies ist beispielsweise auch eine akzeptable Lösung:
xxOxx
Oxx x
x x
x x
x o x
O x
Ox
Regeln
Sowohl die Eingabe als auch die Ausgabe müssen Listen sein, keine Mengen oder andere Datentypen. Die Koordinaten selbst können Listen oder Tupel sein. Sie können die Reihenfolge der beiden Eingänge bei Bedarf ändern.
Sie können entweder ein vollständiges Programm oder eine Funktion schreiben. Die niedrigste Byteanzahl gewinnt und Standardschlupflöcher sind nicht zulässig.
Testfälle
Ihr Programm sollte diese Listen für alle anwendbaren Werte von bearbeiten N
.
[]
[(2,3)]
[(0,0),(1,0),(0,1),(1,1)]
[(0,0),(2,-1),(3,1),(0,4),(5,5)]
[(0,0),(1,0),(2,0),(3,0),(0,3),(1,3),(2,3),(3,3)]
[(0,0),(1,0),(2,0),(3,0),(0,3),(1,3),(2,3),(3,3),(0,1),(0,2),(3,1),(3,2),(8,1),(8,2),(-5,1),(-5,2)]
[(0,0),(20,0),(15,15),(-10,4),(-10,3),(0,-5),(7,6),(7,7),(8,8),(9,8),(10,-2),(-1,12),(-3,10)]
[(0,0),(1,0),(2,0),(3,0),(5,0),(6,0),(7,0),(0,9),(1,9),(2,9),(3,8),(4,9),(5,10),(6,10),(7,9),(3,3),(4,4),(5,5)]
Visualisiert:
===
o
===
oo
oo
===
o
o
o
o
o
===
oooo
oooo
===
oooo
o o o o
o o o o
oooo
===
o
o
o
oo
o
o
o
o
o o
o
o
===
oo
ooo o o
o
o
o
o
oooo ooo
quelle