Programming puzzles: processing lists!

04192017, 09:20 PM
(This post was last modified: 10312017 10:44 AM by pier4r.)
Post: #1




Programming puzzles: processing lists!
(let me know if it is not clear or there are mistakes)
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 needs to be optimized changes, propose one. Feel free to pick any of the challenges, or even none . At least I will try to solve them slowly. userRPL reference: it is assumed that the the minimum size of the input list adapts to fit the challenge, but it is never lower than 100. #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:
#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) 02+15 = 6 { {1 3} {2 4} } # 01+25 = 4  only this match day gets reported as result { {1 4} {2 3} } # 05+21 = 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 N1 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/thread820...l#pid82415  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 nonlist" 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 . Wikis are great, Contribute :) 

« Next Oldest  Next Newest »

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