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.

Maybe this one?

STR->

6 ROLL " " +

6 ROLL + " " +

3 ROLL + " " +

2 ROLL + " " +

2 ROLL + " " +

2 ROLL +

Ray

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.

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

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

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?

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.

Now I see what Eric meant.

Ok, the sequence

STR-> 6 ROLL " " +

STR-> " " 7 ROLL 2 ROLL +

resulting in one more ROLL;-)

Quote:

---

lots of Monkeys on typewriters?

---

Edited: 13 Mar 2011, 8:37 p.m.

Hey, wait! What's that "-" doing in your solution? (MOC grabs trophy back from would-be winner.)

Back to original strings.

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".

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.

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

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

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

Quote:

---

(I really can't program userRPL... brain to used to sys)

---

I'm a bit surprised that sysRPL is still in vogue :-)

- Pauli

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

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.

Holy...

Ok. This one wins the "most rules-disrespecting while simultaneously unreadable though probably working" price.

(Nice, though, if you like scary...)

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

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.

Quote:

---

The monkeys on typewriters will be explained tomorrow.

---

:)

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.

My sulotion is the same count as Raymond's:

STR->

3 roll

4 roll

" " 2 ROLL + +

" " 2 ROLL + +

" " 2 ROLL + +

" " 2 ROLL + +

" " 2 ROLL + +

\<< STR->

    3 ROLL 4 ROLL

    " " 2 ROLL + + " " 2 ROLL + + " " 2 ROLL + + " " 2 ROLL + + " " 2 ROLL + +

\>>

STR->

3 ROLL

4 ROLL

6 -> LIST

<< " " 2 ROLL + + >>

STREAM

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

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.

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.

How about "CLEAR"? :-)

TW

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.

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.

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.

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.

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.

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.