+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: General Forum (/forum-4.html)
+--- Thread: Programming puzzles: processing lists! (/thread-8209.html)
RE: Programming puzzles: processing lists! - DavidM - 05-01-2017 05:45 PM
(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.
RE: Programming puzzles: processing lists! - pier4r - 05-01-2017 08:17 PM
(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.
RE: Programming puzzles: processing lists! - DavidM - 05-02-2017 07:00 PM
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!
RE: Programming puzzles: processing lists! - pier4r - 05-03-2017 08:58 PM
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.
RE: Programming puzzles: processing lists! - Werner - 05-04-2017 07:42 AM
#21 - remove duplicates, keep first instance
Code:
\<<
\-> L
\<<
L
1.
\<< L OVER POS NSUB \=/ DROPN \>>
DOSUBS
\>>
\>>Cheers, Werner
RE: Programming puzzles: processing lists! - Didier Lachieze - 05-04-2017 11:21 AM
#21 on the Prime:
Code:
EXPORT LI21(l)
BEGIN
UNION(l);
END;RE: Programming puzzles: processing lists! - pier4r - 05-04-2017 06:05 PM
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
RE: Programming puzzles: processing lists! - rprosperi - 05-04-2017 06:12 PM
(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.
RE: Programming puzzles: processing lists! - pier4r - 05-04-2017 06:14 PM
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.
RE: Programming puzzles: processing lists! - DavidM - 05-04-2017 11:45 PM
(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.
RE: Programming puzzles: processing lists! - pier4r - 05-05-2017 11:51 AM
(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.
RE: Programming puzzles: processing lists! - John Keith - 05-05-2017 12:24 PM
(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.
RE: Programming puzzles: processing lists! - DavidM - 05-05-2017 07:32 PM
(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
\>>(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?
RE: Programming puzzles: processing lists! - DavidM - 05-05-2017 08:40 PM
(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
\>>RE: Programming puzzles: processing lists! - DavidM - 05-06-2017 02:48 AM
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
\>>
\>>RE: Programming puzzles: processing lists! - pier4r - 05-06-2017 05:25 AM
(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.
RE: Programming puzzles: processing lists! - Werner - 05-06-2017 07:44 AM
@pier4r:
Yours is faster for lists containing lots of duplicates, mine for large lists with few duplicates.
Cheers,Werner
RE: Programming puzzles: processing lists! - pier4r - 05-06-2017 03:21 PM
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-works-only-code/git-2/source/master/hp48-50_series/programs/general/listOperations.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
\>>
\>>RE: Programming puzzles: processing lists! - DavidM - 05-10-2017 02:35 AM
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.
RE: Programming puzzles: processing lists! - pier4r - 05-10-2017 05:44 PM
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.