#5

Photo by Jeremy Thomas on Unsplash

The Problem

You have N stones in a row, and would like to create from them a pyramid. This pyramid should be constructed such that the height of each stone increases by one until reaching the tallest stone, after which the heights decrease by one. In addition, the start and end stones of the pyramid should each be one stone high.

You can change the height of any stone by paying a cost of 1 unit to lower its height by 1, as many times as necessary. Given this information, determine the lowest cost method to produce this pyramid.

For example, given the stones [1, 1, 3, 3, 2, 1], the optimal solution is to pay 2 to create [0, 1, 2, 3, 2, 1].

https://dailycodingproblem.com

My Solution

const stones = [1, 1, 3, 3, 2, 1]
const otherStones = [3, 3, 3, 3, 3]

const removeAtIndex = (arr, index) => arr.slice(0, index).concat(arr.slice(index + 1))

const optimalCost = (stones) => {
	return recursiveCost(stones)
}

const recursiveCost = (stones, cost = 0, pyramid = [], total = 0) => {
	// Define the expected total length of and the current index
	const length = stones.length + pyramid.length
	const index = length - stones.length
	
	// Define what the next element should look like
	let want
	if (index < length / 2) {
		want = index + 1
	} else {
		want = length - index - ((length + 1) % 2)
	}

	// End recursion if the want is less than or equal to 0
	if (want <= 0 && pyramid.length === length) return total

	const lookingFor = want + cost
	const foundIndex = stones.indexOf(lookingFor)

	// If the element exists
	if (foundIndex >= 0) {
		const nextStones = removeAtIndex(stones, foundIndex)
		const nextPyramid = pyramid.concat([want])
		const nextTotal = total + cost
		
		return recursiveCost(nextStones, 0, nextPyramid, nextTotal)
	} else {
	// Otherwise increase cost and try again
		return recursiveCost(stones, cost + 1, pyramid, total)
	}
}