The Museum of HP Calculators

HP Forum Archive 20

[ Return to Index | Top of Index ]

[RPL] ROLL Challenge (tricky)
Message #1 Posted by Oliver Unter Ecker on 13 Mar 2011, 2:19 p.m.

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)
Message #2 Posted by Raymond Del Tondo on 13 Mar 2011, 7:09 p.m.,
in response to message #1 by Oliver Unter Ecker

Maybe this one?

STR->
6 ROLL " " +
6 ROLL + " " +
3 ROLL + " " +
2 ROLL + " " +
2 ROLL + " " +
2 ROLL +

Ray

            
Re: [RPL] ROLL Challenge (tricky)
Message #3 Posted by Eric Smith on 13 Mar 2011, 7:31 p.m.,
in response to message #2 by Raymond Del Tondo

He said that you can't use the same roll count more than once, except 2.

                  
Re: [RPL] ROLL Challenge (tricky)
Message #4 Posted by Raymond Del Tondo on 13 Mar 2011, 7:37 p.m.,
in response to message #3 by Eric Smith

Yes, it's _2_ ROLL, so that should be ok.

            
Re: [RPL] ROLL Challenge (tricky)
Message #5 Posted by Oliver Unter Ecker on 13 Mar 2011, 7:56 p.m.,
in response to message #2 by Raymond Del Tondo

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)
Message #6 Posted by Raymond Del Tondo on 13 Mar 2011, 8:34 p.m.,
in response to message #5 by Oliver Unter Ecker

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)
Message #7 Posted by Oliver Unter Ecker on 13 Mar 2011, 11:02 p.m.,
in response to message #6 by Raymond Del Tondo

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)
Message #8 Posted by Glen Sanft on 14 Mar 2011, 8:02 a.m.,
in response to message #7 by Oliver Unter Ecker

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)
Message #9 Posted by Eric Smith on 13 Mar 2011, 7:31 p.m.,
in response to message #1 by Oliver Unter Ecker

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)
Message #10 Posted by Oliver Unter Ecker on 13 Mar 2011, 8:05 p.m.,
in response to message #9 by Eric Smith

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)
Message #11 Posted by Oliver Unter Ecker on 13 Mar 2011, 8:39 p.m.,
in response to message #9 by Eric Smith

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)
Message #12 Posted by Oliver Unter Ecker on 13 Mar 2011, 8:48 p.m.,
in response to message #11 by Oliver Unter Ecker

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)
Message #13 Posted by Paul Dale on 14 Mar 2011, 1:06 a.m.,
in response to message #1 by Oliver Unter Ecker

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)
Message #14 Posted by Tim Wessman on 14 Mar 2011, 2:05 a.m.,
in response to message #13 by Paul Dale

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)
Message #15 Posted by Paul Dale on 14 Mar 2011, 2:16 a.m.,
in response to message #14 by Tim Wessman

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)
Message #16 Posted by reth on 14 Mar 2011, 7:03 a.m.,
in response to message #15 by Paul Dale

I'd like to know how many people *still* speak Latin only too

                  
Re: [RPL] ROLL Challenge (tricky)
Message #17 Posted by Oliver Unter Ecker on 14 Mar 2011, 6:49 a.m.,
in response to message #14 by Tim Wessman

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)
Message #18 Posted by Tim Wessman on 14 Mar 2011, 12:36 p.m.,
in response to message #17 by Oliver Unter Ecker

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)
Message #19 Posted by Eric Smith on 14 Mar 2011, 2:13 a.m.,
in response to message #13 by Paul Dale

I don't see "DROP" in the list of allowed commands. Otherwise I would have used it myself. :-)

      
Re: [RPL] ROLL Challenge (tricky)
Message #20 Posted by Oliver Unter Ecker on 14 Mar 2011, 6:39 a.m.,
in response to message #1 by Oliver Unter Ecker

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)
Message #21 Posted by Oliver Unter Ecker on 14 Mar 2011, 7:14 a.m.,
in response to message #20 by Oliver Unter Ecker

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)
Message #22 Posted by Bart (UK) on 14 Mar 2011, 10:22 a.m.,
in response to message #20 by Oliver Unter Ecker

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)
Message #23 Posted by Oliver Unter Ecker on 14 Mar 2011, 12:34 p.m.,
in response to message #22 by Bart (UK)

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)
Message #24 Posted by David Hayden on 14 Mar 2011, 8:50 a.m.,
in response to message #1 by Oliver Unter Ecker

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)
Message #25 Posted by Oliver Unter Ecker on 14 Mar 2011, 12:13 p.m.,
in response to message #24 by David Hayden

Sorry, as Eric points out DROP is not in the list of allowed commands.

                  
Re: [RPL] ROLL Challenge (tricky)
Message #26 Posted by Tim Wessman on 14 Mar 2011, 12:38 p.m.,
in response to message #25 by Oliver Unter Ecker

How about "CLEAR"? :-)

TW

      
Re: [RPL] ROLL Challenge (tricky)
Message #27 Posted by Oliver Unter Ecker on 14 Mar 2011, 12:53 p.m.,
in response to message #1 by Oliver Unter Ecker

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)
Message #28 Posted by Oliver Unter Ecker on 14 Mar 2011, 1:14 p.m.,
in response to message #27 by Oliver Unter Ecker

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)
Message #29 Posted by Oliver Unter Ecker on 17 Mar 2011, 12:50 p.m.,
in response to message #1 by Oliver Unter Ecker

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)
Message #30 Posted by Oliver Unter Ecker on 18 Mar 2011, 7:20 p.m.,
in response to message #29 by Oliver Unter Ecker

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)
Message #31 Posted by C.Ret on 23 Mar 2011, 12:22 p.m.,
in response to message #30 by Oliver Unter Ecker

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)
->LIST
n 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)
Message #32 Posted by Oliver Unter Ecker on 23 Mar 2011, 3:08 p.m.,
in response to message #31 by C.Ret

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.


[ Return to Index | Top of Index ]

Go back to the main exhibit hall