## 06ps-06 Boggle Solution

• 0:00 - 0:02
• 0:02 - 0:07
I chose to do it as a single function, which has an embedded function that it calls.
• 0:07 - 0:12
There are two parts to this. We have to first iterate over all the squares in the board.
• 0:12 - 0:19
Then for each of the squares of the board, we want to find all the paths that generate words
• 0:19 - 0:23
and follow all possible paths but cut them off when we have to stop.
• 0:23 - 0:29
Here I said we can enumerate over the locations and the letters that are in the board,
• 0:29 - 0:33
enumerate over them if the letter is not a border character,
• 0:33 - 0:40
then we want to extend the path starting with that letter and that location.
• 0:40 - 0:45
Extend_path says I have a prefix so far, which may or may not be a word,
• 0:45 - 0:52
and I have a path where path is defined as a list of locations that I've visited so far,
• 0:52 - 0:56
and I need that because I can't have a path circle back on itself.
• 0:56 - 1:01
I can't use a location twice, so I need to know where I've been before.
• 1:01 - 1:05
This is similar to the structure of find_words,
• 1:05 - 1:09
but it's constrained to looking on the board through the neighbors.
• 1:09 - 1:11
So what do I do?
• 1:11 - 1:13
I say if the prefix is in the words, I've already found a word,
• 1:13 - 1:18
and the length of that prefix is greater than the minimum length that I'm looking for,
• 1:18 - 1:20
then I add it to the results.
• 1:20 - 1:24
Here that won't have happened because I'm just looking at the first letter--
• 1:24 - 1:28
say the letter P in location i.
• 1:28 - 1:32
That's not going to be a word. It's not going to be greater than the min length, so I keep going.
• 1:32 - 1:40
If the prefix is in my set of prefixes, then I look for every neighboring square j,
• 1:40 - 1:44
which is a neighbor of the last element of my path,
• 1:44 - 1:48
so my path is going to be I start in this location, go to the next location,
• 1:48 - 1:50
go to the next location.
• 1:50 - 1:53
The last element of the path is where I was last.
• 1:53 - 1:55
I want to expand out from there to all the neighbors.
• 1:55 - 1:59
If that j is not in the path, if I haven't circled back yet,
• 1:59 - 2:05
and if the contents of that j is not a border square, if it is a valid letter,
• 2:05 - 2:09
then I just extend the path. I add that letter onto the prefix.
• 2:09 - 2:13
I add that location onto the path and continue, recursively call,
• 2:13 - 2:17
and eventually I'll add all the possible words.
• 2:17 - 2:21
Now, part of the Zen of Python is that flat is better than nested.
• 2:21 - 2:24
Why did I nest here? Well, it's a judgement call.
• 2:24 - 2:30
You certainly could have pulled this out, but if I did pull it out, I would need to pass in
• 2:30 - 2:34
this parameter N, the board, and the result.
• 2:34 - 2:37
There'd be three more parameters that I'd have to pass in,
• 2:37 - 2:42
and I just though it seemed a little bit simpler to only have to call it with two--here and here--
• 2:42 - 2:47
• 2:47 - 2:53
I guess I should say because extend_path is only seven lines long,
• 2:53 - 2:56
I felt it was justified to have it be nested.
• 2:56 - 2:59
If it grew much more than 10 lines, then I'd be very reluctant to have it be nested.
• 2:59 -
I would probably pull it out.
Title:
06ps-06 Boggle Solution
Team:
Udacity
Project:
CS212 - Design of Computer Programs
Duration:
03:02