# Code for finding the “longest” empty space in a grid

I have written some code to find the longest line of empty space in a grid and I'd like to know if it can be simplified or shortened at all.

Here is an example of the input and output of the program:

### Output

As you can see, the program found the longest line to be near the top in the middle. The program is only looking for a 1 block wide line, which is by design. It also supports looking for the longest horizontal line too, which is not shown above.

### Code

function findLongestLineInRow(grid, position, direction) {
let current = 0,
start = 0,
maximum = 0,
offset = 0;

const length = direction === 'vertical' ? grid.length : grid[0].length;

for (let i = 0; i < length; i++) {
const x = direction === 'vertical' ? position : i,
y = direction === 'vertical' ? i : position;

if (grid[y][x]) {
if (current > maximum) {
maximum = current;
offset = start;
}

current = 0;
start = i + 1;
} else {
current++;
}
}

return {
x: direction === 'vertical' ? position : offset,
y: direction === 'vertical' ? offset : position,
length: maximum,
direction
};
}

function findLongestLineInRowRange(start, end, direction) {
let longest = { x: 0, y: 0, length: 0 };

for (let i = start; i < end; i++) {
const line = findLongestLineInRow(grid, i, direction);

if (line.length > longest.length) {
longest = line;
}
}

return longest;
}

function findLongestLineInGrid(grid) {
const horizontal = findLongestLineInRange(0, grid.length, 'horizontal'),
vertical = findLongestLineInRange(0, grid[0].length, 'vertical');

const { x, y, length, direction } = horizontal.length >= vertical.length ? horizontal : vertical;

return {
x, y,
width: direction === 'vertical' ? 1 : length,
height: direction ===  'vertical' ? length : 1,
};
}


And here's an example of it running in the browser:

function findLongestLineInRow(grid, position, direction) {
let current = 0,
start = 0,
maximum = 0,
offset = 0;

const length = direction === 'vertical' ? grid.length : grid[0].length;

for (let i = 0; i < length; i++) {
const x = direction === 'vertical' ? position : i,
y = direction === 'vertical' ? i : position;

if (grid[y][x]) {
if (current > maximum) {
maximum = current;
offset = start;
}

current = 0;
start = i + 1;
} else {
current++;
}
}

return {
x: direction === 'vertical' ? position : offset,
y: direction === 'vertical' ? offset : position,
length: maximum,
direction
};
}

function findLongestLineInRowRange(start, end, direction) {
let longest = { x: 0, y: 0, length: 0 };

for (let i = start; i < end; i++) {
const line = findLongestLineInRow(grid, i, direction);

if (line.length > longest.length) {
longest = line;
}
}

return longest;
}

function findLongestSpace(grid) {
const horizontal = findLongestLineInRowRange(0, grid.length, 'horizontal'),
vertical = findLongestLineInRowRange(0, grid[0].length, 'vertical');

const { x, y, length, direction } = horizontal.length >= vertical.length ? horizontal : vertical;

return {
x, y,
width: direction === 'vertical' ? 1 : length,
height: direction ===  'vertical' ? length : 1,
};
}

const generateRandomGrid = (width, height) =>
Array(height).fill().map(() =>
Array(width).fill().map(() => Math.random() < 0.5));

const drawGrid = (context, grid, cellSize) =>
grid.forEach((column, y) =>
column.forEach((cell, x) =>
cell ? context.fillRect(x * cellSize, y * cellSize, cellSize, cellSize) : void 0));

const drawLongestSpace = (context, space, cellSize) => {
context.fillStyle = 'rgba(255, 0, 0, 0.75)';
context.fillRect(space.x * cellSize, space.y * cellSize,
space.width * cellSize, space.height * cellSize);
};

const context = document.getElementById('canvas').getContext('2d'),
grid = generateRandomGrid(50, 50),
longestSpace = findLongestSpace(grid);

drawGrid(context, grid, 10);
drawLongestSpace(context, longestSpace, 10);
body {
margin: 10px;
text-align: center;
}

#canvas {
border: 1px solid #DDD;
background-color: #FFF;
}
<canvas id="canvas" width="500" height="500"></canvas>

Looks pretty good. I'd probably prefer a const VERTICAL = 'vertical' to the repeated 'vertical' string.