Java Data Structure in C++

[Shashank_Choudhary]

Can someone please help me write this piece of code in C++.
I think we can use std:::unordered_set<> but it doesn't work for me.

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

Thank you

 

[APalley]

unordered_set is the closest structure. What code did you try for that?

 

[Shashank_Choudhary]

unordered_set is the closest structure. What code did you try for that?

Hi Avi

Thank you for replying.
I tried the following ,

std::unordered_set<std::unordered_set<char>> rows(N) ;
       std::unordered_set<std::unordered_set<char>> cols(N) ;
       std::unordered_set<std::unordered_set<char>> boxes(N) ;
       for (int r = 0; r < 9 ; ++r)
       {
           rows.insert(std::unordered_set<char>(N));
           cols.insert(std::unordered_set<char>(N));
           boxes.insert(std::unordered_set<char>(N));
       }

and I get an error : call to implicitly deleted default contsructor.

Then I tried the following , (which works for std::vectors),

std::unordered_set<std::unordered_set<char>> rows(9,std::unordered_set<char>(9));

For which I get no matching constructor error !

 

[APalley]

It looks like you are trying to create a set of sets. The equivalent to your Java code would be a dynamic array of sets. I.e., using new with a shared_ptr.

 

[Daniel Duffy]

Can you explain/paraphrase the problem?
Nested ordered sets? Why?

 

[Shashank_Choudhary]

Can you explain/paraphrase the problem?
Nested ordered sets? Why?

Hi Daniel ,

I am trying to solving the "Valid Sudoku " problem on Leetcode and creating a hash set and iterating through the each element is one way to solve it (Official Solution). The posted solution uses the nested " Hash Set " DS in Java.

 

[Shashank_Choudhary]

It looks like you are trying to create a set of sets. The equivalent to your Java code would be a dynamic array of sets. I.e., using new with a shared_ptr.

Avi can you please help with the syntax? This is the final solution in Java .

class Solution {
    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>();
        }

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                char val = board[r][c];

                // Check if the position is filled with number
                if (val == '.') {
                    continue;
                }

                // Check the row
                if (rows[r].contains(val)) {
                    return false;
                }
                rows[r].add(val);

                // Check the column
                if (cols[c].contains(val)) {
                    return false;
                }
                cols[c].add(val);

                // Check the box
                int idx = (r / 3) * 3 + c / 3;
                if (boxes[idx].contains(val)) {
                    return false;
                }
                boxes[idx].add(val);
            }
        }
        return true;
    }
}

Thank you

 

[Daniel Duffy]

A wild guess might be to have a look at Boost Bimap for nested data structures (AFAIR it's in the ADV C++)

Chapter 1. Boost.Bimap - 1.78.0

www.boost.org

And maybe Multiindex

Boost.MultiIndex Documentation - Index - 1.78.0

www.boost.org

 

[APalley]

Avi can you please help with the syntax? This is the final solution in Java .

class Solution {
    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>();
        }

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                char val = board[r][c];

                // Check if the position is filled with number
                if (val == '.') {
                    continue;
                }

                // Check the row
                if (rows[r].contains(val)) {
                    return false;
                }
                rows[r].add(val);

                // Check the column
                if (cols[c].contains(val)) {
                    return false;
                }
                cols[c].add(val);

                // Check the box
                int idx = (r / 3) * 3 + c / 3;
                if (boxes[idx].contains(val)) {
                    return false;
                }
                boxes[idx].add(val);
            }
        }
        return true;
    }
}

Thank you

auto rows = std::make_shared<std::unordered_set<char>>(std::unordered_set<char>[])(N)

^^something like this

 

[Shashank_Choudhary]

A wild guess might be to have a look at Boost Bimap for nested data structures (AFAIR it's in the ADV C++)

Chapter 1. Boost.Bimap - 1.78.0

www.boost.org

And maybe Multiindex

Boost.MultiIndex Documentation - Index - 1.78.0

www.boost.org

I am sure it will work and yes we work worked with these libraries.
However since this is on the leetcode platform I don't think we can call boost libraries

 

[Shashank_Choudhary]

auto rows = std::make_shared<std::unordered_set<char>>(std::unordered_set<char>[])(N)

^^something like this

Hi Avi ,

I got the following error for the declaration above
Expected '(' for function-style cast or type construction
So I tried this form
auto rows = std::make_shared<std::unordered_set<char>(std::unordered_set<char>[])>(N);
For which I get a new error ,
/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX12.1.sdk/usr/include/c++/v1/memory:900:19: Multiple overloads of 'address' instantiate to the same signature 'std::allocator<std::unordered_set<char> (std::unordered_set<char> *)>::const_pointer (std::allocator<std::unordered_set<char> (std::unordered_set<char> *)>::const_reference) const noexcept' (aka 'std::unordered_set<char> (*(std::unordered_set<char> (&)(std::unordered_set<char> *)) const noexcept)(std::unordered_set<char> *)')

 

[Daniel Duffy]

why not try std:array<std::array<int, 9>, 9>

or even std:array<std::set<int>, 9>

Basing on Java (no stack) is that a good idea, It's a tiny matrix 9X9. Orginal hashset feels like a sledgehammer.
Defining a hast on an array of size 9?

 

[Daniel Duffy]

I am sure it will work and yes we work worked with these libraries.
However since this is on the leetcode platform I don't think we can call boost libraries

I was afraid about that

 

[Shashank_Choudhary]

why not try std:array<std::array<int, 9>, 9>

or even std:array<std::set<int>, 9>

Basing on Java (no stack) is that a good idea, It's a tiny matrix 9X9. Orginal hashset feels like a sledgehammer.
Defining a hast on an array of size 9?

Well , that's is OFFICIAL solution on Leetcode , maybe its faster (complexity is O(n^2)).
I will try your suggested data structure , thank you

 

[Daniel Duffy]

I would reckon for compile time arrays of size 9 that indexiing [] is as good (or even better) than hashimg (and less memory?)
And less programming.