[RPL] ROLL Challenge (tricky) - Printable Version +- HP Forums (https://archived.hpcalc.org/museumforum) +-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html) +--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html) +--- Thread: [RPL] ROLL Challenge (tricky) (/thread-180067.html) [RPL] ROLL Challenge (tricky) - Oliver Unter Ecker - 03-13-2011 Come up with an RPL program that will transform this string "5 1 2 3 4 6" into this string "5 1 4 6 3 2" using no more than 11 of only these commands: STR->, ROLL You may also use numbers, quotes and the "+" operator, which we shan't count as commands. Caveat: Repeated ROLLs may not be provided the same number as argument, unless it's 2. The program using the smallest number of commands wins. Hint: There're at least two approaches one can take. And there may be a twist. Or two. Edited: 13 Mar 2011, 2:26 p.m. Re: [RPL] ROLL Challenge (tricky) - Raymond Del Tondo - 03-13-2011 Maybe this one? ```STR-> 6 ROLL " " + 6 ROLL + " " + 3 ROLL + " " + 2 ROLL + " " + 2 ROLL + " " + 2 ROLL + ``` Ray Re: [RPL] ROLL Challenge (tricky) - Eric Smith - 03-13-2011 It can be done with only one STR-> command, no ROLL commands, and a modest number of the specified uncounted items (numbers, quotes, "+" operator). ```<< STR-> + + + + + -16 + " " + 1 + " " + 4 + " " + 6 + " " + 3 + " " + 2 + >> ``` This assumes exact mode and FIX 0. If you allow numbers inside quotes it can be even shorter. Re: [RPL] ROLL Challenge (tricky) - Eric Smith - 03-13-2011 He said that you can't use the same roll count more than once, except 2. Re: [RPL] ROLL Challenge (tricky) - Raymond Del Tondo - 03-13-2011 Yes, it's _2_ ROLL, so that should be ok. Re: [RPL] ROLL Challenge (tricky) - Oliver Unter Ecker - 03-13-2011 Ray, Very nice! I'm impressed. But, you're using the 6 twice, which violates the caveat. Without yet revealing what you did, can you tell us if you used FORs, DOSUBs, or lots of Monkeys on typewriters? Re: [RPL] ROLL Challenge (tricky) - Oliver Unter Ecker - 03-13-2011 Eric. Oh, darn! You out-twisted me. Your solution is perfectly valid and you carry home the price. But maybe I can be forgiven of not having constructed the challenge in a watertight manner, and amend as follows: "5 1 2 3 4 6" becomes "5.1 1.2 2.6 3.5 4.3 6.4" "5 1 4 6 3 2" becomes "5.1 1.2 4.3 6.4 3.5 2.6" and there's no "."s allowed in the solution... ;-) Thank you! That is, the challenge really wants you to use ROLLs to solve the problem. But, actually, it might be STR-> that plays center-stage. Edited: 13 Mar 2011, 8:33 p.m. Re: [RPL] ROLL Challenge (tricky) - Raymond Del Tondo - 03-13-2011 Now I see what Eric meant. Ok, the sequence `STR-> 6 ROLL " " +` has to be replaced by `STR-> " " 7 ROLL 2 ROLL +` resulting in one more ROLL;-) Quote:lots of Monkeys on typewriters?? Edited: 13 Mar 2011, 8:37 p.m. Re: [RPL] ROLL Challenge (tricky) - Oliver Unter Ecker - 03-13-2011 Hey, wait! What's that "-" doing in your solution? (MOC grabs trophy back from would-be winner.) Back to original strings. Re: [RPL] ROLL Challenge (tricky) - Oliver Unter Ecker - 03-13-2011 Hmm. I guess negative numbers are "numbers" too... So, apologies, keep that trophy and I'm buying a second one. :-) The challenge becomes amended to say "natural numbers" or "number keys" instead of "numbers". Re: [RPL] ROLL Challenge (tricky) - Oliver Unter Ecker - 03-13-2011 Ray, Cool. Ok. 8 "commands" it is for your entry. You're in the lead. I figured the solution was of the form stringToStack ROLL_1..ROLL_N stackToString and I was wrong. Your solution meshes rolling and gluing, and that's great. The monkeys on typewriters will be explained tomorrow. Edited: 13 Mar 2011, 11:04 p.m. Re: [RPL] ROLL Challenge (tricky) - Paul Dale - 03-14-2011 My first thought is this gem: DROP "5 1 4 6 3 2" for a zero count. For the amended version, something similar can be done using SREPL I should think. - Pauli Re: [RPL] ROLL Challenge (tricky) - Tim Wessman - 03-14-2011 SysRPL version: DOSTR> 2SWAP SWAP DEPTH {}N DO>STR THREE OVERLEN\$ #2- SUB\$ Makes the assumptions that you are in exact mode, standard format, and no arguments on the stack except the input. Works for any type of valid string input and desired output of the same format. (I really can't program userRPL... brain too used to sys) TW Edited: 14 Mar 2011, 2:21 a.m. after one or more responses were posted Re: [RPL] ROLL Challenge (tricky) - Eric Smith - 03-14-2011 I don't see "DROP" in the list of allowed commands. Otherwise I would have used it myself. :-) Re: [RPL] ROLL Challenge (tricky) - Paul Dale - 03-14-2011 Quote:(I really can't program userRPL... brain to used to sys) I'm a bit surprised that sysRPL is still in vogue :-) - Pauli Re: [RPL] ROLL Challenge (tricky) - Oliver Unter Ecker - 03-14-2011 This challenge turned from tricky to messy, and I'm in a bit of a pickle: I'm no longer sure what the shortest solution is. I think, though, that the challenge isn't over. There might be a solution of 6 or 7 commands, besting Jay's 8. Bear with me, if you're patient. The challenge was meant to not be about writing a solution program. But, rather, writing a program that will find the solution program. That is, if you took the second approach of two approaches I saw: Two approaches: - Path of Admirable Intuition - Brute Force My basic assumption of the solution template to necessarily look like this ``` stringToStack instruction1..instructionN stackToString where instructionX: number ROLL stringToStack: STR-> (check) stackToString: needs "" (check) + bunch of string concatenations (+), " " (check), and SWAP (missing) SWAP: 2 ROLL (check) ``` was proven wrong by Jay's solution, which meshes the ROLLs with building up the result string from the stack. Here's my development of the brute force approach. It's invalidated to find *the* solution now that my assumed template is known to be not the shortest. But it may be re-tooled to either find a shorter solution OR prove that there are no shorter solutions. Brute force: write an RPL program that writes all possible RPL programs (within our constraints) and test which ones, when applied to the input string, will yield the output string. (ROLL was meant to be but one "shuffle" function that, when applied a few times would be non-linear/head-spinning enough to have people give up on finding a "manual" solution.) Note, the challenge said nothing about constraints to a program that would be used to "come up" with the solution program. So you can use all RPL commands for former. (One of the twists...) There's 6 chars in the string which will end up on the stack. That is, there's a max of 6 sensical ROLLs: 1 ROLL, 2 ROLL, 3 ROLL, 4 ROLL, 5 ROLL, 6 ROLL. As no same-arg ROLLs are allowed -> 6 6 PERM (=720) possible programs. One instruction is a no-op: 1 ROLL -> 5 5 PERM (=120) possible programs. It's unknown how many instructionX we'll have. Except: it cannot be more than 11 (known number of instructions for a solution) minus 1 (STR->) minus # commands to implement stackToString. We can write stackToString. Let's. Given 6 numbers on the stack, we need five concatenations, of numbers and spaces. stackToString: "" + " " + 2 ROLL + " " + 2 ROLL + " " + 2 ROLL + " " + 2 ROLL + " " + 2 ROLL + # commands to implement stackToString: 5 -> upper limit for N: 11 - 1 - 5 -> 5 That is, as per challenge wording, a max of 5 ROLLs is needed. That matches the combinatorial complexity, and doesn't simplify things. But, reading between lines, "program using the smallest number of commands wins" suggests a solution with a lesser number of ROLLs exists. Since we cannot save on any other instructions (OR SO I THOUGHT), it's implied that <= 4 ROLLs are needed. 5 4 PERM (=120) possible programs Let's implement a program generator: ```\<< { 2 3 4 5 6 } permutate @ produce all non-no-op permutations of possible ROLL args DUP SIZE V\-> DROP 4 \->V2 RDM @ reduce to 4 picks 1 \<< "" SWAP 1 \<< + " ROLL " + \>> @ assemble RPL program, precede each ROLL with element DOSUBS @ iterate over elements of each permutation keepIfSolution @ test program; keep on stack (->DOSUBS will roll into result array) if it's a solution \>> DOSUBS @ iterate over permutations \>> ``` ```permutate: your favorite implementation that will produce an array of permutations, given an array ``` And a program tester: ```keepIfSolution: \<< \-> prg \<< X STR\-> @ unpack input string to stack prog STR\-> @ unpack and execute (!) ROLL instructions "" + " " + 2 ROLL + " " + 2 ROLL + " " + 2 ROLL + " " + 2 ROLL + " " + 2 ROLL + Y == @ compare against desired result string prg IFT @ keep ROLL instruction string, if match (implied drop, otherwise) \>> \>> ``` X: input string Y: desired output string Run, and 2.6s later (on ND1), a single solution is found: "5 ROLL 3 ROLL 2 ROLL 6 ROLL" Can we do better? ```Change this DUP SIZE V\-> DROP 4 \->V2 RDM @ reduce to 4 picks to DUP SIZE V\-> DROP 3 \->V2 RDM @ reduce to 3 picks ``` Run, and get another single solution: "2 ROLL 5 ROLL 6 ROLL" That is, the shortest challenge solution program (UNDER THE ASSUMED TEMPLATE) is: ```\<< STR-> 2 ROLL 5 ROLL 6 ROLL "" + " " + 2 ROLL + " " + 2 ROLL + " " + 2 ROLL + " " + 2 ROLL + " " + 2 ROLL + \>> ``` 9 commands, as per (odd) challenge definition of "command". Note, STR-> is used to execute an RPL program that was written on-the-fly. I discovered this feature of STR-> only the other day. I found it so… arbitrary. But inspiring, too, to try and construct a challenge around it. (Btw, one can get the same effect with OBJ-> or LIST->, which seem far more canonical than STR-> for arbitrary command execution.) The "Path of Admirable Intuition" was a no-go for me, but the solution offered a "Path of Knowing in Hindsight": Play through how 2 ROLL, 5 ROLL, 6 ROLL work on the input. Given the (deceptive) proximity of the input and desired output strings, it transpires that if someone had the intuition that - the solution string will be built up in reverse - the *reverse* of the solution is very close after doing one SWAP they could possibly find the solution in seconds. I find it hard to visualize more than one overlapping ROLL, let alone trying to aim for a solution in reverse. Anyway. I'm not quite sure how Jay found the solution. If repeated application of overlapping ROLLs was linear enough to "just do it" (without a headache), my challenge failed to pose a challenge to finding *a* solution. But is it the best or only solution? Can someone deliver a proof? I'll report on my re-tooling to assume a new template but keeping the brute force approach. Edited: 14 Mar 2011, 7:09 a.m. Re: [RPL] ROLL Challenge (tricky) - Oliver Unter Ecker - 03-14-2011 Holy... Ok. This one wins the "most rules-disrespecting while simultaneously unreadable though probably working" price. (Nice, though, if you like scary...) Re: [RPL] ROLL Challenge (tricky) - Reth - 03-14-2011 I'd like to know how many people *still* speak Latin only too Re: [RPL] ROLL Challenge (tricky) - Oliver Unter Ecker - 03-14-2011 I guess the monkeys on typewriters are explained now. If you can't afford DOSUBS or FORs, you gotta have monkeys to write the candidate programs to test for you. Re: [RPL] ROLL Challenge (tricky) - Glen Sanft - 03-14-2011 Quote: The monkeys on typewriters will be explained tomorrow. We're all familiar with the story of how Microsoft develops product... :) Re: [RPL] ROLL Challenge (tricky) - David Hayden - 03-14-2011 ```DROP "5 1 4 6 3 2" ``` Obviously this isn't the kind of solution that was intended, but I'm posting it to make a point about programming: it's easy to over-generalize a program. Or to put it another way, when writing a program, look at the specifics of the problem and see if there is a way to exploit them. Edited: 14 Mar 2011, 8:50 a.m. Re: [RPL] ROLL Challenge (tricky) - Bart (UK) - 03-14-2011 My sulotion is the same count as Raymond's: ```STR-> 3 roll 4 roll " " 2 ROLL + + " " 2 ROLL + + " " 2 ROLL + + " " 2 ROLL + + " " 2 ROLL + + ``` Also, your "That is, the shortest challenge solution program (UNDER THE ASSUMED TEMPLATE)" can become 8 "commands": ```\<< STR-> 3 ROLL 4 ROLL " " 2 ROLL + + " " 2 ROLL + + " " 2 ROLL + + " " 2 ROLL + + " " 2 ROLL + + \>> ``` Ideally the solution would be: StringToStack 3 ROLL 4 ROLL StackToString but the ->STR does not work like the ->ARRAY or ->LIST. However, using some commands not in listed the first post, this is an alternative: ```STR-> 3 ROLL 4 ROLL 6 -> LIST << " " 2 ROLL + + >> STREAM ``` -Bart Re: [RPL] ROLL Challenge (tricky) - Oliver Unter Ecker - 03-14-2011 Sorry, as Eric points out DROP is not in the list of allowed commands. Re: [RPL] ROLL Challenge (tricky) - Oliver Unter Ecker - 03-14-2011 Thank you, Bart. A second valid solution. You're tied with Ray with 8 commands. Your solution uses different ROLL args, so I wouldn't say it's "the same" as Ray's. The question remains if there might be a shorter solution. The ideal solution might be ```stringToStack rollIntoRightOrderAndStackToString ``` where rollIntoRightOrderAndStackToString uses up only 5 commands. Even 6 commands for this would still best the current total. Your STREAM solution is not in the running, but I like it! Edited: 17 Mar 2011, 3:15 p.m. Re: [RPL] ROLL Challenge (tricky) - Tim Wessman - 03-14-2011 Nah, makes perfect sense. :-) ```DOSTR> (equivalent to STR->) 2SWAP (swap with 2 arguments each being swapped, 1 2 3 4 -> 3 4 1 2) SWAP DEPTH (just like userRPL) {}N (equivalent to ->LIST) DO>STR (equivalent to ->STR) THREE OVERLEN\$ (get string in level 2 and do SIZE) #2- (subtract 2 from length) SUB\$ (SUBSTRING from 3-STRING_LEN_-2) ``` See, perfectly readable. As to the rules. . . :-P TW Edited: 14 Mar 2011, 12:39 p.m. Re: [RPL] ROLL Challenge (tricky) - Tim Wessman - 03-14-2011 How about "CLEAR"? :-) TW Re: [RPL] ROLL Challenge (tricky) - Oliver Unter Ecker - 03-14-2011 Here's a solution taking 7 commands. ```\<< STR-> "2 ROLL 5 ROLL 6 ROLL" STR-> "" + " " + 2 ROLL + " " + 2 ROLL + " " + 2 ROLL + " " + 2 ROLL + " " + 2 ROLL + \>> ``` Point here is that "2 ROLL 5 ROLL 6 ROLL" (or Bart's shorter sequence) is a string, the contents of which don't matter and don't count against the commands limit. If one of you posted this, I'd (reluctantly) accept it as solution. As I posted it, I'm calling this an attempt to circumvent the spirit of the challenge (although here STR-> truly *is* playing center-stage) and say it doesn't count. Number to beat is still 8. Edited: 14 Mar 2011, 12:53 p.m. Re: [RPL] ROLL Challenge (tricky) - Oliver Unter Ecker - 03-14-2011 Actually, better yet, here's a 6-command solution: ```\<< "STR-> 2 ROLL 5 ROLL 6 ROLL" STR-> "" + " " + 2 ROLL + " " + 2 ROLL + " " + 2 ROLL + " " + 2 ROLL + " " + 2 ROLL + \>> ``` And if string contents don't matter, even a one-command solution is possible: ```\<< "commands to solve problem not requiring quotes" STR-> \>> ``` Btw: There's no escape character for a quote to permit a string in a string in RPL, is there? (Something like "\" \"" in other languages.) Edited: 14 Mar 2011, 1:40 p.m. Re: [RPL] ROLL Challenge (tricky) - Oliver Unter Ecker - 03-17-2011 Ok. It's a challenge, after all. The number of commands to beat is 6. (With no trickery.) I'll post the solution tomorrow, if no-one feels inclined to preempt me. ;-) Edited: 17 Mar 2011, 12:52 p.m. Re: [RPL] ROLL Challenge (tricky) - Oliver Unter Ecker - 03-18-2011 Ok, here's the solution: ```\<< STR\-> " " + " " 2 ROLL + + 2 ROLL + " " + 2 ROLL + " " 2 ROLL + + " " 2 ROLL + + \>> ``` Note, no ROLL args other than 2 (which effectively is a SWAP) are used. Given that a minimum of 5 swaps are needed to glue the numbers on the stack back into a string, this is a minimal solution. Thank you to those who participated and spent some time on this! Apologies, for not having constructed this challenge better and not having a target number to beat when the challenge was fresh. The intended route--having to use programmatic construction of programs to test--seemingly unraveled, but it actually shifted from having to find indices, to having to find the minimal instruction ordering. Cheers. Re: [RPL] list ROLL Challenge (easy) - C.Ret - 03-23-2011 HI. Sorry, I read this too late to participate to this interesting challenge. NOTE to HP28C/S users: Please note that on HP28C/S the following sequence is illegal : `2 " " + ---------> + Error: Bad Argument Type.` So there is no solution to this challenge on HP28C/S since it is impossible to reconstruct any string from integers without a ->STR instruction. Proposition: Rephrased challenge for HP28C or HP28S users: Quote:Come up with a native RPL program compatible with any RPL's system (from HP28 to HP50 and sysRPL) that will transform ``` this list { 5 1 2 3 4 6 } into this list { 5 1 4 6 3 2 } using no more than 11 of only these commands:LIST-> (or OBJ-> which is tolerate on RPL system where no more LIST-> command exists)->LISTn ROLL (where n stand for any single key-digit 0 to 9). ``` Use of any numbers (except ROLL single key-digit argument), quotes and the "+" or "ADD" operator are prohibited since they may have a different behavior depending of the RPL system. Caveat: Repeated ROLLs may not be provided the same number as argument, whenever it's 2 or not. The program using the smallest number of commands practicable on any HP28C, HP28S, HP48, HP48gx, HP49 and HP50g wins. Special extra prize:to any winning program which reorders any list [bold]{ a b c d e f } into { a b e f d c } where a..f stand for any object. NOTE: n ROLL counts as two steps command. Edited: 23 Mar 2011, 1:11 p.m. Re: [RPL] list ROLL Challenge (easy) - Oliver Unter Ecker - 03-23-2011 Hi C.Ret, Yes, thanks for that correction. It should actually be further changed, because ROLL was a very poor choice. It made finding "a" solution (though not the intended one) way too easy. You probably guessed it, the solution I posted I didn't actually write myself. My RPL calc did. (Note that the challenge asks to "come up" with a solution, not "write" one...) I didn't post the full code because a) I'm using a couple of instructions in ND1 that don't exist on the 50g and I didn't have the time (yet) to look up implementations there and b) maybe I can construct a better challenge exploring this theme at another time, when everyone's forgotten about it... I wonder if algorithmic composition of RPL programs has been explored elsewhere. Let me say that I would have loved to see your solution on the HP-28S! I know you're an incredible wizard on the HP-28S--having solved the FibTriangle on it, is, I think, the biggest calculator-related surprise I had in my life. :-) Cheers. Edited: 23 Mar 2011, 3:10 p.m.