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()