Algorithm that finds 4 "O"s or 4 "X"s on a diagonal, horizontal, or vertical

Question

My algorithm homework revolves around matching 4 "O"'s or 4 "X"'s on a diagonal, horizontal, or vertical. Hopefully that makes sense...

This is what the data looks like below (2D tuples) where I need to recreate a function that returns "O" or "X" or False depending on what is found.

xwins = ((None, None, None, None, None, None, None),
         (None, None, None, None, None, None, None),
         (None, None, None, None, "X" , None, None),
         (None, None, None, "X" , "O" , "O", None),
         (None, "O" , "X" , "X" , "O" , "X", None),
         ("O" , "X" , "O" , "O" , "O" , "X" , "X"))

owins = ((None, None, None, None, None, None, None),
         (None, None, None, None, None, None, None),
         ("O" , "O" , "O" , "O" , None, None, None),
         ("O" , "X" , "X" , "X" , None, None, None),
         ("X" , "X" , "X" , "O" , "X" , None, None),
         ("X" , "O" , "O" , "X" , "O" , None, None))

nowins =(("X" , "X" , None, None, None, None, None),
         ("O" , "O" , None, None, None, None, None),
         ("O" , "X" , "O" , "O" , None, "O" , "O" ),
         ("O" , "X" , "X" , "X" , None, "X" , "X" ),
         ("X" , "X" , "X" , "O" , "X" , "X" , "O" ),
         ("X" , "O" , "O" , "X" , "O" , "X" , "O" ))

Can someone give me a tip on if I should change the data structure? Originally I went at this creating a numpy array out of the data but am having a hard time dealing with the None items in numpy as well as trying to convert the X and O strings to an int...and now I don't know what to do...need to start over from scratch.

Would anyone have any tips or pseudo-code I can glance at, not solve this but some tips would be useful what data structure to use and methods to the madness, ha. What sort of search algorithm would the solution be considered? Not a lot of wisdom here...

Answer 1

As suggested in comments, the task can be done directly without having to modify values to ints or change the structure of the input.

Input: A tuple A of n rows and m columns.
Output: Whether there is matching $4$ "O"'s or 4 "X"'s on a diagonal, horizontal, or vertical line.
Procedure:

# horizontal lines
For i in range(n):
    For j in range(m-3):
        Find if A[i][j], A[i][j+1], A[i][j+2], A[i][j+3] are 4 "0"s or 4 "X"s. Return accordingly if yes.

# vertical lines
For j in range(m):
    For i in range(n-3):
        Find if A[i][j], A[i+1][j], A[i+2][j], A[i+3][j] are 4 "0"s or 4 "X"s. Return accordingly if yes.

# diagonal lines
For i in range(n-3):
    For j in range(m-3):
        Find if A[i][j], A[i+1][j+1], A[i+2][j+2], A[i+3][j+3] are 4 "0"s or 4 "X"s. Return accordingly if yes.

# other diagonal lines
For i in range(3, n):
    For j in range(m-3):
        Find if A[i][j], A[i-1][j+1], A[i-2][j+2], A[i-3][j+3] are 4 "0"s or 4 "X"s. Return accordingly if yes.

Return False, since no $4$ "O"'s nor 4 "X"'s has been found.

One common difficulty is how we can figure out the ranges of the possible indices of the starting "O" or "X".

The basic technique is, for example, if A[i-3][j+3] will be used, then it means "0 <= i-3 < n" and "0 <= j+3 < m", which means "3 <= i < n+3" and "-3 <= j < m -3". Together with "0 <= i < n" and "0 <= j < m", we have "3 <= i < n" and "0 <= j < m-3". That is how we can write "i in range(3, n)" and "j in range(m-3)" in the case of "other diagonal lines".

Answer 2

There is a way, with a little pre-processing that you can do each test in a constant $O(1)$ number of operations, assuming that you have large enough numbers that can store many bits.

---

You can actually store the values as bits:

• Store X's as 11
• Store O's as 00
• Store None as 01.

We will store the entire table as a string of bits this way, with padding depending on whether there are more rows or columns. The idea is that, to detect a row of X's, you will shift the table to the right. For example, suppose our table is the following:

$$\begin{array}{ccc} X & X & O \\ X & X & \text{None} \\ O & O & \text{None} \end{array}$$

We encode the table as the bits:

$$\begin{array}{ccc} 11 & 11 & 00 \\ 11 & 11 & 01 \\ 00 & 00 & 01 \end{array}$$

We have to then pad the table with extra "None" values (or 01):

$$\begin{array}{cccc} 11 & 11 & 00 & 01 \\ 11 & 11 & 01 & 01 \\ 00 & 00 & 01 & 01 \\ \end{array}$$

Now, the next step is to "wrap" the 0's and 1's around, to create a single string. For example, the table above becomes

$$\begin{array}{ccc} \underbrace{11 \; 11 \; 00 \; 01}_\text{row 1} & \underbrace{11 \; 11 \; 01 \; 01}_\text{row 2} & \underbrace{00 \; 00 \; 01 \; 01}_\text{row 3} \\ \end{array}$$

Let's say we want to detect if there is a column with 2 O's in it. We first shift this bit string to the right by 2 bits, and perform a logical "and" or what is called conjunction:

$$\begin{array}{ccccc} 11 \; 11 \; 00 \; 01 & 11 \; 11 \; 01 \; 01 & 00 \; 00 \; 01 \; 01 & & \text{original string}\\ \land \; \land \; \land \; \land & \land \; \land \; \land \; \land & \land \; \land \; \land \; \land & & \\ 01 \; 11 \; 11 \; 00 & 01 \; 11 \; 11 \; 01 & 01 \; 00 \; 00 \; 01 & 01 & \text{shifted string}\\ \hline 11 \; 11 \; 11 \; 01 & 11 \; 11 \; 11 \; 01 & 01 \; 00 \; 01 \; 01 & 01 & \text{RESULT}\\ \end{array}$$

Then we perform a logical "or", also known as disjunction, with a string of all "10" values, which will convert the remaining "None" values to "11":

$$\begin{array}{ccccc} 11 \; 11 \; 11 \; 01 & 11 \; 11 \; 11 \; 01 & 01 \; 00 \; 01 \; 01 & 01 &\text{previous result}\\ \lor \; \lor \; \lor \; \lor & \lor \; \lor \; \lor \; \lor & \lor \; \lor \; \lor \; \lor & \lor & \\ 10 \; 10 \; 10 \; 10 & 10 \; 10 \; 10 \; 10 & 10 \; 10 \; 10 \; 10 & 10 & \text{row of "10"s}\\ \hline 11 \; 11 \; 11 \; 11 & 11 \; 11 \; 11 \; 11 & 11 \; 10 \; 11 \; 11 & 11 & \text{FINAL RESULT}\\ \end{array}$$

Finally, compare the bit string to a string of all "11" values. Note that there is a single zero in the string, which indicates that there are two "O" = "00" values next to each other.

To see how this works, we are taking bit values and performing some logic on them:

$$\begin{array}{c|c|c} \text{original value} & \text{value and "11"} & \text {next value and "10"} \\ \hline 00 & 00 & 01 \\ 01 & 01 & 11 \\ 11 & 11 & 11 \end{array}$$

To detect X = "11" values, we simply have to perform a logical and (conjunction) with "10":

$$\begin{array}{c|c} \text{original value} & \text{value and "10"} \\ \hline 00 & 00 \\ 01 & 00 \\ 11 & 10 \end{array}$$

Then we simply compare the string with a string of all zeros, and if there are any 1's in the string, we know that there are two X="11" values next to each other.

You can repeat this operation if there is more padding. This will allow you to compare 3, 4, or more positions in a line.

For different directions, simply pad and shift accordingly.

---

One point to make is that you can limit the number of extra padding bits slightly. If there are more rows than columns, you want to pad to the left and to the right, and below. Then you can test both diagonal directions by shifting down, since there will be extra padding below.

Otherwise, pad above, below, and to the right. Then test both diagonal operations by shifting right, since there will be extra padding on the right.

Answer 3

I realized that you can actually detect a line of at least $n$ "X" values in $\Theta \left( \lceil \log{(n)} \rceil \right)$ operations, and the same with $n$ "O" values.

---

The idea is to keep two "tables", and you perform tests by bit shifts. In one table, you record a bit 1 for every "X" value, and a 0 for "O" values, "None", and padding. In the other table, you record a bit 1 for every "O" value, and a 0 for "X" values, "None", and padding. Now we just have to detect $n$ ones in a row, either horizontally, vertically, or diagonally.

So on to the task of detecting $n$ ones in a row. We will first show how to detect at least $2^y$ bits in a row that are all equal to 1.

Say the string has a sequence of $2^y$ ones (in a row). If we shift the sequence by $2^{y-1}$ and take the bitwise "and" operation, logical conjunction, we will get a sequence that has at least $2^{y-1}$ ones in a row. Here is this situation:

$$\begin{array}{cccc} 111 \dots 111 & 111 \dots 111 & ??? \dots ??? & \text{original bit string}\\ \land & \land & \land \\ ??? \dots ??? & 111 \dots 111 & 111 \dots 111 & \text{shifted bit string}\\ \hline ??? \dots ??? & 111 \dots 111 & ??? \dots ??? & \text{RESULT} \end{array}$$

...Here we don't care about the bits that are question marks. The takeaway is that the middle bits will be all ones, and that there are exactly $2^{y-1}$ of them in the middle. If any of the rightmost $2^{y-1}$ bits are zero, then the top bit string will force one of the bits in the middle of the result to be zero. If any of the leftmost $2^{y-1}$ bits are zero, the bottom bit string will force at least one of the bits in the middle result to be zero.

So now we have a bit string that will contain $2^{y-1}$ bits in a row if and only if the original bit string contained at least $2^y$ bits in a row. So now we repeat this step by logical conjunction with (the result string shifted by $2^{y-2}$. So we use a loop to do this until we are left with a single bit as the result. It is 1 if and only if there were at least $2^y$ 1's in a row in the original bit string.

This only works if there are at least $2^y$ 1's in a row, for some $y$. So how do we use this for other values?

Say we have $n = 2^y + c$ for some $c$. We first modify the bit string by turning $2^y$ ones into $2^y$ zeros.

The function essentially adds 0 to each side of a string of ones while shortening the string by 1, then 00 to each string of ones while shortening the string by another 2 ones, then 0000 by shortening the string by another 4 ones, etc.

To do this, observe the general step:

$$\begin{array}{cc} 00001111110000???? & \text{original bit string}\\ 000000001111110000 & \text{shifted bit string}\\ \hline 000000001100000000 & \text{RESULT} \end{array}$$

After we have added enough zeros to the string, we proceed similarly to the task when there are (possibly) $2^y$ ones in a row. Assume that we are testing for at least $n = 2^y+c$ ones in a row. We will have already switched $2^{y-1}$ ones into zeros, so we are left with $n_1 = 2^{y-1} + c$ or more ones. We will "half" the number of (possible) ones. We do this by shifting by $\lfloor n_1 / 2 \rfloor$ and conjoining the values, so that we are left with $n_2 = \lfloor n_1 / 2 \rfloor$ or more possible ones. Then we proceed like the last step, we shift by $\lfloor n_2 / 2 \rfloor$ and conjoin. Repeat until there is only one value left, similarly to above.

The function of padding with zeros takes $\Theta \left( \lceil \log{(n)} \rceil \right)$ operations, and the combining of possible ones also takes time $\Theta \left( \lceil \log{(n)} \rceil \right)$, so the total time is $\Theta \left( \lceil \log{(n)} \rceil \right)$.

---

The rest of the algorithm functions in a way similar to my other answer. If you want to find only the rows that have exactly $n$ values in a row, find at least $n$ values in a row, and subtract the result with at least $n-1$ values in a row.

Answer 4

Final Answer in Python which could probably be written better:

def check_winner(A):
    
    n = 6 # rows
    m = 6 # columns

    Os = ["O","O","O","O"]
    Xs = ["X","X","X","X"]

    # horizontal lines
    row_check = []
    for i in range(n):
        for j in range(m-2):

            row_check.append(A[i][j])
            row_check.append(A[i][j+1])
            row_check.append(A[i][j+2])
            row_check.append(A[i][j+3])
            
            if row_check == Os:
                return "O"
            
            if row_check == Xs:
                return "X"

            row_check.clear()
        
    # vertical lines
    col_check = []
    for j in range(m + 1):       
        for i in range(n-2):
            
            col_check.append(A[i][j])
            col_check.append(A[i+1][j])
            col_check.append(A[i+2][j])
            
            #print(col_check)           

            if col_check == Os:
                return "O"
            
            if col_check == Xs:
                return "X"

            col_check.clear()
    
    # diagonal lines
    diag_check = []
    for i in range(3):
        for j in range(4):
            
            diag_check.append(A[i][j])
            diag_check.append(A[i+1][j+1])
            diag_check.append(A[i+2][j+2])
            diag_check.append(A[i+3][j+3])

            if diag_check == Os:
                return "O"
            
            if diag_check == Xs:
                return "X" 

            diag_check.clear()
 
    # diagonal lines
    diag_check2 = []
    for i in range(3):
        for j in range(4):
            
            diag_check2.append(A[i][j+3])
            diag_check2.append(A[i+1][j+2])
            diag_check2.append(A[i+2][j+1])
            diag_check2.append(A[i+3][j])
            
            if diag_check2 == Os:
                return "O"
            
            if diag_check2 == Xs:
                return "X" 

            diag_check2.clear()

#The code below tests your function on three Connect-4
#boards. Remember, the line breaks are not needed to create
#a 2D tuple; they're used here just for readability.
xwins = ((None, None, None, None, None, None, None),
         (None, None, None, None, None, None, None),
         (None, None, None, None, "X" , None, None),
         (None, None, None, "X" , "O" , "O", None),
         (None, "O" , "X" , "X" , "O" , "X", None),
         ("O" , "X" , "O" , "O" , "O" , "X" , "X"))

owins = ((None, None, None, None, None, None, None),
         (None, None, None, None, None, None, None),
         ("O" , "O" , "O" , "O" , None, None, None),
         ("O" , "X" , "X" , "X" , None, None, None),
         ("X" , "X" , "X" , "O" , "X" , None, None),
         ("X" , "O" , "O" , "X" , "O" , None, None))

nowins =(("X" , "X" , None, None, None, None, None),
         ("O" , "O" , None, None, None, None, None),
         ("O" , "X" , "O" , "O" , None, "O" , "O" ),
         ("O" , "X" , "X" , "X" , None, "X" , "X" ),
         ("X" , "X" , "X" , "O" , "X" , "X" , "O" ),
         ("X" , "O" , "O" , "X" , "O" , "X" , "O" ))
         
print(check_winner(xwins))
print(check_winner(owins))
print(check_winner(nowins))