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 retooled 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 nonlinear/headspinning 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 samearg ROLLs are allowed > 6 6 PERM (=720) possible programs.
One instruction is a noop: 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 nonnoop 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 onthefly. 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 nogo 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 retooling to assume a new template but keeping the brute force approach.
Edited: 14 Mar 2011, 7:09 a.m.
