Post Reply 
Programming puzzles: processing lists!
08-19-2017, 09:59 PM
Post: #198
RE: Programming puzzles: processing lists!
I couldn't resist. It hooked me in again, so here's my RPL translation of the Lisp program I posted. It's not particularly pretty, but I thought I'd post it anyway.

Firstly, I created a utility function called LFLTP (Lisp FiLTer on Positions). Its stack diagram is
(List Positions -> RemainderList ExtractedList)
where List is an arbitrary list of things and Positions is a list of positive indexes.
The function then extracts all those objects referenced by the indexes and places them in the ExtractedList, leaving the other objects in RemainderList.

The definition of LFLTP is

\<< { } { } \-> wnt got rem
  \<< 1.
      IF wnt NSUB POS
      THEN 'got'
      ELSE 'rem'
      END STO+
    \>> DOSUBS
    rem REVLIST
    got REVLIST

Then I wrote my equivalent of generate-match-pairings, which I called LAMP (List All Match Pairings). Its code is

\<< { } \-> mps
    IF DUP SIZE 2. == THEN
      1. \->LIST 'mps' STO+
      2. OVER SIZE FOR n
        DUP 1. n 2. \->LIST
        LFLTP SWAP
        2. \<< + \>> DOLIST
        'mps' STO+
which as I said above is not too pretty, and could do with refactoring into smaller routines to make it digestible. The main thing to note is the recursive call of LAMP in the middle.

Some runs:-

{1 2 3 4 5 6} 'LAMP' TEVAL
returns a list of 15 entries and takes about 3.5 seconds.

{1 2 3 4 5 6 7 8} 'LAMP' TEVAL
returns a list of 105 entries and takes about 27 seconds.

{1 2 3 4 5 6 7 8 9 10} 'LAMP' TEVAL
returns a list of 945 entries and takes about 256 seconds.

Seems to be growing with a factor of approx N-1, which seems reasonable. I didn't try anything longer for fear of running out of memory and/or battery power! (I am using a 49g+ so can't run it off USB power.)

Hope this is interesting for someone (other than me, and perhaps David and Pier :-)

Visit this user's website Find all posts by this user
Quote this message in a reply
Post Reply 

Messages In This Thread
RE: Programming puzzles: processing lists! - pdo - 08-19-2017 09:59 PM

User(s) browsing this thread: 1 Guest(s)