Leetcode sudoku válido

Question

Enlace aquí

Incluiré una solución en Python y C ++ y puedes revisar una. Lo que más me interesa es revisar el código C ++, que es algo que comencé a aprender recientemente; aquellos que no conocen C ++ pueden revisar el código Python. Ambas soluciones comparten una lógica similar, por lo que la revisión se aplicará a cualquiera.

---

Planteamiento del problema

Determina si un tablero de Sudoku de 9 x 9 es válido. Solo las celdas llenas deben validarse de acuerdo con las siguientes reglas:

• Cada fila debe contener los dígitos del 1 al 9 sin repetición. Cada columna
• debe contener los dígitos del 1 al 9 sin repetición. Cada uno de los nueve 3 x
• 3 subcajas de la cuadrícula deben contener los dígitos del 1 al 9 sin repetición.

Nota:

Un tablero de Sudoku (parcialmente lleno) podría ser válido pero no necesariamente tiene solución. Solo las celdas llenas deben validarse de acuerdo con las reglas mencionadas.

Ejemplo 1:

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

Ejemplo 2:

Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

valid_sudoku.py

def is_valid(board, empty_value='.', b_size=3):
    seen = set()
    size = b_size * b_size
    for row in range(size):
        for col in range(size):
            if (value := board[row][col]) == empty_value:
                continue
            r = f'0{row}{value}'
            c = f'1{col}{value}'
            b = f'2{row // b_size}{col // b_size}{value}'
            if r in seen or c in seen or b in seen:
                return False
            seen.update({r, c, b})
    return True


if __name__ == '__main__':
    g = [
        ["5", "3", ".", ".", "7", "5", ".", ".", "."],
        ["6", ".", ".", "1", "9", "5", ".", ".", "."],
        [".", "9", "8", ".", ".", ".", ".", "6", "."],
        ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
        ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
        ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
        [".", "6", ".", ".", ".", ".", "2", "8", "."],
        [".", ".", ".", "4", "1", "9", ".", ".", "5"],
        [".", ".", ".", ".", "8", ".", ".", "7", "9"],
    ]
    print(is_valid(g))

Estadísticas:

Runtime: 92 ms, faster than 81.70% of Python3 online submissions for Valid Sudoku.
Memory Usage: 14.1 MB, less than 73.95% of Python3 online submissions for Valid Sudoku.

Aquí hay una solución alternativa que usa numpy, es más corta y más legible pero más lenta:

import numpy as np


def is_valid(board, size=3, empty_value='.'):
    board = np.array(board)
    blocks = board.reshape(4 * [size]).transpose(0, 2, 1, 3).reshape(2 * [size * size])
    for grid in [board, board.T, blocks]:
        for line in grid:
            non_empty = line[line != empty_value]
            if not len(non_empty) == len(set(non_empty)):
                return False
    return True

Estadísticas:

Runtime: 172 ms, faster than 5.19% of Python3 online submissions for Valid Sudoku.
Memory Usage: 30.2 MB, less than 11.10% of Python3 online submissions for Valid Sudoku.

valid_sudoku.h

#ifndef LEETCODE_VALID_SUDOKU_H
#define LEETCODE_VALID_SUDOKU_H

#include <string_view>
#include <unordered_set>

bool sudoku_check_update(const size_t &row, const size_t &col, const char &value,
                         const int &block_size,
                         std::unordered_set<std::string_view> &seen);

bool sudoku_check(const std::vector<std::vector<char>> &board,
                  const char &empty_value = '.');

void test1();

#endif //LEETCODE_VALID_SUDOKU_H

valid_sudoku.cpp

#include <iostream>
#include <vector>
#include <string_view>
#include <cmath>
#include <unordered_set>


bool sudoku_check_update(const size_t &row, const size_t &col, const char &value,
                         const int &block_size,
                         std::unordered_set<std::string_view> &seen) {
    std::string_view r, c, b;
    r = "0-" + std::to_string(row) + value;
    c = "1-" + std::to_string(col) + value;
    b = "2-" + std::to_string(row / block_size) + std::to_string(col / block_size) +
        value;
    for (const auto &seen_id: {r, c, b}) {
        if (seen.find(seen_id) != seen.end())
            return false;
        seen.insert(seen_id);
    }
    return true;
}


bool sudoku_check(const std::vector<std::vector<char>> &board,
                  const char &empty_value = '.') {
    std::unordered_set<std::string_view> seen;
    const auto row_size = board.size();
    const int block_size = std::sqrt(row_size);
    for (size_t row = 0; row < row_size; ++row) {
        for (size_t col = 0; col < row_size; ++col) {
            auto value = board[row][col];
            if (value == empty_value)
                continue;
            if (!sudoku_check_update(row, col, value, block_size, seen))
                return false;
        }
    }
    return true;
}


void test1() {
    std::vector<std::vector<char>> v = {
            {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
            {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
            {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
            {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
            {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
            {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
            {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
            {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
    };
    std::cout << sudoku_check(v);
}

Estadísticas:

Runtime: 48 ms, faster than 17.98% of C++ online submissions for Valid Sudoku.
Memory Usage: 20.4 MB, less than 22.55% of C++ online submissions for Valid Sudoku.

Answer 1

A continuación, se incluyen algunas sugerencias sobre cómo podría mejorar su código.

Versión C ++

Utilice todos los #includes requeridos

El tipo std::vector<std::vector<char>>se usa en la definición de sudoku_check()en el archivo de encabezado, pero #include <vector>falta en la lista de incluye allí.

Minimizar la interfaz

El .harchivo es una declaración de la interfaz de su software. El .cppes la aplicación de esa interfaz. Es una buena práctica de diseño minimizar la interfaz a la que necesitan los programas externos. Por esa razón, me gustaría quitar los sudoku_check_update()y las test1()funciones y el uso justo esto:

#ifndef LEETCODE_VALID_SUDOKU_H
#define LEETCODE_VALID_SUDOKU_H

#include <vector>

bool sudoku_check(const std::vector<std::vector<char>> &board,
                  const char &empty_value = '.');

#endif //LEETCODE_VALID_SUDOKU_H

La implementación debe incluir el encabezado de la interfaz

Como dice el título de esta sección, la implementación debe incluir el encabezado de la interfaz. Esto asegura que la interfaz y la implementación coincidan y elimina errores. Si hacemos eso en este caso, vemos que el valor predeterminado para empty_valuese declara dos veces. Solo debe declararse una vez en el archivo de encabezado.

Hacer funciones locales static

Con la interfaz más pequeña como se propuso anteriormente, la sudoku_check_updatefunción se convierte en un detalle de implementación que se usa solo dentro del .cpparchivo. Por esa razón, debe hacerse staticpara que el compilador sepa que es seguro incorporar la función.

La palabra clave staticcuando se usa con una declaración de función especifica que el enlace es interno. En otras palabras, significa que nada fuera de ese archivo puede acceder a la función. Esto es útil para que el compilador lo sepa porque, por ejemplo, si una staticfunción se usa solo una vez y / o es pequeña, el compilador tiene la opción de poner el código en línea. Es decir, en lugar del lenguaje ensamblador habitual call... retinstrucciones para saltar a una subrutina y regresar de ella, el compilador puede simplemente poner el código de la función directamente en esa ubicación, ahorrando el costo computacional de esas instrucciones y ayudando a asegurar la caché Las predicciones son correctas (porque normalmente la caché aprovecha la localidad de referencia ).

Lea también sobre los especificadores de clases de almacenamiento para comprender mejor lo que statichace en otros contextos y, de manera más general, los especificadores de declaración para obtener explicaciones constexpry más.

¡Arregla el error!

Actualmente, el código se usa de manera string_viewinapropiada. A std::string_viewes esencialmente un puntero a una cadena que existe. Pero sus cadenas se componen y eliminan dinámicamente, por lo que este es un uso no válido de std::string_view. Si reemplaza todas las instancias de string_viewcon string, el programa funciona.

Los problemas de memoria como este y los errores de concurrencia se encuentran entre los problemas más difíciles de detectar y corregir para los programadores. A medida que adquiera más experiencia, descubrirá que su capacidad para detectar estos problemas y evitarlos surge de manera más refleja. Hay muchos enfoques para encontrar tales errores. Consulte la clase simple de detección de fugas para ver algunos de ellos.

Escribe mejores funciones de prueba

El error mencionado anteriormente se descubrió fácilmente llamando a la función varias veces con diferentes entradas. Quizás ya tenía una gama más amplia de funciones de prueba, pero si no es así, le recomiendo que las cree y aplique.

Utilice estructuras de datos eficientes

Si el objetivo de este código es ser eficiente en términos de tiempo de ejecución y memoria, se pueden realizar muchas mejoras. Primero, la estructura de datos std::unordered_set<std::string_view>no es óptima. Siempre que estamos trabajando en una optimización del rendimiento, es útil medir. Así que escribí un programa de prueba muy simple basado en mi plantilla de cronómetro . Esta aquí:

#include "valid_sudoku.h"
#include "stopwatch.h"
#include <iostream>
#include <vector>
#include <string>

int main(int argc, char* argv[]) {
    std::vector<std::vector<char>> v = {
            {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
            {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
            {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
            {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
            {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
            {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
            {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
            {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
    };
    if (argc != 2) {
        std::cout << "Usage: " << argv[0] << " num_trials\n";
        return 1;
    }
    auto iterations = std::stoul(argv[1]);

    Stopwatch<> timer{};

    bool valid{true};
    for (auto i{iterations}; i; --i) {
        valid &= sudoku_check(v);
    }

    auto elapsed{timer.stop()};
    if (!valid) {
        std::cout << "The program failed!\n";
        return 2;
    }
    std::cout << iterations << " trials took " << elapsed << " microseconds\n"
        " for an average of " << elapsed/iterations << " microseconds/trial\n";
}

Cuando ejecuto esto en mi máquina con 1,000,000 de pruebas, (con el error mencionado anteriormente corregido como se describe) aquí está el resultado que obtengo:

1000000 ensayos tomaron 1,44351e + 07 microsegundos para un promedio de 14,4351 microsegundos / ensayo

Ahora pensemos en una estructura de datos más eficiente. En lugar de un unordered_set, podríamos usar un conjunto de matrices fijas. Hay nueve filas, nueve columnas y nueve subcuadrados. Cada uno de ellos contiene un número o no. Para mí, eso sugiere que podríamos usar un objeto como este:

using SeenType = std::array<std::array<std::array<bool, 9>, 9>, 3>;

Contiene los 3 tipos (filas, columnas, subcuadrados) y dentro de cada uno, 9 colecciones de 9 bits; un bit por cada número. Reescribamos la función para usar esto:

static bool sudoku_check_update(std::size_t row, std::size_t col, 
        char value, SeenType &seen) {
    static constexpr std::size_t block_size{3};
    static_assert(block_size * block_size == row_size, "block_size must be the square root of row_size");
    const std::size_t block = col / block_size + block_size * (row / block_size);
    std::size_t dim{0};
    value -= '1';   // adjust from digits '1'-'9' to indices 0-8.
    for (const auto &seen_id: {row, col, block}) {
        if (seen[dim][seen_id][value])
            return false;
        seen[dim][seen_id][value] = true;
        ++dim;
    }
    return true;
}

Ahora vuelva a ejecutar el programa con un millón de pruebas como antes:

1000000 ensayos tomaron 562153 microsegundos para un promedio de 0.562153 microsegundos / ensayo

Así que ese cambio hizo que las cosas fueran 25 veces más rápidas . También podríamos usar el hecho de que se sabe que las dimensiones usan a en std::array<std::array<char, 9>, 9>lugar de los vectores y se usan constexprpara esas dimensiones. Al hacer ese cambio también, obtenemos esto:

1000000 ensayos tomaron 160808 microsegundos para un promedio de 0.160808 microsegundos / ensayo

Así que ahora es 90 veces más rápido .

Preferir {}inicializaciones de estilo

Puede notar que el código que escribo tiende a usar el {}estilo de inicialización. Hay varias razones para esto, incluido el hecho de que cuando lo ve, siempre es una inicialización y no puede confundirse con una llamada de función. Consulte ES.23 para obtener más detalles.

Pasar valores en lugar de referencias para tipos de datos cortos

En lugar de pasar const size_t &colo const char& value, generalmente es mejor pasarlos por valor. Esto suele ser ventajoso porque es probable que el puntero sea más largo que el objeto al que apunta y porque permite la eliminación de una búsqueda indirecta y de memoria.

Mueva los cálculos del tiempo de ejecución al tiempo de compilación cuando sea práctico

Probablemente no tome mucho tiempo, pero esta línea no es tan rápida como podría ser:

const int block_size = std::sqrt(row_size);

Lo que hace esto es convertir row_sizea a double, invoca la sqrtfunción de punto flotante y convierte el doublereverso en un int. Por el contrario, podríamos escribir esto:

constexpr std::size_t block_size{3};

Ahora no lleva nada de tiempo en tiempo de ejecución porque el valor se conoce en tiempo de compilación. También elimina tener que pasar el valor y, como se indicó anteriormente, su definición se puede colocar en el único lugar donde realmente se necesita, que es dentro de la sudoku_check_updatefunción.

Generalmente, preferimos mover cosas del tiempo de ejecución al tiempo de compilación por tres razones:

1. Los programas generalmente se ejecutan más veces de las que se compilan, por lo que optimizamos para las ocurrencias más comunes.
2. Cuanto antes detectemos errores, más baratos y fáciles serán de solucionar.
3. Tiende a hacer que el software sea más pequeño e, internamente, más simple, lo que mejora la velocidad de carga, el rendimiento de la caché y el software más simple tiende a mejorar la calidad.

Versión de Python

Evítalo continuereestructurando el bucle

No hay nada intrínsecamente malo en el uso del operador de morsa, pero parece haber pocas razones para no invertir el sentido de la comparación y simplemente procesar la actualización en lugar de usarla continue. No afecta el rendimiento, pero ayuda al lector humano del código a comprender el flujo del programa. Tiendo a colocar cláusulas de "rescate" tempranas en una función para rechazar rápidamente condiciones inválidas, pero evitar continueen bucles; en última instancia, es una cuestión de legibilidad y estilo en C ++ o Python.

Utilice estructuras de datos más eficientes

Lo que era cierto en C ++ también funciona en Python. Podemos usar las mismas ideas y acelerar el código en un factor de 6:

def is_valid(board, empty_value='.', b_size=3):
    size = b_size * b_size
    seen = [[(size * [False]) for _ in range(size)] for _ in range(3)]
    for row in range(size):
        for col in range(size):
            if (value := board[row][col]) != empty_value:
                block = col // b_size + b_size * (row // b_size)
                dim = 0
                value = int(value) - 1
                for seen_id in [row, col, block]:
                    if seen[dim][seen_id][value]:
                        return False
                    seen[dim][seen_id][value] = True
                    dim += 1
    return True

Answer 2

Minor (y Python), pero personalmente encuentro esto un poco confuso:

if (value := board[row][col]) == empty_value:
    continue
r = f'0{row}{value}'
c = f'1{col}{value}'
b = f'2{row // b_size}{col // b_size}{value}'

Está usando una expresión de asignación para asignar un valor, pero luego solo lo usa en caso falso. Creo que esto sería mucho más limpio al usar una declaración de asignación simple y antigua:

value = board[row][col]
if value == empty_value:
    continue
r = f'0{row}{value}'
c = f'1{col}{value}'
b = f'2{row // b_size}{col // b_size}{value}'

No creo que valga la pena enterrar la línea guardada en la creación de una variable.

Answer 3

C ++

Es más simple, y posiblemente más rápido, pasar pequeños tipos de datos simples como size_ty charpor valor, no por referencia. Entonces deberíamos tener:

bool sudoku_check_update(size_t row, size_t col, char value, int block_size,
                         std::unordered_set<std::string_view> &seen)

bool sudoku_check(const std::vector<std::vector<char>> &board,
                  char empty_value = '.')

---

Más importante aún: std::string_view no se puede utilizar para almacenar cadenas. No es dueño de la cadena, es solo un puntero y un tamaño.

Al hacer algo como esto:

std::string_view r = "0-" + std::to_string(row) + value;

... construimos un temporal std::stringy luego lo asignamos a un string_view. Sin embargo, la cadena temporal queda fuera de alcance al final de esta línea.

Ha pasado. Esta cadena ya no existe. Ha dejado de ser. Caducó y fue a encontrarse con su creador. Esta es una cadena tardía. Es una rigidez. Desprovisto de vida, descansa en paz. Si no lo hubiéramos clavado, std::string_viewestaríamos empujando las margaritas. Ha bajado el telón y se ha unido al coro invisible. Este es un ex-string.

En otras palabras, es un comportamiento indefinido intentar usar eso string_view. Entonces r, cy bnecesitan ser std::stringellos mismos. Y seendebería ser un std::unordered_set<std::string>.

---

Re. std::string_view:

std::string_viewapunta a un rango de caracteres en la memoria. Estos caracteres pueden almacenarse en a std::string, en a std::array, a std::vectoro en un literal de cadena.

Al usarlo std::string_view, obtenemos la misma interfaz (búsqueda, comparación, creación de subcadenas) independientemente de cuál sea el almacenamiento subyacente. Por lo que es útil como lenguaje común entre estos tipos.

Dado std::string_viewque no posee los personajes, no asigna memoria ni se copia a sí mismo. Esto lo hace útil para cosas como analizar archivos de texto largos: podemos buscar y comparar en subcadenas sin hacer la copia que std::stringsería necesaria.

La compensación es que tenemos que asegurarnos de que la vida útil de la cadena real en la memoria sea más larga que la de string_view.