Author Topic: =={ Challenge }== Decompress String  (Read 11411 times)

0 Members and 1 Guest are viewing this topic.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
=={ Challenge }== Decompress String
« on: August 29, 2014, 04:38:49 AM »
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.
« Last Edit: August 29, 2014, 05:39:46 AM by irneb »
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

roy_043

  • Water Moccasin
  • Posts: 1895
  • BricsCAD 18
Re: =={ Challenge }== Decompress String
« Reply #1 on: August 29, 2014, 05:13:56 AM »
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

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: =={ Challenge }== Decompress String
« Reply #2 on: August 29, 2014, 05:17:51 AM »
Design query :
  • assume the string is not empty and contains printable characters.
  • Assume the first element is not numeric.

 :|
« Last Edit: August 29, 2014, 05:22:30 AM by Kerry »
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: =={ Challenge }== Decompress String
« Reply #3 on: August 29, 2014, 05:20:47 AM »
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  :|
« Last Edit: August 29, 2014, 05:24:27 AM by Kerry »
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

roy_043

  • Water Moccasin
  • Posts: 1895
  • BricsCAD 18
Re: =={ Challenge }== Decompress String
« Reply #4 on: August 29, 2014, 05:31:17 AM »
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

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: =={ Challenge }== Decompress String
« Reply #5 on: August 29, 2014, 05:33:36 AM »
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?
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: =={ Challenge }== Decompress String
« Reply #6 on: August 29, 2014, 05:34:17 AM »
< .. >

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.
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: =={ Challenge }== Decompress String
« Reply #7 on: August 29, 2014, 05:37:30 AM »
As some more samples to show these questions:
Code: [Select]
_$ (Decompress "")
""
_$ (Decompress "6")
""
_$ (Decompress "3a2b")
"aab"
_$ (Decompress "a2b")
"aab"
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: =={ Challenge }== Decompress String
« Reply #8 on: August 29, 2014, 05:37:56 AM »
< ..>
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.
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: =={ Challenge }== Decompress String
« Reply #9 on: August 29, 2014, 05:41:14 AM »

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


So, no A-Z ?
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: =={ Challenge }== Decompress String
« Reply #10 on: August 29, 2014, 05:45:37 AM »

  • 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.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

roy_043

  • Water Moccasin
  • Posts: 1895
  • BricsCAD 18
Re: =={ Challenge }== Decompress String
« Reply #11 on: August 29, 2014, 05:46:38 AM »
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

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: =={ Challenge }== Decompress String
« Reply #12 on: August 29, 2014, 05:50:11 AM »


Ahhh, I see you've changed the 'specs' to clarify ...
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

roy_043

  • Water Moccasin
  • Posts: 1895
  • BricsCAD 18
Re: =={ Challenge }== Decompress String
« Reply #13 on: August 29, 2014, 05:53:06 AM »
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

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: =={ Challenge }== Decompress String
« Reply #14 on: August 29, 2014, 06:04:02 AM »
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))
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.