Tell me how to flop

Question

As computer scientists, you're probably all familiar with the basic list operations of pop and push. These are simple operations that modify a list of elements. However, have you ever heard of the operation flop? (as in flip-flop)? It's pretty simple. Given a number n, reverse the first n elements of the list. Here's an example:

>>> a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> a.flop(4)
[4, 3, 2, 1, 5, 6, 7, 8, 9, 10]

The cool thing about the flop operation, is that you can use it do some cool things to a list, such as sorting it. We're going to do something similar with flops:

Given a list of integers, "Neighbor it". In other words, sort it so that every duplicate element appears consecutively.

This can be done with flops! For example, take the following list:

>>> a = [3, 2, 1, 4, 3, 3, 2]
>>> a.flop(4)
[4, 1, 2, 3, 3, 3, 2]
>>> a.flop(3)
[2, 1, 4, 3, 3, 3, 2]
>>> a.flop(6)
[3, 3, 3, 4, 1, 2, 2]

This leads us to the definition of today's challenge:

Given a list of integers, output any set of flops that will result in the list being neighbored.

Using the last list as an example, you should output:

4
3
6

because flopping the list by 4, then by 3, then by 6 will result in a neighbored list. Keep in mind that you do not need to print the shortest possible list of flops that neighbors a list. If you had printed:

4
4
4
3
1
1
6
2
2

instead, this would still be a valid output. However, you may not ever output a number larger than the length of the list. This is because for a list a = [1, 2, 3], calling a.flop(4) is nonsensical.

Here are some examples:

#Input:
[2, 6, 0, 3, 1, 5, 5, 0, 5, 1]

#Output
[3, 7, 8, 6, 9]


#Input
[1, 2]

#Output
<any list of integers under 3, including an empty list>


#Input
[2, 6, 0, 2, 1, 4, 5, 1, 3, 2, 1, 5, 6, 4, 4, 1, 4, 6, 6, 0]

#Output
[3, 19, 17, 7, 2, 4, 11, 15, 2, 7, 13, 4, 14, 2]


#Input
[1, 1, 1, 1, 2, 2, 2, -1, 4]

#Output
[]


#Input
[4, 4, 8, 8, 15, 16, 16, 23, 23, 42, 42, 15]

#Output
[12, 7]

Keep in mind that in each of these examples, the output given is just one potential valid output. As I said before, any set of flops that neighbors the given list is a valid output. You can use this python script to verify if a given list of flops correctly neighbors a list.

You may take input and output in any reasonable format. For example, function arguments/return value, STDIN/STDOUT, reading/writing a file etc. are all valid. As usual, this is code-golf, so make the shortest program you can, and have fun! :)

Answer 1

Haskell, 98 71 bytes

h.r
h(x:s)|(a,b)<-span(/=x)s=l b:l s:h(b++r a)
h e=e
r=reverse
l=length

Try it online!

Explanation

For a list of length n this method produces 2*n flops. It works by looking at the last element of the list, looking for the same element in the list before and flipping it to the second to last position. Then the list with the last element removed is recursively "neighboured".

For the list [1,2,3,1,2] the algorithm works like this:

[1,2,3,1,2]  flip longest prefix that ends in 2: flop 2
[2,1,3,1,2]  bring first element to second to last position: flop n-1 = flop 4
[1,3,1,2,2]  recursively work on n-1 list
[1,3,1,2]    there is no other 2: flop 0
[1,3,1,2]    flop n-1 = flop 3
[1,3,1,2]    recurse
[1,3,1]      flop 1
[1,3,1]      flop 2
[3,1,1]      recurse
[3,1]        flop 0
[3,1]        flop 1
 ...

All together this yields the flops [2,4,0,3,1,2,0,1,0,0] and the neighboured list [3,1,1,2,2].

Answer 2

Wolfram Language (Mathematica), 71 bytes

If[(n=Tr[1^#])<1,{},{i=Last@Ordering@#,n,n-1,i-1}~Join~#0[#~Drop~{i}]]&

Try it online!

How it works

Given an array of length n, outputs a sequence of 4n flops that sort the array in increasing order: in particular, putting duplicate elements next to each other.

The idea is that to sort an array, we move its largest element to the end, and then sort the first n-1 elements of the array. To avoid implementing the flop operation, we move the largest element to the end in a way which does not disturb the other elements:

{3, 2, 1, 5, 3, 3, 2}    starting array, with largest element in position 4
{5, 1, 2, 3, 3, 3, 2}    flop 4 to put the largest element at the beginning
{2, 3, 3, 3, 2, 1, 5}    flop 7 to put the largest element at the end
{1, 2, 3, 3, 3, 2, 5}    flop 6 (7-1) to reverse the effect of flop 7 on other elements
{3, 2, 1, 3, 3, 2, 5}    flop 3 (4-1) to reverse the effect of flop 4 on other elements

In general, if the largest element is in position i, the sequence of flops that moves it to the end is i, n, n-1, i-1.

Answer 3

Jelly, 19 17 bytes

ỤỤạ‘Ḣ
ỤÇÐƤĖµUż’ṚF

Sorts the list.

Try it online!

Answer 4

Python 2, 69 bytes

l=input()
while l:k=l.index(max(l));print-~k,len(l),;l=l[:k:-1]+l[:k]

Try it online!

Answer 5

Clean, 88 bytes

I think there's a possibly shorter one with guards, but I haven't found it yet.

import StdEnv
$[h:t]#(a,b)=span((<>)h)t
=map length[b,t]++ $(b++r a)
$e=e
r=reverse

$o r

Try it online!

As a function literal. Works the same way as Laikoni's Haskell answer, but golfed slightly differently, and of course also in a different language.

Answer 6

JavaScript, 150 bytes

(a,f=n=>(a=[...a.slice(0, n).reverse(),...a.slice(n)],n),l=a.length,i=0)=>a.reduce(c=>[...c,f(a.indexOf(Math.max(...a.slice(0, l-i)))+1),f(l-i++)],[])

Try it online!

JavaScript, 151 bytes

a=>{f=n=>(a=[...a.slice(0,n).reverse(),...a.slice(n)],n),r=[];for(i=a.length+1;--i>0;)r.push(f(a.indexOf(Math.max(...a.slice(0, i)))+1),f(i));return r}

Try it online!

Both basically sort the array by flipping the max number to the beginning and then flipping it to the back, repeating this with the remaining array. The first one uses reduce, the second one uses a for loop.

Ungolfed:

array => {
  let flop = n => {
    array = [...array.slice(0, n).reverse(), ...array.slice(n)]; 
    return n;
  }
  let flops = [];
  for (let i = array.length + 1; --i > 0;) 
  {
    let maxIndex = array.indexOf(Math.max(...array.slice(0, i)));
    flops.push(flop(maxIndex + 1), flop(i));
  }
  return flops;
}

Answer 7

C (gcc), 165 160 bytes

• Thanks to ceilingcat for saving five bytes.

m,j,t;f(A,l)int*A;{for(j=0;j+j<l;A[j]=A[l+~j],A[l+~j++]=t)t=A[j];}F(A,l)int*A;{for(;l;f(A,++m),printf("%d,%d,",m,l),f(A,l--))for(j=m=0;j<l;j++)m=A[j]>A[m]?j:m;}

• Try it online!
• Verification

Answer 8

Perl 5.10 (or higher), 66 bytes

Includes +3 for -n The use 5.10.0 to bring the language to level perl 5.10 is considered free

#!/usr/bin/perl -n
use 5.10.0;
$'>=$&or$.=s/(\S+) \G(\S+)/$2 $1/*say"$. 2 $."while$.++,/\S+ /g

Run with the input as one line on STDIN:

flop.pl <<< "1 8 3 -5 6"

Sorts the list by repeatedly finding any inversion, flopping it to the front then flopping the inversion and flopping everything back to its old position.

It was surprisingly hard to get in the same ballpark as python on this one :-)