Escriba un programa de clasificación que parezca erróneo pero que en realidad sea correcto [cerrado]

12

Escriba un programa que clasifique un vector de números (o cualquier tipo de elemento) que parezca tener uno o más errores, pero en realidad está bien.

  • El código debe ser claro. Alguien que revisa el código debe identificar fácilmente que se trata de un algoritmo de clasificación y debe confundir fácilmente un código correcto con un error.
  • El error (aparente) puede ser cualquier cosa que haga que el código esté mal formado sintáctica o semánticamente (por ejemplo, hacer que el programa no se compile / ejecute, exhiba UB cuando se ejecuta), haga que el programa produzca resultados incorrectos, no termine o no sea determinista.
  • El código debe estar bien formado y el programa debe producir de manera determinista la salida correcta en un tiempo finito.
  • La entrada puede estar codificada en el programa o puede leerse (del usuario, del archivo, etc.).
  • La entrada se considera válida y el programa no es necesario para verificar la corrección de la entrada.
  • Cualquier algoritmo de clasificación es aceptado. La estructura de datos para contener los números no es necesaria para ser un vector real. El programa se puede diseñar para ordenar un número variable de números o un número fijo de números (por ejemplo, un programa para ordenar 3 números está bien ). La ordenación puede ser estable o no (nota: un programa diseñado para hacer una ordenación estable que tiene un error aparente que hace que la ordenación parezca inestable, pero en realidad no es un error: el programa realmente realiza una ordenación estable - es una respuesta válida )
  • puede llamar a cualquiera de las funciones (incluyendo funciones de clasificación), excepto herramientas de 3 ª parte (a menos que sean ampliamente difundidas y utilizadas por ejemplo boospara C++, JQuerypara Javascript- los están bien para su uso)
  • especifica el idioma
  • comente en código la parte que parece un error.
  • explica cómo se ve el error haciendo mal.
  • explique (en un cuadro de spoiler) por qué en realidad no es un error.

Este es un concurso de popularidad. La respuesta con más votos gana.


Este desafío ya ha terminado. El ganador es @Clueless /codegolf//a/30190/11400 con 8 votos. Gracias a todos los que envían!

Si desea ingresar después de que se haya otorgado el ganador, no dude en agregar una nueva respuesta. Estás fuera de carrera, pero todos estamos interesados ​​en ver respuestas interesantes.

bolov
fuente
¿Puedo usar booleanos disponibles en lugar de números?
Οurous
sí, editó la pregunta también: cualquier tipo de elementos
bolov
1
Estoy votando para cerrar esta pregunta como fuera de tema porque los desafíos poco claros ya no están en el tema en este sitio. meta.codegolf.stackexchange.com/a/8326/20469
gato

Respuestas:

11

C ++

Inspirado por Apple goto fail; insecto .

#include <vector>
#include <map>
#include <iostream>

/**
 * Sorts a vector of doubles in reverse order using the bucket sort algorithm.
 */
std::vector<double> reverse_bucket_sort(const std::vector<double>& input) {
    // put each element into a bucket as many times as it appears
    std::map<double, int> bucket_counts;
    for (auto it : input)
        ++bucket_counts[it];

    std::vector<double> sorted_elements; // the return value

    // loop until we are done
    while (bucket_counts.size() > 0) {
        // find the largest element
        double maximum = std::numeric_limits<double>::lowest();
        for (auto it : bucket_counts) {
            if (it.first > maximum)
                maximum = it.first;
                maximum = it.first;
        }

        // add the largest element N times to our sorted vector
        for (int i = 0; i < bucket_counts[maximum]; ++i)
            sorted_elements.push_back(maximum);

        // and now erase the bucket
        bucket_counts.erase(maximum);
    }

    return sorted_elements;
}

int main(int argc, const char * argv[]) {
    std::vector<double> test_case = { 0, 1, 2.5, 10, 2.5, 2 };

    std::cout << "unsorted:";
    for (auto it : test_case) std::cout << " " << it;
    std::cout << std::endl;

    std::cout << "sorted:";
    for (auto it : reverse_bucket_sort(test_case)) std::cout << " " << it;
    std::cout << std::endl;

    return 0;
}

Alrededor de la mitad de la página hay un error: ¡tenemos una línea duplicada después de nuestra ifverificación! Siempre vamos a actualizar el máximo con lo que sea el último valor bucket_count. Afortunadamente estamos bien. En C ++ std::mapse ordena por claves. Así que solo estamos invirtiendo los cubos, que es lo que queremos.

Despistado
fuente
No usaste goto, por lo tanto no hay error. (Refiriéndose a todas las personas que se dice que el fallo no habría ocurrido si Apple no utilizó goto)
user253751
Felicidades, has ganado este desafío al tener la mayor cantidad de votos (8 votos después de 7 días). Además, me gusta mucho su respuesta porque utilizó un error de la vida real.
bolov
8

Python2.x

import random
L = [random.randrange(20) for x in range(20)]
print "Unsorted:", L

def sort(L):
    # terminal case first. Otherwise sort each half recursively and combine
    return L.sort() if L > 1 else sort(L[:len(L)//2]) + sort(L[len(L)//2:])

sort(L)
print "Sorted:", L

Prueba de funcionamiento

list.sortvuelve None, entonces la parte después de la elsees None + None. Afortunadamente, esto no causa un problema porque la comparación de una lista y un int (L > 1)es siempre True. La función siempre regresa, Nonepor lo que ignoramos el valor de retorno e imprimimos el Lque se ha ordenado en su lugar. La fusión de las mitades ordenadas por catenación tampoco habría funcionado incluso si la ejecución hubiera llegado allí.

gnibbler
fuente
Enhorabuena, ha quedado en segundo lugar con 6 votos después de 7 días. Gracias por tu presentación.
bolov
5

C

Usar ordenación incorrectamente: en un sistema de 64 bits, inttiene 4 bytes y char *8 bytes, por lo que no debería funcionar.

Código:

#include <stdlib.h>
#include <stdio.h>

/* Compare integers to sort in reverse order */
int compare(const void *p, const void *q)
{
    const int *a = p;
    const int *b = q;

    return *b - *a;
}

int main()
{
    char *strings[] = {"B", "Que", "Ro", "Sum", "T"};
    int i;

    /* Let's use the integer compare to sort strings */
    qsort(&strings, sizeof(strings) / sizeof(char *), sizeof(char *), compare);

    /* Output the sorted results */
    for (i = 0; i < sizeof(strings) / sizeof(char *); i++)
        printf("%s\n", strings[i]);

    return 0;
}

Construir:

$ gcc -o sort-no-sort sort-no-sort.c 

Correr:

$ ./sort-no-sort 
T
Sum
Ro
Que
B

Sí, ¡está bien!

Suceden cinco cosas: 1) qsortpasa los punteros a los enteros, que son del mismo tamaño que los punteros a los caracteres. 2) Las cadenas no tienen más de cuatro bytes de longitud (tres + un terminador) = el tamaño de un número entero, que la rutina de clasificación felizmente trata como un número entero. 3) La mayoría de los compiladores fuerzan la alineación de las estructuras de datos, por lo que las cadenas más cortas ocupan el mismo espacio. Sin embargo, más grande y prepárate para los fracasos. 4) Endian-ness. 5) Cero inicialización de bytes internos.


fuente
Gracias por tu presentación. Has colocado el 3er. Enhorabuena!
bolov
2

Cobra

class Program
    var _target as List<of bool?> = [true, true, false, true, true, nil, nil, false, true, nil, true]
    def main
        .sort(_target)
        print _target
    def sort(target as List<of bool?>)
        for i in target.count, for n, in target.count -1, if target[n] <> target[n + 1] and (target[n] or target[n + 1] == nil), target[n], target[n + 1] = target[n + 1], target[n]
            #should return sorted as [nil][false][true]

¡Dios mío, parece que he asignado incorrectamente n... y cómo llegaron todas esas comas !?

Cuando nse asigna, el compilador supone que se le está dando la primera mitad de un par clave-valor (debido a la coma), pero no hay un par clave-valor, por lo que el compilador no se queja cuando no puede asignar la segunda mitad de ello a una variable inexistente. Esto da como resultado nsimplemente que se le dé el valor clave ... que en este caso es un número de índice. Todas las otras comas fuera de lugar en la línea final son en realidad parte de la sintaxis estándar de Cobra.

Οurous
fuente
Gracias por tu presentación. Has colocado el 3er. Enhorabuena!
bolov
2

Java

public final class WeirdSort {
    public static void main(final String[] args) {

        //Random
        final Random random = new Random(441287210);

        //Some numbers:
        final List<Integer> list = new ArrayList<Integer>();
        list.add(9);
        list.add(11);
        list.add(3);
        list.add(5);
        list.add(7);

        //Sort randomly:
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(final Integer o1, final Integer o2) {
                return (o1 - o2) + random.nextInt(10);
            }
        });

        //Print
        for(final Integer i:list) {
            System.out.print(i + " ");
        }
    }
}

Prints: 3 5 7 9 11 

Funciona porque este valor aleatorio específico devuelve '1' para los primeros 10 resultados

Roy van Rijn
fuente
1
¿Qué idioma usas?
Knerd
Java, perdón, olvidé mencionar eso (editado).
Roy van Rijn
2

Perl

Contratistas en estos días! ¿No saben que el <=>operador (también conocido como "nave espacial") solo se usa para la clasificación numérica?

¿Y por qué están comparando operadores?

¿Cómo pasó este código incluso nuestras estrictas pruebas? ¡Incluso usa stricty warnings!

use strict;
use warnings;

sub asciibetically { 0-($a lt $b) || 0+($a gt $b) || <=><=><=> }
                                                   #  ^  ^  ^
                                                   # What?? How did Perl even compile??!!

my @sorted = sort asciibetically qw( bravo charlie alpha );

print "@sorted";   # "alpha bravo charlie"
                   # And how come it works??!!

¿Por qué compila Perl?

El único <=>operador real es el del medio. Las otras dos son solo otra forma de escribir glob("="). Esto significa que <=><=><=>(apodado "flota espacial") evalúa a 0.


Por que funciona

La asciibeticallysubrutina es una implementación del cmpoperador de comparación de cadenas : " cmp" binario devuelve -1, 0o 1dependiendo de si el argumento izquierdo es stringwise menor que, igual o mayor que el argumento derecho.

Zaid
fuente
3
Bueno, Perl parece un error de todos modos para mí ...
chill0r