11
\$\begingroup\$

Let's say you have a stack, which at the start contains a b c in this order (a is on the top). You are given the required output stack, in any reasonable format (a list, a string, etc.), e.g. [a, c, b] (here a is on the top, below it c and below it b). You can also take the input reversed if you want, e.g. [b, c, a] where a is in the top

Your task is to output the shortest sequence of operations to achieve that stack formation, and you may assume that there is such sequence, and it's shorter than 10 moves:

  • s - swap the top two elements of the stack, a b c -> b a c

  • d - duplicate the top element of the stack, a b c -> a a b c

  • t - swap (or rotate) the top three elements of the stack, a b c -> b c a

You may call the input/operations whatever you want, as long as it's consistent.

Examples

['a', 'c', 'b'] -> st
([a b c] [b a c] [a c b])
['a','a','b','c'] -> d
['a','b','a','b','c'] -> sdtsdt
([a b c] [b a c] [b b a c] [b a b c] [a b b c] [a a b b c] [a b a b c]) (sdttdt is also valid)
['c','b','a'] -> ts

This is an example ungolfed algorithm which solves it: https://pastebin.com/9UemcUwj

Score

This is a codegolf, so the shortest answer wins. good luck!

Improve this question
\$\endgroup\$
12
  • \$\begingroup\$ right, I've found it and forgot to update, sorry \$\endgroup\$
    – Command Master
    Apr 10, 2020 at 12:04
  • \$\begingroup\$ @Noodle9 sorry, I've accidentally put there an impossible sequance \$\endgroup\$
    – Command Master
    Apr 10, 2020 at 12:17
  • \$\begingroup\$ should be fixed now \$\endgroup\$
    – Command Master
    Apr 10, 2020 at 12:17
  • 3
    \$\begingroup\$ @xnor You're indeed correct. When we don't use any duplicates, the swaps and triple-swaps could put the three values in any order. But as soon as a duplicate is used, the at that point bottom item on the stack will remain the bottom item, since the swap and triple-swap can no longer touch this fourth item on the stack. \$\endgroup\$
    – Kevin Cruijssen
    Apr 10, 2020 at 13:35
  • 2
    \$\begingroup\$ @KevinCruijssen Thanks for the observation. I needed to also convince myself that we can always avoid making one of the two remaining elements "go extinct". For instance, if you try to create b a a a b c and do a b c -> a a b c -> a a a b c, you get stuck. But, you can avoid this by doing a b c -> b a c -> b b a c -> a b b c -> a a b b c -> a b a b c -> a a b a b c -> b a a a b c. (I'm writing any permutation of the top 3 elements as a single step.) In particular, you should always keep two copies of the next element that you need to commit. I hope this allows a short direct solution. \$\endgroup\$
    – xnor
    Apr 10, 2020 at 14:08

7 Answers 7

Reset to default
8
\$\begingroup\$

Python 2, 117 bytes

Simple BFS brute-force algorithm, outputs to STDERR.

t=input()
l=[('abc','')]
for s,o in l:s==t>exit(o);l+=(s[1:3]+s[0]+s[3:],o+'t'),(s[0]+s,o+'d'),(s[1::-1]+s[2:],o+'s')

Try it online!

Combined with Surcoloses way of generating the new stacks, this gets to 97 bytes: Try it online!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Took me a while to understand s==t>exit(o). Simply awesome! \$\endgroup\$
    – Surculose Sputum
    Apr 10, 2020 at 14:03
  • 2
    \$\begingroup\$ 97 bytes by using 1,2,3 instead of d,s,t which allows shorter way to generate new stack. \$\endgroup\$
    – Surculose Sputum
    Apr 10, 2020 at 14:15
  • 1
    \$\begingroup\$ @SurculoseSputum thanks for the suggestion. I have added this as a note, since I feel this more similar to your answer than to mine. \$\endgroup\$
    – ovs
    Apr 10, 2020 at 18:04
8
\$\begingroup\$

JavaScript (ES6), 79 bytes

Expects 460 instead of abc. Output format: \$1\$ = swap, \$2\$ = duplicate and \$3\$ = rotate.

Same logic as the main version, but with a less readable input format which was chosen to optimize the lookup table.

f=s=>([a,b,c]=s,d=s.slice(3))?a-b?f(c+a+b+d)+3:f(b+c+d)+2:[[13,31,3,1,33][s%7]]

Try it online!

JavaScript (ES6),  100 ... 84  81 bytes

Expects 012 instead of abc. Output format: \$1\$ = swap, \$2\$ = duplicate and \$3\$ = rotate.

f=s=>([a,b,c]=s,d=s.slice(3))?a-b?f(c+a+b+d)+3:f(b+c+d)+2:[[3,33,31,,,13,1][s&7]]

Try it online!

How?

This solves the problem by starting with the input string and transforming it back into "012".

Step 1

The first step of the algorithm is to reverse duplicate and rotate operations until the string is exactly 3-character long.

We can notice that given an input string of length \$n\$, there are necessarily \$n-3\$ duplicate.

We can reverse a duplicate operation whenever the first 2 characters of the string are equal.

If the first 2 characters are not equal and the string is still longer than 3 characters, it means that we have to reverse a rotate. (It can't be a swap because the first 2 characters would still be different.)

We need to reverse at most 2 consecutive rotate before we can reverse the next duplicate. (If it still doesn't work after 2 reversed rotate, it means that the input is invalid.)

Step 2

Once we have a string \$s\$ which is 3-character long, we use a lookup table to figure out how "012" can be turned into \$s\$ with as few operations as possible:

"012" : no operation
"021" : "st" because t(s("012")) = t("102") = "021"
"102" : "s"  because s("012") = "102"
"120" : "t"  because t("012") = "120"
"201" : "tt" because t(t("012")) = t("120") = "201"
"210" : "ts" because s(t("012")) = s("120") = "210"

The lookup table works by coercing the string to an integer an applying a modulo \$8\$.

 string | mod 8
--------+-------
  "012" |   4
  "021" |   5
  "102" |   6
  "120" |   0
  "201" |   1
  "210" |   2

Commented

f = s =>               // s = input string
  (                    //
    [a, b, c] = s,     // split the first 3 characters as a, b and c
    d = s.slice(3)     // d = all remaining characters after the 3 first ones
  ) ?                  // if d is not empty:
    a - b ?            //   if a is not equal to b:
      f(c + a + b + d) //     reverse a 'rotate' by re-ordering the first 3 characters
      + 3              //     append a "3"
    :                  //   else:
      f(b + c + d)     //     reverse a 'duplicate' by removing the leading character
      + 2              //     append a "2"
  :                    // else:
    [                  //   make sure the following result can be coerced to a string:
      [                //     lookup table:
        3              //       0: "120" -> "t" encoded as "3"
        33,            //       1: "201" -> "tt" encoded as "33"
        31,            //       2: "210" -> "ts" encoded as "31"
        ,              //       3: not used
        ,              //       4: "012" -> no operation
        13,            //       5: "021" -> "st" encoded as "13"
        1              //       6: "102" -> "s" encoded as "1"
      ]                //
      [s & 7]          //     compute s mod 8
    ]                  //
Improve this answer
\$\endgroup\$
6
\$\begingroup\$

Python 3.8, 105 bytes

f=lambda r,i=0,j=1,s="abc",*l:(t:=i%4)and f(r,i//4,j,s[t>1:t]+s[0]+s[t:],*l,t)or f(r,j,j+1)if s!=r else l

Try it online!

Input: A string representing the goal stack, where the first character of the string is the top of the stack.
Output: A tuple of 0,1,2 representing d,s,t respectively.

This is a brute-force recursive search that simply tries all possible operation sequences of increasing size.

102 bytes if the solution doesn't have to deal with the edge case "abc"

f=lambda r,i=0,j=1,s="abc",*l:(t:=i%4)and f(r,i//4,j,s[t>1:t]+s[0]+s[t:],*l,t)or(s==r)*l or f(r,j,j+1)

Try it online!

How:

Given the stack s as a string, and an operation t = 1, 2, or 3 reperesenting d, s, t respectively, the resulting stack is:

s[t>1:t]+s[0]+s[t:]

A sequence of operations can be encoded as a single integer j, and decoded using division and mod. The solution simply increment j, then test if j can produces the goal stack. This guarantees that the result sequence is the shortest.

The argument i keeps track of the remaining operations in the current sequence. l is the tuple of operations performed.

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

Haskell, 111 110 bytes

g s=[b|(a,b)<-zip f o,a==s]!!0
f="abc":(f>>=k)
k w@(a:b:c:s)=[b:c:a:s,a:w,b:a:c:s]
o="":[x++[w]|x<-o,w<-"tds"]

Try it online!

Finds the position of the target stack in an infinite list of possible stacks f, then uses the result to index into the infinite list of operations o.

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Retina 0.8.2, 88 82 79 bytes

^(.)(\1[a-c]+)
$2d
}`^(.)(.)(\1|\2)([a-c]+)
$3$1$2$4t
abc

ac|bac?
s
a

bc?|c
t

Try it online! Link includes test cases. Uses @xnor's direct approach. Explanation:

^(.)(\1[a-c]+)
$2d

If the first two characters are the same, then they must have just been duplicated, so output a d and remove the first character. (The [a-c] ensures that the outputs collect in reverse order.)

^(.)(.)(\1|\2)([a-c]+)
$3$1$2$4t

If the third character is one of the first two, then try rotating the stack.

}`

Repeat the above stages until the three characters are all different, in which case they should be the last three.

abc

If they are abc then there is nothing left to do.

ac|bac?
s

acb, bac, and cba all need a swap. For bac this completes the operations; acb needs a rotation after the swap, while cba needs a rotation before the swap. Leaving a b or c behind will achieve this later.

a

Remove any remaining as as they have nothing left to contribute.

bc?|c
t

Any remaining bs and cs indicate rotations, except that bc is just one rotation.

Previous brute-force 82-byte solution:

$
¶abc:
{`^(.+)¶(.+¶)*\1:(.*)(¶.+)*$
$3
(.)(.)(.)(.*:.*)
$2$1$3$4s¶$1$&d¶$2$3$1$4t

Try it online! Link includes test cases. Edit: Saved 6 bytes thanks to @someone. Explanation:

$
¶abc:

Append the initial position to the input.

{`

Repeat until a solution is found.

^(.+)¶(.+¶)*\1:(.*)(¶.+)*$
$3

If the input matches an output stack, delete everything except the output sequence.

(.)(.)(.)(.*:.*)
$2$1$3$4s¶$1$&d¶$2$3$1$4t

For each position, compute the three positions arising from applying each of the three operators.

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I think $1$2$3$4 -> $0. \$\endgroup\$
    – the default.
    Apr 10, 2020 at 13:45
  • \$\begingroup\$ @someone Bah, I spent ages trying to think of ways to simplify all of those $s and yet overlooked the obvious one... \$\endgroup\$
    – Neil
    Apr 10, 2020 at 14:00
  • \$\begingroup\$ In fact, I thought about the ages I'd spend trying to simplify all of those $s and decided not to write a Retina answer :) \$\endgroup\$
    – the default.
    Apr 10, 2020 at 14:57
3
\$\begingroup\$

05AB1E, 21 18 17 bytes

g…sŠD×æé.Δ₁`r.V)Q

-1 byte by taking the input as 256 (₁) for abc respectively, instead of ABC (žR) I had prior.

Takes the input in reversed order using the characters 256 for abc respectively.
Outputs s for swap; D for duplicate; and Š for triple swap/rotate.

Try it online or verify all test cases.

Explanation:

g           # Get the length of the (implicit) input-list
 …sŠD       # Push the string "sŠD"
     ×      # Repeat it the length amount of times
      æ     # Take the powerset of this
       é    # Sort them by length
            #  i.e. input-length=3 → ["","s","Š","D","s","Š","D","s","Š","D","sŠ","sD","ŠD","ss","Šs","Ds","sŠ","ŠŠ","DŠ","sŠ","sD","ŠD","DD","sD","ŠD","ss","Šs","Ds","ss","Šs","Ds","sŠ","ŠŠ","DŠ","sŠ","ŠŠ","DŠ","sŠ","sD","ŠD","DD","sD","ŠD","DD","sD","ŠD","sŠD","sŠs","sDs","ŠDs","sŠŠ","sDŠ","ŠDŠ","ssŠ","ŠsŠ","DsŠ","sŠD","sDD","ŠDD","ssD","ŠsD","DsD","sŠD","ŠŠD","DŠD","sŠD","sŠs","sDs","ŠDs","sss","Šss","Dss","sŠs","ŠŠs","DŠs","sŠs","sDs","ŠDs","DDs","sDs","ŠDs","sŠŠ","sDŠ","ŠDŠ","ssŠ","ŠsŠ","DsŠ","sŠŠ","ŠŠŠ","DŠŠ","sŠŠ","sDŠ","ŠDŠ","DDŠ","sDŠ","ŠDŠ","ssŠ","ŠsŠ","DsŠ","ssŠ","ŠsŠ","DsŠ","sŠD","sDD","ŠDD","ssD","ŠsD","DsD","sŠD","ŠŠD","DŠD","sŠD","sDD","ŠDD","DDD","sDD","ŠDD","ssD","ŠsD","DsD","ssD","ŠsD","DsD","sŠD","ŠŠD","DŠD","sŠD","ŠŠD","DŠD","sŠD","sŠDs","sŠDŠ","sŠsŠ","sDsŠ","ŠDsŠ","sŠDD","sŠsD","sDsD","ŠDsD","sŠŠD","sDŠD","ŠDŠD","ssŠD","ŠsŠD","DsŠD","sŠDs","sŠss","sDss","ŠDss","sŠŠs","sDŠs","ŠDŠs","ssŠs","ŠsŠs","DsŠs","sŠDs","sDDs","ŠDDs","ssDs","ŠsDs","DsDs","sŠDs","ŠŠDs","DŠDs","sŠDs","sŠDŠ","sŠsŠ","sDsŠ","ŠDsŠ","sŠŠŠ","sDŠŠ","ŠDŠŠ","ssŠŠ","ŠsŠŠ","DsŠŠ","sŠDŠ","sDDŠ","ŠDDŠ","ssDŠ","ŠsDŠ","DsDŠ","sŠDŠ","ŠŠDŠ","DŠDŠ","sŠDŠ","sŠsŠ","sDsŠ","ŠDsŠ","sssŠ","ŠssŠ","DssŠ","sŠsŠ","ŠŠsŠ","DŠsŠ","sŠsŠ","sDsŠ","ŠDsŠ","DDsŠ","sDsŠ","ŠDsŠ","sŠDD","sŠsD","sDsD","ŠDsD","sŠŠD","sDŠD","ŠDŠD","ssŠD","ŠsŠD","DsŠD","sŠDD","sDDD","ŠDDD","ssDD","ŠsDD","DsDD","sŠDD","ŠŠDD","DŠDD","sŠDD","sŠsD","sDsD","ŠDsD","sssD","ŠssD","DssD","sŠsD","ŠŠsD","DŠsD","sŠsD","sDsD","ŠDsD","DDsD","sDsD","ŠDsD","sŠŠD","sDŠD","ŠDŠD","ssŠD","ŠsŠD","DsŠD","sŠŠD","ŠŠŠD","DŠŠD","sŠŠD","sDŠD","ŠDŠD","DDŠD","sDŠD","ŠDŠD","ssŠD","ŠsŠD","DsŠD","ssŠD","ŠsŠD","DsŠD","sŠDsŠ","sŠDsD","sŠDŠD","sŠsŠD","sDsŠD","ŠDsŠD","sŠDss","sŠDŠs","sŠsŠs","sDsŠs","ŠDsŠs","sŠDDs","sŠsDs","sDsDs","ŠDsDs","sŠŠDs","sDŠDs","ŠDŠDs","ssŠDs","ŠsŠDs","DsŠDs","sŠDsŠ","sŠDŠŠ","sŠsŠŠ","sDsŠŠ","ŠDsŠŠ","sŠDDŠ","sŠsDŠ","sDsDŠ","ŠDsDŠ","sŠŠDŠ","sDŠDŠ","ŠDŠDŠ","ssŠDŠ","ŠsŠDŠ","DsŠDŠ","sŠDsŠ","sŠssŠ","sDssŠ","ŠDssŠ","sŠŠsŠ","sDŠsŠ","ŠDŠsŠ","ssŠsŠ","ŠsŠsŠ","DsŠsŠ","sŠDsŠ","sDDsŠ","ŠDDsŠ","ssDsŠ","ŠsDsŠ","DsDsŠ","sŠDsŠ","ŠŠDsŠ","DŠDsŠ","sŠDsŠ","sŠDsD","sŠDŠD","sŠsŠD","sDsŠD","ŠDsŠD","sŠDDD","sŠsDD","sDsDD","ŠDsDD","sŠŠDD","sDŠDD","ŠDŠDD","ssŠDD","ŠsŠDD","DsŠDD","sŠDsD","sŠssD","sDssD","ŠDssD","sŠŠsD","sDŠsD","ŠDŠsD","ssŠsD","ŠsŠsD","DsŠsD","sŠDsD","sDDsD","ŠDDsD","ssDsD","ŠsDsD","DsDsD","sŠDsD","ŠŠDsD","DŠDsD","sŠDsD","sŠDŠD","sŠsŠD","sDsŠD","ŠDsŠD","sŠŠŠD","sDŠŠD","ŠDŠŠD","ssŠŠD","ŠsŠŠD","DsŠŠD","sŠDŠD","sDDŠD","ŠDDŠD","ssDŠD","ŠsDŠD","DsDŠD","sŠDŠD","ŠŠDŠD","DŠDŠD","sŠDŠD","sŠsŠD","sDsŠD","ŠDsŠD","sssŠD","ŠssŠD","DssŠD","sŠsŠD","ŠŠsŠD","DŠsŠD","sŠsŠD","sDsŠD","ŠDsŠD","DDsŠD","sDsŠD","ŠDsŠD","sŠDsŠD","sŠDsŠs","sŠDsDs","sŠDŠDs","sŠsŠDs","sDsŠDs","ŠDsŠDs","sŠDsŠŠ","sŠDsDŠ","sŠDŠDŠ","sŠsŠDŠ","sDsŠDŠ","ŠDsŠDŠ","sŠDssŠ","sŠDŠsŠ","sŠsŠsŠ","sDsŠsŠ","ŠDsŠsŠ","sŠDDsŠ","sŠsDsŠ","sDsDsŠ","ŠDsDsŠ","sŠŠDsŠ","sDŠDsŠ","ŠDŠDsŠ","ssŠDsŠ","ŠsŠDsŠ","DsŠDsŠ","sŠDsŠD","sŠDsDD","sŠDŠDD","sŠsŠDD","sDsŠDD","ŠDsŠDD","sŠDssD","sŠDŠsD","sŠsŠsD","sDsŠsD","ŠDsŠsD","sŠDDsD","sŠsDsD","sDsDsD","ŠDsDsD","sŠŠDsD","sDŠDsD","ŠDŠDsD","ssŠDsD","ŠsŠDsD","DsŠDsD","sŠDsŠD","sŠDŠŠD","sŠsŠŠD","sDsŠŠD","ŠDsŠŠD","sŠDDŠD","sŠsDŠD","sDsDŠD","ŠDsDŠD","sŠŠDŠD","sDŠDŠD","ŠDŠDŠD","ssŠDŠD","ŠsŠDŠD","DsŠDŠD","sŠDsŠD","sŠssŠD","sDssŠD","ŠDssŠD","sŠŠsŠD","sDŠsŠD","ŠDŠsŠD","ssŠsŠD","ŠsŠsŠD","DsŠsŠD","sŠDsŠD","sDDsŠD","ŠDDsŠD","ssDsŠD","ŠsDsŠD","DsDsŠD","sŠDsŠD","ŠŠDsŠD","DŠDsŠD","sŠDsŠD","sŠDsŠDs","sŠDsŠDŠ","sŠDsŠsŠ","sŠDsDsŠ","sŠDŠDsŠ","sŠsŠDsŠ","sDsŠDsŠ","ŠDsŠDsŠ","sŠDsŠDD","sŠDsŠsD","sŠDsDsD","sŠDŠDsD","sŠsŠDsD","sDsŠDsD","ŠDsŠDsD","sŠDsŠŠD","sŠDsDŠD","sŠDŠDŠD","sŠsŠDŠD","sDsŠDŠD","ŠDsŠDŠD","sŠDssŠD","sŠDŠsŠD","sŠsŠsŠD","sDsŠsŠD","ŠDsŠsŠD","sŠDDsŠD","sŠsDsŠD","sDsDsŠD","ŠDsDsŠD","sŠŠDsŠD","sDŠDsŠD","ŠDŠDsŠD","ssŠDsŠD","ŠsŠDsŠD","DsŠDsŠD","sŠDsŠDsŠ","sŠDsŠDsD","sŠDsŠDŠD","sŠDsŠsŠD","sŠDsDsŠD","sŠDŠDsŠD","sŠsŠDsŠD","sDsŠDsŠD","ŠDsŠDsŠD","sŠDsŠDsŠD"]
.Δ          # Then find the first string which is truthy for:
  ₁         #  Push the builtin 256
   `        #  Pop and push them separated to the stack
    r       #  Reverse the stack, so the order is [6,5,2,string]
     .V     #  Execute the string as 05AB1E code
       )    #  Wrap all values on the stack into a list
        Q   #  And check that it's equal to the (implicit) input-list
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Ruby, 126 bytes

->s{*w='',321;(a,b,*w=w;w<<a+?d<<b*10+(k=b%10)<<a+?s<<b+k*10-(z=b%100)+z/10<<a+?t<<b+k*100-(x=b%1000)+x/10)until w[1]==s;w[0]}

Try it online!

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.