4
\$\begingroup\$

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:

Input

Input

Output

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>

\$\endgroup\$
3
\$\begingroup\$

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

However, you could also add a function to transpose the grid, so columns become rows. I.e. instead of having each of your functions switch between vertical/horizontal all the time, simply transpose the input and output instead.

\$\endgroup\$

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.