Jako informatycy prawdopodobnie wszyscy znacie podstawowe operacje na listach pop i push . Są to proste operacje, które modyfikują listę elementów. Czy słyszałeś jednak o flopie operacji ? (jak w flip- flopie )? To całkiem proste. Biorąc pod uwagę liczbę n , odwróć pierwsze n elementów listy. Oto przykład:

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

Fajną rzeczą w operacji flop jest to, że możesz jej używać do robienia fajnych rzeczy na liście, takich jak sortowanie . Z flopami zrobimy coś podobnego:

Biorąc pod uwagę listę liczb całkowitych, „Neighbor it”. Innymi słowy, posortuj go tak, aby każdy zduplikowany element pojawiał się kolejno.

Można to zrobić za pomocą klap! Na przykład weź następującą 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]

To prowadzi nas do zdefiniowania dzisiejszego wyzwania:

Biorąc pod uwagę listę liczb całkowitych, wypisz dowolny zestaw klap, które spowodują, że lista będzie sąsiadować.

Korzystając z ostatniej listy jako przykładu, powinieneś wypisać:

4
3
6

ponieważ wyrzucenie listy o 4, następnie o 3, a następnie o 6 spowoduje wyświetlenie listy sąsiadów. Pamiętaj, że nie musisz drukować najkrótszej możliwej listy klap sąsiadujących z listą. Jeśli wydrukowałeś:

4
4
4
3
1
1
6
2
2

zamiast tego nadal byłby to prawidłowy wynik. Jednak nigdy nie można wypisać liczby większej niż długość listy. Wynika to z faktu, że w przypadku listy a = [1, 2, 3]dzwonienie a.flop(4)jest bezsensowne.

Oto kilka przykładów:

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

Należy pamiętać, że w każdym z tych przykładów podany wynik to tylko jeden potencjalny prawidłowy wynik. Jak powiedziałem wcześniej, każdy zestaw flopów, który sąsiaduje z podaną listą, jest prawidłowym wyjściem . Możesz użyć tego skryptu Pythona, aby sprawdzić, czy dana lista klap poprawnie sąsiaduje z listą.

Możesz pobierać dane wejściowe i wyjściowe w dowolnym rozsądnym formacie. Na przykład poprawne są argumenty funkcji / wartość zwracana, STDIN / STDOUT, odczyt / zapis pliku itp. Jak zwykle jest to gra w golfa , więc stwórz możliwie najkrótszy program i baw się dobrze! :)

Haskell , 98 71 bajtów

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

Wypróbuj online!

Wyjaśnienie

Dla listy długości nta metoda daje 2*nklapy. Działa, patrząc na ostatni element listy, szukając tego samego elementu na liście przed i odwracając go do drugiej do ostatniej pozycji. Następnie lista z usuniętym ostatnim elementem jest rekurencyjnie „sąsiadowana”.

Dla listy [1,2,3,1,2]algorytm działa w następujący sposób:

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

Wszystko razem daje klapy [2,4,0,3,1,2,0,1,0,0]i listę sąsiadów [3,1,1,2,2].

Wolfram Language (Mathematica) , 71 bajtów

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

Wypróbuj online!

Jak to działa

Biorąc pod uwagę tablicę długości n, generuje sekwencję 4nklap, które sortują tablicę w kolejności rosnącej: w szczególności umieszczanie duplikatów elementów obok siebie.

Chodzi o to, że aby posortować tablicę, przesuwamy jej największy element na koniec, a następnie sortujemy pierwsze n-1elementy tablicy. Aby uniknąć implementacji operacji flop, przesuwamy największy element na koniec w sposób, który nie zakłóca pozostałych elementów:

{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

Ogólnie rzecz biorąc, jeśli największy element jest na swoim miejscu i, sekwencja klap, która przesuwa go do końca, to i, n, n-1, i-1.

Python 2 , 69 bajtów

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

Wypróbuj online!

Galaretka , 19 17 bajtów

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

Sortuje listę.

Wypróbuj online!

Czysty , 88 bajtów

Myślę, że jest prawdopodobnie krótszy ze strażnikami, ale jeszcze go nie znalazłem.

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

$o r

Wypróbuj online!

Jako funkcja dosłowna. Działa tak samo jak odpowiedź Haskell Laikoni , ale grał nieco inaczej w golfa i oczywiście w innym języku.

JavaScript, 150 bajtów

(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++)],[])

Wypróbuj online!

JavaScript, 151 bajtów

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}

Wypróbuj online!

Oba zasadniczo sortują tablicę, przewracając maksymalną liczbę na początek, a następnie przewracając ją do tyłu, powtarzając to z pozostałą tablicą. Pierwszy wykorzystuje redukcję, drugi używa pętli for.

Nie golfowany:

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;
}

Perl 5.10 (lub wyższy), 66 bajtów

Obejmuje +3dla -n The, use 5.10.0aby doprowadzić język do poziomu perl 5.10 jest uważany za darmowy

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

Uruchom z wejściem jako jedną linię na STDIN:

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

Sortuje listę, wielokrotnie znajdując inwersję, przewracając ją do przodu, a następnie przewracając i odwracając wszystko z powrotem do swojej starej pozycji.

Zaskakująco trudno było znaleźć się w tym samym parku, co Python :-)

C (gcc) , 165 160 bajtów

• Dzięki pułapowi cat za oszczędność pięciu bajtów.

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;}

• Wypróbuj online!
• Weryfikacja