Note: except for Othello (which is optional), these Case Studies may
appear on quizzes, midterms, or the final exam.
You should understand their top-down design, and be prepared to explain
what each function or method does in general, and also be prepared to
write any function or method from scratch.
That is not practical and in any
case not helpful. Instead, try to understand the code. You would be
well-served if you wrote these from scratch, referring back to the sample
solutions as needed.
- Word Search
# wordSearch1.py
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 drow in [-1, 0, +1]:
for dcol in [-1, 0, +1]:
if (drow, dcol) != (0, 0):
result = wordSearchFromCellInDirection(board, word,
startRow, startCol,
drow, dcol)
if (result != None):
return result
return None
def wordSearchFromCellInDirection(board, word, startRow, startCol, drow, dcol):
(rows, cols) = (len(board), len(board[0]))
dirNames = [ ["up-left" , "up", "up-right"],
["left" , "" , "right" ],
["down-left", "down", "down-right" ] ]
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[drow+1][dcol+1])
def testWordSearch():
board = [ [ 'd', 'o', 'g' ],
[ 't', 'a', 'c' ],
[ 'o', 'a', 't' ],
[ 'u', 'r', 'k' ],
]
print(wordSearch(board, "dog")) # ('dog', (0, 0), 'right')
print(wordSearch(board, "cat")) # ('cat', (1, 2), 'left')
print(wordSearch(board, "tad")) # ('tad', (2, 2), 'up-left')
print(wordSearch(board, "cow")) # None
testWordSearch()
- Word Search Redux
# wordSearch2.py
# This time with a slightly different handling of directions
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):
possibleDirections = 8 # 3^2 - 1
for dir in range(possibleDirections):
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])
def testWordSearch():
board = [ [ 'd', 'o', 'g' ],
[ 't', 'a', 'c' ],
[ 'o', 'a', 't' ],
[ 'u', 'r', 'k' ],
]
print(wordSearch(board, "dog")) # ('dog', (0, 0), 'right')
print(wordSearch(board, "cat")) # ('cat', (1, 2), 'left')
print(wordSearch(board, "tad")) # ('tad', (2, 2), 'up-left')
print(wordSearch(board, "cow")) # None
testWordSearch()
- Connect4
# connect4.py
# A simple game of connect4 with a text interface
# based on the wordSearch code written in class.
def playConnect4():
rows = 6
cols = 7
board = makeBoard(rows, cols)
player = 'X'
moveCount = 0
printBoard(board)
while (moveCount < rows*cols):
moveCol = getMoveCol(board, player)
moveRow = getMoveRow(board, moveCol)
board[moveRow][moveCol] = player
printBoard(board)
if checkForWin(board, player):
print(f'*** Player {player} Wins!!! ***')
return
moveCount += 1
player = 'O' if (player == 'X') else 'X'
print('*** Tie Game!!! ***')
def makeBoard(rows, cols):
return [ (['-'] * cols) for row in range(rows) ]
def printBoard(board):
rows = len(board)
cols = len(board[0])
print()
# first print the column headers
print(' ', end='')
for col in range(cols):
print(str(col+1).center(3), ' ', end='')
print()
# now print the board
for row in range(rows):
print(' ', end='')
for col in range(cols):
print(board[row][col].center(3), ' ', end='')
print()
def getMoveCol(board, player):
cols = len(board[0])
while True:
response = input(f"Enter player {player}'s move (column number) --> ")
try:
moveCol = int(response)-1 # -1 since user sees cols starting at 1
if ((moveCol < 0) or (moveCol >= cols)):
print(f'Columns must be between 1 and {cols}.', end='')
elif (board[0][moveCol] != '-'):
print('That column is full! ', end='')
else:
return moveCol
except:
# they did not even enter an integer!
print('Columns must be integer values! ', end='')
print('Please try again.')
def getMoveRow(board, moveCol):
# find first open row from bottom
rows = len(board)
for moveRow in range(rows-1, -1, -1):
if (board[moveRow][moveCol] == '-'):
return moveRow
# should never get here!
assert(False)
def checkForWin(board, player):
winningWord = player * 4
return (wordSearch(board, winningWord) != None) # that was easy!
##############################################
# taken from wordSearch.py
##############################################
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 drow in [-1, 0, +1]:
for dcol in [-1, 0, +1]:
if (drow, dcol) != (0, 0):
result = wordSearchFromCellInDirection(board, word,
startRow, startCol,
drow, dcol)
if (result != None):
return result
return None
def wordSearchFromCellInDirection(board, word, startRow, startCol, drow, dcol):
(rows, cols) = (len(board), len(board[0]))
dirNames = [ ['up-left' , 'up', 'up-right'],
['left' , '' , 'right' ],
['down-left', 'down', 'down-right' ] ]
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[drow+1][dcol+1])
playConnect4()
- Othello
# othello.py
# this is optional but interesting!
def make2dList(rows, cols):
a=[]
for row in range(rows): a += [[0]*cols]
return a
def hasMove(board, player):
(rows, cols) = (len(board), len(board[0]))
for row in range(rows):
for col in range(cols):
if (hasMoveFromCell(board, player, row, col)):
return True
return False
def hasMoveFromCell(board, player, startRow, startCol):
(rows, cols) = (len(board), len(board[0]))
if (board[startRow][startCol] != 0):
return False
for dir in range(8):
if (hasMoveFromCellInDirection(board, player, startRow, startCol, dir)):
return True
return False
def hasMoveFromCellInDirection(board, player, 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) ]
(drow,dcol) = dirs[dir]
i = 1
while True:
row = startRow + i*drow
col = startCol + i*dcol
if ((row < 0) or (row >= rows) or (col < 0) or (col >= cols)):
return False
elif (board[row][col] == 0):
# no blanks allowed in a sandwich!
return False
elif (board[row][col] == player):
# we found the other side of the 'sandwich'
break
else:
# we found more 'meat' in the sandwich
i += 1
return (i > 1)
def makeMove(board, player, startRow, startCol):
# assumes the player has a legal move from this cell
(rows, cols) = (len(board), len(board[0]))
for dir in range(8):
if (hasMoveFromCellInDirection(board, player, startRow, startCol, dir)):
makeMoveInDirection(board, player, startRow, startCol, dir)
board[startRow][startCol] = player
def makeMoveInDirection(board, player, 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) ]
(drow,dcol) = dirs[dir]
i = 1
while True:
row = startRow + i*drow
col = startCol + i*dcol
if (board[row][col] == player):
# we found the other side of the 'sandwich'
break
else:
# we found more 'meat' in the sandwich, so flip it!
board[row][col] = player
i += 1
def getPlayerLabel(player):
labels = ['-', 'X', 'O']
return labels[player]
def printColLabels(board):
(rows, cols) = (len(board), len(board[0]))
print(' ', end='') # skip row label
for col in range(cols): print(chr(ord('A')+col),' ', end='')
print()
def printBoard(board):
(rows, cols) = (len(board), len(board[0]))
printColLabels(board)
for row in range(rows):
print(f'{row+1:2} ', end='')
for col in range(cols):
print(getPlayerLabel(board[row][col]), ' ', end='')
print(f'{row+1:2}')
printColLabels(board)
def isLegalMove(board, player, row, col):
(rows, cols) = (len(board), len(board[0]))
if ((row < 0) or (row >= rows) or (col < 0) or (col >= cols)): return False
return hasMoveFromCell(board, player, row, col)
def getMove(board, player):
print('\n**************************')
printBoard(board)
while True:
prompt = 'Enter move for player ' + getPlayerLabel(player) + ': '
move = input(prompt).upper()
# move is something like 'A3'
if ((len(move) != 2) or
(not move[0].isalpha()) or
(not move[1].isdigit())):
print('Wrong format! Enter something like A3 or D5.')
else:
col = ord(move[0]) - ord('A')
row = int(move[1])-1
if (not isLegalMove(board, player, row, col)):
print('That is not a legal move! Try again.')
else:
return (row, col)
def playOthello(rows, cols):
# create initial board
board = make2dList(rows, cols)
board[rows//2][cols//2] = board[rows//2-1][cols//2-1] = 1
board[rows//2-1][cols//2] = board[rows//2][cols//2-1] = 2
(currentPlayer, otherPlayer) = (1, 2)
# and play until the game is over
while True:
if (hasMove(board, currentPlayer) == False):
if (hasMove(board, otherPlayer)):
print('No legal move! PASS!')
(currentPlayer, otherPlayer) = (otherPlayer, currentPlayer)
else:
print('No more legal moves for either player! Game over!')
break
(row, col) = getMove(board, currentPlayer)
makeMove(board, currentPlayer, row, col)
(currentPlayer, otherPlayer) = (otherPlayer, currentPlayer)
print('Goodbye!')
playOthello(8,8)