1980gamer Posted September 8, 2018 Share Posted September 8, 2018 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. Quote Link to comment Share on other sites More sharing options...
RXB Posted September 8, 2018 Share Posted September 8, 2018 Is this XB? Quote Link to comment Share on other sites More sharing options...
1980gamer Posted September 8, 2018 Author Share Posted September 8, 2018 (edited) 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 Quote Link to comment Share on other sites More sharing options...
Asmusr Posted September 8, 2018 Share Posted September 8, 2018 Instead of a recursive function you could use a stack to keep track of which block to check next. Quote Link to comment Share on other sites More sharing options...
1980gamer Posted September 9, 2018 Author Share Posted September 9, 2018 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.. Quote Link to comment Share on other sites More sharing options...
Asmusr Posted September 9, 2018 Share Posted September 9, 2018 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) } } 1 Quote Link to comment Share on other sites More sharing options...
1980gamer Posted September 9, 2018 Author Share Posted September 9, 2018 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. Quote Link to comment Share on other sites More sharing options...
RXB Posted September 10, 2018 Share Posted September 10, 2018 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) Quote Link to comment Share on other sites More sharing options...
+Lee Stewart Posted September 10, 2018 Share Posted September 10, 2018 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 Quote Link to comment Share on other sites More sharing options...
RXB Posted September 10, 2018 Share Posted September 10, 2018 (edited) 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 Quote Link to comment Share on other sites More sharing options...
+Ksarul Posted September 18, 2018 Share Posted September 18, 2018 The Geneve does have DO WHILE in ABASIC. . . Quote Link to comment Share on other sites More sharing options...
1980gamer Posted September 18, 2018 Author Share Posted September 18, 2018 I wanted one of those... Or the TI99/8A Quote Link to comment Share on other sites More sharing options...
+TheBF Posted September 18, 2018 Share Posted September 18, 2018 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. 1 Quote Link to comment Share on other sites More sharing options...
RXB Posted September 18, 2018 Share Posted September 18, 2018 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. Quote Link to comment Share on other sites More sharing options...
+TheBF Posted September 18, 2018 Share Posted September 18, 2018 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. 1 Quote Link to comment Share on other sites More sharing options...
senior_falcon Posted September 21, 2018 Share Posted September 21, 2018 (edited) 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 4 Quote Link to comment Share on other sites More sharing options...
+TheBF Posted September 22, 2018 Share Posted September 22, 2018 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 ? 1 Quote Link to comment Share on other sites More sharing options...
senior_falcon Posted September 22, 2018 Share Posted September 22, 2018 (edited) 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 Quote Link to comment Share on other sites More sharing options...
1980gamer Posted September 23, 2018 Author Share Posted September 23, 2018 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! Quote Link to comment Share on other sites More sharing options...
+Lee Stewart Posted September 23, 2018 Share Posted September 23, 2018 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 1 Quote Link to comment Share on other sites More sharing options...
senior_falcon Posted September 23, 2018 Share Posted September 23, 2018 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. Quote Link to comment Share on other sites More sharing options...
RXB Posted September 23, 2018 Share Posted September 23, 2018 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. Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.