I love this answer to that question, it’s so creative and robust. I translated it to support 256 values without supporting null arrays, and the tree/array shape
generation seems to work. However, I am stuck on how the encoding radix-like function works, and how to translate that given that now POSSIBLE_SHAPE_LIST
is only 9 elements instead of 16 now. How do I get getPath
to appropriate put the path to the value in the tree structure, given the index? Here is the full code:
const POSSIBLE_SHAPE_LIST = [1, 2, 4, 8, 16, 32, 64, 128, 256] const CODE_LIST = collect() console.log(CODE_LIST.join('n')) console.log(getPath(28, 21)) function getPath(size, i) { let code = CODE_LIST[size - 1] let limit = POSSIBLE_SHAPE_LIST[code % POSSIBLE_SHAPE_LIST.length] if (i < limit) { return [i] } for (let sub = 1; sub < 6; sub++) { i -= limit code /= 9 limit = POSSIBLE_SHAPE_LIST[code % POSSIBLE_SHAPE_LIST.length] if (i < limit) { return [sub, i] } } } function collect() { let codes = [] for (let n = 1; n <= 256; n++) { let shapeNumbers = shape(n) let code = encode(shapeNumbers) codes.push(code) } return codes } function encode(shapeNumbers) { let code = 0 for (let i = shapeNumbers.length - 1; i >= 0; i--) { code = code * POSSIBLE_SHAPE_LIST.length + POSSIBLE_SHAPE_LIST.indexOf(shapeNumbers[i]) } return code } /** * Returns number of atomic entries, * followed by data-size(s) of subarrays */ function shape(n) { let p = greatestPowerOf2(n); if (p >= n) { // The only cases where there are no subarrays return [n]; } // Try with one subarray for (let sub = 2; sub < n && sub <= 256; sub *= 2) { let top = n - sub + 1; p = greatestPowerOf2(top); if (p >= top) { return [p - 1, sub]; } } // Try with two subarrays for (let sub1 = 2; sub1 < n && sub1 <= 256; sub1 *= 2) { for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) { let top = n - sub1 - sub2 + 2; if (top < 0) break; p = greatestPowerOf2(top); if (p >= top) { return [p - 2, sub1, sub2]; } } } // Try with three subarrays for (let sub1 = 2; sub1 < n && sub1 <= 256; sub1 *= 2) { for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) { for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) { let top = n - sub1 - sub2 - sub3 + 3; if (top < 0) break; p = greatestPowerOf2(top); if (p >= top) { return [p - 3, sub1, sub2, sub3]; } } } } // Try with four subarrays for (let sub1 = 2; sub1 < n && sub1 <= 256; sub1 *= 2) { for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) { for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) { for (let sub4 = 2; sub4 <= sub3; sub4 *= 2) { let top = n - sub1 - sub2 - sub3 - sub4 + 4; if (top < 0) break; p = greatestPowerOf2(top); if (p >= top) { return [p - 4, sub1, sub2, sub3, sub4]; } } } } } // Try with five subarrays for (let sub1 = 2; sub1 < n && sub1 <= 256; sub1 *= 2) { for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) { for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) { for (let sub4 = 2; sub4 <= sub3; sub4 *= 2) { for (let sub5 = 2; sub5 <= sub4; sub5 *= 2) { let top = n - sub1 - sub2 - sub3 - sub4 - sub5 + 5; if (top < 0) break; p = greatestPowerOf2(top); if (p >= top) { return [p - 5, sub1, sub2, sub3, sub4, sub5]; } } } } } } // Try with 6 subarrays for (let sub1 = 2; sub1 < n && sub1 <= 256; sub1 *= 2) { for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) { for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) { for (let sub4 = 2; sub4 <= sub3; sub4 *= 2) { for (let sub5 = 2; sub5 <= sub4; sub5 *= 2) { for (let sub6 = 2; sub6 <= sub5; sub6 *= 2) { let top = n - sub1 - sub2 - sub3 - sub4 - sub5 - sub6 + 6; if (top < 0) break; p = greatestPowerOf2(top); if (p >= top) { return [p - 6, sub1, sub2, sub3, sub4, sub5, sub6]; } } } } } } } // Try with 7 subarrays for (let sub1 = 2; sub1 < n && sub1 <= 256; sub1 *= 2) { for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) { for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) { for (let sub4 = 2; sub4 <= sub3; sub4 *= 2) { for (let sub5 = 2; sub5 <= sub4; sub5 *= 2) { for (let sub6 = 2; sub6 <= sub5; sub6 *= 2) { for (let sub7 = 2; sub7 <= sub6; sub7 *= 2) { let top = n - sub1 - sub2 - sub3 - sub4 - sub5 - sub6 - sub7 + 7; if (top < 0) break; p = greatestPowerOf2(top); if (p >= top) { return [p - 7, sub1, sub2, sub3, sub4, sub5, sub6, sub7]; } } } } } } } } throw new Error(n) } function greatestPowerOf2(n) { return n >= 256 ? 256 : n >= 128 ? 128 : n >= 64 ? 64 : n >= 32 ? 32 : n >= 16 ? 16 : n >= 8 ? 8 : n >= 4 ? 4 : n >= 2 ? 2 : 1; }
It should not log (at the end) [21]
, it should log something like [14, 1]
following the pattern laid out here. What am I doing wrong in the translation from the original answer?
Advertisement
Answer
There are two issues to fix:
POSSIBLE_SHAPE_LIST = [1, 2, 4, 8, 16, 32, 64, 128, 256]
is only listing the possible values that represent subarrays, but it does not list all possible values for the first element in a shape representation, i.e. the number of atomic values that are not in a nested array. This number does not have to be a power of 2. For instance, the shape for size 28 is [12, 4, 4, 4], which means that there are 3 subarrays of size 4, but also 12 top-level slots. That 12 is not a power of 2, but still needs to be encoded.code /= 9
will perform a floating point division (unlike in Java). And also, that 9 should not be hardcoded since you have a constant for it.So write:
code = Math.floor(code / POSSIBLE_SHAPE_LIST.length)
For resolving the first issue, I would propose to split the collect
functionality into steps:
- Collect all the shapes without encoding them
- Collect the distinct numbers that are used in those shapes and assign that to
POSSIBLE_SHAPE_LIST
- Perform the encoding of those shapes.
So the script could start with this:
let shapes = collectShapes(); // Step 1 const POSSIBLE_SHAPE_LIST = getUsedNumbers(shapes); // Step 2 console.log(POSSIBLE_SHAPE_LIST); // Demonstrate that list has 35 instead of 9 values const CODE_LIST = shapes.map(encode); // Step 3 console.log(CODE_LIST.join('n')); console.log("the shape for size 28 is ", shapes[27]); // for debugging console.log(getPath(28, 21)); // [3, 1] function getUsedNumbers(shapes) { const usedNumberSet = new Set([1,2,4,8,16,32,64,128,256]); for (const shapeNumbers of shapes) { usedNumberSet.add(shapeNumbers[0]); } // Not really necessary to sort, but it is a nice-to-have return [...usedNumberSet].sort((a, b) => a - b); } function collectShapes() { let shapes = []; for (let n = 1; n <= 256; n++) { shapes.push(shape(n)); } return shapes; }
NB: I have the habit to terminate statements with semi-colons, as I don’t want to be dependent on the automatic semi-colon insertion algorithm.