Knights Dialer Exercise

[00:00:00]
>> Hopefully, at the midway point through our exercises, you're starting to develop a little bit more confidence, a little less tenseness over tackling these algorithmic challenges. And hopefully, the takeaway that you're getting here is that there's no writing the big algorithm all at once, top down. That it's always a tiny little series of increments and improvements and additions.

[00:00:28]
It's little tiny Lego pieces that we build on top of each other. And that's how you see me writing the code. That's exactly the best that I can recommend for you as algorithmists as you go forward. We're gonna transition into the next exercise, which is called Knight's Dialer.

[00:00:49]
This is a classic problem, and it has been used in various big name company job interviews. FAANG-type companies have, at one time or another, used problems like this. So it's one of the classic ones, and there are in fact linked in the project repo on this workshop, linked in the readme.

[00:01:13]
There's a link to a series of blog post that an interviewer from Amazon wrote about it and about ways to approach it. So I recommend you go and check those out, read through those as further research on this topic. I've put put my own little twist on the Knight's Dialer, and I think it's gonna provide some nice, meaty stuff for us to dig into.

[00:01:37]
And so, we'll be settled into this exercise for a while. There are several different concepts that we wanna explore. And we will push the envelope quite a bit, but you're on firm ground now. So even though it might start to look a little unfamiliar, don't lose that confidence, you can do this.

[00:01:57]
What is the Knight's Dialer? Building off of the concept of the chessboard before, it's kind of a nice little extension. What if of our chessboard was actually the numeric keypad from an old-school phone? I'm old enough to remember when phones actually had push buttons like this. And I remember that there were phones that didn't even have the little asterisk and the star button, they were literally just blank spaces like you see here.

[00:02:25]
So this is the theoretical setup, obviously, it's kind of a silly example, it sits in a more theoretical space. But it is gonna help us to learn a lot of different concepts within the broader DSA space. The premise of this problem is the knight piece, the K-N-I-G-H-T piece, in the game of chess.

[00:02:50]
For those of you that are familiar with chess, you know that the knight moves in an L pattern, one over and two down. And so we might think of the knight if it were moving on a numeric keypad. If it started on the 1 key, it might move from the one key over to the 6 key, or it might move from the 1 key down to the 8 key.

[00:03:11]
Those are the two places that you could move as a knight if you started on the 1 key. Hopefully that make sense. If you start on the 6 key, where can you move?
>> 7, 1 or 0.
>> Not 4? You said 4?
>> No, 7, 1 or 0.

[00:03:35]
>> You said or 0, I thought you said 4, 0. [LAUGH]
>> I'm gonna show the action.
>> Correct 7,1 and also 0. 0 is a valid move, okay? So what about the 5 key? If you're on the 5 key, where can you move? No one, not a trick question, it's pretty straightforward.

[00:03:59]
There's nowhere to move if you're on the 5 key. And vice versa, there's no other key that could move to the 5 key. So we could have just left it out, but then that would have looked like a really weird dial pad. So we leave it in, even though we're all gonna admit and agree the 5 key doesn't really matter in this problem.

[00:04:16]
So there are ten numbers, but really only nine of them actually matter, you with me? All right, the key question that we need to start with is, what are the nearby keys to me? In other words, what are the places that I can move, if I'm on the 1 key, the answer is 6 and 8.

[00:04:39]
If I'm on the 2 key, the answer is 7 and 9, if I'm on the 6 key, it's 1, 7, and 0, right? So this notion of determining what are my nearby keys, that's gonna be one core thing that we need to solve, that'll be one of our things.

[00:04:52]
And indeed, if you look at the code in the repo, you'll see there's a todo for us to figure out what are my nearby keys. The second part of the problem is knowing that information, once I know what my nearby keys are. If I started on any given key, like the 1 key, and I told you that you could make a certain number of hops, like 4 or 20.

[00:05:18]
What are all of the possible different paths that you might take making all those jumps? In fact, how many different paths could you take, if you started on a given key and you made a certain number of jumps? And the first thing that you should observe about that is that I could start on the 1 key and jump to the 6th key.

[00:05:41]
And then I could jump right back to the 1 key, that's a totally valid move. So given only the count of hops that I can take and the starting key, tell me the count of how many possible different paths I could take around this dial pad. That's the classic statement of the Knight's Dialer.

[00:06:01]
It's a counting problem, you with me? We're not really asking you to draw out all the pads or anything like that, list them all out, we're simply asking you to count them. There are a lot of counting problems in algorithmics, and this is one of them. But here's where I've extended things because there's a third kind of problem that we might tackle within the scope of Knight's Dialer.

[00:06:26]
It's one that I find more interesting even than the counting. Which is, what are the paths that I can take from any given starting key without ever hitting any repeats? In other words, I'm not gonna allow 1, 6, 1. I'm gonna have to go from 1, 6, and then to 7, and then to 2, and then to 9.

[00:06:49]
What are those paths? How many of those are there? You with me? That's an extension to this problem that is not part of the normal classical statement, but we're gonna track that. So that'll be our third part of this problem, is we want to compute the unique paths.

[00:07:06]
Or there's another way of saying this in DSA and computer science terms. Which is to say that the paths that we're counting are what we call cyclic paths, meaning we allow cycles. And we also want to enumerate, or go through, all of the acyclic paths, meaning paths that do not have cycles.

[00:07:28]
So we are counting the cyclic paths because there are many, many, many, many more of those. And we're going to actually enumerate acyclic paths, cuz it's actually very small number of those. If you think about it, there's only nine possible numbers to jump to. So what is the longest possible acyclic path, 9, right?

[00:07:54]
That's the longest possible, actually eight jumps, but nine numbers that we would visit. That's the longest possible path, so we want to list out all of those acyclic paths from a starting number.