def transpose_matrix(matrix):
    """
    Given a matrix, return the transpose.
    """
    pass

def test_transpose_matrix():
    assert transpose_matrix([[1,2,3]]) == [[1], [2], [3]]
    assert transpose_matrix([[5, 4], [4, 0], [7, 10], [-1, 8]]) == [[5, 4, 7, -1], [4, 0, 10, 8]]
    assert transpose_matrix([[1, 3, 5], [2, 4, 6]]) == [[1, 2], [3, 4], [5, 6]]

"""
Explanation: CS 196 Spring 2017 Homework 2
Table of Contents


Transpose Matrix
Orthogonal Vectors
Winner of Tic-Tac-Toe
Spiral Matrix
Flatten List
Sort 2D Matrix
Check Rook
Rotate Matrix
Product Range

Transpose Matrix

Given a 2D array that is n by m, return the transpose of the matrix.
Return None if a transpose does not exist
Example(s):


Example 1:
Input: 
[[5, 4],
    [4, 0],
    [7, 10].
    [-1, 8]]


Output: 
[[5, 4, 7, -1],
    [4, 0, 10, 8]]





Parameters


[[int]] : matrix
matrix to transpose



Returns


[[int]]: Transpose of the list
End of explanation
"""


def orthogonal_vectors(matrix):
    '''
    Compute whether or not all of the column vectors of a matrix are orthogonal to one another
    '''
    pass

def test_orthogonal_vectors():
    assert not orthogonal_vectors([[1,2,3],[-2,1,-4],[-3,4,1]])
    assert orthogonal_vectors([[1,2,4],[-1,-1,7],[3,-1,1]])
    assert orthogonal_vectors([[0,25,-1],[0,4,10],[0,5,-3]])

"""
Explanation: Orthogonal Vectors

<!-- Problem Name should be replaced!-->

Create a program to indicate whether or not the column vectors in a matrix are orthogonal, where the column vectors of a matrix are the vectors &lt;a1,a2,a3&gt;,&lt;b1,b2,b3&gt;,&lt;c1,c2,c3&gt; contained in the matrix:<br/>|a1,b1,c1|<br/>|a2,b2,c2|<br/>|a3,b3,c3|<br/>
Restriction(s):

<!-- Put problem restrictions here -->

Input is an 3x3 array of integers.
No values in the matrix will be larger than 1000.
You may not use functions other than those in Python 3 by default

Example(s):



Example 1:


Input: 

matrix: [
[ 1, 2, 3],
[-2, 1,-4],
[-3, 4, 1]]
size : 3



Output: 

false





Example 2:


Input: 

matrix: [
[ 1, 2, 4],
[-1,-1, 7],
[ 3,-1,1]]



Output: 

true





Example 3:

Input: 
matrix: [
[ 0,25,-1],
[ 0, 4,10],
[ 0, 5,-3]]


Output:
true *Note that the zero vector is orthogonal to all vectors





Parameters


[[int]] : matrix <!-- USE PYTHON TYPES PLEASE (str, list, int, float, etc. Should be in the order of <python type> : <variable name> -->
Representation, in row-major form of matrix containing column vectors



Returns


bool: True/False depending on whether or not vectors are orthogonal

<!-- Don't do second outputs. Then it'll just become a tuple. -->
End of explanation
"""


def winner_of_tic_tac_toe(game):
    """
    Print winner of tic tac toe game
    """
    pass

def test_winner_of_tic_tac_toe():
    assert winner_of_tic_tac_toe([['X','O','X'],['O','X','O'],['X','O','X']]) == "X wins!"
    assert winner_of_tic_tac_toe([['X','X','O'],['O','X','O'],['X','O','O']]) == "O wins!"

"""
Explanation: Winner of Tic Tac Toe

<!-- Problem Name should be replaced!-->

Given a complteted Tic Tac Toe game as 2D matrix, return the winner of the game.
Restriction(s):

<!-- Put problem restrictions here -->

There will either be one winner or no winner, no input where X and O are both winners.
Make sure the returned string is EXACTLY the same as the outputs we give. Failure to do so will result you in getting the test cases wrong.

Example(s):



Example 1:

Input: 

game: [<br/>['X','X','O'], <br/>['O','X','O'],<br/>['X','O','O']]


Output: 

O wins!





Example 2:

Input: 

game: [<br/>['X','O','X'], <br/>['O','X','O'],<br/>['X','O','X']]


Output: 

X wins!





Example 3:

Input: 
game: [<br/>['O','X','O'], <br/>['O','X','O'],<br/>['X','O','X']]
Output:
Draw!





Parameters


list : game
the Tic Tac Toe game



Returns


str: 
the winner of the game, if there is no winner return 'Draw!'
End of explanation
"""


def spiral_matrix(arr):
    """
    return matrix in spiral order
    """
    pass

def test_spiral_matrix():
    assert spiral_matrix([[1, 2, 3, 4],[2, 4, 9, 5],[9, 8, 7, 6]]) == [1, 2, 3, 4, 5, 6, 7, 8, 9, 2, 4, 9]
    assert spiral_matrix([[ 1, 2, 3 ],[ 4, 5, 6 ],[ 7, 8, 9 ]]) == [1, 2, 3, 6, 9, 8, 7, 4, 5]
    assert spiral_matrix([[1,2,3],[11,12,13],[21,22,23]]) == [1, 2, 3, 13, 23, 22, 21, 11, 12]

"""
Explanation: Spiral Matrix

<!-- Problem Name should be replaced!-->

Given a matrix of m x n diemensions (m rows, n columns), return all elements of the matrix in spiral order.
Hint


Draw it out! How should we traverse the 2D list in order to get the output desired?

Example(s):



Example 1:

Input: 

arr: [<br/>[ 1, 2, 3 ], <br/> [ 4, 5, 6 ], <br/> [ 7, 8, 9 ]]


Output: 

[1,2,3,6,9,8,7,4,5]





Example 2:

Input: 
arr: [ <br/>[1, 2, 3, 4], <br/> [2, 4, 9, 5], <br/> [9, 8, 7, 6]]
Output: 
[1,2,3,4,5,6,7,8,9,2,4,9]





Parameters


list : arr
the 2D matrix to be returned in spiral order



Returns


list: 
the 2D matrix in spiral order
End of explanation
"""


def flatten_list(arr):
    """return a flattened list"""
    pass

def test_flatten_list():
    assert flatten_list([[1,2],[3,4]]) == [1,2,3,4]
    assert flatten_list([[1,'a','bbbbb'],[2],[3,4,5,[3,4]]]) == [1,'a','bbbbb',2,3,4,5,[3,4]]
    assert flatten_list([['a', 'b', 'c'], ['d']]) == ['a', 'b', 'c', 'd']

"""
Explanation: Flatten List

Given a list of lists, return a new list with all the elements of the old lists in sequential order
Restriction(s):

The contents of the lists may be any valid Python object.
The lists themselves will always be a list, and will never be None.
Example(s):



Example 1:


Input: 

arr: [[1,2],[3,4]]



Output: 

[1,2,3,4]





Example 2:

Input: 
arr: [[1,'a','bbbbb'],[2],[3,4,5,[3,4]]]


Output: 
[1,'a','bbbbb',2,3,4,5,[3,4]]





Parameters


list : arr
the list of lists to flatten



Returns


list: 
the new flattened list
End of explanation
"""


def sort_matrix(mat):
    """sort a matrix"""
    pass

def test_sort_matrix():
    assert sort_matrix([[5,2],[37,4]]) == [[2,4],[5,37]]
    assert sort_matrix([[0,1,2],[4,3,5]]) == [[0,1,2],[3,4,5]]
    assert sort_matrix([[0,0,0,0,0,14],[-2,8,20,0,0,0]]) == [[-2,0,0,0,0,0],[0,0,0,8,14,20]]
    assert sort_matrix([[5,4,20], [9,-1,19], [91,-19,1]]) == [[-19, -1, 1], [4, 5, 9], [19, 20, 91]]


"""
Explanation: Sort 2D matrix

Given a 2D matrix, return a new matrix of the same dimensions as the old whose contents are the sorted equivalents of the old matrix.
Restriction(s):

The matrix will be rectangular, i.e. the sublists will all be of the same length.
The dimensions of the matrix are strictly positive.
Example(s):



Example:


Input: 

arr: [[5,2],[37,4]]



Output: 

[[2,4],[5,37]]


Example 2:
Input:
arr: [[5,4,20], [9,-1,19], [91,-19,1]]


Output:
[[-19, -1, 1], [4, 5, 9], [19, 20, 91]]



Parameters


mat : arr
the matrix to sort



Returns


list: 
the new, sorted matrix
End of explanation
"""


def check_rook(board):
    """
    Checks if the rook can take the other piece, given a square matrix and 2 characters within that matrix.
    """
    pass

def test_check_rook():
    assert check_rook([['', 'P'], ['', 'R']]) is True
    assert check_rook([['', 'P'], ['R', '']]) is False
    assert check_rook([['', '', 'P'], ['', '', ''], ['', '', 'R']]) is True

"""
Explanation: Check Rook

Given a square matrix (i.e. a chess board) containing a character 'R' (the rook) and a character 'P' (the other piece),
return True if the rook can take the piece, and False otherwise.
Restriction(s):

Every input matrix will be square and contain 'R' and 'P' exactly once each.
Example(s):



Example 1:

Input: 

arr: [<br/>[ '', '', '', 'P' ], <br/> [ '', '', '', '' ], <br/> [ '', '', '', 'R' ], <br/> [ '', '', '', '']]


Output: 

True





Example 2:

Input: 
arr: [<br/>[ '', '', '', 'P' ], <br/> [ 'R', '', '', '' ], <br/> [ '', '', '', '' ], <br/> [ '', '', '', '']]
Output: 
False





Parameters


list : board
the square matrix to be iterated through



Returns


bool: 
whether the rook can take the piece or not
End of explanation
"""


def rotate_matrix(matrix):
    """Given a matrix, rotate the matrix"""
    pass

def test_rotate_matrix():
    assert rotate_matrix([[1, 2, 3], [4, 5, 6]]) == [[4, 1], [5, 2], [6, 3]]
    assert rotate_matrix([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]) == [[13, 9, 5, 1], [14, 10, 6, 2], [15, 11, 7, 3], [16, 12, 8, 4]]

"""
Explanation: Rotate Matrix

<!-- Problem Name should be replaced!-->

Given a 2D matrix, rotate the matrix 90 degrees clockwise, then return the result
Restriction(s):

The 2D matrix will always input. You do not have the consider the empty 2D Matrix [[]]
Example(s):



Example 1:

Input: 

arr: [<br/>[ 1, 2, 3, 4 ], <br/> [ 5, 6, 7, 8 ], <br/> [ 9, 10, 11, 12 ], <br/> [ 13, 14, 15, 16 ]]


Output: 

arr: [<br/>[ 13, 9, 5, 1 ], <br/> [ 14, 10, 6, 2 ], <br/> [ 15, 11, 7, 3 ], <br/> [ 16, 12, 8, 4 ]]





Example 2:

Input: 
arr: [<br/>[ 1, 2, 3 ], <br/> [ 4, 5, 6 ]]
Output: 
arr: [<br/>[ 4, 1 ], <br/> [ 5, 2 ], <br/> [ 6, 3 ]]





Parameters


list : matrix
the matrix to be rotated



Returns


list: 
the rotated matrix
End of explanation
"""


def product_range(arr):
    """
    return difference between maximum and minimum product of a valid path
    """
    pass

def test_product_range():
    # Tests reserved for students
    assert product_range([[1,3,2],[-4,5,6]])==30
    assert product_range([[2,3,-4],[4,9,5]])==63
    assert product_range([[2,-2,6],[5,-10,1]])==80

def test_all():
    # Add your test case here. This should be at the very end
    test_transpose_matrix()
    test_orthogonal_vectors()
    test_winner_of_tic_tac_toe()
    test_spiral_matrix()
    test_flatten_list()
    test_sort_matrix()
    test_check_rook()
    test_rotate_matrix()
    test_product_range()

test_all()

"""
Explanation: Product Range

<!-- Problem Name should be replaced!-->

Given a 2D matrix, find the difference between the maximum and minimum products that can be formed by moving through the columns of the matrix. Valid moves are down-left, downwards, and down-right.
Restrictions

We will only test for arrays that are 2x3 That is, we will test arrays with similar structure to the examples and nothing else.
Example(s):



Example 1:

Input: 

arr: [<br/>[ 1, 3, 2 ], <br/> [-4, 5, 6 ]]


Output: 

30
Maximum formed by moving through 3 and 6, minimum formed by moving through 3 and -4.







Example 2:

Input: 
arr: [ <br/>[2, 3, -4], <br/> [4, 9, 5]]
Output: 
63
Maximum formed by moving through 3 and 9, minimum formed by moving through -4 and 9.







Parameters


[[int]] : arr
the 2D matrix to be used for computing the product



Returns


int: 
the maximum possible product of integers in a valid path through the 2D array
End of explanation
"""


