Schleimpilze können zählen!

10

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 Lvon 2D-Ganzzahlkoordinaten im nativen Format Ihrer Sprache und eine nichtnegative Ganzzahl sein N. Die Liste List garantiert duplikationsfrei, kann jedoch nicht sortiert werden. Die Eingabe Nliegt zwischen 0 und der Länge von Leinschließlich.

Die Liste enthält Leine 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 Kvon 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 Lund Khat genau die Größe N.
  • Die Menge Kist als Teilmenge des ganzzahligen Gitters verbunden (über orthogonale oder diagonale Nachbarschaften).
  • Wenn eine Koordinate von Kentfernt wird, erfüllt sie die ersten beiden Bedingungen nicht mehr.

Beachten Sie, dass N = 0die Ausgabe eine leere Liste sein muss.

Ein Beispiel für eine akzeptable Ausgabe für die obige Liste Lund N = 4wä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 Oeine Koordinate in beiden Lund darstellt Kund jedes xeine Koordinate in Kaber 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
Zgarb
quelle

Antworten:

3

CJam, 77 95 Bytes

Ich denke, das kann ein bisschen mehr Golf gespielt werden, aber hier ist:

q~$<_{{:X;]{[X\]z::-~mhW*}$~:Y{_)Y1{_@=X@=}:B~-g-{+__X=!\}:C~1B=!&}g{_(Y0B-g-\C0B=!&}g}*]_&}L?p

Eingabe geht wie N <Array of coordinate array>. Zum Beispiel:

4 [[0 0] [1 5] [2 1] [0 3] [5 0] [5 5]]

Ausgabe:

[[0 5] [1 5] [0 4] [0 3] [0 0] [0 2] [0 1] [1 1] [2 1]]

Algorithmus :

Der Algorithmus ist ziemlich einfach und sieht folgendermaßen aus:

  • Sortieren Sie das Eingabekoordinatenarray. Dadurch werden die Koordinaten zuerst nach Zeile und dann nach Spalte sortiert.
  • Jetzt wählen wir die ersten NPunkte
  • Jetzt reduzieren wir diese NPunkte. Das Ziel ist der letzte Punkt und die Quelle ist der Abschlusspunkt zu diesem letzten Punkt.
  • Dann beginnen wir mit dem Punkt ganz links oben und gehen nach rechts (oder links), bis er am oder direkt über dem nächsten Punkt liegt.
  • Dann gehen wir runter, um den nächsten Punkt zu erreichen.
  • Es wird garantiert, dass bis zum obigen Punkt in derselben Reihe kein unbedeckter Punkt mehr vorhanden ist. Dies stellt sicher, dass wir keinen anderen Punkt als den gewählten berühren N. Durch Auswahl des Schließpunkts wird auch sichergestellt, dass die zweite Regel wahr bleibt.

Probieren Sie es hier online aus

Optimierer
quelle