text:
import sudsoln.candidate as candidate
import sudsoln.sarray as sarray

class Sudoku():
    '''Sudoku puzzle.'''

    def __init__(self, array, empty = '.', elements = None):
        '''(Sudoku, 2d-array of object, str[, {objects}]) -> None

        Precondition:
        1. each element in elements is of length 1 if specified.
        2. (elements is None) or (len(elements) >= 4)
        3. len(empty) == 1

        Initialize Sudoku puzzle.

        >>> q_small = [  # not a np.array, but acceptable
        ...        ['1', '.', '3', '.'],
        ...        ['.', '2', '.', '.'],
        ...        ['.', '.', '.', '.'],
        ...        ['.', '.', '.', '4']
        ... ]
        ...
        >>> q_small = Sudoku(q_small)
        >>> q_small.n
        2
        >>> question1 = [  # mixture of int and str, and not a np.array
        ...     ['.', '.', '.', '.',   2, '.', '.', '.', '.'],
        ...     [  8,   3, '.',   7,   1,   4, '.',   9,   6],
        ...     ['.',   6, '.',   9, '.',   5,   4, '.',   8],
        ...     ['.',   9, '.',   3, '.',   1, '.', '.',   4],
        ...     ['.',   1, '.',   4, '.',   2, '.', '.',   7],
        ...     ['.',   7,   5, '.', '.', '.',   2,   1, '.'],
        ...     ['.', '.',   4, '.', '.', '.',   7, '.', '.'],
        ...     ['.', '.', '.',   5, '.',   7, '.', '.', '.'],
        ...     ['.', '.', '.',   1,   9,   6, '.', '.', '.']
        ... ]
        ...
        >>> q1 = Sudoku(question1)
        >>> q1.n
        3
        >>> question_big = [
        ...     ['1', '6', 'F', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', 'E', 'G', '7'],
        ...     ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', 'D', '3', 'A', 'F', '8', '.'],
        ...     ['.', '.', '.', '.', '.', '.', '.', 'E', 'B', '5', 'C', 'G', '.', '.', '.', '.'],
        ...     ['.', '.', '.', '.', '.', 'G', '3', 'D', 'A', '1', '.', '.', '.', '.', 'C', '2'],
        ...     ['3', '9', '8', '.', '.', '.', '.', '.', '.', '.', '.', '.', '5', '1', 'B', 'G'],
        ...     ['B', '.', '.', '.', '.', '.', '.', '.', '.', '.', 'E', '6', 'F', '2', 'A', '.'],
        ...     ['.', '.', '.', 'C', '.', '.', '9', 'A', '8', '7', 'B', '2', '.', '.', '.', '.'],
        ...     ['.', 'A', '1', 'E', '.', 'D', '6', 'C', '5', '3', '.', '.', '.', '.', '.', '4'],
        ...     ['F', 'B', '4', '8', '.', '.', '.', '.', '.', '.', '.', '.', '1', '7', 'E', '3'],
        ...     ['C', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '8', 'D', '4', '.', '.'],
        ...     ['.', '.', '.', '.', '.', '1', '.', 'G', '3', 'D', '6', '4', '.', '.', '.', '.'],
        ...     ['.', '.', '.', '.', '.', '3', '8', 'F', '7', 'C', '5', '.', '.', '.', '2', '9'],
        ...     ['G', '4', 'D', 'B', '.', '.', '.', '.', '.', '.', '.', '.', '2', '9', 'F', '5'],
        ...     ['.', '.', '.', '.', '.', '.', '.', '4', '.', '.', '7', 'D', 'E', '6', '.', '.'],
        ...     ['.', '.', '.', '.', '.', '.', '2', '5', 'C', 'G', '8', 'E', '7', '.', '.', '.'],
        ...     ['.', '.', '.', '2', '.', '.', 'A', '1', '9', 'F', '.', '.', '.', '.', '3', '8']
        ... ]
        ...
        >>> q_big = Sudoku(question_big)
        >>> q_big.n
        4
        '''

        # Array type and shape
        if type(array) == str:
            raise TypeError(
                'String object is not acceptable. If you want to ' +\
                'convert a string representation of Sudoku to ' +\
                'Sudoku object, use ' +\
                'sudsoln.to_sudoku(sudoku_str, elements, empty) ' +\
                'instead.'
            )
        array = sarray.Array(array)
        if len(set(array.shape)) != 1:
            raise ValueError(
                'The shape of array must be square, ' +\
                'i.e. number of rows must be equal to number of columns.'
            )

        # Size
        n = list(set(array.shape))[0] ** .5
        if n < 2:
            raise ValueError(
                'The number of rows of array is too small; ' +\
                'it has to be at least 4.'
            )
        if int(n) != n:
            raise ValueError(
                'The number of rows of array is not compatible ' +\
                'for Sudoku puzzle; it has to be a square ' +\
                'of some integer, e.g. 9 = 3 ** 2, 16 = 4 ** 2, etc.'
            )

        # elements and empty
        if type(empty) != str:
            raise TypeError('empty must be of type str.')
        if len(empty) != 1:
            raise ValueError('Length of empty must be 1.')
        if elements is None:
            elements = set(array.flatten())
            if empty not in elements:
                try: # assuming it is already an answer
                    Sudoku(
                        array = array,
                        elements = elements,
                        empty = empty
                    )
                except ValueError:
                    # It isn't in its answer form.
                    # i.e. wrong specification of empty
                    raise KeyError(
                        "empty = '" + empty + "'" + " does not exist " +\
                        "in the array. Either specify the correct " +\
                        "string denoting the emptiness in the array, " +\
                        "or change the string denoting the emptiness " +\
                        "in the array by using " +\
                        "sudsoln.change_empty(array, old, new)."
                    )
            else:
                elements.remove(empty)
            if len(elements) != n ** 2:
                raise ValueError(
                    'Length of the guessed elements is ' +\
                    str(len(elements)) + ', not ' + str(int(n ** 2)) +\
                    '. Either make sure that: ' +\
                    '1. every element in the current array contains ' +\
                    'all of your intended elements at least once, or; ' +\
                    '2. specify elements explicitly, or; ' +\
                    '3. there is exactly one string, and only one, ' +\
                    'that denotes the emptiness in the array. ' +\
                    'For example, if you try to solve a 9-by-9 sudoku ' +\
                    'whose answer form consists of integers from 1 to ' +\
                    '9, either make sure that every integer from 1 to ' +\
                    '9 shows up in the current array at least once, ' +\
                    'or explicitly specify elements = set([str(i) for ' +\
                    'i in range(1, 10)]), or see if the array uses ' +\
                    "'.' and some other string, like ',' or ' ',  to " +\
                    'denote the emptiness.'
                )
        else:
            elements = set([str(item) for item in list(elements)])
        el_test = set(array.flatten()).difference(elements.union({empty}))
        if el_test != set():
            raise ValueError(
                'There exists an element in array that is not ' +\
                'a member of elements: ' + str(el_test)
            )
        if len(elements) != n ** 2:
            raise ValueError(
                'The number of elements in elements must be ' +\
                str(int(n ** 2)) + ', not ' + str(len(elements)) + '.'
            )

        self.show = array
        self.n = int(n)
        self.elements = elements
        self.empty = empty

    def __eq__(self, other):
        '''(Sudoku, Sudoku) -> bool

        Return True iff all the entries of self and other are the same.
        '''

        return self.show == other.show

    def __getitem__(self, key):
        '''(Sudoku, ints/lists/slices/tuples) -> str or Array

        Return the entry of self at key.

        >>> import sudsoln.questions as sq
        >>> q1 = to_sudoku(sq.q1)
        >>> q1
        Sudoku(
            .    .    .    |    .    2    .    |    .    .    .
            8    3    .    |    7    1    4    |    .    9    6
            .    6    .    |    9    .    5    |    4    .    8
        -------------------+-------------------+-------------------
            .    9    .    |    3    .    1    |    .    .    4
            .    1    .    |    4    .    2    |    .    .    7
            .    7    5    |    .    .    .    |    2    1    .
        -------------------+-------------------+-------------------
            .    .    4    |    .    .    .    |    7    .    .
            .    .    .    |    5    .    7    |    .    .    .
            .    .    .    |    1    9    6    |    .    .    .
        n: 3
        elements: 1, 2, 3, 4, 5, 6, 7, 8, 9
        empty: .
        )
        >>> q1[(0, 0)]
        '.'
        >>> q1[(2, 1)]
        '6'
        '''

        return self.show[key]

    def __repr__(self):
        '''(Sudoku) -> Sudoku

        Return the Sudoku representation of self.

        >>> import sudsoln.questions as sq
        >>> q1 = to_sudoku(sq.q1)
        >>> q1
        Sudoku(
            .    .    .    |    .    2    .    |    .    .    .
            8    3    .    |    7    1    4    |    .    9    6
            .    6    .    |    9    .    5    |    4    .    8
        -------------------+-------------------+-------------------
            .    9    .    |    3    .    1    |    .    .    4
            .    1    .    |    4    .    2    |    .    .    7
            .    7    5    |    .    .    .    |    2    1    .
        -------------------+-------------------+-------------------
            .    .    4    |    .    .    .    |    7    .    .
            .    .    .    |    5    .    7    |    .    .    .
            .    .    .    |    1    9    6    |    .    .    .
        n: 3
        elements: 1, 2, 3, 4, 5, 6, 7, 8, 9
        empty: .
        )
        >>> q_big = to_sudoku(sq.q7)
        >>> q_big
        Sudoku(
            1    6    F    .    |    .    .    .    .    |    .    .    .    .    |    .    E    G    7
            .    .    .    .    |    .    .    .    .    |    .    .    D    3    |    A    F    8    .
            .    .    .    .    |    .    .    .    E    |    B    5    C    G    |    .    .    .    .
            .    .    .    .    |    .    G    3    D    |    A    1    .    .    |    .    .    C    2
        ------------------------+------------------------+------------------------+------------------------
            3    9    8    .    |    .    .    .    .    |    .    .    .    .    |    5    1    B    G
            B    .    .    .    |    .    .    .    .    |    .    .    E    6    |    F    2    A    .
            .    .    .    C    |    .    .    9    A    |    8    7    B    2    |    .    .    .    .
            .    A    1    E    |    .    D    6    C    |    5    3    .    .    |    .    .    .    4
        ------------------------+------------------------+------------------------+------------------------
            F    B    4    8    |    .    .    .    .    |    .    .    .    .    |    1    7    E    3
            C    .    .    .    |    .    .    .    .    |    .    .    .    8    |    D    4    .    .
            .    .    .    .    |    .    1    .    G    |    3    D    6    4    |    .    .    .    .
            .    .    .    .    |    .    3    8    F    |    7    C    5    .    |    .    .    2    9
        ------------------------+------------------------+------------------------+------------------------
            G    4    D    B    |    .    .    .    .    |    .    .    .    .    |    2    9    F    5
            .    .    .    .    |    .    .    .    4    |    .    .    7    D    |    E    6    .    .
            .    .    .    .    |    .    .    2    5    |    C    G    8    E    |    7    .    .    .
            .    .    .    2    |    .    .    A    1    |    9    F    .    .    |    .    .    3    8
        n: 4
        elements: 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, G
        empty: .
        )
        '''

        n = self.n
        headline, endline = 'Sudoku(\n', ')'
        midline = ''
        sep = '-----' * n + '----'
        sepline = (sep + '+') * (n - 1) + sep + '\n'
        str_self = str(self) # This is why each element has to be len 1
        j = 0
        for ind in range(0, len(str_self), n ** 2):
            j += 1
            str_row = list(str_self[ind:(ind + n ** 2)])
            for i in range(len(str_row)):
                if i != 0 and i % n == 0:
                    midline += '    |    ' + str_row[i]
                elif i == len(str_row) - 1:
                    if j % n != 0 or j == n ** 2:
                        midline += '    ' + str_row[i] + '\n'
                    else:
                        midline += '    ' + str_row[i] + '\n' + sepline
                else:
                    midline += '    ' + str_row[i]
        subsize = 'n: ' + str(self.n) + '\n'
        lst_els = list(self.elements)
        lst_els.sort()
        els = 'elements: '
        for item in enumerate(lst_els):
            if item[0] != len(lst_els) - 1:
                els += item[1] + ', '
            else:
                els += item[1] + '\n'
        emp = 'empty: ' + self.empty + '\n'
        return headline + midline + subsize + els + emp + endline

    def __setitem__(self, key, value):
        '''(Sudoku, (int, int), int/str) -> None

        Assign value to self's key.

        >>> import sudsoln.questions as sq
        >>> q1 = to_sudoku(sq.q1)
        >>> q1
        Sudoku(
            .    .    .    |    .    2    .    |    .    .    .
            8    3    .    |    7    1    4    |    .    9    6
            .    6    .    |    9    .    5    |    4    .    8
        -------------------+-------------------+-------------------
            .    9    .    |    3    .    1    |    .    .    4
            .    1    .    |    4    .    2    |    .    .    7
            .    7    5    |    .    .    .    |    2    1    .
        -------------------+-------------------+-------------------
            .    .    4    |    .    .    .    |    7    .    .
            .    .    .    |    5    .    7    |    .    .    .
            .    .    .    |    1    9    6    |    .    .    .
        n: 3
        elements: 1, 2, 3, 4, 5, 6, 7, 8, 9
        empty: .
        )
        >>> q1[(0, 0)] = 5
        >>> q1[(8, 8)] = '5'
        >>> q1
        Sudoku(
            5    .    .    |    .    2    .    |    .    .    .
            8    3    .    |    7    1    4    |    .    9    6
            .    6    .    |    9    .    5    |    4    .    8
        -------------------+-------------------+-------------------
            .    9    .    |    3    .    1    |    .    .    4
            .    1    .    |    4    .    2    |    .    .    7
            .    7    5    |    .    .    .    |    2    1    .
        -------------------+-------------------+-------------------
            .    .    4    |    .    .    .    |    7    .    .
            .    .    .    |    5    .    7    |    .    .    .
            .    .    .    |    1    9    6    |    .    .    5
        n: 3
        elements: 1, 2, 3, 4, 5, 6, 7, 8, 9
        empty: .
        )
        '''

        self.show[key] = value

    def __str__(self):
        '''(Sudoku) -> str

        Return the string representation of self.

        >>> import sudsoln.questions as sq
        >>> q1 = to_sudoku(sq.q1)
        >>> str(q1)
        '....2....83.714.96.6.9.54.8.9.3.1..4.1.4.2..7.75...21...4...7.....5.7......196...'
        >>> q1.solve_logically()
        >>> str(q1)
        '549628371832714596761935428298371654613452987475869213154283769986547132327196845'
        '''

        result = ''
        for item in self.show.flatten():
            result += item
        return result

    def all_missings(self):
        '''(Sudoku) -> {str: {int: set of str}}

        Return all missing values of all submatrices, rows, and columns
        of self.

        >>> import sudsoln.questions as sq
        >>> q1 = to_sudoku(sq.q1)
        >>> q1
        Sudoku(
            .    .    .    |    .    2    .    |    .    .    .
            8    3    .    |    7    1    4    |    .    9    6
            .    6    .    |    9    .    5    |    4    .    8
        -------------------+-------------------+-------------------
            .    9    .    |    3    .    1    |    .    .    4
            .    1    .    |    4    .    2    |    .    .    7
            .    7    5    |    .    .    .    |    2    1    .
        -------------------+-------------------+-------------------
            .    .    4    |    .    .    .    |    7    .    .
            .    .    .    |    5    .    7    |    .    .    .
            .    .    .    |    1    9    6    |    .    .    .
        n: 3
        elements: 1, 2, 3, 4, 5, 6, 7, 8, 9
        empty: .
        )
        >>> q1.all_missings() == {
        ...     'submatrix': {
        ...         1: {'9', '7', '1', '2', '5', '4'},
        ...         2: {'3', '6', '8'},
        ...         3: {'7', '1', '2', '5', '3'},
        ...         4: {'8', '2', '3', '6', '4'},
        ...         5: {'9', '7', '8', '5', '6'},
        ...         6: {'9', '8', '5', '3', '6'},
        ...         7: {'9', '7', '1', '8', '2', '5', '3', '6'},
        ...         8: {'2', '3', '4', '8'},
        ...         9: {'9', '1', '8', '2', '5', '3', '6', '4'}
        ...     },
        ...     'row': {
        ...         0: {'9', '7', '1', '8', '5', '3', '6', '4'},
        ...         1: {'2', '5'},
        ...         2: {'3', '7', '2', '1'},
        ...         3: {'7', '8', '2', '5', '6'},
        ...         4: {'9', '8', '5', '3', '6'},
        ...         5: {'9', '8', '3', '6', '4'},
        ...         6: {'9', '1', '8', '2', '5', '3', '6'},
        ...         7: {'9', '1', '8', '2', '3', '6', '4'},
        ...         8: {'7', '8', '2', '5', '3', '4'}
        ...     },
        ...     'col': {
        ...         0: {'9', '7', '1', '2', '5', '3', '6', '4'},
        ...         1: {'2', '5', '4', '8'},
        ...         2: {'9', '7', '1', '8', '2', '3', '6'},
        ...         3: {'2', '6', '8'},
        ...         4: {'7', '8', '5', '3', '6', '4'},
        ...         5: {'9', '3', '8'},
        ...         6: {'9', '1', '8', '5', '3', '6'},
        ...         7: {'7', '8', '2', '5', '3', '6', '4'},
        ...         8: {'9', '1', '2', '5', '3'}
        ...     }
        ... }
        ...
        True
        '''

        n = self.n
        result = {'submatrix': {}, 'row': {}, 'col': {}}
        for i in range(n ** 2):
            result['submatrix'].update({i + 1: self.missing(s = i + 1)})
            result['row'].update({i: self.missing(r = i)})
            result['col'].update({i: self.missing(c = i)})
        return result

    def candidates(self):
        '''(Sudoku) -> Candidate

        Return all numbers that can be entered at each entry of self
        if that entry is self.empty.

        >>> import sudsoln.questions as sq
        >>> q6 = to_sudoku(sq.q6)
        >>> q6
        Sudoku(
            .    3    |    .    4
            .    .    |    .    .
        --------------+--------------
            .    .    |    1    .
            2    .    |    .    .
        n: 2
        elements: 1, 2, 3, 4
        empty: .
        )
        >>> q6.candidates() == candidate.Candidate(
        ...     {
        ...         (0, 0): {'1'},
        ...         (0, 2): {'2'},
        ...         (1, 0): {'1', '4'},
        ...         (1, 1): {'1', '2', '4'},
        ...         (1, 2): {'2', '3'},
        ...         (1, 3): {'1', '2', '3'},
        ...         (2, 0): {'4', '3'},
        ...         (2, 1): {'4'},
        ...         (2, 3): {'2', '3'},
        ...         (3, 1): {'1', '4'},
        ...         (3, 2): {'4', '3'},
        ...         (3, 3): {'3'}
        ...     },
        ...     elements = {1, 2, 3, 4}
        ... )
        ...
        True
        '''

        n = self.n
        empty = self.empty
        elements = self.elements
        entries = {}
        for i in range(1, n ** 2, n): # e.g. n == 3 => 1, 4, 7
            subm, subm_missing = {}, {}
            for j in range(n): # define submatrices first
                subm[i + j] = self.submatrix(i + j)
                subm_missing[i + j] = self.missing(s = i + j)
            for K in range(n): # iterate over rows of a binded submatrix
                row_missing = self.missing(r = i + K - 1)
                subm_index = 0
                col_iters = list(range(n - 1, n ** 2, n))
                for L in range(n ** 2): # iterate over columns
                    if self.show[(i + K - 1, L)] == empty:
                        col_missing = self.missing(c = L)
                        entries[(i + K - 1, L)] =\
                            subm_missing[i + subm_index].intersection(\
                                row_missing, col_missing
                            )
                    if L == col_iters[subm_index]:
                        subm_index += 1
        return candidate.Candidate(entries, elements = elements)

    def col(self, c):
        '''(Sudoku, int) -> Array

        Precondition: 0 <= c <= self.n ** 2 - 1

        Return one of self.n ** 2 columns of self selected by c.

        >>> import sudsoln.questions as sq
        >>> q1 = to_sudoku(sq.q1)
        >>> q1
        Sudoku(
            .    .    .    |    .    2    .    |    .    .    .
            8    3    .    |    7    1    4    |    .    9    6
            .    6    .    |    9    .    5    |    4    .    8
        -------------------+-------------------+-------------------
            .    9    .    |    3    .    1    |    .    .    4
            .    1    .    |    4    .    2    |    .    .    7
            .    7    5    |    .    .    .    |    2    1    .
        -------------------+-------------------+-------------------
            .    .    4    |    .    .    .    |    7    .    .
            .    .    .    |    5    .    7    |    .    .    .
            .    .    .    |    1    9    6    |    .    .    .
        n: 3
        elements: 1, 2, 3, 4, 5, 6, 7, 8, 9
        empty: .
        )
        >>> q1.col(3).flatten()
        ['.', '7', '9', '3', '4', '.', '.', '5', '1']
        '''

        return self.show[:, c]

    def copy(self):
        '''(Sudoku) -> Sudoku

        Return a deep copy of self.

        >>> import sudsoln.questions as sq
        >>> q1 = to_sudoku(sq.q1)
        >>> q1_cp = q1.copy()
        >>> q1_cp == q1
        True
        >>> id(q1_cp) != id(q1)
        True
        >>> q1_cp[0, 0] = 5
        >>> q1_cp.row(0)
        Array([
        ['5', '.', '.', '.', '2', '.', '.', '.', '.']
        ])
        >>> q1.row(0)
        Array([
        ['.', '.', '.', '.', '2', '.', '.', '.', '.']
        ])
        '''

        puzzle_copy = self.show.copy()
        return Sudoku(
            puzzle_copy,
            elements = self.elements,
            empty = self.empty
        )

    def group(self, by):
        '''(Sudoku, str) -> {int: Candidate}

        Precondition: by in ['submatrix', 'row', 'col']

        Return the candidate values grouped by 'by', which is either
        'submatrix', 'row', or 'col'.

        >>> import sudsoln.questions as sq
        >>> q6 = to_sudoku(sq.q6)
        >>> q6
        Sudoku(
            .    3    |    .    4
            .    .    |    .    .
        --------------+--------------
            .    .    |    1    .
            2    .    |    .    .
        n: 2
        elements: 1, 2, 3, 4
        empty: .
        )
        >>> q6.group(by = 'submatrix') == {
        ...     1: candidate.Candidate(
        ...         {
        ...             (0, 0): {'1'},
        ...             (1, 0): {'4', '1'},
        ...             (1, 1): {'4', '2', '1'}
        ...         },
        ...         elements = {1, 2, 3, 4}
        ...     ),
        ...     2: candidate.Candidate(
        ...         {
        ...             (0, 2): {'2'},
        ...             (1, 2): {'3', '2'},
        ...             (1, 3): {'3', '2', '1'}
        ...         },
        ...         elements = {1, 2, 3, 4}
        ...     ),
        ...     3: candidate.Candidate(
        ...         {
        ...             (2, 0): {'3', '4'},
        ...             (2, 1): {'4'},
        ...             (3, 1): {'4', '1'}
        ...         },
        ...         elements = {1, 2, 3, 4}
        ...     ),
        ...     4: candidate.Candidate(
        ...         {
        ...             (2, 3): {'3', '2'},
        ...             (3, 2): {'3', '4'},
        ...             (3, 3): {'3'}
        ...         },
        ...         elements = {1, 2, 3, 4}
        ...     )
        ... }
        ...
        True
        >>> q6.group(by = 'row') == {
        ...     0: candidate.Candidate(
        ...         {
        ...             (0, 0): {'1'},
        ...             (0, 2): {'2'}
        ...         },
        ...         elements = {1, 2, 3, 4}
        ...     ),
        ...     1: candidate.Candidate(
        ...         {
        ...             (1, 0): {'4', '1'},
        ...             (1, 1): {'4', '2', '1'},
        ...             (1, 2): {'3', '2'},
        ...             (1, 3): {'3', '2', '1'}
        ...         },
        ...         elements = {1, 2, 3, 4}
        ...     ),
        ...     2: candidate.Candidate(
        ...         {
        ...             (2, 0): {'3', '4'},
        ...             (2, 1): {'4'},
        ...             (2, 3): {'3', '2'}
        ...         },
        ...         elements = {1, 2, 3, 4}
        ...     ),
        ...     3: candidate.Candidate(
        ...         {
        ...             (3, 1): {'4', '1'},
        ...             (3, 2): {'3', '4'},
        ...             (3, 3): {'3'}
        ...         },
        ...         elements = {1, 2, 3, 4}
        ...     )
        ... }
        ...
        True
        >>> q6.group(by = 'col') == {
        ...     0: candidate.Candidate(
        ...         {
        ...             (0, 0): {'1'},
        ...             (1, 0): {'4', '1'},
        ...             (2, 0): {'3', '4'}
        ...         },
        ...         elements = {1, 2, 3, 4}
        ...     ),
        ...     1: candidate.Candidate(
        ...         {
        ...             (1, 1): {'4', '2', '1'},
        ...             (2, 1): {'4'},
        ...             (3, 1): {'4', '1'}
        ...         },
        ...         elements = {1, 2, 3, 4}
        ...     ),
        ...     2: candidate.Candidate(
        ...         {
        ...             (0, 2): {'2'},
        ...             (1, 2): {'3', '2'},
        ...             (3, 2): {'3', '4'}
        ...         },
        ...         elements = {1, 2, 3, 4}
        ...     ),
        ...     3: candidate.Candidate(
        ...         {
        ...             (1, 3): {'3', '2', '1'},
        ...             (2, 3): {'3', '2'},
        ...             (3, 3): {'3'}
        ...         },
        ...         elements = {1, 2, 3, 4}
        ...     )
        ... }
        ...
        True
        '''

        if by not in ['submatrix', 'row', 'col']:
            raise ValueError(
                "by must be either 'submatrix', 'row', or 'col'."
            )
        return self.candidates().group(by)

    def is_valid_answer(self):
        '''(Sudoku) -> bool

        Return True iff self is a valid sudoku answer, and False otherwise.

        >>> q_small = [
        ...     [  1, '.',   3, '.'],
        ...     ['.',   2, '.', '.'],
        ...     ['.', '.', '.', '.'],
        ...     ['.', '.', '.',   4]
        ... ]
        ...
        >>> q_small = Sudoku(q_small)
        >>> q_small
        Sudoku(
            1    .    |    3    .
            .    2    |    .    .
        --------------+--------------
            .    .    |    .    .
            .    .    |    .    4
        n: 2
        elements: 1, 2, 3, 4
        empty: .
        )
        >>> q_small.is_valid_answer()
        False
        >>> q_small.solve_logically()
        >>> q_small
        Sudoku(
            1    4    |    3    2
            3    2    |    4    1
        --------------+--------------
            4    1    |    2    3
            2    3    |    1    4
        n: 2
        elements: 1, 2, 3, 4
        empty: .
        )
        >>> q_small.is_valid_answer()
        True
        '''

        n = self.n
        empty = self.empty
        elements = self.elements
        if empty in self.show.flatten(): # not even finished yet
            return False
        for i in range(n ** 2):
            if elements != set(self.submatrix(i + 1).flatten()):
                return False
            elif elements != set(self.row(i).flatten()):
                return False
            elif elements != set(self.col(i).flatten()):
                return False
        return True

    def itemset(self, entry, value):
        '''(Sudoku, (int, int), int/str) -> None

        Precondition:
        1. value in self.elements
        2. each int in entry is from 0 to self.n ** 2 - 1 inclusive.

        Mutate entry number of self to value.

        >>> q_small = [
        ...     [  1, '.',   3, '.'],
        ...     ['.',   2, '.', '.'],
        ...     ['.', '.', '.', '.'],
        ...     ['.', '.', '.',   4]
        ... ]
        ...
        >>> q_small = Sudoku(q_small)
        >>> q_small
        Sudoku(
            1    .    |    3    .
            .    2    |    .    .
        --------------+--------------
            .    .    |    .    .
            .    .    |    .    4
        n: 2
        elements: 1, 2, 3, 4
        empty: .
        )
        >>> q_small.itemset((0, 1), 4)
        >>> q_small
        Sudoku(
            1    4    |    3    .
            .    2    |    .    .
        --------------+--------------
            .    .    |    .    .
            .    .    |    .    4
        n: 2
        elements: 1, 2, 3, 4
        empty: .
        )
        '''

        self.show.itemset(entry, value)

    def itemsets(self, entries):
        '''(Sudoku, Candidate or {(int, int): set of ints/strs}) -> None

        Precondition: each int in entries is exactly one element of
        self.elements.

        Mutate entry number of self according to values given in entries
        if the value set has length 1.

        >>> q_small = [
        ...     [  1, '.',   3, '.'],
        ...     ['.',   2, '.', '.'],
        ...     ['.', '.', '.', '.'],
        ...     ['.', '.', '.',   4]
        ... ]
        ...
        >>> q_small = Sudoku(q_small, elements = {'1', '2', '3', '4'})
        >>> candids = q_small.candidates()
        >>> candids == candidate.Candidate(
        ...     {
        ...         (0, 1): {'4'},
        ...         (0, 3): {'2'},
        ...         (1, 0): {'3', '4'},
        ...         (1, 2): {'1', '4'},
        ...         (1, 3): {'1'},
        ...         (2, 0): {'3', '2', '4'},
        ...         (2, 1): {'3', '1', '4'},
        ...         (2, 2): {'1', '2'},
        ...         (2, 3): {'3', '1', '2'},
        ...         (3, 0): {'3', '2'},
        ...         (3, 1): {'3', '1'},
        ...         (3, 2): {'1', '2'}
        ...     },
        ...     elements = {1, 2, 3, 4}
        ... )
        ...
        True
        >>> q_small
        Sudoku(
            1    .    |    3    .
            .    2    |    .    .
        --------------+--------------
            .    .    |    .    .
            .    .    |    .    4
        n: 2
        elements: 1, 2, 3, 4
        empty: .
        )
        >>> q_small.itemsets(candids)
        >>> q_small
        Sudoku(
            1    4    |    3    2
            .    2    |    .    1
        --------------+--------------
            .    .    |    .    .
            .    .    |    .    4
        n: 2
        elements: 1, 2, 3, 4
        empty: .
        )
        '''

        if type(entries) == dict:
            if entries == {}:
                return None
            for entry, values in entries.items():
                if len(values) == 1:
                    self.itemset(entry, list(values)[0])
        elif 'Candidate' in str(type(entries)):
            elements = self.elements
            if entries == candidate.Candidate({}, elements = elements):
                return None
            for entry, values in entries.items():
                if len(values) == 1:
                    self.itemset(entry, list(values)[0])

    def melt(self, include_empty = True):
        '''(Sudoku, bool) -> Candidate

        Return Candidate form of self, and include empty entries
        as well if include_empty is True (by default).

        >>> import numpy as np
        >>> q_small = np.array([
        ...     [  1, '.',   3, '.'],
        ...     ['.',   2, '.', '.'],
        ...     ['.', '.', '.', '.'],
        ...     ['.', '.', '.',   4]
        ... ])
        ...
        >>> q_small = Sudoku(q_small)
        >>> q_small.melt() == candidate.Candidate(
        ... {
        ...     (0, 0): {'1'}, (0, 1): {'.'}, (0, 2): {'3'}, (0, 3): {'.'},
        ...     (1, 0): {'.'}, (1, 1): {'2'}, (1, 2): {'.'}, (1, 3): {'.'},
        ...     (2, 0): {'.'}, (2, 1): {'.'}, (2, 2): {'.'}, (2, 3): {'.'},
        ...     (3, 0): {'.'}, (3, 1): {'.'}, (3, 2): {'.'}, (3, 3): {'4'}
        ... },
        ... elements = {1, 2, 3, 4}
        ... )
        ...
        True
        >>> q_small.melt(include_empty = False) == candidate.Candidate(
        ... {
        ...     (0, 0): {'1'}, (0, 2): {'3'}, (1, 1): {'2'}, (3, 3): {'4'}
        ... },
        ... elements = {1, 2, 3, 4}
        ... )
        ...
        True
        '''

        n = self.n
        empty = self.empty
        result = {}
        for i in range(n ** 2):
            for j in range(n ** 2):
                result[(i, j)] = {self.show[(i, j)]}
        if not include_empty:
            result_copy = result.copy()
            for k, v in result_copy.items():
                if list(v)[0] == empty:
                    result.pop(k)
        return candidate.Candidate(result, elements = self.elements)

    def missing(self, s = None, r = None, c = None):
        '''(Sudoku[, int, int, int]) -> set of str

        Precondition:
        1. 1 <= s <= self.n ** 2
        2. 0 <= r <= self.n ** 2 - 1
        3. 0 <= c <= self.n ** 2 - 1

        Return all missing values of self at the specified submatrix
        number s, the specified row number r, or the specified column
        number c.
        If s is specified, then r and c will be ignored;
        if s is None and r is specified, then c will be ignored;
        If neither s, r, nor c are specified, the function returns None.

        >>> import sudsoln.questions as sq
        >>> q1 = to_sudoku(sq.q1)
        >>> q1
        Sudoku(
            .    .    .    |    .    2    .    |    .    .    .
            8    3    .    |    7    1    4    |    .    9    6
            .    6    .    |    9    .    5    |    4    .    8
        -------------------+-------------------+-------------------
            .    9    .    |    3    .    1    |    .    .    4
            .    1    .    |    4    .    2    |    .    .    7
            .    7    5    |    .    .    .    |    2    1    .
        -------------------+-------------------+-------------------
            .    .    4    |    .    .    .    |    7    .    .
            .    .    .    |    5    .    7    |    .    .    .
            .    .    .    |    1    9    6    |    .    .    .
        n: 3
        elements: 1, 2, 3, 4, 5, 6, 7, 8, 9
        empty: .
        )
        >>> q1.missing(s = 1) == {'2', '5', '4', '9', '7', '1'}
        True
        >>> q1.missing(r = 3) == {'6', '2', '8', '5', '7'}
        True
        >>> q1.missing(c = 8) == {'3', '2', '5', '9', '1'}
        True
        '''

        elements = self.elements
        if s is not None:
            return elements.difference(set(self.submatrix(s).flatten()))
        elif r is not None:
            return elements.difference(set(self.row(r).flatten()))
        elif c is not None:
            return elements.difference(set(self.col(c).flatten()))

    def row(self, r):
        '''(Sudoku, int) -> Array

        Precondition: 0 <= r <= self.n ** 2 - 1

        Return one of self.n ** 2 rows of self selected by r.

        >>> import sudsoln.questions as sq
        >>> q1 = to_sudoku(sq.q1)
        >>> q1
        Sudoku(
            .    .    .    |    .    2    .    |    .    .    .
            8    3    .    |    7    1    4    |    .    9    6
            .    6    .    |    9    .    5    |    4    .    8
        -------------------+-------------------+-------------------
            .    9    .    |    3    .    1    |    .    .    4
            .    1    .    |    4    .    2    |    .    .    7
            .    7    5    |    .    .    .    |    2    1    .
        -------------------+-------------------+-------------------
            .    .    4    |    .    .    .    |    7    .    .
            .    .    .    |    5    .    7    |    .    .    .
            .    .    .    |    1    9    6    |    .    .    .
        n: 3
        elements: 1, 2, 3, 4, 5, 6, 7, 8, 9
        empty: .
        )
        >>> q1.row(2)
        Array([
        ['.', '6', '.', '9', '.', '5', '4', '.', '8']
        ])
        '''

        return self.show[r, :]

    def solve(self, max_trial = 200, quietly = False, seed = None):
        '''(Sudoku, int, bool[, int]) -> str, int

        Mutate self to the answer form, or until max_trial is met, and
        return the time it took to compute the answer and the number of
        trials used. seed can be given for reproducibility. Set
        quietly = True to display no messages.
        '''

        trial = 0
        import datetime
        n = self.n
        empty = self.empty
        start = datetime.datetime.now()
        self.solve_logically()
        sudoku_copy = self.copy()
        sudoku_copy_melted = sudoku_copy.melt()
        if empty in self.show.flatten():
            if not quietly:
                msg = "Logical approaches weren't enough. " +\
                    "Solving with a brute force..."
                print(msg)
            trial += self.solve_forcefully(
                max_trial = max_trial,
                quietly = quietly,
                seed = seed
            )
        end = datetime.datetime.now()
        if self.is_valid_answer():
            return str(end - start), trial
        else:
            if not quietly:
                print('Mission failed; max_trial of', max_trial, 'met.')
            self.itemsets(sudoku_copy_melted)
            return str(end - start), max_trial

    def solve_by_hidden_pairs(self, by = 'submatrix', start = None):
        '''(Sudoku, str[, Candidate]) -> Candidate

        Mutate self using the hidden pairs method based on 'by'. Starting
        candidate can be specified with 'start' argument; if start is
        None, then self.candidates() will be the starting point.
        '''

        return self.solve_by(
            by = by, start = start,
            condition = ['contains', 2], deep = True
        )

    def solve_by(
            self,
            by,
            start = None,
            condition = ['contains', 1],
            deep = False
        ):
        '''(Sudoku, str[, Candidate, [str, int], bool]) -> Candidate

        Precondition: by in ['row', 'col', 'submatrix']

        Solve self by methods involving pairs, triples, or a higher order.
        '''

        elements = self.elements
        bases = ['row', 'col', 'submatrix']
        bases.remove(by)
        names = bases
        if start is None:
            candidates_global = self.candidates()
            candidates_group = self.group(by = by)
        else:
            candidates_global = start
            candidates_group = start.group(by = by)

        changing = True
        while changing:
            sudoku_copy = self.copy()
            etm = candidate.Candidate({}, elements = elements)
            cg_cp = candidates_group.copy()
            for V in cg_cp.values():
                appearances = V.appearances(names)
                appearances.sieve(condition = condition, deep = deep)
                candidates_global.refine(
                    etm,
                    appearances = appearances,
                    condition = condition,
                    deep = deep
                )
            self.itemsets(etm)
            self.itemsets(candidates_global)
            candidates_group = candidates_global.group(by = by)
            if self == sudoku_copy and cg_cp == candidates_group:
                changing = False
        return candidates_global

    def solve_by_pointing_pairs(self, by = 'submatrix', start = None):
        '''(Sudoku, str[, Candidate]) -> Candidate

        Precondition: by in ['row', 'col', 'submatrix']

        Say bases = ['row', 'col', 'submatrix'], and one item is removed by
        bases.remove(by). Define the two leftovers in bases as group1 and
        group2 respectively. This method eliminates candidate numbers in
        other entries of the same group1 (e.g. rows) or group2
        (e.g. columns) based on entries of 'by' (e.g. submatrix) it
        belongs, mutate self into the closest answer form, and return a
        refined Candidate (better than self.candidates() in a sense that
        it has fewer, equal at worst, candidate numbers at each entry)
        based on iterations. Starting candidate can be specified with
        'start' argument; if start is None, then self.candidates() will be
        the starting point.
        '''

        return self.solve_by(
            by = by, start = start,
            condition = ['contains', 1], deep = False
        )

    def solve_forcefully(
            self,
            max_trial = 300,
            quietly = False,
            seed = None
        ):
        '''(Sudoku, int, bool[, int or None]) -> int

        Try out candidate numbers in each entry randomly until self is
        mutated into the answer form, or until max_trial is met. seed
        can be given for reproducibility. Set quietly = True if you don't
        want to display any messages.
        '''

        import random
        if seed is not None:
            random.seed(seed)
        trial = 1
        empty = self.empty
        sudoku_melt = self.melt()
        while empty in self.show.flatten():
            if empty not in self.show.flatten():
                return trial
            entries = self.solve_logically()
            if set() in list(entries.values()):
                if not quietly:
                    print(
                        "Trial number", trial,
                        "out of", max_trial, "failed;",
                        "proceeding to the next trial..."
                    )
                trial += 1
                if trial == max_trial:
                    return max_trial
                self.itemsets(sudoku_melt)
            else:
                keys = list(entries.keys()); keys.sort()
                guess = random.choice(list(entries[keys[0]]))
                self.itemset(keys[0], guess)
                self.solve_logically()
                if empty not in self.show.flatten() and \
                    not self.is_valid_answer():
                    self.itemsets(sudoku_melt)
        return trial

    def solve_globally(self):
        '''(Sudoku) -> None

        Find the only possible number at each entry of self, plug it
        into that entry, and repeat the process until no new mutation
        is made.
        '''

        changing = True
        while changing:
            sudoku_copy = self.copy()
            possible_numbers = self.candidates()
            for k, v in possible_numbers.items():
                if len(v) == 1:
                    self.itemset(k, list(v)[0])
            if sudoku_copy == self:
                changing = False

    def solve_locally(self, by):
        '''(Sudoku, str) -> None

        Precondition: by in ['submatrix', 'row', 'col']

        Find the unique candidate number within each 'by' of self,
        plug that number into that entry, and repeat the process across
        every other groups until no new mutation is made.
        '''

        changing = True
        while changing:
            sudoku_copy = self.copy()
            possible_numbers = self.unique_candidates(by = by)
            for k, v in possible_numbers.items():
                if len(v) == 1:
                    self.itemset(k, list(v)[0])
            if sudoku_copy == self:
                changing = False

    def solve_logically(self):
        '''(Sudoku) -> Candidate or None

        Mutate self to the answer form as close as possible (that is,
        having the least number of empty's), using only logical
        approaches that don't involve randomness or brute force in number
        assignment. Return Candidate if .solve_by*() methods have involved,
        and None otherwise.
        '''

        empty = self.empty
        sudoku_copy = self.copy()

        bases = ['submatrix', 'row', 'col']
        not_ready = True
        there_is_a_progress = True

        while there_is_a_progress:
            sudoku_copy_after_iter = self.copy()
            self.solve_globally()
            if empty not in str(self):
                return None
            for component in bases:
                self.solve_locally(by = component)
                self.solve_globally()
                if empty not in str(self):
                    return None

            start = self.solve_by_pointing_pairs()
            for component2 in bases:
                self.solve_by_hidden_pairs(by = component2, start = start)
                self.solve_by_pointing_pairs(start = start)

            if (sudoku_copy == self or sudoku_copy_after_iter == self):
                there_is_a_progress = False
        return start

    def submatrix(self, s):
        '''(Sudoku, int) -> Array

        Precondition: 1 <= s <= self.n ** 2

        Return one of self.n ** 2 submatrices of self selected by s.

        >>> import sudsoln.questions as sq
        >>> q1 = to_sudoku(sq.q1)
        >>> q1
        Sudoku(
            .    .    .    |    .    2    .    |    .    .    .
            8    3    .    |    7    1    4    |    .    9    6
            .    6    .    |    9    .    5    |    4    .    8
        -------------------+-------------------+-------------------
            .    9    .    |    3    .    1    |    .    .    4
            .    1    .    |    4    .    2    |    .    .    7
            .    7    5    |    .    .    .    |    2    1    .
        -------------------+-------------------+-------------------
            .    .    4    |    .    .    .    |    7    .    .
            .    .    .    |    5    .    7    |    .    .    .
            .    .    .    |    1    9    6    |    .    .    .
        n: 3
        elements: 1, 2, 3, 4, 5, 6, 7, 8, 9
        empty: .
        )
        >>> q1.submatrix(1)
        Array([
        ['.', '.', '.'],
        ['8', '3', '.'],
        ['.', '6', '.']
        ])
        >>> q1.submatrix(3)
        Array([
        ['.', '.', '.'],
        ['.', '9', '6'],
        ['4', '.', '8']
        ])
        >>> q1.submatrix(4)
        Array([
        ['.', '9', '.'],
        ['.', '1', '.'],
        ['.', '7', '5']
        ])
        '''

        n = self.n
        number = 0
        for i in range(n, n ** 2 + 1, n):
            for j in range(n, n ** 2 + 1, n):
                number += 1
                if number == s:
                    return self.show[(i - n):(i), (j - n):(j)]

    def unique_candidates(self, by):
        '''(Sudoku, str) -> Candidate

        Precondition: by in ['submatrix', 'row', 'col']

        Return the unique candidate number at each entry, within each
        group of self, grouped by 'by'.

        >>> q_small = '1.3..2.........4'
        >>> q_small = to_sudoku(q_small, elements = {1, 2, 3, 4})
        >>> q_small
        Sudoku(
            1    .    |    3    .
            .    2    |    .    .
        --------------+--------------
            .    .    |    .    .
            .    .    |    .    4
        n: 2
        elements: 1, 2, 3, 4
        empty: .
        )
        >>> q_small.unique_candidates('submatrix') ==\\
        ...     candidate.Candidate({
        ...                    (0, 1): set(),                (0, 3): {'2'},
        ...     (1, 0): {'3'},                (1, 2): {'4'}, (1, 3): set(),
        ...     (2, 0): set(), (2, 1): set(), (2, 2): set(), (2, 3): {'3'},
        ...     (3, 0): set(), (3, 1): set(), (3, 2): set()
        ...     },
        ...     elements = {1, 2, 3, 4}
        ... )
        ...
        True
        >>> q_small.unique_candidates('row') ==\\
        ...     candidate.Candidate({
        ...                    (0, 1): {'4'},                (0, 3): {'2'},
        ...     (1, 0): {'3'},                (1, 2): set(), (1, 3): set(),
        ...     (2, 0): set(), (2, 1): set(), (2, 2): set(), (2, 3): set(),
        ...     (3, 0): set(), (3, 1): set(), (3, 2): set()
        ...     },
        ...     elements = {1, 2, 3, 4}
        ... )
        ...
        True
        >>> q_small.unique_candidates('col') ==\\
        ...     candidate.Candidate({
        ...                    (0, 1): set(),                (0, 3): set(),
        ...     (1, 0): set(),                (1, 2): {'4'}, (1, 3): set(),
        ...     (2, 0): set(), (2, 1): set(), (2, 2): set(), (2, 3): {'3'},
        ...     (3, 0): set(), (3, 1): set(), (3, 2): set()
        ...     },
        ...     elements = {1, 2, 3, 4}
        ... )
        ...
        True
        '''

        n = self.n
        start = self.group(by = by)
        elements = self.elements
        result = candidate.Candidate({}, elements = elements)
        for V in start.values():
            keys = list(V.keys()); keys.sort() # sorting is unnecessary
            for i in range(len(keys)):
                blacklist, the_rest = [], set()
                blacklist.append(keys[i])
                for k, v in V.items():
                    if k not in blacklist:
                        the_rest.update(v)
                possible_nums = V[keys[i]].difference(the_rest)
                result.update({keys[i]: possible_nums})
        return result

def change_empty(array, old, new):
    '''(2d-array of objects, str, str) -> None

    Precondition: len(new) == 1

    Mutate array by replacing olds with new.

    >>> eg = [
    ...     ['1', '.', '3', '.'],
    ...     ['.', '2', '.', '.'],
    ...     ['.', '.', '.', '.'],
    ...     ['.', '.', '.', '4']
    ... ]
    ...
    >>> change_empty(eg, '.', ' ')
    >>> eg == [
    ...     ['1', ' ', '3', ' '],
    ...     [' ', '2', ' ', ' '],
    ...     [' ', ' ', ' ', ' '],
    ...     [' ', ' ', ' ', '4']
    ... ]
    ...
    True
    '''

    assert len(new) == 1, 'len(new) != 1'
    ch_old = lambda x: new if x == old else x
    if 'ndarray' in str(type(array)) or 'list' in str(type(array)):
        for i in range(len(array)):
            array[i] = list(map(ch_old, array[i]))
    elif 'Array' in str(type(array)):
        shape = array.shape
        for i in range(len(array.show)):
            array.show[i] = list(map(ch_old, array.show[i]))
    else:
        raise TypeError(str(type(array)) + ' not supported')

def fprint(Sudoku):
    '''(Sudoku) -> None

    Print out the formatted version of Sudoku.
    '''

    n = Sudoku.n
    the_range = range(0, n ** 4 + 1, n ** 2)
    item = ''
    result = ''
    sudoku_lst = list(str(Sudoku))
    for c in enumerate(sudoku_lst):
        item += c[1]
        if c[0] != 0 and c[0] + 1 in the_range:
            if c[0] != n ** 4 - 1:
                result += item + '\n'
            else:
                result += item + ''
            item = ''
    print(result)

def to_sudoku(sudoku_str, elements = None, empty = '.'):
    '''(str[, {objects} or None, str]) -> Sudoku

    Preconditions if elements is not None:
    1. set(list(sudoku_str)).issubset(elements.union(empty))
    2. len(elements) == len(sudoku_str) ** .5
    3. All elements in elements has len 1, as well as empty.

    Return the Sudoku object of sudoku_str if it is a string
    representation of Sudoku.
    '''

    n = int(len(sudoku_str) ** .25)
    array = sarray.Array(list(sudoku_str[:(n**4)])).reshape(n**2, n**2)
    return Sudoku(
        array = array,
        elements = elements,
        empty = empty
    )

if __name__ == '__main__':
    import doctest
    doctest.testmod()


text:
import time
import dgl
import torch
from torch.utils.data import Dataset
import random as rd
from ogb.graphproppred import Evaluator

from scipy import sparse as sp
import numpy as np
import itertools
import torch.utils.data
import pandas as pd
import shutil, os
import os.path as osp
from dgl.data.utils import load_graphs, save_graphs, Subset
from ogb.utils.url import decide_download, download_url, extract_zip
from ogb.io.read_graph_dgl import read_csv_graph_dgl
import networkx as nx

import gc

def positional_encoding(g, pos_enc_dim, norm):
    """
        Graph positional encoding v/ Laplacian eigenvectors
    """

    # Laplacian
    A = g.adjacency_matrix_scipy(return_edge_ids=False).astype(float)
    if norm == 'none':
        N = sp.diags(dgl.backend.asnumpy(g.in_degrees()).clip(1), dtype=float)
        L = N * sp.eye(g.number_of_nodes()) - A
    elif norm == 'sym':
        N = sp.diags(dgl.backend.asnumpy(g.in_degrees()).clip(1) ** -0.5, dtype=float)
        L = sp.eye(g.number_of_nodes()) - N * A * N
    elif norm == 'walk':
        N = sp.diags(dgl.backend.asnumpy(g.in_degrees()).clip(1) ** -1, dtype=float)
        L = sp.eye(g.number_of_nodes()) - N * A

    # # Eigenvectors with numpy
    # EigVal, EigVec = np.linalg.eig(L.toarray())
    # idx = EigVal.argsort() # increasing order
    # EigVal, EigVec = EigVal[idx], np.real(EigVec[:,idx])
    # g.ndata['pos_enc'] = torch.from_numpy(np.abs(EigVec[:,1:pos_enc_dim+1])).float()

    # Eigenvectors with scipy
    # EigVal, EigVec = sp.linalg.eigs(L, k=pos_enc_dim+1, which='SR')
    EigVal, EigVec = sp.linalg.eigs(L, k=pos_enc_dim + 1, which='SR', tol=1e-5)
    EigVec = EigVec[:, EigVal.argsort()]  # increasing order
    g.ndata['eig'] = torch.from_numpy(np.real(EigVec[:, :pos_enc_dim + 1])).float()
    print(int(g.ndata['eig'][:, 0].unique().size()[0]))
    if int(g.ndata['eig'][:, 0].unique().size()[0]) != 1:
        return positional_encoding_bis(g, pos_enc_dim, norm)
    return g

def positional_encoding_bis(g, pos_enc_dim, norm):
    """
        Graph positional encoding v/ Laplacian eigenvectors
    """
    num = int(g.number_of_nodes())
    G = nx.Graph()
    G.add_nodes_from([i for i in range(num)])
    for nod1, nod2 in zip(g.all_edges()[0].detach(), g.all_edges()[1].detach()):
        G.add_edge(nod1, nod2)

    components = list(nx.connected_components(G))
    list_G = []
    list_nodes = []

    for component in components:
        G_new = nx.Graph()
        G_new.add_nodes_from(list(component))
        list_G.append(G_new)
        list_nodes.append(list(component))
    for i in range(len(list_G)):
        for nod1, nod2 in list(G.edges(list_nodes[i])):
            list_G[i].add_edge(nod1, nod2)

    EigVec_global = np.ones((num, pos_enc_dim))
    for connected in list_G:
        node_list = list(connected.nodes)
        A = nx.adjacency_matrix(connected, nodelist=node_list).astype(float)
        if norm == 'none':
            D = sp.diags(list(map(lambda x: x[1], connected.degree())))
            L = D - A
        elif norm == 'sym':
            D_norm = sp.diags(list(map(lambda x: x[1] ** (-0.5), connected.degree())))
            D = sp.diags(list(map(lambda x: x[1], connected.degree())))
            L = D_norm * (D - A) * D_norm
        elif norm == 'walk':
            D_norm = sp.diags(list(map(lambda x: x[1] ** (-1), connected.degree())))
            D = sp.diags(list(map(lambda x: x[1], connected.degree())))
            L = D_norm * (D - A)

        if len(node_list) > 2:
            EigVal, EigVec = sp.linalg.eigs(L, k=min(len(node_list) - 2, pos_enc_dim), which='SR', tol=1e-5)
            EigVec = EigVec[:, EigVal.argsort()] / np.max(EigVec[:, EigVal.argsort()], 0)
            EigVec_global[node_list, : min(len(node_list) - 2, pos_enc_dim)] = EigVec[:, :]
        elif len(node_list) == 2:
            EigVec_global[node_list[0], :pos_enc_dim] = np.zeros((1, pos_enc_dim))
    g.ndata['eig'] = torch.from_numpy(EigVec_global).float()
    return g

class DownloadPCBA(object):
    """ Modified version of DglGraphPropPredDataset of ogb.graphproppred, that doesn't save the dataset """

    def __init__(self, name='ogbg-pcba', root="data"):
        self.name = name  ## original name, e.g., ogbg-mol-tox21
        self.dir_name = 'ogbg_molpcba_dgl'
        self.original_root = root
        self.root = osp.join(root, self.dir_name)

        # check version
        # First check whether the dataset has been already downloaded or not.
        # If so, check whether the dataset version is the newest or not.
        # If the dataset is not the newest version, notify this to the user.

        self.download_name = 'pcba'  ## name of downloaded file, e.g., tox21

        self.num_tasks = 128
        self.eval_metric = 'ap'
        self.task_type = 'binary classification'
        self.num_classes = 2

        self.pre_process()

    def pre_process(self):
        processed_dir = osp.join(self.root, 'processed')
        raw_dir = osp.join(self.root, 'raw')
        pre_processed_file_path = osp.join(processed_dir, 'dgl_data_processed')

        ### download
        url = 'https://snap.stanford.edu/ogb/data/graphproppred/csv_mol_download/pcba.zip'
        if decide_download(url):
            path = download_url(url, self.original_root)
            extract_zip(path, self.original_root)
            os.unlink(path)
            # delete folder if there exists
            try:
                shutil.rmtree(self.root)
            except:
                pass
            shutil.move(osp.join(self.original_root, self.download_name), self.root)
        else:
            print("Stop download.")
            exit(-1)

        ### preprocess
        add_inverse_edge = True
        additional_node_files = []
        additional_edge_files = []

        graphs = read_csv_graph_dgl(raw_dir, add_inverse_edge=add_inverse_edge,
                                    additional_node_files=additional_node_files,
                                    additional_edge_files=additional_edge_files)

        labels = pd.read_csv(osp.join(raw_dir, "graph-label.csv.gz"), compression="gzip", header=None).values

        has_nan = np.isnan(labels).any()

        if "classification" in self.task_type:
            if has_nan:
                labels = torch.from_numpy(labels)
            else:
                labels = torch.from_numpy(labels).to(torch.long)
        else:
            labels = torch.from_numpy(labels)

        print('Not Saving...')
        # save_graphs(pre_processed_file_path, graphs, labels={'labels': labels})

        ### load preprocessed files
        self.graphs = graphs
        self.labels = labels

    def get_idx_split(self, split_type=None):
        if split_type is None:
            split_type = 'scaffold'

        path = osp.join(self.root, "split", split_type)

        train_idx = pd.read_csv(osp.join(path, "train.csv.gz"), compression="gzip", header=None).values.T[0]
        valid_idx = pd.read_csv(osp.join(path, "valid.csv.gz"), compression="gzip", header=None).values.T[0]
        test_idx = pd.read_csv(osp.join(path, "test.csv.gz"), compression="gzip", header=None).values.T[0]

        return {"train": torch.tensor(train_idx, dtype=torch.long), "valid": torch.tensor(valid_idx, dtype=torch.long),
                "test": torch.tensor(test_idx, dtype=torch.long)}

    def __getitem__(self, idx):
        """Get datapoint with index"""

        if isinstance(idx, int):
            return self.graphs[idx], self.labels[idx]
        elif torch.is_tensor(idx) and idx.dtype == torch.long:
            if idx.dim() == 0:
                return self.graphs[idx], self.labels[idx]
            elif idx.dim() == 1:
                return Subset(self, idx.cpu())

        raise IndexError(
            'Only integers and long are valid '
            'indices (got {}).'.format(type(idx).__name__))

    def __len__(self):
        """Length of the dataset
        Returns
        -------
        int
            Length of Dataset
        """
        return len(self.graphs)

    def __repr__(self):  # pragma: no cover
        return '{}({})'.format(self.__class__.__name__, len(self))

class PCBADGL(torch.utils.data.Dataset):
    def __init__(self, data, split, norm='none'):
        self.split = split
        self.data = [g for g in data[self.split]]
        self.graph_lists = []
        self.graph_labels = []
        for i, g in enumerate(self.data):
            if g[0].number_of_nodes() > 5 and rd.random() < 0.5: # and rd.random() < 0.2:
                self.graph_lists.append(g[0])
                self.graph_labels.append(g[1])
        self.n_samples = len(self.graph_lists)
        del self.data

    def get_eig(self, norm):
        self.graph_lists = [positional_encoding(g, 2, norm=norm) for g in self.graph_lists]

    def __len__(self):
        """Return the number of graphs in the dataset."""
        return self.n_samples

    def __getitem__(self, idx):
        """
            Get the idx^th sample.
            Parameters
            ---------
            idx : int
                The sample index.
            Returns
            -------
            (dgl.DGLGraph, int)
                DGLGraph with node feature stored in `feat` field
                And its label.
        """
        return self.graph_lists[idx], self.graph_labels[idx]

class PCBADataset(Dataset):
    def __init__(self, name, norm='none', verbose=True):
        start = time.time()
        if verbose:
            print("[I] Loading dataset %s..." % (name))
        self.name = name
        dataset = DownloadPCBA(name = 'ogbg-molpcba')
        split_idx = dataset.get_idx_split()
        self.train = PCBADGL(dataset, split_idx['train'], norm=norm)
        self.val = PCBADGL(dataset, split_idx['valid'], norm=norm)
        self.test = PCBADGL(dataset, split_idx['test'], norm=norm)
        del dataset
        del split_idx
        self.train.get_eig(norm=norm)
        self.val.get_eig(norm=norm)
        self.test.get_eig(norm=norm)

        self.evaluator = Evaluator(name='ogbg-molpcba')

        if verbose:
            print('train, test, val sizes :', len(self.train), len(self.test), len(self.val))
            print("[I] Finished loading.")
            print("[I] Data load time: {:.4f}s".format(time.time() - start))

    # form a mini batch from a given list of samples = [(graph, label) pairs]
    def collate(self, samples):
        # The input samples is a list of pairs (graph, label).
        graphs, labels = map(list, zip(*samples))

        labels = torch.cat([label.unsqueeze(0) for label in labels])
        tab_sizes_n = [ graphs[i].number_of_nodes() for i in range(len(graphs))]
        tab_snorm_n = [ torch.FloatTensor(size,1).fill_(1./float(size)) for size in tab_sizes_n ]
        snorm_n = torch.cat(tab_snorm_n).sqrt()
        tab_sizes_e = [ graphs[i].number_of_edges() for i in range(len(graphs))]
        tab_snorm_e = [ torch.FloatTensor(size,1).fill_(1./float(size)) for size in tab_sizes_e ]
        snorm_e = torch.cat(tab_snorm_e).sqrt()
        batched_graph = dgl.batch(graphs)

        return batched_graph, labels, snorm_n, snorm_e

    def _add_self_loops(self):
        # function for adding self loops
        # this function will be called only if self_loop flag is True

        self.train.graph_lists = [self_loop(g) for g in self.train.graph_lists]
        self.val.graph_lists = [self_loop(g) for g in self.val.graph_lists]
        self.test.graph_lists = [self_loop(g) for g in self.test.graph_lists]

ext: py

reason: import numpy,from scipy,import networkx


text:
import numpy as np
import cv2
from mrcnn import utils

class Shapes(utils.Dataset):
    """Generates the shapes synthetic dataset
    """

    def load_shapes(self, count, height, width):
        self.add_class('shapes', 1, 'square')
        self.add_class('shapes', 2, 'circle')
        self.add_class('shapes', 3, 'triangle')

        # Add images
        for i in range(count):
            bg_color, shapes = self.random_image(height, width)
            self.add_image('shapes', image_id=i, path=None,
                           width=width, height=height,
                           bg_color=bg_color, shapes=shapes)

    def load_image(self, image_id):
        info = self.image_info[image_id]
        bg_color = np.array(info['bg_color']).reshape([1, 1, 3])
        image = np.ones([info['height'], info['width'], 3], dtype=np.uint8)
        image = image * bg_color.astype(np.uint8)
        for shape, color, dims in info['shapes']:
            image = self.draw_shape(image, shape, dims, color)
        return image

    def image_reference(self, image_id):
        info = self.image_info[image_id]
        if info['source'] == 'shapes':
            return info['shapes']
        else:
            super(self.__class__).image_reference(self, image_id)

    def load_mask(self, image_id):
        info = self.image_info[image_id]
        shapes = info['shapes']
        count = len(shapes)
        mask = np.zeros([info['height'], info['width'], count], dtype=np.uint8)
        for i, (shape, _, dims) in enumerate(info['shapes']):
            mask[:, :, i:i+1] = self.draw_shape(mask[:, :, i:i+1].copy(),
                                                shape, dims, 1)
        # Handle occlusions
        occlusion = np.logical_not(mask[:, :, -1]).astype(np.uint8)
        for i in range(count-2, -1, -1):
            mask[:, :, i] = mask[:, :, i] * occlusion
            occlusion = np.logical_and(occlusion,
                                       np.logical_not(mask[:, :, i]))
        # Map class names to class IDs.
        class_ids = np.array([self.class_names.index(s[0]) for s in shapes])
        return mask.astype(np.bool), class_ids.astype(np.int32)

    def draw_shape(self, image, shape, dims, color):
        X, Y, size = dims
        if shape == 'square':
            cv2.rectangle(image, (X - size, Y - size), (X + size, Y + size),
                          color, -1)
        elif shape == 'circle':
            cv2.circle(image, (X, Y), size, color, -1)
        elif shape == 'triangle':
            points = np.array([[(X, Y - size),
                                (X - size/np.sin(np.radians(60)), Y + size),
                                (X + size/np.sin(np.radians(60)), Y + size),
                                ]], dtype=np.int32)
            cv2.fillPoly(image, points, color)
        return image

    def random_shape(self, height, width):
        shape = np.random.choice(["square", "circle", "triangle"])
        color = tuple([np.random.randint(0, 255) for _ in range(3)])
        buffer = 20
        Y = np.random.randint(buffer, height - buffer - 1)
        X = np.random.randint(buffer, width - buffer - 1)
        size = np.random.randint(buffer, height//4)
        return shape, color, (X, Y, size)

    def random_image(self, height, width):
        bg_color = np.array([np.random.randint(0, 255) for _ in range(3)])
        shapes, boxes = [], []
        N = np.random.randint(1, 4)
        for _ in range(N):
            shape, color, dims = self.random_shape(height, width)
            shapes.append((shape, color, dims))
            X, Y, size = dims
            boxes.append([Y - size, X - size, Y + size, X + size])
        # Apply non-max suppression wit 0.3 threshold to avoid
        keep_ixs = utils.non_max_suppression(np.array(boxes), np.arange(N), 0.3)
        shapes = [s for i, s in enumerate(shapes) if i in keep_ixs]
        return bg_color, shapes

max_stars_repo_name: SushmaDG/MaskRCNN

max_issues_repo_name: SushmaDG/MaskRCNN

max_forks_repo_name: SushmaDG/MaskRCNN

reason: import numpy


text:
# channel_equalizer class
# Last modification by Marko Kosunen, marko.kosunen@aalto.fi, 05.01.2018 11:07
#Add TheSDK to path. Importing it first adds the rest of the modules
#Simple buffer template
import os

import numpy as np
#import tempfile

from thesdk import *
from verilog import *
from verilog.testbench import *
from verilog.testbench import testbench as vtb
from signal_generator_802_11n import PLPCsyn_long

class channel_equalizer(verilog,thesdk):
    @property
    def _classfile(self):
        return os.path.dirname(os.path.realpath(__file__)) + "/"+__name__

    def __init__(self,*arg):
        self.proplist = [ 'Rs', 'symbol_length', 'Users' ];    #properties that can be propagated from parent
        self.Rs = 160e6;                   # Sampling frequency
        self.Users = 16;                   # Number of users
        self.symbol_length  = 64;          # OFDM symbol length
        self.A = IO();            # Input data, FFT Bins in series
        self.estimate_sync = IO();
        self.equalize_sync = IO();
        self.estimate_user_index= IO();
        self._Z = IO();           # Output, equalized FFT bins
        self.control_write = IO()
        self.control_write.Data = Bundle()
        self._control_read = IO()
        self.model='py';             #can be set externally, but is not propagated
        self.par= False              #By default, no parallel processing
        self.queue= []               #By default, no parallel processing

        if len(arg)>=1:
            parent=arg[0]
            self.copy_propval(parent,self.proplist)
            self.parent =parent;
        self.init()
    def init(self):
        #This gets updated every time you add an iofile
        #self.iofile_bundle=Bundle()
        #Adds files to bundle
        _=verilog_iofile(self,name='Z',datatype='complex')
        _=verilog_iofile(self,name='control_read',datatype='complex')
        _=verilog_iofile(self,name='A',dir='in')
        _=verilog_iofile(self,name='estimate_sync',dir='in')
        _=verilog_iofile(self,name='equalize_sync',dir='in')
        _=verilog_iofile(self,name='estimate_user_index',dir='in')
        self.vlogparameters=dict([ ('g_Rs',self.Rs),])

    def main(self):
        out=np.array(self.A.Data)
        if self.par:
            self.queue.put(out)
        self._Z.Data=out

    def run(self,*arg):
        if len(arg)>0:
            self.par=True      #flag for parallel processing
            self.queue=arg[0]  #multiprocessing.queue as the first argument
        if self.model=='py':
            self.main()
        else:
          if self.model=='sv':
              self.control_write.Data.Members['control_write'].adopt(parent=self)

              # Create testbench and execute the simulation
              self.define_testbench()
              self.tb.export(force=True)
              self.write_infile()
              self.run_verilog()
              self.read_outfile()
              del self.iofile_bundle

          elif self.model=='vhdl':
              self.print_log(type='F', msg='VHDL model not yet supported')

    def write_infile(self):
        #Input file data definitions
        self.iofile_bundle.Members['A'].data=self.A.Data
        self.iofile_bundle.Members['estimate_sync'].data=self.estimate_sync.Data
        self.iofile_bundle.Members['estimate_user_index'].data=self.estimate_user_index.Data
        self.iofile_bundle.Members['equalize_sync'].data=self.equalize_sync.Data

        # This could be a method somewhere
        for name, val in self.iofile_bundle.Members.items():
            if val.dir=='in':
                self.iofile_bundle.Members[name].write()

    def read_outfile(self):
        #Handle the ofiles here as you see the best
        self.iofile_bundle.Members['Z'].read()
        self.iofile_bundle.Members['control_read'].read()
        self._Z.Data=self.iofile_bundle.Members['Z'].data
        self._control_read.Data=self.iofile_bundle.Members['control_read'].data

        if self.par:
            self.queue.put(self._Z)
            self.queue.put(self._control_read)

    # Testbench definition method
    def define_testbench(self):
        #Initialize testbench
        self.tb=vtb(self)
        # Create TB connectors from the control file
        for connector in self.control_write.Data.Members['control_write'].verilog_connectors:
            self.tb.connectors.Members[connector.name]=connector
            # Connect them to DUT
            try:
                self.dut.ios.Members[connector.name].connect=connector
            except:
                pass

        # Dut is created automaticaly, if verilog file for it exists
        self.tb.connectors.update(bundle=self.tb.dut_instance.io_signals.Members)

        #Assign verilog simulation parameters to testbench
        self.tb.parameters=self.vlogparameters

        # Copy iofile simulation parameters to testbench
        for name, val in self.iofile_bundle.Members.items():
            self.tb.parameters.Members.update(val.vlogparam)

        # Define the iofiles of the testbench. '
        # Needed for creating file io routines
        self.tb.iofiles=self.iofile_bundle

        #Define testbench verilog file
        self.tb.file=self.vlogtbsrc

        ## Start initializations
        #Init the signals connected to the dut input to zero
        for name, val in self.tb.dut_instance.ios.Members.items():
            if val.cls=='input':
                val.connect.init='\'b0'

        # IO file connector definitions
        # Define what signals and in which order and format are read form the files
        # i.e. verilog_connectors of the file
        # All connectors should be already defined at this phase
        name='control_write'
        ionames=[ _.name for _ in self.control_write.Data.Members[name].verilog_connectors ]
        self.iofile_bundle.Members[name].verilog_connectors=\
                self.tb.connectors.list(names=ionames)

        #for name in ionames:
        #    self.tb.connectors.Members[name].type='signed'

        name='estimate_sync'
        ionames=[]
        ionames+=['io_estimate_sync']
        self.iofile_bundle.Members[name].verilog_connectors=\
                self.tb.connectors.list(names=ionames)
        self.iofile_bundle.Members[name].verilog_io_condition='initdone'

        name='estimate_user_index'
        ionames=[]
        ionames+=['io_estimate_user_index']
        self.iofile_bundle.Members[name].verilog_connectors=\
                self.tb.connectors.list(names=ionames)
        self.iofile_bundle.Members[name].verilog_io_condition='initdone'

        name='equalize_sync'
        ionames=[]
        ionames+=['io_equalize_sync']
        self.iofile_bundle.Members[name].verilog_connectors=\
                self.tb.connectors.list(names=ionames)
        self.iofile_bundle.Members[name].verilog_io_condition='initdone'

        name='A'
        ionames=[]
        ionames+=['io_A_real', 'io_A_imag' ]
        self.iofile_bundle.Members[name].verilog_connectors=\
                self.tb.connectors.list(names=ionames)
        self.iofile_bundle.Members[name].verilog_io_condition='initdone'

        name='Z'
        ionames=[]
        for user in range(self.Users):
           ionames+= [ 'io_Z_%s_real' %(user) ,
                     'io_Z_%s_imag' %(user)]
        self.iofile_bundle.Members[name].verilog_connectors=\
                self.tb.connectors.list(names=ionames)

        self.iofile_bundle.Members[name].verilog_io_condition_append(cond='&& initdone')
        for name in ionames:
            self.tb.connectors.Members[name].type='signed'

        name='control_read'
        ionames=[]
        for user in range(self.Users):
           ionames+= [ 'io_estimate_out_%s_real' %(user) ,
                     'io_estimate_out_%s_imag' %(user)]
        self.iofile_bundle.Members[name].verilog_connectors=\
                self.tb.connectors.list(names=ionames)

        self.iofile_bundle.Members[name].verilog_io_condition_append(cond='&& initdone')
        # Should be ok, we just need somthing that trigs the writing to file
        # and is proportional to scan
        self.iofile_bundle.Members[name].verilog_io_sync='@(negedge io_estimate_read_en)\n'
        for name in ionames:
            self.tb.connectors.Members[name].type='signed'

        ## This method is in verilog_testbench class
        self.tb.generate_contents()

if __name__=="__main__":
    import matplotlib.pyplot as plt
    from  channel_equalizer import *
    from  channel_equalizer.controller import controller as channel_equalizer_controller
    from signal_generator_802_11n import PLPCsyn_long
    import pdb

    chlen=64
    len=16*chlen
    phres=64
    fsig=25e6
    refmaxval=30000
    #mode=0  ## Invert channel on chip
    mode=1  ## Invert channel externally
    #indata=2**10*np.exp(1j*2*np.pi/phres*(np.arange(len)*np.round(fsig/dut.Rs*phres)))\
    #        .reshape(-1,1)
    #indata=np.arange(1,2**13).astype(complex).reshape(-1,1)*(1+1j)
    #indata=np.ones((1,2**13)).astype(complex).reshape(-1,1)*(1+1j)
    onerows=np.ones((int(2**13/chlen),1),dtype=complex)
    tdata=np.round((onerows*PLPCsyn_long.T)*1024)
    #channel=onerows*np.ones((1,chlen))+1j*np.ones((1,chlen))
    channel=onerows*((np.arange(chlen)/chlen+1j*np.arange(chlen)/chlen).reshape(1,-1))
    #Should cap the max value to 1
    #channel=onerows*((np.random.normal(0,0.01,chlen)+1j*np.random.normal(0,0.1,chlen)).reshape(1,-1))

    #indata[0,0]=1+1j*1 # To help syncing
    indata=np.round(tdata * channel).reshape(-1,1)
    #indata[0:64:,0]=1+1j #Sync help
    equalize_sync=np.zeros((indata.shape[0],1))
    estimate_sync=np.zeros((indata.shape[0],1))

    controller=channel_equalizer_controller()
    controller.reset()
    controller.reset_estimate_memories()
    controller.step_time(step=10*controller.step)
    controller.write_reference_sequence(maxval=refmaxval)
    controller.set_estimate_format(value=mode)
    controller.step_time()

    equalize_sync[0::128]=1
    controller.start_datafeed()
    controller.step_time(step=125*controller.step)
    estimate_sync[0:16*128:128,0]=1
    estimate_user_index=(np.cumsum(estimate_sync)-1).reshape(-1,1)
    controller.step_time(step=16*128*controller.step)
    controller.set_estimate_zeros()
    controller.read_estimate_out()

    dut=channel_equalizer()
    dut2=channel_equalizer()
    dut.model='py'
    dut2.model='sv'
    for d in [ dut, dut2 ]:
        d.interactive_verilog=False
        d.A.Data=indata
        d.estimate_sync.Data=estimate_sync
        d.estimate_user_index.Data=estimate_user_index
        d.equalize_sync.Data=equalize_sync
        d.control_write=controller.control_write
        d.run()
    #Compute the estimates
    addresses=[0,1,2,3,4,5,32,59,60,61,62,63]
    #estimated_data=dut2._control_read.Data[0:64,0].reshape(-1,1)*np.ones((1,16))
    estimated_data=dut2._control_read.Data
    zf_matrix=np.array([],dtype='complex')
    for bin in range(64):
        c=(dut2._control_read.Data[bin,:]/2**16).reshape(-1,1) ##Channel estimate
        bf=((1/c).T*(2**16-1)).real.astype(int)+1j*((1/c).T*(2**16-1)).imag.astype(int)
        bftest=c*bf
        zf=(np.linalg.pinv(np.conj(c)*c.T)*np.conj(c)).T*2**16
        if bin==0:
            bf_matrix=bf.reshape(1,-1)
            zf_matrix=((zf.real).astype(int)+1j+zf.imag.astype(int)).reshape(1,-1)
        else:
            bf_matrix=np.r_['0', bf_matrix, bf.reshape(1,-1) ]
            zf_matrix=np.r_['0', zf_matrix, zf.reshape(1,-1) ]

    bf_matrix[addresses,:]=0+1j*0
    zf_matrix[addresses,:]=0+1j*0

    #restart simulation
    estimate_sync=np.zeros((indata.shape[0],1))
    controller.reset_control_sequence()
    controller.reset()
    controller.set_estimate_format(value=mode)
    controller.write_reference_sequence(maxval=refmaxval)
    if mode==0:
        controller.write_estimate_sequence(data=estimated_data)
    elif mode==1:
        controller.write_estimate_sequence(data=bf_matrix)
    controller.step_time()
    controller.start_datafeed()
    controller.step_time(step=2**10*controller.step)
    controller.read_estimate_out()
    for d in [ dut, dut2 ]:
        d.interactive_verilog=False
        d.estimate_sync.Data=estimate_sync
        d.run()

    f0=plt.figure(0)
    x_ref=np.arange(64).reshape(-1,1)
    seq_ref=controller.reference_sequence.reshape(-1,1)
    startindex=5750  #This is a random number within the valid output range
    offset=np.argmax(np.abs(np.correlate(
        dut2._Z.Data[startindex:startindex+127,0].reshape(-1),
        controller.reference_sequence.reshape(-1))))
    #print(offset)
    ##pdb.set_trace()
    seq_equalized=dut2._Z.Data[startindex+offset:startindex+offset+64,0].reshape(-1,1)
    plt.plot(x_ref,seq_ref.real,x_ref,seq_equalized.real)
    plt.xlim(0,63)
    plt.suptitle("Verilog model")
    plt.xlabel("Bin")
    plt.ylabel("Symbol")
    plt.grid()
    plt.show(block=False)
    f0.savefig('sequences_verilog.eps', format='eps', dpi=300);

    print(seq_equalized.shape)
    print(seq_ref.shape)
    err=(seq_ref-seq_equalized)
    print(err.shape)

    f1=plt.figure(1)
    plt.plot(x_ref,err)
    plt.xlim(0,63)
    plt.suptitle("Verilog model")
    plt.xlabel("Bin")
    plt.ylabel("Symbol error")
    plt.grid()
    plt.show(block=False)
    f1.savefig('sequences_diff.eps', format='eps', dpi=300);
    input()


text:
#!/usr/bin/env python
# Martin Kersner, m.kersner@gmail.com
# 2016/01/18

import numpy as np

def pascal_classes():
  classes = {'aeroplane' : 1,  'bicycle'   : 2,  'bird'        : 3,  'boat'         : 4,
             'bottle'    : 5,  'bus'       : 6,  'car'         : 7,  'cat'          : 8,
             'chair'     : 9,  'cow'       : 10, 'diningtable' : 11, 'dog'          : 12,
             'horse'     : 13, 'motorbike' : 14, 'person'      : 15, 'potted-plant' : 16,
             'sheep'     : 17, 'sofa'      : 18, 'train'       : 19, 'tv/monitor'   : 20}

  return classes

def pascal_palette():
  palette = {(  0,   0,   0) : 0 ,
             (128,   0,   0) : 1 ,
             (  0, 128,   0) : 2 ,
             (128, 128,   0) : 3 ,
             (  0,   0, 128) : 4 ,
             (128,   0, 128) : 5 ,
             (  0, 128, 128) : 6 ,
             (128, 128, 128) : 7 ,
             ( 64,   0,   0) : 8 ,
             (192,   0,   0) : 9 ,
             ( 64, 128,   0) : 10,
             (192, 128,   0) : 11,
             ( 64,   0, 128) : 12,
             (192,   0, 128) : 13,
             ( 64, 128, 128) : 14,
             (192, 128, 128) : 15,
             (  0,  64,   0) : 16,
             (128,  64,   0) : 17,
             (  0, 192,   0) : 18,
             (128, 192,   0) : 19,
             (  0,  64, 128) : 20 }

  return palette

def palette_demo():
  palette_list = pascal_palette().keys()
  palette = ()

  for color in palette_list:
    palette += color

  return palette

def convert_from_color_segmentation(arr_3d):
  arr_2d = np.zeros((arr_3d.shape[0], arr_3d.shape[1]), dtype=np.uint8)
  palette = pascal_palette()

  # slow!
  for i in range(0, arr_3d.shape[0]):
    for j in range(0, arr_3d.shape[1]):
      key = (arr_3d[i,j,0], arr_3d[i,j,1], arr_3d[i,j,2])
      arr_2d[i, j] = palette.get(key, 0) # default value if key was not found is 0

  return arr_2d

def get_id_classes(classes):
  all_classes = pascal_classes()
  id_classes = [all_classes[c] for c in classes]
  return id_classes

def strstr(str1, str2):
  if str1.find(str2) != -1:
    return True
  else:
    return False

def create_lut(class_ids, max_id=256):
  # Index 0 is the first index used in caffe for denoting labels.
  # Therefore, index 0 is considered as default.
  lut = np.zeros(max_id, dtype=np.uint8)

  new_index = 1
  for i in class_ids:
    lut[i] = new_index
    new_index += 1

  return lut


text:
import os
import h5py
import json
import numpy as np
import pandas as pd
import scipy.signal as spsig
from torch.nn.functional import normalize
from tqdm import tqdm

class ComParEExtractor(object):
    ''' 抽取comparE特征, 输入音频路径, 输出npy数组, 每帧130d
    '''
    def __init__(self, opensmile_tool_dir=None, downsample=10, tmp_dir='.tmp', no_tmp=False):
        ''' Extract ComparE feature
            tmp_dir: where to save opensmile csv file
            no_tmp: if true, delete tmp file
        '''
        if not os.path.exists(tmp_dir):
            os.makedirs(tmp_dir)
        if opensmile_tool_dir is None:
            opensmile_tool_dir = '/root/opensmile-2.3.0/'
        self.opensmile_tool_dir = opensmile_tool_dir
        self.tmp_dir = tmp_dir
        self.downsample = downsample
        self.no_tmp = no_tmp

    def __call__(self, wav):
        basename = os.path.basename(wav).split('.')[0]
        save_path = os.path.join(self.tmp_dir, basename+".csv")
        cmd = 'SMILExtract -C {}/config/ComParE_2016.conf \
            -appendcsvlld 0 -timestampcsvlld 1 -headercsvlld 1 \
            -I {} -lldcsvoutput {} -instname xx -O ? -noconsoleoutput 1'
        os.system(cmd.format(self.opensmile_tool_dir, wav, save_path))

        df = pd.read_csv(save_path, delimiter=';')
        wav_data = df.iloc[:, 2:]
        if len(wav_data) > self.downsample:
            wav_data = spsig.resample_poly(wav_data, up=1, down=self.downsample, axis=0)
            if self.no_tmp:
                os.remove(save_path)
        else:
            wav_data = None
            self.print(f'Error in {wav}, no feature extracted')

        return wav_data

def get_trn_val_tst(target_root_dir, cv, setname):
    int2name = np.load(os.path.join(target_root_dir, str(cv), '{}_int2name.npy'.format(setname)))
    int2label = np.load(os.path.join(target_root_dir, str(cv), '{}_label.npy'.format(setname)))
    assert len(int2name) == len(int2label)
    return int2name, int2label

def padding_to_fixlen(feat, max_len):
    assert feat.ndim == 2
    if feat.shape[0] >= max_len:
        feat = feat[:max_len]
    else:
        feat = np.concatenate([feat, \
            np.zeros((max_len-feat.shape[0], feat.shape[1]))], axis=0)
    return feat

def make_all_comparE(config):
    max_len = 50
    extractor = ComParEExtractor()
    trn_int2name, _ = get_trn_val_tst(config['target_root'], 1, 'trn')
    val_int2name, _ = get_trn_val_tst(config['target_root'], 1, 'val')
    tst_int2name, _ = get_trn_val_tst(config['target_root'], 1, 'tst')
    trn_int2name = trn_int2name.tolist()
    val_int2name = val_int2name.tolist()
    tst_int2name = tst_int2name.tolist()
    all_utt_ids = trn_int2name + val_int2name + tst_int2name
    all_feat = {}
    for utt_id in tqdm(all_utt_ids): # MSP-IMPROV-S01A-F01-S-FM01
        ses_id = int(utt_id.split('-')[3][-1])
        dialog_id = utt_id.split('-')[2]
        wav_path = os.path.join(config['data_root'], 'Audio', f'session{ses_id}', dialog_id, 'S', f'{utt_id}.wav')
        feat = extractor(wav_path)
        all_feat[utt_id] = padding_to_fixlen(feat, max_len)

    for cv in range(1, config['total_cv']+1):
        save_dir = os.path.join(config['feature_root'], 'A', str(cv))
        if not os.path.exists(save_dir):
            os.makedirs(save_dir)
        for set_name in ['trn', 'val', 'tst']:
            int2name, _ = get_trn_val_tst(config['target_root'], cv, set_name)
            cv_feats = []
            for utt_id in int2name:
                cv_feats.append(all_feat[utt_id])
            cv_feats = np.array(cv_feats)
            cv_feats = normalize(cv_feats)
            save_path = os.path.join(save_dir, set_name + '.npy')
            print(f'fold:{cv} {set_name} {cv_feats.shape}')
            np.save(save_path, cv_feats)

def normalize(feats):
    _feats = feats.reshape(-1, feats.shape[2])
    mean = np.mean(_feats, axis=0)
    std = np.std(_feats, axis=0)
    std[std == 0.0] = 1.0
    ret = (feats-mean) / (std)
    return ret

if __name__ == '__main__':
    pwd = os.path.abspath(__file__)
    pwd = os.path.dirname(pwd)
    config_path = os.path.join(pwd, '../../', 'data/config', 'MSP_config.json')
    config = json.load(open(config_path))
    make_all_comparE(config)

reason: import numpy,import scipy


text:
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
__author__="Josh Montague"
__license__="MIT License"

'''
This simple script runs as shown below and assumes there are
an arbitrary number of .jpg image files in an adjacent directory
named data. Predictions are sent to standard out (screen).

$ python simple-demo.py
'''

import glob
from pprint import pprint
import numpy as np
import sys

from keras.applications.vgg16 import VGG16, preprocess_input, decode_predictions
from keras.preprocessing import image

model = VGG16(weights='imagenet')

# assumes existing image files in data/
for im in glob.glob('data/*.jpg'):
    img = image.load_img(im, target_size=(224,224))
    x = image.img_to_array(img)
    x = np.expand_dims(x, axis=0)
    x = preprocess_input(x)
    preds = model.predict(x)
    output = decode_predictions(preds, top=5)[0]
    print('filename: {}'.format(im.split('/')[1]))
    print('predictions:')
    pprint(output, stream=sys.stdout)
    print('\n')

max_stars_repo_name: jrmontag/tweet-image-labels

max_issues_repo_name: jrmontag/tweet-image-labels

max_forks_repo_name: jrmontag/tweet-image-labels


text:
# coding=utf-8
# Copyright 2018 Google LLC & Hwalsuk Lee.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

"""Test cases to verify estimator training and matches our training loop."""

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function

import itertools
import os

from absl import flags
from absl.testing import flagsaver
from absl.testing import parameterized
from compare_gan.src import gan_lib

import numpy as np
import tensorflow as tf

FLAGS = flags.FLAGS

class AbstractGANEstimatorTest(parameterized.TestCase, tf.test.TestCase):
  options = {
      'dataset': 'cifar10',
      'architecture': 'resnet_cifar_arch',
      'batch_size': 4,
      'discriminator_normalization': 'none',
      'gan_type': 'GAN_PENALTY',
      'optimizer': 'sgd',
      'penalty_type': 'no_penalty',
      'save_checkpoint_steps': 1,
      'training_steps': 5,
      'disc_iters': 3,
      'learning_rate': 0.000199999994948,
      'tf_seed': 42,
      'z_dim': 128,
      'lambda': 1,
      'beta2': 0.999000012875,
      'beta1': 0.5,
  }

  def load_checkpoint(self, checkpoint_dir, step):
    checkpoint_path = os.path.join(checkpoint_dir, 'model.ckpt-' + str(step))
    if not tf.gfile.Exists(checkpoint_path + '.index'):
      checkpoint_path = os.path.join(checkpoint_dir,
                                     'GAN_PENALTY.model-' + str(step))
    return tf.train.load_checkpoint(checkpoint_path)

  # The test case trains a model with the non-estimator training loop and the
  # estimator training loop for a few steps and checks that the learned weights
  # match.
  @parameterized.named_parameters(
      [('DiscIters{}Unroll{}TPU{}'.format(*p), p[0], p[1], p[2]) for p in
       itertools.product([1, 3], [False, True], [False, True])]
  )
  @flagsaver.flagsaver
  def testEstimatorEqualsSession(self, disc_iters, unroll_disc_iters, use_tpu):
    if use_tpu and not unroll_disc_iters:
      # This is currently not supported. See b/111760885.
      return

    FLAGS.master = None
    FLAGS.iterations_per_loop = 1

    options = self.options.copy()
    options['disc_iters'] = disc_iters

    workdir = os.path.join(FLAGS.test_tmpdir, 'disc_iters{}/unroll{}'.format(
        disc_iters, unroll_disc_iters))

    options['use_estimator'] = False
    gan_lib.run_with_options(options, os.path.join(workdir, 'no_estimator'))

    # We use the first checkpoint of the run without Estimator to warm start.
    # Otherwise both models start with different values as the tf_seed is fixed
    # but the graphs are still different.
    warm_start = tf.estimator.WarmStartSettings(
        os.path.join(workdir, 'no_estimator/checkpoint/GAN_PENALTY.model-0'))
    options.update({
        'use_estimator': True,
        'unroll_disc_iters': unroll_disc_iters,
        'use_tpu': use_tpu,
    })
    gan_lib.run_with_options(options, os.path.join(workdir, 'estimator'),
                             warm_start_from=warm_start)

    for step in range(0, options['training_steps'], options['disc_iters']):
      tf.logging.info('Comparing checkpoints for step %d', step)
      estimator_ckpt = self.load_checkpoint(
          os.path.join(workdir, 'estimator/checkpoint'), step)
      baseline_ckpt = self.load_checkpoint(
          os.path.join(workdir, 'no_estimator/checkpoint'), step)

      not_equal = 0
      for name in baseline_ckpt.get_variable_to_shape_map():
        assert estimator_ckpt.has_tensor(name), name
        if name.endswith('moving_mean') or name.endswith('moving_variance'):
          # Ignore batch norm values.
          continue
        if 'discriminator' in name and name.endswith('biases'):

          continue
        t1 = estimator_ckpt.get_tensor(name)
        t2 = baseline_ckpt.get_tensor(name)
        if name == 'global_step':
          self.assertEqual(t1, step)
          self.assertEqual(t2, step)
          continue
        if not np.allclose(t1, t2, atol=1e-7):
          not_equal += 1
          diff = np.abs(t1 - t2)
          idx = np.argmax(diff)
          tf.logging.info(
              '%s is not close at step %d: maximum difference: %s (%s -> %s)',
              name, step, diff.max(), t1.flatten()[idx], t2.flatten()[idx])

      self.assertEqual(not_equal, 0)

if __name__ == '__main__':
  tf.test.main()


text:
import pandas as pd
import numpy as np
import sys
import os
import ddot
import argparse
from ddot import Ontology

parser = argparse.ArgumentParser(description='Generate bash file for community detection pipeline.')
parser.add_argument('--outprefix', help='Prefix for files generated. E.g. /path/to/output/directory/fileIdentifier')
parser.add_argument('--minSystemSize', type=int, default=4,
                    help='Minimum number of proteins requiring each system to have.')
args = parser.parse_args()

minSystemSize = args.minSystemSize
print('... start trimming clixo to keep only systems with at least {} proteins'.format(minSystemSize))

f = '{}.clixoOutFile.oaInput'.format(args.outprefix)
ont = Ontology.from_table(f, clixo_format=True)
tsize = list(zip(ont.terms, ont.term_sizes))
delete_term = [x[0] for x in tsize if x[1] < minSystemSize]
trimmed_ont = ont.delete(to_delete=delete_term)
trimmed_ont = trimmed_ont.collapse_ontology(method='python')
trimmed_ont.to_table(f+'.mintsize{}'.format(minSystemSize), clixo_format=True)
print('=== finished trim_clixo.py ===')

max_stars_repo_name: oeway/MuSIC

max_issues_repo_name: oeway/MuSIC

max_forks_repo_name: oeway/MuSIC


text:
from typing import NoReturn
from ...base import BaseEstimator
import numpy as np
from numpy.linalg import det, inv

class GaussianNaiveBayes(BaseEstimator):
    """
    Gaussian Naive-Bayes classifier
    """

    def __init__(self):
        """
        Instantiate a Gaussian Naive Bayes classifier

        Attributes
        ----------
        self.classes_ : np.ndarray of shape (n_classes,)
            The different labels classes. To be set in `GaussianNaiveBayes.fit`

        self.mu_ : np.ndarray of shape (n_classes,n_features)
            The estimated features means for each class. To be set in `GaussianNaiveBayes.fit`

        self.vars_ : np.ndarray of shape (n_classes, n_features)
            The estimated features variances for each class. To be set in `GaussianNaiveBayes.fit`

        self.pi_: np.ndarray of shape (n_classes)
            The estimated class probabilities. To be set in `GaussianNaiveBayes.fit`
        """
        super().__init__()
        self.classes_, self.mu_, self.vars_, self.pi_ = None, None, None, None

    def _fit(self, X: np.ndarray, y: np.ndarray) -> NoReturn:
        """
        fits a gaussian naive bayes model

        Parameters
        ----------
        X : ndarray of shape (n_samples, n_features)
            Input data to fit an estimator for

        y : ndarray of shape (n_samples, )
            Responses of input data to fit to
        """
        self.classes_ = np.unique(y)
        self.mu_ = np.array([X[y == i].mean(axis=0) for i in self.classes_]).T
        self.vars_ = np.array([self._cov_for_class(X, y, i) for i in self.classes_])
        self.pi_ = np.array([len(X[y == i]) for i in self.classes_]) / y.size

    def _cov_for_class(self, X, y, i):
        X_mu = X[y == i] - self.mu_[:, i]
        return np.diag(np.einsum('ij,ji->i', X_mu.T, X_mu) / X_mu.shape[0])

    def _predict(self, X: np.ndarray) -> np.ndarray:
        """
        Predict responses for given samples using fitted estimator

        Parameters
        ----------
        X : ndarray of shape (n_samples, n_features)
            Input data to predict responses for

        Returns
        -------
        responses : ndarray of shape (n_samples, )
            Predicted responses of given samples
        """
        return np.argmax(self.likelihood(X), axis=1)

    def likelihood(self, X: np.ndarray) -> np.ndarray:
        """
        Calculate the likelihood of a given data over the estimated model

        Parameters
        ----------
        X : np.ndarray of shape (n_samples, n_features)
            Input data to calculate its likelihood over the different classes.

        Returns
        -------
        likelihoods : np.ndarray of shape (n_samples, n_classes)
            The likelihood for each sample under each of the classes

        """
        if not self.fitted_:
            raise ValueError("Estimator must first be fitted before calling `likelihood` function")

        return np.array([self._calc_pdf(X - self.mu_.T[c, :], self.vars_[c, :], self.pi_[c]) for c in
                         range(self.classes_.size)]).T

    @staticmethod
    def _calc_pdf(X_minus_mu, cov, pi):
        exp_pi = np.exp(-.5 * np.einsum('ij,ji->i', X_minus_mu @ inv(cov), X_minus_mu.T)) * pi
        Z = np.sqrt((2 * np.pi) ** X_minus_mu.shape[1] * det(cov))
        return exp_pi / Z

    def _loss(self, X: np.ndarray, y: np.ndarray) -> float:
        """
        Evaluate performance under misclassification loss function

        Parameters
        ----------
        X : ndarray of shape (n_samples, n_features)
            Test samples

        y : ndarray of shape (n_samples, )
            True labels of test samples

        Returns
        -------
        loss : float
            Performance under missclassification loss function
        """
        from ...metrics import misclassification_error
        return misclassification_error(y, self.predict(X))

reason: import numpy,from numpy


text:
#!/usr/bin/env python

import bob.bio.base
import numpy

algorithm = bob.bio.base.algorithm.BIC(
  # Distance measure to compare two features in input space
  comparison_function = numpy.subtract,
  # Limit the number of training pairs
  maximum_training_pair_count = 10000,
  # Dimensions of intrapersonal and extrapersonal subspaces
  subspace_dimensions = (30, 30)
)