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