Dime como fracasar

29

Como informáticos, probablemente estén familiarizados con las operaciones básicas de listas de pop y push . Estas son operaciones simples que modifican una lista de elementos. Sin embargo, ¿alguna vez has oído hablar del fracaso de la operación ? (como en flip- flop )? Es muy simple Dado un número n , invierta los primeros n elementos de la lista. Aquí hay un ejemplo:

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

Lo bueno de la operación de flop es que puedes usarla para hacer algunas cosas interesantes en una lista, como ordenarla . Vamos a hacer algo similar con los flops:

Dada una lista de enteros, "Vecino". En otras palabras, ordénelo para que cada elemento duplicado aparezca consecutivamente.

¡Esto se puede hacer con flops! Por ejemplo, tome la siguiente lista:

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

Esto nos lleva a la definición del desafío de hoy:

Dada una lista de enteros, genere cualquier conjunto de flops que resulte en la lista de vecinos.

Usando la última lista como ejemplo, debe generar:

4
3
6

porque si la lista se despliega en 4, luego en 3 y luego en 6, se obtendrá una lista de vecinos. Tenga en cuenta que no necesita imprimir la lista de flops más corta posible que esté junto a una lista. Si hubiera impreso:

4
4
4
3
1
1
6
2
2

en cambio, esto todavía sería una salida válida. Sin embargo, es posible que no siempre el número de una salida mayor que la longitud de la lista. Esto se debe a que para una lista a = [1, 2, 3], llamar no a.flop(4)tiene sentido.

Aquí hay unos ejemplos:

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

Tenga en cuenta que en cada uno de estos ejemplos, la salida dada es solo una salida válida potencial. Como dije antes, cualquier conjunto de flops que sea vecino de la lista dada es una salida válida . Puede usar esta secuencia de comandos de Python para verificar si una lista dada de flops se encuentra correctamente junto a una lista.

Puede tomar entrada y salida en cualquier formato razonable. Por ejemplo, los argumentos de función / valor de retorno, STDIN / STDOUT, leer / escribir un archivo, etc. son todos válidos. Como de costumbre, este es el , ¡así que haz el programa más corto que puedas y diviértete! :)

DJMcMayhem
fuente
3
Lo escuché como fl (punto de flotación) op (eration).
Weijun Zhou
3
@WeijunZhou Esa es una medida de la velocidad de cómputo, para contar las operaciones realizadas por una pieza de hardware. en.wikipedia.org/wiki/FLOPS
iPhoenix
3
¿Las presentaciones tienen que ser deterministas o puedo hacer un flop seudoaleatorio hasta que se agrupe la matriz?
Dennis
3
¿Se permite que aparezcan cero flops en la salida?
Laikoni
44
Relacionados . NB, cualquier respuesta a esa pregunta sería una respuesta a esta, pero dado que ser ordenado es una condición más fuerte que estar "cercado", es posible superarlos en el golf, por lo que esto podría no ser un duplicado (aunque el hecho de que responder hasta ahora no es alentador).
Peter Taylor

Respuestas:

7

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

Pruébalo en línea!

Explicación

Para una lista de longitud neste método produce2*n flops. Funciona mirando el último elemento de la lista, buscando el mismo elemento en la lista anterior y volteándolo a la penúltima posición. Luego, la lista con el último elemento eliminado es recursivamente "vecina".

Para la lista, [1,2,3,1,2]el algoritmo funciona así:

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

En conjunto, esto produce los fracasos [2,4,0,3,1,2,0,1,0,0]y la lista vecina [3,1,1,2,2].

Laikoni
fuente
6

Wolfram Language (Mathematica) , 71 bytes

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

Pruébalo en línea!

Cómo funciona

Dada una matriz de longitud n, genera una secuencia de 4nflops que ordena la matriz en orden creciente: en particular, colocando elementos duplicados uno al lado del otro.

La idea es que para ordenar una matriz, movemos su elemento más grande hasta el final, y luego ordenamos los primeros n-1elementos de la matriz. Para evitar implementar la operación de flop, movemos el elemento más grande hasta el final de manera que no moleste a los otros elementos:

{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 general, si el elemento más grande está en posición i, la secuencia de flops que lo mueve hasta el final lo es i, n, n-1, i-1.

Misha Lavrov
fuente
Puede mover el elemento más grande hasta el final con solo i, n. ¿Por qué entonces hacer n-1, i-1? No hay necesidad de un tipo estable .
Peter Taylor
@PeterTaylor No creo que la respuesta realmente realice flops, sino que elimina el elemento más grande cada vez y genera el equivalente de esa operación en términos de flops.
Neil
3

Jalea , 19 17 bytes

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

Ordena la lista.

Pruébalo en línea!

Dennis
fuente
Creo que ỤŒ¿’Æ!‘ṚĖµUż’ṚFel tipo inverso ya que Œ¿es módulo L!.
Jonathan Allan el
Por alguna razón, eso no funciona para el último caso de prueba, lo que probablemente significa que mi código también fallará en algún caso de borde oscuro ...
Dennis
Y de hecho falla para la entrada [4, 3, 2, 1, 3]. Gorrón.
Dennis
Oh boo es una pena.
Jonathan Allan
Ụ>Ṫ$ƤSạỤĖµUż’ṚFahorrando 2 bytes reemplazando el enlace auxiliar.
millas
2

Limpio , 88 bytes

Creo que hay uno posiblemente más corto con guardias, pero aún no lo he encontrado.

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

$o r

Pruébalo en línea!

Como una función literal. Funciona de la misma manera que la respuesta de Hasikell de Laikoni , pero el golf es un poco diferente y, por supuesto, también en un idioma diferente.

Οurous
fuente
1

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

Pruébalo en línea!

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}

Pruébalo en línea!

Básicamente, ambos ordenan la matriz volteando el número máximo al principio y luego volteándolo hacia atrás, repitiendo esto con la matriz restante. El primero usa reduce, el segundo usa un bucle for.

Sin 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
fuente
0

Perl 5.10 (o superior), 66 bytes

Incluye +3para -n The use 5.10.0para llevar el idioma al nivel perl 5.10 se considera gratuito

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

Ejecute con la entrada como una línea en STDIN:

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

Ordena la lista encontrando repetidamente cualquier inversión, volviéndola al frente y luego volteando la inversión y volviendo a dejar todo en su posición anterior.

Fue sorprendentemente difícil entrar en el mismo estadio que Python en este :-)

Ton Hospel
fuente
0

C (gcc) , 165 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;}
Jonathan Frech
fuente
@ceilingcat Gracias.
Jonathan Frech