Some string manipulation routines

We're glad you came by, but you might find what you're looking for elsewhere. TI-Basic Developer is not the site it once was. While its information on commands and other calculator features remains almost second-to-none, its forum, archives, and even hosting service, Wikidot, have been decaying for years. The calculator community would love to see what you're working on, or help you in your next coding adventure, but TI-Basic Developer is no longer the place to do it. Instead, you should head over to Cemetech (primarily American) or TI-Planet (primarily international). Both are active, well-established forums with their own archives, chatrooms, reference material, and abundant coding tools and resources. We'll see you there, we hope.

Forum Attachments

Some string manipulation routines

Rigel314 26 Aug 2009 03:50

I am writing a game based on Puzzle Frenzy. It is almost pure basic, it uses Exec to fill and restore the screen, and it also depends on an ASM program called drawstr.
I have elected to store all levels as strings.
Every level's string can be up to 60 characters, representing 10 columns of 6 rows.
It stores levels by column. Each column must be complete, so the length is divisible by 6.
Level 2's string looks like: "002300003200003200", it represents:

000
000
233
322
000
000

The game creates pictures at run-time and displays them according to the level string.
I need a function that takes a level string as an input and moves all "0" characters, in a row, to the end of the row and returns the new level string.
I also need a function that takes a level string and replaces all 3 or more of the same number in a row, or column, with "0"
I have working functions for both, but they are very slow.
For an average-sized level, each of these functions has about a 5 second calculation time.
The game is playable, but no one would ever want to wait at least 10 seconds per move (both functions have to run at least once per move.)

If it matters, I'm using a TI-89 Titanium: OS version 3.10, and Hardware version 3.

I guess I'm asking for algorithmic optimization help. Maybe this goes on the optimization challenges page.
If by some very unlikely event that no one is able to help me I will just use these inefficient routines and write this game in C. I wanted to try to push the limits of TIBasic, like I've been encouraged to do, but I'll need some help, not being as good as I thought after discovering this site.

My "0" moving function:

lvgrav(x)
Func
Local  t,z,xy,c,y,s,e,yx
""»yx
For  z,1,6
 ""»y
 For  t,z,dim(x),6
  y&mid(x,t,1)»y
 EndFor
 ""»s
 ""»c
 dim(y)»xy
 For  t,1,xy
  mid(y,t,1)»e
  If  e"0"
   s&e»s
  If  e="0"
   c&"0"»c
 EndFor
 yx&s&c»yx
EndFor
""»y
For  z,1,dim(x)/6
 For  t,z,dim(x),xy
  y&mid(yx,t,1)»y
 EndFor
EndFor
Return  y
EndFunc

My three-in-a-row function:

mvcalc(x)
Func
Local  z,t,ul,c,e,y,f,s,yx,rplcchr
Define  rplcchr(sstr,enum,schr)=Func
Return  mid(sstr,1,enum-1)&schr&mid(sstr,enum+dim(schr),dim(sstr)-enum)
EndFunc
x»y
dim(x)»ul
For  t,1,ul,6
 mid(x,t,6)»f
 ""»e
 If  inString(f,"111")0
  rplcchr(y,t+inString(f,"111")-1,"000")»y
 If  inString(f,"222")0
  rplcchr(y,t+inString(f,"222")-1,"000")»y
 If  inString(f,"333")0
  rplcchr(y,t+inString(f,"333")-1,"000")»y
 If  inString(f,"444")0
  rplcchr(y,t+inString(f,"444")-1,"000")»y
 If  inString(f,"555")0
  rplcchr(y,t+inString(f,"555")-1,"000")»y
 If  inString(f,"1111")0
  rplcchr(y,t+inString(f,"1111")-1,"0000")»y
 If  inString(f,"2222")0
  rplcchr(y,t+inString(f,"2222")-1,"0000")»y
 If  inString(f,"3333")0
  rplcchr(y,t+inString(f,"3333")-1,"0000")»y
 If  inString(f,"4444")0
  rplcchr(y,t+inString(f,"4444")-1,"0000")»y
 If  inString(f,"5555")0
  rplcchr(y,t+inString(f,"5555")-1,"0000")»y
 If  inString(f,"11111")0
  rplcchr(y,t+inString(f,"11111")-1,"00000")»y
 If  inString(f,"22222")0
  rplcchr(y,t+inString(f,"22222")-1,"00000")»y
 If  inString(f,"33333")0
  rplcchr(y,t+inString(f,"33333")-1,"00000")»y
 If  inString(f,"44444")0
  rplcchr(y,t+inString(f,"44444")-1,"00000")»y
 If  inString(f,"55555")0
  rplcchr(y,t+inString(f,"55555")-1,"00000")»y
 If  f="111111"
  rplcchr(y,t,"000000")»y
 If  f="222222"
  rplcchr(y,t,"000000")»y
 If  f="333333"
  rplcchr(y,t,"000000")»y
 If  f="444444"
  rplcchr(y,t,"000000")»y
 If  f="555555"
  rplcchr(y,t,"000000")»y
EndFor

For  t,1,6
 ""»f
 For  z,t,ul,6
  f&mid(x,z,1)»f
 EndFor
 If inString(f,"111")0 Then
  For  z,0,2
   rplcchr(y,t+6*z+6*(inString(f,"111")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"222")0 Then
  For  z,0,2
   rplcchr(y,t+6*z+6*(inString(f,"222")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"333")0 Then
  For  z,0,2
   rplcchr(y,t+6*z+6*(inString(f,"333")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"444")0 Then
  For  z,0,2
   rplcchr(y,t+6*z+6*(inString(f,"444")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"555")0 Then
  For  z,0,2
   rplcchr(y,t+6*z+6*(inString(f,"555")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"1111")0 Then
  For  z,0,3
   rplcchr(y,t+6*z+6*(inString(f,"1111")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"2222")0 Then
  For  z,0,3
   rplcchr(y,t+6*z+6*(inString(f,"2222")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"3333")0 Then
  For  z,0,3
   rplcchr(y,t+6*z+6*(inString(f,"3333")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"4444")0 Then
  For  z,0,3
   rplcchr(y,t+6*z+6*(inString(f,"4444")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"5555")0 Then
  For  z,0,3
   rplcchr(y,t+6*z+6*(inString(f,"5555")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"11111")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"11111")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"22222")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"22222")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"33333")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"33333")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"44444")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"44444")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"55555")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"55555")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"111111")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"111111")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"222222")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"222222")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"333333")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"333333")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"444444")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"444444")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"555555")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"555555")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"1111111")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"1111111")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"2222222")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"2222222")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"3333333")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"3333333")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"4444444")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"4444444")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"5555555")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"5555555")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"11111111")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"11111111")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"22222222")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"22222222")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"33333333")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"33333333")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"44444444")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"44444444")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"55555555")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"55555555")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"111111111")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"111111111")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"222222222")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"222222222")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"333333333")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"333333333")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"444444444")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"444444444")-1),"0")»y
  EndFor
 EndIf
 If inString(f,"555555555")0 Then
  For  z,0,4
   rplcchr(y,t+6*z+6*(inString(f,"555555555")-1),"0")»y
  EndFor
 EndIf
 If f="1111111111" Then
  For  z,0,3
   rplcchr(y,t+6*z+6*(inString(f,"111111111")-1),"0")»y
  EndFor
 EndIf
 If f="2222222222" Then
  For  z,0,3
   rplcchr(y,t+6*z+6*(inString(f,"2222222222")-1),"0")»y
  EndFor
 EndIf
 If f="3333333333" Then
  For  z,0,3
   rplcchr(y,t+6*z+6*(inString(f,"3333333333")-1),"0")»y
  EndFor
 EndIf
 If f="4444444444" Then
  For  z,0,3
   rplcchr(y,t+6*z+6*(inString(f,"4444444444")-1),"0")»y
  EndFor
 EndIf
 If f="5555555555" Then
  For  z,0,3
   rplcchr(y,t+6*z+6*(inString(f,"5555555555")-1),"0")»y
  EndFor
 EndIf
EndFor

Return  y
EndFunc

Re: Some string manipulation routines

DarkerLine 26 Aug 2009 19:50

Okay. Take a deep breath. Now rewrite the program to store things as a matrix instead of a string (or maybe a list of strings. Or something. Experiment!). Also, treating all of those different cases separately instead of all at once is just… wrong.

Edit: here's a neat way to apply gravity to a single row, stored as a list (unfortunately, doesn't work in a function):

:row=0*row→z
:SortD z,row

For a matrix, the code would probably be like:

:For r,1,rowDim(mat)
: mat[r]→row
: row=0*row→z
: SortD z,row
: row→mat[r]
:EndFor

Edit: dammit, I don't think SortD is stable, so that isn't guaranteed to work. Oh well.

Last edited on 26 Aug 2009 20:04 by DarkerLine Show more