Development Strategy

Data Structures

Organize the list of valid words as a list of strings. Organize the grid as a list of lists

Program development

Searching horizontally. First, consider the problem of finding words horizontally in the grid going from left to right. Consider the first row in the example shown above:

y c o d e j

Now repeat this step, but starting at the second element $($i$.$e$.,\text{'}$c$\text{'}).$ Notice that this time you will come to the end of the list one step sooner. Then repeat for the third element, and so on$.$

Next consider the problem of searching for words horizontally going right to left. Suppose we want to search the row y c $$ d e j going right to left. This is actually the same as reversing the row, to

$!$docy bottom to top?

Searching diagonally. Searching diagonally is the hardest part of this problem, however, we are only considering one case: upper$-$left to lower$-$right.

If you can extract each diagonal into a list of letters, then you can simply search through this list as you did before$-$again, reducing this problem to one you've already written code to solve.

Repeat this exercise for the diagonal starting at grid$[1][0].$ Look at how the $x-$ and $y-$coordinates change from each element to the next. How does this compare to the way they changed for the other two diagonals you considered $($above$)?$

Do you see a pattern in how the $x-$ and $y-$coordinates change between successive elements? Can you use this pattern to extract a diagonal going from the upper$-$left to lower$-$right given its starting coordinates into a list?