Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# String compression

ramakrishna ranga
Greenhorn
Posts: 3
How to compress and decompress String like

compress:
Input = AAAABBSXXZZZZ
Output = 4A2BS2X4Z

decompress:
Input = 4A2BS2X4Z
Output=AAAABBSXXZZZZ

Henry Wong
author
Marshal
Posts: 21766
85
Well, what have you done so far? And what problems are you having / seeing?

As far as homework assignment goes, this looks like one of the easier ones.

Henry

Rich Nelson
Greenhorn
Posts: 15
I have the exact same assignment. We're not allowed to use loops though, and the extent of what we ARE allowed to do is really just if statements and switch cases.

Basically, we need to input something like =6-=10+=9j=24\$ where = is the delimiter. The output should be:

------++++++++++jjjjjjjjj\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$

Edit: I guess I just need to know where to start. I honestly have no idea.

Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
Hey, welcome to the ranch, twice! This place works best when you take a shot at something and show us what you have. That way we can see exactly what parts you figured out and where you are stuck.

Say you were pulling cards off a deck and you couldn't see ahead. If you pulled a card that didn't match the previous one, what would you write down? If it did match the previous one, what would you write? See if you can write that logic down in "structured English" like

So first step: no Java, just explain how you'd count cards.

Nicholas Jordan
Ranch Hand
Posts: 1282
We're not allowed to use loops though

Well how do we do it then ? The approach Stan takes is called Tiny, and it grows like the Chia pet you see on Television. The loop approach was described by Alan Turing awhile back while working for a while for the British Government. The other approach, called Duff's device just lets the compiler do the unrolling for you. You still code a loop - note Stan's simplified plain language problem statement has the word while in it.

In computer science, a while is a loop: No other way. You can unroll the loop, but then by Alan's description of the problem, the machine then has to be as big as the problem is. So if you have a way to read the numbers into a machine readable number,......

You do have that, don't you ?

[ September 22, 2007: Message edited by: Nicholas Jordan ]

Rich Nelson
Greenhorn
Posts: 15
That's a good hint, I'll try it out . Thanks.

Rob Spoor
Sheriff
Posts: 20709
68
Well technically you could do it without loops but using recursion instead:

Using this technique just to avoid using loops is quite bad though. If possible, loops should always get the preference, because with recursion all method local variables get put on the stack for each call.

Henry Wong
author
Marshal
Posts: 21766
85
Using this technique just to avoid using loops is quite bad though. If possible, loops should always get the preference, because with recursion all method local variables get put on the stack for each call.

Also keep in mind that someone who hasn't learned loops yet, is unlikely to know what recursion is.

Henry
[ September 23, 2007: Message edited by: Henry Wong ]

Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
Using recursion to avoid loops sounds like a bar bet to me. Possible, but it might get you punched in the schnoz. I sometimes wish for a compiler that would actually punch the coder in the beezer for something like that.

BTW: The example given above =6-=10+=9j=24\$ where = is the delimiter is a bit ambiguous because it has either one or two digits of repeat count. How do you know how many digits to use? What if you were repeating 5s? =35a means what?

I made one of these in COBOL years ago where the minimum number of repeats to be worth escaping and the number of digits were both configurable. Our mainframe data tended to have repeating zeros and spaces and it paid off quite nicely in network time vs cpu time.
[ September 23, 2007: Message edited by: Stan James ]

Nicholas Jordan
Ranch Hand
Posts: 1282
Well, gee folks, OO sounds like a solution in search of problem to me. Using recursion to avoid loops sounds like what the instructor is intending the poster will do, but since I enjoy all-night hair pullers where I   really   figure out how to do it, you know, how the Krell would do it, this triggers a memory of my first approach to the problem:

1: Write and compile a file that has something along the lines of:

2: Open the file in the text editor and copy paste it over to the source code file.

It ran ! Isn't that a joy for the first time programmer ?

You should see stl vector/map add I wrote shortly after that, I stiill have it. Want to see it ?

[ to the Poster: Look up Towers of Hanoi - recursion is a loop ]
[ September 23, 2007: Message edited by: Nicholas Jordan ]

Pat Farrell
Rancher
Posts: 4678
7
I would think you could use a regex to identify repeats, and use length() on the specific match subsets. This would not be obvious, but could probably be smashed into working.

I'd be tempted to use a loop, but I rarely listen to the professors even when I was one.