Post Reply 
Programming puzzles: processing lists!
04-25-2017, 06:31 PM
Post: #41
RE: Programming puzzles: processing lists!
(04-25-2017 04:27 PM)DavidM Wrote:  @Claudio: does newRPL have a "layer" similar in function to SysRPL? If so, is that how you approach the outer-loop processing of the list commands?

No, there's no inner layer per se, but you could think of it as if there is one. Let me clarify that a bit. newRPL basic code is written in C, and presents an API for libraries to use. Those libraries implement the RPL commands basically by doing the dispatch, argument check, then calling the API functions. So you could say that the C code is the inner layer, and the core that presents this API is the "low level".
However, there's a huge difference between calling an API and running an RPL loop like in sysRPL. If you want to define the inner layer as having an RPL loop, then there's no inner layer.
For the specific case of list processing commands, which need to execute a custom RPL program, there is no other way but to run the RPL loop, so those commands in newRPL are actually implemented in... newRPL (surprise). The outer layer == inner layer in this case. There's no need for an inner layer when the outer layer is quite well optimized.
Yes, there's a couple of unnamed (hidden) commands that get most of the job done, and let the loop run for the custom user program, in a sandboxed environment.
Find all posts by this user
Quote this message in a reply
04-25-2017, 08:34 PM
Post: #42
RE: Programming puzzles: processing lists!
Hold on. As far as my understanding of languages goes, I know that if you code in C, while the source is in C, the result is a binary for the CPU architecture (although with some overhead compared to the same binary produced from assembly code, this due to C being at a higher level than assembly).

Then there are the interpreters, like, say, python. Python should be a programming engine written in C that understand code and to avoid "understanding it again" can produce a sort of compiled version that is a bytecode.

So with a C binary the code should run without layers, directly CPU code.
With an interpreted language, there would be a first step to convert the program in internal code and then run the internal code using calls that run CPU code.

So, userRPL -> sysRPL -> saturn code (emulated) -> ARM code

while newRPL -> ARM code

python would be: python -> "compiled python" -> ARM code

When Claudio says "there is the inner layer of C code" it seems that the C code should be interpreted first, instead of being a binary.
Like: newRPL -> C -> ARM code

Am I mistaken?

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
04-25-2017, 10:24 PM (This post was last modified: 04-25-2017 10:30 PM by Vtile.)
Post: #43
RE: Programming puzzles: processing lists!
I post a good quess, which people that truely knows something can then correct.

I think it goes like this:

Userprogram -> newRPL / ARM code

Where newRPL is a set of libraries of ARM machine commands written and compiled in C (C->Assembly->Machinecode [as compilers are as far as I know usually done to produce target machines assembly source and then automatically with apropriate assembler compiled to machine binaries]). I mean both the OS and the (interactive) interpreter.

.. Now we can wait the real knowledge. Smile
Find all posts by this user
Quote this message in a reply
04-26-2017, 12:59 AM
Post: #44
RE: Programming puzzles: processing lists!
(04-25-2017 08:34 PM)pier4r Wrote:  Hold on....

...So, userRPL -> sysRPL -> saturn code (emulated) -> ARM code

I probably contributed to the confusion when I asked Claudio about an equivalent to a sysRPL "layer". In my own defense, I did use quotes. Smile

Seeing the list you made above (with the arrows) leads me to believe that you may have the wrong impression of the relationship of user- and sys-RPL. They're actually just subcategories of commands in the larger set of RPL as a whole. Neither is subordinate to the other, though some might argue that userRPL is actually just a subset of sysRPL that defines a "safer" or "less type-specific" operating model due to the way those commands are implemented.

When the 50g kernel is executing a collection of RPL objects (aka a "program"), it doesn't care if the next object in the stream is one in the category of userRPL or sysRPL. It sees them in the same way, and just executes them one after the other in the same fashion. There's no further interpretation.

(04-25-2017 08:34 PM)pier4r Wrote:  When Claudio says "there is the inner layer of C code" it seems that the C code should be interpreted first, instead of being a binary.
Like: newRPL -> C -> ARM code

Am I mistaken?

I don't want to speak for Claudio, but he was probably using those terms because of the way I asked the question.

In my mind the more important part of his answer pertains to how the RPL loop in newRPL is used to process the list commands. It sounds like the newRPL kernel is executing the list-processing commands more like another newRPL subroutine (with their own sandbox to play in) as opposed to API library calls as is apparently done with most other commands.
Find all posts by this user
Quote this message in a reply
04-26-2017, 01:30 AM
Post: #45
RE: Programming puzzles: processing lists!
(04-24-2017 08:27 PM)pier4r Wrote:  Please provide also the rest of the challenges otherwise I challenge myself (not bad, but still).

Here's my attempt at #6:
Code:
\<<
  @ 'src' is the source list
  @ 'tot' is the count of the current list element being checked
  1 \-> src tot
  \<<
    @ the source list has to have all equal numbers grouped together
    src SORT

    2 @ compare two at a time

    @ for each pair of elements:
    \<<
      IF
        @ are these both the same?
        ==
      THEN
        @ the numbers are equal, so increment the total for this number
        1 'tot' STO+
      ELSE
        @ the numbers are different, so leave the current running total for the
        @ result and start a new running total for the next number
        tot
        1 'tot' STO
      END
    \>>
    DOSUBS

    @ add the final total to the result list
    tot +

    @ at this point, we have a list result that shows the counts of
    @ each unique list element encountered

    @ convert the current result list to one that has:
    @ 0's for each pair of counts that matches
    @ 1's for each pair that doesn't match
    \<< \=/ \>> DOSUBS

    @ sum up all the integers in the above result.  If the total isn't 0, then
    @ the list didn't match the stated criteria.
    \GSLIST "invalid" 'src' IFTE
  \>>
\>>

As before, I focused more on using list processing features than performance. This time I used more appropriate line breaks and added comments, so hopefully it will be more readable.

I'll go ahead an include #7 as well. It should look somewhat familiar:
Code:
\<<
  @ get list size
  DUP SIZE

  @ determine last position of first subset
  DUP 2 / IP

  @ determine indices of last subset
  DUP 1 + ROT

  @ get last subset
  4 PICK UNROT SUB

  @ get first subset
  UNROT 1 SWAP SUB
  
  @ add -1 (sentinel) to first subset
  -1 +

  @ concatenate the lists in the proper order
  SWAP +
\>>
Find all posts by this user
Quote this message in a reply
04-26-2017, 02:49 AM
Post: #46
RE: Programming puzzles: processing lists!
(04-25-2017 08:34 PM)pier4r Wrote:  So, userRPL -> sysRPL -> saturn code (emulated) -> ARM code

while newRPL -> ARM code

python would be: python -> "compiled python" -> ARM code

When Claudio says "there is the inner layer of C code" it seems that the C code should be interpreted first, instead of being a binary.
Like: newRPL -> C -> ARM code

Am I mistaken?

Let's start confirming that C is compiled, and runs native ARM code.

Like every modern piece of software, newRPL is organized as a "stack":
* One layer of low-level subroutines that deal with bare data and exposes an API to manipulate objects and work with the stack, return stack, etc.
* A higher layer of libraries that define the commands, check the arguments, etc.
* The top layer is the RPL code from the user, be it loose commands ran from the keyboard or the menus, or programs stored in variables.

From this perspective, when David asked "is there an inner layer", the answer is yes, there's layers. However, I think he meant an intermediate language like sysRPL, running on the RPL loop. Then the answer is no, because it's the exact same loop, running the same newRPL commands (for the most part, there's a few hidden commands too, but not enough to define a new language), so list commands run in the same outer layer.
Except for the outer layer in RPL, the other 2 are compiled C, hence native ARM code.
So it depends on what kind of layers you are talking about, or how you define layers.

newRPL -> C command libraries -> C lower-level API
Find all posts by this user
Quote this message in a reply
04-26-2017, 04:49 PM
Post: #47
RE: Programming puzzles: processing lists!
OK, I've formatted and commented the others that I've attempted so far.

#8. Very similar to #7 in approach (and appearance):
Code:
\<<
  @ 'src' is the original source list
  \-> src
  \<<
    @ get list size
    src DUP SIZE

    @ determine last position of first subset
    DUP 2 / IP

    @ determine indices of last subset
    DUP 1 + ROT

    @ get last subset
    4 PICK UNROT SUB

    @ get first subset
    UNROT 1 SWAP SUB

    @ if equal, return source, else "invalid"
    == 'src' "invalid" IFTE
  \>>
\>>

#9:
Code:
\<<
  @ 'src' is the original source list
  \-> src
  \<<

    @ first, make a collapsed list of the number groups

    src HEAD 1 +  @ choose an arbitrary number that can't be the same as the
                  @ first element

    \-> last      @ store it as the "last encountered element"
    \<<
      src @ original list
      1   @ look at each element
      \<<
        IF
          @ current element the same as the last one?
          DUP last ==
        THEN
          @ yes, ignore it
          DROP
        ELSE
          @ no, leave it on stack and update 'last'
          DUP 'last' STO
        END
      \>>
      DOSUBS
    \>>

    @ now, make a list of the counts of the individual groups
    @ 'tot' is the running count of an element
    1 \-> tot
    \<<
      src @ original list
      2   @ compare two at a time

      @ for each pair of elements:
      \<<
        IF
          ==
        THEN
          @ the numbers are equal, so increment the total for this number
          1 'tot' STO+
        ELSE
          @ the numbers are different, so leave the current running total for the
          @ result and start a new running total for the next number
          tot
          1 'tot' STO
        END
      \>>
      DOSUBS

      @ add the final total to the list
      tot +
    \>>

    @ convert to a list containing 0s for matching pairs, 1s for mismatches
    \<< \=/ \>> DOSUBS

    @ sum the list; anything other than 0 indicates something didn't match
    \GSLIST

    @ add the sum to the collapsed groups list
    +

    @ final result must be { 3 5 3 0 }, otherwise the src list is invalid
    { 3 5 3 0 } == 'src' "invalid" IFTE
  \>>
\>>

#10:
Code:
\<<
  @ 'src' is the original source list
  \-> src
  \<<
    @ create a sorted list of the individual elements encountered

    src SORT DUP HEAD 1 + @ choose an arbitrary number that can't be the same as the first
    \-> src2 last
    \<<
      src2 @ original list
      1   @ look at each element
      \<<
        IF
          @ current element the same as the last one?
          DUP last ==
        THEN
          @ yes, ignore it
          DROP
        ELSE
          @ no, leave it on stack and update 'last'
          DUP 'last' STO
        END
      \>>
      DOSUBS

      @ create a list of the counts of the individual elements in the same order

      1 \-> tot   @ first count is 1
      \<<
        src2 @ original list
        2    @ compare two at a time

        @ for each pair of elements:
        \<<
          IF
            @ does the pair match?
            ==
          THEN
            @ the numbers are equal, so increment the total for this number
            1 'tot' STO+
          ELSE
            @ the numbers are different, so leave the current running total for the
            @ result and start a new running total for the next number
            tot
            1 'tot' STO
          END
        \>>
        DOSUBS

        @ add the final count to list
        tot +
      \>>
    \>>

    @ if the lists aren't the same, the source was invalid
    == 'src' "invalid" IFTE
  \>>
\>>

#11. Similar approach to others using SUB. Care needed to get the proper indices for even/odd element counts:
Code:
\<<
  @ 'src' is the original source list
  \-> src
  \<<
    @ get list size
    src DUP SIZE

    @ determine last position of first subset
    DUP 2 / CEIL

    @ determine indices of last subset
    OVER 2 / IP 1 + ROT

    @ get last subset, reverse it
    4 PICK UNROT SUB REVLIST

    @ get first subset
    UNROT 1 SWAP SUB

    @ if equal, return source, else "invalid"
    == 'src' "invalid" IFTE
  \>>
\>>

#12. Decided to do this one with a more robust approach than #2. Slower, but behaves better and isn't assumptive:
Code:
\<<
  1   @ check each element by itself
  \<<
    @ check each element for special handling
    CASE
      @ 3 -> 5
      DUP 3 == THEN DROP 5 END
      @ 5 -> 3
      DUP 5 == THEN DROP 3 END
      @ any other element will be left as-is
    END
  \>>
  DOSUBS
\>>
Find all posts by this user
Quote this message in a reply
04-26-2017, 06:24 PM (This post was last modified: 04-26-2017 06:25 PM by pier4r.)
Post: #48
RE: Programming puzzles: processing lists!
David your new #3, #6, #7, #8 looks like variant C solutions (use whatever you like, not only list operations), am I wrong?

Ah wait there is the sub command, I have to check the Aur.

As soon as possible I will compare them to mine.

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
04-26-2017, 06:44 PM
Post: #49
RE: Programming puzzles: processing lists!
(04-26-2017 06:24 PM)pier4r Wrote:  David your new #3, #6, #7, #8 looks like variant C solutions (use whatever you like, not only list operations), am I wrong?

Ah wait there is the sub command, I have to check the Aur.

As soon as possible I will compare them to mine.

That wasn't my intent. I was actually trying to force myself to use list commands wherever I could.

I consider SUB to be a list command in this context, since I am giving it a list and expecting one in return. I'm not exploding the list and doing anything with the elements. So to me, 3, 7, and 8 are all still variant A.

I'm also not sure why you would classify #6 as anything but variant A; the main steps used are SORT, DOSUBS (x2), and ΣLIST. Is there something going on with it that doesn't fit the "A" classification?

If I were to approach these as variant C, I would likely use sysRPL instead. Smile

It's your challenge, so you get to make the rules as you see fit. I'll happily agree to whatever classification you choose for them.
Find all posts by this user
Quote this message in a reply
04-27-2017, 02:11 PM
Post: #50
RE: Programming puzzles: processing lists!
I made TI-89 versions of some of these just to be obnoxious. Wink (Well, and also to get some use out of this thing; it's nice to program, even if it's a bit clumsy for basic number crunching.)

Most are implemented as functions, which can return a value. Some are implemented as a program, since you can't use SortA or SortD in a function, even on local variables. Lazy compiler design, I guess. (I implemented quicksort as a function in pure Basic, but it's a lot slower than the built-in operations.)

Note that I've used != in place of the "not-equals" character, <= and >= for the inequalities, and -> in place of the "STO" arrow.

#1
Code:
p1(x)
Func
Local i,m
dim(x)->m
For i,1,m
  If x[i]!=3 and x[i]!=5:Return "Invalid"
EndFor
Return x
EndFunc
Storing the dim(x) in a variable seemed to be faster than putting it right in the For loop condition. I'm guessing it evaluates the ending value expression at each pass. I could use seq() to process the list, but this allows an early exit on failure.

#2
Code:
p2(x)
Func
Return seq(when(x[i]=3,4,7),i,1,dim(x))
EndFunc
Storing the dim(x) in a variable made no difference here.

#3
Code:
p3(x)
Func
Local d,p
dim(x)->d
iPart(d/3)->p
Return augment(right(x,p),left(x,d-p))
EndFunc

#4
Code:
p4(x)
Func
Local c,i,d
dim(x)->d
1->c
For i,d,1,-1
  If x[i]=1 Then
    0->x[i]
  Else
    1->x[i]
    0->c
    Exit
  EndIf
EndFor
If c=1:augment({1},x)->x
Return x
EndFunc

#5
Code:
p5(x)
Func
Local i,d
dim(x)->d
For i,d,1,-1
  If x[i]=0 Then
    1->x[i]
  Else
    0->x[1]
  Exit
EndIf
EndFor
Return x
EndFunc

#6
Code:
p6(x)
Prgm
Local y,c,l,i,d,t
If dim(x)=0:Goto e
x->y
0->c
SortA y
y[1]->l
dim(y)->d
0->t
For i,1,d
  If y[i]=l Then
    c+1->c
  Else
    If t=0 Then
      c->t
    ElseIf c!=t Then
      Goto i
    EndIf
    1->c
    y[i]->l
  EndIf
EndFor
If c!=t and t!=0:Goto i
Lbl e
Disp x
Return

Lbl i
Disp "Invalid"
EndPrgm

#7
Code:
p7(x)
Func
Local d,h
dim(x)->d
iPart(d/2)->h
Return augment(augment(left(x,h),{-1}),right(x,d-h))
EndFunc

#8
Code:
p8(x)
Func
Local d
dim(x)->d
If mod(d,2)=1:Goto i
If d=0:Return x
If left(x,d/2)=right(x,d/2):Return x
Lbl i
Return "Invalid"
EndFunc
[code]

#9
[code]p9(x)
Func
Local k,i,d
dim(x)->d
If d=0:Return x
If x[1]!=3:Goto i
1->i

Loop
  If x[i]!=3 Then
    i-1->k
    Exit
  EndIf
  i+1->i
  If i>d:Goto i
EndLoop

Loop
  If x[i]!=5 Then
    If (i-1)/2!=k:Goto i
    Exit
  EndIf
  i+1->i
  If i>d:Goto i
EndLoop

Loop
  If x[i]!=3:Goto i
  i+1->i
  If i>d Then
    If (i-1)/3!=k:Goto i
    Exit
  EndIf
EndLoop

Return x

Lbl i
Return "Invalid"
EndFunc

#10
Code:
p10(x)
Prgm
Local y,n,c,d,i
x->y
SortA y
dim(y)->d
If d=0:Goto v
0->c
y[1]->n
If n!=iPart(n) or n<1:Goto i

1->i
While i<=d
  If y[i]!=n Then
    If c!=n:Goto i
    1->c
    y[i]->n
    If n!=iPart(n) or n<1:Goto i
  Else
    c+1->c
  EndIf
  i+1->i
EndWhile

If c!=n:Goto i

Lbl v
Disp x
Return

Lbl i
Disp "Invalid"
EndPrgm

Might attempt a few more of these later.
Visit this user's website Find all posts by this user
Quote this message in a reply
04-27-2017, 02:22 PM
Post: #51
RE: Programming puzzles: processing lists!
(04-25-2017 06:25 PM)DavidM Wrote:  I have no direct experience with GoferLists, so I'm not qualified to render any opinions on its performance. My comments were directed at the built-in list processing commands that UserRPL has. I believe GoferLists is SysRPL-based, so I see no reason it wouldn't perform at least as well as the built-in commands. Possibly better if the algorithms are optimized and/or special-cased in areas that the built-in ones aren't.

The performance of GoferLists is highly variable to put it mildly. Some functions are very slow, some are quite fast, and some are redundant duplicates of existing RPL functions. Still, I consider GoferLists to be essential for anyone doing list- or text-based programming on the HP 50.

John
Find all posts by this user
Quote this message in a reply
04-27-2017, 03:56 PM
Post: #52
RE: Programming puzzles: processing lists!
(04-26-2017 06:44 PM)DavidM Wrote:  
(04-26-2017 06:24 PM)pier4r Wrote:  David your new #3, #6, #7, #8 looks like variant C solutions (use whatever you like, not only list operations), am I wrong?

Ah wait there is the sub command, I have to check the Aur.

As soon as possible I will compare them to mine.

That wasn't my intent. I was actually trying to force myself to use list commands wherever I could.

I consider SUB to be a list command in this context, since I am giving it a list and expecting one in return.

Then it is variant A, my "rotate list" is a routine for lists but internally uses the stack, still I consider it variant A since it takes a list as input and returns a list as output. I quickly skimmed the code and missed it. I hope to find time to compare the result (and learn some technique as well). I still have to do the remaining challenges and also computing a suitable random testing generator for challenge #6 (for that I need to compute the probability that out of a random list, I get one valid for the challenge).

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
04-27-2017, 04:00 PM
Post: #53
RE: Programming puzzles: processing lists!
@Dave Britten: nice, I may join you since my ti 89 lays unused (but I would also like to find for it a more suitable role. Moreover if I use to many things at once I cannot have time for newRPL, there is a wiki to fill and source code to read).

@John Keith. Thanks for the info. I thought it was always faster or very similar to the basic built in procedures.

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
04-27-2017, 04:37 PM
Post: #54
RE: Programming puzzles: processing lists!
(04-27-2017 03:56 PM)pier4r Wrote:  I still have to do the remaining challenges and also computing a suitable random testing generator for challenge #6 (for that I need to compute the probability that out of a random list, I get one valid for the challenge).

Is there some reason you need to rely solely on chance for the testing? I simply created some supplemental programs to generate known-valid lists of sufficient size, and then slightly altered a duplicate to invalidate them.
Find all posts by this user
Quote this message in a reply
04-28-2017, 07:16 AM
Post: #55
RE: Programming puzzles: processing lists!
(04-27-2017 04:37 PM)DavidM Wrote:  Is there some reason you need to rely solely on chance for the testing? I simply created some supplemental programs to generate known-valid lists of sufficient size, and then slightly altered a duplicate to invalidate them.

Yes I do the same for debug. For performance testing slightly random stuff adds fun (plus let me refresh some concepts, you know when the probability is slim one reflects a bit about which corners could be cut for a faster check). Otherwise I can just post my solution and you can test it with your routines.

Moreover with random inputs (within the given constraints) I ensure a bit more that my algorithm is correct (it happened more than once to catch errors that I did not catched before).

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
04-28-2017, 03:40 PM (This post was last modified: 04-28-2017 04:01 PM by pier4r.)
Post: #56
RE: Programming puzzles: processing lists!
(04-26-2017 01:30 AM)DavidM Wrote:  Here's my attempt at #6:

I have problems with this one (clever function though! I still have to improve a lot to match the ideas). At the end one has \GSLIST that seems not to work when the list to sum is {1. } (I have approximate mode on, and at first I run tests with 10 elements, not 100, to see if I did everything correctly)

Could you confirm?

In the meanwhile I add a 0 to the result list (but it will add to the execution time) because { 1. 0. } works with \GSLIST .


Ok after the fix, your function fails when the entire list is composed by one element (like a 10 element list composed by 10 times 10).

The version I'm using is the following
Code:

    c6DavidM
    \<<
      @ 'src' is the source list
      @ 'tot' is the count of the current list element being checked
      1 \-> src tot
      \<<
        @ the source list has to have all equal numbers grouped together
        src SORT

        2 @ compare two at a time

        @ for each pair of elements:
        \<<
          IF
            @ are these both the same?
            ==
          THEN
            @ the numbers are equal, so increment the total for this number
            1 'tot' STO+
          ELSE
            @ the numbers are different, so leave the current running total for the
            @ result and start a new running total for the next number
            tot
            1 'tot' STO
          END
        \>>
        DOSUBS

        @ add the final total to the result list
        tot +

        @ at this point, we have a list result that shows the counts of
        @ each unique list element encountered

        @ convert the current result list to one that has:
        @ 0's for each pair of counts that matches
        @ 1's for each pair that doesn't match
        \<< \=/ \>> DOSUBS

        @ sum up all the integers in the above result.  If the total isn't 0, then
        @ the list didn't match the stated criteria.
        @\GSLIST "invalid" 'src' IFTE
        
        0 +
          @Pier: adding a 0 to the list because \GSLIST fail with lists of 1 element.
        \GSLIST 0 1 IFTE
          @Pier: normalize the result like my function to compare.
          @ 0 invalid, 1 valid.
      \>>
    \>>

The the input list generator can be found at the link below, it may provide quick debug possibilities.
So now I try to check your second attempt at #3 using the SUB command.

You #3 is very fast!

Recap:

Pier#1: avg: 50 lists of 100 elements 0.15 secs
DavidM#1 avg: 50 lists of 100 elements 1.94 secs
DavidM#2 avg: 50 lists of 100 elements 0.043 secs

Side question. The tester function is the following (the complete code is here)

Code:

    cTesterGeneric
    \<<
      10 @iterations
      10 @listSize
      { } @inputList
      \<< c1vaV1 \>>
       @c1FuncP
      \<< c1DavidM \>>
       @c1FuncDavidM
      \<< c2vaV1 \>>
       @c2FuncP
      \<< c2DavidM \>>
       @c2FuncDavidM
      \<< c3vaV1 \>>
       @c3FuncP
      \<< c3DavidM \>>
       @c3FuncDavidM
      \<< c4vaV1 \>>
       @c4FuncP
      \<< c4DavidM \>>
       @c4FuncDavidM
      \<< c5vaV1 \>>
       @c5FuncP
      \<< c5DavidM \>>
       @c5FuncDavidM
      \<< c6vaV1 \>>
       @c6FuncP
      \<< c6DavidM \>>
       @c6FuncDavidM
      0 @cFuncP
      0 @cFuncDavidM
      { } @timeListP
      { } @timeListDavidM
      { } @posCheckedListP
      { } @posCheckedListDavidM
      0 @listGenFunc
      \<< \<-listSize {3 5} getRandomListFromValues \>>
        @inputListGenC1
      \<< \<-listSize {3 5} getRandomListFromValues \>>
        @inputListGenC2
      \<< \<-listSize -10 10 getRandomList \>>
        @inputListGenC3
      \<< \<-listSize { 0 1 } getRandomListFromValues \>>
        @inputListGenC4
      \<< \<-listSize { 0 1 } getRandomListFromValues \>>
        @inputListGenC5
      \<< \<-listSize c6listGen \>>
        @inputListGenC6
      \->
      iterations
      \<-listSize
      inputList
      c1FuncP
      c1FuncDavidM
      c2FuncP
      c2FuncDavidM
      c3FuncP
      c3FuncDavidM
      c4FuncP
      c4FuncDavidM
      c5FuncP
      c5FuncDavidM
      c6FuncP
      c6FuncDavidM
      cFuncP
      cFuncDavidM
      timeListP
      timeListDavidM
      posCheckedListP
      posCheckedListDavidM
      listGenFunc
      inputListGenC1
      inputListGenC2
      inputListGenC3
      inputListGenC4
      inputListGenC5
      inputListGenC6
      \<<
        inputListGenC6 'listGenFunc' STO
        c6FuncP 'cFuncP' STO
        c6FuncDavidM 'cFuncDavidM' STO
      
        1 iterations
        START
          listGenFunc EVAL 'inputList' STO
          
          inputList cFuncP TEVAL
          @collect the timing
          OBJ\-> DROP
          'timeListP' SWAP STO+
          @ collect the pos checked.
          'posCheckedListP' SWAP STO+
          
          inputList cFuncDavidM TEVAL
          @collect the timing
          OBJ\-> DROP
          'timeListDavidM' SWAP STO+
          @ collect the pos checked.
          'posCheckedListDavidM' SWAP STO+
        NEXT
        
        timeListP
        posCheckedListP
        timeListDavidM
        posCheckedListDavidM
      \>>
    \>>

Now in the input functions, like inputListGenC6, I have to use a compiled variable otherwise the value of "listSize" is not recalled as I think.

For example in \<< \<-listSize c6listGen \>> the behavior when I use a plain "listSize" (instead of the compiled variable) is the following: listSize is saved as 'listSize' in the variable listSizeV of the c6listGen routine. Then in the routine:

\<< n \>> 'n' 1 listSizeV 1 SEQ
works.

While
listSizeV 2 *
returns the algebraic object 'listSize*2'

I thought that variables were properly seen by subprograms in a program, in this case I mean \<< listSize c6listGen \>> should see the value of the variable.
So I thought a compiled variable should not be necessary but so far I don't see a workaround (and I was lucky that so far all the other input functions worked without compiled variables, using only "listSize", that then got changed in compiled variable for challenge 6)

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
04-28-2017, 08:53 PM
Post: #57
RE: Programming puzzles: processing lists!
(04-28-2017 03:40 PM)pier4r Wrote:  I have problems with this one [#6]... At the end one has \GSLIST that seems not to work when the list to sum is {1. } (I have approximate mode on, and at first I run tests with 10 elements, not 100, to see if I did everything correctly)

Could you confirm?

I can definitely confirm -- you have provided perfectly legitimate input to the program and the approach I used simply doesn't work for that case. It actually falls apart in two separate ways, and I should have remembered both situations as I have hit upon both of them before. Specifically:

1) DOSUBS normally provides a list as its result, EXCEPT for when that list would be empty. In that situation, it doesn't return anything at all. While I disagree with how it works (I think it should return an empty list instead), this isn't the first time I've hit on this issue and I should have remembered it. Ouch. I need to take another look at how I do that first step to address it. It may also be an issue for some of my other submissions.

2) Yes, ΣLIST needs a list of at least 2 elements. I've run into this one before as well. Like I said, I need more practice with list processing on this platform! I think you've hit on the easiest patch for this (adding a 0).

(04-28-2017 03:40 PM)pier4r Wrote:  You #3 is very fast!

It is, because SUB on a list is very efficient. It really doesn't have to do much. The other challenges that I used SUB for will probably be very fast as well. If I didn't make some other silly mistake! Smile

(04-28-2017 03:40 PM)pier4r Wrote:  Side question.
[lots of code...]

Haven't spent a lot of time looking at this just yet, but my suspicion is that the issue has to do with which variables are already defined and which aren't when the code is parsed.

In your supplied code, you are referencing listSize in the program provided to the local var before the var has actually been created (it is created when the → step is executed). At that point, it is simply assumed to be a var name instead of the var itself (since it hasn't actually been created yet). That's probably why it shows up as 'listSize' instead of listSize when the code is run -- it wasn't a known variable when the code was compiled.
Find all posts by this user
Quote this message in a reply
04-28-2017, 09:51 PM (This post was last modified: 05-02-2017 06:33 AM by pier4r.)
Post: #58
RE: Programming puzzles: processing lists!
@DavidM: thanks for the answer, and yes I created this challenge also to force myself to think more in terms of list operations, that seems pretty optimized (at least, avoiding MAP) although, as you said, sometimes seems to return or complain for counterintuitive reasons. The point about the "variable not yet local" makes a lot of sense, but why then it works for the first 5 inputs, maybe it is luck.

I already linked the source file containing the entire code for my solutions, here, the code for single challenges will follow below (but likely will not be as updated as the linked file). Moreover once reminded about SUB, I tried to use it because a bit more practical in some cases than DOSUBS or DOLIST. (STREAM I cannot love it, aside for very simple stuff. Moreover I love the fact that one can just call operations between lists, like 'equal' . great function library from the 50g).

Average timings for 50 lists of 100 elements (note that I adapted the output of the DavidM functions to return 1 or 0 for easier comparison.
#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

#7
Pier: 0.050 s
DavidM: 0.053 s

I guess we do mostly the same approach

#8
Pier: 0.29 s (thanks David for the double check)
DavidM: 0.034 s

#9
Pier: 0.26 s
DavidM: 1.83 s

#10 (like #6)
Pier: 1.58 s (impressed that SUB overused is faster than __one__ DOSUBS)
DavidM: 2.77 s

As usual, results and timings on other platforms are welcomed.

#6 input gen
Code:

    c6listGen
    @ given alist of length 100 of positive integers
    @ ensure that every integer appears in the list a numbeer of times
    @ equal to its value.
    @ generates valid and invalid lists, with a naive approach
    
    @ok it seems correct.
    \<<
      0   @validValuesList
      0   @addedElements
      0   @elementToAdd
      0   @duplicatesAdded
      { } @resultList
      \->
      @input
      listSizeV
      @local var
      validValuesList
      addedElements
      elementToAdd
      duplicatesAdded
      resultList
      \<<
        @ plan v1
        @ Instead of partitioning a number, we make a more
        @ trivial approach. 
        @ We know that if the list size is 10, 10 times 10 would fill it,
        @ so we take all the numbers from 1 to 10. 11 would not fit by default
        @ for example.
        @ We then generate a list with all this numbers.
        @ We then randomize the list.
        @ We consume the elements of the list and we put them inside the resulting
        @ list a number of times equal to their value.
        @ Only few lists generated in this way will be valid, but
        @ it is better than a totally random approach, because it is more likely
        @ that a list composed by 1 and 9 (for a 10 size list) could happen.
        \<< n \>> 'n' 1 listSizeV 1 SEQ 
        'validValuesList' STO
        
        validValuesList listSizeV 2 * shuffleList
        'validValuesList' STO
        
        WHILE
          addedElements listSizeV <
        REPEAT
          validValuesList listHead
          'validValuesList' STO
            @ on the stack we have the first element of the valid elements (lvl 2)
            @ and the remaining list (this level 1)
          'elementToAdd' STO
          
          0 'duplicatesAdded' STO
          WHILE
            duplicatesAdded elementToAdd <
            addedElements listSizeV <
            AND
          REPEAT
            'resultList' elementToAdd STO+
            'addedElements' 1 STO+
            'duplicatesAdded' 1 STO+
          END        
        END
        
        @ for more testing, shuffle the list a bit
        @ too easy when sorted.
        resultList listSizeV 2 * shuffleList
      \>>
    \>>

#6
Code:

    @ given alist of length 100 of positive integers
    @ ensure that every integer appears in the list a numbeer of times
    @ equal to its value.
    
    @it seems correct
    
    @avg: 50 lists 50 elements 3.04 seconds.
    @ impressive how certain list operations are faster than one list operation plus many variables
    @ (see dosubs) rather than several smaller list ops (see challenge 10)
    \<<
      0 @value
        @note that the input are positive integers.
      0 @value2
      0 @valueRepetitions
      10 @ufValid
      \->
      @input
      inputList
      @local
      value
      value2
      valueRepetitions
      ufValid
      \<<
        ufValid SF
          @ we assume the list is valid
        
        inputList SORT
          @list sorted, easier to operate on it.
        1
          @taking one element at time 
        \<<
          IF
            ufValid FS?
          THEN
            'value2' STO
              @save the input value
              
            @debug ###
            @value2
            @value
            @valueRepetitions
            @debug ###
            IF
              value2 value ==
            THEN
              'valueRepetitions' 1 STO-
                @I always get tricked by the order of the STO-
              
              IF
                valueRepetitions 0 <
              THEN
                ufValid CF
              END
            ELSE
              IF
                valueRepetitions 0 ==
              THEN
                value2 'value' STO
                value2 1 - 'valueRepetitions' STO
              ELSE
                ufValid CF
              END
            END
          ELSE
            DROP
              @should just drop the read element
          END
        \>>
        DOLIST
        
        IF
          valueRepetitions 0 \=/
          @ended with an incomplete repetition value.
        THEN
          ufValid CF
        END
        
        ufValid FS?
        1 0
        IFTE
      \>>
    \>>

#7
Code:

  @ given an input list of even length of positive integers, put a -1 in the middle.
    
    @ it seems correct
    @ avg time 50 lists 100 elements 0.050 sec
    \<<
      \->
      @input
      inputList
      \<<
        inputList
        DUP SIZE
        -1 SWAP
        @ stack
        @ l3: input list
        @ l2: -1
        @ l1: size of the list (even)
        2 / 1 +
         @we want the position equal to size/2 + 1
        addElementInList
      \>>
    \>>

#8 input gen
Code:

    @ for challenge 8 list generator of lists that have
    @ sometimes the second part repeated, and sometimes not.
    \<<
      \->
      @input
      listSizeV
      \<<
        IF
          RAND 2 * IP
        THEN
          @if 1
          listSizeV 2 / 
          1 10 getRandomList
          DUP
          +
        ELSE
          listSizeV 1 10 getRandomList
        END
      \>>
    \>>

#8
Code:

    @ verify if an even list is made by two lists
    @ it seems correct
    @ avg time 50 lists of 100 elements: 0.029 secs
    \<<
      0
      \->
      @input
      inputList
      @local var
      listSizeV
      \<<
        inputList SIZE 'listSizeV' STO
        
        @ get first half
        inputList 
        1 
        listSizeV 2 / 
        SUB
        
        @ get second half
        inputList 
        listSizeV 2 / 1 +
        listSizeV
        SUB
        
        @subtract
        -
        
        @sum the resulting list
        \GSLIST 0 ==
        1 0
        IFTE
          @ 1 if valid result
          @ 0 otherwise
      \>>
    \>>

#9 input gen
Code:

    @ for challenge 9 list generator of lists
    @ list with 3 parts of equal size, sometimes with
    @ first and third part equal, all the parts made out
    @ of one integer repeated.
    \<<
      3 / IP 3 *
        @fixing the input when not multiple by 3
        @ int(input / 3) * 3
      \->
      @input
      listSizeV
        @assumed multiple by 3
        @if not, we fix it.
      \<<
        IF
          RAND 2 * IP
        THEN
          @if 1
          3
          listSizeV 3 /
          NDUPN DROP
          5
          listSizeV 3 /
          NDUPN DROP
          3
          listSizeV 3 /
          NDUPN 3 *
            @we reuse the 'n' left on the stack by NDUPN
          \->LIST
        ELSE
          listSizeV {3 5} getRandomListFromValues
        END
      \>>
    \>>

#9
Code:

    c9vaV1
    @ verify that a list has a structure { A B C}
    @ where A, B, C are sublists with same length.
    @ A and C are equal
    @ All three contains the repetition of the same positive integer.
    
    @it seems correct
    @ time 50 lists 100 elements: 0.26 sec
    \<<
      0  @listSizeV
      0  @tempElement
      0  @firstThird
      0  @secondThird
      0  @thirdThird
      \->
      @input
      inputList
      @local var
      listSizeV
      tempElement
      firstThird
      secondThird
      thirdThird
      \<<
        inputList SIZE 'listSizeV' STO
        
        @extracting the parts
        inputList
        1 listSizeV 3 /
          @it is assumed that the list size is of the proper length
          @otherwise checks should be added.
        SUB 'firstThird' STO
        
        inputList
        listSizeV 3 / 1 +
        listSizeV 3 / 2 *
        SUB 'secondThird' STO
        
        inputList
        listSizeV 3 / 2 * 1 +
        listSizeV 
        SUB 'thirdThird' STO
        
        IF
          firstThird thirdThird ==
        THEN
          @the first and the last third are equal, but now we need to know
          @ if they are made of the proper elements.
          
          firstThird DUP HEAD -
          secondThird DUP HEAD -
          +
          thirdThird DUP HEAD -
          +
          \GSLIST 0 ==
            @ if all the three parts are composed by the same element
            @ thanks to the neat built in functions
            @ subtracting the head element from the list returns a list of 0
            @ adding all those lists together
            @ and then summing them with \GSLIST
            @ if it is equal to zero means that all is good.
            @ otherwise not.
          1 0
          IFTE
        ELSE
          0 @invalid
        END
      \>>
    \>>

#10
Code:

    c10vaV1
    @ actually like challenge #6 but I want to approach differently
    @ because, different approaches may give more ideas or at least more fun
    @ or more data.
    
    @ it seems correct
    @avg: 50 lists 50 elements 1.58 seconds.
    \<<
      
      0  @curElement
      1  @curFirstPos
      0  @listSize
      10 @ufValid
      \->
      @input
      inputList
      @local var
      curElement
      curFirstPos
      listSize
      ufValid
      \<<
        ufValid SF
          @assuming good result.
        inputList SIZE 'listSize' STO
          @we save the last position that at the start is the size of the list.
          
        inputList SORT 'inputList' STO
          @we sort the list
        
        @ now we extract the elements and we assume that they are repeated
        @ enough times, and we extract sublists to check if those
        @ are really composed by the repeated subelements.
        inputList HEAD 'curElement' STO
        
        WHILE
          ufValid FS?
          curFirstPos listSize \<=
            @we don't want to go over the borders.
          AND
        REPEAT
          inputList
          curFirstPos
          curFirstPos curElement + 1 -
            @ { 1 4 4 4 4} we want to extract from 2 to 5, not from 2 to 6
          SUB
          curElement -
            @if the extracted sublist is composed by repetition of the element
            @it will be equal to all zero.
            @ so we compare to a list of the same type
            @ (this because \GSLIST is not so reliable with list of one element)
            @ note that SUB returns an empty list when the index for the extraction
            @ are "outside the list"
          0 curElement NDUPN \->LIST
          
          IF
            ==
          THEN
            curFirstPos curElement + 'curFirstPos' STO
              @ ideally, if it is valid until the end,
              @ this will overflow the list size of 1
            IF
              curFirstPos listSize \<=
            THEN
              inputList curFirstPos GET 'curElement' STO
            END
          ELSE
            ufValid CF
          END
        END
        
        @result
        ufValid FS?
        1 0
        IFTE
      \>>
    \>>

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
04-29-2017, 08:28 AM
Post: #59
RE: Programming puzzles: processing lists!
(04-28-2017 08:53 PM)DavidM Wrote:  DOSUBS normally provides a list as its result, EXCEPT for when that list would be empty. In that situation, it doesn't return anything at all.

Look here for DOSBS and DOLST programs to replace DOSUBS and DOLIST, without those quirks.

Cheers, Werner

41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE
Find all posts by this user
Quote this message in a reply
04-30-2017, 02:31 PM (This post was last modified: 04-30-2017 05:09 PM by pier4r.)
Post: #60
RE: Programming puzzles: processing lists!
New solutions and timings.

#11
50 lists of 100 elements, average time
Pier: 0.054 s
David: 0.047 s

#13 (this is an interesting one)
50 lists of 100 elements, average time
Pier: 4.03 s

#11 input generator
Code:

    c11listGen
    @ it seems to work
    \<<
      0 @resultList
      \->
      @input
      listSize
      @local var
      resultList
      \<<
        IF
          RAND 2 * IP 
        THEN
          @make a list palindrome
          
          @first half
          listSize 2 / IP 
          1 listSize
          getRandomList
          DUP
            @it will leave a copy on the stack
          'resultList' STO
          
          IF
            listSize 2 MOD 0 \=/
          THEN
            @add a random number in the middle
            
            RAND listSize * IP 1 +
            +
          END
          
          @add the first half reverted
          resultList REVLIST
          +
          @ the result list is already on the stack, no more actions needed.
        ELSE
          listSize
          1 listSize
          getRandomList
        END
      \>>
    \>>

#11
Code:

    c11vaV1
    @ given a list of positive integers, verify that it is palindrome
    @ it seems to work
    
    @timings: 50 lists of 100 elements 0.054 secs
    \<<
      0 @inputListSize
      \->
      @input
      inputList
      @local var
      inputListSize
      \<<
        inputList SIZE 'inputListSize' STO
        
        @ if the number of elements are odd, the central one will stay there,
        @ so no problem.
        
        @ extract the first half of the list
        inputList
        1 inputListSize 2 / IP
        SUB
        
        @extract second part
        inputList
        @starting point
        IF
          inputListSize 2 MOD 0 ==
        THEN
          inputListSize 2 / 1 +
        ELSE
          inputListSize 2 / IP 2 +
          @ 1 2 3 4 5 6 7 , we want to start from 5
        END
        @end point
        inputListSize
        SUB REVLIST
        
        @ now on the stack we have the first part of the list
        @ and the second part reverted.
        @ we check if they are equal.
        ==
        1 0
        IFTE
      \>>
    \>>

#13 input generator and code
Code:

    c13incrListValueWithLimitHelp
"input:
L2: reference list to define the max value for every position
L1: list to increase, same size of reference list

output:
L1: list increased according to the limit of the reference list.
If overflow, all zeroed.
"
    
    c13incrListValueWithLimit
    @ given a reference list for a max value
    @ add 1 to a given list, and perform carry operations
    @ if the increased element in the list "hit" the maximum
    @ value in the reference list.
    @ The reference list and the input list are incremented
    @ right to left like numbers, although in some cases this may be not
    @ necessary, but this means that the procedure may be reused also to
    @ compute numbers in base N exploded, digits by digits, in a list
    
    @it seems working.
    \<<
      0  @currValue
      0  @currRefValue
      10 @ufCarry
      \->
      @input
      referenceList
        @ like { 2 2 3}
      listToIncrease
        @ like { 2 0 1} output { 2 0 2}
      @local var
      currValue
      currRefValue
      ufCarry
      \<<
        @ reverse the lists to process them from the "lower" digit
        @ assuming that the input consider lower digits the end digits
        referenceList REVLIST 'referenceList' STO
        listToIncrease REVLIST 'listToIncrease' STO
        
        ufCarry SF
          @ we need to carry the operation.
        
        listToIncrease
        1 @one element at time
        \<<
          IF ufCarry FS? THEN
            'currValue' STO
            
            IF
              currValue 1 +
              referenceList NSUB GET
              >
            THEN
              0 @ produce a zero
            ELSE
              @ increment and stop
              currValue 1 +
              ufCarry CF
            END
          END
          @ otherwise we leave the read value as it is
        \>>
        DOSUBS
        
        IF
          ufCarry FS?
        THEN
          @total reset
          DROP
          
          0
          referenceList SIZE
          NDUPN
          \->LIST
        ELSE
          @do not forget that the list were reverted
          REVLIST
        END
      \>>
    \>>
    
    c13factorsCompositionHelp
"input:
L1: a positive integer

output:
L1: list of all evently divisors of the number, the number itself excluded
but 1 included.
"
    
    c13factorsComposition
    @ given a number in input
    @ retrieve the factors of the number
    @ and then the posible compositions.
    @ For example 100 -> 2, 4, 5, 10, 20, 25, 50, 100 (the last excluded since it is not interesting)
    @ this using the multiplicity of the factors and increasing it.
    
    @ it seems working.
    \<<
      0 @sf3
      0 @sf105
      {}      @factorsResult
      {}      @factorsElements
      {}      @factorsMultiplicity
      {}      @currentCombList
      { 1 }   @resultList
      \->
      @input
      inputNumber
      @local var
      sf3
      sf105
      factorsResult
      factorsElements
      factorsMultiplicity
      currentCombList
        @current combination of multiplicity list
      resultList
      \<<
        -3 FS? 'sf3' STO
          @ either 0 when clear, or 1 when set.
        -3 CF
          @this for factors and ISPRIME
        
        -105 FS? 'sf105' STO
        
        inputNumber \->Q FACTORS 'factorsResult' STO
        
        IF
          -105 CF
            @this for ISPRIME
          inputNumber ISPRIME?
          -105 SF
            @ speed up
        THEN
          @only one factor, the entire list
          @since it is not interesting, return the basic factor, 1
          resultList
        ELSE
          @there are more than one factor, so let's iterate on the
          @possible combinations of factors.
          
          @extract the factor list
          factorsResult
          1
          \<<
            @they are in odd positions
            IF
              NSUB 2 MOD 0 ==
            THEN
              DROP
            END
          \>>
          DOSUBS
          'factorsElements' STO
          
          @extract the multiplicity list
          factorsResult
          1
          \<<
            IF
              NSUB 2 MOD 1 ==
            THEN
              DROP
            END
          \>>
          DOSUBS
          'factorsMultiplicity' STO
          
          @the hp 50g functions library is awesome.
          @ if I have list A and list B, I can do A^B
          @ and every element of A gets the power of the corresponding element of B.
          @ How much "I have to do it on my own, or I need to search" is saved.
          
          0 factorsMultiplicity SIZE NDUPN \->LIST 'currentCombList' STO
            @the variable containing the actual exponentiations
          DO
            factorsMultiplicity
            currentCombList
            c13incrListValueWithLimit
            'currentCombList' STO
            
            'resultList'
            factorsElements currentCombList ^
            1 +
            \PILIST
              @product. profuct list and sumlist complain for list of size 1, so we always add a 1
              @ (in the case of the produt) to the list to be used. So there are always two
              @ elements.
            STO+
          UNTIL
            currentCombList
            factorsMultiplicity
            ==
              @we stop when the current list it is exactly like the
              @multiplicity list (it means we are finished)
          END
            
          @we pop out the tail, since it should be the number itself
          resultList
          tailList
          DROP
            @real result list on the stack
        END
          
        IF sf3 THEN
          -3 SF
        ELSE
          -3 CF
        END
        
        IF sf105 THEN
          -105 SF
        ELSE
          -105 CF
        END
      \>>
    \>>
    
    c13listGen
    @ produce list generated by sublists sometimes.
    @ it seems to work
    \<<
      0 @subSize
      0 @resultList
      \->
      @input
      listSize
      @local var
      subSize
      resultList
      \<<
        IF
          RAND 2 * IP 
        THEN
          @make a list generated by a sublist
          
          @random feasible size for the sublist
          listSize c13factorsComposition
            @list of possible sizes for sublists
          DUP SIZE
            @ take the size
          RAND * IP 1 +
            @take a random value between 1 and size
          GET 
            @interesting GET accept several floats, I fixed with IP
            @ quite late.
          DUP 'subSize' STO
          1 listSize getRandomList
            @generate a random list of positive integers
          
          @now duplicate it enough times
          listSize subSize /
          NDUPN @it leaves the number of duplications on the list
          1 - @reduce it of 1
          1 SWAP
            @ stack: 1 numb_duplications_minus_one
          START
            + @concatenate lists
          NEXT
        ELSE
          listSize
          1 listSize
          getRandomList
        END
      \>>
    \>>
    
    c13vaV1
    @ given a list, finding the smallest generating sublist starting from the head
    @ of the main list.
    
    @ since we know the size of the size of the list, the generating sublist is
    @ one of the possible composition of the factors of the size of the list.
    @ That is, if the listSize is a prime number, no sublists exists.
    
    @timings: 50 lists of 100 elements 4.03 s
    \<<
      0    @listSizeV
      0    @possibleSubLengths
      0    @listSize2
      0    @sublistLength
      1    @counter
      0    @testingSublist
      11   @ufValid
      \->
      @input
      inputList
      @local var
      listSizeV
      possibleSubLengths
      listSize2
      sublistLength
      counter
      testingSublist
      ufValid
        @ TODO:
        @ to use the same user flag I should use store and save flags in every program
        @ and subprogram, so I never have conflicts of values in flags.
      \<<
        inputList SIZE 'listSizeV' STO
        
        @ we get the possible sublist lengths
        listSizeV c13factorsComposition
        DUP SIZE 'listSize2' STO
        'possibleSubLengths' STO
        
        ufValid CF
        
        @then we consume the list of possible length checking if they
        @match the original list
        WHILE
          counter listSize2 \<=
          ufValid FC?
          AND
            @if the counter is within the list size and no valid
            @sublist are found.
        REPEAT
          @extract the sublist made out of the amount of elements specified
          @by the possible length list
          
          possibleSubLengths counter GET 'sublistLength' STO
          
          inputList
          1 sublistLength
          SUB
            @sublist on the stack
          
          @ now we replicate the sublist to match the list length
          listSizeV sublistLength /
          NDUPN
            @this leaves the number of replications on the stack
          1 - @decrementing it of one.
          1 SWAP
            @ stack: 1 number_of_repetitions_minus_one
          START
            +
              @concatenate the sublists
          NEXT
          
          @we have the sublist concatenated on the stack
          @now we compare with the original
          IF
            inputList ==
          THEN
            ufValid SF
            listSizeV sublistLength /
              @the result is "how many sublists"
          ELSE
            1 'counter' STO+
          END
        END
        
        IF ufValid FC? THEN
          0
            @0 generating sublists
        END
      \>>
    \>>






added also #16 and #17 as processing list challenges (and the more "list things" I see, the more I will add. Of course I know that I miss a lot of possible challenges that I don't see at the moment, but those are ok)

#16
Code:

    c16vaV1
    \<<
      { 0 8 8 2 }  @mult117
      { 1 3 4 }    @primeN
      { 6 4 0 9 }  @intCubed
      0 @iterations
      0 @stoFlags
      \->
      mult117
      primeN
      intCubed
      iterations
      stoFlags
      \<<
        RCLF 'stoFlags' STO
        @-3 SF
      
        @ multiple117
        @ I could compute multiples of 117 until I get the right digits
        @ but I need to convert a number in digits then.
        @ so let's try with permutations. I could write a function
        @ to return all the permutations of a list, but so far I put it
        @ in the todo. So we do random permutations (shuffle) of a list.
        @ it will eventually hit the mark.
        WHILE
          mult117 { 1000 100 10 1 } *
          \GSLIST
          117 MOD 0 \=/
        REPEAT
          mult117 8 shuffleList
          'mult117' STO
          1 'iterations' STO+
        END
        
        iterations
        mult117    
        
        0 'iterations' STO
        WHILE
          primeN { 100 10 1 } *
          \GSLIST
          ISPRIME? NOT
        REPEAT
          primeN 8 shuffleList
          'primeN' STO
          1 'iterations' STO+
        END
        
        iterations
        primeN
        
        0 'iterations' STO
        WHILE
          intCubed { 1000 100 10 1 } *
          \GSLIST
          3 XROOT
            @now we have the cube root of the value
          FP 0 \=/
            @continue until the cube root is not returning an integer.
        REPEAT
          intCubed 8 shuffleList
          'intCubed' STO
          1 'iterations' STO+
        END
        
        iterations
        intCubed
        
        stoFlags STOF
      \>>
    \>>

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
Post Reply 




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