Category Archives: Algorithms

Sorting an Array of Tuples in Python

In this video I show a nice way to work with Data in Python, by using Tuples.

I also show how to easily and conveniently sort the Data based on your preferred criteria by using lambdas.

What happens if we have accents, ç, Ç etc…

You can download the code from:

https://gitlab.com/carles.mateo/python_combat_guide/-/blob/master/src/arrays_with_tuples.py

Working on a Sudoku Solver in Python (Source Code)

This is a document previous to a live code review session.

It has the information to prepare for the upcoming code review session, where I plan to share the lessons learned, decision I took, mistakes I did, refactors I had to overcome, and tentatively we will refactor code in order to add some Unit Testing.

History

I used to play sudoku with my family, so from time to time I do by myself.

Once I found a sudoku that was impossible and it happened that it was a typo from the newspaper, so, when I found another impossible sudoku I wanted to know if it was me, or if there was a typo or similar, so I decided to write a Sudoku Solver that will solve the sudoku for me.

The bad guys

I had problems solving these two sudokus:

Some Screenshots

The Source Code

You can clone the project from here:

https://gitlab.com/carles.mateo/sudo-ku-solver

You will have to install colorama package, as I used it for giving colors to the output:

pip3 install colorama

The main program sudokusolver.py:

import copy
from lib.colorutils import ColorUtils


class SudokuMap():
    
    def __init__(self, i_width, i_height, o_color=ColorUtils()):
        self.i_width = i_width
        self.i_height = i_height
        self.o_color = o_color

        self.a_map = self.generate_empty_map()

    def generate_empty_map(self):
        a_map = []
        a_row = []
        a_i_possible_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
        for i_x in range(self.i_width):
            a_row.append(a_i_possible_numbers.copy())

        for i_y in range(self.i_height):
            a_map.append(copy.deepcopy(a_row))

        return a_map

    def set_number(self, i_number, i_x, i_y):
        """
        Sets a well known (already defined in the original map) number for a position
        :param i_number:
        :param i_x:
        :param i_y:
        :return:
        """
        self.a_map[i_y][i_x] = [i_number]

    def detect_and_remove_a_number_from_possibles_from_a_row(self, i_y):
        """
        We will elinate this possibility from the row
        :return: Boolean
        """

        b_found = False
        self.o_color.print_label("Detecting numbers to remove from row " + str(i_y))

        for i_x in range(0, self.i_width):
            a_i_numbers_possible = self.a_map[i_y][i_x]
            if len(a_i_numbers_possible) == 1:
                b_found = True
                i_number_found = self.a_map[i_y][i_x][0]
                print("Found a number that will be removed from horizontal and vertical and in quadrant", i_number_found, "at", i_x, i_y)
                self.remove_a_number_from_possibles_in_a_row(i_number_to_remove=i_number_found, i_y=i_y)
                self.remove_a_number_from_possibles_in_a_column(i_number_to_remove=i_number_found, i_x=i_x)
                self.remove_a_number_from_possibles_in_quadrant(i_number_to_remove=i_number_found, i_x=i_x, i_y=i_y)

        return b_found

    def remove_a_number_from_possibles_in_a_row(self, i_number_to_remove, i_y):
        """
        Removes a number from the list of possibles in that row
        :param i_number_to_remove:
        :param i_y:
        :return:
        """

        self.o_color.print_label("> Scanning for removing " + str(i_number_to_remove) + " in row " + str(i_y))

        for i_x in range(0, self.i_width):
            a_i_numbers_possible = self.a_map[i_y][i_x]
            if len(a_i_numbers_possible) == 1 and a_i_numbers_possible[0] == i_number_to_remove:
                # This is the right cell, ignore it
                pass
            else:
                # Subtract the number from the sequence
                if i_number_to_remove in a_i_numbers_possible:
                    a_i_numbers_possible_old = a_i_numbers_possible.copy()
                    a_i_numbers_possible.remove(i_number_to_remove)
                    print("> Removed", i_number_to_remove, "From:", str(i_x) + "x" + str(i_y), a_i_numbers_possible_old, "Pending:", a_i_numbers_possible)
                    self.a_map[i_y][i_x] = a_i_numbers_possible
                    if len(a_i_numbers_possible) == 1:
                        # Trigger it again for the number recently discovered
                        i_new_number_to_remove = a_i_numbers_possible[0]
                        self.o_color.print_success("> Found " + str(i_new_number_to_remove) + " From: " + str(i_x) + "x" + str(i_y))
                        self.remove_a_number_from_possibles_in_a_row(i_number_to_remove=i_new_number_to_remove, i_y=i_y)
                        self.remove_a_number_from_possibles_in_a_column(i_number_to_remove=i_new_number_to_remove, i_x=i_x)
                        self.remove_a_number_from_possibles_in_quadrant(i_number_to_remove=i_new_number_to_remove, i_x=i_x, i_y=i_y)

        self.o_color.print_label("> Leaving scan for " + str(i_number_to_remove) + " in row " + str(i_y))

    def remove_a_number_from_possibles_in_a_column(self, i_number_to_remove, i_x):
        """
        Removes a number from the list of possibles in that row
        :param i_number_to_remove:
        :param i_y:
        :return:
        """

        self.o_color.print_label("V Scanning for removing " + str(i_number_to_remove) + " in col " + str(i_x))

        for i_y in range(0, self.i_height):
            a_i_numbers_possible = self.a_map[i_y][i_x]
            if len(a_i_numbers_possible) == 1 and a_i_numbers_possible[0] == i_number_to_remove:
                # This is the right cell, ignore it
                pass
            else:
                # Subtract the number from the sequence
                if i_number_to_remove in a_i_numbers_possible:
                    a_i_numbers_possible_old = a_i_numbers_possible.copy()
                    a_i_numbers_possible.remove(i_number_to_remove)
                    print("V Removed", i_number_to_remove, "From:", i_x, i_y, a_i_numbers_possible_old, "Pending:", a_i_numbers_possible)
                    # @TODO: Remove, as it's a pointer it is not needed
                    self.a_map[i_y][i_x] = a_i_numbers_possible
                    if len(a_i_numbers_possible) == 1:
                        # Trigger it again for the number recently discovered
                        i_new_number_to_remove = a_i_numbers_possible[0]
                        self.o_color.print_success("Found " + str(i_new_number_to_remove) + " From: " + str(i_x) + " " + str(i_y))
                        self.remove_a_number_from_possibles_in_a_row(i_number_to_remove=i_new_number_to_remove, i_y=i_y)
                        self.remove_a_number_from_possibles_in_a_column(i_number_to_remove=i_new_number_to_remove, i_x=i_x)
                        self.remove_a_number_from_possibles_in_quadrant(i_number_to_remove=i_new_number_to_remove, i_x=i_x, i_y=i_y)

        self.o_color.print_label("V Leaving scan for " + str(i_number_to_remove) + " in col " + str(i_x))

    def remove_a_number_from_possibles_in_quadrant(self, i_number_to_remove, i_x, i_y):
        """

        :param i_number_to_remove:
        :param i_x:
        :param i_y:
        :return:
        """

        i_x_quadrant = int(i_x / 3)
        i_y_quadrant = int(i_y / 3)

        i_x_ini = i_x_quadrant * 3
        i_x_end = i_x_ini + 2

        i_y_ini = i_y_quadrant * 3
        i_y_end = i_y_ini + 2

        for i_y_rel in range(i_y_ini, i_y_end + 1):
            for i_x_rel in range(i_x_ini, i_x_end + 1):
                a_i_numbers_possible = self.a_map[i_y_rel][i_x_rel]
                if len(a_i_numbers_possible) == 1 and a_i_numbers_possible[0] == i_number_to_remove:
                    # This is the right cell, ignore it
                    pass
                else:
                    # Subtract the number from the sequence
                    if i_number_to_remove in a_i_numbers_possible:
                        a_i_numbers_possible_old = a_i_numbers_possible.copy()
                        a_i_numbers_possible.remove(i_number_to_remove)
                        print("X Removed", i_number_to_remove, "From:", i_x_rel, i_y_rel, a_i_numbers_possible_old, "Pending:", a_i_numbers_possible)
                        # Nota: Here I had a bug and I was "liant-la parda"
                        # if len(a_i_numbers_possible) == 1:
                        #     # Trigger it again for the number recently discovered
                        #     i_new_number_to_remove = a_i_numbers_possible[0]
                        #     string_ints = [str(int) for int in ints]
                        #     self.o_color.print_success("X Found " + str(i_new_number_to_remove) + " From: " + str(i_x) + "x" + str(i_y) + "[]")
                        #     self.remove_a_number_from_possibles_in_a_row(i_number_to_remove=i_new_number_to_remove, i_y=i_y)
                        #     self.remove_a_number_from_possibles_in_a_column(i_number_to_remove=i_new_number_to_remove, i_x=i_x)

    def check_if_number_possibles_in_quadrant_is_unique(self, i_number_to_check, i_x, i_y):
        """

        :param i_number_to_remove:
        :param i_x:
        :param i_y:
        :return: b_found
        """

        i_x_quadrant = int(i_x / 3)
        i_y_quadrant = int(i_y / 3)

        i_x_ini = i_x_quadrant * 3
        i_x_end = i_x_ini + 2

        i_y_ini = i_y_quadrant * 3
        i_y_end = i_y_ini + 2

        i_number_of_occurrences_found = 0
        i_x_position_number = 0
        i_y_position_number = 0

        b_unique = False

        for i_y_rel in range(i_y_ini, i_y_end + 1):
            for i_x_rel in range(i_x_ini, i_x_end + 1):
                a_i_numbers_possible = self.a_map[i_y_rel][i_x_rel]
                for i_number_in_possibles in a_i_numbers_possible:
                    if len(a_i_numbers_possible) > 1 and i_number_in_possibles == i_number_to_check:
                        # This is the right cell, ignore it
                        i_number_of_occurrences_found += 1
                        i_x_position_number = i_x_rel
                        i_y_position_number = i_y_rel
                        if i_number_of_occurrences_found > 1:
                            # Unsuccessful
                            break

        if i_number_of_occurrences_found == 1:
            # Success!
            a_i_numbers_possible = [i_number_to_check]
            self.a_map[i_y_position_number][i_x_position_number] = a_i_numbers_possible
            b_unique = True

        return b_unique, i_x_position_number, i_y_position_number

    def check_if_number_possibles_in_row_is_unique(self, i_number_to_check, i_y):
        """

        :param i_number_to_check:
        :param i_x:
        :param i_y:
        :return:
        """

        i_number_of_occurrences_found = 0
        i_x_position_number = 0
        i_y_position_number = 0

        b_unique = False

        for i_x_rel in range(0, 9):
            a_i_numbers_possible = self.a_map[i_y][i_x_rel]
            for i_number_in_possibles in a_i_numbers_possible:
                if len(a_i_numbers_possible) > 1 and i_number_in_possibles == i_number_to_check:
                    # This is the right cell, ignore it
                    i_number_of_occurrences_found += 1
                    i_x_position_number = i_x_rel
                    i_y_position_number = i_y
                    if i_number_of_occurrences_found > 1:
                        # Unsuccessful
                        break

        if i_number_of_occurrences_found == 1:
            # Success!
            a_i_numbers_possible = [i_number_to_check]
            self.a_map[i_y_position_number][i_x_position_number] = a_i_numbers_possible
            b_unique = True

        return b_unique, i_x_position_number, i_y_position_number

    def get_map_drawing_as_string(self, a_map_alternative=None):
        s_map = ""
        i_counter_y = 0
        s_separator_rows = "="

        a_map_to_use = self.a_map
        if a_map_alternative is not None:
            a_map_to_use = a_map_alternative

        s_map = s_map + s_separator_rows * 37 + "\n"
        for a_row in a_map_to_use:
            i_counter_y += 1
            if i_counter_y == 3:
                i_counter_y = 0
                s_separator_rows = "="
            else:
                s_separator_rows = "-"

            s_map = s_map + "|"
            i_counter = 0
            for a_i_numbers_possible in a_row:
                i_counter += 1

                if len(a_i_numbers_possible) == 1:
                    s_number = str(a_i_numbers_possible[0])
                else:
                    s_number = " "

                if i_counter == 3:
                    s_separator = "|"
                    i_counter = 0
                else:
                    s_separator = "¦"
                s_map = s_map + " " + s_number + " " + s_separator
            s_map = s_map + "\n"

            s_map = s_map + s_separator_rows * 37 + "\n"

            # Replace 0 by " "
            s_map = s_map.replace("0", " ")

        s_map = s_map + "\n\n"
        i_total_numbers_found, a_s_numbers_found = self.get_total_numbers_found()
        s_map = s_map + "Total numbers found: " + str(i_total_numbers_found) + " Numbers found: " + " ".join(a_s_numbers_found) + "\n"

        return s_map

    def get_map_drawing_of_possibles_as_string(self, a_map_alternative=None):
        s_map = ""
        i_counter_y = 0
        s_separator_rows = "="

        a_map_to_use = self.a_map
        if a_map_alternative is not None:
            a_map_to_use = a_map_alternative

        s_map = s_map + self.o_color.color_blue(s_separator_rows * ((9 * ( 9 + 2 )) + 10)) + "\n"
        for a_row in a_map_to_use:
            i_counter_y += 1
            if i_counter_y == 3:
                i_counter_y = 0
                s_separator_rows = "="
            else:
                s_separator_rows = "-"

            s_map = s_map + self.o_color.color_blue("|")
            i_counter = 0
            for a_i_numbers_possible in a_row:
                i_counter += 1

                if len(a_i_numbers_possible) == 1:
                    # The right number
                    s_number = str(a_i_numbers_possible[0]).center(9)
                    s_number = self.o_color.color_success(s_number)
                else:
                    a_i_numbers_possible_string = []
                    for i_number in a_i_numbers_possible:
                        s_number = str(i_number)
                        # Replace by the color sequence
                        if i_number == 2:
                            s_number = self.o_color.color_red(s_number)
                        if i_number == 3:
                            s_number = self.o_color.color_yellow(s_number)
                        if i_number == 4:
                            self.o_color.color_magenta(s_number)
                        a_i_numbers_possible_string.append(s_number)
                    # s_number = "".join(a_i_numbers_possible_string).ljust(9)
                    s_number = "".join(a_i_numbers_possible_string) + " " * (9-len(a_i_numbers_possible))

                if i_counter == 3:
                    s_separator = self.o_color.color_blue("|")
                    i_counter = 0
                else:
                    s_separator = self.o_color.color_blue("¦")
                s_map = s_map + " " + s_number + " " + s_separator
            s_map = s_map + "\n"

            s_map = s_map + self.o_color.color_blue(s_separator_rows * ((9 * (9 + 2)) + 10)) + "\n"

            # Replace 0 by " "
            s_map = s_map.replace("0", " ")

        return s_map

    def get_total_numbers_found(self):

        i_total_numbers_found = 0
        a_s_numbers_found = []

        for i_y in range(0, self.i_height):
            for i_x in range(0, self.i_width):
                a_i_numbers_possible = self.a_map[i_y][i_x]
                if len(a_i_numbers_possible) == 1:
                    i_total_numbers_found = i_total_numbers_found + 1
                    i_number_found = self.a_map[i_y][i_x][0]
                    s_number_found = str(i_number_found)
                    if s_number_found not in a_s_numbers_found:
                        a_s_numbers_found.append(s_number_found)

        return i_total_numbers_found, a_s_numbers_found


if __name__ == "__main__":

    o_color = ColorUtils()

    o_map = SudokuMap(9, 9, o_color=o_color)
    o_map.set_number(i_number=1, i_x=1, i_y=0)
    o_map.set_number(3, 4, 0)
    o_map.set_number(8, 7, 0)

    o_map.set_number(8, 0, 1)
    o_map.set_number(7, 3, 1)
    o_map.set_number(4, 5, 1)
    o_map.set_number(6, 8, 1)

    o_map.set_number(3, 2, 2)
    o_map.set_number(9, 6, 2)

    o_map.set_number(2, 1, 3)
    o_map.set_number(4, 4, 3)
    o_map.set_number(6, 7, 3)

    o_map.set_number(5, 0, 4)
    o_map.set_number(6, 3, 4)
    o_map.set_number(2, 5, 4)
    o_map.set_number(8, 8, 4)

    o_map.set_number(3, 1, 5)
    o_map.set_number(8, 4, 5)
    o_map.set_number(7, 7, 5)

    o_map.set_number(2, 2, 6)
    o_map.set_number(6, 6, 6)

    o_map.set_number(9, 0, 7)
    o_map.set_number(4, 3, 7)
    o_map.set_number(3, 5, 7)
    o_map.set_number(2, 8, 7)

    o_map.set_number(8, 1, 8)
    o_map.set_number(6, 4, 8)
    o_map.set_number(1, 7, 8)

    # Extra
    # o_map.set_number(2, 0, 0)

    # Speculative
    o_map.set_number(7, 0, 3)


    # Another map
    o_map2 = SudokuMap(9, 9, o_color=o_color)
    o_map2.set_number(i_number=5, i_x=0, i_y=0)
    o_map2.set_number(i_number=9, i_x=5, i_y=0)

    o_map2.set_number(i_number=7, i_x=2, i_y=1)
    o_map2.set_number(i_number=2, i_x=7, i_y=1)

    o_map2.set_number(i_number=2, i_x=0, i_y=2)
    o_map2.set_number(i_number=3, i_x=4, i_y=2)
    o_map2.set_number(i_number=1, i_x=5, i_y=2)
    o_map2.set_number(i_number=9, i_x=7, i_y=2)

    o_map2.set_number(i_number=7, i_x=0, i_y=3)
    o_map2.set_number(i_number=1, i_x=2, i_y=3)
    o_map2.set_number(i_number=6, i_x=3, i_y=3)
    o_map2.set_number(i_number=9, i_x=4, i_y=3)
    o_map2.set_number(i_number=4, i_x=8, i_y=3)

    o_map2.set_number(i_number=1, i_x=4, i_y=4)

    o_map2.set_number(i_number=6, i_x=0, i_y=5)
    o_map2.set_number(i_number=7, i_x=4, i_y=5)
    o_map2.set_number(i_number=4, i_x=5, i_y=5)
    o_map2.set_number(i_number=3, i_x=6, i_y=5)
    o_map2.set_number(i_number=1, i_x=8, i_y=5)

    o_map2.set_number(i_number=5, i_x=1, i_y=6)
    o_map2.set_number(i_number=3, i_x=3, i_y=6)
    o_map2.set_number(i_number=6, i_x=4, i_y=6)
    o_map2.set_number(i_number=8, i_x=8, i_y=6)

    o_map2.set_number(i_number=6, i_x=1, i_y=7)
    o_map2.set_number(i_number=7, i_x=6, i_y=7)

    o_map2.set_number(i_number=9, i_x=3, i_y=8)
    o_map2.set_number(i_number=3, i_x=8, i_y=8)

    # Extra help while not implemented the best algorithm
    # =============================================================================================================
    # |     5     ¦ 148       ¦ 48        |     7     ¦     2     ¦     9     | 148       ¦     3     ¦     6     |
    # -------------------------------------------------------------------------------------------------------------
    # | 13489     ¦ 13489     ¦     7     | 48        ¦ 48        ¦     6     | 148       ¦     2     ¦     5     |
    # -------------------------------------------------------------------------------------------------------------
    # |     2     ¦ 48        ¦     6     |     5     ¦     3     ¦     1     | 48        ¦     9     ¦     7     |
    # =============================================================================================================
    # |     7     ¦ 38        ¦     1     |     6     ¦     9     ¦ 358       |     2     ¦ 58        ¦     4     |
    # -------------------------------------------------------------------------------------------------------------
    # | 348       ¦ 2348      ¦ 3458      | 28        ¦     1     ¦ 358       |     6     ¦     7     ¦     9     |
    # -------------------------------------------------------------------------------------------------------------
    # |     6     ¦ 289       ¦ 589       | 28        ¦     7     ¦     4     |     3     ¦ 58        ¦     1     |
    # =============================================================================================================
    # | 14        ¦     5     ¦     2     |     3     ¦     6     ¦     7     |     9     ¦ 14        ¦     8     |
    # -------------------------------------------------------------------------------------------------------------
    # | 3489      ¦     6     ¦ 3489      |     1     ¦ 458       ¦ 58        |     7     ¦ 45        ¦     2     |
    # -------------------------------------------------------------------------------------------------------------
    # | 148       ¦     7     ¦ 48        |     9     ¦ 458       ¦     2     | 145       ¦     6     ¦     3     |
    # =============================================================================================================
    # By best algorithm I mean that the last in the middle vertical quadrant from the top right horizontally,
    # only 5 can be in a column. That clarifies that 5 must go to the other column in last quadrant, first column. Coord 6x8
    # o_map2.set_number(i_number=5, i_x=6, i_y=8)
    # ERROR traces from a bug fixed to mentioned during the code review
    # Surprisingly this fails
    # > Leaving scan for 8 in row1
    # V Scanning for removing 8 in col 4
    # V Removed 8 From: 4 7 [5, 8] Pending: [5]
    # Found 5 From: 4 7
    #
    # > Scanning for removing 5 in row 7
    # > Removed 5 From: 5 7 [5, 8] Pending: [8]
    # > Found 8 From: 5 7
    #
    # > Scanning for removing 8 in row 7
    # > Removed 8 From: 0 7 [3, 8] Pending: [3]
    # > Found 3 From: 0 7

    o_map = o_map2

    print(o_map.get_map_drawing_as_string())

    b_changes_found = True
    while b_changes_found is True:
        b_changes_found = False

        for i_y in range(0, o_map.i_height):
            b_found = o_map.detect_and_remove_a_number_from_possibles_from_a_row(i_y=i_y)
            if b_found is True:
                print(o_map.get_map_drawing_as_string())

        for i_y in range(0, o_map.i_height):
            o_map.o_color.print_label("Scanning quadrants for row " + str(i_y))
            for i_number in range(1, 10):
                for i_x in range(0, o_map.i_width):
                    b_found, i_x_found, i_y_found = o_map.check_if_number_possibles_in_quadrant_is_unique(i_number_to_check=i_number, i_x=i_x, i_y=i_y)
                    if b_found is True:
                        # Search again
                        b_changes_found = True
                        o_map.remove_a_number_from_possibles_in_a_row(i_number_to_remove=i_number, i_y=i_y_found)
                        o_map.remove_a_number_from_possibles_in_a_column(i_number_to_remove=i_number, i_x=i_x_found)

                    b_found, i_x_found, i_y_found = o_map.check_if_number_possibles_in_row_is_unique(i_number_to_check=i_number, i_y=i_y)
                    if b_found is True:
                        b_changes_found = True
                        o_map.remove_a_number_from_possibles_in_a_column(i_number_to_remove=i_number, i_x=i_x_found)

                if b_changes_found is True:
                    print(o_map.get_map_drawing_as_string())

    # @TODO: Implement check if number in quadrant can only go to a column, to remove the non possible in that column from another quadrant
    # @TODO: Implement check if in a line only one number can go to a column.

    print(o_map.get_map_drawing_as_string())
    print(o_map.get_map_drawing_of_possibles_as_string())

The color library lib/colorutils.py:

from colorama import Fore, Back, Style , init


class ColorUtils:

    def __init__(self):
        # For Colorama on Windows
        init()

    def print_error(self, m_text, s_end="\n"):
        """
        Prints errors in Red.
        :param s_text:
        :return:
        """

        # If they pass numbers
        s_text = str(m_text)

        print(Fore.RED + s_text)
        print(Style.RESET_ALL, end=s_end)

    def print_success(self, m_text, s_end="\n"):
        """
        Prints errors in Green.
        :param s_text:
        :return:
        """

        # If they pass numbers
        s_text = str(m_text)
        print(Fore.GREEN + s_text)
        print(Style.RESET_ALL, end=s_end)

    def color_success(self, m_text):
        """
        Colors only this
        :param m_text:
        :return:
        """

        s_text = str(m_text)
        return Fore.GREEN + s_text + Fore.RESET

    def color_black(self, m_text):
        s_text = str(m_text)
        return Fore.BLACK + s_text + Fore.RESET

    def color_blue(self, m_text):
        s_text = str(m_text)
        return Fore.BLUE + s_text + Fore.RESET

    def color_red(self, m_text):
        s_text = str(m_text)
        return Fore.RED + s_text + Fore.RESET

    def color_yellow(self, m_text):
        s_text = str(m_text)
        return Fore.YELLOW + s_text + Fore.RESET

    def color_magenta(self, m_text):
        s_text = str(m_text)
        return Fore.MAGENTA + s_text + Fore.RESET

    def print_label(self, m_text, s_end="\n"):
        """
        Prints a label and not the end line
        :param s_text:
        :return:
        """

        # If they pass numbers
        s_text = str(m_text)

        print(Fore.BLUE + s_text, end="")
        print(Style.RESET_ALL, end=s_end)

    def return_text_blue(self, s_text):
        """
        Restuns a Text
        :param s_text:
        :return: String
        """
        s_text_return = Fore.BLUE + s_text + Style.RESET_ALL
        return s_text_return

Python Game Tic Tac Toe

I implemented this very simple game for my book Python 3 Exercises for Beginners.

Source Code available here:

https://gitlab.com/carles.mateo/python-classes/-/blob/main/2021-09-10/game_tic-tac-toe.py


class TicTacToe:

    def __init__(self):
        self.a_a_s_map = []
        self.generate_map()

    def generate_map(self):
        self.a_a_s_map = []

        for i_y in range(3):
            a_s_pos_x = [" ", " ", " "]
            self.a_a_s_map.append(a_s_pos_x)

    def get_map(self):
        s_map = ""

        s_map = s_map + "    1   2   3\n"
        s_map = s_map + "  -------------\n"
        for i_y in range(3):
            s_map = s_map + str(i_y + 1) + " |"
            for s_char in self.a_a_s_map[i_y]:
                s_map = s_map + " " + s_char + " |"
            s_map = s_map + "\n"
            s_map = s_map + "  -------------\n"

        return s_map

    def validate_move(self, s_char, i_x, i_y):
        """
        Validates the movement and updates the map
        :param s_char:
        :param i_x:
        :param i_y:
        :return: bool
        """
        i_x = i_x - 1
        i_y = i_y - 1

        if self.a_a_s_map[i_y][i_x] == " ":
            self.a_a_s_map[i_y][i_x] = s_char
            return True

        return False

    def check_win(self):
        for s_char in ["O", "X"]:

            # check horizontal
            for i_y in range(3):
                i_horizontal_match = 0
                for i_x in range(3):
                    if self.a_a_s_map[i_y][i_x] == s_char:
                        i_horizontal_match = i_horizontal_match + 1
                if i_horizontal_match == 3:
                    return True

            # Check vertical
            for i_x in range(3):
                i_vertical_match = 0
                for i_y in range(3):
                    if self.a_a_s_map[i_y][i_x] == s_char:
                        i_vertical_match = i_vertical_match + 1
                if i_vertical_match == 3:
                    return True

            # Check diagonal
            if self.a_a_s_map[1][1] == s_char:
                if self.a_a_s_map[0][0] == s_char and self.a_a_s_map[2][2] == s_char:
                    return True
                if self.a_a_s_map[0][2] == s_char and self.a_a_s_map[2][0] == s_char:
                    return True

        return False

    def check_stale(self):
        for i_y in range(3):
            for i_x in range(3):
                if self.a_a_s_map[i_y][i_x] == " ":
                    # Is not full
                    return False

        # We checked all and all were full
        return True


def get_from_keyboard(s_question, i_min, i_max):
    i_number = 0
    while True:
        s_answer = input(s_question)
        try:
            i_number = int(s_answer)
        except:
            print("Please, type a number")
            continue

        if i_number < i_min or i_number > i_max:
            print("Invalid value. Values should be between", i_min, "and", i_max)
            continue

        # Validations are Ok
        break

    return i_number


if __name__ == "__main__":
    o_tictactoe = TicTacToe()

    while True:

        s_map = o_tictactoe.get_map()
        print(s_map)

        while True:
            i_x = get_from_keyboard("Your move O for x: ", i_min=1, i_max=3)
            i_y = get_from_keyboard("Your move O for y: ", i_min=1, i_max=3)

            b_valid_move = o_tictactoe.validate_move("O", i_x, i_y)
            if b_valid_move is False:
                print("Invalid move")
                continue

            break

        s_map = o_tictactoe.get_map()
        print(s_map)
        b_check_win = o_tictactoe.check_win()
        if b_check_win is True:
            print("Player O wins!")
            exit(0)

        b_stale = o_tictactoe.check_stale()
        if b_stale is True:
            print("Nobody wins in war")
            exit(0)

        while True:
            i_x = get_from_keyboard("Your move X for x: ", i_min=1, i_max=3)
            i_y = get_from_keyboard("Your move X for y: ", i_min=1, i_max=3)

            b_valid_move = o_tictactoe.validate_move("X", i_x, i_y)
            if b_valid_move is False:
                print("Invalid move")
                continue

            break

        s_map = o_tictactoe.get_map()
        print(s_map)
        b_check_win = o_tictactoe.check_win()
        if b_check_win is True:
            print("Player X wins!")
            exit(0)

CSort multithread versus QuickSort with Java Source Code

Updated on 2017-04-04 12:58 Barcelona Time 1491303515:

  • A method writeValuesFromArrayListToDisk(String sFilename) has been introduced as per a request, to easily check that the data is properly sorted.
  • A silly bug in the final ArrayList generation has been solved. It was storing iCounter that was always 1 as this is not the compressed version, for supporting repeated numbers, of the algorithm. I introduced this method for the article, as it is not necessary for the algorithm as it is already sorted, and unfortunately I didn’t do a final test on the output. My fault.
  • Some JavaDoc has been updated

Past Friday I was discussing with my best friend about algorithms and he told me that hadoop is not fast enough, and about when I was in Amazon and as part of the test they asked me to defined an S3 system from the scratch, and I did using Java and multiple streams per file and per node (replication factor) and they told me that what I just created was the exact way their system works, and we ended talking about my sorting algorithm CSort, and he asked me if it could run in MultiThread. Yes, it is one of the advantages in front of QuickSort. Also it can run in multinode, different computers. So he asked me how much faster it would be a MultiThread version of CSort, versus a regular QuickSort.

Well here is the answer with 500 Million of registers, with values from 1 to 1000000, and deduplicating.

2017-03-26 18:50:41 CSort time in seconds:0.189129089
2017-03-26 18:51:47 QuickSort cost in seconds:61.853190885

That’s Csort is 327 times faster than QuickSort!. In this example and with my busy 4 cores laptop. In my 8 cores computer it is more than 525 times faster. Imagine in a Intel Xeon Server with a 64 cores!.

How is it possible? The answer is easy, it has O(n) complexity. I use linear access.

This depends on your universe of Data. Please read my original posting about CSort here, that explains it on detail.

Please note that CSort with compression is also available for keeping duplicated values and also saving memory (space) and time, with equally totally astonishing results.

Please note that in this sample I first load the values to an Array, and then I work from this. This is just to avoid bias by discarding the time of loading the data from disk, but, in the other article you have samples where CSort sorts at the same time that loads the data from disks. I have a much more advanced algorithm that self allocates the memory needed for handling an enormous universe of numbers (big numbers and small with no memory penalty), but I’m looking forward to discuss this with a tech giant when it hires me. ;) Yes, I’m looking for a job.

In my original article I demonstrated it in C and PHP, this time here is the code in Java. It uses the MT Notation.

You can download the file I used for the tests from here:

Obviously it runs much more faster than hashing. I should note that hashing and CSorting with .containsKey() is faster than QuickSorting. (another day I will talk about sorting Strings faster) ;)

/*
 * (c) Carles Mateo blog.carlesmateo.com
 * Proof of concept of CSort, with multithread, versus QuickSort
 * For the variables notation MT Notation is used.
 */
package com.carlesmateo.blog;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;

/**
 * @author carles mateo
 */
public class CSortMultiThread extends Thread {
    // Download the original file from the blog
    public static final int piNUM_REGISTERS_IN_FILE = 50000000;
    // Max value found, to optimize the memory used for CSort
    // Note that CSort can be implemented in the read from file mechanism
    // in order to save memory (space)
    public static int piMaxValue = 0;
    // The array containing the numbers read from disk
    public static int[] paiNumbers;
    // The array used by CSort (if not using direct loading from disk)
    public static int[] paiNumbersCsorted;
    // Final ArrayList Sorted. CSort and QuickSort finally fullfil this
    public static ArrayList<Integer> pliNumbers = new ArrayList<>();
   
    // For the Threads
    private Thread oT;
    private String sThreadName;
    private int piStart;
    private int piEnd;
    private boolean bFinished = false;
   
    CSortMultiThread (String name, int iStart, int iEnd) {
        sThreadName = name;
        piStart = iStart;
        piEnd = iEnd;
        writeWithDateTime("Creating " +  sThreadName );
    }
   
    public void run() {
        writeWithDateTime("Running " +  sThreadName + " to sort from " + piStart + " to " + piEnd);
        int iCounter;
        int iNumber;        

        for (iCounter=piStart; iCounter < piEnd; iCounter++) {
            iNumber = paiNumbers[iCounter];
            paiNumbersCsorted[iNumber] = 1;
        }          

      System.out.println("Thread " +  sThreadName + " exiting.");
      bFinished = true;
    }
   
    public void start () {
        writeWithDateTime("Starting " +  sThreadName );
        if (oT == null) {
            oT = new Thread (this, sThreadName);
            oT.start ();
        }
    }
    /**
     * Write values to Disk to demonstrate that are sorted ;)
     * @param sFilenameData 
     */
    private static void writeValuesFromArrayListToDisk(String sFilenameData) {
        ObjectOutputStream out = null;
        int iCounter;
        try {
            out = new ObjectOutputStream(new FileOutputStream(sFilenameData));
            
            for (iCounter=0; iCounter<pliNumbers.size(); iCounter++) {
                out.writeChars(pliNumbers.get(iCounter).toString() + "\n");
            }
            
            // To store the object instead
            //out.writeObject(pliNumbers);
            
        } catch (IOException e) {
            System.out.println("I/O Error!");
            e.printStackTrace();
            displayHelpAndQuit(10);
        } finally {
            if (out != null) {
                try {
                    out.close();    
                } catch (IOException e) {
                    System.out.println("I/O Error!");
                    e.printStackTrace();
                    displayHelpAndQuit(10);
                }   
            }
        }
    }
   
    /** 
     *  Reads the data from the disk. The file has 50M and we will be duplicating
     *  to get 500M registers.
     *  @param sFilenameData 
     */
    private static void readValuesFromFileToArray(String sFilenameData) {

        BufferedReader oBR = null;
        String sLine;
        int iCounter = 0;
        int iRepeat;
        int iNumber;
        
        // We will be using 500.000.000 items, so dimensionate the array
        paiNumbers = new int[piNUM_REGISTERS_IN_FILE * 10];

        try {

            oBR = new BufferedReader(new FileReader(sFilenameData));

            while ((sLine = oBR.readLine()) != null) {
                for (iRepeat = 0; iRepeat < 10; iRepeat++) {
                    int iPointer = (piNUM_REGISTERS_IN_FILE * iRepeat) + iCounter;
                    iNumber = Integer.parseInt(sLine);
                    paiNumbers[iPointer] = iNumber;
                    if (iNumber > piMaxValue) {
                        piMaxValue = iNumber;
                    }
                }                
                
                iCounter++;
            }
            
            if (iCounter < piNUM_REGISTERS_IN_FILE) {
                write("Warning... only " + iCounter + " values were read");
            }

        } catch (FileNotFoundException e) {
            System.out.println("File not found! " + sFilenameData);
            displayHelpAndQuit(100);
        } catch (IOException e) {
            System.out.println("I/O Error!");
            e.printStackTrace();
            displayHelpAndQuit(10);
        } finally {
            if (oBR != null) {
                try {
                    oBR.close();
                } catch (IOException e) {
                    System.out.println("I/O Error!");
                    e.printStackTrace();
                    displayHelpAndQuit(10);
                }
            }
        }        
    }
    
    private static String displayHelp() {
        String sHelp = "Help\n" +
                "====\n" +
                "Csort from Carles Mateo blog.carlesmateo.com\n" +
                "\n" +
                "Proof of concept of the fast load algorithm\n" +
                "\n";
        
        return sHelp;
    }
    
    /**
     * Displays Help Message and Quits with and Error Level
     * Errors:
     *  - 1   - Wrong number of parameters
     *  - 10  - I/O Error
     *  - 100 - File not found
     * @param iErrorLevel 
     */
    private static void displayHelpAndQuit(int iErrorLevel) {
        System.out.println(displayHelp());
        System.exit(iErrorLevel);
        
    }
    
    // This is QuickSort from vogella http://www.vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html
    public static void sort() {
        int piNumber = paiNumbers.length;
        quicksort(0, piNumber - 1);        
    }
    
    private static void quicksort(int low, int high) {
        int i = low, j = high;
        // Get the pivot element from the middle of the list
        int pivot = paiNumbers[low + (high-low)/2];

        // Divide into two lists
        while (i <= j) {
            // If the current value from the left list is smaller then the pivot
            // element then get the next element from the left list
            while (paiNumbers[i] < pivot) {
                i++;
            }
            // If the current value from the right list is larger then the pivot
            // element then get the next element from the right list
            while (paiNumbers[j] > pivot) {
                j--;
            }

            // If we have found a values in the left list which is larger then
            // the pivot element and if we have found a value in the right list
            // which is smaller then the pivot element then we exchange the
            // values.
            // As we are done we can increase i and j
            if (i <= j) {
                exchange(i, j);
                i++;
                j--;
            }
        }
        // Recursion
        if (low < j)
            quicksort(low, j);
        if (i < high)
            quicksort(i, high);
    }

    private static void exchange(int i, int j) {
        int temp = paiNumbers[i];
        paiNumbers[i] = paiNumbers[j];
        paiNumbers[j] = temp;
    }
    
    /** 
     * We want to remove duplicated values
     */
    private static void removeDuplicatesFromQuicksort() {
        int iCounter;
        int iOldValue=-1;
        int iNewValue;
        
        for (iCounter=0; iCounter<paiNumbers.length; iCounter++) {
            iNewValue = paiNumbers[iCounter];
            if (iNewValue != iOldValue) {
                iOldValue = iNewValue;
                pliNumbers.add(iNewValue);
            }
        }
    }
// End of vogella QuickSort code

    /**
     * Generate the final Array
     */
    private static void copyFromCSortToArrayList() {
        int iCounter;
        int iNewValue;
        
        for (iCounter=0; iCounter<=piMaxValue; iCounter++) {
            iNewValue = paiNumbersCsorted[iCounter];
            if (iNewValue > 0) {
                pliNumbers.add(iCounter);
            }
        }
    }

    /**
     * Write with the date
     * @param sText 
     */
    private static void writeWithDateTime(String sText) {
        DateFormat oDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        Date oDate = new Date();
        String sDate = oDateFormat.format(oDate);
        write(sDate + " " + sText);
    }
    
    /**
     * Write with \n
     * @param sText 
     */
    private static void write(String sText) {
        System.out.println(sText + "\n");
    }    
   
    public static void main(String args[]) throws InterruptedException {
        // For Profiling
        long lStartTime;
        double dSeconds;
        long lElapsedTime;
        
        int iThreads = 8;
        int iRegistersPerThread = piNUM_REGISTERS_IN_FILE / iThreads;
        CSortMultiThread[] aoCSortThreads = new CSortMultiThread[iThreads];
        
        writeWithDateTime("CSort MultiThread proof of concept by Carles Mateo");
        writeWithDateTime("Reading values from Disk...");
        readValuesFromFileToArray("/home/carles/Desktop/codi/java/carles_sort.txt");
        writeWithDateTime("Readed");

        writeWithDateTime("Total values to sort de deduplicate " + paiNumbers.length);
        writeWithDateTime("The max value between the Data is " + piMaxValue);
        paiNumbersCsorted = new int[piMaxValue + 1];
                
        writeWithDateTime("Performing CSort with removal of duplicates");
        lStartTime = System.nanoTime();
        for (int iThread=0; iThread < iThreads; iThread++) {
            int iStart = iThread * iRegistersPerThread;
            int iEnd = ((iThread + 1) * iRegistersPerThread) - 1;
            if (iThread == (iThreads -1)) {
                // Last thread grabs the remaining. 
                // For instance 100/8 = 12 so each Thread orders 12 registers,
                // but last thread orders has 12 + 4 = 16
                iEnd = piNUM_REGISTERS_IN_FILE -1 ;
            }
            CSortMultiThread oThread = new CSortMultiThread("Thread-" + iThread, iStart, iEnd);
            oThread.start();
            
            aoCSortThreads[iThread] = oThread;
        }       
        
        boolean bExit = false;
        while (bExit == false) {
            bExit = true;
            for (int iThread=0; iThread < iThreads; iThread++) {
                if (aoCSortThreads[iThread].bFinished == false) {
                    bExit = false;
                    // Note: 10 milliseconds. This takes some CPU cycles, but we need
                    // to ensure that all the threads did finish.
                    sleep(10);
                    continue;
                }
            }
        }
        writeWithDateTime("Main loop ended");
                
        writeWithDateTime("Copy to the ArrayList");
        copyFromCSortToArrayList();
        
        writeWithDateTime("The final array contains " + pliNumbers.size());
        
        lElapsedTime = System.nanoTime() - lStartTime;
        dSeconds = (double)lElapsedTime / 1000000000.0;
        writeWithDateTime("CSort time in seconds:" + dSeconds);

        writeWithDateTime("Writing values to Disk...");
        writeValuesFromArrayListToDisk("/home/carles/Desktop/codi/java/carles_sort-csorted.txt");

        // Reset the ArrayList
        pliNumbers = new ArrayList<>();
        
        lStartTime = System.nanoTime();
        /** QuickSort begin **/
        writeWithDateTime("Sorting with QuickSort");
        sort();
        writeWithDateTime("Finished QuickSort");
        
        writeWithDateTime("Removing duplicates from QuickSort");
        removeDuplicatesFromQuicksort();
        writeWithDateTime("The final array contains " + pliNumbers.size());
        lElapsedTime = System.nanoTime() - lStartTime;
        dSeconds = (double)lElapsedTime / 1000000000.0;
        
        writeWithDateTime("QuickSort cost in seconds:" + dSeconds);
    }
}

The complete traces:

run:
2017-03-26 19:28:13 CSort MultiThread proof of concept by Carles Mateo
2017-03-26 19:28:13 Reading values from Disk...
2017-03-26 19:28:39 Readed
2017-03-26 19:28:39 Total values to sort de deduplicate 500000000
2017-03-26 19:28:39 The max value between the Data is 1000000
2017-03-26 19:28:39 Performing CSort with removal of duplicates
2017-03-26 19:28:39 Creating Thread-0
2017-03-26 19:28:39 Starting Thread-0
2017-03-26 19:28:39 Creating Thread-1
2017-03-26 19:28:39 Starting Thread-1
2017-03-26 19:28:39 Running Thread-0 to sort from 0 to 6249999
2017-03-26 19:28:39 Creating Thread-2
2017-03-26 19:28:39 Starting Thread-2
2017-03-26 19:28:39 Running Thread-1 to sort from 6250000 to 12499999
2017-03-26 19:28:39 Creating Thread-3
2017-03-26 19:28:39 Running Thread-2 to sort from 12500000 to 18749999
2017-03-26 19:28:39 Starting Thread-3
2017-03-26 19:28:39 Creating Thread-4
2017-03-26 19:28:39 Starting Thread-4
2017-03-26 19:28:39 Running Thread-3 to sort from 18750000 to 24999999
2017-03-26 19:28:39 Creating Thread-5
2017-03-26 19:28:39 Running Thread-4 to sort from 25000000 to 31249999
2017-03-26 19:28:39 Starting Thread-5
2017-03-26 19:28:39 Creating Thread-6
2017-03-26 19:28:39 Starting Thread-6
2017-03-26 19:28:39 Running Thread-5 to sort from 31250000 to 37499999
2017-03-26 19:28:39 Creating Thread-7
2017-03-26 19:28:39 Starting Thread-7
2017-03-26 19:28:39 Running Thread-6 to sort from 37500000 to 43749999
2017-03-26 19:28:39 Running Thread-7 to sort from 43750000 to 49999999

Thread Thread-0 exiting.
Thread Thread-2 exiting.
Thread Thread-1 exiting.
Thread Thread-6 exiting.
Thread Thread-7 exiting.
Thread Thread-5 exiting.
Thread Thread-4 exiting.
Thread Thread-3 exiting.
2017-03-26 19:28:39 Main loop ended

2017-03-26 19:28:39 Copy to the ArrayList
2017-03-26 19:28:39 The final array contains 1000001
2017-03-26 19:28:39 CSort time in seconds:0.189129089

2017-03-26 19:28:39 Sorting with QuickSort
2017-03-26 19:29:40 Finished QuickSort
2017-03-26 19:29:40 Removing duplicates from QuickSort
2017-03-26 19:29:41 The final array contains 1000001
2017-03-26 19:29:41 QuickSort cost in seconds:61.853190885

BUILD SUCCESSFUL (total time: 1 minute 28 seconds)