Suponha que você receba algumas letras maiúsculas distintas espalhadas em uma matriz retangular de células em branco. Cada célula na matriz pertence à letra mais próxima , definida como a letra alcançável no menor número de etapas horizontais e / ou verticais - sem etapas diagonais. (Se uma célula é equidistante de duas ou mais letras mais próximas, ela pertence à que ocorrer primeiro em ordem alfabética. Uma célula com uma letra maiúscula pertence a essa letra.) Limite - células são aquelas que são horizontal ou verticalmente adjacente a uma ou mais células que não pertencem à letra à qual eles próprios pertencem.

Escreva um subprograma de procedimento com o seguinte comportamento, produzindo um tipo de diagrama de Voronoi ...

Entrada : qualquer sequência ASCII composta apenas por pontos, letras maiúsculas e novas linhas, de modo que, quando impressa, exiba uma matriz retangular do tipo descrito acima, com pontos atuando como espaços em branco.

Saída : Uma impressão da sequência de entrada com cada célula limite em branco substituída pela versão em minúscula da letra à qual ela pertence. (O subprograma faz a impressão.)

Exemplo 1

Entrada:

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

Saída:

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

Um esboço destacando os limites:

Exemplo 2

Entrada:

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

Saída:

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

Aprimoramento de cores:

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}/

A entrada é fornecida ao subprograma como uma única sequência na pilha. Infelizmente, tive que usar um putsdevido ao requisito de que a rotina tenha que imprimir o resultado.

Explicação do código

O bloco externo faz um loop essencialmente sobre todas as posições (x, y) de acordo com o tamanho dos retângulos de entrada. Dentro do loop, as coordenadas xey são deixadas na pilha de cada vez. Após a conclusão de cada linha, o resultado é impresso no console.

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

O código executado dentro do loop primeiro leva o caractere correspondente da entrada.

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

Então, basicamente, verificamos, se temos um ., ou seja, se (possivelmente) temos que substituir o personagem.

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

Novamente, o código interno começa com um loop, agora sobre todas as 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]

O trecho de código interno recente simplesmente retorna a letra (minúscula) do ponto mais próximo, dadas as duas 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

Portanto, das cinco letras mais próximas para as coordenadas (x, y) (x, y + 1) (x + 1, y) (x, y-1) (x-1, y), pegue a primeira, se não todas são igual, caso contrário, pegue 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"))

Existem três partes, cada uma das quais precisa estar em sua própria linha devido à sintaxe do Python:

1. A primeira linha configura as variáveis. wé a largura de uma linha do quadro (incluindo a nova linha no final, que será reciclada como uma coluna de preenchimento). ré um rangeobjeto que indexa todos os caracteres s. né uma tupla de deslocamentos do índice para atingir os vizinhos de um caractere (portanto, se você quiser permitir que as letras se espalhem na diagonal, basta adicionar -w-1,-w+1,w-1,w+1à tupla). xé um nome abreviado para o str.replacemétodo, que é usado várias vezes no código posterior (as chamadas parecerão estranhas, já que eu uso x(s,*"xy")para salvar caracteres, em vez do convencional s.replace("x", "y")). A ssequência de parâmetros também é modificada levemente neste momento, com seus .caracteres e novas linhas sendo substituídos por~caracteres (porque eles ordenam depois de todas as letras). Os ~caracteres de preenchimento de uma linha também são adicionados ao final. tmais tarde será usado como referência à versão "antiga" de s, mas precisa ser inicializada para algo diferente sdo início e zero leva apenas um caractere (um valor mais Pythonic seria None, mas são três caracteres extras) .
2. A segunda linha possui um loop que é atualizado repetidamente susando uma compreensão de lista. À medida que a compreensão percorre os índices de s, os ~caracteres são substituídos pelos minde seus vizinhos. Se um ~personagem estiver completamente cercado por outros ~s, isso não fará nada. Se estiver ao lado de uma ou mais letras, será a menor delas (favorecendo o "a"excesso "b"etc.). As novas linhas que foram transformadas em ~caracteres são preservadas, detectando seus índices com o operador de módulo. A linha de preenchimento no final não é atualizada na compreensão da lista (porque o intervalo de índices,, rfoi calculado antes de serem adicionados a s). Em vez disso, uma nova linha de~caracteres é adicionado após a compreensão ser concluída. Observe que sse torna uma lista de caracteres em vez de uma sequência após a primeira passagem do loop (mas como o Python é flexível sobre os tipos, ainda podemos indexar para obter os caracteres da mesma maneira).
3. A última linha oculta o interior do diagrama e reconstrói os caracteres em uma sequência a ser impressa. Primeiro, qualquer carta cercada apenas por outras cópias de si mesma (ou ~caracteres do preenchimento) é substituída por .. Em seguida, todos os caracteres são concatenados juntos em uma única sequência. Por fim, os ~caracteres de preenchimento são convertidos novamente em novas linhas e a sequência é impressa.

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

Faz uma inundação preencher para calcular o resultado. O trailing for/ zipcombo gera uma matriz xpara cada célula que contém o valor nessa célula e seus quatro vizinhos. Em seguida, usamos o truque de Blckknght e várias minpossibilidades para cada célula. Esses são o valor original da célula, quaisquer vizinhos se a célula ainda não tiver sido visitada ou a .se ela tiver sido visitada e todos os vizinhos forem .iguais à própria célula.

Aqui está. Este é o meu primeiro programa de F #. Se eu perdi um recurso do idioma, me avise enquanto ainda estou aprendendo.

Aqui está a minha entrada de amostra

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

Aqui está a saída

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

Aqui está o código. Apreciar.

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

Agora, precisamos converter esses dados em uma matriz de dupla dimensão para que possamos acessá-los atravé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

Vamos criar uma matriz representando a propriedade de cada célula

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

Vamos ter um método utilitário para ver o que aconteceu.

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

Vamos criar um registro para representar onde reside uma letra maiúscula específica.

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

Agora queremos encontrar todas as letras maiú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)

À medida que avançamos, precisamos de um conceito de direção.

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. 

À medida que avançamos, precisaremos saber sobre tamanho. Isso nos ajudará a monitorar se estamos saindo dos limites.

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

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

Padrão ativo: corresponde aos critérios de uma determinada célula.

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)

Agora estamos reduzindo o imposto sobre metais. Isso reivindica a célula!

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

Usando o padrão ativo, reivindique esta célula se não for reivindicada e retorne as coordenadas das células adjacentes.

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 começando a criar listas desse pacote de dados, vamos criar um tipo para tornar as coisas mais claras.

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

Dada uma lista de critérios para reivindicar células, iteraremos sobre a lista retornando as próximas células para reivindicar e recuar nessa 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, crie um critério de reivindicação em cada direção e depois recursivamente reivindique essas células.

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 precisa de um principal.

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