Topic: =={ Challenge }== Decompress String

[irneb]

Since the previous FizzBuzz challenge was seen as "nice", I thought I'd add another one.

Here's the request: The compression algorithm created a string where each numeral digit means the uncompressed string preceding it is repeated that many times. You must write the decompress function. Assume the compressed string can only contain characters 0 through 9 and a through z, while the decompressed can only contain a through z.

E.g.

Code: [Select]

_$ (Decompress "ab2c3")
"ababcababcababc"
_$ (Decompress "ab4c3d2")
"ababababcababababcababababcdababababcababababcababababcd"
Edited to add content range of string.

[roy_043]

My first solution:

Code - Auto/Visual Lisp: [Select]

1. (defun Roy_Decompress (str / out tmp)
2.   (setq out "")
3.   (foreach int (vl-string->list str)
4.     (cond
5.       ((= int 48) ; 0
6.         (setq out "")
7.       )
8.       ((= int 49) ; 1
9.         out
10.       )
11.       ((<= 50 int 57) ; 2-9
12.         (setq tmp out)
13.         (repeat (- int 49)
14.           (setq out (strcat out tmp))
15.         )
16.       )
17.       (T
18.         (setq out (strcat out (chr int)))
19.       )
20.     )
21.   )
22. )

[Kerry]

Design query :

• assume the string is not empty and contains printable characters.
• Assume the first element is not numeric.

 

[Kerry]

Design query :
does a string "A23"  mean repeat "A" 23 times or repeat "A"  2 times then 3 times ??

I assume  repeat "A"  2 times then 3 times 

[roy_043]

I assume  repeat "A"  2 times then 3 times 

That has been my assumption. And I have assumed a non-empty string.

Another interesting issue: What if the input string does not end in a digit?

[irneb]

Design query :

• assume the string is not empty and contains printable characters.
• Assume the first element is not numeric.

 

• Assume string only contains characters of 0-9 and a-z
• No, first element could be numeric as well ... does it make any difference in the result?

Design query :
does a string "A23"  mean repeat "A" 23 times or repeat "A"  2 times then 3 times ??

I assume  repeat "A"  2 times then 3 times 

Your assumption is correct:

...each numeral digit means ...

Another interesting issue: What if the input string does not end in a digit?

Really? Please explain?

[Kerry]

< .. >

Another interesting issue: What if the input string does not end in a digit?

I had assumed the last element would just be appended to the result string.

[irneb]

As some more samples to show these questions:

Code: [Select]

_$ (Decompress "")
""
_$ (Decompress "6")
""
_$ (Decompress "3a2b")
"aab"
_$ (Decompress "a2b")
"aab"

[Kerry]

< ..>
No, first element could be numeric as well ... does it make any difference in the result?]
< ..>

Only in so much as the possibility must be allowed for.

[Kerry]

• Assume string only contains characters of 0-9 and a-z

So, no A-Z ?

[irneb]

• Assume string only contains characters of 0-9 and a-z

So, no A-Z ?

If you really want to you can do those too, but it's not a big issue. Actually the way I've written mine means everything except for 0-9 will be possible in the result.

[roy_043]

Another interesting issue: What if the input string does not end in a digit?

Really? Please explain?

Code: [Select]

_$ (Decompress "a2b")
"aab"

So (Decompress "a2b") should return the same result as (Decompress "a2b1").
Seems interesting enough to me...

[Kerry]

Ahhh, I see you've changed the 'specs' to clarify ...

[roy_043]

Revised code to account for empty string input.

Code - Auto/Visual Lisp: [Select]

1. (defun Roy_Decompress_2 (str / out tmp)
2.   (setq out "")
3.   (foreach int (vl-string->list str)
4.     (cond
5.       ((<= 50 int 57) ; 2-9
6.         (setq tmp out)
7.         (repeat (- int 49)
8.           (setq out (strcat out tmp))
9.         )
10.       )
11.       ((= int 48) ; 0
12.         (setq out "")
13.       )
14.       ((/= int 49) ; 1
15.         (setq out (strcat out (chr int)))
16.       )
17.     )
18.   )
19.   out
20. )

[irneb]

Revised code to account for empty string input.

Awesome! Very close to mine, most notable difference is mine works with lists instead of strings.

Code - Auto/Visual Lisp: [Select]

1. (defun Decompress (string / result temp)
2.   (setq string (vl-string->list string))
3.   (while string
4.     (cond ((= (car string) 48) (setq result nil))
5.           ((< 48 (car string) 58)
6.            (setq temp result)
7.            (repeat (- (car string) 49)
8.              (setq result (append result temp))))
9.           ((setq result (append result (list (car string))))))
10.     (setq string (cdr string)))
11.   (vl-list->string result))