29
\$\begingroup\$

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 , so make the shortest program you can, and have fun! :)

\$\endgroup\$
  • 3
    \$\begingroup\$ I heard it as fl(oating point) op(eration). \$\endgroup\$ – Weijun Zhou Jan 31 '18 at 0:21
  • 3
    \$\begingroup\$ @WeijunZhou That's a measure of computational speed, for counting operations carried out py a piece of hardware. en.wikipedia.org/wiki/FLOPS \$\endgroup\$ – iPhoenix Jan 31 '18 at 0:24
  • 3
    \$\begingroup\$ Do submissions have to be deterministic or can I pseudo-randomly flop until the array is grouped? \$\endgroup\$ – Dennis Jan 31 '18 at 3:17
  • 3
    \$\begingroup\$ Are zero flops allowed to appear in the output? \$\endgroup\$ – Laikoni Jan 31 '18 at 7:49
  • 4
    \$\begingroup\$ Related. NB any answer to that question would be an answer to this one, but since being sorted is a stronger condition than being "neighboured" it may be possible to out-golf them so this might not be a duplicate (although the fact that the only answer so far sorts is not encouraging). \$\endgroup\$ – Peter Taylor Jan 31 '18 at 8:24
7
\$\begingroup\$

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].

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You can move the largest element to the end with just i, n. Why then do n-1, i-1? There's no need for a stable sort. \$\endgroup\$ – Peter Taylor Jan 31 '18 at 8:27
  • \$\begingroup\$ @PeterTaylor I don't think the answer actually performs flops, rather, it removes the largest element each time, and outputs the equivalent of that operation in terms of flops. \$\endgroup\$ – Neil Jan 31 '18 at 9:38
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

Jelly, 19 17 bytes

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

Sorts the list.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I think ỤŒ¿’Æ!‘ṚĖµUż’ṚF reverse sorts since Œ¿ is modulo L!. \$\endgroup\$ – Jonathan Allan Jan 31 '18 at 20:16
  • \$\begingroup\$ For whatever reason, that doesn't work for the last test case, which probably means that my code will fail for some obscure edge case as well... \$\endgroup\$ – Dennis Jan 31 '18 at 20:30
  • \$\begingroup\$ And it does indeed fail for input [4, 3, 2, 1, 3]. Bummer. \$\endgroup\$ – Dennis Jan 31 '18 at 20:38
  • \$\begingroup\$ Oh, boo; that's a shame. \$\endgroup\$ – Jonathan Allan Jan 31 '18 at 21:00
  • \$\begingroup\$ Ụ>Ṫ$ƤSạỤĖµUż’ṚF saving 2 bytes by replacing the helper link. \$\endgroup\$ – miles Feb 16 '18 at 15:59
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$
0
\$\begingroup\$

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 :-)

\$\endgroup\$
0
\$\begingroup\$

C (gcc), 165 160 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;}
\$\endgroup\$
  • \$\begingroup\$ @ceilingcat Thank you. \$\endgroup\$ – Jonathan Frech Aug 6 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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