Put the colours back in order

Question

Background

I wrote up a web-based sketchpad that lets the user pick from a series of colours, and tracks the recently selected colours for ease of use. I randomly had this idea as a personal puzzle, but couldn't figure it out, so I thought I'd post it here.

The recent colour list follows 2 rules for when a colour is selected:

• If the colour already exists in the list, it's moved up to the front of the list by swapping it with the tile that was previously at the front.

• If the colour wasn't already in the list, it's prepended to the front, without any swapping taking place.

In the screenshot below:

The order of the colours selected leading to the above "Recent Colours" were:

Blue, Pink, Yellow, White, Black, Purple, Red, Green

The Problem

What order (if any) can you select colours from the quick bar to have the "Recent Colours" bar be in the same order as the "Quick Colours" bar above?

Hint: It's not as simple as selecting the colours in the reverse order of the "Quick Bar".

Answer 1

Assuming that the starting position is the one shown in the screenshot, all of the colors are already in the bar, so the only possible move is to swap a color with the first one in the bar. To put a color in the right place, it must be the first one in the bar, and then the color that is occupying its place must be selected to swap it in. If we consider which colors in which places, we get that:

• White and Green are in each other's spots;
• Red and Black are in each other's spots;
• Purple is in Blue's spot, Blue is in Pink's spot, and Pink is in Purple's spot;
• Yellow is already in the right spot.

We can fix White and Green on the first move by selecting White. To fix Red and Black takes three moves: one to put Red in the first slot, one to swap it into the right slot (putting Black in the first slot), and one to put Black into the right slot (returning White to the first slot). Similarly, Purple, Blue, and Pink take four moves. In total it takes eight selections to get the colors right. One possible sequence (but not the only one) is:

White, Red, Black, White, Purple, Pink, Blue, White.

In general, it is possible to return the colors to the right order no matter what order they are originally in. An algorithm to do this might be:

• If the color in the first slot is not White, select whichever color is occupying the slot that it should go in.
• Otherwise, select any color that is not in the right place.

Every time the first step is done, one color that isn't White goes into the right place, while every time the second step is done, the result is a situation where the first step applies. Because no step ever causes a non-White color to be removed from its correct place, this guarantees that eventually all the colors will be in the right order.

Answer 2

Not as comprehensive as the first one, but still...

To push a color into the last place, bring it to the front (by selecting it), then select the last one on the current list. Since the last place will never come into play again, we can select the color that's supposed to be at the 2nd-to-last place and the color coming 2nd-to-last then rinse and repeat. When only the first and 2nd colors are left untouched, we can either let it be or just select the 2nd on the current list. Starting from the position in the recent colors section in the image, it can be done by selecting the colors in this order:

Pink, Blue, Purple, Green, White, Red, Black, White.