# Worst Case Manhattan Exclusion

Imagine a W by H grid of squares that wraps toroidally. Items are placed onto the grid as follows.

The first item can be placed on any square, but subsequent items must not be within a Manhattan distance R of any previous item (also known as a Von Neumann neighbourhood of range R). Carefully choosing the positions allows fitting a large number of items onto the grid before there are no more valid positions. However, instead consider the opposite aim: What is the lowest number of items that can be placed and leave no further valid positions?

Here is a radius 5 exclusion zone:

Here is another radius 5 exclusion zone, this time near the edges so the wrapping behaviour is apparent:

### Input

Three integers:

• W: width of grid (positive integer)
• H: height of grid (positive integer)
• R: radius of exclusion zone (non-negative integer)

### Output

An integer N, which is the smallest number of items that can be placed preventing any further valid placements.

### Details

• A radius of zero gives an exclusion zone of 1 square (the one the item was placed on).
• A radius of N excludes the zone that can be reached in N orthogonal steps (remember the edges wrap toroidally).

Your code must work for the trivial case of R = 0, but does not need to work for W = 0 or H = 0.

Your code must also deal with the case where R > W or R > H.

# Time limit and test cases

Your code must be able to deal with all of the test cases, and each test case must complete within 5 minutes. This should be easy (the example JavaScript solution takes a few seconds for each test case). The time limit is mainly to exclude the extreme brute force approach. The example approach is still fairly brute force.

If your code completes within 5 minutes on one machine but not on another that will be close enough.

Test cases in the form inputs: output as W H R : N

5 4 4 : 1
5 4 3 : 2
5 4 2 : 2
5 4 1 : 5

7 5 5 : 1
7 5 4 : 2
7 5 3 : 2
7 5 2 : 4

8 8 8 : 1
8 8 7 : 2
8 8 6 : 2
8 8 5 : 2
8 8 4 : 2
8 8 3 : 4

7  6  4 : 2
7  6  2 : 4
11  7  4 : 3
11  9  4 : 4
13 13  6 : 3
11 11  5 : 3
15 14  7 : 2
16 16  8 : 2


# Snippet to help visualise and play around with ideas

canvas = document.getElementById('gridCanvas');ctx = canvas.getContext('2d');widthSelector = document.getElementById('width');heightSelector = document.getElementById('height');radiusSelector = document.getElementById('radius');itemCount = document.getElementById('itemCount');canvasMaxWidth = canvas.width;canvasMaxHeight = canvas.height;gridlineColour = '#888';emptyColour = '#ddd';itemColour = '#420';hoverCellColour = '#840';exclusionColour = '#d22';validColour = '#8f7';invalidColour = '#fbb';overlapColour = '#600';resetGrid();x = -1;y = -1;function resetGrid() {gridWidth = widthSelector.value;gridHeight = heightSelector.value;radius = radiusSelector.value;numberOfItems = 0;itemCount.value = numberOfItems + ' items placed.';cells = [gridWidth * gridHeight];for (i=0; i<gridWidth*gridHeight; i++) {cells[i] = '#ddd';}cellSize = Math.min(Math.floor(canvasMaxWidth/gridWidth), Math.floor(canvasMaxHeight/gridHeight));pixelWidth = gridWidth * cellSize + 1;canvas.width = pixelWidth;pixelHeight = gridHeight * cellSize + 1;canvas.height = pixelHeight;leaveCanvas();}function checkPosition(event) {bound = canvas.getBoundingClientRect();canvasX = event.clientX - bound.left;canvasY = event.clientY - bound.top;newX = Math.min(Math.floor(canvasX / cellSize), gridWidth-1);newY = Math.min(Math.floor(canvasY / cellSize), gridHeight-1);if (newX != x || newY != y) {x = newX;y = newY;drawGrid();}}function leaveCanvas() {x = -1;y = -1;drawGrid();}function drawGrid() {ctx.fillStyle = gridlineColour;ctx.fillRect(0, 0, pixelWidth, pixelHeight);cellColour = cells[x + gridWidth * y];if (cellColour == itemColour || cellColour == exclusionColour) {zoneColour = invalidColour;} else {zoneColour = validColour;}for (gridX=0; gridX<gridWidth; gridX++) {for (gridY=0; gridY<gridHeight; gridY++) {colour = (cells[gridX + gridWidth * gridY]);if (x >= 0 && y >= 0) {if (x == gridX && y == gridY) {colour = hoverCellColour;} else if (manhattanDistance(x, y, gridX, gridY) <= radius) {if (colour == exclusionColour) {colour = overlapColour;} else if (colour != itemColour) {colour = zoneColour;}}}ctx.fillStyle = colour;ctx.fillRect(gridX * cellSize + 1, gridY * cellSize + 1, cellSize - 1, cellSize - 1);}}}function manhattanDistance(a, b, c, d) {horizontal = Math.min(Math.abs((gridWidth + c - a) % gridWidth), Math.abs((gridWidth + a - c) % gridWidth));vertical = Math.min(Math.abs((gridHeight + d - b) % gridHeight), Math.abs((gridHeight + b - d) % gridHeight));return vertical + horizontal;}function placeItem(event) {bound = canvas.getBoundingClientRect();canvasX = event.clientX - bound.left;canvasY = event.clientY - bound.top;attemptX = Math.min(Math.floor(canvasX / cellSize), gridWidth-1);attemptY = Math.min(Math.floor(canvasY / cellSize), gridHeight-1);colour = cells[attemptX + gridWidth * attemptY];if (colour != itemColour && colour != exclusionColour) {for (a=0; a<gridWidth; a++) {for (b=0; b<gridHeight; b++) {if (manhattanDistance(a, b, attemptX, attemptY) <= radius) {cells[a + gridWidth * b] = exclusionColour;}}}cells[attemptX + gridWidth * attemptY] = itemColour;drawGrid();numberOfItems++;itemCount.value = numberOfItems + ' items placed.';}}
<canvas id='gridCanvas' width='500' height='300' style='border:none' onmousemove='checkPosition(event)' onmouseleave='leaveCanvas()' onclick='placeItem(event)'></canvas><br><textarea id='itemCount' readonly></textarea><br><button id='reset' onclick='resetGrid()'>Reset</button> with the following values:<br>Width:<input id='width' type='number' value='20' min='1' max='50' maxlength='2' step='1'><br>Height:<input id='height' type='number' value='13' min='1' max='30' maxlength='2' step='1'><br>Radius:<input id='radius' type='number' value='5' min='0' max='60' maxlength='2' step='1'>

# Example (ungolfed) solution

Just an example for small outputs (resulting from radius not much smaller than the width and height). Can handle any of the test cases but will time out and give up for most larger cases.

itemCount = document.getElementById('itemCount')
calculateButton = document.getElementById('calculate')
widthSelector = document.getElementById('width')
heightSelector = document.getElementById('height')

function calculate() {
calculateButton.disabled = true
widthSelector.disabled = true
heightSelector.disabled = true
itemCount.value = 'Calculating...'
setTimeout(delayedCalculate, 100)
}

function delayedCalculate() {
gridWidth = widthSelector.value
gridHeight = heightSelector.value
startingMin = gridWidth*gridHeight + 1
var cells = [gridWidth * gridHeight]
for (i=0; i<gridWidth*gridHeight; i++) {
cells[i] = 0
}
var gridState = gridWithItemAdded(cells, 0, 0)
var minimum = minFromHere(gridState) + 1
itemCount.value = 'Minimum ' + minimum + ' items required.'
calculateButton.disabled = false
widthSelector.disabled = false
heightSelector.disabled = false
}

function minFromHere(gridState) {
var x
var y
var newGridState
var noCells = true
var min = startingMin
for (x=0; x<gridWidth; x++) {
for (y=0; y<gridHeight; y++) {
if (gridState[x + gridWidth * y] == 0) {
noCells = false
m = minFromHere(newGridState)
if (m < min) {
min = m
}
}
}
}
if (noCells) return 0
return min + 1
}

var a
var b
var grid = gridState.slice()
for (a=0; a<gridWidth; a++) {
for (b=0; b<gridHeight; b++) {
if (manhattanDistance(a, b, x, y) <= radius) {
grid[a + gridWidth * b] = 1
}
}
}
return grid
}

function manhattanDistance(a, b, c, d) {
horizontal = Math.min(Math.abs((gridWidth + c - a) % gridWidth), Math.abs((gridWidth + a - c) % gridWidth))
vertical = Math.min(Math.abs((gridHeight + d - b) % gridHeight), Math.abs((gridHeight + b - d) % gridHeight))
return vertical + horizontal
}
<textarea id='itemCount' readonly></textarea>
<br>
<button id='calculate' onclick='calculate()'>Calculate</button> with the following values:
<br>
Width:<input id='width' type='number' value='5' min='1' max='50' maxlength='2' step='1'>
<br>
Height:<input id='height' type='number' value='4' min='1' max='30' maxlength='2' step='1'>
<br>
Radius:<input id='radius' type='number' value='1' min='0' max='60' maxlength='2' step='1'>

• Awesome code snippet! – Stretch Maniac Jun 9 '15 at 23:24
• @StretchManiac thanks :) I'm trying to learn JavaScript so any feedback is welcome – trichoplax Jun 10 '15 at 0:12
• That is a pretty nice snippet. I like that color scheme too. Is it from a palette? – miles Jun 11 '15 at 22:56
• @miles thank you - the colours are just guessed and then fine tuned a bit (but not much - they are still all 3 character colour codes rather than 6). You can see the colours used in the third block of lines in the snippet code. – trichoplax Jun 11 '15 at 23:04

# Python 2, 216 182 bytes

def f(W,H,R):L={(i%W,i/W)for i in range(W*H)};M={(x,y)for x,y in L if min(x,W-x)+min(y,H-y)>R};g=lambda s:min([1+g(s-{((a+x)%W,(b+y)%H)for x,y in L-M})for a,b in s]or[1]);return g(M)


Input like f(16,16,8). Uses pretty much the same algorithm as @trichoplax's sample, but with sets. Initially I didn't place the first item at (0, 0), but this made it choke on the last few cases.

All cases above complete within 10 seconds, well under the limit. In fact, the cases are small enough that I had a little room to be less efficient, allowing me to remove a check which checked for duplicate states.

(Thanks to @trichoplax for golfing help)

Expanded:

def f(W,H,R):
# All cells
L={(i%W,i/W)for i in range(W*H)}

# Mask: Complement of exclusion zone around (0, 0)
M={(x,y)for x,y in L if min(x,W-x)+min(y,H-y)>R}

# Place recursively
g=lambda s:min([1+g(s-{((a+x)%W,(b+y)%H)for x,y in L-M})for a,b in s]or[1])
return g(M)


# Python 3, 270262260251246 226

(Thanks to Sp3000 for:

• -~ instead of +1, which lets me lose a space after return on the last line.
• losing superfluous parentheses around W*H.
• lambdas...
• putting everything on one line.
• python modulo % gives positive result for negative numbers, to save another 20 bytes)

This is the JavaScript example answer from the question ported into Python 3.

To avoid having to pass so many function arguments around, I've moved the two supporting functions inside the calculate function so that they share its scope. I've also condensed each of these functions into a single line to avoid the cost of indentation.

### Explanation

This fairly brute force approach places the first item at (0, 0), and then marks all the excluded squares. It then recursively places an item at all remaining valid squares until all squares are excluded, and returns the minimum number of items required.

### Golfed code:

def C(W,H,R):r=range;M=lambda g:min([M(G(g,x,y))for x in r(W)for y in r(H)if g[x+W*y]]or[-1])+1;G=lambda g,x,y:[g[a+W*b]if min((x-a)%W,(a-x)%W)+min((y-b)%H,(b-y)%H)>R else 0for b in r(H)for a in r(W)];return-~M(G([1]*W*H,0,0))


### Ungolfed code:

def calculate(W, H, R):
starting_min = W * H + 1
cells = [0] * (W * H)
grid_state = grid_with_item_added(cells, 0, 0, W, H, R)
return min_from_here(grid_state, starting_min, W, H, R) + 1

def min_from_here(grid_state, starting_min, W, H, R):
no_cells = True
min = starting_min
for x in range(W):
for y in range(H):
if grid_state[x + W * y] == 0:
no_cells = False
new_grid_state = grid_with_item_added(grid_state, x, y, W, H, R)
m = min_from_here(new_grid_state, starting_min, W, H, R)
if m < min:
min = m

if no_cells:
return 0
else:
return min + 1

def grid_with_item_added(grid_state, x, y, W, H, R):
grid = grid_state[:]
for a in range(W):
for b in range(H):
if manhattan_distance(a, b, x, y, W, H) <= R:
grid[a + W * b] = 1

return grid

def manhattan_distance(a, b, c, d, W, H):
horizontal = min(abs(W + c - a) % W, abs(W + a - c) % W)
vertical = min(abs(H + d - b) % H, abs(H + b - d) % H)
return horizontal + vertical

if __name__ == '__main__':
import sys
arguments = sys.argv[1:]
if len(arguments) < 3:
print('3 arguments required: width, height and radius')
else:
print(calculate(int(arguments[0]), int(arguments[1]), int(arguments[2])))


The ungolfed code defines a function and also includes code to allow it to be called from the command line. The golfed code just defines the function, which is sufficient for standard code golf questions.

If you would like to test the golfed code from the command line, here it is with the command line handling included (but not golfed):

### Command line testable golfed code

def C(W,H,R):r=range;M=lambda g:min([M(G(g,x,y))for x in r(W)for y in r(H)if g[x+W*y]]or[-1])+1;G=lambda g,x,y:[g[a+W*b]if min((x-a)%W,(a-x)%W)+min((y-b)%H,(b-y)%H)>R else 0for b in r(H)for a in r(W)];return-~M(G([1]*W*H,0,0))

if __name__ == '__main__':
import sys
arguments = sys.argv[1:]
if len(arguments) < 3:
print('3 arguments required: width, height and radius')
else:
print(C(int(arguments[0]), int(arguments[1]), int(arguments[2])))