Valid Sudoku - LeetCode

S

Shashank_Choudhary

C++ Certificate Advanced C++ Certificate
Joined
1/21/19
Messages
313
Points
138
Hi ,

I want to implement the JAVA solution to the valid sudoku problem on LeetCode in C++. It uses hashset<hashset> form . I understand std::unordered_set<std::unordered_set<int>> would be the ideal DS but I am struggling to default initialize it . You can see the snippet of the JAVA solution below ,
Java: 
public boolean isValidSudoku(char[][] board) {
        int N = 9;

        // Use hash set to record the status
        HashSet<Character>[] rows = new HashSet[N];
        HashSet<Character>[] cols = new HashSet[N];
        HashSet<Character>[] boxes = new HashSet[N];
        for (int r = 0; r < N; r++) {
            rows[r] = new HashSet<Character>();
            cols[r] = new HashSet<Character>();
            boxes[r] = new HashSet<Character>();
        }
        
        .....
        
        }

Any help would be much appreciated !
Thanks :)
 
What problems are you trying to solve?
Scary code and it is JAVA!!!!

The term cargo cult programmer may apply when anyone inexperienced with the problem at hand copies some program code from one place to another with little understanding of how it works or whether it is required.

Cargo cult programming - Wikipedia

en.wikipedia.org en.wikipedia.org

Of course, I might be missing some vital information.
 
Last edited:
Daniel Duffy said:
What problems are you trying to solve?
Scary code and it is JAVA!!!!

The term cargo cult programmer may apply when anyone inexperienced with the problem at hand copies some program code from one place to another with little understanding of how it works or whether it is required.

Cargo cult programming - Wikipedia

en.wikipedia.org en.wikipedia.org

Of course, I might be missing some vital information.
Click to expand...
This is the problem statement :
leetcode.com

LeetCode - The World's Leading Online Programming Learning Platform

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com

I realized I did start a thread when I solved this question for the first time using vectors Java Data Structure in C++
 
But I want to replicate the HashSet<> code above using unordered_set ...
This is one solution to the problem using vectors ,

C++: 
bool isValidSudoku(vector<vector<char>>& board)
    {
       int N = 9;
        std::vector<int> row(N);
        std::vector<int> col(N);
        std::vector<int> box(N);
        
      
        for(int r = 0; r < N ; ++r)
        {
            for(int c = 0; c < N ; ++c)
            {
                if(board[r][c] == '.')
                    continue;
                int val = board[r][c] - '0';
                int pos = 1 << (val -1);
                if((row[r] & pos) > 0)
                    return false;
                row[r] |= pos;
                    
                if((col[c] & pos) > 0)
                    return false;
                col[c] |= pos;
                    
                int idx = (r/3) * 3 + c/3;
                if((box[idx] & pos) > 0)
                    return false;
                box[idx] |= pos;
            }
        }
        
        return true;
    }
 
Shashank_Choudhary said:
This is the problem statement :
leetcode.com

LeetCode - The World's Leading Online Programming Learning Platform

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com

I realized I did start a thread when I solved this question for the first time using vectors Java Data Structure in C++
Click to expand...
The specification is ambiguous

1. Is Example 1 an example of a valid board?'OK, yes it is.

2. "Each row must contain the digits 1-9 without repetition."
is ambiguous

"Each row must contain non-repeating subset digits 1-9 without repetition. Blanks are alowed."
3. It is a compile-time matrix really, yes.

//

I would use a compile-time matrix based onn std::array<std::array<int, NCols>, NRows> + multithreadin environment, e.g.

A. 1 thread to process rows
B. 1 thread to process columns
C. 2(or 4?) to process sub-matrices

The final challenge is to check uniqueness. C++ has not std::is_unique but C++20 has std::unique_copy. Check sizes of original and "uniqued" containers.

// it's a great way to learn parallel programming, BTW. The pattern is called Geometric Decomposition.
 
Last edited:
Shashank_Choudhary said:
But I want to replicate the HashSet<> code above using unordered_set ...
This is one solution to the problem using vectors ,

C++: 
bool isValidSudoku(vector<vector<char>>& board)
    {
       int N = 9;
        std::vector<int> row(N);
        std::vector<int> col(N);
        std::vector<int> box(N);
  
 
        for(int r = 0; r < N ; ++r)
        {
            for(int c = 0; c < N ; ++c)
            {
                if(board[r][c] == '.')
                    continue;
                int val = board[r][c] - '0';
                int pos = 1 << (val -1);
                if((row[r] & pos) > 0)
                    return false;
                row[r] |= pos;
              
                if((col[c] & pos) > 0)
                    return false;
                col[c] |= pos;
              
                int idx = (r/3) * 3 + c/3;
                if((box[idx] & pos) > 0)
                    return false;
                box[idx] |= pos;
            }
        }
  
        return true;
    }
Click to expand...
I don't see why you need those 3 vectors row, col, box. They are just views of board.
And where are they initialised?

maybe std::array better than std::vector here?

// the original Java HashSet is so wrong. And "char"....
 
Last edited:
Analogy

The Ariane 5 reused the code from the inertial reference platform from the Ariane 4, but the early part of the Ariane 5's flight path differed from the Ariane 4 in having higher horizontal velocity values. This caused an internal value BH (Horizontal Bias) calculated in the alignment function to be unexpectedly high.
 
Shashank_Choudhary said:
I believe we don’t need ordering here thats why I chose unordered_set .. also its very frustrating that these websites don’t provide C++ solutions . I have premium membership still all the questions have Java/Python implementation!
Click to expand...
In the old days there were no sites, so you had to do it yourself.
We are in a new phase of software ... the copy and paste generation.

I have heard this criticism from at least 6 experienced project leaders /architects in the last months. It's a big problem.

I give my first face-to-face course in 3 years (there was a lockdown you know) and I experienced it first-hand.

The focus is rather skewed at the moment.

Just a remark.
 
Last edited:
Daniel Duffy said:
In the old days there were no sites, so you had to do it yourself.
We are in a new phase of software ... the copy and paste generation.

I have heard this criticism from at least 6 experienced project leaders /architects in the last months. It's a big problem.

I give my first face-to-face course in 3 years (there was a lockdown you know) and I experienced it first-hand.

The focus is rather skewed at the moment.

Just a remark.
Click to expand...
So what would be your recommendation ? Should I pickup a standard Algorithms book like Introduction to Algorithms by Cormen (used at MIT) and try to implement solutions from scratch. You are absolutely right about the "copy paste" culture !!
I am doing this as part of my quant trader/developer job interview prep. I manage to solve the pure C++ questions, thanks to your courses here on Quantnet :) but I struggle with Algorithms ..
 
Shashank_Choudhary said:
So what would be your recommendation ? Should I pickup a standard Algorithms book like Introduction to Algorithms by Cormen (used at MIT) and try to implement solutions from scratch. You are absolutely right about the "copy paste" culture !!
I am doing this as part of my quant trader/developer job interview prep. I manage to solve the pure C++ questions, thanks to your courses here on Quantnet :) but I struggle with Algorithms ..
Click to expand...

Doing/knowing algorithms is important. Why not start with 1) understanding and b) applying industry standard STL algorithms. Use them on a need-be basis.

Writing your own b-tree ADT is nice but very 90s. Leave it to C++ and other experts, just like we don't (usually) write our own matrix solvers.

I haven't given an algo course since late 1990s.

Better to learn how to write maintainable code. Desing Patterns are good, if done correctly.

And LOTS of real programming.
 
Last edited:
Daniel Duffy said:
Doing/knowing algorithms is important. Why not start with 1) understanding and b) applying industry standard STL algorithms. Use them on a need-be basis.

Writing your own b-tree ADT is nice but very 90s. Leave it to C++ and other experts, just like we don't (usually) write our own matrix solvers.

I haven't given an algo course since late 1990s.

Better to learn how to write maintainable code. Desing Patterns are good, if done correctly.

And LOTS of real programming.
Click to expand...
Thank you :)
I guess all of this I can follow this if I work on a project . I am exploring a few ideas , hopefully I will find something interesting this summer !!
 

Similar threads

S
Java Data Structure in C++
Replies
14
Views
3K
Daniel Duffy
Daniel Duffy
I
Team Blind 75 leetcode questions - relevance?
Replies
1
Views
8K
auroreaborealis
A
T
Is there a "LeetCode" type website for math & prob brain teasers?
Replies
3
Views
4K
Daniel Duffy
Daniel Duffy
Back
Top Bottom