+- 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)
Programming puzzles: processing lists! - pier4r - 04-19-2017 09:20 PM
(let me know if it is not clear or there are mistakes or also duplicates with problems already existing in other threads)
I thought the following for the userRPL but I do believe other calculators / programming modes would fit too.
The challenges are not so difficult to be solved, but are difficult to be solved quickly for fairly large list (100+ elements). Of course for sysRPL or other calculators the size where things need to be optimized changes. You can propose a certain size for fast environments.
Feel free to pick any of the challenges, or even none
. At least I will try to solve them slowly.Note(s):
- it is presumed that the the minimum size of the input list adapts to fit the challenge, but it is never lower than 100 or, in case of large computations, 10. Unless it is otherwise stated.
#1
Input: a list of 3s and/or 5s
Output: the input list, if 3s and 5s as alternated in the input list. Otherwise the input list followed by "invalid".
Example(s):
{ 3 5 3} -> { 3 5 3}
{ 3 5 3 3 5 } -> { 3 5 3 3 5 } invalid
{ 3 5 3 5 3 5 3 5 } -> { 3 5 3 5 3 5 3 5 }
#2
input: a list of 3s and/or 5s
output: the input list, but for every 3 put a 4 and for every 5 a 7.
Example(s):
{ 3 5 3 3 5 } -> { 4 7 4 4 7 }
#3
input: a list of integers
output: the last floor(list_size/3) element of the list at the beginning
Example(s):
{ 3 5 3 3 5 4 5 7 3 -1 6 } -> { 3 -1 6 3 5 3 3 5 4 5 7}
#4
input: a list of 0s and/or 1s
output: treating the input list as a binary number, add 1 to it. Produce the resulting list.
Example(s):
{ 0 0 0 1} -> { 0 0 1 0 }
{ 0 1 0 0} -> { 0 1 0 1 }
{ 1 1 1} -> { 1 0 0 0 } (thanks Han)
#5
input: a list of 0s and 1s (at least one 1).
output: treating the input list as a binary number, subtract 1 to it. Produce the resulting list.
Example(s):
{ 0 0 1 0 } -> { 0 0 0 1}
{ 0 1 0 1 } -> { 0 1 0 0}
#6
input: a list of positive integers.
output: verify that every integer in the list appears the same amount of times. Produce the list if true and "invalid" if false.
Example(s):
{ 1 2 3 3} -> "invalid"
{ 1 2 3 1 2 3 1 2 3 1 2 } -> "invalid"
{ 1 2 3 1 2 3 1 2 3 1 2 3 } -> { 1 2 3 1 2 3 1 2 3 1 2 3 }
#7
input: given a list, of even length, of positive integers.
output: the input list, but with a -1 in the middle
Example(s):
{ 1 2 3 3} -> { 1 2 -1 3 3}
{ 1 2 3 1 2 3 1 5 } -> { 1 2 3 1 -1 2 3 1 5 }
#8
input: given a list, of even length, of integers.
output: verify that the second half of the list is equal to the first half. If yes, produce the list, otherwise "invalid"
Example(s):
{ 1 2 3 3} -> "invalid"
{ 1 2 -3 1 2 -3 } -> { 1 2 -3 1 2 -3 }
#9
input: given a list of 3s and/or 5s.
output: verify that the input list has K 3s at the beginning, then K 5s, then K 3s again. For any K. If yes, produce the list, otherwise "invalid"
Example(s):
{ 3 3 3 3 5 3 } -> "invalid"
{ 3 3 3 5 5 5 3 3 3 } -> { 3 3 3 5 5 5 3 3 3 }
{ 3 3 3 3 3 5 5 5 5 5 3 3 3 3 3 } -> { 3 3 3 3 3 5 5 5 5 5 3 3 3 3 3 }
#10 (similar to #6 actually)
input: given a list of positive integers.
output: verify that the input list has exactly N times the integer N when N is in the list. Produce the list if yes, otherwise "invalid"
Example(s):
{ 1 1 2 2 3 3 } -> "invalid"
{ 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 } -> { 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 }
{ 1 3 3 3 7 7 7 7 7 7 7} -> { 1 3 3 3 7 7 7 7 7 7 7}
{ 7 7 1 7 3 7 7 3 7 3 7 } -> { 7 7 1 7 3 7 7 3 7 3 7 }
#11
input: given a list of positive integers.
output: verify that the input list is palindrome. Produce the list if yes, otherwise "invalid"
Example(s):
{ 1 2 3 3 1} -> "invalid"
{ 1 2 3 3 2 1} -> { 1 2 3 3 2 1}
{ 1 2 3 2 1} -> { 1 2 3 2 1}
#12 (Han saw that is similar to the #2, so feel free to pick one)
input: given a list of 3s and/or 5s.
output: transform a 3 in a 5 and a 5 in a 3.
Example(s):
{ 3 3 3 3 5 3 } -> { 5 5 5 5 3 5 }
#13 (thanks Han for the observations)
input: given a list of positive integers.
output: verify that the list is made up by the repetition of a sublist (the smaller generating sublist). Of course the case that the generating sublist is equal to the entire list is not interesting. Another point is that a sublist is generated by consecutive elements of the list, and we do not consider rotations. For example using the generating sublist { 1 2 3 } it is not allowed to produce this { 3 1 2 3 1 2 3 1 2 } . So necessarily the sub list if existing, starts from the head of the main list.
Return the number of times the generating sublist appears, "invalid" otherwise.
Example(s):
{3 3 3 3 3} -> 5
{3 3 3 3 3 4} -> "invalid"
{ 1 2 3 4 1 2 3 4 1 2 3 4} -> 3
{ 1 2 1 2 1 2 1 2 } -> 4
#14 (once again, thanks Han)
input: given a list of positive integers between 1 and 9 with __one__ 0.
(Han saw that if we do not limit the integers the chances to go in overflow are high. With integers between 1 and 9 one has still the chance to go in overflow, but not so easy)
output: given the max value in the list, say M. Compute the value of the part of the list before 0, interpreted as number in base (M+1), and then the value of the part of the list after 0 as number in base (M+1). Return the difference in base 10 as list of digits. Note that one has to multiply the digits by the proper power of 10, therefore is the difference is -1111 the digits are { -1 -1 -1 -1}
Example(s): (I hope I'm not making mistakes here)
{ 1 2 3 0 1 2 } -> { 2 1 }
{ 3 4 2 1 0 5 6 7 5} -> {-1 -1 -9 -6 }
#15
input: given a list of positive integers with __one__ 0.
output: given the max value in the list, say M. Compute the value of the part of the list before 0, interpreted as number in base (M+1), and then the value of the part of the list after 0 as number in base (M+1). Return the sum, but as a list representing the number in base M+1.
{ 1 2 3 0 1 2 } -> {1 1 1} (base 4)
{ 3 4 2 1 0 5 6 7 5} -> { 1 1 3 1 6 } (base 8)
#16
input: numbers of this challenge as element of a list so 0882 is { 0 8 8 2}
- find a multiple of 117 that has the digits 0882
- find a prime number that has the digits 1 3 4
- find a cube of an integer that has the digits 6 4 0 9
output: The answers.
#17 (thanks for the note David)
input: a list of 4 positive integers
output: all the permutations of the list, In list form or in number, except the initial one.
For example { 1 2 3 4 } a permutation is { 2 3 4 1} or 2341
#18
input: all the list between { 1 0 0 0 } and { 9 9 9 9 } (list of digits between 1000 and 9999)
output: compute all the middle square sequences with seeds of 4 digits (see here ), stopping a sequence if the new "seed" is equal to the old one or if the sequence is longer than 10000 steps.
Example(s):
Sequence starting from { 1 8 4 2 }
Code:
. 1842^2 = 3392964
. considering it with 8 digits (if necessary with leading zeroes)
. 03392964
. taking the 4 middle digits
. 03[3929]64
. new step { 3 9 2 9 }
. 3929^2 = 15437041
. 15437041 ->15[4370]41
. new step {4 3 7 0}
. further steps (compact)
. 4 3 7 0 -> 0969
. 9 6 9 -> 9389
. 9 3 8 9 -> 1533
. 1 5 3 3 -> 3500
. 3 5 0 0 -> 2500
. 2 5 0 0 -> 2500 # stop, new step equal to the old one.#18.1
Bonus of the #18 . Like the #18 but a lookup table for computations, when possible.
#19
input: considering lists as collection of digits in base 10 for integers (so no decimals, also leading zeroes are allowed)
output: given two lists, representing two numbers, produce:
addition
subtraction (by convention, the subtraction puts a minus sign on all the digits)
multiplication
integer division
(positive integer) power.
Example(s):
{ 1 0 1 0} addition { 5 0 } = { 1 0 6 0 }
{ 1 0 1 0} subtraction { 1 0 5 0 } = { -0 -0 -4 -0 } or { -4 -0 }
{ 1 0 1 0} multiplication { 5 0 } = { 5 0 5 0 0 }
{ 1 0 1 0} (int) division { 5 0 } = { 2 0 }
{ 5 3 } (pos int) power { 3 } = { 1 4 8 8 7 7 }
#20
(variant of this)
Input: a list of sublists. Every sublist is made out of 3 elements { A B C }.
A identifies a point (or a node on a graph), B identifies another point different from A, C identifies the connection between those two points. the nodes are identified by positive integers. The minimum positive integer for a node is 1, the maximum positive integer for a node is not greater than the square root of the size of the list in input. So if the list is long X elements (sublists) the maximum node can have an index that is 2*sqrt(X) rounded to the next integer.
A connection can be of type 1, 2 or 3. (handy numbers because those numbers can be derived from one another, like 1 + 2 = 3)
Type 1 allows only the goods of type 1 to pass, type 2 allows only the goods of type 2 to pass, type 3 allows both goods of type 1 and 2 to pass.
A sublist { A B C } is different from { B A C } it means that the graph is a directed graph.
Information may be duplicated, that is: { A B C} may appear multiple times in the input, of course the information contained in it counts only once. It may also happen that there exist { A B 1}, { A B 2} and { A B 3} in the list (multiple times), of course the higher information will be consider. This means that { A B 1 } and { A B 2 } can be converted to { A B 3} so all the rest is redundant. When there are { A B 1 } and { A B 3} then { A B 1 } is redundant.
Output: a list of nodes that can reach every other node in the list sending goods of type 1 or type 2. (it should be a clique in graph terms)
Example(s):
- input:
{ { 1 2 3 } { 2 3 1 } { 3 4 2 } {4 5 1 } { 5 4 2 } { 5 6 3 } { 2 6 3 } { 6 1 3 } }
- output { 1 2 6 }
- input:
{ { 1 2 3 } { 2 3 1 } { 3 4 2 } {4 5 1 } { 5 4 2 } { 5 6 3 } { 2 6 2 } { 6 1 3 } }
- output { } or 0 .
#21 Remove duplicates from a list
Input: a list of positive integers
output: the input, with duplicated removed, retaining relative positions of the first appearance of a number. (one can attack the simplified version first - no retain of the relative positions)
Example(s):
{ 1 2 3} -> { 1 2 3}
{ 1 1 2 3 } -> { 1 2 3 }
{ 1 2 3 1 2 3 } -> { 1 2 3 }
{ 1 3 2 2 2 3 3 3 3 3 2 1 } -> { 1 3 2}
#22
By product of #20.
Given two list of positive integers. Add the elements (with equal position in the lists ) if those are different, don't add if those are equal.
Example(s):
{ 1 2 3 } + { 2 2 2 } = { 3 2 5 }
{ 1 2 3 } + { 1 2 3 } = { 1 2 3 }
#23
Given a list of positive integers between 1 and 9.
Every element bigger than 0 can "jump" to the left or to the right of a number of positions equal to its value (of course without exceeding the limit of the list). If the number jumps in a position occupied by another number, the destination position gets incremented, while the source position gets zeroed.
Zeroes cannot be a destination. Only places with positive numbers.
The challenge is to find an algorithm that ensures that either there is a way
to end up with one position having the sum of all the numbers in the list, (printing the moves) or not.
Example(s):
{ 1 2 1 2 1 2 1 1 2 1 1 1} -> { 0 3 1 2 1 2 1 1 2 1 1 1} -> { 0 0 1 2 4 2 1 1 2 1 1 1} -> { 0 0 1 2 4 2 1 1 2 1 2 0} -> { 0 0 1 2 4 2 1 1 3 0 2 0} -> { 0 0 1 2 4 2 1 1 5 0 0 0} -> { 0 0 0 3 4 2 1 1 5 0 0 0} -> { 0 0 0 3 4 2 0 2 5 0 0 0} -> { 0 0 0 3 4 0 0 4 5 0 0 0} -> { 0 0 0 7 4 0 0 0 5 0 0 0} -> { 0 0 0 12 4 0 0 0 0 0 0 0} - no more possible moves, this sequence of choices is not working because we have 2 elements greater than 0.
##
due to those challenges DavidM started to create a new library in SysRPL to handle list processing, that is a great byproduct of this contest!
Moreover, although I suppose that several libraries of commands for processing lists - developed in RPL - exists and are available in public domain through forums, newsgroups, hpcalc.org, personal web sites, pdfs (see one minute marvels) and what not , I decided to be inspired at first by the commands created by David to define more challenges, even though some may be short. (I also guess that a lot of effort, unfortunately, was never shared by the authors about a lot of useful programs and knowledge)
#24 (inspired by LEQ)
Input: two lists of positive integers.
Output: report the numbers of mismatches between the two lists. That is, if the two lists have the same elements (although in different positions) it returns 0, otherwise the number of mismatching elements.
Example(s):
{ 1 2 3 } { 3 2 1 } -> 0
{ 1 2 3 4 } { 1 2 3 } -> 1
{ 1 2 3 } { 1 2 3 4 } -> 1
#25 (inspired by LCNT)
Input: two lists of positive integers, L1 and L2.
Output: the score computed by the following procedure.
- Given an element that is in L1 but not in L2, increment the score by the value of the element in the same position in L2. (remember L2 is not empty by the premise of the challenges). If L2 is smaller than L1. Use the position modulo the size of L2 to find a position in L2.
- Given an element that is in L2 but not L1, reduce the score by the element in L1 that is in the same position of the element in L2. If L1 is smaller than L2, use the same procedure above but to find the position in L1.
- Given an element that is both lists. Compute appearances_in(L1) - appearances_in(L2) then multiply the result by the sum of the elements in the positions of the occurrences of the element, in the list where the element is most numerous, of the list that has less occurrences of the element. If one list is smaller than another, use the modulo as explained above. Then add the result to the score.
Example(s):
{ 1 2 3 } { 1 2 3 } -> 0
{ 1 2 3 4 } { 1 2 3 } -> 1 (pos 4 modulo 3 = pos 1, pos 1 = 1)
{ 1 1 1 2} { 1 2 } -> 8 ( L1 has 3 ones, while L2 only 1. So the difference of occurrences is 2. Then the sum of the elements in L2 that are in the same position of the ones in L1 is 1+2+1 (the last one using the modulo). Therefore 4+2 = 8 )
{ 1 2 } { 4 5 6 } -> 5 ( 4 + 5 minus 1+2+1)
#26 (inspired by LGRP )
Input: a list of positive integers.
Output: return the same list pruning consecutive repetitions, only leaving the first element of the repetition.
Example(s):
{ 1 2 3 } -> { 1 2 3 }
{ 1 2 3 2 2 3 3 3 1 } -> { 1 2 3 2 3 1 }
#27 (inspired by LREPL )
Input: a list of positive integers, a list of positions, a list of sublists of the same number of the list of positions
Output: the original list expanded with the sublists inserted starting from the position mentioned in the list of positions
Example(s):
{ 1 2 3 } { 1 2 8 } { { 1} {1 3 } { 5 3 2 } } -> { 1 1 3 1 2 3 5 3 2 } (8 is too big and is capped to the last position like a +)
#28 (inspired by LDST )
Input: a list of positive integers
Output: grouping those integers in two sublists that shows the closest difference in terms of sums. If more than one result is possible, return only one of them.
{ 1 2 3 4 5 6 } -> { 1 2 3 4 } { 5 6 }
Example(s):
{ 1 2 3 4 5 6 } -> { 1 2 3 4 } { 5 6 }
#28b
Input: a list of positive integers
Output: given the sum of the elements of the list, find the smallest factor that divides the sum (if the result is prime, add one to the list, and to the sum), then split the list in a number of sublists equal to this factor in a way that the sum of the differences of the sum of every sublist is minimal. If the smallest factor is bigger than the list itself (say the smaller factor is 7 and the list is only size 6), then report it to the user and reject the task. If more than one result is possible, return only one of them.
Example(s):
{ 1 2 3 4 5 6 } -> 21, can be divided by 3. { 1 6 } { 2 5 } { 3 4} , all the differences are 0.
{ 1 2 3 4 5 8 } -> 23, prime, adding +1 { 1 2 3 4 5 8 1 } , to divide in two lists. { 4 8 } { 1 1 2 3 5 } , difference 0.
#29 (inspired by rolling a dice K times and finding repetitions)
Input: a list of positive integers L1, a second list of positive integers L2.
Output: find all the cases the list L2 appears in the list L1 returning the first index of a match.
Example(s):
{ 1 2 3 4 4 2 3 } { 2 3 } -> { 2, 6 } ( { 2 3 } appears starting from index 2 and 6 )
{ 5 4 1 1 1 } { 1 } -> { 3 4 5 }
{ 5 4 1 1 1 } { 1 1 } -> { 3 4 }
#30 (inspired by rolling a dice K times and doing statistics)
Input: two lists of positive integers, L1 and L2.
Output: the elements of L2 have a relationship with the elements of L1. We want to keep it and still order L2. Sothe poit is that the element L1j is related to the element L2j. Therefore we want L2 sorted, in ascending order. And L1 sorted as well to keep the relationship valid.
Example(s):
{ 7 6 7 } { 3 2 1 } -> { 7 6 7 } { 1 2 3 }
{ 3 18 2 3 7 } { 2 1 2 1 3} -> { 18 3 3 2 7 } { 1 1 2 2 3 } (note, if more than one element has the same value, like the 1s in the example, it is assumed that the first 1s relationship goes first, the second foes second and so on)
#31 frequencies
input: a list of positive integers L1
output: two lists (that could be also two columns of a matrix) L2 and L3. L2 is like L1 but with elements sorted and duplicates removed. L3 is the list that contains the occurrences of the elements of L2 in L1, obviously with corresponding positions
examples:
{ 2 3 2 3 1 2 } -> { 1 2 3 } { 1 3 2 }
#32 multiple GET
input: two lists of positive integers L1 and L2. L2 is the list of positions that we want to extract from L1 (note, positions can re repeated). Values in L2 cannot exceed the size of L1 of course.
output: the list of the elements that we want to extract
examples:
{ 5 4 3 2 1 } { 1 2 3 1 1 1 } -> { 5 4 3 5 5 5 }
#33 from list to balanced binary tree
(actually in #20 one could need to move from a list of connections to a list of lists, here we do the contrary).
input: a list of positive integers
output: a list of connections that represent a balanced binary tree. A connection is a sublist { S D } where S is the number of the source node, D is the number of the destination node. The root node is defined by the { 0 D } since zero is not belonging to the input list.
Example(s):
{ 1 2 3} -> { { 0 2 } { 2 1 } { 2 3 } }
#34 from list to search balanced binary tree
input: a list of positive integers (no duplicates. For that check the #20 or make a variant of this that is a bit more complicated)
output: a list of connections that represent a search binary tree. A connection is a sublist { S D } where S is the number of the source node, D is the number of the destination node. The root node is defined by the { 0 D } since zero is not belonging to the input list.
Example(s):
{ 1 2 3} -> { { 0 2 } { 2 1 } { 2 3 } }
#35 check if balanced binary tree
input: a list containing sublists of 2 elements like { {S1 D1} {S2 D2} .. {SN DN} } . A connection is a sublist { S D } where S is the number of the source node, D is the number of the destination node. The root node is defined by the { 0 D }. The input does not have duplicates, so { Sx Dx } appears only once (if you want to deal with duplicates, the #20 is there for you). Still it may be that the nodes reported are not even a tree, like { { 1 2} { 3 4 } { 5 6 } } Those nodes are not connected at all.
output: verify that the list represents a balanced binary tree (reporting 0 if not and 1 if yes). Bonus: reporting the height. Possible variant to make it easier: all the leaves tends to be completed on the left branches . That is, between two branches, if there are not enough nodes left, the left branch is filled first, then the right.
Example(s):
{ { 0 2 } { 2 1 } { 2 3 } } -> 1 "height":1
#36 return all the positions of sublists containing a given element
(stumbled while thinking about #35)
input: a list L! containing only sublists with positive integers (but no further sublists) and a positive integer
output: the positions of sublists in L1 containing the given integer.
Example(s):
{ { 1 2 } { 1 3 } { 1 5 } { 2 5 } } 5 -> { 3 4 }
{ { 1 2 } { 1 3 } { 1 7 } { 2 3 } } 9 -> { 0 }
#37 Possible non conflicting match day pairings (needed for tournament simulations)
Input: a list of positive integers indicating teams , so like {1 2 3 4} (4 teams). the list has size multiple of 2.
Output: all the possible match day pairings. That is: every match day is a list of sublists in the forum {A B} where A and B are the number of two teams, and the team A appears only in one pairing as well as the team B. All the teams appear in the list of pairings for one day. The order of pairings does not matter, {A B} and {B A} are the same (it is not considered home and away).
Example(s):
{ 1 2 3 4} -> { {1 2} {3 4} } { {1 3} {2 4} } { {1 4} {2 3} }
#37b Possible non conflicting match day pairings picking the one having the smallest sum of differences between opponents
Input: a list of positive integers indicating teams , so like {1 2 3 4} (4 teams). the list has size multiple of 2. And a list of scores for each team, like { 0 2 1 5} (team4 has 5 points, team 3 only 1, team 2 two points, team 1 has no points).
Output: like the #37, but the program has to report only those match days that ensure that the pairings have the smallest total sum in terms of points difference between paired team.
example(s):
{ 1 2 3 4}{ 0 2 1 5} ->
{ {1 2} {3 4} } # sum of score differences (in absolute value) |0-2|+|1-5| = 6
{ {1 3} {2 4} } # |0-1|+|2-5| = 4 -- only this match day gets reported as result
{ {1 4} {2 3} } # |0-5|+|2-1| = 6
#37c (variant of #37 suggested by pdo)
Like the 37, just instead of generating all the solutions, being able to generate a single solution with a proper input (input defined by the author of the solution). Plus the program should be able to generate all the solutions (no duplicates) given a range of inputs well defined. Caveat: the input cannot be the solution itself or a translation/compression of it in some other representation.
#38 (generating all the possible calendars of tournaments)
So you have solved #37 or #37c . Now we want to find all the possible calendars. That is:
- given N teams (even)
- A calendar is a collection of match days (see #37) that ensure that every team is paired against all the others just once (so in the collection there are N-1 match days).
- since the space of solution may be too large. The output is: given a specific input (defined by the author of the solution) all the match days in a valid calendar is returned. Plus the solution should ensure that all the calendars are returned (with no duplicates) if the program receives inputs from a well defined range. Caveat: the input cannot be the solution itself or a translation/compression of it in some other representation.
#39 Increasing/decreasing a value in a list (of integers or reals)
Input:
L3: a list of reals or integers (not mixed)
L2: the position to change
L1: the increase/decrease
Output: the list with the increment/decrement
Example(s):
{ 1 2 3 4 5 } 3 3 -> { 1 2 6 4 5 }
{ 1 2 3 4 5 } 3 -3 -> { 1 2 0 4 5 }
#39b like #39 but for a list of positions
Input:
L3: a list of reals or integers (not mixed)
L2: the positions to change in a list
L1: the increase/decrease
{ 1 2 3 4 5 } {2 3} {4 3} -> { 1 6 6 4 5 }
{ 1 2 3 4 5 } {2 3} {-2 -3} -> { 1 0 0 4 5 }
#40 remove all occurrences of one value from a list
See: http://www.hpmuseum.org/forum/thread-8209-post-82415.html#pid82415
#41 monotonic sum
Input: list of numbers.
output: increasing the sum of the elements sequentially. (like a sort of summation)
{ 34 7 92 5 } -> { 34 41 133 138 }
#42 the change-in-coins machine
Inspired from http://www.hpmuseum.org/forum/thread-3840.html
Input: an integer. Not too big (say, smaller than 1 million).
output: the top 5 combinations of the factors {1,2,5,10,20,50,100,200} in terms of smaller coins number. It is an optimization process and it is known that the greedy algorithms do not always work to find the smallest amount of coins to return, but the challenge here is to return the top5, not only the top1.
Note, if there are multiple combinations with the same amount of coins, say:
{50 20 10 10 10}
{50 20 20 5 5}
{20 20 20 20 20}
One can add the flavour that the one most preferred are the one that has the most of the same coins (to stack them nicely). In other words, {20 20 20 20 20} is the best one, then {50 20 10 10 10} then {50 20 20 5 5}.
The converse flavour is also true. To have variety in the pocket, so one can buy things without getting change back, one can give back the combination with the most variety first, so {50 20 20 5 5}, then {50 20 10 10 10} then {20 20 20 20 20}.
Example(s):
100 -> { {100} {50 50} {50 20 20 10} {50 20 10 10 10} {20 20 20 20 20} } //you can use also another notation for the output, like FACTORS for example, but it has to be clear how to interpret it
5 -> { { 5 } { 2 2 1 } { 2 1 1 1 } { 1 1 1 1 1 } } //only 4 results because there are no others.
#42.1 the change-in-coins machine generic
Like the #42 only the factors composition is also given in input. So.
Input: an integer. Not too big (say, smaller than 1 million). Plus a list of positive integers (each different from the other) that we name as inputFactors.
output: the top 5 combinations of the inputFactors in terms of smaller coins number.
#43 This is ultra huge, long and difficult (but I did not want to lose the idea)
Seeing numbers as list of digits, implement addition, subtraction, division, multiplication and all the other operations to get really large results, although slowly.
One can do it as well with strings.
Inspiration: http://www.hpmuseum.org/forum/thread-10339.html
#44 streaks of increasing values
Input: A list of 0 and 1, representing losses and wins accordingly.
Each isolated 1 or the initial 1 of a group is equal to a 1.
Groups of 1s have increasing value, for example {1 1 1} is mapped to the values {1 2 3}.
Output: the sum of the mapped values given the input list.
Inspired by http://www.hpmuseum.org/forum/thread-12373.html
Example:
{1 0 0 1 1 0 1 0 1 1 1} -> is mapped to
{1 0 0 1 2 0 1 0 1 2 3} -> sum: 11
#44.1 biggest group of non zero values
Same input as in #44. Determine the size of the biggest streak of 1.
Example:
{1 0 0 1 1 0 1 0 1 1 1} -> 3 @as the longest streak is 3
#45 find duplicates and return their positions
Input: a list of entries, for simplicity, reals.
Ouput: a list of sublists (or equivalent structure). Each sublists contains the index of all the entries that are equal. There should be no sublist of entries appearing only once (or not appearing at all)
Example(s):
{ 1 2 3 1 4 5 6 1 7 8 9 9 } -> { { 1 4 8 } { 11 12 } }
as only 1 and 9 are repeated.
#46 Match the integer
See https://www.hpmuseum.org/forum/thread-18533.html
#47 Increase a list of "list positions" (for LPICK for example)
We have a list of numbers (or objects) and we want to pick the numbers from the list in a certain order.
Say the list of numbers is { 5 4 3 2 1 } and we want to pick them in the order { 1 5 1 5 1 5 2 4 2 4} getting the list { 5 1 5 1 5 1 4 2 4 2 }.
We want to do this systematically though. That is, we want to pick the elements first with the sequence { 1 1 1 1 1 1 1 1 1 1}.
Then with the sequence { 1 1 1 1 1 1 1 1 1 2 }, then comes { 1 1 1 1 1 1 1 1 1 3 } and so on until { 1 1 1 1 1 1 1 1 1 5 }.
Then comes { 1 1 1 1 1 1 1 1 2 1} and so on. Such lists can be used with LPICK from LixtExt (https://www.hpcalc.org/details/7971)
Thus write a program that gets in input a list of positions (to pick) and the maximum value for a position and increments it by 1.
Thus the input is:
L2: maxValueForPositions
L1: list of positions to increment.
Output
L1: list of positions incremented by 1. NOTE: there is no undeflow. If one gets in input the maximum list, say { 5 5 5 } in output one gets the same list.
--
Every challenge has the following variants.
Variant type a
Solving the challenge processing the list with list operations (built in, from libraries like GoferList, self made, whatever) but not built "ad hoc" for the challenge. This to avoid to transform the list in stack elements, vectors, matrix or whatever within the main program.
Transforming a list is allowed only in functions to process lists, that should be created for generic lists, like a list of positive integers, and not for particular lists coming from this challenge (the generalized version may fit the particular case through clever inputs).
Of course if one wants to use the stack as variable space is ok (like duplicating the input list a couple of times), the point is that the list should not be "exploded/transformed in a non-list" to be processed.
Variant type b
You can transform the list in another container object (vector, matrix, list of lists), but still avoiding to use pure stack operations to process it. (well aside from little stack actions , like positioning inputs for a command for example "pos varList SWAP GET")
Variant type c
Do whatever you like to solve the problem.
edit: after solving some challenges (at first I just adapted them from the game manufactoria) I have to say that some are pretty pleasant.
One source of challenges. Bonus .
RE: Programming puzzles: processing lists! - Han - 04-20-2017 02:21 PM
In #4, it is not clear if the resulting list should be expanding in the event that the "addition" causes a carry on the most significant digit. For example, should { 1 1 1 } result in { 1 0 0 0 } or { 0 0 0 } ?
RE: Programming puzzles: processing lists! - pier4r - 04-20-2017 02:22 PM
(04-20-2017 02:21 PM)Han Wrote: In #4, it is not clear if the resulting list should be expanding in the event that the "addition" causes a carry on the most significant digit. For example, should { 1 1 1 } result in { 1 0 0 0 } or { 0 0 0 } ?
nice catch. {1 0 0 0} I fix it, fixed.
RE: Programming puzzles: processing lists! - Han - 04-20-2017 02:35 PM
(04-20-2017 02:22 PM)pier4r Wrote:(04-20-2017 02:21 PM)Han Wrote: In #4, it is not clear if the resulting list should be expanding in the event that the "addition" causes a carry on the most significant digit. For example, should { 1 1 1 } result in { 1 0 0 0 } or { 0 0 0 } ?
nice catch. {1 0 0 0} I fix it, fixed.
Additional question: should the list be of the exact size as the input if no carry happens? This is important because the lazy approach would simply always return a list whose size is one larger than that of the input.
EDIT: More comments:
#12 and #2 do not seem all that different
#14 could easily run into overflow problems if your list is a minimum of 100 elements; did you mean to return the number as a list of digits in base 10?
RE: Programming puzzles: processing lists! - Han - 04-20-2017 04:09 PM
Here are some of my solutions for the HP Prime. I'll post RPL solutions later.
Code:
Spoilers...
EXPORT LC1(l)
BEGIN
local s:=size(l);
local n;
local e1:=3;
local e2:=5;
if l(1)==5 then
e1:=5;
e2:=3;
end;
for n from 1 to s do
if bitand(n,1) then
if l(n)<>e1 then return(0); end;
else
if l(n)<>e2 then return(0); end;
end;
end;
return(1);
END;
EXPORT LC2(l)
BEGIN
local s:=size(l);
local n;
for n from 1 to s do
if l(n)==3 then
l(n):=4;
else
if l(n)==5 then l(n):=7; end;
end;
end;
return(l);
END;
EXPORT LC3(l)
BEGIN
local s:=size(l);
local m:=floor(s/3);
local n;
makelist(
l(
ifte(n<=m,l(s-m+n),l(n-m))
), n, 1, s
);
END;
EXPORT LC4small(l)
BEGIN
local s:=size(l);
local j,n,p2;
n:=0; p2:=1;
for j from 1 to s do
if l(j) then n:=n+p2; end;
p2:=2*p2;
end;
n:=n+1;
s:=s+(bitand(n,p2)<>0);
p2:=2*p2;
makelist((bitand(n,p2:=bitsr(p2,1))<>0),j,1,s);
END;
EXPORT LC4(l)
BEGIN
local s:=size(l);
local j,d;
local c:=1;
for j from s downto 1 do
d:=l(j)+c;
c:=bitsr(d,1);
l(j):=bitand(d,1);
end;
if c then
return(makelist(ifte(j>1,l(j-1),1),j,1,s+1));
else
return(l);
end;
END;
EXPORT LC5(l)
BEGIN
local s:=size(l);
local j,d;
local c:=0;
for j from s downto 1 do
d:=l(j)+c+1;
c:=bitsr(d,1);
l(j):=bitand(d,1);
end;
END;
EXPORT LC6(l)
BEGIN
local s:=size(l);
local j,n;
local ints:={};
local count:={};
for j from 1 to s do
if n:=pos(ints,l(j)) then
count(n):=count(n)+1;
if count(n)>ints(n) then return(0); end;
else
ints(0):=l(j);
count(0):=1;
end;
end;
s:=size(count);
for j from 2 to s do
if count(j)<>count(j-1) then return(0); end;
end;
return(1);
END;
EXPORT LC7(l)
BEGIN
local s:=size(l);
local m:=s/2;
local n;
local nl:=makelist(
ifte(n<=m,l(n),l(n-1)),
n,1,s+1
);
nl(m+1):=-1;
return(nl);
END;
EXPORT LC8(l)
BEGIN
local s:=size(l);
local m:=s/2;
local j;
for j from 1 to m do
if l(j)<>l(m+j) then return(0); end;
end;
return(1);
END;
EXPORT LC9(l)
BEGIN
local s:=size(l);
local j,k,m;
local b:=0;
local n:=3;
for j from 1 to s do
if l(j)<>3 then break; end;
end;
k:=j-1;
m:=s/k;
if m<>floor(m) then return(0); end;
for j from k+1 to s do
if b then
b:=b-1;
else
b:=k;
if n==3 then n:=5; else n:=3; end;
end;
if l(j)<>n then return(0); end;
end;
return(1);
END;
EXPORT LC10(l)
BEGIN
local s:=size(l);
local j,n;
local ints:={};
local count:={};
for j from 1 to s do
if n:=pos(ints,l(j)) then
count(n):=count(n)+1;
if count(n)>ints(n) then return(0); end;
else
ints(0):=l(j);
count(0):=1;
end;
end;
s:=size(count);
for j from 1 to s do
if count(j)<>ints(j) then return(0); end;
end;
return(1);
END;
EXPORT LC11(l)
BEGIN
local s:=size(l);
local m:=bitsr(s,1);
local j;
for j from 1 to m do
if l(j)<>l(s-j+1) then return(0); end;
end;
return(1);
END;RE: Programming puzzles: processing lists! - pier4r - 04-20-2017 05:30 PM
(04-20-2017 02:35 PM)Han Wrote: Additional question: should the list be of the exact size as the input if no carry happens? This is important because the lazy approach would simply always return a list whose size is one larger than that of the input.
yes. I thought to put your observation in the main post, but there are already examples showing this.
Quote:EDIT: More comments:
#12 and #2 do not seem all that different
True, so I put a note on the #12.
Quote:#14 could easily run into overflow problems if your list is a minimum of 100 elements; did you mean to return the number as a list of digits in base 10?
No I did not thought about the overflow. You are right. I put a cap on the positive integers, this does not strike out the problem completely but it is less easy to run in overflow.
@ han: thanks for your solutions. I will surely use them when I will pick up the prime language, that so far I had no time. Having "small and ad hoc" programs sometimes is complementary to explain some syntax.
I still have to attack the problem with the 50g making use of STREAM, DOLIST, DOSUBS or functions for lists. I don't believe it will be difficult, but to make it fast, that is difficult.
If someone wants a random generator for lists, one can find one here:
Code:
getRandomList
\<<
@0
\->
@input
numElements
minValue
maxValue
@local var
@counter
\<<
\<<
maxValue RAND * IP minValue +
\>>
'counter'
1 numElements 1
@ from 1 to numElements, increment of 1
SEQ
\>>
\>>It has to be adapted to generate lists with only two values that are not successive, though. (like 3 and 5)
RE: Programming puzzles: processing lists! - pier4r - 04-20-2017 05:42 PM
@han a question. If I read your code properly your solutions are of the variant #1 right? You are not exploding/transforming the list in other collections if I am not mistaken, correct?
RE: Programming puzzles: processing lists! - Han - 04-20-2017 06:48 PM
(04-20-2017 05:42 PM)pier4r Wrote: @han a question. If I read your code properly your solutions are of the variant #1 right? You are not exploding/transforming the list in other collections if I am not mistaken, correct?
Correct. The input lists are kept as lists. If the input list is modified, only its elements are modified (i.e. the input list is modified and returned as the output list). Otherwise, a newly created list is returned as the output. There is no transformation of any list into some other object type or structure.
I deviated from your instructions slightly in that when a list is "valid" I return a 1 (as opposed to the original list), although such a desired output can be easily achieved by changing the return statement to return the original list.
RE: Programming puzzles: processing lists! - pier4r - 04-20-2017 07:13 PM
Yes, the output "invalid" was more a visual sign than something else.
RE: Programming puzzles: processing lists! - pier4r - 04-20-2017 09:35 PM
Challenge #1a userRPL, 50g.
more functions: http://www.hpmuseum.org/forum/thread-8114.html
I noted that the test failed almost immediately and so I started to estimate the probabilities.
If I'm not mistaken, the test will succeed - given a random list - with probability:
1/2 for 2 elements
1/4 for 3 elements
1/8 for 4 elements
1/2^(n-1) for n elements
so it is very likely to fail.
Therefore I made the random input list smaller , only 10 elements, and I let the test execute 2048 times.
I should expect around 4 successes. let's see how long it takes to compute all this.
Code:
c1tester
\<<
{ } @timeList
{ } @positionCheckedList
\->
timeList
positionCheckedList
\<<
1 100
START
100 {3 5} getRandomListFromValues
'c1vaV1' TEVAL
@collect the timing
OBJ\-> DROP
'timeList' SWAP STO+
'positionCheckedList' SWAP STO+
NEXT
timeList
positionCheckedList
\>>
\>>
c1vaV1
\<<
@ given a list in input of 3 and 5, length 100+
@ if those are not alterated, the list is invalid
@ returning possible different values for statistics
1 @lastPosChecked
3 @uf3
5 @uf5
10 @ufInvalid
\->
@inputs
inputL
@local
lastPosChecked
uf3
uf5
ufInvalid
\<<
@flags as booleans
uf3 CF
uf5 CF
ufInvalid CF
@set the first value.
@ with if then else
IF
inputL 1 GET 3 ==
THEN
uf3 SF
ELSE
uf5 SF
END
inputL
\<<
\->
listEl
\<<
IF
NSUB 1 >
@we already used the first element
ufInvalid FC?
@ list not invalid
AND
THEN
CASE
listEl 3 ==
uf5 FS?
AND
THEN
uf5 CF
uf3 SF
END
listEl 5 ==
uf3 FS?
AND
THEN
uf3 CF
uf5 SF
END
@def
ufInvalid SF
END
END
IF
ufInvalid FC?
THEN
'lastPosChecked' 1 STO+
END
\>>
\>>
DOSUBS
@inputL
@
@IF
@ ufInvalid FS?
@THEN
@ "invalid"
@END
lastPosChecked
\>>
\>>RE: Programming puzzles: processing lists! - Didier Lachieze - 04-20-2017 09:55 PM
My solutions for #1 to #11 plus #13 & #21 on the Prime :
Code:
EXPORT LI1(l)
BEGIN
LOCAL a,b;
a:=IFTE(l(1)==3,{3,5},{5,3});
b:=MAKELIST(a(I MOD 2),I,1,SIZE(l));
RETURN IFTE(EQ(l,b),l,"invalid");
END;
EXPORT LI2(l)
BEGIN
EXECON("IFTE(&1==3,4,IFTE(&1==5,7,&1))",l);
END;
EXPORT LI3(l)
BEGIN
LOCAL a,b;
a:=SIZE(l);
b:=FLOOR(a/3)+1;
MAKELIST(l(((I-b) MOD a)+1),I,1,a);
END;
EXPORT LI4(l)
BEGIN
LOCAL a,b,c,j;
a:=SIZE(l);b:={};c:=1;
FOR j FROM a DOWNTO 1 DO
b(j):= l(j) XOR c;
c:=l(j) AND c;
END;
IFTE(c,CONCAT(c,b),b);
END;
EXPORT LI5(l)
BEGIN
LOCAL a,b,c,j;
a:=SIZE(l);b:={};c:=1;
FOR j FROM a DOWNTO 1 DO
b(j):= l(j) XOR c;
c:= (NOT l(j)) AND c;
END;
b;
END;
EXPORT LI6(l)
BEGIN
LOCAL a;
a:=UNION(l);
a:=MAKELIST(SIZE(INTERSECT(l,{a(I)})),I,1,SIZE(a));
IF ΠLIST(a==a(1)) THEN l ELSE "invalid" END;
END;
EXPORT LI7(l)
BEGIN
LOCAL a:=SIZE(l);
IFTE(odd(a),l,CONCAT(l({1,a/2}),{-1},l({a/2+1,a})));
END;
EXPORT LI8(l)
BEGIN
LOCAL a:=SIZE(l);
IFTE(odd(a),l,IFTE(EQ(l({1,a/2}),l({a/2+1,a})),l,"invalid"));
END;
EXPORT LI9(l)
BEGIN
LOCAL a:=SIZE(l);
IF (a MOD 3)==0 THEN
IF EQ(l({1,a/3}),MAKELIST(3,I,1,a/3)) AND
EQ(l({a/3+1,2*a/3}),MAKELIST(5,I,1,a/3)) AND
EQ(l({1,a/3}),l({2*a/3+1,a})) THEN RETURN l;
END;
END;
"invalid";
END;
EXPORT LI10(l)
BEGIN
LOCAL a,b;
a:=UNION(l);
b:=MAKELIST(SIZE(INTERSECT(l,{a(I)})),I,1,SIZE(a));
IF EQ(a,b) THEN l ELSE "invalid" END;
END;
EXPORT LI11(l)
BEGIN
IFTE(EQ(l,REVERSE(l)),l,"invalid");
END;
EXPORT LI13(l)
BEGIN
LOCAL a,b,c,k;
a:=SIZE(l);
b:=mat2list(idivis(a));
FOR k FROM 1 TO SIZE(b)-1 DO
c:=MAKELIST(l(((I-1) MOD b(k))+1),I,1,a);
IF EQ(l,c) THEN RETURN(a/b(k)); END;
END;
"invalid";
END;
EXPORT LI21(l)
BEGIN
UNION(l);
END;RE: Programming puzzles: processing lists! - DavidM - 04-21-2017 12:43 AM
Many of the list processing shortcuts tend to misbehave if you provide them with lists containing no elements, 1 element, or invalid elements. For these challenges, I'm taking you at your word that the input won't include any of those situations.
I've played around with the first 12 of these so far, but am only including the first few here. My focus has been more on using the list commands than on performance considerations, and I suspect that most of what I've done could be sped up with a more brute-force approach.
Here's what I came up with for the first few:
Code:
@@@ SPOILER ALERT
Ch01
\<<
DUP \<< == \>> DOSUBS
\GSLIST "invalid" IFT
\>>
Ch02
\<<
1 \<< 3 == 4 7 IFTE \>> DOLIST
\>>
Ch03
\<<
\-> src
\<<
src SIZE DUP 3 / FLOOR - \-> bp
\<<
src 1 \<< NSUB bp \<= \<< DROP \>> IFT \>> DOSUBS
src 1 \<< NSUB bp > \<< DROP \>> IFT \>> DOSUBS
+
\>>
\>>
\>>
Ch04
\<<
1 \-> carry
\<<
REVLIST 1 \<< carry + DUP 1 > 'carry' STO 1 == \>> DOLIST
IF carry THEN 1 + END
\>>
REVLIST
\>>
Ch05
\<<
0 \-> carry
\<<
REVLIST 1 \<< carry + 1 + DUP 1 > 'carry' STO 2 MOD \>> DOLIST
\>>
REVLIST
\>>As I mentioned above, I've intentionally coded these with the assumption that the input is exactly as described. In particular, I haven't done any kind of validation that the input contains the proper numbers. As such, the code is only functional for valid input, and will fail miserably with unexpected input. For that matter, it may fail with valid input, too.
But it at least worked for the test cases I gave it.
RE: Programming puzzles: processing lists! - pier4r - 04-21-2017 05:37 AM
(04-20-2017 09:35 PM)pier4r Wrote: Challenge #1a userRPL, 50g.
more functions: http://www.hpmuseum.org/forum/thread-8114.html
I noted that the test failed almost immediately and so I started to estimate the probabilities.
If I'm not mistaken, the test will succeed - given a random list - with probability:
1/2 for 2 elements
1/4 for 3 elements
1/8 for 4 elements
1/2^(n-1) for n elements
so it is very likely to fail.
....
So after 2048 tests with a list of size 10 (output equal to 11 when valid).
1st: a lot of memory used, especially to save the results instead of deleting it accidentally.
2nd: the smaller the list, the faster the stack operations.
3rd: I got 2 elevens (list passed completely) and 7 tens (list failed at the last element)
The theory should have been 4 elevens and 8 tens, so I would assume that my code is not failing. To be sure as soon as possible I will code a function that instead of producing randomly a list of two values, will produce with a certain proportion random lists and valid lists.
4th: the average execution time per list of 10 elements was 0.26 seconds, per list of 100 elements was 1.9 seconds.
(04-21-2017 12:43 AM)DavidM Wrote: Many of the list processing shortcuts tend to misbehave if you provide them with lists containing no elements, 1 element, or invalid elements. For these challenges, I'm taking you at your word that the input won't include any of those situations.
Yes, I wanted to avoid annoying corner cases. Just a straight processing. I will have to compare your code with mine, your is way more compact. If you want to contribute in the comparison you are welcomed.
Oh, I just understood what your first challenge is doing (compare the nth element with the nth-1 element , I'm not sure about the last element ). That's a beauty! Asap I will compare speed (and results).
Instead someone with a prime may compare the code between han and didier, they do not look the same.
RE: Programming puzzles: processing lists! - Didier Lachieze - 04-21-2017 05:47 AM
I've updated my post with the solutions from #1 to #11.
RE: Programming puzzles: processing lists! - Han - 04-21-2017 12:13 PM
#13 is not clear to me -- what is meant by:
"verify that the list is made up by two identical (also the order) sublists. Return the number of sublists if valid, "invalid" otherwise"
If the sublists are identical then wouldn't the original list simply be generated by a single sublist? What is the significance of having two identical sublists? Also, should the program always return the largest proper sublist that generates the original list?
{ 1 2 1 2 1 2 1 2 } can be generated by { 1 2 } or by { 1 2 1 2 }; should the answer be 2 or 4?
RE: Programming puzzles: processing lists! - pier4r - 04-21-2017 02:14 PM
Han, nice catch again. First the "two sublists" is an error, should not have been there. One should identify the smaller generating sublist, that is not valid if the list is equal to the entire sublist. I mean if one has { 3 3 3 4} one could claim that the generating sublist is {3 3 3 4} and that's not interesting.
I will fix the main post as soon as I am with a computer.
RE: Programming puzzles: processing lists! - Han - 04-21-2017 02:26 PM
(04-21-2017 02:14 PM)pier4r Wrote: Han, nice catch again. First the "two sublists" is an error, should not have been there. One should identify the smaller generating sublist, that is not valid if the list is equal to the entire sublist. I mean if one has { 3 3 3 4} one could claim that the generating sublist is {3 3 3 4} and that's not interesting.
I will fix the main post as soon as I am with a computer.
Also, another comment on #14 -- are you sure you want to be using lists of size 100 or more (for the input) and requiring the output be an integer? If the list size is 100 or more, it may be better to return the result as a list of digits (again due to overflow). Limiting the integers to a max value of 9 only addresses one of the overflow issues. The other issue is from a large list with 0 being approximately close toward either end of the list.
RE: Programming puzzles: processing lists! - pier4r - 04-21-2017 04:03 PM
Han, yes you convinced me. Actually I wanted to use that problem to push the boundaries of the math environment, handling big integers. But that's ok nevertheless. So changed the statements. Any further observation is welcomed.
I still have to do the tests on the challenge 1.
RE: Programming puzzles: processing lists! - pier4r - 04-21-2017 09:03 PM
Some more results
more code: here
Code:
c2tester
\<<
10 @iterations
10 @listSize
{ } @rndList
{ } @timeListC2vaV1
{ } @timeListDavidM
{ } @posCheckedListC2vaV1
{ } @posCheckedListDavidM
\->
iterations
listSize
rndList
timeListC2vaV1
timeListDavidM
posCheckedListC2vaV1
posCheckedListDavidM
\<<
1 iterations
START
listSize {3 5} getRandomListFromValues 'rndList' STO
rndList 'c2vaV1' TEVAL
@collect the timing
OBJ\-> DROP
'timeListC2vaV1' SWAP STO+
@ collect the pos checked.
'posCheckedListC2vaV1' SWAP STO+
rndList 'c2DavidM' TEVAL
@collect the timing
OBJ\-> DROP
'timeListDavidM' SWAP STO+
@ collect the pos checked.
'posCheckedListDavidM' SWAP STO+
NEXT
timeListC2vaV1
posCheckedListC2vaV1
timeListDavidM
posCheckedListDavidM
\>>
\>>
c2vaV1
@given alist of length 100 of 3s and 5s, return the same list
@ with 4 instead of 3 and 7 instead of 5
@it seems correct
@ 10 lists of 10 elements: 0.22 secs
@ 50 lists of 100 elements: 2.32 secs
\<<
{ } @resultList
\->
@input
inputList
@local
resList
\<<
inputList
\<<
\->
value
\<<
@we place a 4 on the stack
value 3 ==
4 IFT
@we place a 7 on the stack otherwise
value 5 ==
7 IFT
@we add the result to the output list
@ we need to swap the values though otherwise
@ the solution gets reversed.
'resList' SWAP STO+
\>>
\>>
DOSUBS
resList
\>>
\>>Correctness, both mine and DavidM (no other person contributed so far) are apparently correct.
Speed:
- challenge 1
Pier
@ 128 lists of 5 elements, average check length, 0.17 seconds
@ 10 lists of 100 elements, 1.73 sec average.
David
@ 128 lists of 5 elements, average check length, 0.061 seconds
@ 10 lists of 100 elements, 0.58 sec average.
- challenge 2
Pier
@ 10 lists of 10 elements: 0.22 secs
@ 50 lists of 100 elements: 2.32 secs
David
@ 10 lists of 10 elements: 0.08 secs
@ 50 lists of 100 elements: 0.59 secs
Outclassed!
Let's see for the next challenges if I can step up the solution. Furthermore the solution of david are very quick. I wonder if working with the stack could be faster or just be barely faster.
PS: I will compare more RPL based results if those appears during those days. Otherwise someone else has to do it.
RE: Programming puzzles: processing lists! - Didier Lachieze - 04-22-2017 09:14 AM
I've added the solution #13 to my post.
I need to review the solutions for #4 and #5 which are not working well with long lists.
EDIT: I've updated the solutions for #4 and #5 to work with long lists.