Personal Algorithm Coding Test

algorithm

def ConnectFourWinner(strArr):
    current_player = strArr[0]
    # Parse the board rows into a 2D list of characters
    board = [row.strip("()[]{}").split(',') for row in strArr[1:]]

    ROWS, COLS = 6, 7  # Standard Connect Four dimensions

    # Check if a segment contains 3 player discs and 1 empty slot
    def is_valid_segment(segment):
        player_count = segment.count(current_player)
        empty_count = segment.count('x')
        return player_count == 3 and empty_count == 1

    # Iterate over all possible 4-slot segments
    for row in range(ROWS):
        for col in range(COLS):
            # Check horizontal (right)
            if col + 3 < COLS:
                segment = [board[row][col + i] for i in range(4)]
                if is_valid_segment(segment):
                    return f"({row + 1}x{col + segment.index('x') + 1})"

            # Check vertical (down)
            if row + 3 < ROWS:
                segment = [board[row + i][col] for i in range(4)]
                if is_valid_segment(segment):
                    return f"({row + segment.index('x') + 1}x{col + 1})"

            # Check diagonal (down-right)
            if row + 3 < ROWS and col + 3 < COLS:
                segment = [board[row + i][col + i] for i in range(4)]
                if is_valid_segment(segment):
                    return f"({row + segment.index('x') + 1}x{col + segment.index('x') + 1})"

            # Check diagonal (down-left)
            if row + 3 < ROWS and col - 3 >= 0:
                segment = [board[row + i][col - i] for i in range(4)]
                if is_valid_segment(segment):
                    return f"({row + segment.index('x') + 1}x{col - segment.index('x') + 1})"

    return "none"


test_cases = [
    # Horizontal cases
    ["R", "(x,R,R,R,x,x,x)", 
          "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)"],
    ["R", "(R,x,R,R,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)"],
    ["R", "(R,R,x,R,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)"],
    ["R", "(R,R,R,x,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)"],

    # Vertical cases
    ["R", "(x,x,x,x,x,x,x)", "(R,x,x,x,x,x,x)", "(R,x,x,x,x,x,x)", "(R,x,x,x,x,x,x)", "(x,x,x,x,x,x,x)", "(x,x,x,x,x,x,x)"],
    ["R", "(R,x,x,x,x,x,x)", "(x,x,x,x,x,x,x)", "(R,x,x,x,x,x,x)", "(R,x,x,x,x,x,x)", "(x,x,x,x,x,x,x)", "(x,x,x,x,x,x,x)"],
    ["R", "(R,x,x,x,x,x,x)", "(R,x,x,x,x,x,x)", "(x,x,x,x,x,x,x)", "(R,x,x,x,x,x,x)", "(x,x,x,x,x,x,x)", "(x,x,x,x,x,x,x)"],
    ["R", "(R,x,x,x,x,x,x)", "(R,x,x,x,x,x,x)", "(R,x,x,x,x,x,x)", "(x,x,x,x,x,x,x)", "(x,x,x,x,x,x,x)", "(x,x,x,x,x,x,x)"],

    # Diagonal up-right cases
    ["R", "(x,x,x,x,x,x,x)",
          "(x,x,x,R,x,x,x)",
          "(x,x,R,x,x,x,x)",
          "(x,R,x,R,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)"],
    ["R", "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,R,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,x,x,R,x,x,x)",
          "(x,x,x,x,R,x,x)"],
    ["R", "(x,x,x,R,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,R,x,x,x,x,x)",
          "(R,R,x,x,x,x,x)",
          "(x,x,R,x,x,x,x)",
          "(x,x,x,R,x,x,x)"],
    ["R", "(x,x,x,x,x,R,x)",
          "(x,x,x,x,R,x,x)",
          "(x,x,x,R,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,R,x,x,x,x,x)",
          "(x,x,R,x,x,x,x)"],

    # Diagonal down-right cases
    ["R", "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,R,x,x,x,x,x)",
          "(x,x,R,x,x,x,x)",
          "(x,x,x,R,x,x,x)",
          "(x,x,x,x,x,x,x)"],
    ["R", "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(R,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,x,R,x,x,x,x)",
          "(x,x,x,R,x,x,x)"],
    ["R", "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,x,R,x,x,x,x)",
          "(x,x,x,R,x,x,x)",
          "(x,x,x,x,x,x,x)",
          "(x,x,x,x,x,R,x)"],
    ["R", "(x,x,x,x,x,x,x)",
          "(x,x,R,x,x,x,x)",
          "(x,x,x,R,x,x,x)",
          "(x,x,x,x,R,x,x)",
          "(R,x,x,x,x,x,x)",
          "(x,R,x,x,x,x,x)"]
]

# Test all cases
for i, case in enumerate(test_cases, start=1):
    result = ConnectFourWinner(case)
    print(f"Test Case {i}: Result = {result}")

import itertools

def MatrixBorder(strArr):
    """
    Determine the minimum number of row and column swaps required to arrange the matrix such that:
    - All border positions are 1s.
    - All inner positions are 0s.
    
    Parameters:
        strArr: A list of strings, where each string represents a row of the matrix.
    
    Returns:
        Minimum number of swaps required to achieve the desired arrangement.
    """
    # Parse input (e.g. "(0,1,1)" -> [0,1,1])
    matrix = []
    for row_str in strArr:
        row_str = row_str.strip("()[]{}")
        nums = [int(x) for x in row_str.split(',')]
        matrix.append(nums)

    n = len(matrix)

    # Function to count inversions in a permutation (minimum adjacent swaps)
    def count_inversions(perm):
        inv = 0
        for i in range(len(perm)):
            for j in range(i+1, len(perm)):
                if perm[i] > perm[j]:
                    inv += 1
        return inv

    # Check if a given arrangement satisfies the border and inner conditions
    def check_border(arranged):
        for c in range(n):
            if arranged[0][c] != 1 or arranged[n-1][c] != 1:  # Top and bottom rows
                return False
        for r in range(n):
            if arranged[r][0] != 1 or arranged[r][n-1] != 1:  # Left and right columns
                return False
        for r in range(1, n-1):  # Inner cells
            for c in range(1, n-1):
                if arranged[r][c] != 0:
                    return False
        return True

    # Minimum swaps needed
    min_swaps = float('inf')

    # Generate all permutations of row and column indices
    all_rows = list(itertools.permutations(range(n)))
    all_cols = list(itertools.permutations(range(n)))

    for row_perm in all_rows:
        row_swaps = count_inversions(row_perm)
        for col_perm in all_cols:
            col_swaps = count_inversions(col_perm)
            # Skip if current partial sum is already >= min_swaps
            if row_swaps + col_swaps >= min_swaps:
                continue

            # Apply the current permutations to the matrix
            arranged = []
            for rp in row_perm:
                new_row = [matrix[rp][cp] for cp in col_perm]
                arranged.append(new_row)

            # Check if the arrangement satisfies the conditions
            if check_border(arranged):
                min_swaps = min(min_swaps, row_swaps + col_swaps)

    return min_swaps if min_swaps != float('inf') else -1

# Example usage
if __name__ == "__main__":
    # Test Case 1
    input_matrix_1 = ["(0,1,1)", "(1,1,1)", "(1,1,1)"]
    result_1 = MatrixBorder(input_matrix_1)
    print(f"Minimum swaps for Test Case 1: {result_1}")  # Expected Output: 2

    # Test Case 2
    input_matrix_2 = ["(0,1,0,1)", "(1,1,1,1)", "(0,1,0,1)", "(1,1,1,1)"]
    result_2 = MatrixBorder(input_matrix_2)
    print(f"Minimum swaps for Test Case 2: {result_2}")  # Expected Output: 2

from collections import deque

def ArrayJumping(arr):
    # Find the largest value and its index in the array
    max_value = max(arr)
    max_index = arr.index(max_value)
    n = len(arr)

    # Initialize a queue for BFS and a visited set
    queue = deque([(max_index, 0)])  # (current position, jump count)
    visited = set()

    while queue:
        current, jumps = queue.popleft()

        # Skip already visited nodes
        if current in visited:
            continue
        visited.add(current)

        # Calculate possible next positions (left and right jumps)
        for direction in [1, -1]:
            next_position = (current + direction * arr[current]) % n
            if next_position < 0:
                next_position += n  # Handle negative indices

            if next_position == max_index:
                # If back at the starting position, return jump count
                return jumps + 1

            # Add new position to the queue
            queue.append((next_position, jumps + 1))

    # If BFS completes, it's impossible to return to the start; return -1
    return -1

# Example tests
print(ArrayJumping([1, 2, 3, 4, 2]))  # Expected output: 3
print(ArrayJumping([1, 7, 1, 1, 1, 1]))  # Expected output: 2

ChatGPT

A conversational AI system that listens, learns, and challenges

https://chatgpt.com/c/6790e95d-0970-8007-991f-ebae6719ceb8

ChatGPT

A conversational AI system that listens, learns, and challenges

https://chatgpt.com/c/679035df-1528-8007-96e0-0dd194a1569f