Kata

Task

Create a (fast) function that takes a shape (set of unit squares) and returns the borders of the shape as a multiline string, using box-drawing characters.

Input

• shape [set of tuples (int, int)]

The shape is a plane geometric figure formed by one or more pieces, each piece is formed by joining one or more unit squares edge to edge. The shape parameter contains the (x,y) coordinates of the unit squares that form the shape.

x axis is horizontal and oriented to the right, y axis is vertical and oriented upwards.

Examples

A set with one element (e.g. {(1,1)}, {(7,11)}, {(50,35)}, ...) represents a square whose sides have length 1.
A set with two elements with the same y coord and consecutive x coord (e.g. {(1,1),(2,1)} or {(7,5),(8,5)}) is a rectangle, width: 2, height: 1. A set with two elements with the same x coord and consecutive y coord (e.g. {(1,1),(1,2)} or {(7,5),(7,6)}) is a rectangle, width: 1, height: 2.

Ranges

• Size of shape (len(shape), number of unit squares): 1–5000
• Width/height of shape (max(coord)-min(coord)+1): 1–120
• x, y coordinates: -500–500

Output [string]

Multiline string representing the border of the input shape, using box-drawing characters.

• No trailing spaces
• No trailing newline
• Minimum leading spaces (at least one line starts with a non-space char)

Allowed chars:

CHAR  CODE   NAME

      000a   newline
      0020   space
  ─   2500   box drawings light horizontal
  │   2502   box drawings light vertical
  ┌   250c   box drawings light down and right
  ┐   2510   box drawings light down and left
  └   2514   box drawings light up and right
  ┘   2518   box drawings light up and left
  ┼   253c   box drawings light vertical and horizontal

Border drawing

Borders are drawn between unit squares, not inside squares. There isn't a 1:1 relationship between chars in output string and (x,y) coordinates in input shape.

If two borders separated by n unit squares (e.g. opposite sides of a nxn square), the distance of corresponding chars in output string is n, i.e. there are n-1 chars between them (see examples below).

Examples

• 1x1 square => four corner chars in two rows, without other intermediate chars:

  {(1,1)}  =>  '┌┐\n└┘'
  ┌┐
  └┘
  

• 2x1 rectangle => four corners, with horizontal lines (─) between left and right corners:

  {(1,1),(2,1)}  =>  '┌─┐\n└─┘'
  ┌─┐
  └─┘
  

• 1x2 rectangle => three rows, with vertical lines (│) between top and bottom corners:

  {(1,1),(1,2)}  =>  '┌┐\n││\n└┘'
  ┌┐
  ││
  └┘
  

• 2x2 square => three rows, horizontal/vertical lines between corners and a space (' ') in the center:

  {(1,1),(2,1),(1,2),(2,2)}  =>  '┌─┐\n│ │\n└─┘'
  ┌─┐
  │ │
  └─┘
  

• shapes may have holes, inner borders must be drawn; 4x4 square with a 2x2 hole:

  {(0,0),(0,1),(0,2),(0,3),(1,0),(1,3),(2,0),(2,3),(3,0),(3,1),(3,2),(3,3)}  =>  '┌───┐\n│┌─┐│\n││ ││\n│└─┘│\n└───┘'
  ┌───┐
  │┌─┐│
  ││ ││
  │└─┘│
  └───┘
  

• shapes may have multiple separate pieces, all pieces must be drawn; two squares with 1-unit gap:

  {(x,y) for x in range(3) for y in range(3)} | {(x,y) for x in range(4,7) for y in range(3)}  =>  '┌──┐┌──┐\n│  ││  │\n│  ││  │\n└──┘└──┘'
  ┌──┐┌──┐
  │  ││  │
  │  ││  │
  └──┘└──┘
  

• pieces may touch each other at corners, common corners are drawn with ┼:

  {(x,y) for x in range(4) for y in range(3)} | {(x,y) for x in range(4,8) for y in range(3,6)}  => '    ┌───┐\n    │   │\n    │   │\n┌───┼───┘\n│   │\n│   │\n└───┘'
  ....┌───┐
  ....│   │
  ....│   │        .... = leading spaces
  ┌───┼───┘
  │   │
  │   │
  └───┘
  

Performances and tests

The algorithm must be efficient, even with complex shapes, convoluted borders, multiple holes, ...

There are 299 tests:

• 25 fixed tests, with small shapes;
• 54 normal random tests, with small shapes;
• 220 performance tests, with medium/large shapes and timeout.

Performance tests

Typical range (10th–90th percentile) and average values of shapes used in timed tests:

180 tests with medium shapes

• size (unit squares): 800–1600, avg: 1170
• width: 53–70, avg: 61
• height: 45–62, avg: 53
• number of pieces: 18–43, avg: 29
• number of holes: 13–30, avg: 21
• area coverage (squares/(width*height)): 30%–42%, avg: 36%

40 tests with large shapes

• size (unit squares): 1800–3300, avg: 2500
• width: 69–89, avg: 79
• height: 77–99, avg: 88
• number of pieces: 37–77, avg: 56
• number of holes: 28–56, avg: 41
• area coverage: 30%–42%, avg: 36%

Maximum time: 3.0 seconds
(reference solution: 2.28 ± 0.08 s)

"Draw the borders" series

Draw the borders I - Simple ascii border (5 kyu)

border drawing: outer squares, +-|
shapes: simple, one piece
other requirements: ignore holes
performances: not important

Draw the borders II - Fast and furious (this kata)

border drawing: between squares, ─│┌┐└┘┼
shapes: complex, many pieces and holes
performances: very important

Draw the Borders III - Fancy borders (2 kyu ?, beta)

border drawing: between squares, ━┃┏┓┗┛╋─│┌┐└┘┼╃╄╅╆
shapes: complex, many pieces and holes
other requirements: different pieces/holes borders
performances: probably important