Supposons que l'on vous donne des lettres majuscules distinctes dispersées dans un tableau rectangulaire de cellules autrement vides. Chaque cellule du tableau appartient à la lettre la plus proche , définie comme la lettre accessible dans le plus petit nombre d'étapes horizontales et / ou verticales - pas d'étapes diagonales. (Si une cellule est équidistante de deux ou plusieurs lettres les plus proches, elle appartient à la première de ces lettres dans l'ordre alphabétique. Une cellule avec une lettre majuscule appartient à cette lettre.) Les cellules limites sont celles qui sont horizontales ou verticales adjacent à une ou plusieurs cellules n'appartenant pas à la lettre à laquelle elles appartiennent.

Écrivez un sous-programme de procédure avec le comportement suivant, produisant une sorte de diagramme de Voronoï ...

Entrée : toute chaîne ASCII composée uniquement de points, de lettres majuscules et de sauts de ligne, de telle sorte qu’une fois imprimée, elle affiche un tableau rectangulaire du type décrit ci-dessus, les points faisant office de blancs.

Sortie : une impression de la chaîne d'entrée avec chaque cellule frontière vide remplacée par la version en minuscule de la lettre à laquelle elle appartient. (Le sous-programme fait l'impression.)

Exemple 1

Contribution:

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

Sortie:

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

Un croquis soulignant les limites:

Exemple 2

Contribution:

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

Sortie:

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

Amélioration des couleurs:

GolfScript, 138 144 137 caractères

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

L'entrée est donnée au sous-programme sous la forme d'une chaîne unique sur la pile. Malheureusement, j'ai dû utiliser un en putsraison de l'exigence selon laquelle la routine doit imprimer le résultat.

Explication du code

Le bloc externe boucle essentiellement sur toutes les positions (x, y) en fonction de la taille des rectangles d'entrée. Dans la boucle, les coordonnées x et y sont laissées à chaque fois sur la pile. Une fois chaque ligne terminée, le résultat est imprimé sur la 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

Le code exécuté dans la boucle prend d'abord le caractère correspondant de l'entrée.

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

Ensuite, fondamentalement, nous vérifions si nous avons un ., c'est-à-dire si nous devons (éventuellement) remplacer le caractère.

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

Encore une fois, le code interne commence par une boucle, maintenant sur toutes les coordonnées (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]

L'extrait de code interne récent renvoie simplement la lettre (en minuscule) du point le plus proche, compte tenu des deux coordonnées.

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

Donc, à partir des cinq lettres les plus proches pour les coordonnées (x, y) (x, y + 1) (x + 1, y) (x, y-1) (x-1, y), prenez la première, sinon toutes sont égal, sinon prendre 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 caractères:

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

Il y a trois parties, chacune devant être sur sa propre ligne en raison de la syntaxe de Python:

1. La première ligne définit les variables. west la largeur d'une rangée de la planche (y compris la nouvelle ligne à la fin, qui sera recyclée comme colonne de rembourrage). rest un rangeobjet qui indexe tous les caractères de s. nest un tuple de décalages d'index pour atteindre les voisins d'un caractère (donc si vous vouliez permettre aux lettres de s'étaler en diagonale, vous auriez juste besoin d'ajouter -w-1,-w+1,w-1,w+1au tuple). xest un nom court pour la str.replaceméthode, qui est utilisée plusieurs fois dans le code ultérieur (les appels seront étranges cependant, puisque j'utilise x(s,*"xy")pour enregistrer des caractères, plutôt que le conventionnel s.replace("x", "y")). Les caractères (car ils trient après toutes les lettres). Une ligne de caractères de remplissage est également ajoutée à la fin.s chaîne de paramètres est également légèrement modifiée à ce stade, avec son. caractères et sauts de ligne étant remplacés par~~tsera utilisé plus tard comme référence à l '"ancienne" version de s, mais il doit être initialisé à quelque chose de différent sau début, et zéro ne prend qu'un seul caractère (une valeur plus Pythonique seraitNone , mais ce sont trois caractères supplémentaires) .
2. La deuxième ligne a une boucle qui se met sà jour à plusieurs reprises en utilisant une compréhension de liste. Au fur et à mesure que la compréhension parcourt les index de s, les ~caractères sont remplacés par ceux minde leurs voisins. Si un ~personnage était complètement entouré d'autres ~s, cela ne fera rien. Si elle était à côté d'une ou plusieurs lettres, il deviendra le plus petit d'entre eux ( en favorisant "a"plus "b", etc.). Les sauts de ligne qui ont été convertis en ~caractères sont conservés en détectant leurs index avec l'opérateur de module. La ligne de remplissage à la fin n'est pas mise à jour dans la liste de compréhension (car la plage d'index,, a rété calculée avant d'être ajoutée auxs ). Au lieu de cela, une nouvelle rangée de~des caractères sont ajoutés une fois la compréhension terminée. Notez que celas devient une liste de caractères plutôt qu'une chaîne après le premier passage de la boucle (mais parce que Python est flexible sur les types, nous pouvons toujours indexer pour obtenir les caractères de la même manière).
3. La dernière ligne évide l'intérieur du diagramme et reconstruit les caractères en une chaîne à imprimer. Tout d'abord, toute lettre qui n'est entourée que par d'autres copies de lui-même (ou des ~caractères du remplissage) est remplacée par .. Ensuite, les caractères sont tous concaténés ensemble dans une seule chaîne. Enfin, les ~caractères de remplissage sont reconvertis en nouvelles lignes et la chaîne est imprimée.

Python, 229 226 caractères

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

Est-ce qu'une inondation se remplit pour calculer le résultat. Le trailing for/ zipcombo génère un tableau xpour chaque cellule contenant la valeur dans cette cellule et ses quatre voisins. Ensuite, nous utilisons l'astuce de Blckknght et minun tas de possibilités pour chaque cellule. Il s'agit de la valeur de cellule d'origine, de tous les voisins si la cellule n'a pas encore été visitée, ou a .si elle a été visitée et que tous les voisins sont .ou sont égaux à la cellule elle-même.

C'est ici. Ceci est mon premier programme F #. Si j'ai raté une caractéristique de la langue, veuillez m'alerter car j'apprends encore.

Voici mon exemple d'entrée

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

Voici la sortie

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

Voici le code. Prendre plaisir.

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

Nous devons maintenant convertir ces données en un tableau à double dimension afin de pouvoir y accéder via des indexeurs.

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

Créons une matrice représentant la propriété de chaque cellule

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

Ayons une méthode utilitaire pour voir ce qui s'est passé.

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

Créons un enregistrement pour représenter où réside une majuscule particulière.

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

Maintenant, nous voulons trouver toutes les lettres majuscules.

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)

Alors que nous nous déplaçons, nous avons besoin d'un concept de direction.

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. 

Alors que nous nous déplaçons, nous allons avoir besoin de connaître la taille. Cela nous aidera à contrôler si nous sortons des limites.

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

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

Modèle actif: correspond aux critères d'une cellule donnée.

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)

Nous passons maintenant à la taxe sur le laiton. Cela réclame la cellule!

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

En utilisant le modèle actif, revendiquez cette cellule si elle n'est pas réclamée et renvoyez les coordonnées des cellules 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

Nous commençons à créer des listes de ce sac de données, créons un type pour rendre les choses plus claires.

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

Étant donné une liste de critères pour réclamer des cellules, nous allons parcourir la liste en retournant les cellules suivantes à réclamer et à rentrer dans cette liste.

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)

Pour chaque capital, créez un critère de revendication dans chaque direction, puis revendiquez récursivement ces cellules.

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

Chaque programme a besoin d'un principal.

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