How to make tree pattern fit constraints but so algorithm is generic instead of hardcoded?

Question

Building off this question, the next question is, how to build an algorithm which will take as input an index/integer, and output the path to the appropriate node in the tree. The examples of how the trees might be structured are as follows, but I might be wrong. Ideally there would be a pattern which all of them follow so we can have an equation to map index to path.

base-1
  a

base-2
  a
  b

base-3
  a
  b
  c
  null

base-4
  a
  b
  c
  d

base-5
  a
  b
  c
  tree
    d
    e

base-6
  a
  b
  c
  d
  e
  f
  null
  null

base-7
  a
  b
  c
  d
  e
  f
  g
  null

base-8
  a
  b
  c
  d
  e
  f
  g
  h

base-9
  a
  b
  c
  d
  e
  f
  g
  tree
    h
    i

base-10
  a
  b
  c
  d
  e
  f
  g
  tree
    h
    i
    j
    null

base-11
  a
  b
  c
  d
  e
  f
  g
  tree
    h
    i
    j
    k

base-12
  a
  b
  c
  d
  e
  f
  tree
    g
    h
    i
    j
  tree
    k
    l

base-13
  a
  b
  c
  d
  e
  f
  g
  tree
    h
    i
    j
    k
    l
    m
    null
    null

base-14
  a
  b
  c
  d
  e
  f
  g
  tree
    h
    i
    j
    k
    l
    m
    n
    null

base-15
  a
  b
  c
  d
  e
  f
  g
  tree
    h
    i
    j
    k
    l
    m
    n
    o

base-16
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  p

base-17
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  tree
    p
    q

base-18
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  tree
    p
    q
    r
    null

base-19
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  tree
    p
    q
    r
    s

base-20
  a
  b
  c
  d
  e
  f
  tree
    g
    h
    i
    j
    k
    l
    m
    n
  tree
    o
    p
    q
    r
    s
    t
    null
    null

base-21
  a
  b
  c
  d
  e
  f
  tree
    g
    h
    i
    j
    k
    l
    m
    n
  tree
    o
    p
    q
    r
    s
    t
    u
    null

base-22
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  tree
    p
    q
    r
    s
    t
    u
    v
    null

base-23
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  tree
    p
    q
    r
    s
    t
    u
    v
    w

base-24
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  tree
    o
    p
    q
    r
    s
    t
    u
    v
  tree
    w
    x

base-25
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  tree
    o
    p
    q
    r
    s
    t
    u
    v
  tree
    w
    x
    y
    null

base-26
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  tree
    o
    p
    q
    r
    s
    t
    u
    v
  tree
    w
    x
    y
    z

base-27
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  tree
    n
    o
    p
    q
    r
    s
    t
    u
  tree
    v
    w
    x
    y
  tree
    z
    aa

base-28
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  tree
    o
    p
    q
    r
    s
    t
    u
    v
  tree
    w
    x
    y
    z
    aa
    ab
    null
    null

base-29
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  tree
    p
    q
    r
    s
    t
    u
    v
    w
    x
    y
    z
    aa
    ab
    ac
    null
    null

base-30
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  p
  q
  r
  s
  t
  u
  v
  w
  x
  y
  z
  aa
  ab
  ac
  ad
  null
  null

base-31
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  p
  q
  r
  s
  t
  u
  v
  w
  x
  y
  z
  aa
  ab
  ac
  ad
  ae
  null

base-32
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  p
  q
  r
  s
  t
  u
  v
  w
  x
  y
  z
  aa
  ab
  ac
  ad
  ae
  af

There can only be 32 possible items in each level, and max 2 levels. Each tree can only have power-of-2 number of elements. In some cases I put null because it requires less nodes or less traversal than adding a new tree. If there is not a consistent pattern to it, you can create an appropriate similar pattern if no precise pattern is found. Ideally there is a pattern so an equation can be used to generate the path from an index.

Some other things to note:

Always start the list with the top-most levels filled out as much as possible.
Allow up to 2 null values on 8 or more.

My attempt is pretty hardcoded still.

function getPathFromIndex(size, index) {
  if (size < 5) {
    return [index]
  }

  if (size === 5) {
    if (index > 2) {
      return [2, index - 3]
    } else {
      return [index]
    }
  }

  if (size < 9) {
    return [index]
  }

  if (size < 12) {
    if (index > 6) {
      return [6, index - 7]
    } else {
      return [index]
    }
  }

  // continue hardcoding.
}

Is there a way of accomplishing a similar goal (with the power of 2 constraint, and only 1 level of nesting), yet make the algorithm less hardcoded? Can you restructure the trees in such a way to make that possible?

Some hints:

How many trees does it need to be divided into?
Given that number, how to automatically chunk the array into the tree?

And [example variant](https://gist.github.com/lancejpollard/2c9f31c560d41dbe3119983b1eeeb728) without the idea of null, instead only using nested trees. — Lance, Feb 12 '22 at 12:23
The largest size is 128, but even just doing it for 32 would be helpful. I'm not sure with 128 if you need more layers of nesting than 2. If you do, that is fine, it can be allowed. — Lance, Feb 12 '22 at 15:31
There are many shapes possible for 128. If we take the rule in the first bullet point, then it should probably be something like `28,[32],[32],[32],[4]`, where the first 28 are top level values, after which there are 4 subarrays. Or would you prefer the simpler `[32],[32],[32],[32]`? — trincot, Feb 12 '22 at 15:42
Keeping it consistent with the rules would probably be better, so the first one I would prefer. — Lance, Feb 12 '22 at 16:36

trincot · Accepted Answer · 2022-02-15T18:46:29.920

This is going to be a long road...

As I also could not find a mathematical formula to solve this, I went for a data-driven solution: a lookup table that gives me the shape of the (potentially) nested array for each individual size (between 1 and 128).

A shape can be defined by a few numbers:

The number of top-level, non-null values
The number of non-null values in the first sub array if there is one
The number of non-null values in the second sub array if there is one
The number of non-null values in the third sub array if there is one
The number of non-null values in the fourth sub array if there is one

The potential null padding can be inferred from this information, as we know that a power of 2 must be reached.

An example:

Size = 102

This can be represented with the following numbers:

28, 30, 30, and 14

This means an array of that size will look like this:

[
    0,
    1,
    2,
    3,
    ...,
    27,
    [28, 29,..., 57, null, null],
    [58, 59,..., 87, null, null],
    [88, 89,..., 101, null, null],
    null
]

Note that there are null values involved to reach powers of 2. The top level has (including the final null) 32 elements. The first two inner sub arrays have a total size of 32 (including the padding null values), and the third one has 16 elements (also including the padding).

Generating the shapes

To avoid having to determine shapes manually for each of the 128 array sizes, I wrote a brute force function to make a valid shape choice for each of these sizes. This I just used to fix these shapes, and is not part of the final solution:

function shape(n) { // Returns number of atomic entries, followed by data-size(s) of subarrays
    const greatestPowerOf2 = (n) => 
        n >= 32 ? 32 : n >= 16 ? 16 : n >= 8 ? 8 : n >= 4 ? 4 : n >= 2 ? 2 : 1;

    let p = greatestPowerOf2(n+2);
    if (p >= n) {
        // The only cases where there are no subarrays
        return [n];
    }
    // Try with one subarray
    for (let sub = 2; sub < n && sub <= 32; sub *= 2) {
        let maxInnerNulls = sub == 2 ? 0 : sub == 4 ? 1 : 2;
        let top = n - sub + 1;
        p = greatestPowerOf2(top+2+maxInnerNulls);
        if (p >= top) {
            let nulls = p - top;
            let innerNulls = Math.min(maxInnerNulls, nulls);
            nulls -= innerNulls;
            return [p - 1 - nulls, sub - innerNulls];
        }
    }
    // Try with two subarrays
    for (let sub1 = 2; sub1 < n && sub1 <= 32; sub1 *= 2) {
        let maxInnerNulls1 = sub1 == 2 ? 0 : sub1 == 4 ? 1 : 2;
        for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
            let top = n - sub1 - sub2 + 2;
            if (top < 0) break;
            let maxInnerNulls2 = sub2 == 2 ? 0 : sub2 == 4 ? 1 : 2;
            p = greatestPowerOf2(top+2+maxInnerNulls1+maxInnerNulls2);
            if (p >= top) {
                let nulls = p - top;
                let innerNulls1 = Math.min(maxInnerNulls1, nulls);
                nulls -= innerNulls1;
                let innerNulls2 = Math.min(maxInnerNulls2, nulls);
                nulls -= innerNulls2;
                return [p - 2 - nulls, sub1 - innerNulls1, sub2 - innerNulls2];
            }
        }
    }
    // Try with three subarrays
    for (let sub1 = 2; sub1 < n && sub1 <= 32; sub1 *= 2) {
        let maxInnerNulls1 = sub1 == 2 ? 0 : sub1 == 4 ? 1 : 2;
        for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
            let maxInnerNulls2 = sub2 == 2 ? 0 : sub2 == 4 ? 1 : 2;
            for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) {
                let top = n - sub1 - sub2 - sub3 + 3;
                if (top < 0) break;
                let maxInnerNulls3 = sub3 == 2 ? 0 : sub3 == 4 ? 1 : 2;
                p = greatestPowerOf2(top+2+maxInnerNulls1+maxInnerNulls2+maxInnerNulls3);
                if (p >= top) {
                    let nulls = p - top;
                    let innerNulls1 = Math.min(maxInnerNulls1, nulls);
                    nulls -= innerNulls1;
                    let innerNulls2 = Math.min(maxInnerNulls2, nulls);
                    nulls -= innerNulls2;
                    let innerNulls3 = Math.min(maxInnerNulls3, nulls);
                    nulls -= innerNulls3;
                    return [p - 3 - nulls, sub1 - innerNulls1, sub2 - innerNulls2, sub3 - innerNulls3];
                }
            }
        }
    }
    // Try with four subarrays
    for (let sub1 = 2; sub1 < n && sub1 <= 32; sub1 *= 2) {
        let maxInnerNulls1 = sub1 == 2 ? 0 : sub1 == 4 ? 1 : 2;
        for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
            let maxInnerNulls2 = sub2 == 2 ? 0 : sub2 == 4 ? 1 : 2;
            for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) {
                let maxInnerNulls3 = sub3 == 2 ? 0 : sub3 == 4 ? 1 : 2;
                for (let sub4 = 2; sub4 <= sub3; sub4 *= 2) {
                    let top = n - sub1 - sub2 - sub3 - sub4 + 4;
                    if (top < 0) break;
                    let maxInnerNulls4 = sub4 == 2 ? 0 : sub4 == 4 ? 1 : 2;
                    p = greatestPowerOf2(top+2+maxInnerNulls1+maxInnerNulls2+maxInnerNulls3+maxInnerNulls4);
                    if (p >= top) {
                        let nulls = p - top;
                        let innerNulls1 = Math.min(maxInnerNulls1, nulls);
                        nulls -= innerNulls1;
                        let innerNulls2 = Math.min(maxInnerNulls2, nulls);
                        nulls -= innerNulls2;
                        let innerNulls3 = Math.min(maxInnerNulls3, nulls);
                        nulls -= innerNulls3;
                        let innerNulls4 = Math.min(maxInnerNulls4, nulls);
                        nulls -= innerNulls4;
                        return [p - 4 - nulls, sub1 - innerNulls1, sub2 - innerNulls2, sub3 - innerNulls3, sub4 - innerNulls4];
                    }
                }
            }
        }
    }
}

I admit this code is not elegant, with lots of code repetition, but it serves the intended purpose: it generates a shape (the set of numbers explained above) for any given array size.

Encoding the shapes in less space

The numbers for the sub arrays cannot be just any number. They must be either a power of 2, or one less (when one padding null is assumed) or two less (when two null values are assumed). So the possible numbers are in this set:

[1, 2, 3, 4, 6, 7, 8, 14, 15, 16, 30, 31, 32]

The first number (which represents the count of values at the top level), can also be in that set, but can also be in the range 27 - 29. This is because the sub arrays that follow and potential null padding also count for reaching the power of 2 at the top level. This means that there are exactly 16 possible numbers in the first position of the shape "encoding". We could compress this encoding by mapping these numbers to 4-bit values (giving 16 possibilities). As it turned out there are never more than 4 subarrays needed, we will need 20 bits for encoding a shape.

Now we should determine what these 20-bit numbers are for 128 shapes and collect them in an array that can serve as lookup table.

Here is the function to encode numbers into that 20-bit encoding:

function encode(shapeNumbers) {
    let code = 0;
    for (let i = shapeNumbers.length - 1; i >= 0; i--) {
        code = code*16 + [1,2,3,4,6,7,8,14,15,16,27,28,29,30,31,32].indexOf(shapeNumbers[i]);
    }
    return code;
}

I collected the codes with this function:

function collectCodes() {
    let codes = [null];
    for (let n = 1; n <= 128; n++) {
        let shapeNumbers = shape(n);
        let code = encode(shapeNumbers);
        codes.push(code);
    }
    return codes;
}

function shape(n) { // Returns number of atomic entries, followed by data-size(s) of subarrays
    const greatestPowerOf2 = (n) => 
        n >= 32 ? 32 : n >= 16 ? 16 : n >= 8 ? 8 : n >= 4 ? 4 : n >= 2 ? 2 : 1;

    let p = greatestPowerOf2(n+2);
    if (p >= n) {
        // The only cases where there are no subarrays
        return [n];
    }
    // Try with one subarray
    for (let sub = 2; sub < n && sub <= 32; sub *= 2) {
        let maxInnerNulls = sub == 2 ? 0 : sub == 4 ? 1 : 2;
        let top = n - sub + 1;
        p = greatestPowerOf2(top+2+maxInnerNulls);
        if (p >= top && p <= 32) {
            let nulls = p - top;
            let innerNulls = Math.min(maxInnerNulls, nulls);
            nulls -= innerNulls;
            return [p - 1 - nulls, sub - innerNulls];
        }
    }
    // Try with two subarrays
    for (let sub1 = 2; sub1 < n && sub1 <= 32; sub1 *= 2) {
        let maxInnerNulls1 = sub1 == 2 ? 0 : sub1 == 4 ? 1 : 2;
        for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
            let top = n - sub1 - sub2 + 2;
            if (top < 0) break;
            let maxInnerNulls2 = sub2 == 2 ? 0 : sub2 == 4 ? 1 : 2;
            p = greatestPowerOf2(top+2+maxInnerNulls1+maxInnerNulls2);
            if (p >= top && p <= 32) {
                let nulls = p - top;
                let innerNulls1 = Math.min(maxInnerNulls1, nulls);
                nulls -= innerNulls1;
                let innerNulls2 = Math.min(maxInnerNulls2, nulls);
                nulls -= innerNulls2;
                return [p - 2 - nulls, sub1 - innerNulls1, sub2 - innerNulls2];
            }
        }
    }
    // Try with three subarrays
    for (let sub1 = 2; sub1 < n && sub1 <= 32; sub1 *= 2) {
        let maxInnerNulls1 = sub1 == 2 ? 0 : sub1 == 4 ? 1 : 2;
        for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
            let maxInnerNulls2 = sub2 == 2 ? 0 : sub2 == 4 ? 1 : 2;
            for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) {
                let top = n - sub1 - sub2 - sub3 + 3;
                if (top < 0) break;
                let maxInnerNulls3 = sub3 == 2 ? 0 : sub3 == 4 ? 1 : 2;
                p = greatestPowerOf2(top+2+maxInnerNulls1+maxInnerNulls2+maxInnerNulls3);
                if (p >= top && p <= 32) {
                    let nulls = p - top;
                    let innerNulls1 = Math.min(maxInnerNulls1, nulls);
                    nulls -= innerNulls1;
                    let innerNulls2 = Math.min(maxInnerNulls2, nulls);
                    nulls -= innerNulls2;
                    let innerNulls3 = Math.min(maxInnerNulls3, nulls);
                    nulls -= innerNulls3;
                    return [p - 3 - nulls, sub1 - innerNulls1, sub2 - innerNulls2, sub3 - innerNulls3];
                }
            }
        }
    }
    // Try with four subarrays
    for (let sub1 = 2; sub1 < n && sub1 <= 32; sub1 *= 2) {
        let maxInnerNulls1 = sub1 == 2 ? 0 : sub1 == 4 ? 1 : 2;
        for (let sub2 = 2; sub2 <= sub1; sub2 *= 2) {
            let maxInnerNulls2 = sub2 == 2 ? 0 : sub2 == 4 ? 1 : 2;
            for (let sub3 = 2; sub3 <= sub2; sub3 *= 2) {
                let maxInnerNulls3 = sub3 == 2 ? 0 : sub3 == 4 ? 1 : 2;
                for (let sub4 = 2; sub4 <= sub3; sub4 *= 2) {
                    let top = n - sub1 - sub2 - sub3 - sub4 + 4;
                    if (top < 0) break;
                    let maxInnerNulls4 = sub4 == 2 ? 0 : sub4 == 4 ? 1 : 2;
                    p = greatestPowerOf2(top+2+maxInnerNulls1+maxInnerNulls2+maxInnerNulls3+maxInnerNulls4);
                    if (p >= top && p <= 32) {
                        let nulls = p - top;
                        let innerNulls1 = Math.min(maxInnerNulls1, nulls);
                        nulls -= innerNulls1;
                        let innerNulls2 = Math.min(maxInnerNulls2, nulls);
                        nulls -= innerNulls2;
                        let innerNulls3 = Math.min(maxInnerNulls3, nulls);
                        nulls -= innerNulls3;
                        let innerNulls4 = Math.min(maxInnerNulls4, nulls);
                        nulls -= innerNulls4;
                        return [p - 4 - nulls, sub1 - innerNulls1, sub2 - innerNulls2, sub3 - innerNulls3, sub4 - innerNulls4];
                    }
                }
            }
        }
    }
}

function encode(shapeNumbers) {
    let code = 0;
    for (let i = shapeNumbers.length - 1; i >= 0; i--) {
        code = code*16 + [1,2,3,4,6,7,8,14,15,16,27,28,29,30,31,32].indexOf(shapeNumbers[i]);
    }
    return code;
}

function collectCodes() {
    let codes = [null];
    for (let n = 1; n <= 128; n++) {
        let shapeNumbers = shape(n);
        let code = encode(shapeNumbers);
        codes.push(code);
    }
    return codes;
}

console.log(JSON.stringify(collectCodes()));

This gave this result:

[null,0,1,2,3,18,4,5,6,21,37,53,68,69,7,8,9,24,40,56,71,72,88,104,359,855,871,111,119,120,13,14,15,30,46,62,77,78,94,110,365,861,877,124,125,126,142,158,413,909,925,1405,1661,1677,1693,5788,1915,1916,1917,220,221,222,238,254,509,1005,1021,1501,1757,1773,1789,30588,2011,2012,2013,2269,2525,2541,2557,6652,14828,14844,26844,27100,27116,27132,30683,30684,3547,3548,3549,3805,4061,4077,4093,8188,16364,16380,28380,28636,28652,28668,32219,32220,36316,40412,40668,40924,40940,40956,106491,237547,237563,433883,434139,434155,434171,56794,56795,56796,60892,64988,65244,65500,65516,65532,131067,262123,262139]

The solution code

Now that we have this, we can throw away the above JavaScript functions. This array has the info we need to reproduce a shape or to translate an index into a path.

const codes = [null,0,1,2,3,18,4,5,6,21,37,53,68,69,7,8,9,24,40,56,71,72,88,104,359,855,871,111,119,120,13,14,15,30,46,62,77,78,94,110,365,861,877,124,125,126,142,158,413,909,925,1405,1661,1677,1693,5788,1915,1916,1917,220,221,222,238,254,509,1005,1021,1501,1757,1773,1789,30588,2011,2012,2013,2269,2525,2541,2557,6652,14828,14844,26844,27100,27116,27132,30683,30684,3547,3548,3549,3805,4061,4077,4093,8188,16364,16380,28380,28636,28652,28668,32219,32220,36316,40412,40668,40924,40940,40956,106491,237547,237563,433883,434139,434155,434171,56794,56795,56796,60892,64988,65244,65500,65516,65532,131067,262123,262139];

const codeMap = [1,2,3,4,6,7,8,14,15,16,27,28,29,30,31,32];

function getPath(size, i) {
    let code = codes[size];
    let limit = codeMap[code % 16];
    if (i < limit) return [i];
    for (let sub = limit; code; sub++) {
        i -= limit;
        code >>= 4;
        limit = codeMap[code % 16];
        if (i < limit) return [sub, i];
    }
}

// Demo with size 28
let size = 28;
for (let i = 0; i < size; i++) {
    console.log(i, JSON.stringify(getPath(size, i)));
}

This is wonderful, thank you!! Can you explain what the brute force `shape` function is doing? Is it possible to make it more dynamic? Just wondering, I can try soon. I bet with this approach you could optimize it by generating _functions_ that are each hardcoded to the specific shape, then it doesn't need to do that complex loop to get the path. — Lance, Feb 15 '22 at 01:25
`shape` looks for a tree structure that fits the given size and stays within the rules. It gives precedence to trees that have the fewest possible subarrays. So for instance, if the size is a power of 2 (<= 32) when you add 0, 1 or 2 nulls, then the best solution is a flat array of that size. Then a solution is tried with one subarray, allowing for nulls to be padded to the inner and outer array, ...etc, ...etc. What do you mean with more dynamic? More elegant code avoiding code repetition? — trincot, Feb 15 '22 at 08:02
Ok, well now I want to try and do it [without nulls](https://gist.github.com/lancejpollard/2c9f31c560d41dbe3119983b1eeeb728) this time, with 256 being the max instead of 128, and where 256 is the max of each subtree instead of 32. So I need to first better understand how you did this, so I can try this alternate approach. Your solution is so deep and yet so elegant. Really cool! I want to follow the same sort of codes idea, I like it a lot. Really, after it hits 256, it will change data structure to a skip-list, but 256 or less will use something like this. — Lance, Feb 15 '22 at 08:05
Ah, without nulls, you'd have to make the calls to `greatestPowerOf2(n)` without adding something to the argument. So `greatestPowerOf2(n)` and `greatestPowerOf2(top)`. And lose all the variables that refer to nulls. But you would need to add (duplicate) code to cover the need for 5 subarrays, and maybe even 6. Just try how far you get (with increasing sizes) before the code runs to the end without finding a solution. Repetition of code could be avoided by using recursion in some way, but I didn't give that a thought until now. — trincot, Feb 15 '22 at 08:09
How does the `encode` function work, is it some sort of radix-like thing? — Lance, Feb 15 '22 at 08:26
It just takes the list of possible values (the array with 16 entries) and uses the *index* of that array as the code for it. Then it considers that such a single code takes 4 bits, and so adding more of them to the same final code, means shifting four bits to make room for the next code, ...etc. Yes, you could see it as a radix based solution. The radix is 16 here. — trincot, Feb 15 '22 at 08:31
Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/242030/discussion-between-lance-and-trincot). — Lance, Feb 15 '22 at 09:11
I think the `getPath` is incorrect, it is returning `[1, 1]` for size=29, i=14 in my case in the new implementation. I think it's because `return [sub, i]`, sub will be 1 through 6 (also not sure why the 6), but it should take into account the top-level offset of items. Any ideas? — Lance, Feb 15 '22 at 18:04
That limitation of 6 is related to the expected number of subarrays... it is not generic. A better stop condition is `code`, i.e. it should be non-zero. Do you mean with "new implementation", the one with sizes up to 256? — trincot, Feb 15 '22 at 18:27
Yes new implementation is one with 256. But I think it's incorrect also here as well, with `return [sub, i]`, `sub` needs to account for the top-level items or something. — Lance, Feb 15 '22 at 18:34
Indeed, the value for `sub` should start at `limit`, not at `1`. So the loop should read `for (let sub = limit; code; sub++)`. Corrected in the answer now. — trincot, Feb 15 '22 at 18:46
Should it be `sub - 1`? [Here](https://imgur.com/a/qfno0U9) is size=29,i=14, looks like off by 1. Maybe I'm misreading :p — Lance, Feb 15 '22 at 19:28
I think it is correct, the 13 toplevel items have index numbers 0 to 12, then index 13 is the first subarray, and in that array we have the 13th element at index 0, and the fourteenth at index 1. So [13, 1] seems correct. — trincot, Feb 15 '22 at 20:16

How to make tree pattern fit constraints but so algorithm is generic instead of hardcoded?

1 Answers1

An example:

Generating the shapes

Encoding the shapes in less space

The solution code

Linked