Author Topic: [challenge] A09 : Run-length Encoding of a list  (Read 746 times)

0 Members and 1 Guest are viewing this topic.

JohnK

  • Administrator
  • Seagull
  • Posts: 10140
[challenge] A09 : Run-length Encoding of a list
« on: December 30, 2021, 09:21:32 AM »
Using only AutoLisp, implement run-length encoding (RLE) on a list of duplicate entries. If an element has no duplicates it is simply copied into the result list meaning that only elements with duplicates are transferred as (N E) lists to the result list.

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

Donate to TheSwamp.org

Lee Mac

  • Seagull
  • Posts: 12696
  • London, England
Re: [challenge] A09 : Run-length Encoding of a list
« Reply #1 on: December 30, 2021, 09:33:54 AM »
Quick first stab -
Code - Auto/Visual Lisp: [Select]
  1. (defun rle1 ( l / f )
  2.     (defun f ( l x n )
  3.         (if l
  4.             (if (= x (car l))
  5.                 (f (cdr l) x (1+ n))
  6.                 (cons (if (= 1 n) x (list n x)) (f (cdr l) (car l) 1))
  7.             )
  8.             (list (if (= 1 n) x (list n x)))
  9.         )
  10.     )
  11.     (f (cdr l) (car l) 1)
  12. )
Code - Auto/Visual Lisp: [Select]
  1. _$ (rle1 '(a a a a b c c a a d e e e e))
  2. ((4 A) B (2 C) (2 A) D (4 E))
« Last Edit: December 30, 2021, 10:27:38 AM by Lee Mac »

Lee Mac

  • Seagull
  • Posts: 12696
  • London, England
Re: [challenge] A09 : Run-length Encoding of a list
« Reply #2 on: December 30, 2021, 09:36:36 AM »
Another, iterative -
Code - Auto/Visual Lisp: [Select]
  1. (defun rle2 ( l / n r x )
  2.     (while l
  3.         (setq x (car l)
  4.               l (cdr l)
  5.               n 1
  6.         )
  7.         (while (and l (= x (car l)))
  8.             (setq n (1+  n)
  9.                   l (cdr l)
  10.             )
  11.         )
  12.         (setq r (cons (if (= 1 n) x (list n x)) r))
  13.     )
  14.     (reverse r)
  15. )

JohnK

  • Administrator
  • Seagull
  • Posts: 10140
Re: [challenge] A09 : Run-length Encoding of a list
« Reply #3 on: December 30, 2021, 09:47:14 AM »
Iterative will be faster but here was mine.

Code - Auto/Visual Lisp: [Select]
  1. (defun encode-rle-list (aList / pack)
  2.         (defun pack (aList)
  3.           (defun group-subarray (element seg aList)
  4.             (cond
  5.               ((null aList)
  6.                (list (cons element seg)))
  7.               ((eq element (car aList))
  8.                (group-subarray element (cons element seg) (cdr aList)))
  9.               (t
  10.                 (cons
  11.                   (cons element seg)
  12.                   (group-subarray (car aList) '() (cdr aList))))
  13.               )
  14.             )
  15.           (if (null aList)
  16.             '()
  17.             (group-subarray (car aList) '() (cdr aList)))
  18.           )
  19.   (mapcar
  20.     '(lambda (x)
  21.        (if (= (length x) 1)
  22.          (car x)
  23.          (list (length x) (car x))))
  24.     (pack aList)
  25.     )
  26.   )
  27.  

EDIT: removed "extra" function from code. ...not sure what I was thinking at the time.
« Last Edit: December 30, 2021, 11:32:31 AM by John Kaul (Se7en) »
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org

ronjonp

  • Needs a day job
  • Posts: 7437
Re: [challenge] A09 : Run-length Encoding of a list
« Reply #4 on: December 30, 2021, 12:49:14 PM »
Hey John, why are you limiting these challenges to only 'pure' autolisp?
It would be fun to use all the tools in the bag then bench the vl variants against themselves as well as the pure autolisp against themselves then a total bench.

Maybe have the participants name the functions like so to easily keep track:
VL-<USERNAME>-<FUNCTIONNAME>-<#>
VANILLA-<USERNAME>-<FUNCTIONNAME>-<#>

Just a thought  :-)

Windows 11 x64 - AutoCAD /C3D 2022

Custom Build PC

JohnK

  • Administrator
  • Seagull
  • Posts: 10140
Re: [challenge] A09 : Run-length Encoding of a list
« Reply #5 on: December 30, 2021, 01:07:58 PM »
The thought was:
1. Beginners could learn the basic principles easier. (But there isn't a whole lot of interactions happening with these)
2. VL has a lot of these functions baked in (vl-somethin' ...) and submissions would be short and dumb.

We can certainly open these up to VL and AL but we should have rules (like you suggest).

Maybe those names could be simplified?
<FUNCTIONNAME>-<USER>-<#>
or
vl_<FUNCTIONNAME>-<USER>-<#>


I tried to make an "ASSERT" function to check the results before adding the submission to the benchmark list but it didn't work out that well. I would like to do more testing but everyone's so quiet.
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org

BIGAL

  • Swamp Rat
  • Posts: 1037
  • 40 + years of using Autocad
Re: [challenge] A09 : Run-length Encoding of a list
« Reply #6 on: December 30, 2021, 10:18:32 PM »
I use a method by Gile works great for Block attribute quantities.

Code: [Select]
; By AlanH Aug 2021
(vl-load-com)
; By Gile
(defun my-count (a L)
  (cond
   ((null L) 0)
   ((equal a (car L)) (+ 1 (my-count a (cdr L))))
   (t (my-count a (cdr L))))
)

; By Gile
(defun remove_doubles (lst)
  (if lst
    (cons (car lst) (remove_doubles (vl-remove (car lst) lst)))
  )
)

(setq lst '("a" "a" "a" "a" "b" "b" "b" "b" "b" "C" "C" ))
(setq lst2 (remove_doubles lst))
(foreach val lst2
(setq cnt (my-count  val lst))
(setq lst3 (cons (list val cnt) lst3))
)

(("C" 2) ("b" 5) ("a" 4))
A man who never made a mistake never made anything

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7320
  • AKA Daniel
Re: [challenge] A09 : Run-length Encoding of a list
« Reply #7 on: December 31, 2021, 04:46:49 AM »
sorry, bored
Lee's while in C++20

Code - C: [Select]
  1. #include <iostream>
  2. #include <vector>
  3. #include <variant>
  4. #include <string>
  5.  
  6. using namespace std;
  7. using Values = vector<variant<int32_t, double_t, wstring>>;
  8.  
  9. int main()
  10. {
  11.         const Values l =
  12.         {
  13.                 L"a", L"a", L"a", L"a", L"b", L"c", L"c", L"a",
  14.                 L"a", L"d", L"e", L"e", L"e", L"e", 4, 4, 4, 4, 5.75
  15.         };
  16.         auto i = l.begin(), in = i, e = l.end();
  17.         while (in != e) {
  18.                 auto n = 1;
  19.                 while (++in != e && *i == *in) {
  20.                         n++;
  21.                         i++;
  22.                 }
  23.                 if (n == 1)
  24.                         visit([](auto&& x) {std::wcout << x; }, *i);
  25.                 else
  26.                         visit([&](auto&& x) {std::wcout << '(' << n << ' ' << x << ')'; }, *i);
  27.                 i = in;
  28.         }
  29.         cin.get();
  30. }
  31.  
Retired

roy_043

  • Water Moccasin
  • Posts: 1895
  • BricsCAD 18
Re: [challenge] A09 : Run-length Encoding of a list
« Reply #8 on: January 03, 2022, 04:27:26 PM »
Lst may not contain nil:
Code - Auto/Visual Lisp: [Select]
  1. (defun encode-rle-list-roy (lst / tmp)
  2.   (apply
  3.     'append
  4.     (mapcar
  5.       '(lambda (cur / ret)
  6.         (cond
  7.           ((not cur)
  8.             (if (cdr tmp)
  9.               (list (list (length tmp) (car tmp)))
  10.               tmp
  11.             )
  12.           )
  13.           ((not tmp)
  14.             (setq tmp (list cur))
  15.             nil
  16.           )
  17.           ((equal cur (car tmp))
  18.             (setq tmp (cons cur tmp))
  19.             nil
  20.           )
  21.           (T
  22.             (setq ret
  23.               (if (cdr tmp)
  24.                 (list (list (length tmp) (car tmp)))
  25.                 tmp
  26.               )
  27.             )
  28.             (setq tmp (list cur))
  29.             ret
  30.           )
  31.         )
  32.       )
  33.       (append lst '(nil))
  34.     )
  35.   )
  36. )

dexus

  • Newt
  • Posts: 75
Re: [challenge] A09 : Run-length Encoding of a list
« Reply #9 on: January 06, 2022, 07:46:34 AM »
Here is my first attempt.
This was without looking at the others, the second one looks virtually identical to Lee's submission. :brow:

Code - Auto/Visual Lisp: [Select]
  1. (defun rle-dexus (lst / counter item output)
  2.   (if lst (progn
  3.     (setq counter 0 item (car lst))
  4.     (while (= item (car lst))
  5.       (setq counter (1+ counter) lst (cdr lst))
  6.     )
  7.     (setq output (cons (if (= counter 1) item (list counter item)) (rle-dexus lst)))
  8.   ))
  9.   output
  10. )
And a version with a loop:
Code - Auto/Visual Lisp: [Select]
  1. (defun rle-dexus-loop (lst / counter item output)
  2.   (while lst
  3.     (setq counter 0 item (car lst))
  4.     (while (= item (car lst))
  5.       (setq counter (1+ counter) lst (cdr lst))
  6.     )
  7.     (setq output (cons (if (= counter 1) item (list counter item)) output))
  8.   )
  9.   (reverse output)
  10. )
« Last Edit: January 06, 2022, 08:13:32 AM by dexus »

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: [challenge] A09 : Run-length Encoding of a list
« Reply #10 on: January 20, 2022, 02:20:00 AM »
Code - Auto/Visual Lisp: [Select]
  1. (defun f (l)
  2.   (if l
  3.     (if (atom (car l))
  4.       (if (= (car l) (cadr l))
  5.         (f (cons (list 1 (car l)) (cdr l)))
  6.         (cons (car l) (f (cdr l)))
  7.       )
  8.       (if (= (cadar l) (cadr l))
  9.         (f (cons (list (1+ (caar l)) (cadar l)) (cddr l)))
  10.         (cons (car l) (f (cdr l)))
  11.       )
  12.     )
  13.   )
  14. )

VovKa

  • Swamp Rat
  • Posts: 1475
  • Ukraine
Re: [challenge] A09 : Run-length Encoding of a list
« Reply #11 on: January 20, 2022, 05:21:46 AM »
here's the same problem as in A01 and A08