Supongamos que le dan algunas letras mayúsculas distintas dispersas en una matriz rectangular de celdas en blanco de otro modo. Cada celda de la matriz pertenece a la letra más cercana a ella, definida como la letra alcanzable en el menor número de pasos horizontales y / o verticales, sin pasos diagonales. (Si una celda es equidistante de dos o más letras más cercanas, pertenece a cualquiera de esas letras que esté primero en orden alfabético. Una celda con una letra mayúscula pertenece a esa letra). Las celdas límite son aquellas que están horizontal o verticalmente adyacente a una o más celdas que no pertenecen a la letra a la que pertenecen.

Escriba un subprograma de procedimiento con el siguiente comportamiento, produciendo una especie de diagrama de Voronoi ...

Entrada : cualquier cadena ASCII compuesta solo de puntos, letras mayúsculas y nuevas líneas, de modo que cuando se imprime muestra una matriz rectangular del tipo descrito anteriormente, con puntos que actúan como espacios en blanco.

Salida : una impresión de la cadena de entrada con cada celda de límite en blanco reemplazada por la versión en minúscula de la letra a la que pertenece. (El subprograma imprime).

Ejemplo 1

Entrada:

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

Salida:

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

Un bosquejo que destaca los límites:

Ejemplo 2

Entrada:

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

Salida:

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

Mejora de color:

GolfScript, 138 144 137 caracteres

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

La entrada se da al subprograma como una sola cadena en la pila. Lamentablemente tuve que usar un putsdebido al requisito de que la rutina tiene que imprimir el resultado.

Explicación del código.

El bloque externo esencialmente recorre todas las posiciones (x, y) de acuerdo con el tamaño de los rectángulos de entrada. Dentro del bucle, las coordenadas x e y se dejan en la pila cada vez. Después de completar cada línea, el resultado se imprime en la consola.

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

El código ejecutado dentro del bucle primero toma el carácter correspondiente de la entrada.

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

Luego, básicamente verificamos si tenemos un ., es decir, si (posiblemente) tenemos que reemplazar el carácter.

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

Nuevamente, el código interno comienza con un bucle, ahora sobre todas las coordenadas (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]

El fragmento de código interno reciente simplemente devuelve la letra (minúscula) del punto más cercano, dadas las dos coordenadas.

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

Entonces, de las cinco letras más cercanas para las coordenadas (x, y) (x, y + 1) (x + 1, y) (x, y-1) (x-1, y) tome la primera, si no todas son igual, de lo contrario tomar 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 caracteres:

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

Hay tres partes, cada una de las cuales debe estar en su propia línea debido a la sintaxis de Python:

1. La primera línea configura las variables. wes el ancho de una fila del tablero (incluida la nueva línea al final, que se reciclará como columna de relleno). res un rangeobjeto que indexa todos los caracteres en s. nes una tupla de desplazamientos de índice para llegar a los vecinos de un personaje (por lo tanto, si desea permitir que las letras se extiendan en diagonal, solo necesitaría agregar -w-1,-w+1,w-1,w+1a la tupla). xes un nombre corto para el str.replacemétodo, que se usa varias veces en el código posterior (las llamadas se verán extrañas, ya que uso x(s,*"xy")para guardar caracteres, en lugar de los convencionales s.replace("x", "y")). La scadena de parámetros también se modifica ligeramente en este punto, y sus .caracteres y líneas nuevas se reemplazan por~caracteres (porque se ordenan después de todas las letras). Los ~caracteres de relleno de una fila también se agregan al final. tmás tarde se usará como referencia a la versión "antigua" de s, pero debe inicializarse a algo que no sea igual al sprincipio, y cero solo toma un carácter (un valor más pitónico sería None, pero eso es tres caracteres adicionales) .
2. La segunda línea tiene un bucle que se actualiza repetidamente sutilizando una lista de comprensión. A medida que la comprensión itera sobre los índices de s, los ~caracteres son reemplazados por los minde sus vecinos. Si un ~personaje estaba completamente rodeado de otros ~s, esto no hará nada. Si era junto a una o más letras, se convertirá en el más pequeño de ellos (que favorece "a"sobre "b", etc.). Las nuevas líneas que se convirtieron en ~caracteres se conservan al detectar sus índices con el operador de módulo. La fila de relleno al final no se actualiza en la comprensión de la lista (porque el rango de índices r, se calculó antes de agregarlos s). En cambio, una nueva fila de~los caracteres se agregan después de que se realiza la comprensión. Tenga en cuenta que se sconvierte en una lista de caracteres en lugar de una cadena después del primer paso del bucle (pero debido a que Python es flexible sobre los tipos, todavía podemos indexarlos para obtener los caracteres de la misma manera).
3. La última línea ahueca el interior del diagrama y reconstruye los caracteres en una cadena para imprimir. Primero, cualquier letra que esté rodeada solo por otras copias de sí misma (o ~caracteres del relleno) se reemplaza por .. A continuación, los caracteres se concatenan todos juntos en una sola cadena. Finalmente, los ~caracteres de relleno se convierten nuevamente en nuevas líneas y se imprime la cadena.

Python, 229 226 caracteres

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

¿Se llena una inundación para calcular el resultado? El trailing for/ zipcombo genera una matriz xpara cada celda que contiene el valor en esa celda y sus cuatro vecinos. Luego usamos el truco de Blckknght y minun montón de posibilidades para cada celda. Esos son el valor de celda original, cualquier vecino si la celda aún no ha sido visitada, o un .si se ha visitado y todos los vecinos son .o iguales a la celda misma.

Aquí está. Este es mi primer programa F #. Si me perdí una característica del idioma, avíseme ya que todavía estoy aprendiendo.

Aquí está mi entrada de muestra

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

Aquí está la salida

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

Aquí está el código. Disfrutar.

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

Ahora necesitamos convertir esos datos en una matriz de doble dimensión para poder acceder a ellos a través de indexadores.

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

Creemos una matriz que represente la propiedad de cada celda

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

Tengamos un método de utilidad para ver qué ha sucedido.

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

Creemos un registro para representar dónde reside una letra mayúscula en particular.

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

Ahora queremos encontrar todas las letras mayúsculas.

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)

A medida que avanzamos, necesitamos un concepto de dirección.

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. 

A medida que avanzamos, necesitaremos saber sobre el tamaño. Esto nos ayudará a controlar si nos estamos moviendo fuera de los límites.

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

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

Patrón activo: coincide con los criterios de una celda determinada.

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)

Ahora nos estamos acercando al impuesto a los metales. ¡Esto reclama la celda!

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

Usando el patrón activo, reclame esta celda si no se reclama, y ​​devuelva las coordenadas de las celdas adyacentes.

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

Estamos comenzando a crear listas de esta bolsa de datos, creemos un tipo para aclarar las cosas.

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

Dada una lista de criterios para reclamar celdas, iteraremos sobre la lista devolviendo las siguientes celdas para reclamar y recurrir a esa lista.

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)

Para cada capital, cree un criterio de reclamo en cada dirección y luego recursivamente reclame esas celdas.

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

Todo programa necesita un principal.

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