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 }
#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-820...l#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 .
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-820...l#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 .