Finde die Wege!

10

Sie müssen ein Programm oder eine Funktion schreiben.

Die Eingabe ist eine 'Karte' von Zahlen. Sie können die Karte entweder als Zeichenfolge mit neuen Zeilenzeichen ( \n) oder als 2D-Array von Zeichenfolgen verwenden.

Alle Karten bestehen aus 5 mal 5 Zeichen, und die Zeichen sind immer entweder Ziffern größer als 0 oder Leerzeichen.

Hier ist ein Beispiel für eine Karte:

12 45
11233
  233
    1
2 899

Ihre Aufgabe ist es, die verbundenen Komponenten in der Karte zu finden. Eine gültige Komponente ist eine Reihe von mindestens drei horizontal und / oder vertikal ( nicht diagonal ) verbundenen identischen Ziffern ( keine Leerzeichen ). Sie müssen dann die Zeichen der gültigen verbundenen Komponenten durch xs ersetzen und das Ergebnis drucken oder zurückgeben.

Die Ausgabe für das obige Beispiel wäre also:

x2 45
xx2xx
  2xx
    1
2 899

Hier ist ein weiterer Testfall (danke an Martin Ender):

Input:
2   3
    4
 1  5
111 6
11  7

Output:
2   3
    4
 x  5
xxx 6
xx  7

Dies ist Code Golf, also gewinnt der kürzeste Code in Bytes!

Daniel
quelle
Sind Einbauten erlaubt?
Ioannes
@Joannes, ja.
Daniel

Antworten:

1

JavaScript (ES6), 171 161 139 137 136 133 132 Bytes

f=(a,i=0)=>(F=i=>" "<c&&a[i]===c&&(a[i]=n,1+F(i-1)+F(i+1)+F(i-6)+F(i+6)),n=1,c=a[i],n=F(i)>2?"x":c,c=1,F(i),i>28?a:f(a,++i+(i%6>4)))
<!-- this HTML included just for testing --><textarea rows=5 cols=6 oninput="document.querySelector`pre`.innerHTML=this.value.length==29?f([...this.value]).join``:'invalid input'">12 45&#10;11233&#10;  233&#10;    1&#10;2 899</textarea><br/><pre></pre>

Dies ist eine Übersetzung meiner Python-Antwort. E / A als Zeichenarrays.

Schade, dass es keinen effizienten Weg gibt sum...

PurkkaKoodari
quelle
5

Python 3, 238 237 200 199 192 181 Bytes

def f(a,i=0):F=lambda i,n,c:29>i>=0!=" "!=a[i]==c!=n and(a.__setitem__(i,n)or-~sum(F(i+j,n,c)for j in[-1,1,-6,6]));j=i+i//5;F(j,[a[j],"x"][2<F(j,1,a[j])],1);i>23or f(a,i+1);return a

Definiert eine Funktion f(a), die die Eingabe als Array von Zeichen verwendet und dasselbe geänderte Array zurückgibt. ( Zeichenarrays sind standardmäßig als Zeichenfolgen zulässig. )

Ungolfed mit Erklärung

Der geänderte Code ist rekursiv, funktioniert aber genauso.

# The main function; fills all continuous nonempty areas of size >= 3 in array
# with x's. Both modifies and returns array.
def findpaths(array):
    # Fills a continuous area of curr_char in array with new_char, starting
    # from index. Returns the number of cells affected.
    def floodfill(index, new_char, curr_char):
        if (0 <= index < 29                   # Check that the position is in bounds
                and (index + 1) % 6 != 0      # Don't fill newlines
                and array[index] != " "       # Don't fill empty cells
                and array[index] == curr_char # Don't fill over other characters
                and curr_char != new_char):   # Don't fill already filled-in cells
            array[index] = new_char # Fill current position
            return (1 # Add neighboring cells' results, plus 1 for this cell
                    + floodfill(index + 1, new_char, curr_char)  # Next char
                    + floodfill(index - 1, new_char, curr_char)  # Previous char
                    + floodfill(index + 6, new_char, curr_char)  # Next line
                    + floodfill(index - 6, new_char, curr_char)) # Previous line
        return 0 # Nothing was filled. The golfed solution returns False here,
                 # but that's coerced to 0 when adding.

    for i in range(25): # Loop through the 25 cells
        i += i // 5 # Accommodate for newlines in input
        curr_char = array[i] # Get the cell's contents
        # Fill the area from the cell with dummies
        area_size = floodfill(i, 1, curr_char)
        # Convert dummies to "x" if area was large enough, back to original otherwise
        fill_char = "x" if 2 < area_size else curr_char
        floodfill(i, fill_char, 1)
    return array
PurkkaKoodari
quelle
2 Bytes aus, um die mathematica-Lösung zu schlagen ...
FlipTack
1
@FlipTack Ja. Ich glaube nicht, dass es heute passiert, aber ich übersetze dies in JS und es sieht vielversprechend aus.
PurkkaKoodari
3

Ruby, 304 Bytes

def b(s,i)
  @v=[]
  b2(s,i,s[i])
end
def b2(s,i,c)
  if(0...s.size)===i&&s[i]==c&&!@v[i]
    @v[i]=s[i]='x'
    [1,-1,6,-6].each{|j|b2(s,i+j,c)}
  end
  s
end
def f(s)
  z = s.dup
  ps = ->(i){b(z.dup,i).scan('x').size}
  (0...s.size).each{|i|b(s, i)if ![' ',"\n"].include?(s[i])&&ps.call(i)>2}
  s
end

Anwendungsbeispiel:

puts f(File.read("map.txt"))

Der Code verwendet die Blot-Methode erneut, um die Pfadlänge zu berechnen.

Variablen / Methoden:

  • f (s): Funktion zum Konvertieren einer Kartenzeichenfolge, gibt eine neue Karte mit 'x' zurück
  • ps (i): Pfadgröße vom Kartenindex i (wobei x = i% 6, y = i / 6)
  • s: Eingabezeichenfolge, durch "\ n" getrennte Kartenlinien
  • z: Kopie der Eingabezeichenfolge
  • b (s, i): 'Blot'-Funktion: Schreibt' x 'aus dem Kartenindex i über Pfade
  • @v: 'besucht' Array

Versuch einer detaillierteren Erklärung:

Erstellen Sie eine Kopie der Eingabezeichenfolge, mit der wir die Länge des Pfads von einem bestimmten Punkt in der Karte ermitteln.

z = s.dup

Definieren Sie eine anonyme Funktion 'ps' (Pfadlänge) (Lambda), die den Kartenindex i als Argument verwendet. es gibt die Länge des Pfades von diesem Punkt zurück. Dazu wird die Methode 'b' (Blot) aufgerufen, um x in eine Kopie der Originalkarte einzufügen, und anschließend die Anzahl der x in der zurückgegebenen Zeichenfolge gezählt.

  ps = ->(i){b(z.dup,i).scan('x').size}

Der folgende Teil durchläuft jedes Zeichen in der Karte (Index i, Zeichen s [i]). Es ruft die Funktion 'b' (Blot) an der Kartenposition i auf, wenn die Pfadlänge von Position i größer als 2 ist und wenn es sich nicht um ein Leerzeichen oder ein Zeilenumbruchzeichen handelt.

  (0...s.size).each { |i|
     b(s, i) if ![' ',"\n"].include?(s[i]) && ps.call(i) > 2
  }

Die Funktion b (Blot) verwendet die Map-Zeichenfolge und einen Index als Argument. Es initialisiert @v (besuchtes Array) und ruft die Hilfsfunktion b2 auf.

def b(s,i)
  @v=[]
  b2(s,i,s[i])
end

Die Funktion b2 verwendet die Kartenzeichenfolge, eine Kartenposition (i) und ein Zeichen im aktuellen Pfad (c). Es ruft sich rekursiv auf, um verbundene Ziffernabschnitte durch das Zeichen 'x' zu ersetzen. es gibt die Eingabezeichenfolge zurück (dies ist so, dass die ps-Funktion scan () für den Rückgabewert aufrufen kann).

Diese if-Anweisung überprüft, ob die angegebene Kartenposition (i) innerhalb der Grenzen der Zeichenfolge (0 ... s.size) liegt und ob das Zeichen bei s [i] mit dem Startzeichen identisch ist. Außerdem wird @v [i] aktiviert, um eine unendliche Rekursion zu vermeiden.

if(0...s.size) === i && s[i] == c && !@v[i]

Dies ist das Bit, das das Zeichen am Index (i) durch das Zeichen 'x' ersetzt. Außerdem wird dieser Index als besucht markiert.

@v[i] = s[i] = 'x'

Hier ruft sich b2 rekursiv auf und sucht nach dem Pfad. i + 1 ist ein Zeichen rechts, i-1 ist ein Zeichen links, i + 6 ist eine Zeile tiefer (5 Ziffern + 1 Zeilenumbruch = 6 Zeichen), i-6 ist eine Zeile höher.

[1,-1,6,-6].each { |j| b2(s, i+j, c) }
Andrew
quelle
1

C (Ansi), 243 233 179 188 Bytes

Golf:

#define O o[1][l]
x,n,l,L;r(o,l)char**o;{if(!(l>L|l<0|O<47|O!=x))n++,O++,r(o,l-1),r(o,l+6),r(o,l-6),r(o,l+1),n>2?O='x':O--;}main(g,o)char**o;{for(;(L=30)>l;l++)n=0,x=O,r(o,l);puts(o[1]);}

Mit Anmerkungen:

#define O o[1][l]
x,n,l,L;      /*-------------------------- Globals*/
r(o,l)char**o;{ /*------------------------ Recursive Function*/
    if(!(l>L|l<0|O<47|O!=x)) /*----------- if this cell is valid(in
                                              range, is a number, is the 
                                              same as the parent number*/
    n++,     /*--------------------------- Increment count*/
    O++,     /*--------------------------- Increment character to mark*/
    r(o,l-1),  /*------------------------- Recurse left*/
    r(o,l+6),  /*------------------------- Recurse down*/
    r(o,l-6),  /*------------------------- Recurse down*/
    r(o,l+1),  /*------------------------- Recurse right*/
    n>2?O='x':O--;  /*---------------------If greater than 3, replace with x, else decrement character*/ 
}          /*----------------------------- Return*/

main(g,o)char**o;{ /*--------------------- Main*/
    for(;l<(L=30);l++){ /*---------------- For entire string and set L*/
        n=0;
        x=O;        /*-------------------- set counter to 0*/
        r(o,l); /*------------------------ Recurse*/
    } /*---------------------------------- End While*/
    puts(o[1]); /*------------------------ Print*/

}}

Eingang:

Erwartet eine neue Zeile am Anfang und Ende der Zeichenfolge.

Beispiel Eingabe:

./findPaths "
12 45
11233
  233
    1
2 899
"

Beispielausgabe:

x2 45
xx2xx
  2xx
    1
2 899

Aktualisieren

Durch das Fixieren des Rasters konnte ich fast 60 Bytes sparen.

dj0wns
quelle
Ich denke, ich kann wie 22 Zeichen speichern, wenn ich dies auf eine feste Kartengröße ändere - ich werde das ändern, wenn ich etwas anderes finde, das ich ändern möchte
dj0wns
1

Mathematica, 180 Bytes

(f=Flatten@#;p=Partition)[If[Tr[1^VertexComponent[r~Graph~Cases[##&@@p[#,2,1]&/@Join[g=p[r,5],g],{a_,b_}/;(A=f[[a]])==f[[b]]&&A!=" ":>a<->b],#]]<3,f[[#]],"x"]&/@(r=Range@25),5]&

Erläuterung:

(f=Flatten@#;p=Partition)[
  If[
    Tr[1^VertexComponent[
        r~Graph~Cases[
          ##&@@p[#,2,1]&/@Join[g=p[r,5],g],
          {a_,b_}/;(A=f[[a]])==f[[b]]&&A!=" ":>a<->b
        ],
        #
      ]]<3,
    f[[#]],
    "x"
  ]&/@(r=Range@25),
  5
]&

Reine Funktion, die ein 5x5Array akzeptiert . ist das 3-Byte-Zeichen U+F3C7für den privaten Gebrauch, das den Postfix-Transponierungsoperator darstellt \[Transpose].

(f=Flatten@#;p=Partition): Glättet die Eingabeliste und speichert sie in f. Legt es fest p = Partitionund gibt es zurück.

g=p[r,5]: Das Array {{1,2,3,4,5}, ..., {21,22,23,24,25}}(dies liegt daran, dass res auf gesetzt wird Range@25).

Join[g=p[r,5],g]: die Liste der Zeilen und Spalten von g.

p[#,2,1]&: Reine Funktion, die die Liste #in Unterlisten 2mit einer Überlappung unterteilt 1; dh die Liste benachbarter Paare in #.

##&@@p[#,2,1]&: Wie oben, außer dass a zurückgegeben wird Sequence.

##&@@p[#,2,1]&/@Join[g=p[r,5],g]: Ordnet die vorherige Funktion der Zeilen und Spalten von gzu, um eine Liste aller benachbarten Einträge in zu erhalten g. Mein Bauch sagt, dass es einen kürzeren Weg gibt, dies zu tun.

r~Graph~Cases[...]: Graph, dessen Eckpunkte die ganzen Zahlen sind 1, ..., 25und dessen Kanten die Kanten zwischen benachbarten Einträgen sind, in gdenen dieselben entsprechenden Einträge im Eingabearray vorhanden sind (außer " ")

{a_,b_}/;(A=f[[a]])==f[[b]]&&A!=" ": Muster, das so übereinstimmt {a,b}, dass f[[a]] == f[[b]](gleicher Wert im Eingabearray) und das nicht gleich ist " ". Set A = f[[a]]speichern 1Byte.

...:>a<->b: Ersetzen Sie jede Übereinstimmung durch eine ungerichtete Kante von a nach b.

VertexComponent: Gibt die verbundene Komponente des zweiten Arguments (einen Scheitelpunkt) im ersten Argument (ein Diagramm) zurück.

Tr[1^VertexComponent[...]]: Die Größe der angeschlossenen Komponente. Speichert 1Byte von Length@VertexComponent[...].

If[Tr[...]<3,f[[#]],"x"]&: Reine Funktion, die einen Eintrag #in nimmt g. Wenn die Größe der angeschlossenen Komponente kleiner als ist 3, ersetzen Sie sie durch den entsprechenden Eintrag in der Eingabe. Andernfalls ersetzen Sie es durch "x".

(f=Flatten@#;p=Partition)[...,5]: Und schließlich das Ergebnis in ein 5x5Array umformen .

Genisis
quelle
0

Clojure, 188 Bytes

Das ist ziemlich überwältigend: D.

#(apply str(map-indexed(fn[i v](if((set(flatten(for[m(range 30)](let[n(for[p[-1 -6 1 6]:when(=(get %(+ m p)0)((set"123456789")(% m)))](+ m p))](if(< 1(count n))(conj n m)[])))))i)\x v))%))

Wird so aufgerufen (es wird ein 1D-Vektor von Zeichen benötigt):

(def f #(apply str(...))

(print (str "\n" (f (vec (str "12 45\n"
                              "11233\n"
                              "  233\n"
                              "    1\n"
                              "2 899\n")))))

(print (str "\n" (f (vec (str "2   3\n"
                              "    4\n"
                              " 1  5\n"
                              "111 6\n"
                              "11  7\n")))))

Zu faul, um es zu lösen, for[m(range 30)]besucht aber im Grunde jeden Index und für jeden Index erstellt das Innere let[n(for[p[-1 -6 1 6]...(+ m p))]eine Liste von 0 bis 4 Elementen, in der Orte aufgelistet sind, die den gleichen Wert (1 - 9) wie der mittlere Ort hatten. Wenn mehr als ein Nachbar mit dem Mittelstück übereinstimmt, bedeutet dies, dass alle diese einen Cluster bilden, sodass diese Positionen zu dem Satz hinzugefügt werden, der bei verwendet wird (if((set(flatten(...)))i). Wenn der Index iaus der Menge gefunden wird, \xwird er ausgegeben und ansonsten der ursprüngliche Wert. Das :when( ... )ist ziemlich interessant ...

NikoNyrh
quelle