Dites-moi comment flop

29

En tant qu'informaticiens, vous connaissez probablement tous les opérations de liste de base de pop and push . Ce sont des opérations simples qui modifient une liste d'éléments. Cependant, avez-vous déjà entendu parler de l'opération flop ? (comme dans bistable flop , )? C'est assez simple. Étant donné un nombre n , inversez les n premiers éléments de la liste. Voici un exemple:

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

La chose intéressante à propos de l'opération de flop, c'est que vous pouvez l'utiliser pour faire des choses intéressantes sur une liste, comme le trier . Nous allons faire quelque chose de similaire avec les flops:

Étant donné une liste d'entiers, "Neighbour it". En d'autres termes, triez-le de sorte que chaque élément en double apparaisse consécutivement.

Cela peut être fait avec des flops! Par exemple, prenez la liste suivante:

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

Cela nous amène à la définition du défi d'aujourd'hui:

Étant donné une liste d'entiers, affichez tout ensemble de flops qui entraînera le voisinage de la liste.

En utilisant la dernière liste comme exemple, vous devez sortir:

4
3
6

car flasher la liste par 4, puis par 3, puis par 6 se traduira par une liste voisine. Gardez à l'esprit que vous n'avez pas besoin d'imprimer la liste de flops la plus courte possible qui voisine une liste. Si vous aviez imprimé:

4
4
4
3
1
1
6
2
2

au lieu de cela, ce serait toujours une sortie valide. Cependant, vous ne pouvez jamais afficher un nombre supérieur à la longueur de la liste. En effet, pour une liste a = [1, 2, 3], appeler a.flop(4)n'a pas de sens.

Voici quelques exemples:

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

Gardez à l'esprit que dans chacun de ces exemples, la sortie donnée n'est qu'une sortie potentiellement valide. Comme je l'ai déjà dit, tout ensemble de flops qui voisine la liste donnée est une sortie valide . Vous pouvez utiliser ce script python pour vérifier si une liste donnée de flops voisine correctement une liste.

Vous pouvez prendre des entrées et des sorties dans n'importe quel format raisonnable. Par exemple, les arguments de fonction / valeur de retour, STDIN / STDOUT, la lecture / écriture d'un fichier, etc. sont tous valides. Comme d'habitude, c'est , alors faites le programme le plus court possible et amusez-vous! :)

DJMcMayhem
la source
3
Je l'ai entendu comme fl (point flottant) op (eration).
Weijun Zhou
3
@WeijunZhou C'est une mesure de la vitesse de calcul, pour compter les opérations effectuées sur un morceau de matériel. en.wikipedia.org/wiki/FLOPS
iPhoenix
3
Les soumissions doivent-elles être déterministes ou puis-je effectuer un flop pseudo-aléatoire jusqu'à ce que le tableau soit groupé?
Dennis
3
Les flops zéro sont-ils autorisés à apparaître dans la sortie?
Laikoni
4
Connexes . NB: toute réponse à cette question serait une réponse à celle-ci, mais étant donné que le tri est une condition plus forte que le fait d'être "voisin", il peut être possible de les jouer à l'extérieur, ce qui pourrait ne pas être un doublon (bien que le seul réponse jusqu'à présent n'est pas encourageante).
Peter Taylor

Réponses:

7

Haskell , 98 71 octets

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

Essayez-le en ligne!

Explication

Pour une liste de longueur, ncette méthode produit des 2*nflops. Il fonctionne en regardant le dernier élément de la liste, en recherchant le même élément dans la liste avant et en le retournant de l'avant-dernière position. Ensuite, la liste avec le dernier élément supprimé est récursivement "voisine".

Pour la liste, [1,2,3,1,2]l'algorithme fonctionne comme ceci:

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

Tous ensemble, cela donne les flops [2,4,0,3,1,2,0,1,0,0]et la liste des voisins [3,1,1,2,2].

Laikoni
la source
6

Wolfram Language (Mathematica) , 71 octets

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

Essayez-le en ligne!

Comment ça marche

Étant donné un tableau de longueur n, génère une séquence de 4nflops qui trient le tableau dans un ordre croissant: en particulier, en plaçant les éléments en double les uns à côté des autres.

L'idée est que pour trier un tableau, nous déplaçons son plus grand élément à la fin, puis trions les premiers n-1éléments du tableau. Pour éviter de mettre en œuvre l'opération de flop, nous déplaçons le plus gros élément à la fin d'une manière qui ne perturbe pas les autres éléments:

{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

En général, si le plus grand élément est en position i, la séquence de flops qui le déplace jusqu'à la fin l'est i, n, n-1, i-1.

Misha Lavrov
la source
Vous pouvez déplacer le plus grand élément vers la fin avec juste i, n. Pourquoi alors n-1, i-1? Il n'y a pas besoin d'un tri stable .
Peter Taylor
@PeterTaylor Je ne pense pas que la réponse effectue réellement des flops, elle supprime plutôt le plus gros élément à chaque fois et génère l'équivalent de cette opération en termes de flops.
Neil
3

Gelée , 19 17 octets

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

Trie la liste.

Essayez-le en ligne!

Dennis
la source
Je pense que le tri ỤŒ¿’Æ!‘ṚĖµUż’ṚFinversé Œ¿est modulo L!.
Jonathan Allan
Pour une raison quelconque, cela ne fonctionne pas pour le dernier cas de test, ce qui signifie probablement que mon code échouera également pour certains cas de bord obscurs ...
Dennis
Et il échoue en effet pour l'entrée [4, 3, 2, 1, 3]. Bummer.
Dennis
Oh, boo; c'est une honte.
Jonathan Allan
Ụ>Ṫ$ƤSạỤĖµUż’ṚFéconomiser 2 octets en remplaçant le lien d'assistance.
miles
2

Nettoyer , 88 octets

Je pense qu'il y en a peut-être un plus court avec des gardes, mais je ne l'ai pas encore trouvé.

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

$o r

Essayez-le en ligne!

En tant que fonction littérale. Fonctionne de la même manière que la réponse Haskell de Laikoni , mais a joué un peu différemment, et bien sûr aussi dans une langue différente.

Οurous
la source
1

JavaScript, 150 octets

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

Essayez-le en ligne!

JavaScript, 151 octets

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}

Essayez-le en ligne!

Les deux trient essentiellement le tableau en retournant le nombre maximum au début, puis en le retournant à l'arrière, en répétant cela avec le tableau restant. Le premier utilise réduire, le second utilise une boucle for.

Non golfé:

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;
}
mdatsev
la source
0

Perl 5.10 (ou supérieur), 66 octets

Comprend +3pour -n l' use 5.10.0apporter la langue au niveau perl 5.10 est considéré comme gratuit

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

Exécutez avec l'entrée en une seule ligne sur STDIN:

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

Trie la liste en trouvant à plusieurs reprises toute inversion, en la renversant vers l'avant, puis en renversant l'inversion et en replaçant le tout dans son ancienne position.

C'était étonnamment difficile de se retrouver dans le même stade que le python sur celui-ci :-)

Ton Hospel
la source
0

C (gcc) , 165160 octets

  • Merci à plafondcat pour avoir économisé cinq octets.
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;}
Jonathan Frech
la source
@ceilingcat Merci.
Jonathan Frech