Programming puzzles: processing lists!

[pdo]

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

Code:


\<< { } { } \-> 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

Code:


\<< { } \-> mps
  \<<
    IF DUP SIZE 2. == THEN
      1. \->LIST 'mps' STO+
    ELSE
      2. OVER SIZE FOR n
        DUP 1. n 2. \->LIST
        LFLTP SWAP
        LAMP
        DUP SIZE ROT SWAP NDUPN \->LIST SWAP
        2. \<< + \>> DOLIST
        'mps' STO+
      NEXT
      DROP
    END mps REVLIST
  \>>
\>>

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 :-)

Paul