Could you massage this stack for me?

Question

Forth is one of the few non-esoteric stack-based languages. For this challenge, we will use a small subset of Forth, which simply executes a sequence of words in a linear fashion — without any definitions or loops.

In good Forth code, each word definition includes a stack effect comment, which explains the layout of the stack before and after the word's execution. For example, + has the stack effect a b -- sum, swap has the stack effect a b -- b a, and fill does ptr len byte --. Both before and after the --, the top of the stack is to the right, and thus the stack elements are written in the order in which you'd have to push them.

Note that, if the word only manipulates the order of elements on stack, the stack effect is a complete specification of its behavior. Your task is to write a program or function that takes such a stack effect as input, and emits an implementation of it in the subset of Forth described below.

The Forth subset

Your output may make use of the words drop, dup, swap, >r and r>. Three of those are fully specified by their stack effect:

drop ( a -- )
dup ( a -- a a )
swap ( a b -- b a )

The last two make use of the return stack. Apart from the main data stack, Forth also has another stack, which is used to save return addresses while calling user-defined words. However, since Forth implementers are trusting people, the programmer may also store their own data on the return stack within one procedure, as long as they clean it up before returning.

To use the return stack, we have the last two words:

• >r ( x -- ; R: -- x ) moves an item from the data stack to the return stack
• r> ( -- x ; R: x -- ) moves an item from the return stack back to the data stack

Your code must use the return stack on in a balanced manner.

Example

Let's take a close look at one of the programs you could output given the input c a b -- b a b.

      Data stack    Return stack
      c a b
swap  c b a
>r    c b           a
swap  b c           a
drop  b             a
dup   b b           a
r>    b b a
swap  b a b

Here, swap >r swap drop dup r> swap would be your output.

Input and output

Your input will consist of two lists of names, describing the before and after states of the stack. The names in the first list will all be unique. The names in the second list all occur in the first one.

The output list may contain duplicates, and it does not need to include every name from the input list.

Parsing is not a part of the challenge, so you may use any reasonable format for these lists. Some examples of the input formats you can choose:

"a b -- b a"
"a b", "b a"
"ab:ba"
["a", "b"], ["b", "a"]
[2, 7], [7, 2]

In particular, you are allowed to reverse the ordering, taking the top of the stack to be the beginning of each list.

Your output, which represents a Forth program, can also use any way of encoding a sequence of instructions. For example:

"drop swap dup >r swap r>"
"xsd>s<"
"earwax"
[3, 2, 1, 0, 2, 4]

Test cases

Each test consists of two lines. The first is the input, but since the solution isn't unique, the second line is merely an example of what the output can look like. You can use this Python program to check that the programs you are generating are correct.

If you'd like to generate some larger test cases, use this script.

a b -- a b a
>r dup r> swap

a b -- b a b
swap >r dup r> swap

c a b -- b a b
swap >r swap drop dup r> swap

a b c -- c b a
swap >r swap r> swap

a b c -- b c a
>r swap r> swap

a b c d -- d a c
swap >r swap drop swap r>

a b c d -- d c b a
swap >r swap >r swap r> swap r> swap >r swap r>

Answer 1

K (ngn/k), 42 bytes

{,//a,({(x#2;|!3;x#,3 0)}'x?y),2+a,2+a:~x}

Try it online!

Verify the test cases!

Takes the input as two lists of positive integers (or chars). Returns a list of integers, where 0 1 2 3 4 is mapped to >r dup r> swap drop respectively.

How it works

This uses a simple, highly systematic approach. First, all items are moved to the return stack. Then the return stack is used like a "variable stack", so each requested item is fetched in order, preserving the return stack after each fetch. Finally, the return stack is cleared.

Using ( a b -- a b a ) as an example:

>r >r     Move a and b to the return stack
          a is the top (zeroth) item on the R-stack, b is the next one
r> dup >r               Fetch a
r> r> dup >r swap >r    Fetch b
r> dup >r               Fetch a
r> r> drop drop    Clear the return stack

In general, in order to fecth n-th item (0-based), the following sequence is used:

n+1 copies of r>    Move n+1 items from return stack to main stack
dup >r              Copy nth item and move one copy back to return stack
n copies of (swap >r)   Move the unneeded items to return stack

Answer 2

Julia 0.7, 188 bytes

b>a=push!(a,pop!(b))
a\b=for i=1:-1%UInt,j=Iterators.product(fill(1:5,i)...)
try
s=+a;r=[];z=[]
j.|>k->k<2?s>z:k<3?[s[end]]>s:k<4?(s>z;s>r;z>s;r>s):k<5?s>r:r>s
s==b&&return j
catch;end
end

Try it online!

brute-force approach.

b>a=push!(a,pop!(b)) is used a lot to shorten the code. r is the return stack, and z is a stack used for swap and drop

inputs are 2 lists of numbers, output is a list of number, where:

1: drop
2: dup
3: swap
4: >r
5: r>

last test case takes over 1 minute for TIO to compute

Bubbler's answer is probably smarter but let's say my program gives the shortest answer possible

Answer 3

Zsh -e, 86 bytes

echo $(for x<<<A
for y (`<i`)(<<<G\ A;for x;{<<<F;((x-y));<<<S\ A})|sort
for x<<<F\ X)

Attempt This Online!

It's hard to cut down on the <<< repetition.

Uses almost the same method as Bubbler's answer, except it ends with r> drop r> drop ... instead of r> r> ... drop drop ....

Names are integers. Expects the input stack on the command-line and the output stack in a file called i.

Output encoding:

A  >r
F  r>
G  dup
S  swap
X  drop

The second line loops over the output stack and produces instructions to retrieve each item. The strange letter choices are to finagle the possible outputs into the right orders so that sort can arrange them correctly into the order of instructions Bubbler describes:

To fetch the n'th item (0-indexed), the following sequence is used:

n+1 copies of (r>)      Move n+1 items from return stack to main stack
(dup >r)                Copy nth item and move one copy back to return stack
n copies of (swap >r)   Move the unneeded items to return stack

This saves over a repeat loop and finding the index using Zsh's builtin ${@[(i)$y]} (which is quite a mouthful)

I use ((x-y)) to manually find the index of the item y. If x equals y then x-y is zero, the (()) exits with a "failure" status code, and thanks to the -e option, that failure implicitly exits and breaks out of the loop, but only until the innermost layer of (). This is a much shorter than break.

echo $() collapses all newlines into spaces.

Answer 4

Jelly, (26?) 27 bytes

^{26 if the result need not be flat (while still consistent) - remove trailing F}

iⱮ’“¡©“®¢‘xⱮj€12b4;,a"4,1ɗF

A dyadic Link that accepts the starting data stack in reverse on the left and the final data stack in reverse on the left and yields a list of integers:

0 >r
1 r>
2 swap
3 dup
4 drop

Try it online! (Footer formats like the question does.)

Or see the Python suite of test results.

How?

This builds the reverse of the final data stack in the return stack one item at a time by "copying" the item from the data stack, leaving the data stack unaffected, then it drops all of the original items from the data stack and pulls all the copied items back.

To "copy" an item it pushes all those above it, then repeatedly pulls and swaps so that all the original main items are back on the data stack with the required item on top, then duplicates and pushes and then performs the conjugate of everything before the duplication to get main back to how it started.

For example, to push d from abcd... (where a is on top):

>r >r >r r> swap r> swap r> swap dup >r swap >r swap >r swap >r r> r> r>

...or

(>r)*3 (r> swap)*3 (dup >r) (swap >r)*3 (r>)*3

Where 3 is three because there are three items on top of d.

Code breakdown

iⱮ’“¡©“®¢‘xⱮj€12b4;,a"4,1ɗF - Link: starting (reversed); final (reversed)
 Ɱ                          - map with:
i                           -   first index of (final item) in (starting items)
  ’                         - decrement -> 0-based indices
   “¡©“®¢‘                  - code-page indices = [[0,6],[8,1]]
           Ɱ                - map with:
          x                 -   times - e.g. 3 -> [[0,0,0,6,6,6],[8,8,8,1,1,1]]
            j€12            - join each with twelves
                b4          - convert from base four
                                0->[0]; 6->[1,2]; 12->[3,0]; 8->[2,0]; 1->[1]
                         ɗ  - last three links as a dyad - f(starting, final):
                   ,        -   pair -> [starting, final] e.g. ["abc","ba"]
                      4,1   -   [4,1]                          [4,1]
                     "      -   zip with:
                    a       -     logical AND                  [[4,4,4],[1,1]]
                  ;         - concatenate
                          F - flatten