Angenommen, Sie erhalten verschiedene Großbuchstaben, die in einer rechteckigen Anordnung von ansonsten leeren Zellen verteilt sind. Jede Zelle im Array gehört zu dem nächstgelegenen Buchstaben , definiert als der Buchstabe, der in der kleinsten Anzahl horizontaler und / oder vertikaler Schritte erreichbar ist - keine diagonalen Schritte. (Wenn eine Zelle , die von zwei oder mehr Buchstaben nächsten gleich weit entfernt ist, gehört sie zu welchen diesen Briefen zuerst in alphabetischer Reihenfolge. Eine Zelle mit einem Buchstaben Großbuchstaben in er dieses Schreiben gehört.) Boundary -Cells sind solche , die horizontal oder vertikal sind , benachbart zu einer oder mehreren Zellen, die nicht zu dem Buchstaben gehören, zu dem sie selbst gehören.

Schreiben Sie ein Prozedur-Unterprogramm mit folgendem Verhalten und erstellen Sie eine Art Voronoi-Diagramm ...

Eingabe : Eine beliebige ASCII-Zeichenfolge, die nur aus Punkten, Großbuchstaben und Zeilenumbrüchen besteht, sodass beim Drucken ein rechteckiges Array der oben beschriebenen Art mit Punkten als Leerzeichen angezeigt wird.

Ausgabe : Ein Ausdruck der Eingabezeichenfolge, wobei jede leere Begrenzungszelle durch die Kleinbuchstabenversion des Buchstabens ersetzt wird, zu dem sie gehört. (Das Unterprogramm druckt.)

Beispiel 1

Eingang:

......B..
.........
...A.....
.........
.......D.
.........
.C.......
.....E...
.........

Ausgabe:

...ab.B..
....ab.bb
...A.abdd
aa...ad..
cca.ad.D.
..caeed..
.C.ce.edd
..ce.E.ee
..ce.....

Eine Skizze, die die Grenzen hervorhebt:

Beispiel 2

Eingang:

............................U...........
......T.................................
........................................
.....................G..................
..R.......S..........F.D.E............I.
.........................H..............
.....YW.Z...............................
......X.................................
........................................
........................................
......MN...........V....................
......PQ................................
........................................
.............L...............J..........
........................................
........................................
....C...........K.......................
........................................
..................................A.....
...........B............................

Ausgabe:

..rt.....ts...sg......gduu..U.....ui....
..rt..T..ts...sg......gddeu......ui.....
...rt...ts....sg......gddeeu....ui......
....rttts.....sggggggGgdde.euuuui.......
..R.rywss.S....sfffffFdDdEeeeeeei.....I.
...ryywwzs.....sf....fddhHhhhhhhhi......
..ryyYWwZzs..sssffff.fddh.......hi......
..rxxxXxzzs.sllvvvvvffddh....hhhhi......
rrrxxxxnzzssl.lv....vfddh...hjjjjii.....
mmmmmmmnnnnnl.lv.....vvdh..hj....jai....
mmmmmmMNnnnnl.lv...V...vvhhj.....jaai...
ppppppPQqqql...lv.......vhj......ja.ai..
ppppp.pq.ql....lkv.....vjj.......ja..aii
cccccppqql...L.lkkv...vj.....J...ja...aa
.....cpqqlll..lk..kvvvvj........ja......
......cccbbbllk....kkkkj.......ja.......
....C...cb..bk..K......kj.....ja........
.......cb....bk........kjjjjjja.........
......cb......bk.......kaaaaaa....A.....
.....cb....B...bk......ka...............

Farbverbesserung:

GolfScript, 138 144 137 Zeichen

:^n%,,{{^n/1$=2$>1<.'.'={;{@~@+@@+\{^3$?^<n/),\,@-abs@@-abs+99*+}++^'.
'-\$1<{32+}%}++[0..1.0..(.0]2/%..&,(\0='.'if}{@@;;}if}+^n?,%puts}/

Die Eingabe wird dem Unterprogramm als einzelne Zeichenfolge auf dem Stapel übergeben. Leider musste ich putswegen der Anforderung, dass die Routine das Ergebnis ausdrucken muss, eine verwenden.

Erklärung des Codes

Der äußere Block durchläuft im Wesentlichen alle Positionen (x, y) entsprechend der Größe der Eingaberechtecke. Innerhalb der Schleife bleiben die Koordinaten x und y jedes Mal auf dem Stapel. Nach Abschluss jeder Zeile wird das Ergebnis auf der Konsole ausgegeben.

:^              # save input in variable ^
n%,,{{          # split along newlines, count rows, make list [0..rows-1] 
    ???             # loop code, see below
}+^n?,%puts}/       # ^n?, count columns, make list [0..cols-1], loop and print

Der Code, der in der Schleife ausgeführt wird, erhält zuerst das entsprechende Zeichen der Eingabe.

^n/                 # split input into lines
1$=                 # select the corresponding row
2$>1<               # select the corresponding col

Dann prüfen wir grundsätzlich, ob wir eine haben ., dh ob wir den Charakter (möglicherweise) ersetzen müssen.

.'.'={              # if the character is '.'
    ;               # throw away the '.'
    ???             # perform more code (see below)
}{                  # else
    @@;;            # remove coordinates, i.e. keep the current character 
                    # (i.e. A, B, ... or \n)
}if                 # end if

Wieder beginnt der innere Code mit einer Schleife, die nun über alle Koordinaten (x, y) (x, y + 1) (x + 1, y) (x, y-1) (x-1, y) verläuft.

{                   
    @~@+@@+\        # build coordinates x+dx, y+dy
    ???             # loop code
}++                 # push coordinates before executing loop code
[0..1.0..(.0]2/%    # loop over the coordinates [0 0] [0 1] [1 0] [0 -1] [-1 0]

Das aktuelle innere Codefragment gibt einfach den (Kleinbuchstaben) des nächstgelegenen Punkts zurück, wenn die beiden Koordinaten gegeben sind.

{                   # loop
    ^3$?^<          # find the current letter (A, B, ...) in the input string, 
                    # take anything before
    n/              # split at newlines
    ),              # from the last part take the length (i.e. column in which the letter is)
    \,              # count the number of lines remaining (i.e. row in which the letter is)
    @-abs@@-abs+    # calculate distance to the given coordinate x, y
    99*+            # multiply by 99 and add character value (used for sorting
                    # chars with equal distance)
}++                 # push the coordinates x, y
^'.
'-                  # remove '.' and newline
\$                  # now sort according to the code block above (i.e. by distance to letter)
1<{32+}%            # take the first one and make lowercase

Also von den fünf nächsten Buchstaben für die Koordinaten (x, y) (x, y + 1) (x + 1, y) (x, y-1) (x-1, y) nehmen Sie den ersten, wenn nicht alle gleich, sonst nimm a ..

.                   # copy five letter string
.&,(                # are there distinct letters?
\0=                 # first letter (i.e. nearest for coordinate x,y)
'.'                 # or dot
if                  # if command

Python 3 - 424 422 417 332 295 Zeichen:

def v(s):
 w=s.find("\n")+1;n=(-1,1,-w,w);r=range(len(s));x=str.replace;s=x(x(s,*".~"),*"\n~")+"~"*w;t=0
 while s!=t:t=s;s=[min(s[i+j]for j in n).lower()if"~"==s[i]and(i+1)%w else s[i]for i in r]+["~"]*w
 print(x("".join(s[i]if any(s[i]!=s[i+j].lower()!="~"for j in n)else"."for i in r),*"~\n"))

Es gibt drei Teile, von denen jeder aufgrund der Python-Syntax in einer eigenen Zeile stehen muss:

1. Die erste Zeile legt die Variablen fest. wist die Breite einer Reihe des Brettes (einschließlich der Zeilenvorschublinie am Ende, die als Polstersäule wiederverwertet wird). rist ein rangeObjekt, das alle Zeichen in indexiert s. nist ein Tupel von Index-Offsets, um an die Nachbarn eines Zeichens zu gelangen (wenn Sie also zulassen möchten, dass sich die Buchstaben diagonal ausbreiten, müssen Sie nur -w-1,-w+1,w-1,w+1das Tupel ergänzen ). xist eine Kurzbezeichnung für die str.replaceMethode, die im späteren Code mehrmals verwendet wird (die Aufrufe sehen jedoch merkwürdig aus, da ich x(s,*"xy")Zeichen speichere, anstatt der herkömmlichen s.replace("x", "y")). Die sParameterzeichenfolge wird an dieser Stelle ebenfalls leicht geändert, und die .Zeichen und Zeilenumbrüche werden durch ersetzt~Zeichen (weil sie nach allen Buchstaben sortieren). Die Füllzeichen einer Zeile ~werden ebenfalls am Ende hinzugefügt. twird später als Verweis auf die "alte" Version von verwendet s, muss jedoch zu sBeginn auf einen Wert initialisiert werden, der nicht gleich ist , und Null benötigt nur ein Zeichen (ein pythonischerer Wert wäre None, aber das sind drei zusätzliche Zeichen). .
2. Die zweite Zeile enthält eine Schleife, die wiederholt sanhand eines Listenverständnisses aktualisiert wird . Während das Verständnis über die Indizes von iteriert s, werden die ~Zeichen durch die minihrer Nachbarn ersetzt. Wenn ein ~Charakter vollständig von anderen ~s umgeben war, wird dies nichts bewirken. Wenn es neben einem oder mehreren Buchstaben steht, wird es der kleinste von ihnen (Bevorzugung "a"gegenüber "b"usw.). Die Zeilenumbrüche, die in ~Zeichen umgewandelt wurden, werden beibehalten, indem ihre Indizes mit dem Moduloperator ermittelt werden. Die Füllzeile am Ende wird im Listenverständnis nicht aktualisiert (da der Bereich der Indizes rberechnet wurde, bevor sie hinzugefügt wurden s). Stattdessen eine neue Reihe von~Zeichen werden hinzugefügt, nachdem das Verständnis abgeschlossen ist. Beachten Sie, dass snach dem ersten Durchlauf der Schleife eher eine Liste von Zeichen als eine Zeichenfolge angezeigt wird (da Python jedoch in Bezug auf Typen flexibel ist, können wir dennoch einen Index erstellen, um die Zeichen auf die gleiche Weise zu ermitteln).
3. In der letzten Zeile werden die Innenseiten des Diagramms ausgehöhlt und die Zeichen zu einer Zeichenfolge zusammengefügt, die gedruckt werden soll. Erstens wird jeder Buchstabe, der nur von anderen Kopien von sich selbst (oder ~Zeichen aus der Polsterung) umgeben ist, durch ersetzt .. Als nächstes werden alle Zeichen zu einer einzigen Zeichenfolge zusammengefügt. Schließlich werden die ~Füllzeichen wieder in Zeilenumbrüche umgewandelt und die Zeichenfolge gedruckt.

Python, 229 226 Zeichen

def F(s):
 e,f,b='~.\n';N=s.index(b)+1;s=s.replace(f,e)
 for i in 2*N*e:s=''.join(min([x[0]]+[[y.lower()for y in x if y>b],all(y.lower()in f+b+x[0]for y in x)*[f]][x[0]!=e])for x in zip(s,s[1:]+b,s[N:]+b*N,b+s,b*N+s))
 print s

F("""......B..
.........
...A.....
.........
.......D.
.........
.C.......
.....E...
.........
""")

Füllt sich eine Flut, um das Ergebnis zu berechnen? Das Nachziehen for/ zipKombinieren erzeugt ein Array xfür jede Zelle, die den Wert in dieser Zelle und ihren vier Nachbarn enthält. Dann verwenden wir den Trick von Blckknght und mineine Reihe von Möglichkeiten für jede Zelle. Dies sind die ursprünglichen Zellenwerte, etwaige Nachbarn, wenn die Zelle noch nicht besucht wurde, oder a, .wenn sie besucht wurden und alle Nachbarn .der Zelle selbst entsprechen oder gleich sind .

Hier ist es. Dies ist mein erstes F # -Programm. Wenn ich ein Feature der Sprache verpasst habe, benachrichtigen Sie mich bitte, da ich noch lerne.

Hier ist meine Beispieleingabe

 . . . . . . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . B . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . A . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . C . . . . . . . .
 . . . . . . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . G . . . . .
 . . . . . . . D . . . . . . . . . . . . . . . . .
 . . . . . . . . F . . . . . . . . . . . . . . . .
 . . . . . . . E . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . . . . . . .

Hier ist die Ausgabe

 . . . . . . . . . a b . . . . . . . b g . . . . .
 . . . . . . . . . a b . B . . . b b b g . . . . .
 . . . . . . . . . . a b . . . b c c c g . . . . .
 . . . . . . . . A . . a b . b c . . c g . . . . .
 . . . . . . . . . . . a b b c . . . c g . . . . .
 a a a a a a a a . . . a b c . . C . c g . . . . .
 d d d d d d d d a a a a b c . . . c g . . . . . .
 . . . . . . . . d d d d b c . . c g . G . . . . .
 . . . . . . . D d d d d d c . . c g . . . . . . .
 d d d d d d d d f f f f f f c . c g . . . . . . .
 e e e e e e e e e e e e e e c . c g . . . . . . .
 . . . . . . . . . . . . . e c . c g . . . . . . .
 . . . . . . . . . . . . . e c . c g . . . . . . .
 . . . . . . . . . . . . . e c . c g . . . . . . .

Hier ist der Code. Genießen.

// The first thing that we need is some data. 
let originalData = [
     "........................."
     "............B............" 
     "........................." 
     "........A................" 
     "........................." 
     "................C........"          
     "........................." 
     "...................G....." 
     ".......D................." 
     "........F................"           
     ".......E................."          
     "........................."
     "........................."
     "........................."
     ]

Jetzt müssen wir diese Daten in ein Array mit doppelter Dimension konvertieren, damit wir über Indexer darauf zugreifen können.

let dataMatrix = 
    originalData
    |> List.map (fun st -> st.ToCharArray())
    |> List.toArray

// We are going to need a concept of ownership for each
// cell. 
type Owned = 
    | Unclaimed
    | Owner of char
    | Claimed of char
    | Boundary of char

Lassen Sie uns eine Matrix erstellen, die den Besitz jeder Zelle darstellt

let claims =
    dataMatrix
    |> Array.map (fun row ->
        row
        |> Array.map (function
            | '.' -> Owned.Unclaimed
            | ch -> Owned.Owner(ch))
        )

Lassen Sie uns eine nützliche Methode haben, um zu sehen, was passiert ist.

let printIt () =
    printfn ""
    claims
    |> Array.iter (fun row ->
        row |> Array.iter (function
            | Owned.Claimed(ch) -> printf " ." 
            | Owned.Owner(ch) -> printf " %c" ch
            | Owned.Boundary(ch) -> printf " %c" ch
            | _ -> printf " ." )
        printfn "")            

Erstellen wir einen Datensatz, der angibt, wo sich ein bestimmter Großbuchstabe befindet.

type CapitalLocation = { X:int; Y:int; Letter:char }

Jetzt wollen wir alle Großbuchstaben finden.

let capitals = 
    dataMatrix
    |> Array.mapi (fun y row -> 
        row 
        |> Array.mapi (fun x item -> 
            match item with
            | '.' -> None
            | _ -> Some({ X=x; Y=y; Letter=item }))
        |> Array.choose id
        |> Array.toList
        )
    |> Array.fold (fun acc item -> item @ acc) List.empty<CapitalLocation>
    |> List.sortBy (fun item -> item.Letter)

Während wir uns bewegen, brauchen wir ein Konzept der Richtung.

type Direction =
    | Left = 0
    | Up = 1
    | Right = 2
    | Down = 3   

// Function gets the coordinates of the adjacent cell. 
let getCoordinates (x, y) direction =
    match direction with
    | Direction.Left -> x-1, y
    | Direction.Up -> x, y-1
    | Direction.Right -> x+1, y
    | Direction.Down -> x, y+1
    | _ -> (-1,-1) // TODO: Figure out how to best throw an error here. 

Während wir uns fortbewegen, müssen wir über die Größe Bescheid wissen. Dies hilft uns zu überwachen, ob wir uns außerhalb der Grenzen bewegen.

type Size = { Width:int; Height: int }    

// Get the size of the matrix. 
let size = {Width=originalData.Head.Length; Height=originalData.Length}

Aktives Muster: Entspricht den Kriterien einer bestimmten Zelle.

let (|OutOfBounds|UnclaimedCell|Claimed|Boundary|) (x,y) =
    match (x,y) with 
    | _,_ when x < 0 || y < 0 -> OutOfBounds
    | _,_ when x >= size.Width || y >= size.Height -> OutOfBounds
    | _ ->                     
        match claims.[y].[x] with
        | Owned.Unclaimed -> UnclaimedCell(x,y)
        | Owned.Claimed(ch) -> Claimed(x,y,ch)
        | Owned.Boundary(ch) -> Boundary(x,y,ch)
        | Owned.Owner(ch) -> Claimed(x,y,ch)

Jetzt kommen wir zur Messingsteuer. Das beansprucht die Zelle!

let claimCell letter (x, y) =         
    // Side effect: Change the value of the cell
    (claims.[y].[x] <- Owned.Claimed (System.Char.ToLower letter)) |> ignore

Beanspruchen Sie diese Zelle unter Verwendung des aktiven Musters, wenn sie nicht beansprucht wird, und geben Sie die Koordinaten der benachbarten Zellen zurück.

let claimAndReturnAdjacentCells (letter, coordinates, direction) =
    match coordinates with 
    | UnclaimedCell (x,y) ->         
        // Claim it and return the Owned object.
        claimCell letter coordinates // meaningful side effect
        // use Direction as int to allow math to be performed. 
        let directionInt = int direction;            
        Some(
            // [counter-clockwise; forward; clockwise]
            [(directionInt+3)%4; directionInt; (directionInt+1)%4]                 
            |> List.map enum<Direction>                 
            |> List.map (fun newDirection -> 
                (
                    letter, 
                    getCoordinates coordinates newDirection, 
                    newDirection
                ))
        )
    | Claimed(cx,cy,cch) when cch <> System.Char.ToLower letter-> 
        // If we find a "Claimed" element that is not our letter, we have 
        // hit a boundary. Change "Claimed" to "Boundary" and return the 
        // element that led us to evaluating this element. It is also a 
        // boundary. 
        (claims.[cy].[cx] <- Owned.Boundary (System.Char.ToLower cch)) |> ignore
        let reverseDirection = enum<Direction>(((int direction)+2)%4)
        Some[(
            cch,
            getCoordinates (cx, cy) reverseDirection,
            reverseDirection
        )]
    | _ -> None

Wir fangen an, Listen dieser Datentasche zu erstellen. Lassen Sie uns einen Typ erstellen, um die Dinge klarer zu machen.

type CellClaimCriteria = (char * (int * int) * Direction)

Wenn eine Liste mit Kriterien zum Beanspruchen von Zellen gegeben ist, werden wir die Liste durchlaufen, um die nächsten zu beanspruchenden Zellen zurückzugeben und in diese Liste zurückzukehren.

let rec claimCells (items:CellClaimCriteria list) =
    items
    |> List.fold (fun acc item ->
        let results = claimAndReturnAdjacentCells item 
        if Option.isSome(results) 
        then (acc @ Option.get results) 
        else acc
        ) List.empty<CellClaimCriteria> 
    |> (fun l ->            
        match l with
        | [] -> []
        | _ -> claimCells l)

Erstellen Sie für jedes Kapital ein Anspruchskriterium für jede Richtung und beanspruchen Sie diese Zellen dann rekursiv.

let claimCellsFromCapitalsOut ()=
    capitals
    |> List.fold (fun acc capital ->
        let getCoordinates = getCoordinates (capital.X, capital.Y)
        [Direction.Left; Direction.Up; Direction.Right; Direction.Down]
        |> List.map (fun direction ->                
            (
                capital.Letter, 
                getCoordinates direction, 
                direction
            ))
        |> (fun items -> acc @ items)) List.empty<CellClaimCriteria>
    |> claimCells

Jedes Programm braucht eine Hauptleitung.

[<EntryPoint>]
let main args = 
    printIt()
    claimCellsFromCapitalsOut()
    printIt()
    0