Предположим, вам даны несколько разных заглавных букв, разбросанных по прямоугольному массиву пустых ячеек. Каждая ячейка в массиве принадлежит ближайшей к ней букве , определяемой как буква, достижимая за наименьшее количество горизонтальных и / или вертикальных шагов - без диагональных шагов. (Если ячейка находится на одинаковом расстоянии от двух или более ближайших букв, она принадлежит любой из этих букв в алфавитном порядке. Ячейка с заглавной буквой в ней относится к этой букве.) Граничные ячейки - это те, которые расположены горизонтально или вертикально рядом с одной или несколькими ячейками, которые не принадлежат букве, к которой они принадлежат.

Напишите подпрограмму процедуры со следующим поведением, создавая вид диаграммы Вороного ...

Ввод : Любая строка ASCII, состоящая только из точек, заглавных букв и новых строк, так что при печати она отображает прямоугольный массив описанного выше типа с точками, действующими как пробелы.

Вывод : распечатка входной строки с заменой каждой пустой граничной ячейки на строчную версию буквы, которой она принадлежит. (Подпрограмма выполняет печать.)

Пример 1

Входные данные:

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

Выход:

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

Эскиз с выделением границ:

Пример 2

Входные данные:

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

Выход:

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

Улучшение цвета:

GolfScript, 138 144 137 символов

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

Входные данные передаются подпрограмме в виде одной строки в стеке. К сожалению, мне пришлось использовать putsиз-за требования, что процедура должна печатать результат.

Пояснение к коду

Внешний блок по существу проходит по всей позиции (x, y) в соответствии с размером входных прямоугольников. Внутри цикла координаты x и y остаются в стеке каждый раз. После завершения каждой строки результат выводится на консоль.

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

Код, выполняемый в цикле, сначала принимает соответствующий символ ввода.

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

Затем в основном мы проверяем, есть ли у нас ., т.е. должны ли мы (возможно) заменить символ.

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

Опять же, внутренний код начинается с цикла, теперь по всем координатам (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]

Недавний фрагмент внутреннего кода просто возвращает букву (в нижнем регистре) ближайшей точки, учитывая две координаты.

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

Поэтому из пяти ближайших букв для координат (x, y) (x, y + 1) (x + 1, y) (x, y-1) (x-1, y) берут первую, если не все равно, иначе возьмите ..

.                   # 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 символов:

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

Есть три части, каждая из которых должна быть в отдельной строке из-за синтаксиса Python:

1. Первая строка устанавливает переменные. wявляется шириной ряда доски (включая символ новой строки в конце, который будет переработан как столбец заполнения). rэто rangeобъект, который индексирует все символы в s. nявляется кортежем смещения индекса для соседей символа (поэтому, если вы хотите, чтобы буквы расширялись по диагонали, вам просто нужно добавить -w-1,-w+1,w-1,w+1к кортежу). xэто краткое имя str.replaceметода, которое несколько раз используется в более позднем коде (хотя вызовы будут выглядеть странно, поскольку я использую x(s,*"xy")для сохранения символы, а не обычные s.replace("x", "y")). sСтрока параметра немного изменен на данный момент , а также, с ее .символов и новой строки заменяются~символы (потому что они сортируют после всех букв). В ~конце также добавляется количество отступов строки . tпозже будет использоваться как ссылка на «старую» версию s, но его нужно инициализировать чем-то, что не равно sв начале, и ноль занимает только один символ (более Pythonic значение будет None, но это три дополнительных символа) ,
2. Во второй строке есть цикл, который многократно обновляется sс использованием понимания списка. По мере того, как понимание перебирает индексы s, ~символы заменяются minсоседями. Если ~персонаж был полностью окружен другими персонажами ~, это ничего не изменит. Если оно было рядом с одной или несколькими буквами, оно станет самым маленьким из них (предпочтение "a"над "b"и т. Д.). Новые строки, которые были превращены в ~символы, сохраняются путем определения их индексов с помощью оператора модуля. Строка отступа в конце не обновляется в понимании списка (так как диапазон индексов rбыл вычислен до того, как они были добавлены s). Вместо этого свежий ряд~символы добавляются после того, как понимание сделано. Обратите внимание, что sсписок становится символом, а не строкой после первого прохода цикла (но поскольку Python обладает гибкостью в отношении типов, мы все равно можем индексировать, чтобы получить символы таким же образом).
3. Последняя строка раскрывает внутреннюю часть диаграммы и перестраивает символы в строку для печати. Во-первых, любая буква, которая окружена только другими ее копиями (или ~символами из отступа), заменяется на .. Затем все символы объединяются в одну строку. Наконец, ~символы заполнения преобразуются обратно в новые строки, и строка печатается.

Питон, 229 226 символов

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

Заполняет ли поток, чтобы вычислить результат. Конечный for/ zipкомбинированный генерирует массив xдля каждой ячейки, содержащий значение в этой ячейке и ее четырех соседях. Затем мы используем трюк Blckknght и minкучу возможностей для каждой ячейки. Это исходное значение ячейки, любые соседи, если ячейка еще не посещена, или a, .если она была посещена и все соседи равны .или равны самой ячейке.

Вот. Это моя первая программа на F #. Если я пропустил функцию языка, пожалуйста, предупредите меня, поскольку я все еще учусь.

Вот мой пример ввода

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

Вот вывод

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

Вот код Наслаждаться.

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

Теперь нам нужно преобразовать эти данные в массив двойного измерения, чтобы мы могли получить к нему доступ через индексаторы.

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

Давайте создадим матрицу, представляющую право собственности на каждую ячейку

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

Давайте посмотрим на то, что произошло.

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

Давайте создадим запись, чтобы представить, где находится конкретная заглавная буква.

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

Теперь мы хотим найти все заглавные буквы.

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)

По мере нашего продвижения нам нужна концепция направления.

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. 

Когда мы будем двигаться, нам нужно будет знать размер. Это поможет нам отслеживать, выходим ли мы за пределы.

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

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

Активный шаблон: соответствует критериям данной ячейки.

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)

Теперь мы переходим к латунному налогу. Это утверждает, что клетка!

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

Используя активный шаблон, закажите эту ячейку, если она не востребована, и верните координаты соседних ячеек.

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

Мы начинаем создавать списки этого пакета данных, давайте создадим тип, чтобы прояснить ситуацию.

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

Учитывая список критериев для ячеек заявки, мы перебираем список, возвращая следующие ячейки для заявки и возвращаясь в этот список.

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)

Для каждой столицы создайте критерии заявки в каждом направлении, а затем рекурсивно заявите эти ячейки.

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

Каждая программа нуждается в главной.

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