Consejos para probar código en programación competitiva

Pruebas Los problemas de codificación a veces pueden volverse agitados. Aquí hay algunos consejos para usar al probar problemas de programación algorítmica.

En general, hay cuatro categorías principales de defectos en el programa:

1. Errores sintácticos
2. Errores semánticos
3. Errores en tiempo de ejecución / Excepción
4. Errores lógicos

Errores sintácticos

Los errores sintácticos son generalmente errores gramaticales en un programa.

Para verificar el programa en busca de errores sintácticos, debe seguir los pasos a continuación:

• Compilando el código en el compilador
• Algunos errores sintácticos comunes son:
  • Extraviar llaves, paréntesis, etc.
  • Final de comentarios fuera de lugar
  • Errores tipográficos
  • Palabras clave fuera de lugar

Errores semánticos 

Los errores semánticos pueden obedecer a la gramática, pero violar otras reglas del lenguaje.
Algunos errores semánticos comunes son:

• Realizar operaciones incorrectas en tipos de datos primitivos.
• Método de instancia de invocación que no está definido.
• No declarar una variable antes de usarla.

Errores de tiempo de ejecución/excepciones

Los errores de tiempo de ejecución generalmente ocurren en el momento de la ejecución del programa.
Ejemplos de errores/excepciones de tiempo de ejecución son:

• División por cero
• índice de array fuera de los límites
• Número de errores de formato
• Excepción de puntero nulo

Errores lógicos

Los errores lógicos son un error en el diseño de la clase o en la implementación de un algoritmo.
Los errores lógicos se pueden evitar mediante:

• Esforzarse por la claridad y la simplicidad.
• Considere casos extremos o de esquina
• Pensando en las condiciones pre/post
• Organizando el código

Prueba de errores lógicos en código con ejemplo

Los errores lógicos de prueba/errores en el código son difíciles de encontrar. Aquí hay un recorrido por los errores lógicos de prueba en el código con la ayuda de un ejemplo.

Problema del producto máximo por pares : dada una array o una secuencia de N números y el objetivo es encontrar un número que se pueda obtener multiplicando algunos dos números de esta secuencia.

Soluciones

Solución ingenua – O(N ² )

Iterar a través de todos los pares posibles en la secuencia usando un bucle for anidado.

// Function to find the maximum
// pairwise product
int MaxPairwiseProduct(
    const std::vector<int>& numbers)
{
    int max_product = 0;
    int n = numbers.size();
 
    // Loop to find the pairs
    // with the maximum product
    for (int first = 0; first < n;
         ++first) {
        for (int second = first + 1;
             second < n; ++second) {
            max_product
                = std::max(
                    max_product,
                    numbers[first]
                        * numbers[second]);
        }
    }
    return max_product;
}

Enfoque eficiente:

La mejor solución para este problema sería encontrar los dos números más grandes y los dos más pequeños de la secuencia y devolver un máximo de productos entre (el más grande, el segundo más grande) y (el más pequeño, el segundo más pequeño). Y eso sería en tiempo O(n).

A continuación se muestra la implementación del enfoque anterior:

// Efficient Approach for the
// maximum product pair
long long MaxPairwiseProductFast(
    const std::vector<int>& numbers)
{
    int large1 = -1;
    int large2 = -1;
    int n = numbers.size();
 
    // Loop to iterate over the elements
    // of the given array
    for (int i = 0; i < n; ++i) {
        if (numbers[large1] < numbers[i]
            || large1 == -1)
            large1 = i;
    }
    for (int j = 0; j < n; ++j) {
        if ((numbers[j] != numbers[large1])
            && ((numbers[large2] < numbers[j])
                || (large2 == -1))) {
            large2 = j;
        }
    }
 
    return ((long long)numbers[large1]
            * numbers[large2]);
}

 
Pruebas

Puede realizar una variedad de pruebas en su código, pero las pruebas más comunes pueden ser estas tres:

1. Antes de enviar el código para su evaluación, se debe probar el código con pruebas de ejemplo de la declaración del problema, que son las más fáciles de escribir y verificar.
2. Pequeños casos de esquina, que se pueden escribir a mano y para los que conoce las respuestas. También hemos abordado algunos casos de esquina en nuestra implementación: (largo largo) para abordar problemas de rango de enteros, (si declaraciones) y controles (abs).
3. Grandes pruebas aleatorias, que se generan mediante scripts simples para probar la complejidad del tiempo. Este tipo de prueba se llama prueba de estrés .

Ponga a prueba su código:

En realidad, esta es una situación bastante estándar cuando se resuelven problemas de programación algorítmica. Entonces, ¿qué son las pruebas de estrés? En general, es un script que crea pruebas aleatorias en un bucle infinito y, para cada prueba, llama a su solución en esta prueba y una solución alternativa correcta en la misma prueba y compara los resultados. Si encuentra una prueba en la que el resultado de sus soluciones difiere, puede verificar cuál de ellas arroja la respuesta incorrecta, depurarla y luego volver a ejecutar el script de prueba de esfuerzo.

A continuación se muestra el ejemplo de prueba de estrés del código del problema de ejemplo anterior:

#include <bits/stdc++.h>
using namespace std;
 
// Function to show the stress
// Testing of the code
int main()
{
    while (true) {
        int n = rand() % 3 + 2;
        cout << n << endl;
        std::vector<int> a;
        for (int i = 0; i < n; ++i) {
            a.push_back(rand() % 10);
        }
        for (int i = 0; i < n; ++i) {
            cout << a[i] << ' ';
        }
        cout << endl;
        long long res1 = MaxPairwiseProduct(a);
        long long res2 = MaxPairwiseProductFast(a);
        if (res1 != res2) {
            cout << "Wrong Answer: "
                 << res1 << ' '
                 << res2 << endl;
            break;
        }
        else
            cout << "OK\n";
    }
    return 0;
}

 
Este sencillo script es su algoritmo de prueba de esfuerzo. Al ejecutar esto, puede encontrar que las implementaciones anteriores difieren en algunos casos cuando aparecen elementos duplicados en la array.

Ahora bien, esto se debe a un error pasado por alto en el algoritmo, es decir, comprobamos que el número en la posición j es diferente del máximo que ya hemos encontrado. Pero ese es exactamente el problema. En cambio, lo que necesitamos es que j debe ser diferente de large1 porque no queremos encontrar el mismo índice, pero podemos encontrar el número que es igual al primer máximo encontrado. Entonces, en lugar de esta comparación, lo que realmente necesitamos es comparar j con large1 .

Solución final sin errores:

// Function to find the maximum
// pair wise product
long long MaxPairwiseProductSuperFast(
    const std::vector<int>& numbers)
{
    int poslarge1 = INT_MIN,
        poslarge2 = INT_MIN;
    int neglarge1 = INT_MIN,
        neglarge2 = INT_MIN;
    int n = numbers.size();
 
    if (n < 2) {
        return 0;
    }
    if (n == 2) {
        return ((long long)numbers[0]
                * numbers[1]);
    }
 
    // Loop to iterate over the elements
    // of the array and find the two
    // largest and two smallest elements
    for (int i = 0; i < n; ++i) {
        if (numbers[i] > poslarge1) {
            poslarge2 = poslarge1;
            poslarge1 = numbers[i];
        }
        else if (numbers[i] > poslarge2)
            poslarge2 = numbers[i];
        if (numbers[i] < 0
            && abs(numbers[i]) > abs(neglarge1)) {
            neglarge2 = neglarge1;
            neglarge1 = numbers[i];
        }
        else if (numbers[i] < 0
                 && abs(numbers[i]) > abs(neglarge2))
            neglarge2 = numbers[i];
    }
 
    return (
        std::max(
            (long long)poslarge1 * poslarge2,
            (long long)neglarge1 * neglarge2));
}