How to support 256 values without null in array-tree pattern generator?

Question

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?

Answer 1

There are two issues to fix:

1. 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.

2. 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:

1. Collect all the shapes without encoding them
2. Collect the distinct numbers that are used in those shapes and assign that to POSSIBLE_SHAPE_LIST
3. 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.