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.