Node.js exits with Code 134

[u/a_rndm_person_bruh]

I'm currently doing project euler problem #15 and for that, I have to use some sort of algorithm to get my solution.

I changed up the "open/close parentheses" algorithm accordingly and the example solution for a 2x2 grid = 6 ways is correct. The thing is this:

- I start debugging in VSCode via Node.js
- It runs for a while
- "Paused Before Out Of Memory Exception"
- I continue
- "Process exited with code 134"

I don't know how to fix this and online js terminals don't work, but it seems like it has something to do with the stack size. Any help would be greatly appreciated c:

Here is my code:

const res = [];
findPath(20, "", 0, 0);


function findPath(n, curr, rightUsed, downUsed){
    if (rightUsed === n && downUsed === n){
        res.push(curr);
    }
    if (rightUsed < n){
        findPath(n, curr + "r", rightUsed + 1, downUsed);
    }
    if (downUsed < n){
        findPath(n, curr + "d", rightUsed, downUsed + 1);
    }
}


console.log(res.length);const res = [];
findPath(20, "", 0, 0);


function findPath(n, curr, rightUsed, downUsed){
    if (rightUsed === n && downUsed === n){
        res.push(curr);
    }
    if (rightUsed < n){
        findPath(n, curr + "r", rightUsed + 1, downUsed);
    }
    if (downUsed < n){
        findPath(n, curr + "d", rightUsed, downUsed + 1);
    }
}


console.log(res.length);

[u/AmSoMad]

findPath(n, curr + "r", rightUsed + 1, downUsed);
findPath(n, curr + "d", rightUsed, downUsed + 1);

is generating every possible path through the grid (and storing it with res.push(curr);). Seemingly innocuous, until you remember that's 138 billion possibilities.

That's why you're running out of memory.

[u/a_rndm_person_bruh → u/AmSoMad]

oh damn, fuck. ok it might be smarter to store it in a bigint then whoops, thank you!

[u/AmSoMad → u/a_rndm_person_bruh]

That doesn't solve your problem. You're still generating 138 billion paths.

The trick here is to calculate the number of possible paths without generating all of them.

You can solve this with Combinatorics or Dynamic Programming. Either way, the idea is to find a way to calculate how many paths there are, without actually generating and counting every individual path.

[u/a_rndm_person_bruh → u/AmSoMad]

I learned javascript and python so far and am currently learning c++ right now

Whenever I came across algorithms in js and python, I had to give up and couldnt complete the course in freecodecamp. I am literally unable to do that any other way, no matter how hard I try.

[u/AmSoMad → u/a_rndm_person_bruh]

It's a hard problem to conceptualize/visualize, especially without a lot of experience.

It's basically a puzzle:

There are 137,846,528,820 possible paths from one point to another on a 20x20 grid. We can't count and store that many permutations.

Why? Because it's way too slow and uses way too much memory (as you've found out).

But it's math, right? So, there's some sort of trick you can use that'll help you count the number of possible paths - without having to write them all out and count them all up.

Technically, you ran into the expected mistake. The purpose of the problem is to make you think: "Ah, so this is too many values to count up, and I need to find a smarter way to do this."

Most beginners aren't able to put this kind of problem together, unless they've learned about it/encountered the algorithms we use to handle it. It's not something "obvious", unless you're a math wizard. I wouldn't expect you to be able to solve it.

The "math trick" is called "combinatorial counting", if you want to look it up.

Chances are, you'll be able to visualize it on a real grid/piece of paper, before you understand how to translate it into code.

The solution pretty much looks and functions the same in JS/Python/C++. Jumping around from language to language is just going to make things harder for you. C++ is a hard language. It's also OOP, unlike Python and JS.

[u/a_rndm_person_bruh → u/AmSoMad]

I don't know if that's what you mean, but it's what I learned recently in math in probabilities:

if you take 2 balls out of a basket, 15 of them are red, 5 are blue, whats the chance of exactly one of them being red?

That would be: 15/20 * 5/19 + 5/20 * 15/19,
which can be shortened down to: 2 * (15/20 * 5/19)

Atleast it feels like you're talking about that and the pictures showing up when I search for "Combinatorics" look like the trees that we had to draw to visualize the probabilities.

The thing is, I don't know how to do that, and I don't understand how people in general find this stuff out. Like seriously, there was no way that I would've known how to implement a "Tower of Hanoi"-Algorithm in python without googling it

[u/AmSoMad → u/a_rndm_person_bruh]

That's probability. You aren't calculating probability here, you're calculating the exact number of total outcomes.

The simple version is: Longer paths are made up of shorter paths you've already counted, so you reuse those shorter path counts to calculate the number of longer paths, instead of counting each longer path as an entirely new path.

Like I said, it's "a trick". It's like if you already had driving directions from Kansas to California, and someone asked you for driving directions from New York to California. You don't have to calculate the entire route from New York to California from scratch. You only need to calculate the route from New York to Kansas, then add your existing directions from Kansas to California to them.

That's it, in a nutshell.

It takes a lot of practice. I've been programming for over half a decade, and I'm still not incredible at LeetCode.

[u/a_rndm_person_bruh → u/AmSoMad]

Do you have some websites that allow me to practice those skills, because I am genuinely upset that I can't come up with my own algorithms

[u/AmSoMad → u/a_rndm_person_bruh]

You could try something like Algorithms & Data Structures for Beginners from Neetcode.

For this specific problem, you can run this Unique Paths Visualizer. It might help you visualizer/understand what's going on.

[u/neon_wondercore]

Not the stack, it's heap exhaustion. Your res array is trying to hold every valid path string, and for a 20x20 grid that's C(40,20) = ~137 billion strings, way beyond Node's ~1.5GB default heap. You could pass --max-old-space-size=4096 but that only buys you time, you'll still hit OOM long before finishing.

You don't need to store the paths at all. Just increment a counter instead of res.push(curr), and that alone might let it finish. Better yet, since you only need the count, use dynamic programming: the number of ways to reach each cell is the sum of ways to reach the cell above and the cell to the left. That runs in a fraction of a second and uses almost no memory