Author Topic: [challenge] A10 : Decode a run-length encoded list  (Read 446 times)

0 Members and 1 Guest are viewing this topic.

JohnK

  • Administrator
  • Needs a day job
  • Posts: 9947
[challenge] A10 : Decode a run-length encoded list
« on: January 03, 2022, 10:58:38 AM »
Happy new year and I hope the transition back to work is going good for everyone.
***
Using only AutoLisp, given a run-length code list, construct its uncompressed version.

Example:
(decode-rle-list '((4 A) B (2 C) (2 A) D (4 E))
> (a a a a b c c a a d e e e e)
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org

Stefan

  • Bull Frog
  • Posts: 288
Re: [challenge] A10 : Decode a run-length encoded list
« Reply #1 on: January 03, 2022, 11:12:27 AM »
Code - Auto/Visual Lisp: [Select]
  1. (defun decode-stef1 (l)
  2.   (apply
  3.    'append
  4.     (mapcar
  5.      '(lambda (x / l)
  6.         (if
  7.           (atom x)
  8.           (list x)
  9.           (repeat (car x)
  10.             (setq l (cons (cadr x) l))
  11.           )
  12.         )
  13.       )
  14.       l
  15.     )
  16.   )
  17. )
« Last Edit: January 03, 2022, 11:23:56 AM by Stefan »

JohnK

  • Administrator
  • Needs a day job
  • Posts: 9947
Re: [challenge] A10 : Decode a run-length encoded list
« Reply #2 on: January 03, 2022, 11:20:21 AM »
In my method I choose not to use a function that returns a list--like mapcar does--and construct a new list. I didn't choose that because I thought it would be faster but just to use a different method.

Code - Auto/Visual Lisp: [Select]
  1. (defun decode-rle-list-se7en (aList / naList)
  2.   (foreach x aList
  3.       (if (and (listp x) (> (length x) 0))
  4.         (repeat
  5.           (car x)
  6.           (set 'naList (cons (cadr x) naList)))
  7.         (set 'naList (cons x naList)))
  8.       )
  9.   (reverse naList)
  10.   )
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org

Stefan

  • Bull Frog
  • Posts: 288
Re: [challenge] A10 : Decode a run-length encoded list
« Reply #3 on: January 03, 2022, 11:22:16 AM »
Code - Auto/Visual Lisp: [Select]
  1. (defun decode-stef2 (l / r)
  2.   (while l
  3.     (if (atom (car l))
  4.       (setq r (cons (car l) r))
  5.       (repeat
  6.         (caar l)
  7.         (setq r (cons (cadar l) r))
  8.       )
  9.     )
  10.     (setq l (cdr l))
  11.   )
  12.   (reverse r)
  13. )
« Last Edit: January 03, 2022, 05:58:54 PM by Stefan »

Tharwat

  • Swamp Rat
  • Posts: 645
  • Hypersensitive
Re: [challenge] A10 : Decode a run-length encoded list
« Reply #4 on: January 03, 2022, 12:33:38 PM »
Code - Auto/Visual Lisp: [Select]
  1. (defun Decode:Tharwat ( lst / new )
  2.   (foreach itm (reverse lst)
  3.     (if (listp itm)
  4.       (repeat (car itm)
  5.         (setq new (cons (cadr itm) new))
  6.         )
  7.       (setq new (cons itm new))
  8.       )
  9.     )
  10.   new
  11.   )

ronjonp

  • Needs a day job
  • Posts: 7360
Re: [challenge] A10 : Decode a run-length encoded list
« Reply #5 on: January 03, 2022, 03:50:00 PM »
Code - Auto/Visual Lisp: [Select]
  1. (defun decode-rjp (l)
  2.   (defun _f (x / l)
  3.     (if (listp x)
  4.       (repeat (car x) (setq l (cons (cadr x) l)))
  5.       (list x)
  6.     )
  7.   )
  8.   (apply 'append (mapcar '_f l))
  9. )
  10.  
  11. (defun decode-rjp2 (l / a r)
  12.   (repeat (length l)
  13.     (setq a (car l))
  14.     (if (listp a)
  15.       (repeat (car a) (setq r (cons (cadr a) r)))
  16.       (setq r (cons  a r))
  17.     )
  18.     (setq l (cdr l))
  19.   )
  20.   (reverse r)
  21. )
  22.  
« Last Edit: January 03, 2022, 04:03:49 PM by ronjonp »

Windows 10 x64 - AutoCAD /C3D 2020

Custom Build PC

Lee Mac

  • Seagull
  • Posts: 12605
  • London, England
Re: [challenge] A10 : Decode a run-length encoded list
« Reply #6 on: January 03, 2022, 05:51:28 PM »
Code: [Select]
(decode-stef2 nil)

Lee Mac

  • Seagull
  • Posts: 12605
  • London, England
Re: [challenge] A10 : Decode a run-length encoded list
« Reply #7 on: January 03, 2022, 05:56:22 PM »
Another, recursive -
Code - Auto/Visual Lisp: [Select]
  1. (defun decode-LM1 ( l )
  2.     (cond
  3.         (   (not l) l)
  4.         (   (atom  (car  l)) (cons (car l) (decode-LM1 (cdr l))))
  5.         (   (zerop (caar l)) (decode-LM1 (cdr l)))
  6.         (   (cons  (cadar l) (decode-LM1 (cons (list (1- (caar l)) (cadar l)) (cdr l)))))
  7.     )
  8. )

Stefan

  • Bull Frog
  • Posts: 288
Re: [challenge] A10 : Decode a run-length encoded list
« Reply #8 on: January 03, 2022, 06:07:14 PM »
Code: [Select]
(decode-stef2 nil)
Noted and updated.



well20152016

  • Newt
  • Posts: 125
Re: [challenge] A10 : Decode a run-length encoded list
« Reply #9 on: January 03, 2022, 06:53:58 PM »
Code - Auto/Visual Lisp: [Select]
  1. (defun decode-rle-list (aList / l)
  2. (mapcar '(lambda (x )
  3.            (if(atom x)
  4.              (setq l (cons x l))
  5.              (repeat (car x)(setq l (cons (cadr x) l)))
  6.   )
  7.            )aList)
  8.   (reverse l)
  9.   )

Stefan

  • Bull Frog
  • Posts: 288
Re: [challenge] A10 : Decode a run-length encoded list
« Reply #10 on: January 04, 2022, 01:18:00 AM »
Code - Auto/Visual Lisp: [Select]
  1. (defun decode-stef3 (l / f g)
  2.   (defun f (l)
  3.     (if l
  4.       (if
  5.         (atom (car l))
  6.         (cons (car l) (f (cdr l)))
  7.         (g (caar l) (cadar l))
  8.       )
  9.     )
  10.   )
  11.   (defun g (n x)
  12.     (if
  13.       (zerop n)
  14.       (f (cdr l))
  15.       (cons x (g (1- n) x))
  16.     )
  17.   )
  18.   (f l)
  19. )

apricot125

  • Mosquito
  • Posts: 11
Re: [challenge] A10 : Decode a run-length encoded list
« Reply #11 on: January 04, 2022, 07:53:04 PM »
Code: [Select]
(defun decode (lst / ret x)
  (defun ** (alst / i)
    (if (= 1 (car alst))
        (list (cadr alst))
        (cons (cadr alst) (** (list (1- (car alst)) (cadr alst))))
    )
  )
  (setq ret '())
  (foreach x lst
    (if (atom x)
        (setq ret (append ret (list x)))
        (setq ret (append ret (**   x)))
    )
  )
)

JohnK

  • Administrator
  • Needs a day job
  • Posts: 9947
Re: [challenge] A10 : Decode a run-length encoded list
« Reply #12 on: January 07, 2022, 08:48:07 AM »
Benchmarks:
Code: [Select]
Elapsed milliseconds / relative speed for 65536 iteration(s):

    (DECODE:THARWAT ALIST)...................1062 / 1.88 <fastest>
    (DECODE-STEF2 ALIST).....................1110 / 1.80
    (DECODE-STEF3 ALIST).....................1235 / 1.62
    (DECODE-RLE-LIST-SE7EN ALIST)............1250 / 1.60
    (DECODE-RLE-LIST-WELL20152016 ALIST).....1359 / 1.47
    (DECODE-RJP2 ALIST)......................1375 / 1.45
    (DECODE-STEF1 ALIST).....................1547 / 1.29
    (DECODE-RJP ALIST).......................1640 / 1.22
    (DECODE-APRICOT ALIST)...................1734 / 1.15
    (DECODE-LM1 ALIST).......................2000 / 1.00 <slowest>
Code: [Select]
Elapsed milliseconds / relative speed for 65536 iteration(s):

    (DECODE:THARWAT ALIST)...................1063 / 1.85 <fastest>
    (DECODE-STEF2 ALIST).....................1093 / 1.80
    (DECODE-STEF3 ALIST).....................1172 / 1.68
    (DECODE-RJP2 ALIST)......................1188 / 1.66
    (DECODE-RLE-LIST-SE7EN ALIST)............1266 / 1.56
    (DECODE-RLE-LIST-WELL20152016 ALIST).....1312 / 1.50
    (DECODE-STEF1 ALIST).....................1531 / 1.29
    (DECODE-RJP ALIST).......................1562 / 1.26
    (DECODE-APRICOT ALIST)...................1640 / 1.20
    (DECODE-LM1 ALIST).......................1969 / 1.00 <slowest>

Code - Auto/Visual Lisp: [Select]
  1.   (defun decode-stef1 (l)
  2.     (apply
  3.       'append
  4.       (mapcar
  5.         '(lambda (x / l)
  6.            (if
  7.              (atom x)
  8.              (list x)
  9.              (repeat (car x)
  10.                      (setq l (cons (cadr x) l))
  11.                      )
  12.              )
  13.            )
  14.         l
  15.         )
  16.       )
  17.     )
  18.   (defun decode-rle-list-se7en (aList / naList)
  19.     (foreach x aList
  20.              (if (and (listp x) (> (length x) 0))
  21.                (repeat
  22.                  (car x)
  23.                  (set 'naList (cons (cadr x) naList)))
  24.                (set 'naList (cons x naList)))
  25.              )
  26.     (reverse naList)
  27.     )
  28.   (defun decode-stef2 (l / r)
  29.     (while l
  30.            (if (atom (car l))
  31.              (setq r (cons (car l) r))
  32.              (repeat
  33.                (caar l)
  34.                (setq r (cons (cadar l) r))
  35.                )
  36.              )
  37.            (setq l (cdr l))
  38.            )
  39.     (reverse r)
  40.     )
  41.   (defun Decode:Tharwat ( lst / new )
  42.     (foreach itm (reverse lst)
  43.              (if (listp itm)
  44.                (repeat (car itm)
  45.                        (setq new (cons (cadr itm) new))
  46.                        )
  47.                (setq new (cons itm new))
  48.                )
  49.              )
  50.     new
  51.     )
  52.  
  53.   (defun decode-rjp (l)
  54.     (defun _f (x / l)
  55.       (if (listp x)
  56.         (repeat (car x) (setq l (cons (cadr x) l)))
  57.         (list x)
  58.         )
  59.       )
  60.     (apply 'append (mapcar '_f l))
  61.     )
  62.  
  63.   (defun decode-rjp2 (l / a r)
  64.     (repeat (length l)
  65.             (setq a (car l))
  66.             (if (listp a)
  67.               (repeat (car a) (setq r (cons (cadr a) r)))
  68.               (setq r (cons  a r))
  69.               )
  70.             (setq l (cdr l))
  71.             )
  72.     (reverse r)
  73.     )
  74.   (defun decode-LM1 ( l )
  75.     (cond
  76.       (   (not l) l)
  77.       (   (atom  (car  l)) (cons (car l) (decode-LM1 (cdr l))))
  78.       (   (zerop (caar l)) (decode-LM1 (cdr l)))
  79.       (   (cons  (cadar l) (decode-LM1 (cons (list (1- (caar l)) (cadar l)) (cdr l)))))
  80.       )
  81.     )
  82.   (defun decode-rle-list-well20152016 (aList / l)
  83.     (mapcar '(lambda (x )
  84.                (if(atom x)
  85.                  (setq l (cons x l))
  86.                  (repeat (car x)(setq l (cons (cadr x) l)))
  87.                  )
  88.                )aList)
  89.     (reverse l)
  90.     )
  91.   (defun decode-stef3 (l / f g)
  92.     (defun f (l)
  93.       (if l
  94.         (if
  95.           (atom (car l))
  96.           (cons (car l) (f (cdr l)))
  97.           (g (caar l) (cadar l))
  98.           )
  99.         )
  100.       )
  101.     (defun g (n x)
  102.       (if
  103.         (zerop n)
  104.         (f (cdr l))
  105.         (cons x (g (1- n) x))
  106.         )
  107.       )
  108.     (f l)
  109.     )
  110.   (defun decode-apricot (lst / ret x)
  111.     (defun ** (alst / i)
  112.       (if (= 1 (car alst))
  113.         (list (cadr alst))
  114.         (cons (cadr alst) (** (list (1- (car alst)) (cadr alst))))
  115.         )
  116.       )
  117.     (setq ret '())
  118.     (foreach x lst
  119.              (if (atom x)
  120.                (setq ret (append ret (list x)))
  121.                (setq ret (append ret (**   x)))
  122.                )
  123.              )
  124.     )
  125.  
  126.   (setq aList '((4 A) B (2 C) (2 A) D (4 E)))
  127.   (benchmark
  128.     '(
  129.       (decode-rle-list-well20152016 aList)
  130.       (decode-stef3 aList)
  131.       (decode-apricot aList)
  132.       (decode-LM1 aList)
  133.       (decode-rjp2 aList)
  134.       (decode-rjp aList)
  135.       (Decode:Tharwat aList)
  136.       (decode-stef2 aList)
  137.       (decode-rle-list-se7en aList)
  138.       (decode-stef1 aList)
  139.       )
  140.     )
  141.   )
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org

bruno_vdh

  • Newt
  • Posts: 31
Re: [challenge] A10 : Decode a run-length encoded list
« Reply #13 on: January 12, 2022, 11:48:14 AM »
Hello,
For the game with repli see challenge A12  :wink:
http://www.theswamp.org/index.php?topic=57308.msg608109#msg608109

Code: [Select]
(defun decode-rle-list (l)
  (apply 'append (mapcar '(lambda (x) (if (atom x) (list x) (repli (cdr x) (car x)))) l)))

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1566
  • Moscow (Russia)
Re: [challenge] A10 : Decode a run-length encoded list
« Reply #14 on: January 20, 2022, 01:32:18 AM »
Code - Auto/Visual Lisp: [Select]
  1. (defun f (l / a)
  2.   (cond ((not l) l)
  3.         ((atom (car l)) (cons (car l) (f (cdr l))))
  4.         ((append (repeat (caar l) (setq a (cons (cadar l) a))) (f (cdr l))))
  5.   )
  6. )