Programming puzzles: processing lists!

[DavidM]

(04-28-2017 09:51 PM)pier4r Wrote:  #6 (that is very similar to #10, my bad)
Pier: 3.04 seconds (impressive the slow down even using DOSUBS)
DavidM: waiting for fix, or using the result for #10

Rather than totally rewrite #6, I simply changed a couple of things to address the issue of a "homogenous" list. While I was at it, I went ahead and also handled a list of only one number, which I assumed to be valid in this case. These changes make my approach even slower than before, though not significantly. Still no speed demon here. :-)

Code:

\<<
  \-> src
  \<<
    src
    IF
      @ does the list contain more than 1 number?
      DUP SIZE 1 >
    THEN
      @ the source list has to have all equal numbers grouped together
      SORT

      @ compare two at a time
      2

      @ for each pair of elements:
      \<<
        @ if this is the first iteration, position a "1" as the running total
        IF
          NSUB 1 ==
        THEN
          1 UNROT
        END

        @ if these two numbers are the same, increment the existing running total
        IF
          ==
        THEN
          1 +
        ELSE
          @ the numbers are different, so leave the current running total for the
          @ result on the stack and start a new running total for the next number
          1
        END
      \>>
      DOSUBS

      IF
        @ more than 1 unique number was encountered
        DUP SIZE 1 >
      THEN
        @ convert the current result list to one that has:
        @ 0's for each pair that matches
        @ 1's for each pair that doesn't match
        \<< \=/ \>> DOSUBS

        @ sum up all the integers in the result.  If the total isn't 0, then
        @ the list didn't match the stated criteria.
        \GSLIST
      ELSE
        @ only 1 number represented, so the list was valid
        DROP 0
      END

      "invalid" 'src' IFTE

    END

    @ a source list with only 1 number is assumed to be valid
  \>>
\>>

Looks like you have some impressive times in your results! I've been working on some non-related things lately that haven't allowed for much time to devote to this. I'll give this another look now as I'm interested in seeing the approaches others have used to the problems I've already attempted. Still won't look at the ones I haven't yet tried, though.

[pier4r]

(05-01-2017 05:45 PM)DavidM Wrote:  Looks like you have some impressive times in your results!

For the #6 I will have to check.

For the speed, I just "learn by appreciating", you let me discover SUBs and I abuse it (because first correctness, then speed, unless when it takes too long), and multiple SUBs are even better than one DOSUBS. Dunno, maybe I mess up the code but it just works faster.

[DavidM]

The challenges for #2 and #12 are simple enough that they make good examples for multiple languages. I thought I'd show one approach to that type of problem using SysRPL, though this example doesn't use the built-in list processing features.

First, some general considerations:

1) One of the great benefits to SysRPL programming is a speed improvement realized from using type-specific commands that don't waste time checking their arguments first. There is a risk, though. Passing the wrong type of argument to a command doesn't usually end well, and will likely cause a crash and possibly the loss of data. Type checking that may be considered a luxury in UserRPL isn't optional with SysRPL.

2) SysRPL commands can't be entered into a program using the same "<< command1 command2 ... >>" structure that UserRPL uses on the calculator. The code has to be compiled into a single object before it can be used, and there are several ways to do this. My preferred way is to write and compile the code on a computer using Debug4x, then transfer it to the calculator after debugging it. So the example below uses the syntax appropriate for that particular scenario.

3) SysRPL is still RPL. A running SysRPL program uses the stack and other calculator resources in the same ways that UserRPL does. So items are placed on (and removed from) the stack in the same ways that you are already used to seeing them. There are simply more commands available that work in slightly different ways than you may be used to seeing.

To help with reading the code, here's a couple of hints about some specifics:
- a SysRPL "LAM" is the equivalent of a UserRPL local variable. I've used a particular type of LAM here known as a "NULLLAM", which is accessed via an index number instead of a name. They are one of the best things about SysRPL IMHO because they allow you the benefits a local variables with notable speed improvements over named locals. For readability, I DEFINEd a "substitute" for the 1GETLAM SysRPL command to make it more clear what was actually happening.
- numbers in RPL can be REAL (which always have a fraction mark) or INTEGER (which never have a fraction mark). In SysRPL, integers of this type are called ZINTs.

Enough of that. Here's my liberally-commented version of a SysRPL solution to challenge #12:

Code:

INCLUDE DirMacro.s

ASSEMBLE
   Dir <Ch1203>
RPL

( local variable DEFINE for readability )
DEFINE   GetListSize    1GETLAM

::
   CK1NOLASTWD          ( program needs at least 1 object on stack )

   CK&DISPATCH1         ( dispatch to the appropriate block based on type of object )

   list ::              ( this block applies if SL1 object is a list )
      INNERCOMP         ( explode the list )
      DUP1LAMBIND       ( make a copy of the size then bind it to NULLLAM #1 )

      #1+_ONE_DO (DO)   ( do for each element in the list )

         DUPTYPEREAL? IT ::            ( only do if object is a REAL )
            %3 OVER %= casedrop %5     ( 3 becomes 5 )
            %5 OVER %= casedrop %3     ( 5 becomes 3 )
         ;                             ( any other REAL is ignored )

         DUPTYPEZINT? IT ::            ( only do if object is a ZINT )
            Z3_ OVER Z= casedrop Z5_   ( 3 becomes 5 )
            Z5_ OVER Z= casedrop Z3_   ( 5 becomes 3 )
         ;                             ( any other ZINT is ignored )

         ( any other object type is ignored )

         GetListSize ROLL  ( roll the entire list on the stack )
      LOOP                 ( end of DO loop )

      GetListSize {}N      ( implode the list )
      ABND                 ( release NULLLAMs )
   ;
;

This above SysRPL implementation was meant to be the functional equivalent of this UserRPL program:

Code:

\<<
  LIST\->
  DUP \-> listSize
  \<<
    1 SWAP START
      CASE
        3 OVER == THEN DROP 5 END
        5 OVER == THEN DROP 3 END
      END
      listSize ROLL
    NEXT
    listSize \->LIST
  \>>
\>>

I didn't use DOSUBS in this case in order to provide for a more direct comparison.

There's a couple of notable benefits that the SysRPL implementation provides:
- A well-formed SysRPL program should always check for appropriate stack contents when it starts. Not doing so can (and probably will) result in a crash. So this program provides meaningful checking of its argument, and will exit gracefully with an appropriate error if a list isn't in stack level 1 upon entry.
- The program flow differentiates between REAL and INTEGER elements and provides the translation of the numbers accordingly. This could also have been done using UserRPL, of course, but it was an easy add to the SysRPL version since I had to check the type anyway. I didn't bother to do that with the UserRPL version.

So what about performance?

Readability is subjective, but I believe the SysRPL version is at least as readable as the UserRPL version, at least to someone familiar with the language constructs.

The UserRPL version may look smaller than the SysRPL version, but that's probably due to the lack of comments and tighter spacing. The actual size of the SysRPL version is 110 bytes, as compared with 127 for the UserRPL version. The UserRPL version could have saved some bytes by using a shorter local variable name, at the cost of readability. One of the size benefits of SysRPL is that there are many "combo" commands that do multiple steps while only taking up 5 nibbles.

Speed is probably the best benefit here. The extra time taken by nearly all UserRPL commands to validate their arguments adds up during the execution of a program, especially when loops are involved. For this test I used the average of 50 iterations of lists containing 200 elements. Here's how the two versions performed:

UserRPL version: 1.878 seconds/list
SysRPL version: 0.386 seconds/list

Not too shabby!

[pier4r]

DavidM thanks for the sysRPL hint. Long ago I read a similar one by Andreas Müller (software49g) . I see the power of sysRPL but I also see that is closer to assembly at times, therefore I would rather move on hpgcc / newRPL without USB , especially knowing that some nice users contributed with libraries to wrap back and forth objects with hpgcc. Like this: http://www.hpcalc.org/details/7177
The reason would be speed and still more readability than sysRPL , that at least for new users looks a bit too cryptic. (once one is used to RPL, then it becomes more familiar, of course)

Moreover from previous post it seems to me that you yourself can handle hpgcc programs (while I have the todo open since long time), so you may relate what I mean.

Of course if you want to do all the challenges in sysRPL, I suppose they will be useful as n-th example (this time on lists) for sysrpl programming.

(Plus I did not expect the sysRPL to be "only" 3 times as fast as the userRPL)

Anyway, back to list processing. I added some more challenges to the first post and I attacked the challenge #21. I still have to check the timings on #6 from the userRPL of DavidM.

#21 simple

Code:


    @ remove duplicates from a list of positive integers
    @ without maintaining the relative position
    
    @it seems to work.
    \<<
      0 @lastEl
      0 @resultList
      \->
      @input
      inputList
      @local var
      lastEl
      resultList
      \<<
        
        inputList SORT
        1
        \<<
          IF
            DUP lastEl ==
              @ if the last element is equal to the current
            NSUB 1 >
              @we keep the head
            AND
          THEN
            @ drop it, we have it already
            DROP
          ELSE
            @we leave the element
            @but we also save it
            DUP 'lastEl' STO
          END
        \>>
        DOSUBS
      \>>
    \>>

#21

Code:


    @ remove duplicates from a list of positive integers
    @ maintaining the relative position using the first appearance of an element.
    
    @it seems to work.
    \<<
      0 @lastEl
      0 @newEl
      { } @resultList
      \->
      @input
      inputList
      @local var
      lastEl
      newEl
      resultList
      \<<
        
        inputList
        1
        \<<
          @I'm fighting since one hour with DOSUBS not liking the
          @output of this subprogram. It seems that if I don't leave something
          @ to put in the result list, DOSUBS complains
          @ (although it is not always necessary, I can run a program made of just
          @ drop and it works. I guess DOSUBS is not so clear to me)
          @ so I decide to use the resultList but actually the list made by
          @ DOSUBS will be the real result.
          'newEl' STO
          IF
            resultList newEl POS 0 ==
              @element not found in the result list
          THEN
            @we save it
            'resultList' newEl STO+
            @plus we drop it for DOSUBS otherwise we get complains
            newEl
          END
        \>>
        DOSUBS
      \>>
    \>>

more code as usual on assembla, as linked in previous posts.

[Werner]

#21 - remove duplicates, keep first instance

Code:

\<<
  \-> L
  \<<
    L
    1.
    \<< L OVER POS NSUB \=/ DROPN \>>
    DOSUBS
  \>>
\>>

Cheers, Werner

[Didier Lachieze]

#21 on the Prime:

Code:

EXPORT LI21(l)
BEGIN
 UNION(l);
END;

[pier4r]

While reading the general forum (page 41 now) I discovered this post: http://www.hpmuseum.org/forum/thread-4496.html

Inside a member pointed to the one minute marvels that contains interesting list operations. Also there is a version for duplicates.

Also the one minute marvel mentions handouts about Hp 48 periodical learning sessions. Were those, by chance, uploaded somewhere? Would be nice to have a look at them.

Also, thanks for the solutions about the #21 I will confront with mine asap

[rprosperi]

(05-04-2017 06:05 PM)pier4r Wrote:  Also the one minute marvel mentions handouts about Hp 48 periodical learning sessions. Were those, by chance, uploaded somewhere? Would be nice to have a look at them.

By sheer coincidence, they are being collected and will be released as a complete set, probably at HHC in September. Once available, an announcement will be made here at MoHPC.

[pier4r]

This is an amazing coincidence but I thought that the community, being always eager about valuable documentation, had somehow done this already. Well better late than never! Considering that the calculators will hopefully last another decade,allowing users to enjoy the documents.

[DavidM]

(05-04-2017 07:42 AM)Werner Wrote:  #21 - remove duplicates, keep first instance
...

Very nice, Werner. I especially like how you used the outcome of a test as the parameter for DROPN. I believe that would have shortened some of my earlier submissions! I'll remember that one moving forward.

[pier4r]

(05-01-2017 05:45 PM)DavidM Wrote:  

(04-28-2017 09:51 PM)pier4r Wrote:  #6 (that is very similar to #10, my bad)
Pier: 3.04 seconds (impressive the slow down even using DOSUBS)
DavidM: waiting for fix, or using the result for #10

Rather than totally rewrite #6, I simply changed a couple of things to address the issue of a "homogenous" list. While I was at it, I went ahead and also handled a list of only one number, which I assumed to be valid in this case. These changes make my approach even slower than before, though not significantly. Still no speed demon here. :-)

So first I had to handle the case that the second dosubs returns a list of only one element, that \GSLIST does not like, If I understood your comments correctly (I love comments and I am a bit critical to code - especially using the stack - posted without them. Although better having the code than nothing), when the result is 0 then the processing returns valid. Therefore I add a 0 to the list returned by dosubs and GSLIST likes it.

If I am not mistaken. The list { 5 5 5 5 5 6 6 6 6 6 } is returned as valid, but it is not.
Also: { 1 2 3 1 2 3 } is valid (but it is not).

Could you check if I messed up with your code?

For the #21 I'm a bit surprised because I did not expect such timings.
The compact version of werner handles correctly 50 lists of 100 elelemnts in 1.61 seconds.
My longer program (you know, I don't like cryptic stack operations) handles the same workload in 1.35 seconds.

[John Keith]

(05-04-2017 11:21 AM)Didier Lachieze Wrote:  #21 on the Prime:

Code:

EXPORT LI21(l)
BEGIN
 UNION(l);
END;

The GoferLists function Nub also does this.

[DavidM]

(05-05-2017 11:51 AM)pier4r Wrote:  So first I had to handle the case that the second dosubs returns a list of only one element, that \GSLIST does not like, If I understood your comments correctly. Therefore I add a 0 to the list returned by dosubs and GSLIST likes it.

Yes, I can't believe I missed that in the version that I copied into the last post. I cleaned it up a bit and went ahead and simply returned 0 (invalid) or 1 (valid) in this version:

Code:

\<<
  SORT                    @ input list must have elements grouped together
  IF                      @ if more than 1 element
    DUP SIZE 1 >
  THEN                    @ yes, more than 1 element in source list
    2
    \<<
      IF                  @ is this the first pair in the list?
        NSUB 1 ==
      THEN
        1 UNROT           @ if so, place the first running total
      END

      IF                  @ if the pair of list elements is the same
        ==
      THEN
        1 +               @ yes, add 1 to current running total
      ELSE
        1                 @ no, make a new running total
      END
    \>>
    DOSUBS

    IF                    @ was there more than 1 unique element?
      DUP SIZE 1 >
    THEN                  @ yes, make sure all counts were the same
      \<< \=/ \>> DOSUBS
      0 +                 @ \GSLIST protection for list with 1 element
      \GSLIST             @ sum the result to check for any inequalities
      NOT                 @ convert sum to result
    ELSE                  @ no, just one unique element repeated multiple times
      DROP                @ the list containing 1 element
      1                   @ list is valid by definition
    END
  ELSE                    @ there was only 1 element
    DROP                  @ drop the source list
    1                     @ list is valid by definition
  END
\>>

I know this particular algorithm isn't the fastest, but I wanted to go ahead and stick with the original plan to see it through.

(05-05-2017 11:51 AM)pier4r Wrote:  If I am not mistaken. The list { 5 5 5 5 5 6 6 6 6 6 } is returned as valid, but it is not.
Also: { 1 2 3 1 2 3 } is valid (but it is not).

I don't understand why those two lists should be considered invalid. Your original challenge for #6 says "verify that every integer in the list appears the same amount of times". Doesn't every integer appear the same number of times in both of those lists? What am I missing?

[DavidM]

(05-05-2017 11:51 AM)pier4r Wrote:  For the #21 I'm a bit surprised because I did not expect such timings.
The compact version of werner handles correctly 50 lists of 100 elelemnts in 1.61 seconds.
My longer program (you know, I don't like cryptic stack operations) handles the same workload in 1.35 seconds.

Your code is longer, but I believe it actually has the potential to be more efficient due to 1 main reason: your use of POS is searching a list that never contains duplicates, whereas Werner's POS is searching the original list (which may contain duplicates). The quantity and position of duplicates can have some bearing on the performance as well.

To show the other extreme, an input list with no duplicates removes any "short-circuit" searches that POS might make, and thus negates the advantage yours gains from that. Try the list created by this code to see a different outcome:

Code:

\<<
  1 100 FOR n
    n
  NEXT
  100 \->LIST
\>>

[DavidM]

I finally got around to working on #13. This was more fun than some of the others.

Code:

\<<
  DUP         @ src - source list
  SIZE        @ srcsz - source list size
  1           @ kg - "keep going" boolean
  DUP         @ subsz - sublist size (initially 1)
  0           @ subcnt - quantity of sublists for valid solution
  \-> src srcsz kg subsz subcnt
  \<<
    WHILE
      kg      @ "keep going" flag
    REPEAT
      IF      @ only attempt the current sublist if it fits
        srcsz subsz MOD NOT

      THEN    @ this is a valid sublist size to check

        @ build a test list based on the current sublist size
        src 1 subsz SUB       @ create test sublist based on source
        srcsz subsz /         @ the number of sublists is based on source size
        NDUPN                 @ replicate the sublists
        1 - 1 SWAP START + NEXT @ add the test sublists together

        IF    @ does the test list match the source?
          src ==

        THEN  @ yes, a match
          srcsz subsz / 'subcnt' STO    @ store the matching sublist count
          0 'kg' STO                    @ signal that loop exit condition
        END
      END

      @ increment subsz and signal exit condition if max size reached
      'subsz' INCR
      IF    @ is the next sublist size >= the source list size?
        srcsz \>=

      THEN  @ yes, signal the exit condition
        0 'kg' STO
      END
    END

    @ report final result; either the sublist count or "invalid"
    subcnt DUP "invalid" IFTE

  \>>
\>>

[pier4r]

(05-05-2017 07:32 PM)DavidM Wrote:  I don't understand why those two lists should be considered invalid. Your original challenge for #6 says "verify that every integer in the list appears the same amount of times". Doesn't every integer appear the same number of times in both of those lists? What am I missing?

Ugh, damn me you are right so maybe my #6 was wrong all the time because I mixed it with #10.

I should check my code now and then compare it to yours.
I mean I wrote the challenge, the examples, and them I am confused, what a shame.

[Werner]

@pier4r:
Yours is faster for lists containing lots of duplicates, mine for large lists with few duplicates.
Cheers,Werner

[pier4r]

So I had to fix my #6, all the time I mixed with the the #10 damn me.

timings (average on 50 lists of 100 elements)
#6
Pier: 2.87 s
David: 2.74 s

#13
Pier: 3.92 s (was 4.03 s)
David: 2.67 s

All code: https://app.assembla.com/spaces/various-...erations.s

#6 input gen

Code:


  \<<
      0    @possibleSubLengths     
      0    @chosenLength
      0    @possibleElements
      { }  @resList
      \->
      @input
      listSize
      @local var
      possibleSubLengths
      chosenLength
      possibleElements
      resList
      \<<
        IF
          2 RAND * IP 0 >
        THEN
          @generate a valid list
          @the repetition of the elements can be only a multiple of
          @the size.
          listSize c13factorsComposition
            @we get the possible subLengths
          listSize +
            @we also add the length itself
          'possibleSubLengths' STO
          
          @we randomize the list
          possibleSubLengths
          DUP SIZE 2 * shuffleList
          HEAD 'chosenLength' STO
          
          @now we create a list of all the numbers util lengthSize
          @repetitions so
          'n' 'n' 1 listSize 1 SEQ
          @shuffle
          listSize 2 * shuffleList
          @save
          'possibleElements' STO
          
          @now we consume those adding them to the result list a proper
          @number of times
          1 listSize
          FOR counter
            possibleElements headList
            @we save the list without the head
            SWAP 'possibleElements' STO
            
            resList SWAP
            @ we have the head, we replicate it
            @ and then we add it to the result list
            chosenLength NDUPN
            \->LIST +
            'resList' STO
          chosenLength STEP
          
          @leave the result but mixed
          resList listSize 2 * shuffleList
        ELSE
          @generate a random list
          listSize 1 listSize getRandomList
        END
      \>>
    \>>

#6 solver

Code:


    \<<
      0  @listSize
      0  @subSize
      0  @counter
      12 @ufValid
      \->
      @input
      inputList
      @localvar
      listSize
      subSize
      counter
      ufValid
      \<<
        @The plan:
        @sort the list
        @then if the list is valid all the elements will occupy equal
        @space in the list. So we can do it with sub.
        @To get the space of the list, we can use SORT and the reversed sort
        @so with POS we know the first and the last postion, if the know the
        @size of the list.
        @ a problem for this is a list with unique elements except some.
        @a no I have it, we ask for "different" in a dosub.
        inputList SIZE 'listSize' STO
        inputList SORT 'inputList' STO
        
        @assume positive
        ufValid SF
        
        @we know that the head element is in first position,
        @but how many times it appears?
        inputList
        DUP HEAD
        returnAllPos
        SIZE 'subSize' STO
          @we save the amount of positions
          @we could have also done it taking the last POS
          @ with a reverted list and then figuring out the size.
          @ but I want to use a routine that can be helpful.
          
        @now we can test all the sublists one after another.
        @but before a little check for possibility.
        IF 
          listSize subSize MOD 0 \=/
        THEN
          @no way it can be valid
          ufValid CF
        END
        
        IF
          ufValid FS?
            @if still it is valid
          subSize 1 >
            @if we have a sub that is larger than 1
          AND
        THEN
          1 'counter' STO
          WHILE
            ufValid FS?
            counter subSize * 1 + listSize <
              @the starting point of the next sub is within the size
            AND
          REPEAT
            inputList
            counter subSize * 1 + 
              @starting point
            counter 1 + subSize *
              @end point
            SUB
              @we have a sublist that should be done
              @of the same element, between counter*subSize + 1
              @ and (counter + 1)*subsize
              
            @we need to know if there is always the same element so
            @if it is so, if we test for inequality we get always zero
            2
            \<< \=/ \>>
            DOSUBS
            0 +
              @ to avoid \GSLIST complainst
            IF
              \GSLIST 0 \=/
            THEN
              @invalid list
              ufValid CF
            END
            
            1 'counter' STO+
          END
        ELSE
          IF
            ufValid FS?
              @if still it is valid
            subSize 1 ==
              @if we have a sub that is exactly one
            AND
          THEN
            inputList
            2  
              @2 elements one behind the other, if we get duplicates and not
              @uniques, we will see
            \<< == \>>
            DOSUBS
              @if we have only unique elements, the list should be made out of zeroes
            0 + @avoiding complaints from \GSLIST
            
            IF
              \GSLIST 0 \=/
            THEN
              @invalid list
              ufValid CF
            END
          END
        END
        
        ufValid FS?
          @valid 1, invalid 0
      \>>
    \>>

[DavidM]

Regarding #21:

OK, this is clearly cheating, but I just ran across this function reference while looking at some SysRPL list-handling routines. It turns out that there's a built-in function ("^COMPRIMext") for removing duplicates in a list, but it's only accessible via FLASHEVAL from UserRPL on the 50g:

Code:

\<< #2FD006 FLASHEVAL \>>

It looks like it simply explodes the list and then rebuilds it using "^AppendList", which is itself another SysRPL command that adds an element to a list but only if it isn't already there. The nice thing about it is that it is essentially a Saturn code object with a wrapper, so it should be relatively fast.

[pier4r]

Why cheating? If it works (and it works in general, not for a specific case like "only numbers up to 7", but like "all the positive integers that can be handled as reals), great.

I'll check as soon as I finish the #20, I'm stuck traversing the graph at the moment. I mean I have an idea, but I guess will be super slow, but it may be a good point to optimize from.