# Make a Voronoi diagram (ASCII variant)

Suppose you're given some distinct uppercase letters scattered in a rectangular array of otherwise-blank cells. Each cell in the array belongs to the letter nearest to it, defined as the letter reachable in the smallest number of horizontal and/or vertical steps -- no diagonal steps. (If a cell is equidistant from two or more nearest letters, it belongs to whichever of those letters is first in alphabetical order. A cell with an uppercase letter in it belongs to that letter.) Boundary-cells are those that are horizontally or vertically adjacent to one or more cells that do not belong to the letter that they themselves belong to.

Write a procedure subprogram with the following behavior, producing a kind of Voronoi diagram ...

Input: Any ASCII string composed only of dots, uppercase letters, and newlines, such that when printed it displays a rectangular array of the kind described above, with dots acting as blanks.

Output: A printout of the input string with each blank boundary-cell replaced by the lowercase version of the letter it belongs to. (The subprogram does the printing.)

Example 1

Input:

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

Output:

...ab.B..
....ab.bb
...A.abdd
..caeed..
.C.ce.edd
..ce.E.ee
..ce.....

A sketch highlighting the boundaries:

Example 2

Input:

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

Output:

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

Color enhancement:

• +1; interesting; but I noticed that the cells in the sample input and output have one space of padding between each character. Is that a requirement? Dec 26, 2013 at 1:21
• @DoorknobofSnow - Oops, my mistake -- it was unintended. I'll edit to remove them. Dec 26, 2013 at 1:28
• So to be clear this is a Manhattan metric diagram, not Euclidean? Voronoi diagrams can be pretty cool in non-Euclidean metric spaces (see here, or fire up Blender if you have a copy; it has some interesting metrics built in). Dec 27, 2013 at 21:30
• @WChargin - Essentially, yes. Here the "distance" between two cells is just the least number of steps needed to walk from the one cell to the other, stepping only between horizontally- or vertically-adjacent cells along the way. (It's always a nonnegative integer.) This is the taxicab metric if we imagine the cells as street-intersections in a city whose streets are zero-width and whose blocks are unit squares. Dec 28, 2013 at 3:52

# Python 3 - 424422417332 295 characters:

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

There are three parts, each of which needs to be on its own line due to Python's syntax:

1. The first line sets up the variables. w is the width of a row of the board (including the newline at the end, which will be recycled as a padding column). r is a range object that indexes all the characters in s. n is a tuple of index offsets to get at the neighbors of a character (so if you wanted to allow the letters to spread out diagonally, you'd just need to add -w-1,-w+1,w-1,w+1 to the tuple). x is a short name for the str.replace method, which gets used several times in the later code (the calls will look odd though, since I use x(s,*"xy") to save characters, rather than the conventional s.replace("x", "y")). The s parameter string is modified slightly at this point as well, with its . characters and newlines being replaced by ~ characters (because they sort after all letters). A row's worth of padding ~ characters are also added to the end. t will later be used as a reference to the "old" version of s, but it needs to be initialized to something not equal to s at the start, and zero takes only one character (a more Pythonic value would be None, but that's three extra characters).
2. The second line has a loop that repeatedly updates s using a list comprehension. As the comprehension iterates over the indexes of s, ~ characters are replaced by the min of their neighbors. If a ~ character was completely surrounded by other ~s, this will do nothing. If it was next to one or more letters, it will become the smallest of them (favoring "a" over "b", etc.). The newlines that were turned to ~ characters are preserved by detecting their indexes with the modulus operator. The padding row at the end isn't updated in the list comprehension (because the range of indexes, r, was calculated before they were added to s). Instead, a fresh row of ~ characters is added after the comprehension is done. Note that s becomes a list of characters rather than a string after first pass of the loop (but because Python is flexible about types we can still index to get at the characters in the same way).
3. The last line hollows out the insides of the diagram and rebuilds the characters into a string to be printed. First, any letter that is surrounded only by other copies of itself (or ~ characters from the padding) gets replaced by .. Next, the characters are all concatenated together into a single string. Finally, the padding ~ characters are converted back to newlines and the string is printed.
• Probably the r=range ought to be inside the function body to be considered part of a callable procedure, but you can save characters by writing r=range;s=[l.replace. You can also squeeze out more characters by writing if"~"==s[y][x]else and if"~"==s[y][x]else, for a total of 422. (Btw, this ran for me with Python 2.7) Dec 26, 2013 at 23:15
• @r.e.s.: Thanks for those suggestions. I've put r=range at the end of the function's first line (where I set up other variables), and shaved off a couple of spaces I'd missed before. I'm not sure if I got both of the ones you were referring to, as you seem to have mentioned the same thing twice. And, in Python 2.7 it can be a further two characters shorter, since you don't need the parentheses after print (usually that only saves 1 character, but print"\n".join(...) works). Dec 27, 2013 at 0:58
• Oops, I mis-pasted that second one. It was supposed to be s[y][x]for (removing a space), but you seem to have found it anyway. Dec 27, 2013 at 1:38
• Yep, that's the other one I got. I just decided to try a bigger change and went to a 1d rather than 2d list, which turned out to save a bunch of characters! Dec 27, 2013 at 1:47

### GolfScript, 138144 137 characters

:^n%,,{{^n/1$=2$>1<.'.'={;{@~@+@@+\{^3\$?^<n/),\,@-abs@@-abs+99*+}++^'.
'-$1<{32+}%}++[0..1.0..(.0]2/%..&,(\0='.'if}{@@;;}if}+^n?,%puts}/ Input is given to the subprogram as a single string on the stack. Unfortunately I had to use a puts because of the requirement that the routine has to print the result. Explanation of the code The outer block essentially loops over all position (x,y) according to the size of the input rectangles. Within the loop the coordinates x and y are left on the stack each time. After each line is complete the result is printed to 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 The code executed within the loop first takes the corresponding character of the input. ^n/ # split input into lines 1= # select the corresponding row 2>1< # select the corresponding col Then basically we check, if we have a ., i.e. if we (possibly) have to replace the character. .'.'={ # 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 Again, the inner code starts with a loop, now over all coordinates (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] The recent inner code snippet simply returns the (lower case) letter of the nearest point, given the two coordinates. { # 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

So from the five nearest letters for the coordinates (x,y) (x,y+1) (x+1,y) (x,y-1) (x-1,y) take the first, if not all are equal, otherwise take a ..

.                   # copy five letter string
.&,(                # are there distinct letters?
\0=                 # first letter (i.e. nearest for coordinate x,y)
'.'                 # or dot
if                  # if command
• Your code did ok with Example 1, so I was surprised when it did some cells incorrectly in Example 2: In each of the first three lines, it puts ".ui" where "ui." should be, and in the fourth line, it puts "zs" where "s." should be, and puts "ui" where "i." should be, etc. etc. Dec 26, 2013 at 17:45
• @r.e.s Missed the "equidistant - first in alphabetical order" part. Unfortunately, the sort operation isn't stable. Added a few chars to fix that one. Dec 26, 2013 at 17:57

## Python, 229 226 chars

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

Does a flood fill to compute the result. The trailing for/zip combo generates an array x for each cell containing the value in that cell and its four neighbors. Then we use Blckknght's trick and min a bunch of possibilities for each cell. Those are the original cell value, any neighbors if the cell has not been visited yet, or a . if it has been visited and all neighbors are . or equal to the cell itself.

• Since the subprogram is supposed to do the printing, you can just change return s to print s. Also, can't y!=b be changed to y>b? That would make 226 characters, I think. Dec 27, 2013 at 14:47