The steps of sorting a stack of disks on three pegs

Question

You have a Tower of Hanoi-esque set of 3 pegs. There is a stack of unsorted disks labelled from 1 to n (inclusive) on one of these pegs. The other two pegs are empty.

The only move allowed is to move the top k disks from a peg A to another peg B, without changing the order of the moved disks. (Think taking a stack of CDs from the top of a disk spindle and putting the whole stack, unchanged, on a different spindle.) You may not take disks from the middle of the stack, without moving all disks on top of it to another peg first.

Given an unsorted list of numbers, representing the order of the disks on the starting peg, write the shortest program, function, or code snippet that outputs in any format the steps needed to sort the disks from least to greatest, using only the move described above.

The outputted steps must include the number of disks moved, the source peg, and the destination peg. Only output moves that move at least 1 disk. The outputted solution need not be the shortest. The sorted disks must end on the starting peg. You may use any arbitrary, three-valued label for the pegs.

The input will always be unsorted, and with n >= 2.

Examples

For these examples, the output step format is [src][#disks][dest]. The pegs are labelled a, b, c. The input is ordered from top to bottom (first element is the top disk).

Note that the example outputs are only one possible sequence of moves to sort the disk.

// input -> steps
2 1 -> a1b a1b b2a
3 1 2 -> a1b a2b b3a
1 4 3 2 -> a1b a1c a1c a1c b1c c4a
1 2 5 3 4 -> a2b a1c b2a a4c c5a
2 1 3 4 5 -> a1b a1b b2a
1 2 9 3 6 7 8 4 5 10 -> a2b a1c b2a a3b a3c a2c c6a c3a

Miscellaneous Comments

• Using the move described, I think it's possible that you only need 2 pegs. I don't know how to prove this, however. (e.g. to swap two adjacent elements 1 and 2 on a stack with arbitrary elements above p and below s such that the contents are p12s, move p1 -> p -> p2 -> p21. This leads to a final stack p21s.)
• I do not know if this sort of sort has a name.

^{The ideas from this challenge may be applicable to Solve an Inglenook Sidings Puzzle.}

• Wheat Wizard: Aren't the tower of hanoi moves a subset of these moves? (Only move one at a time, must stack smaller on greater) That should be enough to prove it.
• Arnauld: According to the test cases, it seems like we have to end up on the starting peg. But I haven't seen this requirement in the description.
• Arnauld: Are moves of 0 disc allowed in the output?
• bigyihsuan: @Arnauld no, all outputted moves should move at least 1 disk. As for the starting peg, I will add that to the description.
• Darrel Hoffman: It's similar to "Pancake Sort", only you don't flip the stack when you move it. Runtime is probably similar though.

Answer 1

JavaScript (ES6), 97 bytes

A silly algorithm using only two pegs. The I/O format is the one used in the challenge.

f=(a,n=N=a.length)=>n?`a${(i=a.indexOf(n))+1}b ${i?`b${i}a `:""}`+f(a,n-1,a.splice(i,1)):`b${N}a`

Try it online!

Or 88 bytes with an alternate output format (N> to move N discs from a to b, N< to move N discs from b to a).

Algorithm

1. Take all discs in A up to the disc with the highest label included and move them to B.

   step 1

2. Take all discs in B up to the disc with the highest label excluded and move them back to A. Or ignore this step if there's nothing to move.

   step 2

Repeat steps 1 and 2 \$N\$ times even if the discs are already sorted. We end up with a sorted pile on B. Finally, move everything from B to A.

• Mukundan314: -7 bytes by constructing the reverse and finally reversing
• Arnauld: @Mukundan314 Thanks. I think it's different enough to be posted as your own separate answer. (You can use a+a instead of a+''.)

Answer 2

Jelly, 23 bytes

NỤ>";\§ạƲż’$ṭLFJḂƝżƊṛ/Ƈ

A monadic Link that accepts the disks as an unordered list of a prefix of the natural numbers and yields a list of instructions. Each instruction is:

[[ToPeg, FromPeg], DiskCount]

where the initially full peg is 0 while 1 and 2 are the others (although we only use 0 and 1 anyway :p)

Try it online!

How?

The resulting algorithm

Pick up all the disks from the "Source Peg" and put them on another peg, the "Buffer Peg", then repeatedly (a) pick up as many disks as needed from the Buffer Peg to reach the largest disk and place them onto the Source Peg, and then, if possible, (b) pick up one less disk than in (a) from the Source Peg and place them on the Buffer Peg.

Code

NỤ>";\§ạƲż’$ṭLFJḂƝżƊṛ/Ƈ - Link: unordered list of [1..N], Disks
N - negate {Disks}
 Ụ - grade {that} up
 -> Places = Disk indices sorted by Disk value, descending
 Ʋ - last four links as a monad - f(Places):
 ;\ - prefixes of {Places}
 " - zip with:
 > - {Place} greater than {Prefix} (vectorises)
 § - sums -> Counts
 [count of values both earlier in Places and less than V
 for V in Places] 
 ạ - {that} absolute difference {Places}
 -> counts of disks to pick up from the Buffer Peg at
 each iteration.
 $ - last two links as a monad - f(X=that):
 ’ - decrement -> counts of disks to return to the Buffer Peg
 ż - {X} zip with {that} -> PairsOfCounts
 L - length {Disks} (the initial move count)
 ṭ - {PairsOfCounts} tack {that}
 F - flatten -> AllCounts (plus a trailing zero)
 Ɗ - last three links as a monad - f(AllCounts):
 J - indices {AllCounts} -> [1..AllCounts]
 Ɲ - for neighbouring pairs:
 Ḃ - mod two
 -> [[1,0],[0,1],[1,0],[0,1],...]
 ż - {that} zip with {AllCounts}
 Ƈ - keep those for which:
 / - reduce by:
 ṛ - get right argument
 (i.e. remove instructions where zero disks would be moved)

Answer 3

Charcoal, (削除) 48 (削除ここまで) 45 bytes

W⌈Φθ›κ⊕λ«≔⊕⌕θιηUMθ⎇‹λι§θ%+ληικ⟦+abι+baη+ba−ιη

Try it online! Link is to verbose version of code. Outputs in the format [src][dest][#discs]. Explanation:

W⌈Φθ›κ⊕λ«

While at least one disc is out of place, get the highest valued such disc. Call this i.

≔⊕⌕θιη

Get is current index (1-indexed). Call this h.

UMθ⎇‹λι§θ%+ληικ

Rearrange the discs in memory according to the following three movements, ready for the next iteration of the loop.

⟦+abι+baη+ba−ιη

Move i discs from a to b, then h discs from b to a, then the remaining discs from b to a.

Answer 4

Python, ^{(削除) 89 (削除ここまで)} 86 bytes

f=lambda a:a and[f"a{(i:=a.index(min(a)))+1}b"]+(i>0*a.pop(i))*[f"b{i}a"]+f(a)+["b1a"]

Attempt This Online!

Uses an algorithm similar to the one @Arnauld uses, but instead constructs the reverse sorted order on the second peg and then moves elements one at a time from the second peg back to the first peg. Since the sequence was reversed on the second peg, moving elements one at a time back to the first peg will result in the sorted sequence.

JavaScript (Node.js), ^{(削除) 89 (削除ここまで)} 88 bytes

-2 byte thanks to @Arnauld

f=(a,n=1)=>a+a&&`a${(i=a.indexOf(n))+1}b ${i?`b${i}a `:""}${f(a,n+1,a.splice(i,1))}b1a `

Try it online!

Answer 5

Japt -x, 38 bytes

Yeesh! This is pretty hideous. And, in golfing it down, it evolved into an almost port of Mukundan's JS solution.

¬©" ab{T=Ub°V)Ä+TÎç" ba"+TUjT)+ß} ba1

Try it

¬©" ab{T=Ub°V)Ä+TÎç" ba"+TUjT)+ß} ba1 :Implicit input of array U
¬ :Join
 © :Logical AND with
 " ab : Begin string literal
 { : Interpolate
 T= : Assign to variable T
 Ub : First 0-based index in U of
 ° : Prefix increment
 V : Second input variable (which defaults to 0)
 ) : End assignment
 Ä : Add 1
 + : Concatenate
 TÎ : Sign of T
 ç" ba"+T : Repeat " ba"+T that many times
 UjT : Remove & return the Tth element from U, mutating it (this gets passed as a second argument to ç, which only expects 1 argument)
 ) : End repeat
 +ß : Concatenate a recursive call with implicit arguments U & V
 } : End interpolation
 ba1 : End string literal
 :Implicitly trim and output

Answer 6

Ruby, (削除) 74... (削除ここまで) 65 bytes

f=->*l,m{l[-m]?"a#{k=l.max}b b#{k-1}a b1a "+f[m,*l]:m<2?"":f[*l]}

Try it online!

What

If the bottom disc is not the largest, move the whole stack to b, then all except one back, and the remaining one on top. This will "rotate" the stack, iterate until the largest disc is on the bottom.

If the largest disc is on the bottom, leave it alone and repeat the procedure for the remaining ones.

How

f=->*l,m{ # m is the bottom of the stack
 l[-m]? # if l has at least m elements 
 # (m is not the largest disc)
 "a#{k=l.max}b b#{k-1}a b1a " # Move all, then put them back with the bottom disc on top
 +f[m,*l] # rotate the input list and repeat
 :m<2?"" # m is the largest disc, if this is the last one stop
 :f[*l]} # otherwise repeat for the rest of the stack

Answer 7

JavaScript (Node.js), 74 bytes

f=a=>(n=a.length)^(p=a.pop())?`a${n}b b${n-1}a b1a `+f([p,...a]):a+a&&f(a)

Try it online!

-1B Shaggy

while (remain) {
 while (bottom != length) {
 move bottom to top
 }
 ignore bottom
}

Answer 8

Jelly, 22 bytes

ṪṭjI$ż"€€ß‘ȦƇ;ñ
ṙMç€MẎ

Try it online!

Outputs in the format [#disks, fromto] (e.g. [5, 12]). The two pegs we use are numbered 1 (starting peg) and 2.

I worked out the algorithm used here by myself, but I think it's a variation on @Neil's. The basic idea is to go through the disks in order from largest to smallest: the disk we're checking is moved from peg 1 to peg 2 (along with everything above it), then all remaining disks smaller than the one we're checking are moved from peg 1 to peg 2, then all disks are moved from peg 2 to peg 1. This ensures that the disk we're checking, and all larger disks, end up in order at the bottom of peg 1, thus once all the disks have been checked, all disks are in order on peg 1.

The I/O format in this question is somewhat verbose to comply with and makes up a significant proportion of the answer – 9 of the 22 bytes are spent meeting I/O format restrictions. (Because this problem can be solved using only two pegs, a more natural format would be along the lines of "number of disks to move from peg 1 to peg 2, then number of disks to move from peg 2 to peg 1", allowing zero-sized moves.)

Explanation

Main link

The main link takes one argument, the stack of disks on peg 1.

 ṙMç€MẎ
 M For each maximal element in the list,
 ṙ produce a list by rotating that element to the start;
 € and for each {resulting rotated list}
 ç call the helper link 1l·, with arguments {that rotated list}
 M and a list of the locations of the maximal elements
 Ẏ then concatenate the resulting outputs.

The main link determines a) what order the disks on peg 1 will be in after a series of three moves, and b) when to stop recursing. (Stopping the recursion is done by iterating over a list of lists produced from all maximal elements of the original list; there will be either 0 or 1 such element, thus either we do a 1-iteration loop in order to recurse, or a 0-iteration loop in order to stop recursing.)

Helper link 1l·

The helper link takes two arguments: the order the disks on peg 1 will be in after a sequence of three moves, and the number of disks that were moved by the first of those moves. (The second argument is taken as a 1-element list, because that's the format that the main link provides it in.)

The helper link is given only the relevant subset of the disks on peg 1 (i.e. not including disks that were already moved into place earlier). This means that the last element of the first argument is the disk that is being moved into place.

 ṪṭjI$ż"€€ß‘ȦƇ;ñ
 ṭ Concatenate {the second argument}
 Ṫ and the last element of {the first argument};
 j between those two elements, place
 I the forward differences of
 $ the concatenated list (i.e. arg2 - last of arg1);
 ż zip with
 "€€ß‘ [12, 12, 21];
 Ƈ {in the resulting list,} keep only elements that
 Ȧ contain no zeroes (including recursively)
 ; and to {the result of that}, append
 ñ {the result of} a call to the main link (see below)
 Ṫ in which the last element of {arg1} is deleted

The helper link basically just calculates the sizes of the moves (first the substack consisting of the disk that's being moved into place and the disks above it, then the rest of the portion of the stack we're looking at, and then the whole thing moved back the other way). The calculations are very easy but done in a bit of a weird order to reduce the need to spend bytes on plumbing (first we take the number of disks in the first move and the total nubmer of disks, then place the difference in between). The three moves are always in the same directions (1 to 2, 1 to 2, and 2 to 1), so that can be hardcoded; but we have to remove zero-sized moves (however, there's no requirement to remove redundant moves, so if the last disk we're looking at is already in place, the stack above it gets moved from 1 to 2 then 2 to 1 for consistency).

After the last disk is moved into place, the helper link recursively calls the main link to move all the previous disks, using ñ. As far as I can tell, this is somehow exploiting a bug in Jelly, because ñ is being used in a way that doesn't match its documentation – it is supposed to reparse the link being called as though it takes two arguments, but the main link doesn't parse correctly if you actually give it two arguments. Although I'm not sure, I think that what's happening is that the previous 1-argument call to the main link somehow ended up getting cached in a way that isn't invalidated properly. The correct way to call the main link would be to use Ñ, which specifies the correct (1-argument) parser to use; however, that would give it the wrong implicit argument, so I'd have to waste a byte to disambiguate as Ñ{ (specifying to use the left argument of the current link). In this case, ñ provides the main link with two arguments (the left and right arguments of the current link), but it's only a 1-argument link; fortunately, it happens to read from the correct argument, so everything works. In any case, the code appears to work, even though I don't fully understand why.

• Neil: Yes, you're also splitting the pile and swapping the top (two) parts. I could probably output the parts in your order by changing my code to ⟦+abη+ab−ιη+baι.