26
\$\begingroup\$

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
aa...ad..
cca.ad.D.
..caeed..
.C.ce.edd
..ce.E.ee
..ce.....

A sketch highlighting the boundaries:

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:

color enhancement

\$\endgroup\$
  • 1
    \$\begingroup\$ +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? \$\endgroup\$ – Doorknob Dec 26 '13 at 1:21
  • \$\begingroup\$ @DoorknobofSnow - Oops, my mistake -- it was unintended. I'll edit to remove them. \$\endgroup\$ – r.e.s. Dec 26 '13 at 1:28
  • \$\begingroup\$ 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). \$\endgroup\$ – wchargin Dec 27 '13 at 21:30
  • \$\begingroup\$ @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. \$\endgroup\$ – r.e.s. Dec 28 '13 at 3:52
5
\$\begingroup\$

GolfScript, 138 144 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
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – r.e.s. Dec 26 '13 at 17:45
  • \$\begingroup\$ @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. \$\endgroup\$ – Howard Dec 26 '13 at 17:57
7
\$\begingroup\$

Python 3 - 424 422 417 332 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.
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – r.e.s. Dec 26 '13 at 23:15
  • \$\begingroup\$ @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). \$\endgroup\$ – Blckknght Dec 27 '13 at 0:58
  • \$\begingroup\$ 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. \$\endgroup\$ – r.e.s. Dec 27 '13 at 1:38
  • \$\begingroup\$ 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! \$\endgroup\$ – Blckknght Dec 27 '13 at 1:47
4
\$\begingroup\$

Here it is. This is my first F# program. If I missed a feature of the language, please alert me as I am still learning.

Here is my sample input

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

Here is the output

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

Here is the code. Enjoy.

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

Now we need to convert that data to a double dimension array so that we can access it through indexers.

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 us create a matrix representing the ownership of each cell

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

Let us have a utility method to see what has happened.

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

Let us create a record to represent where a particular capital letter resides.

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

Now we want to find all of the capital letters.

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)

As we move about, we need a concept of 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. 

As we move about, we are going to need to know about size. This will help us monitor whether we are moving out of bounds.

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

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

Active Pattern: matches criteria of a given cell.

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)

Now we are getting down to brass tax. This claims the cell!

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

Using the active pattern, claim this cell if unclaimed, and return the coordinates of the adjacent cells.

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

We are starting to create lists of this data bag, let us create a type to make things clearer.

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

Given a list of criterial for claiming cells, we will iterate over the list returning the next cells to claim and recurse into that list.

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)

For each capital, create a claim criteria in each direction and then recursively claim those cells.

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

Every program needs a main.

[<EntryPoint>]
let main args = 
    printIt()
    claimCellsFromCapitalsOut()
    printIt()
    0
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Well done for getting a working solution in a language you're not familiar with. However, you've missed the final step: this is code-golf, which means that the aim is to write the shortest possible program: single-character identifiers, only the whitespace which is strictly required to compile, etc. \$\endgroup\$ – Peter Taylor Jan 6 '14 at 10:42
  • 5
    \$\begingroup\$ PeterTaylor you are right. I missed that. This site needs more "Programming Puzzles" and less "Code Golf". \$\endgroup\$ – Phillip Scott Givens Jan 6 '14 at 16:14
3
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – r.e.s. Dec 27 '13 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.