is this viable / possible on the TI99/4A? using XB

[1980gamer]

I need to write a recursive function well subroutine that will scan the play field for adjacent matching blocks.

 

5x5 example:

 

10011

11010

01100

00100

1111 <-- if a 1 is dropped here

 

the X's would be removed data

 

x0011

xx010

0xx00

00x00

xxxxx

 

Leaving:

 

0011

010

000

0000

 

Dropping a zero on any of the bottom 3 lines would leave us

 

11

1

 

Think along the line of Same Game. In fact, I was thinking of trying to do same game! But this is for something else.

 

I would be grateful any feedback or expedience you may have.

 

 

 

 

[RXB]

Is this XB?

[1980gamer]

Ideally it would be done in XB.

 

However, it may not be possible. Or if possible, maybe to slow to be viable?

 

If a "plug-in" could be used, I would do that, if XB is not possible. I may need to brute force this, but that would certainly be slow and larger than I want.

.

Edited September 8, 2018 by 1980gamer

[Asmusr]

Instead of a recursive function you could use a stack to keep track of which block to check next.

[1980gamer]

Hi Asmusr, A stack?

 

I don't know what you are saying? Maybe this is what I call brute force?

 

My play field will be at the most 10x9 -1 I was first thinking of storing row and column data in an array were Source Char matched the char to the left and keep going left until it did not match.

Then, Match up 1. If it matched, then go left until no match, then go right until no match. Now, do I go up a row, or do I go left or right if a match exists, then go up. then look left right over and over...

This runs away quickly. Thus, recursive seems like the way to do this.....?

 

But, I have seen the magic you have created here. So, can you explain use a stack for me? Note. I am a very procedural thinker. I write TSQL all day..

[Asmusr]

A stack is a list or array with two main operations: push to place a value on top of the stack and pop to get and remove the top value.

 

It would take me far too long time to try to write this in BASIC, so here is some pseudo Java-like code to try to explain the difference between using a recursive function and a stack. To keep it short I'm assuming you can push two values onto the stack in one operation: stack.push(x,y).

Recursive:

check(x, y, value) {
	if (map(x,y)==value) {
	    map(x,y)='x'
	    check(x-1,y,value)
	    check(x,y+1,value)
	    check(x,y-1,value)
	}
}

Using a stack:

stack.push(x, y)
while (stack.isNotEmpty()) {
	y = stack.pop()
        x = stack.pop()
	if (map(x,y)==value) {
		map(x,y)='x'
		stack.push(x-1,y)
		stack.push(x,y+1)
		stack.push(x,y-1)
	}
}

[1980gamer]

Thank you for the example!

 

I will try to convert this to xb I think I can do this.

 

Don't you wish TI had do while I use for next with early exit logic. I used to roll my own, but I have been using for next lately and it is easier.

[RXB]

Thank you for the example!

 

I will try to convert this to xb I think I can do this.

 

Don't you wish TI had do while I use for next with early exit logic. I used to roll my own, but I have been using for next lately and it is easier.

Hmmm DO WHILE is just:

If X=SOMETHING THEN SUBROUTINE

 

You could even make it a SUB routine CALL DOWHILE(x)

[+Lee Stewart]

Hmmm DO WHILE is just:

If X=SOMETHING THEN SUBROUTINE

 

You could even make it a SUB routine CALL DOWHILE(x)

 

That is not how Do..While works, Rich. The following is how one might implement @Asmusr’s while():

100 REM ...part of program that manipulates X
    .
    .
    .
500 IF X=0 THEN 600         ! WHILE condition
510 REM ...WHILE true part
    .
    .
    .
590 GOTO 500
600 REM ...remainder of program (WHILE false part)

...lee

[RXB]

How is mine any different you just added more lines?

 

I just did not add in a GOTO that IF X=SOMETHING THEN SUBROUTINE

 

40 IF X=0 THEN CALL DOWHILE :: GOTO 40 ELSE 50

50 ....

 

 

1000 SUB DOWHILE(X)

 

 

1010 SUBEND

 

What exactly did I get wrong?

 

Also you could drop the ELSE 50 and would still work.

 

Anyway why do we need DO WHILE when we already have exactly what it does?

It is like putting a cup holder on your your cup holder..not really needed.

Edited September 10, 2018 by RXB

[+Ksarul]

The Geneve does have DO WHILE in ABASIC. . .

[1980gamer]

I wanted one of those... Or the TI99/8A

[+TheBF]

 

Anyway why do we need DO WHILE when we already have exactly what it does?

It is like putting a cup holder on your your cup holder..not really needed.

 

You are correct. You don't need it. 9900 Assembly language does not have structured loops... well... except in Forth assembler. :-)

 

But all of these things came out of the development of structured programming. It was felt by the experts like Dijkstra and Wirth that structuring things would get "spaghetti code" under control.

Maintaining commercial programs is a bigger expense than writing the code. It goes on for years.

Code that jumps all over the place gets hard to understand from the text of the program for the maintainer and is harder to modify.

 

So the structures that were common made you keep your loops localized.

FOR NEXT is one such structured loop in BASIC but you don't need it.

 

I remember that structured programming ticked off some people back in the day. They saw it as inefficient.

 

Dijkstra was clear on what he thought:

"It is practically impossible to teach good programming to students that have had a prior exposure to BASIC:

as potential programmers they are mentally mutilated beyond hope of regeneration"

 

He was apparently rather opinionated.

[RXB]

People do not think like Forth (Stack thinking) as you have to force yourself to thinking like a Computer stack, it does not come naturally.

Quantum computers do behave more like how our minds work.

 

Not Binary but multiple states.

[+TheBF]

People do not think like Forth (Stack thinking) as you have to force yourself to thinking like a Computer stack, it does not come naturally.

Quantum computers do behave more like how our minds work.

 

Not Binary but multiple states.

 

True. Stack machines take some practice to get use to.

 

I was actually thinking about the dawn of structured programming with languages like Algol68, Pascal, and C.

 

Forth used these same ideas probably (I don't know for certain) because it comes from the late 60s/early 70s time frame like these other old languages.

[senior_falcon]

All the discussion about DO WHILE led me to an interesting discovery involving FOR/NEXT. Usually FOR/NEXT is simply used as a counter, something like this:

10 FOR I=1 TO 10::PRINT I;SQR(I)::NEXT I

But XB really lets you bend the rules in a FOR/NEXT loop.

 

Here is a simple XB program:

1 J=3

2 J=J*-1.2345 :: PRINT J

3 IF J<=10 THEN 2

Here is an equivalent program done as a FOR/NEXT loop:

10 J=3

20 FOR J=J TO 10 STEP 1E-99

30 J=J*-1.2345 :: PRINT J

40 NEXT J

Here the FOR part of the loop doesn't do anything except set a limit of 10; when J is greater than 10 the program exits the loop. It is perfectly legal to change the value of J when in the loop. You cannot use STEP 0, but STEP 1E-99 does the same thing.

Interestingly, this executes a little faster than than the more normal code in lines 1-3.

Edited September 21, 2018 by senior_falcon

[+TheBF]

 

All the discussion about DO WHILE led me to an interesting discovery involving FOR/NEXT. Usually FOR/NEXT is simply used as a counter, something like this:

10 FOR I=1 TO 10::PRINT I;SQR(I)::NEXT I

But XB really lets you bend the rules in a FOR/NEXT loop.

 

Here is a simple XB program:

1 J=3

2 J=J*-1.2345 :: PRINT J

3 IF J<=10 THEN 2

Here is an equivalent program done as a FOR/NEXT loop:

10 J=3

20 FOR J=J TO 10 STEP 1E-99

30 J=J*-1.2345 :: PRINT J

40 NEXT J

Here the FOR part of the loop doesn't do anything except set a limit of 10; when J is greater than 10 the program exits the loop. It is perfectly legal to change the value of J when in the loop. You cannot use STEP 0, but STEP 1E-99 does the same thing.

Interestingly, this executes a little faster than than the more normal code in lines 1-3.

 

 

So this is potentially a faster infinite loop than GOTO ?

[senior_falcon]

 

So this is potentially a faster infinite loop than GOTO ?

Yeah, but not much:

10 J=0::I=.00001

20 J=J+I

30 IF J<10 THEN 20

Run for 1 minute and J=.05424 In TI BASIC J=.07037 - 30% faster than XB!

10 J=0::I=.00001

20 FOR J=J TO 10 STEP 1E-99

30 J=J+I

40 NEXT J

Run for 1 minute and J=.05977 In TI BASIC J=.08013 - 34% faster than XB!

So in this ultra simple loop that just adds one number there is a 10% speed increase. In a real loop that actually does something, I doubt you would notice any improvement.

(edit) The way I set this up you might think this is a normal FOR/NEXT loop with a step of .00001. That is not what is being tested. The point of this is to find out whether there is a speed difference between IF J<10 THEN 20 and NEXT J with a limit of 10 and a step of 0. J=J+I is just a simple way to find out how many loops are done in a minute. In the real world, J=J+I would be replaced with something useful using HCHARs, VCHARS, arithmetic operations, etc. and the loop would continue until J was greater than 10

Edited September 24, 2018 by senior_falcon

[1980gamer]

Just curious, does this speed increase hold up when complied?

 

I am working on something right now that has a bunch of looping, anything I can squeeze out of this would help the game.

 

Some of the time, I am actually using sound to slow the loop...but at other times....I need as much performance as I can get!

[+Lee Stewart]

Just curious, does this speed increase hold up when complied?

 

I am working on something right now that has a bunch of looping, anything I can squeeze out of this would help the game.

 

Some of the time, I am actually using sound to slow the loop...but at other times....I need as much performance as I can get!

 

XB only uses floating point numbers. The compiled version can only use integers. Without reading Harry’s manual, I do not know what happens with .00001 and 1E-99, but I suspect they are both truncated to 0, which would result in infinite loops in both cases.

 

...lee

[senior_falcon]

I ran some further tests with this technique in TI BASIC and posted the numbers above in post #18.

To answer Gene's question, I ran a simple test that does indeed show a slight increase in speed with this technique:

10 FOR I=0 TO 30000 STEP 0 (test in XB with 1E-99)

20 I=I+1

30 NEXT I

40 PRINT I

This takes 17 seconds to complete when compiled

The equivalent code is:

20 I=I+1

30 IF I<30001 THEN 20

40 PRINT I

This takes 20 seconds to complete when compiled. (This is about 16x faster than when running in XB)

So there is some potential for increasing speed by around 20%, but your loop undoubtedly does more than just add 2 numbers. When you figure in all the instructions in the loop, that 20% speed increase will shrink to 1 or 2%.

Writing tighter code is the best way to speed things up. Italian cuisine is best when served on a plate, not in a program!

Lee wrote: I do not know what happens with .00001 and 1E-99, but I suspect they are both truncated to 0

The compiler is not that clever. The decimal point will crash it and 1E-99 becomes DATA 1E-99 which the assembler would not like.

[RXB]

 

XB only uses floating point numbers. The compiled version can only use integers. Without reading Harry’s manual, I do not know what happens with .00001 and 1E-99, but I suspect they are both truncated to 0, which would result in infinite loops in both cases.

 

...lee

100% correct. XB does use Floating Point way to much when it should not do so.

Why I removed RXB normal Assembly Floating Point Random Number Generator and replaced it with the GPL Random Number Generator.

 

Floating Point is insanely slow for a Language to use all the time. A better approach would be only use Floating Point when needed, otherwise use Integer.