Fülle ein Gitter mit Rittern

15

Eine Ritterfüllung ist eine Überflutungsfüllung, die die Konnektivität der Ritterschachfigur verwendet. Speziell:

 1 1
1   1
  0
1   1
 1 1

(0 ist der Anfangspunkt, 1s zeigt die verbundenen Zellen)

Herausforderung

Führen Sie bei einem 2D-Raster aus Räumen und Wänden und einer anfänglichen Position eine Ritterfüllung auf dem Raster durch. Kürzester Code gewinnt.

Regeln

  • Sie können Eingaben und Ausgaben in jedem beliebigen Format (Bild, Zeichenfolge, Array, was auch immer) erstellen. Sie können die ursprüngliche Position als Teil des Eingaberasters oder als separate Koordinate verwenden. Für diese Erklärung wird das folgende Format verwendet:

    ########    # = wall
    ########    x = initial location
    ## x  ##
    ##    ##
    ########
    ##    ##
    ########
    ########
    
  • Die Ausgabe ist eine Kopie des Eingaberasters mit dem hinzugefügten Ritterfüllungsergebnis

  • Ihre Füllung darf nicht dieselbe "Farbe" wie der Raum oder die Wände haben, sondern kann dieselbe sein wie die ursprüngliche Ortsmarkierung. In dem obigen Bild wäre eine gültige Ausgabe beispielsweise:

    ########    # = wall
    ########    @ = fill (could also have been x)
    ## @ @##
    ## @ @##
    ########
    ##@ @ ##
    ########
    ########
    
  • Sie können davon ausgehen, dass das Eingabegitter immer eine 2-Zellen-Wand auf allen Seiten enthält

  • Sie können davon ausgehen, dass sich der ursprüngliche Standort niemals innerhalb einer Wand befindet
  • Sie können davon ausgehen, dass das Raster niemals größer als 1000x1000 ist
  • Builtins sind in Ordnung
  • Kürzester Code (in Bytes) gewinnt

Testfälle

#Bezeichnet in allen Testfällen eine Wand, bezeichnet einen leeren Raum und xbezeichnet den anfänglichen Ort der Füllung. @bezeichnet die Ausgabefüllung.

Input 1:

########
########
## x  ##
##    ##
########
##    ##
########
########

Output 1:

########
########
## @ @##
## @ @##
########
##@ @ ##
########
########

Input 2:

############
############
## ##    x##
## ##     ##
#####     ##
##        ##
############
############

Output 2:

############
############
## ##@@@@@##
##@##@@@@@##
#####@@@@@##
## @@@@@@@##
############
############

Input 3:

####################
####################
##  ##            ##
##  ##            ##
##  ##  ########  ##
##  ##  ########  ##
##  ##  ##    ##  ##
##  ##  ##    ##  ##
##  ##  ##    ##  ##
##  ##  ##    ##  ##
##  ##  ########  ##
##  ##  ########  ##
##  ##        ##  ##
##  ##       x##  ##
##  ############  ##
##  ############  ##
##                ##
##                ##
####################
####################

Output 3:

####################
####################
##@@##@@@@@@@@@@@@##
##@@##@@@@@@@@@@@@##
##@@##@@########@@##
##@@##@@########@@##
##@@##@@##    ##@@##
##@@##@@##    ##@@##
##@@##@@##    ##@@##
##@@##@@##    ##@@##
##@@##@@########@@##
##@@##@@########@@##
##@@##@@@@@@@@##@@##
##@@##@@@@@@@@##@@##
##@@############@@##
##@@############@@##
##@@@@@@@@@@@@@@@@##
##@@@@@@@@@@@@@@@@##
####################
####################

Input 4:

################
################
##           ###
##     x     ###
##  #######  ###
##  #######  ###
##  ##   ##  ###
##  ##   ##  ###
##  ##   ##  ###
##  ########  ##
##  ########  ##
##        ##  ##
##        ##  ##
################
################

Output 4:

################
################
##   @   @   ###
## @   @   @ ###
##  #######  ###
##@ ####### @###
##  ##   ##  ###
## @##   ##@ ###
##  ##   ##  ###
##@ ########@ ##
##  ########  ##
## @   @  ## @##
##   @   @##  ##
################
################

Input 5:

##############
##############
##         ###
##         ###
##         ###
##   ###   ###
##   #x#   ###
##   ###   ###
##         ###
##         ###
##         ###
##############
##############

Output 5:

##############
##############
##@@@@@@@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##@@@###@@@###
##@@@#@#@@@###
##@@@###@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##############
##############
Dave
quelle
Etwas verwandt.
Martin Ender

Antworten:

4

Oktave, 73 Bytes

function a=F(s,a)do;b=a;until(a=~s&imdilate(a,de2bi(")0#0)"-31)))==b;a+=s

Online Demo!

* Einige Änderungen wurden angewendet, um in rextester ausgeführt zu werden.

Eine Funktion, die ein 2d-Array von 0 & 2 als Wand und ein Array von 0 & 1 als Anfangsposition verwendet und ein Array von 0 & 1 & 2 ausgibt.

rahnema1
quelle
Sieht gut aus, aber muss das nicht pkg load ...außerhalb des Test-Frameworks ausgeführt werden? Wenn imdilate& de2biohne expliziten Import verfügbar ist, ist das in Ordnung.
Dave
@ Dave In früheren Versionen von Octave, einschließlich der in tio installierten Version, war es möglich, ein Paket zu installieren, damit es automatisch geladen werden kann. Jetzt bemerkte ich, dass diese Funktion aus Octave entfernt wurde! Bitte sehen Sie dies .
Rahnema1
Meinetwegen. Solange Sie eine Version anvisieren, die zuvor -autoentfernt wurde, ist dies kein Problem, und ich vermute, dass diese Antwort keine neuen Funktionen verwendet.
Dave
3

JavaScript (ES6), 116 Byte

f=(s,l=s.search`
`,t=s.replace(eval(`/(x| )([^]{${l-2}}(....)?|[^]{${l+l}}(..)?)(?!\\1)[x ]/`),'x$2x'))=>s==t?s:f(t)

v=(s,l=s.search`
`)=>!/^(#+)\n\1\n[^]*x[^]*\n\1\n\1$/.test(s)|s.split`
`.some(s=>s.length-l|!/^##.+##$/.test(s))&&`Invalid Input`
textarea{font-family:monospace}
<textarea rows=11 cols=33 oninput=o.value=v(this.value)||f(this.value)></textarea><textarea rows=11 cols=33 id=o reaodnly></textarea>

Basierend auf meiner Antwort auf Fehlerhafte Schlösser erkennen . Füllt mit xs.

Neil
quelle
Können Sie ein Test-Snippet / einen Test-Link hinzufügen?
Amtszeit
2

Python 3 , 394 387 381 356 352 347 319 313 154 139 Bytes

  • 154 Bytes, nachdem nur die Kernfunktion und nicht die Funktion für die E / A-Formatierung gezählt wurde
  • 7 Bytes gespart: dank @Jacoblaw und @ Mr.Xcoder: except:0
  • 28 Bytes gespart !!!: Dank @ovs: try: exceptBlock und mehrere andere Golf losgeworden
  • Vielen Dank an @ Dave für das schöne Testmodul.
  • 6 Bytes gespart: g[(a,b)]als geradeg[a,b]
  • @nore 15 Bytes gespeichert !!! :
def x(g,a,b,m):
 if(a,b)in g and"!">g[a,b]or m:
  g[a,b]="@"
  for i in 1,2,-1,-2:
   for j in 3-abs(i),abs(i)-3:g=x(g,a+i,b+j,0)
 return g

Probieren Sie es online!

officialaimm
quelle
1
kannst du except:passstattdessen tun
Jacoblaw
1
Ich bin mir ziemlich sicher, dass dies stark golfen werden kann
Mr. Xcoder
2
@Jacoblaw noch besser:except:0
Mr. Xcoder
1
319 Bytes
Ovs
1
Hier ist eine etwas einfacher zu testende Version des TiO: Probieren Sie es online aus!
Dave
1

Mathematica, 117 Bytes

Die übliche Geschichte: Leistungsstarke Einbauten, aber lange Namen…

HighlightGraph[g,ConnectedComponents[h=Subgraph[g=KnightTourGraph@@Dimensions@#,Flatten@#~Position~1],#2]~Prepend~h]&

Probieren Sie es am Wolfram Sandkasten!

Es werden zwei Eingaben benötigt: Zuerst wird das Eingaberaster als Array von 0s (für die Wände) und 1s (für Leerzeichen), dann eine einzelne Ganzzahl für die Startposition, die durch Nummerieren des Rasters entlang der Zeilen von oben nach unten ermittelt wird, z

1  2  3  4  5
6  7  8  9  10
11 12 13 14 ...

Sie können die Funktion wie folgt aufrufen HighlightGraph[...~Prepend~h]&[{{0,0,...,0}, {0,0,...,0}, ..., {0,0,...,0}}, 20].

Die KnightTourGraphFunktion erstellt einen Graphen mit Scheitelpunkten, die Positionen im Gitter entsprechen, und Kanten, die gültigen Ritterbewegungen entsprechen. Dann nehmen wir Subgraphdie Scheitelpunkte, die keine Wände sind, und ermitteln die ConnectedComponentsScheitelpunkte des Startscheitelpunkts. Die Ausgabe ist ein Diagramm (um 90 ° gegen den Uhrzeigersinn gedreht), bei dem die nicht an der Wand befindlichen Scheitelpunkte rot und die ausgefüllten Scheitelpunkte gelb hervorgehoben sind. Für den ersten Testfall sieht die Ausgabe beispielsweise folgendermaßen aus:

Ausgabe für Testfall 1: Eine Grafik mit einigen hervorgehobenen Bereichen

Kein Baum
quelle
Nun, das sieht auf jeden Fall so aus, als wäre es am schwierigsten zu testen! Könnten Sie ein Beispiel hinzufügen, wie man es in der Sandbox aufruft, für diejenigen von uns, die Mathematica seit unserer Universitätszeit nicht mehr berührt haben? Meine Versuche von f=... f[{0,...,0;0,...,0}, 19]und ähnlichem sind kläglich gescheitert.
Dave
@ Dave, mit können Sie die Funktion aufrufen HighlightGraph[g,ConnectedComponents[h=Subgraph[g=KnightTourGraph@@Dimensions@#,Flatten@#~Position~1],#2]~Prepend~h]&[{{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,1,1,1,1,0,0},{0,0,1,1,1,1,0,0},{0,0,0,0,0,0,0,0},{0,0,1,1,1,1,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0}},20](für den ersten Testfall). Ich habe das in der Frage bearbeitet - tut mir leid, dass es von Anfang an nicht da war!
Kein Baum