Function that sums up all integers from a deeply nested array-CodePudding

I have an issue here, I'm trying to create a function that sums up all integers from a deeply nested array, but it's failing an unit test, which means something is not right. Here is my function:

export const arraySum = (arr) => {
  let sum = 0;
  for (let i = 0; i < arr.length; i  ) {
    if (typeof arr[i] === "number") sum = sum   arr[i];
    else if (Array.isArray(arr[i])) sum = sum   arraySum(arr[i]);
  }
  return sum;
};

And here is my unit test which is failing:

test("it should sum up from deeply nested arrays", () => {
    type ValueOrArray = number | Array<ValueOrArray>;
    const createDeeplyNestedArray = (depth: number): ValueOrArray => {
      let retval: ValueOrArray = [1];
      for (let i = 0; i < depth - 1; i  ) {
        retval = [1, retval];
      }
      return retval;
    };

    const NUMBER_OF_ELEMENTS = 100000;
    const arr = createDeeplyNestedArray(NUMBER_OF_ELEMENTS);
    expect(arraySum(arr)).toEqual(NUMBER_OF_ELEMENTS);
  });

CodePudding user response：

Function memory is stored on something called a "call stack". Whenever you call a function, all of its variables are allocated and pushed onto the 'stack' and when the function returns, they are popped off the stack. Given the following code:

const a = () => {
}

const b = () => {
   a()
   // some code
}

const c = () => {
   b()
}

c()

When c is called, your call stack will contain all the memory for variables used in c. When c calls b, all the memory for variables used in b are added to the stack. When b calls a all the memory for variables used in a are added to the stack. When a finishes executing (so when you get to 'some code'), variables related to a are deallocated and removed from the stack.

The problem you have here is that every time your function recursively calls itself, more memory is being allocated onto the stack. to stop this kind of code using up all the system memory, the runtime limits how big the stack can get - which is why you are hitting this error.

To pass this test, you need a solution which doesn't call itself every time it hits an array within an array. Here's my solution, effectively using an array as a buffer; each time I hit a nested array I add it to the buffer. Once I finish processing the outer array, I then check if there is any arrays left in the buffer.

export const arraySum = (arr) => {
  let sum = 0;
  const buffer = [arr];
  while (buffer.length > 0) {
    const next = buffer.shift();
    for (let i = 0; i < next.length; i  ) {
      if (typeof next[i] === "number") sum = sum   next[i];
      else if (Array.isArray(next[i])) buffer.push(next[i]);
    }
  }
  return sum;
};

CodePudding user response：

That doesn't work bc like Keith said you are reaching the maximum call stack size.

RangeError: Maximum call stack size exceeded is a type of error thrown in JavaScript when a function call is made that exceeds the program's stack size. The call stack is a data structure that keeps track of which functions have been called, and in what order.

Maybe you can try to solve it in a iterative way like this:

 const arraySum = (arr) => {
  if (!Array.isArray(arr)) return 0;
  let sum = 0;
  while (Array.isArray(arr)) {
    let arrCopy = [];
    for (let i = 0; i < arr.length; i  ) {
      if (typeof arr[i] === "number") sum = sum   arr[i];
      else if (Array.isArray(arr[i])) arrCopy = arrCopy.concat(arr[i]);
    }
    arr = arrCopy.length > 0 ? arrCopy : null;
  }
  return sum;
};

CodePudding user response：

We can use a stack or queue in place of recursion. Also, order doesn't matter.

function f(A) {
  let sum = 0;
  let stack = [A];
  
  while (stack.length > 0) {
    stack.pop().forEach(e => {
      if (Array.isArray(e))
        stack.push(e);
      else if (typeof e === "number")
        sum  = e;
    });
  }
  
  return sum;
}

console.log(f([1,2,[3,[4]]]));

CodePudding user response：

The approach of combining a flat based flattening function which circumvents call stack errors of very deeply nested arrays of a nesting depth close to 10_000 and higher and a reduce based function which does sum-up number types only, does solve the OP's problem. And the following implementation does prove it ...

// Implementation
function flatAlmostInfiniteNestedArray(arr) {
  while (arr.length < (arr = arr.flat(1000)).length) {
  }
  return arr;
}
function totalNestedNumberValues(arr) {
  return flatAlmostInfiniteNestedArray(arr)
    .reduce((total, value) => (
      'number' === typeof value
        ? total   value
        : total
    ), 0);
}

// Test
const createDeeplyNestedArray = depth => {
  let retval = [1];
  for (let i = 0; i < depth - 1; i  ) {
    retval = [1, retval];
  }
  return retval;
};
const NUMBER_OF_ELEMENTS = 100000;
const arr = createDeeplyNestedArray(NUMBER_OF_ELEMENTS);

console.log(
  '(totalNestedNumberValues(arr) === NUMBER_OF_ELEMENTS) ?..',
  (totalNestedNumberValues(arr) === NUMBER_OF_ELEMENTS),
);

.as-console-wrapper { min-height: 100%!important; top: 0; }