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.

Introduction

When I decided it was time to develop a more formal understanding of algorithms, I turned to Grokking Algorithms by Aditya Y. Bhargava, published by Manning Publications in 2016. This book consistently came up in online recommendations as an approachable, beginner-friendly introduction to algorithms, and that’s exactly what I was looking for—a bird’s-eye view of the subject without diving too deeply into technical details.

I wanted a foundational understanding of algorithms that I could build on, and this book sure delivered. With just 11 chapters, it’s concise yet comprehensive, making it an excellent starting point for anyone who is, like me, new to algorithms.

Structure and Content

The book begins with foundational topics, like binary search and an introduction to Big O notation—an essential concept for understanding algorithm efficiency. It then progresses to more complex algorithms, including quicksort, Dijkstra’s algorithm, and binary trees. The final chapter introduces a few advanced algorithms, inviting readers to explore further if they’re interested.

The exercises scattered throughout the chapters also stood out to me. These aren’t overly complex, but are thoughtfully designed to test your understanding of the material. As a beginner, I found them both manageable and effective in reinforcing the concepts presented.

Writing Style and Visuals

The writing style is one of the book’s greatest strengths. It’s simple, engaging, and approachable without being condescending. The author strikes a perfect balance between clarity and charm, making what could be a dry topic genuinely interesting.

The visuals, however, are the highlight. Each algorithm is paired with clear, inviting illustrations that help explain the logic behind the code. They’re not just decorative—they’re functional and informative. For example, the diagrams for binary trees were instrumental in helping me grasp the concept and its applications, such as encryption.

These visuals make it easy to “grok,” or intuitively understand, even the more abstract ideas. For someone like me, whose university days are long behind them and who never formally studied algorithms, this made the book feel accessible and unintimidating.

My Learning Experience

This book did an excellent job of demystifying algorithms for me, particularly the building blocks like binary search, quicksort, and Big O notation.

That said, I found the theoretical examples for certain algorithms, like breadth-first search and Dijkstra’s algorithm, a bit abstract. While the book explains the logic behind these algorithms effectively, I would have appreciated more real-world coding examples to see how these concepts translate into solving real-world problems. However, I understand that adding such examples would have made the book longer and likely beyond its intended scope.

Strengths of the Book

• Approacheability: The book is beginner-friendly and perfect for those new to algorithms.
• Clarity: The writing is straightforward and avoids unnecessary complexity.
• Visuals: The illustrations are charming, engaging, and extremely effective in clarifying complex concepts.
• Conciseness: At just 11 chapters, it’s short enough to be approachable but still covers a wide range of topics.

Weaknesses of the Book

• Limited Real-World Examples: While the theoretical explanations are excellent, beginners might struggle to see how to apply some algorithms in practical scenarios, such as using graphs to solve real-world problems.
• Focus on Theory Over Practice: The exercises are helpful but limited in scope. More hands-on practice might have enhanced the learning experience.

That said, these points aren’t so much weaknesses as they are reflections of the book’s purpose—it’s an introductory work, and diving deeper would likely go beyond its intended audience.

Who Is This Book For?

This book is ideal for beginners and students looking for a gentle introduction to algorithms. It’s especially helpful for those who find academic texts intimidating or overly complex. If you’re just starting your journey with algorithms or want to revisit the basics in a friendly way, this book is an excellent choice.

Final Thoughts and Rating

I genuinely enjoyed Grokking Algorithms. It was engaging, fun and the furthest thing from boring. Every chapter left me excited to learn more, and the time I spent reading it felt like a worthwhile investment. For me, it served as a perfect springboard into more advanced works, such as Introduction to Algorithms by MIT Press.

Overall, I give Grokking Algorithms 5 out of 5 stars. It achieves exactly what it sets out to do—introducing beginners to the world of algorithms in an accessible and enjoyable way. If you’re just starting to explore algorithms, I highly recommend giving this book a try.

Exploring the Algorithm Behind Mirko’s Handshake Problem

Disclaimer: I have no idea why this problem is called “Misa” when the protagonist’s nme is “Mirko”. I can only assume that “misa” is maybe Czech for “mass”, as the problem is about shaking hands with people at church:)

Anyway, I really enjoyed this problem, and I want to explore the approach and logic behind solving a seating arrangement problem involving handshakes. The algorithm I came up with is designed to calculate two key values:

1. The number of existing handshakes in the seating arrangement.
2. The maximum additional handshakes possible if Mirko takes a seat optimally.

This solution employs a grid traversal algorithm with careful attention to boundary conditions, allowing it to work well for seating matrices of varying sizes.

l3. Problem Breakdown

The problem involves:

- A matrix of seats represented by `.` (empty) and `o` (occupied).
- Each person seated (`o`) can shake hands with adjacent seated individuals in the following directions: – Right, Bottom-right diagonal, Bottom, and Bottom-left diagonal for existing handshakes.
- Mirko, a potential new entrant, can create new handshakes if seated optimally. This requires considering all 8 possible directions.

Algorithm Methodology

This solution uses a brute-force approach with nested loops to traverse the matrix and calculate:

1. Existing Handshakes: By iterating over each seat and checking adjacent seats in four directions (to avoid double counting).
2. Optimal Handshakes for Mirko: By considering every empty seat (`.`) and calculating potential handshakes in all 8 directions.

The overall time complexity is O(rows × cols), as each seat in the matrix is visited once.

Key Functions and Their Roles

1. `rows_columns_input`:

- Parses user input to extract the number of rows and columns for the seating matrix.

2. `seat_matrix_input`:

- Constructs the seating matrix by taking input for each row and storing it as a list of characters.

3. `handshakes`:

- Traverses the matrix to count existing handshakes by examining the right, bottom-right, bottom, and bottom-left directions.
- Uses boundary checks to ensure the traversal doesn’t go out of bounds.

4. `mirko_handshakes`:

- Traverses the matrix to identify empty seats (`.`).
- For each empty seat, calculates the number of potential handshakes by examining all 8 directions.
- Keeps track of the maximum possible handshakes Mirko can achieve.

5. `main`:

- Orchestrates the overall solution:

Brute Force with Boundary Checks

A key aspect of this algorithm is how it handles boundary conditions during grid traversal. For example, when calculating existing handshakes in `handshakes`:

if j + 1 < cols and seat_matrix_input[i][j+1] == "o":
    handshakes += 1

This ensures the algorithm doesn’t attempt to access elements beyond the matrix boundaries. A similar approach is used in mirko_handshakes.

What Approach is Used?

This solution primarily uses grid traversal with nested loops:

Nested Loops for Grid Traversal: Each cell in the matrix is visited exactly once using two loops:

 for i in range(rows):
        for j in range(cols):

Directional Adjacency Checks: Adjacency is checked in specific directions using relative offsets (e.g., i + 1, j + 1 for bottom-right diagonal). Brute Force Search for Mirko’s potential seating: For Mirko’s seat placement, every empty seat is considered, and all 8 directions are checked to calculate potential handshakes. This is because I’m not yet smart enough to come up with anything better :D.

Strengths and Weaknesses

The strength of this approach is that it is pretty simple and foolproof. However, from my reading of “Introduction to Algorithms” I now know that potential improvements should always be considered, so here is one way I thought of to improve my solution:

Skipping Empty Rows or Columns: In theory, rows or columns without any o could be skipped to reduce unnecessary computations.

So, without further ado, here is the full code for the problem:

def rows_columns_input() -> list:    
    rows_columns = input().split(" ")
    return list(map(int, rows_columns))


def seat_matrix_input(rows: int) -> list:
    seat_matrix = []
    for _ in range(rows):
        seat_matrix_input = input()
        line = []
        for char in seat_matrix_input:
            line.append(char)
        seat_matrix.append(line)
    return seat_matrix

def handshakes(seat_matrix_input: list, rows: int, cols: int) -> int:
    handshakes = 0

    for i in range(rows):
        for j in range(cols):
            current_seat = seat_matrix_input[i][j]
            if current_seat == '.':
                continue
            if j + 1 < cols and seat_matrix_input[i][j+1] == "o":
                handshakes += 1
            if j + 1 < cols and i + 1 < rows and seat_matrix_input[i+1][j+1] == "o":
                handshakes += 1
            if i + 1 < rows and seat_matrix_input[i+1][j] == "o":
                handshakes += 1
            if j - 1 >= 0 and i + 1 < rows and seat_matrix_input[i+1][j-1] == "o":
                handshakes += 1

    return handshakes

def mirko_handshakes(seat_matrix_input: list, rows: int, cols: int) -> int:
    max_handshakes = 0

    for i in range(rows):
        for j in range(cols):
            handshakes = 0
            current_seat = seat_matrix_input[i][j]
            if current_seat == 'o':
                continue
            if j + 1 < cols and seat_matrix_input[i][j+1] == "o":
                handshakes += 1
            if j + 1 < cols and i + 1 < rows and seat_matrix_input[i+1][j+1] == "o":
                handshakes += 1
            if i + 1 < rows and seat_matrix_input[i+1][j] == "o":
                handshakes += 1
            if j - 1 >= 0 and i + 1 < rows and seat_matrix_input[i+1][j-1] == "o":
                handshakes += 1
            if j - 1 >= 0 and seat_matrix_input[i][j - 1] == "o":
                handshakes += 1
            if j - 1 >= 0 and i - 1 >= 0 and seat_matrix_input[i-1][j-1] == "o":
                handshakes += 1
            if i - 1>= 0 and seat_matrix_input[i - 1][j] == "o":
                handshakes += 1
            if i - 1 >= 0 and j + 1 < cols and seat_matrix_input[i -1][j - 1] == "o":
                handshakes += 1

            if handshakes > max_handshakes:
                max_handshakes = handshakes   

    return max_handshakes

def main():
    rows, cols = rows_columns_input()

    matrix = seat_matrix_input(rows)

    no_mirko_hand = handshakes(matrix, rows, cols)

    mirko_hand = mirko_handshakes(matrix, rows, cols)

    total_handshakes = no_mirko_hand + mirko_hand

    print(total_handshakes)

if __name__ == "__main__":
    main()

Introduction

The book I’m reviewing today is JavaScript Crash Course , authored by Nick Morgan and published by No Starch Press in 2024. It’s a relatively recent release and sits at 376 pages—making it a mid-length read. I picked up this book while starting my journey into learning JavaScript for web development. It came highly recommended by people on Reddit (where else would one look for such recommendations?), and since I’ve had great experiences with other No Starch Press titles, I decided to give it a try. Spoiler alert: I wasn’t disappointed! But also, this is a review written by a very green beginner to webdev, so if you are in any way experienced, you will likely not find the parts I describe as “challenging” actually “challenging”.

Book Structure and Content Overview

The book is divided into two main parts:

Part 1. Crash Course in JavaScript: The first part consists of nine chapters covering JavaScript fundamentals. This section introduces basic programming concepts, JavaScript syntax, and DOM manipulation.

Part 2. Project-Based Learning: The second part features three hands-on projects that showcase more advanced JavaScript capabilities:
• A Pong Game: A classic game coded entirely in JavaScript.
• Music Composition with JavaScript: An interesting and specialized project focused on creating music through code.
• GitHub API Visualization: A project that demonstrates how to interact with APIs and visualize data.

This structure works well, starting with the basics and then walking the reader through 3 very different and more complex projects. The fundamentals are covered thoroughly, and the projects give a taste of what you can do with JavaScript once you have the basics down.

Writing Style and Readability

The book is very well-written, with a clear and engaging style. Nick Morgan manages to inject a bit of humor throughout, making it a fun read without sacrificing clarity or conciseness. The explanations are thorough enough without going into excessive detail, making it easy to follow along even if you have just a basic understanding of programming concepts. I did have to look to other sources for more in-depth information on some of the material presented though. Nick also provides sample code for all exercises and projects on CodePen.

Strengths of the Book

One of the biggest strengths of JavaScript Crash Course is its engaging, accessible approach. It really lives up to its title—offering a quick yet comprehensive introduction to JavaScript basics, followed by practical examples that demonstrate what you can build with these new skills.

The projects are particularly well-done. They cover a range of topics and skills, from game development to API usage. This variety makes the book appealing to a broad audience, offering something for everyone. Even though the projects are challenging, they provide great inspiration and plenty of opportunities to experiment and customize, which I found to be quite fun and inspiring.

Weaknesses and Areas for Improvement

While the book is mostly beginner-friendly, there are a couple of areas that might pose challenges for absolute beginners. The first part of the book covers fundamentals well, but it lacks practical exercises to help solidify the concepts. For someone with no prior programming experience, this might make it harder to develop hands-on skills before diving into the projects.

The projects, although fantastic, are quite advanced. For example, the music composition project feels highly specialized and might be intimidating for a beginner. While I could follow along with the code, replicating these projects on my own would have been nigh impossible at my current level of experience. Including an appendix with beginner-level exercises would have been a great addition to bridge this gap and provide more practice opportunities.

Who Should Read This Book?

I would recommend JavaScript Crash Course to anyone with an interest in learning JavaScript who already has a basic understanding of programming concepts. It’s ideal for students, hobbyists, and beginner-intermediate learners looking to broaden their knowledge and explore what’s possible with JavaScript. However, if you’re a complete beginner with no coding experience, you might find the lack of introductory practice exercises challenging.

My Learning Experience

For me, this book served as a true crash course. I spent roughly 40 hours working through it, including following all the exercises and coding along with each project. It clarified a lot of concepts and gave me a good sense of JavaScript’s capabilities. While I found the projects difficult, they were also rewarding and gave me a lot of ideas for my own experiments.

Conclusion and Final Rating

Overall, I would rate JavaScript Crash Course 4.5 out of 5 stars. It delivers exactly what it promises: a quick but comprehensive introduction to JavaScript, paired with three cool projects that showcase what you can build with the language. The writing is engaging, the content is relevant and up-to-date, and the projects are diverse and well-designed. I’m only deducting half a star because I felt the book could benefit from some beginner-friendly exercises to practice the fundamentals before tackling the more advanced projects.

Additional Resources Recommendation

As a final note, I highly recommend checking out other titles from No Starch Press. I’ve read several of their books, and they consistently provide high-quality content, written by talented authors. Their books are well-edited, fun, and a great resource for anyone looking to improve their programming skills and knowledge. I particularly enjoyed Al Sweigart’s and Lee Vaughan’s Python books(for example).

This one was definitely tough! By this one I mean this Decoding DNA problem from dmoj.ca. I have to admit that simply understanding the task was probably at least half the challenge, as I am not very familiar with how DNA works.

This problem was recommended in “Learn to code by solving problems” in the chapter dedicated to writing functions, and I tried my best to squeeze as much as I could from functions in this case.

Although kind of complicated, when broken down into simple pseudocode steps, it was a lot easier to approach this problem, which is another approach I learned to practice from the book.

As you can see I did use the [::-1] reversal that I mentioned in a previous post in this problem.

Anyway, here is my solution:

 #57 Decoding DNA - ecoo12r1p2

def DNA_data() -> list:
    DNA_list = []

    while len(DNA_list) < 5:
        DNA_string = input()
        DNA_list.append(DNA_string)
    return DNA_list


# identify TATAAT promoter and return start of transcription index
def start_of_transcription(DNA_string: str) -> int:
    index = DNA_string.find("TATAAT")
    if index != -1:
        # find returns -1 if no such string found, so we can control for this case
        start_of_transcription = index + 10
        return start_of_transcription
    else:
        print("promoter not found in strand")
        return -1


def complementary_reversed(sequence):    
    complement = {"A": "T", "T": "A", "C": "G", "G": "C"}
    complement_sequence = "".join(complement[base] for base in sequence)
    return complement_sequence[::-1]


# identify base 6 terminator sequence
def end_of_transcription(dna_seq: str, transcription_start: int) -> int:
    length = 6 #length of terminatro sequence
    end_of_transcription = -1

    for i in range(transcription_start, len(dna_seq)):
        # extract candidate with base 6
        candidate = dna_seq[i:i + length]
        complementary_rev = complementary_reversed(candidate)

        #search for this complementary reversed sequence after the candidate sequence
        found_index = dna_seq.find(complementary_rev, i + length)

        if found_index != -1:
            end_of_transcription = i
            break

    #if no valid terminator found transcripton ends at end of strand
    if end_of_transcription == -1:
        print("no terminator sequences found")

    return end_of_transcription

#convert RNA              
def get_RNA(dna_seq, start_of_transcription, end_of_transcription):
        rna_code = {"A":"U","T":"A","C":"G","G":"C"}

        # get transcription unit segment
        dna_segment = dna_seq[start_of_transcription:end_of_transcription]

        # convert DNA to RNA
        rna_result = "".join(rna_code[base] for base in dna_segment)
        return rna_result


#Main program
dna_strings_lst = DNA_data()

for i in range(len(dna_strings_lst)):
    dna_seq = dna_strings_lst[i]
    transcription_start = start_of_transcription(dna_seq)
    if transcription_start == -1:
        continue
    transcription_end = end_of_transcription(dna_seq, transcription_start)
    if transcription_end == -1:
        continue
    rna_seq = get_RNA(dna_seq, transcription_start, transcription_end)
    print(f"{i+1}: {rna_seq}")