Implemente el algoritmo de clasificación de Thanos

93

El algoritmo de clasificación es el siguiente:

Mientras la lista no esté ordenada, ajuste la mitad de todos los elementos (elimínelos de la lista). Continúe hasta que la lista esté ordenada o solo quede un elemento (que está ordenado de manera predeterminada). Este algoritmo de clasificación puede dar resultados diferentes según la implementación.

El procedimiento de eliminación de elementos depende de la implementación que decida, pero la lista debe ser la mitad del tiempo anterior a una pasada del procedimiento de eliminación de elementos. Su algoritmo puede decidir eliminar ya sea la primera mitad o la lista, la última mitad de la lista, todos los elementos impares, todos los elementos pares, uno a la vez hasta que la lista sea la mitad de la lista, o ninguno no mencionado.

La lista de entrada puede contener una cantidad arbitraria de elementos (dentro de lo razonable, digamos hasta 1000 elementos), no solo listas perfectamente divisibles de 2 ^ n elementos. Tendrá que eliminar (n + 1) / 2 o (n-1) / 2 elementos si la lista es impar, ya sea codificada o decidida aleatoriamente durante el tiempo de ejecución. Decide por ti mismo: ¿qué haría Thanos si el universo contuviera una cantidad extraña de seres vivos?

La lista se ordena si ningún elemento es más pequeño que cualquier elemento anterior. Se pueden producir duplicados en la entrada y en la salida.

Su programa debe tomar una matriz de enteros (a través de stdin o como parámetros, ya sea elementos individuales o un parámetro de matriz), y devolver la matriz ordenada (o imprimirla en stdout).

Ejemplos:

// A sorted list remains sorted
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]

// A list with duplicates may keep duplicates in the result
[1, 2, 3, 4, 3] -> [1, 3, 3] // Removing every second item
[1, 2, 3, 4, 3] -> [3, 4, 3] -> [4, 3] -> [3] // Removing the first half
[1, 2, 3, 4, 3] -> [1, 2] // Removing the last half

[1, 2, 4, 3, 5] podría dar resultados diferentes:

// Removing every second item:
[1, 2, 4, 3, 5] -> [1, 4, 5]

o:

// Removing the first half of the list
[1, 2, 4, 3, 5] -> [3, 5] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [4, 3, 5] -> [3, 5] // With (n-1)/2 items removed

o:

// Removing the last half of the list
[1, 2, 4, 3, 5] -> [1, 2] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [1, 2, 4] // With (n-1)/2 items removed

o:

// Taking random items away until half (in this case (n-1)/2) of the items remain
[1, 2, 4, 3, 5] -> [1, 4, 3] -> [4, 3] -> [4]
vrwim
fuente
Sería muy útil tener un caso de prueba que realmente requiera múltiples instantáneas para múltiples algoritmos de ajuste diferentes.
Cadena no relacionada
22
No necesitamos clasificar y eliminar la mitad de las respuestas ...
Sumner18
44
Caso de prueba sugerida: [9, 1, 1, 1, 1]. Mi propio algoritmo falló en esta entrada
Conor O'Brien

Respuestas:

19

R , 41 bytes

x=scan();while(any(x-sort(x)))x=x[!0:1];x

Pruébalo en línea!

Kirill L.
fuente
3
is.unsorteden lugar de any(...)también serían 41 bytes.
Giuseppe
Este método base tiene 44 bytes como una función recursiva, podría ser golfable: ¡ Pruébelo en línea!
CriminallyVulgar
12

Brachylog (v2), 6 bytes

≤₁|ḍt↰

Pruébalo en línea!

Esta es una presentación de función. Entrada desde la izquierda, salida hacia la derecha, como de costumbre. (El enlace TIO utiliza un argumento de línea de comandos que envuelve automáticamente la función en un programa completo, para que pueda verla en acción).

Explicación

≤₁|ḍt↰
≤₁       Assert that {the input} is sorted {and output it}
  |      Handler for exceptions (e.g. assertion failures):
   ḍ     Split the list into two halves (as evenly as possible)
    t    Take the last (i.e. second) half
     ↰   Recurse {and output the result of the recursion}

Ronda de bonificación

≤₁|⊇ᵇlᵍḍhtṛ↰

Pruébalo en línea!

El chasquido debe ser aleatorio, ¿no? Aquí hay una versión del programa que elige los elementos supervivientes al azar (al tiempo que garantiza que la mitad sobreviva en cada ronda).

≤₁|⊇ᵇlᵍḍhtṛ↰
≤₁            Assert that {the input} is sorted {and output it}
  |           Handler for exceptions (e.g. assertion failures):
   ⊇ᵇ         Find all subsets of the input (preserving order)
     lᵍ       Group them by length
       ḍht    Find the group with median length:
         t      last element of
        h       first
       ḍ        half (split so that the first half is larger)
          ṛ   Pick a random subset from that group
           ↰  Recurse

Esto sería bastante más corto si pudiéramos reordenar los elementos, pero ¿por qué un algoritmo de clasificación querría hacer eso ?

ais523
fuente
12
Un byte por piedra infinita.
djechlin
@djechlin el byte infinito es la razón por la que debes ir por la cabeza y especialmente por la mandíbula.
El gran pato
10

Perl 6 , 30 bytes

$!={[<=]($_)??$_!!.[^*/2].&$!}

Pruébalo en línea!

Función recursiva que elimina la segunda mitad de la lista hasta que se ordena.

Explicación:

$!={                         }    # Assign the function to $!
    [<=]($_)??                    # If the input is sorted
              $_                  # Return the input
                !!                # Else
                  .[^*/2]         # Take the first half of the list (rounding up)
                         .&$!     # And apply the function again
Jo King
fuente
8

Java 10, 106 97 bytes

L->{for(;;L=L.subList(0,L.size()/2)){int p=1<<31,f=1;for(int i:L)f=p>(p=i)?0:f;if(f>0)return L;}}

-9 bytes gracias a @ OlivierGrégoire .

Pruébalo en línea.

Solo deje la primera mitad de la lista cada iteración, y elimina los elementos si el tamaño de la lista es impar.norte+12

Explicación:

L->{               // Method with Integer-list as both parameter and return-type
  for(;;           //  Loop indefinitely:
      L=L.subList(0,L.size()/2)){
                   //    After every iteration: only leave halve the numbers in the list
    int p=1<<31,   //   Previous integer, starting at -2147483648
        f=1;       //   Flag-integer, starting at 1
    for(int i:L)   //   Inner loop over the integer in the list:
      f=p>(p=i)?   //    If `a>b` in a pair of integers `a,b`:
         0         //     Set the flag to 0
        :          //    Else (`a<=b`):
         f;        //     Leave the flag the same
    if(f>0)        //   If the flag is still 1 after the loop:
      return L;}}  //    Return the list as result
Kevin Cruijssen
fuente
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;} es más corto usando transmisiones, pero no he podido descubrir cómo evitar el java.lang.IllegalStateException: stream has already been operated upon or closederror después de devolver la transmisión
Encarnación de la ignorancia
@EmbodimentofIgnorance esto sucede porque reducees una operación de terminal que cierra la transmisión. Nunca podrá llamar reducedos veces en la misma transmisión. Sin embargo, puede crear una nueva secuencia.
Olivier Grégoire
1
97 bytes
Olivier Grégoire
@ OlivierGrégoire Ese orden parece tan simple ahora que lo veo ... A veces se necesita mirar desde otro ángulo para ver lo obvio que otros fallan inicialmente, supongo. :) ¡Gracias!
Kevin Cruijssen
1
No se preocupe, no era obvio: trabajé para llegar allí. Probé al menos 10 versiones antes de encontrar esa;)
Olivier Grégoire
8

Wolfram Language (Mathematica) , 30 bytes

#//.x_/;Sort@x!=x:>x[[;;;;2]]&

Pruébalo en línea!

@Doorknob guardó 12 bytes

J42161217
fuente
1
En lugar de tomar la primera mitad, puede guardar algunos bytes al tomar cualquier otro elemento ( x[[;;;;2]]).
Pomo de la puerta
@Doorknob sí, por supuesto ...
J42161217
pensé que podría haber algunos ahorros al usarlo OrderedQ, pero no podía hacerlo funcionar
Greg Martin
@ GregMartin que usé OrderedQen mi primer acercamiento (ver ediciones)
J42161217
7

JavaScript (ES6),  49  48 bytes

Guardado 1 byte gracias a @tsh

Elimina cada segundo elemento.

f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>a^=1)):a

Pruébalo en línea!

Arnauld
fuente
p++&1->a^=1
tsh
6

05AB1E , 8 7 bytes

[Ð{Q#ιн

-1 byte gracias a @Emigna .

n12

Pruébelo en línea o verifique algunos casos de prueba más (o verifique esos casos de prueba con paso a paso para cada iteración ).

Alternativa de 7 bytes por @Grimy :

ΔÐ{Ê>äн

n2n12

Pruébelo en línea o verifique algunos casos de prueba más (o verifique esos casos de prueba con paso a paso para cada iteración ).

Explicación:

[        # Start an infinite loop:
 Ð       #  Triplicate the list (which is the implicit input-list in the first iteration)
  {Q     #  Sort a copy, and check if they are equal
    #    #   If it is: Stop the infinite loop (and output the result implicitly)
  ι      #  Uninterweave: halve the list into two parts; first containing all even-indexed
         #  items, second containing all odd-indexed items (0-indexed)
         #   i.e. [4,5,2,8,1] → [[4,2,1],[5,8]]
   н     #  And only leave the first part

Δ        # Loop until the result no longer changes:
 Ð       #  Triplicate the list (which is the implicit input-list in the first iteration)
       #  Sort a copy, and check if they are NOT equal (1 if truthy; 0 if falsey)
    >    #  Increase this by 1 (so 1 if the list is sorted; 2 if it isn't sorted)
     ä   #  Split the list in that many parts
      н  #  And only leave the first part
         # (and output the result implicitly after it no longer changes)
Kevin Cruijssen
fuente
3
Puede usar en ιlugar de si cambia a una estrategia de mantener todos los demás elementos .
Emigna
1
Alternativa 7 usando la estrategia "eliminar la última mitad":ΔÐ{Ê>äн
Grimy
@Grimy Ese también es un enfoque bastante agradable. ¿Debo agregarlo a mi publicación (acreditándote, por supuesto), o quieres publicarlo como una respuesta separada?
Kevin Cruijssen
Siéntase libre de agregarlo.
Grimy
6

TI-BASIC (TI-84), 47 42 45 44 bytes

-1 byte gracias a @SolomonUcko!

Ans→L1:Ans→L2:SortA(L1:While max(L1≠Ans:iPart(.5dim(Ans→dim(L2:L2→L1:SortA(L1:End:Ans

La lista de entrada está adentro Ans.
La salida está adentro Ansy se imprime implícitamente.

Explicación:

Ans→L1                  ;store the input into two lists
Ans→L2
SortA(L1                ;sort the first list
                        ; two lists are needed because "SortA(" edits the list it sorts
While max(L1≠Ans        ;loop until both lists are strictly equal
iPart(.5dim(Ans→dim(L2  ;remove the latter half of the second list
                        ; removes (n+1)/2 elements if list has an odd length
L2→L1                   ;store the new list into the first list (updates "Ans")
SortA(L1                ;sort the first list
End
Ans                     ;implicitly output the list when the loop ends

Nota: TI-BASIC es un lenguaje tokenizado. El recuento de caracteres no es igual al recuento de bytes.

Tau
fuente
Creo que puede reemplazar not(min(L1=Anscon max(L1≠Anspara guardar un byte.
Solomon Ucko
3

Haskell , 57 55 bytes (gracias solo a ASCII)

f x|or$zipWith(>)x$tail x=f$take(div(length x)2)x|1>0=x

Pruébalo en línea!


Código original

f x|or$zipWith(>)x(tail x)=f(take(div(length x)2)x)|1>0=x

Pruébalo en línea!


Sin golf:

f xs | sorted xs = f (halve xs)
     | otherwise = xs

sorted xs = or (zipWith (>) xs (tail xs))

halve xs = take (length xs `div` 2) xs
Sachera
fuente
1
Bienvenido a PPCG!
Rɪᴋᴇʀ
56
Solo ASCII
57 :(
ASCII solo
55
solo ASCII
3

Octava , 49 bytes

l=input('');while(~issorted(l))l=l(1:2:end);end;l

Pruébalo en línea! Este fue un viaje donde más aburrido es mejor. Tenga en cuenta las dos entradas mucho más interesantes a continuación:

50 bytes

function l=q(l)if(~issorted(l))l=q(l(1:2:end));end

Pruébalo en línea! En lugar de la solución imperativa poco interesante, podemos hacer una solución recursiva, por solo un byte adicional.

53 bytes

f(f=@(g)@(l){l,@()g(g)(l(1:2:end))}{2-issorted(l)}())

Pruébalo en línea! Sí. Una función anónima recursiva, gracias a la brillante respuesta de @ ceilingcat en mi pregunta de . Una función anónima que devuelve una función anónima recursiva definiéndose en su lista de argumentos. Me gustan las funciones anónimas. Mmmmm

Sanchises
fuente
2

MATL , 11 bytes

tv`1L)ttS-a

Pruébalo en línea!

Esto funciona eliminando cada segundo elemento.

Explicación

t      % Take a row vector as input (implicit). Duplicate
v      % Vertically concatenate the two copies of the row vector. When read with
       % linear indexing (down, then across), this effectively repeats each entry
`      % Do...while
  1L)  %   Keep only odd-indexed entries (1-based, linear indexing)
  t    %   Duplicate. This will leave a copy for the next iteration
  tS   %   Duplicate, sort
  -a   %   True if the two arrays differ in any entry
       % End (implicit). A new iteration starts if the top of the stack is true
       % Display (implicit). Prints the array that is left on the stack
Luis Mendo
fuente
2
Roto para la lista inicialmente ordenada: [1, 2, 3, 4, 5] debe permanecer [1, 2, 3, 4, 5]
Falco
@Falco ¡Gracias! Corregido ahora
Luis Mendo
2

Japt , 10 bytes

eUñ)?U:ßUë

Intentalo

eUñ)?U:ßUë     :Implicit input of array U
e              :Compare equality with
 Uñ            :  U sorted
   )           :End compare
    ?U:        :If true then return U else
       ß       :Run the programme again with input
        Uë     :  Every second element of U
Lanudo
fuente
2

Java (JDK) , 102 bytes

n->{for(;n.stream().reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.subList(0,n.size()/2));return n;}

Ya hay una respuesta C #, así que decidí probar mi mano en una respuesta Java.

Pruébalo en línea!

Encarnación de la ignorancia
fuente
Es hora de probar F # :)
aloisdg
2

Cristal , 58 bytes

Con Array#sort( 58 bytes ):

->(a : Array(Int32)){while a!=a.sort;a.pop a.size/2;end;a}

Pruébalo en línea!

Sin Array#sort( 101 bytes ):

->(a : Array(Int32)){while a.map_with_index{|e,i|e>a.fetch i+1,Int32::MAX}.any?;a.pop a.size/2;end;a}

Pruébalo en línea!

Kinxer
fuente
2

Casco , 6 5 bytes

1 byte guardado gracias a Zgarb

ΩΛ<Ċ2

Pruébalo en línea!

Explicación

ΩΛ<Ċ2
Ω         Repeat until
 Λ<         all adjacent pairs are sorted (which means the list is sorted)
   Ċ2         drop every second element from the list
León
fuente
Esto es 11 bytes, no 6. ›echo -n" ΩΛ <(← ½ "| wc --bytes 11
Mike Holler
@MikeHoller Como muchos otros idiomas de golf, Husk utiliza una página de códigos personalizada, para tener acceso a más caracteres diferentes: github.com/barbuz/Husk/wiki/Codepage
Leo
Gracias, aprendí algo hoy :)
Mike Holler
1
Use en Ċ2lugar de (←½guardar un byte.
Zgarb
2

Gaia , 9 8 bytes

eo₌⟨2%⟩↻

Pruébalo en línea!

Explicación:

e		| eval input as a list
       ↻	| until
 o		| the list is sorted
  ₌		| push additional copy
   ⟨2%⟩  	| and take every 2nd element
Giuseppe
fuente
2

Julia 1.0 , 30 bytes

-x=x>sort(x) ? -x[1:2:end] : x

Pruébalo en línea!

Toma cada segundo elemento de la matriz si no está ordenado.

niczky12
fuente
use un operador ASCII como -para 20 bytes. También casi nunca contamos caracteres: | así que sería bueno si eso se eliminara del encabezado
solo ASCII
Cambió eso. Gracias por 2 bytes!
niczky12
2

C ++ (gcc) , 103 bytes

No puedo comentar, pero mejoré la versión de movatica al reducir las inclusiones y usar auto.

-2 Bytes: ceilingcat
-2 Bytes: solo ASCII

#include<regex>
auto f(auto l){while(!std::is_sorted(l.begin(),l.end()))l.resize(l.size()/2);return l;}

Pruébalo en línea!

peterzuger
fuente
1
¿Alguna razón que no puedas usar l.size()/2?
Solo ASCII
Sí, no funciona de esa manera :)
peterzuger
1
¿Qué quieres decir? devolver una lista de tamaño (n+1)/2o (n-1)/2ambos son válidos. hmm ....
ASCII-solo
Ohh oops, no vi eso gracias
peterzuger
1

VDM-SL , 99 bytes

f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0]) 

Nunca se envió en vdm antes, por lo que no estoy seguro de las reglas específicas del idioma. Así que he enviado como una definición de función que toma un seq of inty devuelve unseq of int

Un programa completo para ejecutar podría verse así:

functions
f:seq of int +>seq of int
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0]) 
Datos caducados
fuente
1

Pyth, 10 bytes

.W!SIHhc2Z

Pruébelo en línea aquí . Esto elimina la segunda mitad en cada iteración, redondeando hacia abajo. Para cambiarlo y eliminar la primera mitad, redondeando hacia arriba, cambie el ha e.

.W!SIHhc2ZQ   Q=eval(input())
              Trailing Q inferred
  !SIH        Condition function - input variable is H
   SIH          Is H invariant under sorting?
  !             Logical not
      hc2Z    Iteration function - input variable is Z
       c2Z      Split Z into 2 halves, breaking ties to the left
      h         Take the first half
.W        Q   With initial value Q, execute iteration function while condition function is true
Sok
fuente
Tomar todos los demás elementos de la lista es más corto. Reemplazar hccon %. Esto también le permite eliminar la variable lambda final Zy dejar que Pyth la complete implícitamente, para un total de 2 bytes guardados.
hakr14
1

C ++ (gcc) , 139 137 116 bytes

-2 bytes gracias al techo, -21 bytes gracias a PeterZuger

#include<regex>
auto f(std::vector<int>l){while(!std::is_sorted(l.begin(),l.end()))l.resize(-~l.size()/2);return l;}

Cambie el tamaño del vector a su primera mitad hasta que esté ordenado.

Pruébalo en línea!

movatica
fuente
1
Se requiere que las importaciones se incluyan en el recuento de bytes, por lo que debe agregar includes
Encarnación de la ignorancia
Gracias, los agregaré.
movatica
1

K (oK) , 22 20 bytes

Solución:

{(*2 0N#x;x)x~x@<x}/

Pruébalo en línea!

Itere sobre la entrada hasta que esté ordenada ... si no está ordenada, tome los primeros n / 2 elementos.

{(*2 0N#x;x)x~x@<x}/ / the solution
{                 }/ / lambda that iterates
                <x   / indices that sort x ascending (<)
              x@     / apply (@) these indices back to x
            x~       / matches (~) x? returns 0 or 1
 (       ; )         / 2-item list which we index into
          x          / original input (ie if list was sorted)
       #x            / reshape (#) x
   2 0N              / as 2 rows
  *                  / take the first one      

Ediciones:

  • -2 bytes gracias a ngn
callejero
fuente
1
(.5*#x)#x->*2 0N#x
ngn
Pensé en hacerlo, 2 0Npero supuse que sería más largo (sin pruebas), ¡gracias!
StreetSter
0

Retina , 38 bytes

\d+
*
/(_+),(?!\1)/+`,_+(,?)
$1
_+
$.&

Pruébalo en línea! Toma números separados por comas. Explicación:

\d+
*

Convierte a unario.

/(_+),(?!\1)/+`

Repita mientras la lista no está ordenada ...

,_+(,?)
$1

... eliminar todos los elementos pares.

_+
$.&

Convierte a decimal.

Neil
fuente
0

C (gcc) , 66 bytes

Recorta la segunda mitad de la lista en cada iteración ( n/2+1elementos si la longitud es impar).

Pruébalo en línea!

Toma la entrada como un puntero al inicio de una matriz de intseguido de su longitud. Salidas al devolver la nueva longitud de la matriz (ordena en el lugar).

t(a,n,i)int*a;{l:for(i=0;i<n-1;)if(a[i]>a[++i]){n/=2;goto l;}a=n;}

Versión sin golf:

t(a, n, i) int *a; { // take input as a pointer to an array of int, followed by its length; declare a loop variable i
  l: // jump label, will be goto'ed after each snap
  for(i = 0; i < n - 1; ) { // go through the whole array …
    if(a[i] > a[++i]) { // … if two elements are in the wrong order …
      n /= 2; // … snap off the second half …
      goto l; // … and start over
    }
  }
  a = n; // implicitly return the new length
}
OOBalance
fuente
Sugerir en ~i+nlugar dei<n-1
ceilingcat