#3 – 100 Days of Coding Problems

Day 3

The Problem

A wall consists of several rows of bricks of various integer lengths and uniform height. Your goal is to find a vertical line going from the top to the bottom of the wall that cuts through the fewest number of bricks. If the line goes through the edge between two bricks, this does not count as a cut.

For example, suppose the input is as follows, where values in each row represent the lengths of bricks in that row

[[3, 5, 1, 1],
 [2, 3, 3, 2],
 [5, 5],
 [4, 4, 2],
 [1, 3, 3, 3],
 [1, 1, 6, 1, 1]]

The best we can we do here is to draw a line after the eighth brick, which will only require cutting through the bricks in the third and fifth row.

Given an input consisting of brick lengths for each row such as the one above, return the fewest number of bricks that must be cut to create a vertical line.
https://dailycodingproblem.com

My Solution

const wall = [
	[3, 5, 1, 1],
	[2, 3, 3, 2],
	[5, 5],
	[4, 4, 2],
	[1, 3, 3, 3],
	[1, 1, 6, 1, 1]
]

const leastCuts = (wall) => {
	let rowSum = 0
	const data = {}
	
	for (let row of wall) {
		rowSum = 0

		for (let col of row.slice(0, row.length - 1)) {
			rowSum += col
			
			if (data[rowSum] === undefined) data[rowSum] = 0
			data[rowSum] += 1
		}
	}
	
	const mostCommonCut = Object.keys(data)
	  .map(str => +str)
	  .sort((a, b) => data[b] - data[a])[0]
	
	return wall.length - +data[mostCommonCut]
}

View Code

In solving this problem, I quickly realized that it was not as complex as it seemed. The question was really asking, find the most common slit out of all the rows. For example, when taking the first row of the wall:

[3, 5, 1, 1]

There is a slit at 3, 8, 9, and, of course, 10.

The code that I wrote simply computed and stored the number of slit totals throughout the entire wall, sorted those by largest to smallest in number, and then subtracted the number (4 in the case of the sample wall given) from the height of the wall—6 rows.

Optimizations

1. Fewer repetitions

Even though this was one of the more easy problems, there are many optimizations that can make it much faster. For example, the for loop can be broken out of much sooner if it can be determined that in the remaining rows, none of the slits in second place are able to catch up.

In order to achieve that level of optimization however, it is most likely that a more complex data structure be used than just an object for keeping data on the most common cuts through the wall. Not only would each item need to keep its wall position and count, but it would also need to keep its relation to other items’ count.

2. Faster sorting

In my solution, the browser’s sorting algorithm was used, but the browser’s sorting algorithm assumes nothing about the data, whereas in this problem it is most likely the case that most of the data is similar in length, so a different sorting algorithm than the browser’s default might make finding the most common slit position much faster.

3. Path optimizations

One last thing that could be optimized is the algorithm itself. For example, if paired with the few repetitions optimization, it would be much faster to start with the rows that have fewer elements. See the following order of visiting the rows:

[[3, 5, 1, 1],
 [2, 3, 3, 2],
 [5, 5],
 [4, 4, 2],
 [1, 3, 3, 3],
 [1, 1, 6, 1, 1]]

Row 3
Row 4
Row 1, 2, 5

In this particular map, going in that order does not help improve algorithm speed, but it would most likely increase algorithm speed on much bigger maps where slit overlap is less common and there is a cut that is more common than all other cuts.

#3