Analyzing the USACO Tic-Tac-Toe Problem: Using Sets to avoid duplicates 🐄

Still on my Learn to Code by Solving Problems binge, and I found this problem quite interesting, so I decided to share my solution and thought process behind it.
The USACO Tic-Tac-Toe problem is a variation of the classic game, with cows claiming squares and competing for victories individually or as pairs. The full text can be found here.

The reason I decided to write this up is because initially I had solved it in a way that should have worked (to my mind), but didn’t (around 50% of the test cases failed). I couldn’t quite figure out why and had a look at the solution provided. Turned out that the magic ingredient I was missing was sorted tuples.

Problem Overview 📋

Farmer John’s cows play a modified version of tic-tac-toe on a 3×3 board. Each square is marked by the initial of the cow who claims it, and the goal is to determine:

1. How many individual cows can claim a row, column, or diagonal as their own.
2. How many distinct pairs of cows can claim a row, column, or diagonal where both cows contribute to the win.

The challenge lies in correctly identifying the unique winners while accounting for all possible rows, columns, and diagonals. Obviously I used sets for this.

Solution Approach 🔍

Step 1: Input Representation

The input is represented as a list of strings, each containing three characters (representing rows of the board). This makes it easy to work with rows directly and derive columns and diagonals.

with open('tttt.in', 'r') as input_file:
board = [line.strip() for line in input_file]  # Represent board as a list of strings

Step 2: Extract Rows, Columns, and Diagonals 🔀

Using the board representation, we derive:

- Row Sets: Each row is converted into a set, containing unique characters in that row.
- Column Sets: Each column is constructed by iterating over the rows and collecting characters at the same index.
- Diagonal Sets: The two diagonals are constructed by indexing characters along their respective positions.

row_sets = [set(row) for row in board]
column_sets = [set(board[row][col] for row in range(3)) for col in range(3)]
diagonal_1 = set(board[i][i] for i in range(3))
diagonal_2 = set(board[i][2 - i] for i in range(3))
diagonal_sets = [diagonal_1, diagonal_2]

This way we extract all sets relevant to us for our analysis of potential winners and winning teams.

Step 3: Combine All Sets 🔗

We merge the row, column, and diagonal sets into a single list for unified processing:

all_sets = row_sets + column_sets + diagonal_sets

Using Sets to Identify Winners 🏆

Step 4: Single-Cow Winners

To identify individual cow winners, we check if a set contains only one unique element. Such a set implies a single cow has claimed the entire row, column, or diagonal.

winners1_set = set()
for s in all_sets:
if len(s) == 1:
winners1_set.add(tuple(sorted(s)))

Here, we use tuple(sorted(s)) to ensure uniform representation of the cow’s identity, even though there’s only one element in the set. I don’t think this is actually necessary for the one winner case, but I still used sorted tuples here for consistency’s sake.

Step 5: Two-Cow Team Winners 🐄🐄

For two-cow team winners, we check if a set contains exactly two unique cows. This ensures that (‘A’, ‘X’) and (‘X’, ‘A’) are not interpreted as 2 different sets, which was happening in my initial solution, leading to it failing the judge check.

winners2_set = set()
for s in all_sets:
if len(s) == 2:
winners2_set.add(tuple(sorted(s)))

Writing Output 📝

Finally, print the single-cow and team results to output.

with open('tttt.out', 'w') as output_file:
output_file.write(f"{len(winners1_set)}\n")
output_file.write(f"{len(winners2_set)}")

Final Thoughts 💭

This solution is my attempt at using Python’s data structures to solve the tic-tac-toe problem efficiently. I liked the extra challenge of making sure that there are no duplicate sets, which led me to dig a bit deeper and to arrive at the sorted tuple solution.

Do you have alternative approaches or optimizations for this task? One of the solutions written in C on the USACO site uses a brute-force approach simply looping through rows, columns and diagonals, which avoids using high order concepts like set, and is likely a lot more efficient because of this.