So I am creating a maze generating algorithm using recursive backtracking. I keep track of the points that I visit in a stack using a matrix. This matrix has two columns, one for the x-coordinate, and one for the y-coordinate. The problem is, my program works for small mazes, but for bigger mazes my calculator runs out of memory. I was wondering if there is a less memory intensive way to implement a stack. I'm thinking about using strings as a possible way to do it. I use a ti-84 CSE by the way.
Your stack should probably be implemented using a list. I'll be using L1 for demonstration purposes. A stack is a last-in, first-out data structure. List elements are accessible by using
L1(X)
Where X is the item you want. This means first in has to go to L1(1) (the beginning of the list; the 1st item), and onwards, and first out has to come out of the last item in the list. To find how many items are in a list (and therefore find out the Nth item is the last) use
dim(L1)
This will give a number of how many items there are. Instead of storing it to a variable, we can use it to always access the last item in a list. using this:
L1(dim(L1))->M
//this addresses the item of L1 at dim(L1), meaning the last item
Now M will have the value of the last item. This is the first-out part. Then, to destroy the last item (since you popped it off), do this:
dim(L1)-1->dim(L1)
So putting it all together, your "pop" code will be:
If dim(L1)>0
Then
// It checks if L1 has an element to pop off in the first place
L1(dim(L1))->M
dim(L1)-1->dim(L1)
End
Now, M will have the value of the last item, and the last item is destroyed. Now, onto the push code. To push, you must put your number into a new slot one higher than the old last number. Essentially, you must make a new last item to put it in. Luckily, this is very easy in TI-Basic. Your "push" code would be:
If dim(L1)<99
// It checks if L1 has less than the maximum number of elements,
// which is 99.
M->L1(dim(L1)+1)
And if you're gonna be storing X/Y coordinates with your stack, I'd recommend a format such as this:
X + .01Y -> M
//X=3, Y = 15
// This would make M be 3.15
And to seperate these back into two seperate coordinates:
int(M)->X
// The integer value of M is 3, which is what X was earlier
100*fPart(M)->Y
// The fraction part of M was .15. Multiply that by 100 to get 15,
// which is what Y was earlier