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')
radiusSelector = document.getElementById('radius')
function calculate() {
calculateButton.disabled = true
widthSelector.disabled = true
heightSelector.disabled = true
radiusSelector.disabled = true
itemCount.value = 'Calculating...'
setTimeout(delayedCalculate, 100)
}
function delayedCalculate() {
gridWidth = widthSelector.value
gridHeight = heightSelector.value
radius = radiusSelector.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
radiusSelector.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
newGridState = gridWithItemAdded(gridState, x, y)
m = minFromHere(newGridState)
if (m < min) {
min = m
}
}
}
}
if (noCells) return 0
return min + 1
}
function gridWithItemAdded(gridState, x, y) {
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'>