###############################################################################
# ---------------- 15-112 Recitation #6: 2D lists ---------------- #

# This is a starter file of the problems we did in recitation. A good way to
# use this file is to try to re-write problems you saw in recitation from
# scratch. This way, you can test your understanding and ask on Piazza or
# office hours if you have questions :)

# --------------------------------------------------------------------------- #
###############################################################################
# Code Tracing
###############################################################################
# LEARNING OBJECTIVES
# What is aliasing?
# What is copying and deep copying?
# How do we solve 2D list code tracing problems?

import copy
def ct(a):
	b = a
	c = copy.copy(a)
	d = copy.deepcopy(a)
	a[0][0] = b[0][1]
	c[1].extend(d[0])
	c[1][:2] = b[-1]
	d[2] = c[1]
	b = b[0] + d
	a[1] = a[1] + [6]
	c[0].insert(0, a.pop())
	d[2][0] += c[2][0]
	d[1] = 112
	b[1] = ["summer"]
	return(a, b, c, d)

L = [[1, 4], [3, 5], [8, 0]]
for val in ct(L):
	# print(val)
# print(L)

###############################################################################
#hasColOfZeroes
###############################################################################
# LEARNING OBJECTIVES
# How do we navigate through a 2D list?
# How do we evaluate an attribute of a list?

'''
Write the function hasColOfZeros(L)
that takes a 2d list L and returns True if at least one column in L only
contains 0’s, and False otherwise.
'''

def hasColOfZeros(L):
    return 42


###############################################################################
#Diagonal
###############################################################################
# LEARNING OBJECTIVES
# How do we navigate through a 2D list?
# How do we evaluate an attribute of a list?

'''
Given a square, 2D list of ints, find the left-to-right, top-to-bottom diagonal 
with the biggest sum. Return a tuple of (startingRow, startingCol, bestSum) of 
the diagonal with the biggest sum. Note that we are only considering diagonals 
that go from left to right and top to bottom.
In the example below, bestDiagonal would return (0, 0, 15). 
[[1, 2, 3]
 [4, 5, 6]
 [7, 8, 9]]
'''
def bestDiagonal(L):
	return (42, 42, 42)


################################################################################
# All Word Search Words
################################################################################
# LEARNING OBJECTIVES
# How do we use 2D lists and tuples?
# How do we modify previously written functions?

'''
Use the word search functions from lecture today. 
Except, take in the board and a list of all of the words that you need to find, 
and return a list of tuples that contain the word, location, and direction to search. 
For example, with the following board, wordSearch(board, ["dog", "cat", "cow"])) 
should return [('dog', (0, 0), 'right'), ('cat', (1, 2), 'left'), ('cow', None)]
board = [ [ 'd', 'o', 'g' ],
          [ 't', 'a', 'c' ],
          [ 'o', 'a', 't' ],
          [ 'u', 'r', 'b' ]
        ]
'''
# MODIFY THESE FUNCTIONS
def wordSearch(board, word):
    (rows, cols) = (len(board), len(board[0]))
    for row in range(rows):
        for col in range(cols):
            result = wordSearchFromCell(board, word, row, col)
            if (result != None):
                return result
    return None

def wordSearchFromCell(board, word, startRow, startCol):
    for dir in range(8):
        result = wordSearchFromCellInDirection(board, word,
                                               startRow, startCol, dir)
        if (result != None):
            return result
    return None

def wordSearchFromCellInDirection(board, word, startRow, startCol, dir):
    (rows, cols) = (len(board), len(board[0]))
    dirs = [ (-1, -1), (-1, 0), (-1, +1),
             ( 0, -1),          ( 0, +1),
             (+1, -1), (+1, 0), (+1, +1) ]
    dirNames = [ "up-left"  ,   "up", "up-right",
                 "left"     ,         "right",
                 "down-left", "down", "down-right" ]
    (drow,dcol) = dirs[dir]
    for i in range(len(word)):
        row = startRow + i*drow
        col = startCol + i*dcol
        if ((row < 0) or (row >= rows) or
            (col < 0) or (col >= cols) or
            (board[row][col] != word[i])):
            return None
    return (word, (startRow, startCol), dirNames[dir])



# test function for our NEW version of word search
def testWordSearch():
    board = [ [ 'd', 'o', 'g' ],
              [ 't', 'a', 'c' ],
              [ 'o', 'a', 't' ],
              [ 'u', 'r', 'b' ],
            ]
    print(wordSearch(board, ["dog", "cat", "cow"])) # [('dog', (0, 0), 'right'), ('cat', (1, 2), 'left'), ('cow', None)]
    print(wordSearch(board, ["tad", "bat"])) # [('tad', (2, 2), 'up-left'), ('bat', (3, 2), 'up-left')]

testWordSearch()

###############################################################################
# Reasoning Over Code
###############################################################################
# LEARNING OBJECTIVES
# How do we solve reasoning over code problems with lists, strings, and loops?
# How do we use lists with strings as values? How is this similar to 2D lists?
# How do we use list methods?

def rc(s):
	L = s.split("e")
	assert(len(L[0]) == len(L[-1]) and L[0] != L[-1])
	assert(len(L) == len(L[1]) and len(L) == 3)
	assert(len(L[1]) > len(L[0]) > 1)
	seen = list()
	count = 0
	for i in range(len(L)):
		for j in range(len(L[i])):
			if i == j: 
				assert(L[i][j] == "a")
			else: 
				assert(L[i][j] != "a")
			if L[i][j] in seen:
				count += 1
				seen.remove(L[i][j])
			seen.append(L[i][j])
	return count == 1 and len(seen) == 2*len(L) and L[2][::-1] == "um" and "".join(sorted(seen)) == "akmtuy"