pyramid-puzzle-gist.js

// As I was considering how to solve the problem, I saw two main paths forward. Either a recursive solution, 
// or an iterative solution. The recursive solution was more obvious to me, so that's where I stared. Looking 
// at the pyramid, what I saw was that the "longest slide down" from any point was going to be sum of that 
// element, plus the "longest slide down" from the max of the left or right options. Visually:

// The pyramid:

      7
    4   8
  6   9   3
5   1   4   9

// Has a capstone of 7 (the top), and two sub-pyramids

    4                   8
  6   9       and     9   3
5   1   4           1   4   9

// This led to my roughly pseudocoded function with a base case and recursive case:

// function longestSlideDown takes pyramid
// base case
//    if pyramid is only 1 row high
//    return the capstone
// recursive case
//    define the left pyramid
//    define the right pyramid
//    recurisvely call longestSlideDown on each pyramid
//    return the value of the capstone plus the larger of the two slides

// That led to the following:

const { max } = require('ramda')

const longestSlideDown = (pyramid) => {
  const height = pyramid.length
  const capstone = pyramid[0][0]
  const underCapstone = pyramid.slice(1)

  if(height == 1) {
    return capstone
  } else {
    const subPyramidLeft = underCapstone.map(row => row.slice(0, row.length - 1))
    const subPyramidRight = underCapstone.map(row => row.slice(1))
    const longestSlideLeft = capstone + longestSlideDown(subPyramidLeft)
    const longestSlideRight = capstone + longestSlideDown(subPyramidRight)
    return max(longestSlideLeft, longestSlideRight)
  }
}

// This works great, if the pyramid is small, however as they pyramid grows this function becomes really
// inefficient. The problem is when the function runs, it ends up caclulating the same slides many times over. 
// If you look at the example above, you can see the small sub pyramid of

  9
1   4

// which ends up getting checked more than once. The value isn't changing, the longest slide from 9 is always
// 9 + 4 = 13, which means memoizing it somehow would be helpful. But how to do that in a recursive function? 
// Part of the challenge here is that when the function is called recursively, it does so as if it is the top 
// of the pyramid. That's by design, but I needed a way for each call to have a sense of where it was in the 
// larger pyramid. The only way I could think to do this is with a passed location object, comprised of the row 
// of the pyramid, and the index of that row. This changed my code like so:

const { max } = require('ramda')

const longestSlideDown = (pyramid, location = {}) => {
  const height = pyramid.length
  const capstone = pyramid[0][0]
  const underCapstone = pyramid.slice(1)
  const row = location.row || 0
  const index = location.index || 0

  if(height == 1) {
    return capstone
  } else {
    const subPyramidLeft = underCapstone.map(row => row.slice(0, row.length - 1))
    const subPyramidRight = underCapstone.map(row => row.slice(1))
    const leftLocation = {row: row + 1, index}
    const rightLocation = {row: row + 1, index: index + 1}
    const longestSlideLeft = capstone + longestSlideDown(subPyramidLeft, leftLocation)
    const longestSlideRight = capstone + longestSlideDown(subPyramidRight, rightLocation)
    return max(longestSlideLeft, longestSlideRight)
  }
}

// This solved the problem of not knowing where I was in the pyramid, but that info is only useful if I'm 
// memoizing the values that I find at each step. This created an additional problem, because memoized values 
// will need to be passed somehow. The way that I thought to do this was with another parameter, memo, that 
// pushes in values as max slide are found. I then added the code to check the memo to see if a found max slide 
// has been caculated at my current location. This was enough for me to successfully traverse the epic pyramid:

const { max } = require('ramda')

const longestSlideDown = (pyramid, location = {}, memo = []) => {
  const height = pyramid.length
  const capstone = pyramid[0][0]
  const underCapstone = pyramid.slice(1)
  const row = location.row || 0
  const index = location.index || 0
  const foundMax = memo.find(item => (item.row == row && item.index == index))

  if(foundMax) {
    return foundMax.maxSlide
  } else if(height == 1) {
    memo.push({row, index, maxSlide: capstone})
    return capstone
  } else {
    const subPyramidLeft = underCapstone.map(row => row.slice(0, row.length - 1))
    const subPyramidRight = underCapstone.map(row => row.slice(1))
    const leftLocation = {row: row + 1, index}
    const rightLocation = {row: row + 1, index: index + 1}
    const longestSlideLeft = capstone + longestSlideDown(subPyramidLeft, leftLocation, memo)
    const longestSlideRight = capstone + longestSlideDown(subPyramidRight, rightLocation, memo)
    const maxSlide = max(longestSlideLeft, longestSlideRight)
    memo.push({row, index, maxSlide})
    return maxSlide
  }
}

// There's a functional trade-off happening in this step. I'm modifying the existing parameter of memo in 
// place with .push, however, given that I would never actually call the function with that parameter, I decided 
// I could live with that. The other way I thought to deal with this necessary impurity was with a wrapper 
// function, which looks very similar:

const { max } = require('ramda')

const longestSlideDown = (pyramid) => {
  const memo = []

  const recursiveLongestSlideDown = (pyramid, location = {}) => {
    const height = pyramid.length
    const capstone = pyramid[0][0]
    const underCapstone = pyramid.slice(1)
    const row = location.row || 0
    const index = location.index || 0
    const foundMax = memo.find(item => (item.row == row && item.index == index))

    if(foundMax) {
      return foundMax.maxSlide
    } else if(height == 1) {
      memo.push({row, index, maxSlide: capstone})
      return capstone
    } else {
      const subPyramidLeft = underCapstone.map(row => row.slice(0, row.length - 1))
      const subPyramidRight = underCapstone.map(row => row.slice(1))
      const leftLocation = {row: row + 1, index}
      const rightLocation = {row: row + 1, index: index + 1}
      const longestSlideLeft = capstone + recursiveLongestSlideDown(subPyramidLeft, leftLocation, memo)
      const longestSlideRight = capstone + recursiveLongestSlideDown(subPyramidRight, rightLocation, memo)
      const maxSlide = max(longestSlideLeft, longestSlideRight)
      memo.push({row, index, maxSlide})
      return maxSlide
    }
  }

  return recursiveLongestSlideDown(pyramid)
}

// After coming up with a recursive solution, my mind turned to the iterative path. While I didn't think 
// about it too much at first, this ended up being an easier solution to the problem. I would probably 
// also argue that it's the more elegant solution.

// The iterative solution requires thinking about the problem differently. Instead of starting at the top, 
// what if we start at the bottom? Consider our same pyramid from before:

      7
    4   8
  6   9   3
5   1   4   9

// Remember from the recursive solution that we saw each pyramid is just a collection of progressively 
// smaller pyramids. In effect, you could think of every element in the bottom row as a 1 row tall pyramid. 
// That means that the whole bottom row is a collection of 'longestSlideDown' results already. We can take 
// this fact, and combine the last two rows, to get the longestSlideDown from the second to last row. 
// Continuing this until we get to the top, will ultimately give us the maxium value:


      7
    4   8               7  
  6   9   3   =>     4    8     =>     7    => 
5   1   4   9     11   13   12      17   21      28

// To double check: 7 + 8 + 9 + 4 = 28

// So how to code that behavior? Here's the pseudocode:

// function longestSlideDown takes pyramid
// use a rightReduce to start with the last row, a collection greatest possible values from the bottom
//    for each iteration of the reduce
//    map over the row, and return the maximum slide from that location, using the summarized values from below
//    since each row is 1 smaller than the last, we naturally consume the pyramid as we move up
// return the final value from the reduced pyramid

// And here's how that looks coded

const { max } = require('ramda')

const longestSlideDown = (pyramid) => {
  return pyramid.reduceRight((greatestSums, row) => {
    return row.map((elem, index) => {
      const sumLeft = elem + greatestSums[index]
      const sumRight = elem + greatestSums[index + 1]
      return max(sumLeft, sumRight)
    })
  })[0]
}