Reversing a String Efficiently?

[meishe91]

So, first off. Brand new to the site, loving what I have seen so far here Just wanted to say that in my first thread. Ok, now to my question.

I'm using a TI-84+ and have been working on a way to make a decimal to binary program (I know it has been done, but its just something that I'm trying to work out on my own. Yay motivation ). I have a theory on how to complete this but the only issue I can't think of a way to program is an efficient way of reversing the variables inside a String. Like say you have "1234" stored to Str1, what I'm asking is if there is a way of restoring the information in that variable to either the same one or another one (so instead of "1234" being stored to Str1 it would be "4321"). I'm sorry if that doesn't make sense, I can try to rephrase it.
I have used the search engine and the routine pages and couldn't find anything. I am sorry if it is out there and I simply missed it.

Thanks for any help

[meishe91]

Now that is all that I have to do to make this program workable really. Everything works fine, you just have to read the final output backwards. Another quick question though, though I wouldn't be surprised if it has been asked before. How this program is working really is that I have "1" stored to Str1 and 0 to Str2 and " " (a space) stored to Str3 (the final outputed String) and I'm adding the strings to make the appropriate binary code. What I'm curious about is if there is a reason that when I had "" (no space) stored to Str3 (instead of the space) it wouldn't work and I would get a Invalid Dimentions Error. I just don't really understand why it is happening. (Its not a huge deal, it just leaves an extra space at the beginning right now, but if I figure out that String reverse thing it won't be an issue.)

Again, thanks for anything.

[thornahawk]

Empty strings are not supported in TI-BASIC, so you usually need a dummy character to start with. sub( is the function to use to get rid of the space or whatever other dummy string you use.

thornahawk

[meishe91]

[Weregoose]

Welcome to United-TI, Meishe91! :)

Here's how I would go about it:

Supposing you have a string in Str1 that you want to reverse, you'll first want to store a separate string at the start of your program with nothing but a buffer character, (e.g., a space, question mark, or whatever). This is because, as you've discovered, the interpreter doesn't like working with empty strings (and that's really the only reason here that's worth knowing).

Then, for X starting at 1 and incrementally going towards the length( of Str1, you'll want to sub( out the (length(Str1)-X+1)^th character from the input string and add it to the tail end of the buffer string.

So, for the well-famed "Hello World", the algorithm would work as follows:

´X´´Substring´´´´Buffer String
´1´´Hello World´´?d
´2´´Hello World´´?dl
´3´´Hello World´´?dlr
´4´´Hello World´´?dlro
´5´´Hello World´´?dlroW
´6´´Hello░World´´?dlroW░
´7´´Hello World´´?dlroW o
´8´´Hello World´´?dlroW ol
´9´´Hello World´´?dlroW oll
10´´Hello World´´?dlroW olle
11´´Hello World´´?dlroW olleH

After the loop, you may use sub( again to remove the "dummy" first character in the output string.

If you're brave, there is another approach which uses only one string, and which effectively concatenates the initial string onto itself in reverse order, and this requires use of the sub( command at the end to extract the entire latter half of the output.

As a final challenge: if you have only one line inside of the For( loop (did I forget to mention that you should use one of these?), you may not need a second variable at all, but instead just keep using Ans in a clever way.

Go forth, and make code.

[meishe91]

[thornahawk]

Essentially, this "brave approach" Goose is speaking of uses the input string as the dummy instead of a single character; with that example above, you end up with something like "Hello WorldlroW olleH" before applying sub( to it.

thornahawk

[meishe91]

[thornahawk]

The program for string reversal would work like that, but there's a version hidden somewhere in the forums that hinges on the unique properties of Ans.

As for decimal to binary, witness the following:

[Weregoose]

Edit: I submitted this and then went back and saw your edits at post #6 for the first time. This was not at all a response to your programs nor was it an endeavor to show how to do them differently. And yet, your code does give me further confidence in your merits as a programmer.

Disclaimer: [2nd] [ENTER] on the home screen will probably be useful throughout this post. I don't want to be accountable for any repetitive stress injuries.

Start out with 210 as the input. This is even. Divide it by two to get 105, which is an odd number. Divide that by two to get 52.5 – fractional part notwithstanding, we'll call this "even". Continuing along through 26.25, 13.125, etc., all the way down until no digits linger to the left of the decimal point, the parities will eventually be recorded as: even, odd, even, even, odd, even, odd, odd.

All odd numbers leave a remainder of 1 when divided by two. All even numbers leave a remainder of 0 when divided by two. If we make these substitutions, reverse the order, and then condense the digits, it becomes 11010010. This is exactly the binary representation of our original quantity.

Rather than recursively dividing by two, we can use seq( to rebuild each step individually by dividing by the appropriate power of two. This translates to seq(210/2^(X-1),X,1,B) (for an arbitrary number of bits). We know that we'll have eight bits this time, so we'll use 8→B for now.

It's noteworthy that seq( allows for a negative increment – as each step no longer depends on the one right before it, we can obtain the same line of results coming in from the opposite direction. This saves us from having to reposition the final digits later:

8→B:seq(210/2^(X-1),X,B,1,-1

Compare with the original:

8→B:seq(210/2^(X-1),X,1,B

To determine odd-or-even, we only need to address the integer parts, so we'll use int( or iPart( on the sequence itself.

Come to think of it, let's filter as much out of that seq( command as possible in the meantime.

8→B:int(210/2^seq(X-1,X,B,1,-1

As stated earlier, a number that leaves a remainder when divided by two must be an odd number. So, we'll first use that operation on our list (by multiplying it by one-half) and then take the fractional parts for evaluation:

8→B:fPart(.5int(210/2^seq(X-1,X,B,1,-1

Here we are given a list of two different numbers. We could do Ans≠0 to turn all the nonzeros into ones, or we could simply double all the values inside the list. One-half will essentially become one, and zero will remain zero.

8→B:2fPart(.5int(210/2^seq(X-1,X,B,1,-1

So, that works. But now for the small matter of generalizing B...

It's always going to equal the exponent of the smallest power of two that can fully contain our input (N) – anything less, and we'd be losing digits; anything more, and we'd be tacking on leading zeros. To avoid this kind of loss/redundancy, we'd have to solve 2^B = N beforehand.

Skipping the math lesson, the correct number of digits is given by 1+int(log(N)/log(2)). However, because of issues like this one, we really ought to make that 1+int(round(log(N)/log(2))) instead. Using that as our B, the sequence should maintain the correct length.

This...

1+int(round(log(N)/log(2→B
2fPart(.5int(N/2^seq(X-1,X,B,1,-1

...is not half bad. But we can toy with it to improve it a little.

We'll begin by shifting X's start and end values by negative one, and then compensating for the difference in the first argument:

1+int(round(log(N)/log(2→B
2fPart(.5int(N/2^seq(X,X,B-1,0,-1

Thus we have the same powers of two without explicitly subtracting one each time.

But we see that B, having already been given a plus-one term in the top line, is now losing the same amount in line two. Intuitively, this tell us that this dissociative addend/subtend can be omitted from both lines. But if you want an algebraic excuse, then replace B with its expression and simplify – the ones will simply cancel each other out.

int(round(log(N)/log(2→B
2fPart(.5int(N/2^seq(X,X,B,0,-1

An obvious change here is to remove the →B and use Ans in place of the second B, but I'm leaving it in for your purposes. Think you can expand it into a For( loop and make a string out of it? I'm pretty sure you're capable enough.

–Goose

[meishe91]

[thornahawk]

[Xeda112358]

Here is a code I have made. It doesn't do the string reverse thing, but you can add that. Also, instead of a prompt, use something like this:

10:prgmDECTOBIN

10 is the number to convert. This program makes use of "the unique properties of Ans." The string is also stored in Ans at the end of the program.

PROGRAM:DECTOBIN
:Ans→B
:iPart(log(Ans)/log(2→C
:"0→Str1
:For(A,C,0,-1
:"0
:If B≥2^A
:Then
:B-2^A→B
:"1
:End
:Str1+Ans→Str1
:End
:sub(Str1,2,length(Str1)-1

[DarkerLine]

If the only reason you want to reverse a string is to make the output list the digits in a correct order, there's an easier way to do it. Replace Str1+Ans→Str1 with Ans+Str1→Str1 -- this way, the digits are added to the front, instead of to the back. At the end, you'll have to replace sub(Str1,2,length(Str1)-1 with sub(Str1,1,length(Str1)-1 because now, you want to remove the last character instead of the first.

[meishe91]

[thornahawk]

"Binary to Decimal Program"

- You might appreciate this hint. :)

thornahawk

[kinkoa]

hmm this is cool

[meishe91]

[thornahawk]

[meishe91]