0
$\begingroup$

I recently got an amazing answer to an SO question about how to calculate the path in a tree to an item, where you give it the corresponding array index, and the array size, and chunk size (don't even need to use the tree itself!):

const data = [
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 105, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0
]

const tree = divide(data, 5)
assert(tree, walk(5, 100, 42), 3)
assert(tree, walk(5, 100, 44), 105)

function assert(tree, path, value) {
  let drill = tree;
  while (path.length) {
    drill = drill[path.shift()]
  }
  if (drill !== value) {
    throw new Error(`${drill} != ${value}`)
  }
  console.log('It matches', value)
}

function walk(chunkSize, dataSize, index) {
  let depth = Math.floor(Math.log(dataSize - 1) / Math.log(chunkSize)) + 1
  let path = []
  let i = 0
  while (i < depth) {
    path.unshift(index % chunkSize)
    index = Math.floor(index / chunkSize)
    i++
  }
  return path
}

function divide(data, size) {
  if (data.length <= size) return data
  const result = []
  for (let i = 0; i < data.length; i += size) {
    result.push(data.slice(i, i + size))
  }
  return divide(result, size)
}

How can you prove, mathematically, that this is the solution to the problem? That walk will give you a path to the corresponding index in the tree? How do you show from first principles mathematically that this is how it works? To me this is just pure magic, I don't see how anyone could have figured this out other than through brute force and then just memorizing the answer haha.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.