Załóżmy, że masz kilka wyraźnych wielkich liter rozproszonych w prostokątnym układzie niepozornych komórek. Każda komórka w tablicy należy do najbliższej litery , zdefiniowanej jako litera osiągalna w najmniejszej liczbie poziomych i / lub pionowych kroków - bez kroków po przekątnej. (Jeśli komórka jest w równej odległości od dwóch lub więcej najbliższych liter, należy do którejkolwiek z tych liter, która jest pierwsza w kolejności alfabetycznej. Komórka z wielką literą należy do tej litery.) Komórki graniczne to komórki, które są poziomo lub pionowo przylegające do jednej lub więcej komórek, które nie należą do litery, do której one należą.

Napisz podprogram procedury o następującym działaniu, tworząc rodzaj diagramu Voronoi ...

Dane wejściowe : dowolny ciąg ASCII złożony tylko z kropek, wielkich liter i znaków nowej linii, tak że po wydrukowaniu wyświetla prostokątną tablicę opisanego powyżej rodzaju, z kropkami działającymi jak puste miejsca.

Dane wyjściowe : wydruk ciągu wejściowego z każdą pustą komórką graniczną zastąpioną małą wersją litery, do której należy. (Podprogram wykonuje wydruk).

Przykład 1

Wkład:

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

Wydajność:

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

Szkic podkreślający granice:

Przykład 2

Wkład:

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

Wydajność:

..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...............

Wzmocnienie kolorów:

GolfScript, 138 144 137 znaków

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

Dane wejściowe są przekazywane do podprogramu jako pojedynczy ciąg znaków na stosie. Niestety musiałem skorzystać z putspowodu, że procedura musi wydrukować wynik.

Objaśnienie kodu

Blok zewnętrzny zasadniczo zapętla się we wszystkich pozycjach (x, y) zgodnie z rozmiarem prostokątów wejściowych. W pętli współrzędne xiy pozostają za każdym razem na stosie. Po zakończeniu każdego wiersza wynik jest drukowany na konsoli.

:^              # 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

Kod wykonywany w pętli najpierw pobiera odpowiedni znak danych wejściowych.

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

Następnie w zasadzie sprawdzamy, czy mamy ., tzn. Czy (ewentualnie) musimy zastąpić znak.

.'.'={              # 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

Ponownie wewnętrzny kod zaczyna się od pętli, teraz ponad wszystkimi współrzędnymi (x, y) (x, y + 1) (x + 1, y) (x, y-1) (x-1, y)

{                   
    @~@+@@+\        # 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]

Ostatni fragment kodu wewnętrznego zwraca po prostu (małą literę) literę najbliższego punktu, biorąc pod uwagę dwie współrzędne.

{                   # 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

Tak więc z pięciu najbliższych liter dla współrzędnych (x, y) (x, y + 1) (x + 1, y) (x, y-1) (x-1, y) weź pierwszą, jeśli nie wszystkie są równe, w przeciwnym razie weź ..

.                   # 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 znaków:

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"))

Istnieją trzy części, z których każda musi znajdować się w osobnej linii ze względu na składnię Pythona:

1. Pierwszy wiersz ustawia zmienne. wto szerokość rzędu deski (w tym nowego wiersza na końcu, który zostanie przetworzony jako kolumna wypełnienia). rto rangeobiekt, który indeksuje wszystkie znaki s. njest krotką przesunięć indeksu, aby dostać się do sąsiadów postaci (więc jeśli chcesz, aby litery rozłożyły się po przekątnej, wystarczy dodać -w-1,-w+1,w-1,w+1do krotki). xto krótka nazwa str.replacemetody, która jest używana kilkakrotnie w późniejszym kodzie (wywołania będą jednak wyglądać dziwnie, ponieważ używam x(s,*"xy")do zapisywania znaków, a nie konwencjonalnych s.replace("x", "y")). W stym momencie łańcuch parametru jest również nieco modyfikowany, a jego .znaki i znaki nowej linii są zastępowane przez~znaki (ponieważ sortują po wszystkich literach). Na ~końcu dodawane są również wartości dopełniania wiersza . tzostanie później użyty jako odniesienie do „starej” wersji s, ale musi zostać zainicjowany na coś, co nie jest równe sna początku, a zero przyjmuje tylko jeden znak (byłaby to bardziej pythoniczna wartość None, ale to trzy dodatkowe znaki) .
2. Druga linia zawiera pętlę, która wielokrotnie aktualizuje się sprzy użyciu listy. Jak zrozumienie iteracje nad indeksy s, ~znaki są zastępowane przez minswoich sąsiadów. Jeśli ~postać została całkowicie otoczona przez inne osoby ~, nic to nie da. Gdyby to było obok jednej lub więcej liter, staje się najmniejsza z nich (faworyzowanie "a"ponad "b"itp). Nowe linie, które zostały zamienione na ~znaki, są zachowywane poprzez wykrycie ich indeksów za pomocą operatora modułu. Wiersz dopełniania na końcu nie jest aktualizowany w rozumieniu listy (ponieważ zakres indeksów rzostał obliczony przed ich dodaniem s). Zamiast tego nowy rząd~znaki są dodawane po zakończeniu zrozumienia. Zauważ, że spo pierwszym przejściu pętli staje się listą znaków, a nie ciągiem znaków (ale ponieważ Python jest elastyczny w kwestii typów, nadal możemy indeksować, aby uzyskać znaki w ten sam sposób).
3. Ostatni wiersz wydobywa wnętrze diagramu i przekształca znaki w ciąg znaków do wydrukowania. Po pierwsze, każda litera, która jest otoczona tylko innymi jej kopiami (lub ~znakami z wypełnienia), zostaje zastąpiona przez .. Następnie wszystkie znaki są łączone w jeden ciąg. Na koniec ~znaki dopełniające są konwertowane z powrotem na znaki nowej linii i drukowany jest ciąg.

Python, 229 226 znaków

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...
.........
""")

Wypełnia powódź, aby obliczyć wynik. Trailing for/ zipcombo generuje tablicę xdla każdej komórki zawierającą wartość w tej komórce i jej czterech sąsiadach. Następnie wykorzystujemy sztuczkę Blckknght i minkilka możliwości dla każdej komórki. Są to oryginalne wartości komórki, sąsiedzi, jeśli komórka nie była jeszcze odwiedzana, lub a, .jeśli została odwiedzona, a wszyscy sąsiedzi są .równi samej komórce.

Oto jest To mój pierwszy program w języku F #. Jeśli przegapiłem jakąś funkcję tego języka, powiadom mnie, gdy się uczę.

Oto moje przykładowe dane wejściowe

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

Oto wynik

 . . . . . . . . . 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 . . . . . . .

Oto kod. Cieszyć się.

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

Teraz musimy przekonwertować te dane na tablicę dwuwymiarową, abyśmy mogli uzyskać do nich dostęp za pośrednictwem indeksatorów.

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

Stwórzmy macierz reprezentującą własność każdej komórki

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

Pozwól nam skorzystać z metody użyteczności, aby zobaczyć, co się stało.

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 "")            

Stwórzmy zapis, który reprezentuje miejsce, w którym znajduje się konkretna litera.

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

Teraz chcemy znaleźć wszystkie wielkie litery.

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)

Kiedy się poruszamy, potrzebujemy koncepcji kierunku.

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 miarę przemieszczania się będziemy musieli wiedzieć o rozmiarze. Pomoże nam to monitorować, czy wychodzimy poza granice.

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

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

Aktywny wzorzec: pasuje do kryteriów danej komórki.

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)

Teraz dochodzimy do podatku od mosiądzu. To twierdzi komórkę!

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

Korzystając z aktywnego wzorca, przejmij tę komórkę, jeśli nie została odebrana, i zwróć współrzędne sąsiednich komórek.

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

Zaczynamy tworzyć listy tej torby danych, pozwól nam stworzyć typ, aby wszystko było bardziej zrozumiałe.

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

Biorąc pod uwagę listę kryteriów zgłaszania roszczeń do komórek, przejdziemy do następnej listy, zwracając kolejne komórki, aby zgłosić roszczenia i powrócić do tej listy.

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)

Dla każdego kapitału utwórz kryteria roszczenia w każdym kierunku, a następnie rekurencyjnie przeszukaj te komórki.

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

Każdy program wymaga głównego.

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