Misalkan Anda diberi beberapa huruf besar berbeda yang tersebar dalam array persegi panjang sel-sel sebaliknya. Setiap sel dalam array milik huruf terdekat darinya, didefinisikan sebagai huruf yang dapat dijangkau dalam jumlah terkecil dari langkah horizontal dan / atau vertikal - tidak ada langkah diagonal. (Jika sel berjarak sama dari dua atau lebih huruf terdekat, itu milik mana dari huruf-huruf itu yang pertama dalam urutan abjad. Sebuah sel dengan huruf besar di dalamnya adalah milik huruf itu.) Batas- sel adalah mereka yang secara horizontal atau vertikal. berdekatan dengan satu atau lebih sel yang bukan milik surat milik mereka sendiri.

Tulis subprogram prosedur dengan perilaku berikut, menghasilkan semacam diagram Voronoi ...

Input : Setiap string ASCII yang hanya terdiri dari titik, huruf besar, dan baris baru, sehingga ketika dicetak akan menampilkan array persegi panjang dari jenis yang dijelaskan di atas, dengan titik-titik yang bertindak sebagai kosong.

Keluaran : Cetakan string input dengan masing-masing sel batas kosong digantikan oleh versi huruf kecil dari surat itu. (Subprogram melakukan pencetakan.)

Contoh 1

Memasukkan:

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

Keluaran:

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

Sebuah sketsa yang menyoroti batas-batas:

Contoh 2

Memasukkan:

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

Keluaran:

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

Peningkatan warna:

GolfScript, 138 144 137 karakter

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

Input diberikan ke subprogram sebagai string tunggal pada tumpukan. Sayangnya saya harus menggunakan putskarena persyaratan bahwa rutin harus mencetak hasilnya.

Penjelasan kode

Blok luar dasarnya loop atas semua posisi (x, y) sesuai dengan ukuran persegi panjang input. Dalam lingkaran, koordinat x dan y dibiarkan di tumpukan setiap kali. Setelah setiap baris selesai, hasilnya dicetak ke konsol.

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

Kode yang dieksekusi dalam loop pertama-tama mengambil karakter input yang sesuai.

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

Maka pada dasarnya kita periksa, jika kita punya ., yaitu jika kita (mungkin) harus mengganti karakter.

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

Sekali lagi, kode bagian dalam dimulai dengan satu lingkaran, sekarang atas semua koordinat (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]

Cuplikan kode dalam baru-baru ini hanya mengembalikan huruf (huruf kecil) dari titik terdekat, mengingat dua koordinat.

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

Jadi dari lima huruf terdekat untuk koordinat (x, y) (x, y +1) (x +1, y) (x, y-1) (x-1, y) ambil yang pertama, jika tidak semua sama, jika tidak ambil 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 karakter:

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

Ada tiga bagian, yang masing-masing harus pada jalurnya sendiri karena sintaks Python:

1. Baris pertama mengatur variabel. wadalah lebar baris papan (termasuk baris baru di akhir, yang akan didaur ulang sebagai kolom pengisi). radalah rangeobjek yang mengindeks semua karakter di s. nadalah tuple indeks offset untuk mendapatkan tetangga karakter (jadi jika Anda ingin membiarkan surat menyebar secara diagonal, Anda hanya perlu menambahkan -w-1,-w+1,w-1,w+1tuple). xadalah nama pendek untuk str.replacemetode ini, yang digunakan beberapa kali dalam kode selanjutnya (panggilan akan terlihat aneh, karena saya gunakan x(s,*"xy")untuk menyimpan karakter, daripada yang konvensional s.replace("x", "y")). The sparameter string dimodifikasi sedikit pada saat ini juga, dengan .karakter dan baris baru digantikan oleh~karakter (karena mereka mengurutkan setelah semua huruf). Nilai baris ~karakter padding juga ditambahkan ke bagian akhir. tnantinya akan digunakan sebagai referensi ke versi "lama" s, tetapi perlu diinisialisasi ke sesuatu yang tidak sama dengan sdi awal, dan nol hanya mengambil satu karakter (nilai yang lebih Pythonic akan menjadi None, tetapi itu tiga karakter tambahan) .
2. Baris kedua memiliki loop yang berulang kali diperbarui smenggunakan pemahaman daftar. Sebagai pemahaman yang berulang pada indeks s, ~karakter digantikan oleh mintetangga mereka. Jika ~karakter sepenuhnya dikelilingi oleh karakter lain ~, ini tidak akan melakukan apa-apa. Jika itu adalah sebelah satu atau lebih huruf, itu akan menjadi yang terkecil dari mereka (mendukung "a"lebih "b", dll). Baris baru yang diubah menjadi ~karakter dipertahankan dengan mendeteksi indeks mereka dengan operator modulus. Baris padding di bagian akhir tidak diperbarui dalam pemahaman daftar (karena rentang indeks,, rdihitung sebelum ditambahkan ke s). Alih-alih, barisan baru~karakter ditambahkan setelah pemahaman dilakukan. Catatan yang smenjadi daftar karakter daripada string setelah melewati pertama dari loop (tetapi karena Python fleksibel tentang tipe kita masih dapat mengindeks untuk mendapatkan karakter dengan cara yang sama).
3. Baris terakhir mengeluarkan bagian dalam diagram dan membangun kembali karakter menjadi string yang akan dicetak. Pertama, setiap huruf yang hanya dikelilingi oleh salinan dirinya sendiri (atau ~karakter dari padding) akan diganti .. Selanjutnya, semua karakter digabung menjadi satu string. Akhirnya, ~karakter padding dikonversi kembali ke baris baru dan string dicetak.

Python, 229 226 karakter

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

Apakah mengisi banjir untuk menghitung hasilnya. Trailing for/ zipcombo menghasilkan array xuntuk setiap sel yang berisi nilai dalam sel itu dan empat tetangganya. Lalu kami menggunakan trik Blckknght dan minbanyak kemungkinan untuk setiap sel. Itu adalah nilai sel asli, tetangga mana pun jika sel belum dikunjungi, atau .jika telah dikunjungi dan semua tetangga adalah .atau sama dengan sel itu sendiri.

Ini dia. Ini adalah program F # pertama saya. Jika saya melewatkan fitur bahasa, harap beri tahu saya karena saya masih belajar.

Ini adalah input sampel saya

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

Ini outputnya

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

Ini kodenya. Nikmati.

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

Sekarang kita perlu mengkonversi data itu ke array dimensi ganda sehingga kita dapat mengaksesnya melalui pengindeks.

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

Mari kita buat matriks yang mewakili kepemilikan setiap sel

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

Mari kita memiliki metode utilitas untuk melihat apa yang terjadi.

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

Mari kita membuat catatan untuk mewakili di mana huruf kapital tertentu berada.

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

Sekarang kami ingin menemukan semua huruf kapital.

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)

Ketika kita bergerak, kita membutuhkan konsep arah.

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. 

Saat kita bergerak, kita perlu tahu tentang ukuran. Ini akan membantu kita memantau apakah kita bergerak keluar dari batas.

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

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

Pola Aktif: cocok dengan kriteria sel yang diberikan.

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)

Sekarang kita mulai membayar pajak. Ini mengklaim sel!

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

Menggunakan pola aktif, klaim sel ini jika tidak diklaim, dan kembalikan koordinat sel yang berdekatan.

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

Kami mulai membuat daftar kantong data ini, mari kita buat jenis untuk membuat hal-hal lebih jelas.

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

Diberikan daftar kriteria untuk mengklaim sel, kami akan mengulangi daftar yang mengembalikan sel berikutnya untuk mengklaim dan muncul kembali ke dalam daftar itu.

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)

Untuk setiap modal, buat kriteria klaim di setiap arah dan kemudian klaim secara sel-sel tersebut.

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

Setiap program membutuhkan program utama.

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