3
\$\begingroup\$

Here we have the following code.

let i = 1
while (i <= 256) {
  log(i)
  i++
}

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;
}

function log(n) {
  console.log(`${n} => ${JSON.stringify(shape(n))}`)
}

It consists of a shape function which takes a number from 1 to 256, and outputs an array following this pattern (here is a snippet):

base-1
  a

base-2
  a
  b

base-3
  a
  tree
    b
    c

base-4
  a
  b
  c
  d

base-5
  a
  b
  c
  tree
    d
    e

base-6
  a
  b
  tree
    c
    d
  tree
    e
    f

base-7
  a
  b
  tree
    c
    d
    e
    f
  tree
    g

Basically, it says the "shape" of the tree that should be produced. For example, on log(12) it outputs [6,4,2]. That means there should be 6 top-level elements, followed by nested 2 elements (starting from the top), followed by nested 2 elements (starting from the top again). This shape function will always return an array where every level of the array has a power of 2 number of elements (6 + 2 children is 8 a power of 2, 2 is power of 2, and 2 is a power of 2).

The question is, how can you remove the duplication of the shape function, where it has loops for 2, 3, or 4 nested arrays? How can you remove those "cases" and make it into a generic loop of some sort that tries 2, then tries 3, then tries 4, without a switch statement or any sort of duplication?

\$\endgroup\$
4
  • 5
    \$\begingroup\$ en.wikipedia.org/wiki/Recursion \$\endgroup\$
    – BCdotWEB
    Feb 15, 2022 at 9:34
  • 1
    \$\begingroup\$ @Lance Can you explain why 12 => [6,4,2] but not [4,2,2,2,2] I didn't quite catch the idea. But I have a feeling that maybe there is no need for so many cycles, everything can be solved by calculation. \$\endgroup\$ Feb 16, 2022 at 18:52
  • \$\begingroup\$ @DaniilLoban because I think it tries to fill the top-level with as many nodes as it can, to keep the traversal to a minimum. Then it fills the nested nodes with whatever else. It would look like this for example: [a, b, c, d, e, f, [g, h, i, j], [k, l]]. See this question for all the possible shapes (at the bottom). \$\endgroup\$
    – Lance
    Feb 16, 2022 at 20:12
  • \$\begingroup\$ @Lance there is an option how to improve this code by almost getting rid of embedded loops, but its performance drops by 2.5 times on average, so I do not know if it is worth publishing, it only has flexibility. \$\endgroup\$ Feb 17, 2022 at 15:24

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.