Sudoku valido con codice Leetcode

Question

Link qui

Includerò una soluzione in Python e C ++ e potrai esaminarne una. Sono principalmente interessato a rivedere il codice C ++ che è una cosa che ho iniziato a imparare di recente; chi non conosce il C ++ può rivedere il codice Python. Entrambe le soluzioni condividono una logica simile, quindi la revisione si applicherà a qualsiasi.

---

Dichiarazione problema

Determina se una tavola Sudoku 9 x 9 è valida. Solo le celle riempite devono essere convalidate secondo le seguenti regole:

• Ogni riga deve contenere le cifre 1-9 senza ripetizioni. Ogni colonna
• deve contenere le cifre 1-9 senza ripetizioni. Ciascuno dei nove 3 x
• 3 sottocaselle della griglia devono contenere le cifre 1-9 senza ripetizioni.

Nota:

Una scheda Sudoku (parzialmente riempita) potrebbe essere valida ma non è necessariamente risolvibile. Solo le celle riempite devono essere convalidate secondo le regole menzionate.

Esempio 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

Esempio 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))

Statistiche:

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.

Ecco una soluzione alternativa che utilizza numpy, è più breve e più leggibile ma più 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

Statistiche:

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);
}

Statistiche:

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

Ecco alcuni suggerimenti su come potresti migliorare il tuo codice.

Versione C ++

Utilizzare tutte le richieste #includes

Il tipo std::vector<std::vector<char>>viene utilizzato nella definizione di sudoku_check()nel file di intestazione, ma non #include <vector>è presente nell'elenco degli include.

Riduci a icona l'interfaccia

Il .hfile è una dichiarazione dell'interfaccia al tuo software. Il .cppè l' implementazione di tale interfaccia. È una buona pratica di progettazione ridurre al minimo l'interfaccia a ciò che è necessario per i programmi esterni. Per questo motivo, rimuoverei le funzioni e sudoku_check_update()e test1()userei semplicemente questo:

#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

L'implementazione dovrebbe includere l'intestazione dell'interfaccia

Come afferma il titolo di questa sezione, l'implementazione dovrebbe includere l'intestazione dell'interfaccia. Ciò garantisce che l'interfaccia e l'implementazione corrispondano ed elimina gli errori. Se lo facciamo in questo caso, vediamo che il valore predefinito per empty_valueviene dichiarato due volte. Dovrebbe essere dichiarato solo una volta nel file di intestazione.

Crea funzioni locali static

Con l'interfaccia più piccola come sostenuto in precedenza, la sudoku_check_updatefunzione diventa un dettaglio di implementazione utilizzato solo all'interno del .cppfile. Per questo motivo, dovrebbe essere fatto in staticmodo che il compilatore sappia che è sicuro incorporare la funzione.

La parola chiave staticquando utilizzata con una dichiarazione di funzione specifica che il collegamento è interno. In altre parole significa che niente al di fuori di quel file può accedere alla funzione. Questo è utile per il compilatore sapere perché, ad esempio, se una staticfunzione viene utilizzata solo una volta e / o è piccola, il compilatore ha la possibilità di mettere il codice inline. Cioè, invece del solito linguaggio assembly call... retistruzioni per saltare a una subroutine e tornare da essa, il compilatore può semplicemente mettere il codice per la funzione direttamente in quella posizione, risparmiando il costo di calcolo di quelle istruzioni e aiutando a garantire la cache le previsioni sono corrette (perché normalmente la cache sfrutta la località di riferimento ).

Leggi anche gli identificatori della classe di archiviazione per capire meglio cosa staticfa in altri contesti e più in generale gli specificatori di dichiarazione per spiegazioni di constexpre altro ancora.

Risolvi il bug!

Il codice attualmente utilizza in modo string_viewinappropriato. A std::string_viewè essenzialmente un puntatore a una stringa esistente. Ma le tue stringhe vengono composte ed eliminate dinamicamente, quindi questo è un uso non valido di std::string_view. Se sostituisci tutte le istanze di string_viewcon string, il programma funziona.

Problemi di memoria come questo e errori di concorrenza sono tra i problemi più difficili da rilevare e correggere per i programmatori. Man mano che acquisisci più esperienza, scoprirai che la tua capacità di individuare questi problemi ed evitarli viene in modo più riflessivo. Esistono molti approcci per trovare tali errori. Vedere la classe semplice di rilevamento delle perdite per alcuni di essi.

Scrivi funzioni di test migliori

Il bug menzionato sopra è stato facilmente scoperto chiamando la funzione più volte con diversi input. Forse avevi già una gamma più ampia di funzioni di test, ma in caso contrario, ti consiglio vivamente di crearle e applicarle.

Usa strutture dati efficienti

Se l'obiettivo di questo codice è essere efficiente in termini di tempo di esecuzione e memoria, è possibile apportare molti miglioramenti. Innanzitutto, la struttura dei dati std::unordered_set<std::string_view>non è ottimale. Ogni volta che stiamo lavorando a un'ottimizzazione delle prestazioni, è utile misurare. Quindi ho scritto un programma di test molto semplice basato sul mio modello di cronometro . È qui:

#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";
}

Quando lo eseguo sulla mia macchina con 1.000.000 di prove, (con il bug annotato sopra risolto come descritto) ecco il risultato che ottengo:

1000000 prove hanno impiegato 1,44351e + 07 microsecondi per una media di 14,4351 microsecondi / prova

Ora pensiamo a una struttura dati più efficiente. Invece di un unordered_set, potremmo usare un insieme di array fissi. Ci sono nove righe, nove colonne e nove quadrati secondari. Ognuno di questi contiene un numero o no. Per me, questo suggerisce che potremmo usare un oggetto come questo:

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

Contiene i 3 tipi (righe, colonne, quadrati secondari) e all'interno di ciascuno, 9 raccolte di 9 bit; un bit per ogni numero. Riscriviamo la funzione per usare questo:

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;
}

Ora riesegui il programma con un milione di prove come prima:

1000000 prove hanno impiegato 562153 microsecondi per una media di 0,562153 microsecondi / prova

Quindi quel cambiamento ha reso le cose 25 volte più veloci . Potremmo anche usare il fatto che le dimensioni sono note per usare a std::array<std::array<char, 9>, 9>invece dei vettori e constexprper quelle dimensioni. Facendo anche questo cambiamento, otteniamo questo:

1000000 prove hanno impiegato 160808 microsecondi per una media di 0,160808 microsecondi / prova

Quindi ora è 90 volte più veloce .

Preferisci le {}inizializzazioni di stile

Potresti notare che il codice che scrivo tende a utilizzare lo {}stile di inizializzazione. Ci sono diversi motivi per questo, incluso il fatto che quando lo vedi, è sempre un'inizializzazione e non può essere scambiato per una chiamata di funzione. Vedere ES.23 per maggiori dettagli.

Passa valori anziché riferimenti per tipi di dati brevi

Piuttosto che passare const size_t &colo const char& value, in genere è meglio passare quelli per valore. Questo è spesso vantaggioso perché è probabile che il puntatore sia più lungo dell'oggetto a cui punta e perché consente l'eliminazione di un riferimento indiretto e di una ricerca di memoria.

Spostare i calcoli dal runtime al tempo di compilazione, ove pratico

Probabilmente non ci vuole molto tempo, ma questa linea non è così veloce come potrebbe essere:

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

Ciò che fa è convertire row_sizein un double, invoca la funzione a virgola mobile sqrte converte il doubleback in un file int. Al contrario, potremmo semplicemente scrivere questo:

constexpr std::size_t block_size{3};

Ora non ci vuole tempo in fase di esecuzione perché il valore è noto in fase di compilazione. Elimina anche la necessità di passare il valore e, come sopra, la sua definizione può essere collocata nell'unico posto di cui è effettivamente necessario, che è all'interno della sudoku_check_updatefunzione.

In generale, preferiamo spostare le cose dal runtime al tempo di compilazione per tre motivi:

1. i programmi vengono generalmente eseguiti più volte di quanto vengono compilati, quindi ottimizziamo per le occorrenze più comuni
2. prima rileviamo i bug, più economici e facili saranno risolverli
3. tende a rendere il software più piccolo e, internamente, più semplice che migliora la velocità di caricamento, le prestazioni della cache e il software più semplice tende a migliorare la qualità

Versione Python

Evita continueristrutturando il ciclo

Non c'è nulla di intrinsecamente sbagliato nel tuo uso dell'operatore tricheco, ma sembra che ci siano poche ragioni per non invertire il senso del confronto e semplicemente elaborare l'aggiornamento piuttosto che utilizzare continue. Non influisce sulle prestazioni, ma aiuta il lettore umano del codice a comprendere il flusso del programma. Tendo a inserire le prime clausole di "bailout" all'inizio di una funzione per rifiutare rapidamente condizioni non valide, ma evitandole continuenei cicli; alla fine è una questione di leggibilità e stile sia in C ++ che in Python.

Usa strutture dati più efficienti

Ciò che era vero in C ++ funziona anche in Python. Possiamo usare le stesse idee e velocizzare il codice di un fattore 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 (e Python), ma personalmente trovo che questo sia un po '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}'

Stai usando un'espressione di assegnazione per assegnare un valore, ma poi la usi solo nel caso falso. Penso che questo sarebbe molto più pulito usando una semplice vecchia dichiarazione di assegnazione:

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}'

Non credo che la linea salvata valga la pena seppellire la creazione di una variabile.

Answer 3

C ++

È più semplice e forse più veloce passare piccoli tipi di dati semplici come size_te charper valore, non per riferimento. Quindi dovremmo avere:

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 = '.')

---

Ancora più importante: std::string_view non può essere utilizzato per memorizzare le stringhe. Non possiede la stringa, è solo un puntatore e una dimensione.

Facendo qualcosa di simile:

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

... costruiamo un temporaneo std::stringe poi lo assegniamo a un file string_view. Tuttavia, la stringa temporanea esce dall'ambito alla fine di questa riga!

È passato. Questa stringa non è più. Ha cessato di esistere. È scaduto ed è andato a incontrare il suo creatore. Questa è una stringa in ritardo. È un rigido. Privo di vita riposa in pace. Se non l'avessimo inchiodato a un std::string_view, starebbe spingendo verso l'alto le margherite. Ha calato il sipario e si è unito al coro invisibile. Questa è una ex stringa.

In altre parole, è un comportamento indefinito cercare di usarlo string_view. Quindi r, ce bdevono essere std::stringse stessi. E seendovrebbe essere un file std::unordered_set<std::string>.

---

Ri. std::string_view:

std::string_viewpunta a un intervallo di caratteri in memoria. Questi caratteri possono essere memorizzati in a std::string, in a std::array, a std::vectoro in una stringa letterale.

Usando std::string_viewotteniamo la stessa interfaccia (ricerca, confronto, creazione di sottostringhe) indipendentemente da quale sia lo storage sottostante. Quindi è utile come linguaggio comune tra questi tipi.

Poiché std::string_viewnon possiede i caratteri, non esegue l'allocazione della memoria o la copia da solo. Questo lo rende utile per cose come l'analisi di file di testo lunghi: possiamo cercare e confrontare nelle sottostringhe senza fare la copia che std::stringfarebbe.

Il compromesso è che dobbiamo garantire che la durata della stringa effettiva in memoria sia più lunga di quella del file string_view.