CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Understanding Word Search

1. READ FIRST!
2. General approach: Break it down!
3. Setting up the initial view with init(data)
4. Drawing the board
5. Drawing the words
6. Selecting letters
7. Did we find a word?
8. The Solver Logic
9. Wrapping it all up
10. Full code

1. READ FIRST!
   1. These notes are here to help you better understand Word Search!
   2. Before reading this, you should be familiar with the concepts and implementation of the Model-View-Controller (MVC) approach to animations with tkinter. If you have not already done so, we strongly recommend you read the class notes on animations first!
   3. We also recommend that you familiarize yourself with word search puzzles. You can find many interactive word search puzzles online; pick one that looks fun and give it a try!


2. General approach: Break it down!
   Implementing a word search game from scratch is arguably a more complex task than we have encountered so far. First, let's consider our requirements:
   • The puzzle must be interactive so that we can solve it ourselves.
   • Our code should be adaptive to many differing conditions, such as different letters and words, the number of cells in the grid, and the size of the window to name a few.
   • Our code should also be able to solve itself: If we press "s" the program should draw a line through all words in the grid that are also present in the solution list.
   For now, let's focus on making the interactive puzzle part, and then we'll come back to the solver logic. This is mostly a matter of breaking down what we need to keep track of in our model, what the view must draw to represent the state of the board, and what the controller must do to make the game interactive. Let's tackle these in order. Start by grabbing the empty animation code from class notes on animations!


3. Setting up the initial view with init(data)
   We are given an empty init(data) function in the animation starter code. This only gets called once! Let's fill that out with some information we need to draw the board as soon as the program runs, and while we're here, we'll also initialize some values we'll want when we make the game interactive.
   def init(data): #We can represent the board as a 2D list data.board = [ [ 'd', 'o', 'g' ], [ 't', 'a', 'c' ], [ 'o', 'a', 't' ], [ 'u', 'r', 'k' ], ] #The words we're searching for can go in a 1D list data.solutions = [ "dog", "cat", "tad"] #Assume the cells are square. How big can we make them? cellWidth = data.width//len(data.board[0]) cellHeight = data.height//len(data.board) data.cellSize = min(cellWidth, cellHeight) #Set up some empty lists we'll discuss later #We'll append to these to keep track of player interactions data.selected = [] data.solvedWords = []
   
   We're keeping track of our board layout and puzzle words using 2D and 1D lists, respectively, and we'll use these frequently. We'll also use data.cellSize often. We determine this by calculating how many cells we need to fit horizontally and vertically in our window, and how wide and tall they can be given the width and height of our window. Since we want our cells to be square, we take the minimum of those two values for the cell size.
   The two empty lists will be used and explained in greater detail once we get to implementing the controller for interactions, but we're adding them here to avoid having to revisit init(data) later.


4. Drawing the board
   Now we can draw the board! The empty function redrawAll(canvas, data) is provided in the starter code and is called by the run function every time we need to update the view. There are a few different parts of the puzzle, so let's start by adding helper functions that we can fill in as we go.
   def drawBoard(canvas, data): pass def drawLines(canvas, data): pass def drawSolutions(canvas, data): pass def redrawAll(canvas, data): #Draw the grid and letters drawBoard(canvas, data) #Draw lines through found words drawLines(canvas, data) #Write the word list drawSolutions(canvas, data)
   
   Now we can write drawBoard(canvas, data), which should draw our cells in some color, and then draw the letters inside the cells at a reasonable font size. We calculated data.cellSize in init(data), and we'll use that size along with the dimensions of the board (a 2D list) to find the top left and bottom right coordinates for each cell. If we iterate over the rows and columns of the board and allow the top left of the first cell to be at (0,0), perhaps this isn't as complicated as it first appears. While iterating, we can also draw the text for each box in a similar manner. The main difference is that we need a single coordinate for each letter, and we want them to be in the center of each box.
   Note: The default window size in the starter code may not be large enough or a convenient shape. For this particular puzzle, I set the size to 600x600 by calling run(600,600) at the bottom of the starter code.
   def drawBoard(canvas, data): #For every row... for row in range(len(data.board)): #And every column... for col in range(len(data.board[row])): color = "turquoise" #Find the top left coordinates for each cell starting at (0,0) left = col*data.cellSize top = row*data.cellSize #Draw the cells! canvas.create_rectangle(left, top, left + data.cellSize, top + data.cellSize, fill=color) #Put the corresponding letter from data.board in each cell canvas.create_text(left + data.cellSize/2, top + data.cellSize/2, text=data.board[row][col], font="Arial " + str(int(data.cellSize/2)) + " bold")
   
   Check it out! We've got our board!
   
   
   
5. Drawing the words
   Next, let's draw the words we're searching for. Remember that we stored these as a 1D list in init(data). We'll be using data.board and data.cellSize again as well.
   def drawSolutions(canvas, data): #Margin keps the words from touching the cells margin = 20 #The left coordinate is going to be the same for every word left = data.cellSize * len(data.board[0]) + margin #For every word, draw as text down the right side of the puzzle for i in range(len(data.solutions)): canvas.create_text(left, data.cellSize*i, text=data.solutions[i], anchor="nw", font="Arial " + str(int(data.cellSize/4)) + " bold")
   
   Our board, now with words!
   
   
   
6. Selecting letters
   Next, let's add controller code so that cells change color when we click them. Remember when we initialized data.selected as an empty list in init(data)? Now we'll use that to keep track of the rows and columns of all selected cells. In mousePressedn(event, data), when the user clicks inside the window, we calculate which row and column the mouse is in. If the row and column are valid, i.e. the user clicked a cell, we append those values to data.selected. Otherwise, if the user clicks outside of the cell, we re-initialize data.selected as an empty list, effectively de-selecting all cells. This way we don't trap ourselves if we make a mistake and click the wrong letter.
   def mousePressed(event, data): # Note: this only works if the user clicks the cells in the correct order. # Fixing that is a task for another day... #Find the row and column of the clicked cell row = event.y // data.cellSize col = event.x // data.cellSize #If the row and column are in range of the board... if 0 <= row < len(data.board) and \ 0 <= col < len(data.board[0]): #Add the row and column to the list of selected cells data.selected.append((row, col)) #Otherwise if we clicked outside, de-select all cells else: data.selected = []
   
   Note the caveat that this only works if the user "behaves" and only selects cells in a line and in the proper order. (How do you think you might enforce only selecting connected cells? How about connected cells in the same row, column, or diagonal? Can you make the order of selection not matter? We won't dive into this, but you might have ideas once we're finished!)
   Naturally we want to be able to see which cells are selected, so let's make a slight addition to drawBoard(canvas,data) so that the color of the box is set to yellow if its row-column pair is in data.selected.
   def drawBoard(canvas, data): #For every row... for row in range(len(data.board)): #And every column... for col in range(len(data.board[row])): #New code here: #Color the cell yellow if selected, turquoise otherwoise! if (row, col) in data.selected: color = "yellow" else: color = "turquoise" #Find the top left coordinates for each cell starting at (0,0) left = col*data.cellSize top = row*data.cellSize #Draw the cells! canvas.create_rectangle(left, top, left + data.cellSize, top + data.cellSize, fill=color) #Put the corresponding letter from data.board in each cell canvas.create_text(left + data.cellSize/2, top + data.cellSize/2, text=data.board[row][col], font="Arial " + str(int(data.cellSize/2)) + " bold")
   
   Now we can select some letters!
   
   
   
7. Did we find a word?
   Let's add some logic for detecting when we have found a word. We'll define "find" to mean that the selected cells contain letters that form one of the words from data.solutions. Ideally the selected cells are touching at an edge or corner and in a straight line, but all that matters in our simple example is the order. It makes the most sense to check for a found word right after a new cell is selected, so we'll make a small modification to mousePressed(event,data). Note the introduction of a new helper function! If we detect a word has been found, we'll append data.solvedWords with a list containing the row-col pairs of the first and last cells selected. This lets us draw a line through the word later!
   def mousePressed(event, data): # Note: this only works if the user clicks the cells in the correct order. # Fixing that is a task for another day... #Find the row and column of the clicked cell row = event.y // data.cellSize col = event.x // data.cellSize #If the row and column are in range of the board... if 0 <= row < len(data.board) and \ 0 <= col < len(data.board[0]): #Add the row and column to the list of selected cells data.selected.append((row, col)) #New code here: #If word found, append row-column pairs of the first/last cells selected #Then clear the selected cells if foundWord(data): data.solvedWords.append([data.selected[0], data.selected[-1]]) data.selected = [] #Otherwise if we clicked outside, de-select all cells else: data.selected = []
   
   Now we'll write the helper function foundWord(data), which is potentially a cleaner strategy than what we showed in Lecture 2. The basic idea is that we build a string using the row-col pairs in data.selected and we check to see if it matches a word in data.solutions.
   def foundWord(data): word = "" #For every selected cell, append its letter for point in data.selected: (row, col) = point word += data.board[row][col] #Return if the selected cells match a word we're searching for return word in data.solutions
   
   It's time for us to go back to our last draw function, drawLines(canvas,data). When redrawAll(canvas,data) is called, it will call drawLines(canvas,data). For every found word, i.e. every list of two row-col pairs in data.solvedWords, we'll draw a line through the first and last cells (and, if the user behaved and selected cells in a line, the rest of the word).
   def drawLines(canvas, data): for line in data.solvedWords: left = line[0][1] * data.cellSize + data.cellSize/2 top = line[0][0] * data.cellSize + data.cellSize/2 right = line[1][1] * data.cellSize + data.cellSize/2 bottom = line[1][0] * data.cellSize + data.cellSize/2 canvas.create_line(left, top, right, bottom, width=5, fill="white")
   
   If the above code looks a little confusing, try code tracing through it with the row-col coordinates for the first and last letters of the word 'cat' from the list. The coordinates for 'c' are row=1, col=2, and the coordinates for 't' (or the t that we want, anyway) are row=1, col=0. That means if data.solvedWords contains these coordinates, we would see an iteration where line=[[1,2],[1,0]]. Then try running the code and see if it behaves properly when you find the three words! If so, the interactive puzzle is done (though you can make it more robust) and we can move on to the solver!
   
   
   
8. The Solver Logic
   Phew... nice job making it this far! Glad you're still with us. Let's think high-level about how we can write a program that finds all the words in the puzzle. We can apply top-down design here to make this problem easier to approach. Let's make the following functions:
   1. Our end goal is: When we press the "s" key, we want our program to draw a line through every word in the puzzle. That means we'll be using keyPressed(event,data), and one way we could approach the problem is to iterate through the words in data.solutions and search the cells for one word at a time. This suggests we might want a helper function wordSearch(board,word). Our drawLines(canvas,data) function needs the row-col coordinates of the first and last cell of the found word, so wordSearch(board,word) should return a list of two row-col coordinate pairs if the word is found and None otherwise. That way we can just directly append the output to data.solvedWords.
      def keyPressed(event, data): if event.char == "s": for word in data.solutions: data.solvedWords.append(wordSearch(data.board, word))
   
   
   2. If we want wordSearch(board, word) to check all possible locations for the word, we need to start somewhere, so let's iterate over every cell as a potential starting point. It's easier to search for a word if the starting cell is already specified, so for each cell we'll call wordSearchFromPosition(board,word,row,col). Like before, we want wordSearchFromPosition(board,word,row,col) to return a list of two row-col coordinate pairs if it finds the word from the given starting point, and None otherwise. If it returns anything other than None, we can stop iterating and wordSearch(board,word) can return that result, because it means the word has been found. Otherwise if the iterations complete and the word hasn't been found from any starting position, it returns None.
      def wordSearch(board, word): for row in range(len(board)): for col in range(len(board[0])): result = wordSearchFromPosition(board, word, row, col) if result != None: return result return None
   
   
   3. This part is especially important! The pattern employed in wordSearchFromPosition(board,word,row,col) is commonly used when traversing 2D lists. This function needs to check if the letters in any of 8 possible directions from the given starting point will form the given word. Each cell has row and column coordinates that are independently one more or one less than the cells around it. Perhaps this is best shown by an illustration, where each cell's coordinates relative to the center square are shown. The center square has coordinates [row,col]. (For a 3x3 grid these coordinates would be [1,1], but assume we are showing you one 3x3 chunk of a larger grid.)
      
      
      Given this pattern, we can specify any of the 8 directions in a 2D list using simple horizontal and vertical components. (Note that the 9th combination [0,0] is usually skipped because it indicates no directional change.) We commonly use the variables drow and dcol, each of which is an integer in the list [-1,0,1]. In our problem, we want to try finding our word from a given starting point in each of 8 possible directions, so we loop over the values of drow and dcol.
      One last time, we'll substitute a future helper function to check for our word in a given direction. We'll use the rather wordy name wordSearchFromPositionInDir(board,word,row,col,drow,dcol).
      def wordSearchFromPosition(board, word, row, col): #For each direction... for drow in [-1, 0, 1]: for dcol in [-1, 0, 1]: #Skip the no-direction case if drow == dcol == 0: continue #Check this direction for our word result = wordSearchFromPositionInDir(board, word, row, col, drow, dcol) if result != None: return result return None
   
   
   4. Finally we're at a step we can complete without helper functions. Given our board, one word to find, our starting position, and a direction to search, we should be able to determine if our word is present. In wordSearchFromPositionInDir(board,word,row,col,drow,dcol) we loop over the length of our word, starting at zero. If you code-trace the first iteration, you can see that first we are comparing the letter in our starting position to the first letter of our word. If it doesn't match, we can stop searching; our word doesn't start here. If it does, we iterate and move one cell in the direction specified by drow and dcol. We then check the letter in this cell to see if it matches the next letter in our word, and we continue.
      We have to be a little careful, because our program will crash if we try to check a cell outside the range of our board! Specifically, we'll be asking for an index out of range of our list. That's why we've got to check our indices for this and return None if we detect we're out of range. We certainly aren't going to find our word outside of the board, so we can stop.
      If we reach the end of the word, that means we found it!
      Now we can return the row-col pairs of the first and last letter, and these will get passed all the way up through our helper functions until they are appended onto data.solvedWords in keyPressed(event,data). Then when our view refreshes, we should see that drawLines(canvas,data) has created a new line through the word. Then the whole process repeats with searching for the next word in data.solutions. Here's that last helper function:
      def wordSearchFromPositionInDir(board, word, row, col, drow, dcol): curRow, curCol = row, col for i in range(len(word)): curRow = row + i*drow curCol = col + i*dcol if curRow < 0 or curRow >= len(board) or \ curCol < 0 or curCol >= len(board[row]): return None if board[curRow][curCol] != word[i]: return None return [(row, col), (curRow, curCol)]
   
   Run your code! Did you get this without having to click anything?
   
   
   
9. Wrapping it up
   So, hopefully this clears up some of the confusing points, or at least lets you examine them in more detail. There are a lot of concepts and patterns at work here, and the big takeaway message of this coding challenge is that everything becomes a lot more manageable when we break it down. There are a lot of things that our simple implementation doesn't take into account (such as players not clicking words in a line, etc.). There's also room for additional features, like removing words from the list once they've been found. Many of these modifications are much easier to make because of how we've broken the problem up.
   Suffice to say, Word Search isn't the only grid-based game where many of these concepts can come in handy... ::wink wink::. Of course they generalize to other types of problems as well, especially if they involve 2D lists, but we definitely recommend that you contemplate which of these techniques might be handy in a more immediate application. Like... sudoku, maybe?


10. Full code
    Here's all the code we wrote in one place in case you have questions as to how it fits together! It's a little more condensed and the comments are removed for space. If you want to download the python file, click here!
    # Word Search Animation from 09/27/18 Lecture from tkinter import * # Word Search Solver Algorithm def wordSearch(board, word): for row in range(len(board)): for col in range(len(board[0])): result = wordSearchFromPosition(board, word, row, col) if result != None: return result return None def wordSearchFromPosition(board, word, row, col): for drow in [-1, 0, 1]: for dcol in [-1, 0, 1]: if drow == dcol == 0: continue result = wordSearchFromPositionInDir(board, word, row, col, drow, dcol) if result != None: return result return None def wordSearchFromPositionInDir(board, word, row, col, drow, dcol): curRow, curCol = row, col for i in range(len(word)): curRow = row + i*drow curCol = col + i*dcol if curRow < 0 or curRow >= len(board) or \ curCol < 0 or curCol >= len(board[row]): return None if board[curRow][curCol] != word[i]: return None return [(row, col), (curRow, curCol)] # Word Search Animation def init(data): data.board = [ [ 'd', 'o', 'g' ], [ 't', 'a', 'c' ], [ 'o', 'a', 't' ], [ 'u', 'r', 'k' ], ] data.solutions = [ "dog", "cat", "tad"] cellWidth = data.width//len(data.board[0]) cellHeight = data.height//len(data.board) data.cellSize = min(cellWidth, cellHeight) data.selected = [] data.solvedWords = [] def foundWord(data): word = "" for point in data.selected: (row, col) = point word += data.board[row][col] return word in data.solutions def mousePressed(event, data): # Note: this only works if the user clicks the cells in the correct order. # Fixing that is a task for another day... row = event.y // data.cellSize col = event.x // data.cellSize if 0 <= row < len(data.board) and \ 0 <= col < len(data.board[0]): data.selected.append((row, col)) if foundWord(data): data.solvedWords.append([data.selected[0], data.selected[-1]]) data.selected = [] else: data.selected = [] def keyPressed(event, data): if event.char == "s": for word in data.solutions: data.solvedWords.append(wordSearch(data.board, word)) def drawBoard(canvas, data): for row in range(len(data.board)): for col in range(len(data.board[row])): if (row, col) in data.selected: color = "yellow" else: color = "turquoise" left = col*data.cellSize top = row*data.cellSize canvas.create_rectangle(left, top, left + data.cellSize, top + data.cellSize, fill=color) canvas.create_text(left + data.cellSize/2, top + data.cellSize/2, text=data.board[row][col], font="Arial " + str(int(data.cellSize/2)) + " bold") def drawLines(canvas, data): for line in data.solvedWords: left = line[0][1] * data.cellSize + data.cellSize/2 top = line[0][0] * data.cellSize + data.cellSize/2 right = line[1][1] * data.cellSize + data.cellSize/2 bottom = line[1][0] * data.cellSize + data.cellSize/2 canvas.create_line(left, top, right, bottom, width=5, fill="white") def drawSolutions(canvas, data): margin = 20 left = data.cellSize * len(data.board[0]) + margin for i in range(len(data.solutions)): canvas.create_text(left, data.cellSize*i, text=data.solutions[i], anchor="nw", font="Arial " + str(int(data.cellSize/4)) + " bold") def redrawAll(canvas, data): drawBoard(canvas, data) drawLines(canvas, data) drawSolutions(canvas, data) #################################### # use the run function as-is #################################### def run(width=300, height=300): def redrawAllWrapper(canvas, data): canvas.delete(ALL) canvas.create_rectangle(0, 0, data.width, data.height, fill='white', width=0) redrawAll(canvas, data) canvas.update() def mousePressedWrapper(event, canvas, data): mousePressed(event, data) redrawAllWrapper(canvas, data) def keyPressedWrapper(event, canvas, data): keyPressed(event, data) redrawAllWrapper(canvas, data) # Set up data and call init class Struct(object): pass data = Struct() data.width = width data.height = height root = Tk() root.resizable(width=False, height=False) # prevents resizing window init(data) # create the root and the canvas canvas = Canvas(root, width=data.width, height=data.height) canvas.configure(bd=0, highlightthickness=0) canvas.pack() # set up events root.bind("<Button-1>", lambda event: mousePressedWrapper(event, canvas, data)) root.bind("<Key>", lambda event: keyPressedWrapper(event, canvas, data)) redrawAll(canvas, data) # and launch the app root.mainloop() # blocks until window is closed print("bye!") run(600, 600)