[RPL] ROLL Challenge (tricky) Oliver Unter Ecker Member Posts: 239 Threads: 9 Joined: Dec 2010 03-13-2011, 02:19 PM 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. Raymond Del Tondo Posting Freak Posts: 1,841 Threads: 54 Joined: Jul 2005 03-13-2011, 07:09 PM Maybe this one? ```STR-> 6 ROLL " " + 6 ROLL + " " + 3 ROLL + " " + 2 ROLL + " " + 2 ROLL + " " + 2 ROLL + ``` Ray Eric Smith Posting Freak Posts: 2,309 Threads: 116 Joined: Jun 2005 03-13-2011, 07:31 PM 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. Eric Smith Posting Freak Posts: 2,309 Threads: 116 Joined: Jun 2005 03-13-2011, 07:31 PM He said that you can't use the same roll count more than once, except 2. Raymond Del Tondo Posting Freak Posts: 1,841 Threads: 54 Joined: Jul 2005 03-13-2011, 07:37 PM Yes, it's _2_ ROLL, so that should be ok. Oliver Unter Ecker Member Posts: 239 Threads: 9 Joined: Dec 2010 03-13-2011, 07:56 PM 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? Oliver Unter Ecker Member Posts: 239 Threads: 9 Joined: Dec 2010 03-13-2011, 08:05 PM 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. Raymond Del Tondo Posting Freak Posts: 1,841 Threads: 54 Joined: Jul 2005 03-13-2011, 08:34 PM 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. Oliver Unter Ecker Member Posts: 239 Threads: 9 Joined: Dec 2010 03-13-2011, 08:39 PM Hey, wait! What's that "-" doing in your solution? (MOC grabs trophy back from would-be winner.) Back to original strings. Oliver Unter Ecker Member Posts: 239 Threads: 9 Joined: Dec 2010 03-13-2011, 08:48 PM 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". Oliver Unter Ecker Member Posts: 239 Threads: 9 Joined: Dec 2010 03-13-2011, 11:02 PM 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. Paul Dale Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 03-14-2011, 01:06 AM 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 Tim Wessman Posting Freak Posts: 1,278 Threads: 44 Joined: Jul 2007 03-14-2011, 02:05 AM 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 Eric Smith Posting Freak Posts: 2,309 Threads: 116 Joined: Jun 2005 03-14-2011, 02:13 AM I don't see "DROP" in the list of allowed commands. Otherwise I would have used it myself. :-) Paul Dale Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 03-14-2011, 02:16 AM Quote:(I really can't program userRPL... brain to used to sys) I'm a bit surprised that sysRPL is still in vogue :-) - Pauli Oliver Unter Ecker Member Posts: 239 Threads: 9 Joined: Dec 2010 03-14-2011, 06:39 AM 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. Oliver Unter Ecker Member Posts: 239 Threads: 9 Joined: Dec 2010 03-14-2011, 06:49 AM Holy... Ok. This one wins the "most rules-disrespecting while simultaneously unreadable though probably working" price. (Nice, though, if you like scary...) Reth Senior Member Posts: 556 Threads: 9 Joined: Jul 2007 03-14-2011, 07:03 AM I'd like to know how many people *still* speak Latin only too Oliver Unter Ecker Member Posts: 239 Threads: 9 Joined: Dec 2010 03-14-2011, 07:14 AM 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. Glen Sanft Junior Member Posts: 20 Threads: 1 Joined: Feb 2011 03-14-2011, 08:02 AM Quote: The monkeys on typewriters will be explained tomorrow. We're all familiar with the story of how Microsoft develops product... :) David Hayden Senior Member Posts: 528 Threads: 40 Joined: Dec 2008 03-14-2011, 08:50 AM ```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. Bart (UK) Posting Freak Posts: 850 Threads: 10 Joined: Mar 2009 03-14-2011, 10:22 AM 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 Oliver Unter Ecker Member Posts: 239 Threads: 9 Joined: Dec 2010 03-14-2011, 12:13 PM Sorry, as Eric points out DROP is not in the list of allowed commands. Oliver Unter Ecker Member Posts: 239 Threads: 9 Joined: Dec 2010 03-14-2011, 12:34 PM 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. Tim Wessman Posting Freak Posts: 1,278 Threads: 44 Joined: Jul 2007 03-14-2011, 12:36 PM 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. Tim Wessman Posting Freak Posts: 1,278 Threads: 44 Joined: Jul 2007 03-14-2011, 12:38 PM How about "CLEAR"? :-) TW Oliver Unter Ecker Member Posts: 239 Threads: 9 Joined: Dec 2010 03-14-2011, 12:53 PM 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. Oliver Unter Ecker Member Posts: 239 Threads: 9 Joined: Dec 2010 03-14-2011, 01:14 PM 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. Oliver Unter Ecker Member Posts: 239 Threads: 9 Joined: Dec 2010 03-17-2011, 12:50 PM 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. Oliver Unter Ecker Member Posts: 239 Threads: 9 Joined: Dec 2010 03-18-2011, 07:20 PM 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. C.Ret Senior Member Posts: 260 Threads: 0 Joined: Oct 2008 03-23-2011, 12:22 PM 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. Oliver Unter Ecker Member Posts: 239 Threads: 9 Joined: Dec 2010 03-23-2011, 03:08 PM 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. « Next Oldest | Next Newest »

 Possibly Related Threads... Thread Author Replies Views Last Post Writing RPL programs on OS X Sean Freeman 18 2,452 11-30-2013, 03:59 PM Last Post: Sean Freeman 48G vs 49G+ User RPL Speed Comparison John Colvin 7 1,122 11-16-2013, 10:07 PM Last Post: Han RPL 32 David Hayden 4 936 11-11-2013, 11:34 AM Last Post: David Hayden Roll-down key in HP-15C Steve Ross 6 1,190 10-15-2013, 04:12 AM Last Post: Nick_S HHC / HP Museum Programming Contest for RPN and RPL machines Gene Wright 18 2,337 09-22-2013, 09:39 AM Last Post: Miguel Toro (Printer) Roll Call Matt Agajanian 2 628 08-26-2013, 09:48 PM Last Post: Matt Agajanian RPL long vs. short names peacecalc 5 944 10-30-2012, 01:25 PM Last Post: peacecalc Mini-challenge: HHC2012 RPL programming contest with larger input David Hayden 14 1,837 10-05-2012, 10:36 PM Last Post: David Hayden HHC 2012 RPL Programming Contest Gene Wright 33 3,435 09-27-2012, 01:57 AM Last Post: Werner HHC 2012 programming contests coming soon (RPN and RPL) Gene Wright 9 1,295 09-21-2012, 03:38 PM Last Post: Paul Dale

Forum Jump: