@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
\>>
\>>
Search
Member List
Calendar
Help
/
Programming puzzles: processing lists!
