12 Beginner Python Projects - Coding Course

What's up code squad. My name is Kyla gang.  And today in this video I prepared 12 beginner   Python projects. And I'm going to walk you guys  through the implementations for all of them. Now,   a couple of notes before we begin, here's a  list of all the projects. These projects are in   order from what I consider to be the easiest,  most beginner friendly to the most complex.   They'll range from madlibs, which is a string  concatenation to an unbeatable, tic tac toe AI   to photo editing in Python. In addition, you might  see me make a few mistakes run into a few bugs   during these tutorials. The reason why I decided  to leave these in there is because I think it's a   very important skill to know how to go back and  fix your mistakes. Because everybody inevitably   makes mistakes. And I thought it would be  really good for you guys to see some of my logic   when I go back, and I fix them. And of  course, if you guys are interested in more,   be sure to subscribe to my YouTube channel, Kylie  Yang for coding projects, and just fun computer   science related topics. Follow me on Twitch Kyle  Yang for live streams of unedited coding sessions   and follow me on instagram and twitter at  Kylie Whiting. Okay, so let's get started.   In a traditional Madlib, you would have a bunch of  blanks in a paragraph. And you would have somebody   fill out those blanks and then read the paragraph  out loud with the words that they chose in those   blanks. So we're going to recreate this project  in Python using string concatenation. So let's   talk a little bit about string concatenation.  In other words, how do you put strings together.   So suppose we want to create a string that says  subscribe to blank, and this blank is going   to be a YouTuber. So we can create a variable  YouTuber, and this is going to be some string.   So there are a few ways to create the  string that says subscribe to the YouTuber.   One way to do it is we can have the string  subscribe to, and then we can concatenate it   with youtuber by just adding a plus sign. The  second way is to have a string subscribe to   and then have these curly braces. And what we  can do is we can call string dot format YouTuber,   and what this is going to do, it's going to put  the YouTuber, whatever the value of youtuber is   into where the curly braces are in that string.  And now the third method, and what I think is the   most straightforward is called an F string. And  an F string, we can define this f string by just   prepending an F in front of the string. And then  we can say subscribe to and then the curly braces.   And then directly in the curly braces, we can  add the variable name YouTuber. So with an   empty string, let's try running this real fast  just to check that there are like no errors,   and they all turn out to be the same thing.  So let's open terminal and run the script.   So here we see subscribe to blank, three times.  No errors. Okay, everything looks good. So now   let's try with the YouTuber actually filled  out to some string. Let's just try Kylie Yang.   So let's run this again. And you'll see that  now all three of these print statements,   say subscribe to Kylie Yang. And so for the  sake of this Madlib, we're going to use the   last one the F string just because I think that's  the cleanest way to express string concatenation.   Okay, so starting this Madlib. So first we're just  going to assign Madlib variable equals and then an   F string. So let's say computer programming  is so blank or blank is some adjective. And   now we have to define this variable adjective.  So we can say adjective equals input. So here,   we're going to get a user input.  And let's do adjective as a prompt.   It makes me so excited all the time. Because  I love to blank. Let's make that a verb.   And this break right here, this is just saying,  This is telling Python Hey, this string has gone   on to the next line. That's all that little  slash there is. Stay hydrated and verb to   like you are and let's make this a famous person.  exclamation mark. Okay, so let's just use that   example right there. And now Don't forget to  define these variables verb one verb two and   famous person. So up here we're gonna say verb one  equals input. And the prompt is just going to be   verb because all we want is a user to input some  verb. And now verb two is going to be the same.   thing, but instead verb to will be the name of  the variable. And then famous person, again equals   input. So we're getting user input. And we're  gonna say famous person as a prompt. Okay, so I   actually have to remove the space. And then at the  end, we have to print the Madlib to show the user.   So that's it though. Now we can run this  code. Alright, so adjective let's do amazing   verb. How about skydive, and then  another verb jump, and a famous person?   Captain America Okay, so our Madlib is computer  programming is so amazing. It makes me so excited   all the time. Because I love to skydive, stay  hydrated and jump like you are Captain America.   And so yeah, there you have it. That's Madlib in  Python. Alright, so if you guys actually download   my code, which is linked somewhere below, you'll  notice that there's a file called random Mad   libs.py. What this is going to do is it'll choose  one of these four madlibs that I prepared, and   it'll let you play that game. Alright, adjective  pretty, another adjective soft, another adjective.   Pretty glow bursts suddenly, across the  enchanted sky above them as an edge of   dazzling sun appeared over the sill of the  nearest mass, the light hit both of their hand   at the same time. So that Voldemort's was suddenly   a flaming water bottle. What did I just  read? Anyways, there's a Madlib for you.   First, I'm going to teach you guys how  to implement a guessing game where the   computer has a secret number. And we are trying  to guess that secret number. So the first step   is actually having the computer generate a secret  number for us to guess. And in order to do that,   we're going to import random. Whenever we  call import random, it actually goes to this   package that comes with Python. And it says,  Hey, all of these functions that are here,   like make these accessible in our scripts,  so that we can call these functions.   So for example, in order to get a random number,  something like random dot Rand int might be very   applicable because it returns a random integer n,  such that A is less than or equal to n less than   or equal to b. So a and b are the parameters of  this function. And we need to pass in arguments.   I'm going to define a function and I'm going  to define this function. Let's say, guess,   I'm going to make x a parameter so that we can  pass that into this random get number function.   So first, we need to get the random number.   And our random number. Well, we're going to use  random dot and then Rand int, which is exactly   what we saw down here. Let's make it between one  and x. Okay, so now, basically, what this is going   to return is a random number for us to guess.  Okay, what's our second step here? Our second step   is, once the computer has a random number, we  need to guess right, we need to guess in Terminal   and input what our guess of the number is, and  the computer will tell us whether it's too high,   too low. Or if we've guessed the number  correctly, I need to keep looping until   I get the right answer, right. So that sounds  like a job for loops. And basically, since we   don't have a predefined universe to iterate over,  we're going to use a while loop. So let's insert   while in there. And now in this while  loop, we need an expression here, right?   And now for this expression, when do we want to  stop this loop, we want to stop it when our guests   number equals the random number. So that means our  expression should be something along the lines of   guess does not equal random number, then we  want to iterate over some things. Now we need   to actually define this guest. And we're not going  to make a guess up here because we're just trying   to initialize the variable tell Python that this  variable exists. So we can go back and change it   later. So after a random number, I'm going to  say guests equals zero, right? Because we don't   want our guests to ever accidentally equal that  random number. and here if guess is zero, well,   random numbers random dot Rand int between one  and x. And that means that it will never be zero.   So while the guests tonight equal the random  number, we're going to get the users guests. So   guests equals input guests a number and we can  even get little fancier here, between one. And   so let's use an F string. And we can do x. Let's  just see what that looks like real fast. Let's   call our function guests at the bottom of our  script. And then let's just print our guests.   Let's see what happened when we run this. Alright,  so if we run this, pick guess a number between one   and 10. Let's do five. Okay, so we've printed the  number, right? And I'm just going to cast this as   integer because I want my guesses to be integers.  So what do we have? so far? The computer has said,   okay, I've gotten a random number. And now we've  set up this loop where I can keep guessing until I   guess, the right number. But that's no fun, right?  We kind of want the computer to give us some   feedback, give us some clues into what's right  and what's wrong. So that means that I'm going   to use some if statements and these statements  are going to tell me Hey, you're kind of high,   kind of low, or, oh, maybe you've gotten it.  Alright, so let's add these if statements in   so if our guests is less than our random number,  then we can print. Sorry, guests again, too low.   All right, but then elsif, our guests is greater  than our random number, then we can print   sorry, guests again, too high. And then if it's  not less than if it's greater than that means it's   just right. It's in that Goldilocks zone, right?  And that means that you have guessed the jackpot,   you have guessed that random number. And so  what do we do that? Well, we actually don't   have to do anything. Because remember this loop.  While the guest does not equal the random number,   it does all of this. But as soon as your guest  equals a random number. So once you've input this   guest, we don't hit any of these if statements.  So then we come back to while the guests is not   equal to number, but now your guests equals  the random number. So it actually breaks out   of this loop. Meaning that at the very end, I can  print. Yay, congrats. You have guessed the number.   And you know what we can even just  tossing a random number in there.   So let's use our F string again. Yay, congrats.  You have guessed the number random number   correctly. Alright, are we ready  to play? So if we go to terminal?   Let's run our script. Okay, it gets a number  between one and 10. I'm going to do four.   Okay, it was too high. So maybe two to low.  Alright, so that means if four is too high, if two   is too low, it has to be three, right? Wow, look  at that. I've guessed the number three correctly.   Alright, so we talked about earlier how the  computer is guessing our number. But we can   also do the complete inverse of that function, we  can come up with a secret number and we can have   the computer try to guess it. So now I'm going  to create a new function called computer guests.   effects. Great, right. And in this function,  let's think about what we actually have to do.   So I have a secret number. And I'm not going to  tell the computer what the secret number is right?   That basically means the computer has a range of  numbers to work with a minimum and a maximum a   low and a high. Okay, so that means let's set the  low and the high initially because we know what   that is without even having to loop over anything.  So I'm going to say low, the lower bound is one,   and the high is x. Because we do have that entire  range between one and x to work with initially   until the user can provide some feedback, we  need to be able to tell the computer if it's too   high or too low, or if they've guessed correctly,  which means that let's initialize a feedback   variable. Alright, feedback. And at first, there  aren't any guesses, nothing's too high, nothing's   too low. So just like how we initialize guests to  be zero, let's initialize this to an empty string.   And now basically, we want to loop over  this feedback expression. So while this   feedback expression does not equal what we're  going to make it represent when it's correct,   let's do c because C for correct. So  while this feedback does not equal C,   Well, the first thing I need the computer to do is  to get a new number. So I'm going to make guessed   random, I'm going to use random dot random again.  And this time we're going between low and high.   Now we don't want it to always be between one  and x, right? Because we want to be able to kind   of change these bounds according to the user's  feedback, because you know that if something is   too high, then anything above that we can kind  of stop considering. And then if it's too low,   anything below that we can stop considering.  So that's why I'm passing in these low and high   values into this random so that we can get a new  number between the bounds that we know has to be   correct. Okay, so we have a guest. And now we're  trying to ask the user for feedback, hey, is our   guest right? Or is it wrong. So here, I'm going to  do feedback equals, and let's say user input is.   So I'm going to use an F string again. So  I can put this variable inside my string   is guess, too high. And let's make that Ah, okay,  too low, that's going to be L, or correct. And   that, of course, is C, the user is going to input  h, l, or C, I have these uppercase letters here,   this lowercase up here, I'm just going to make  this input lowercase. So adding that dot lower   at the end is going to take whatever this string  is from the input, and just lowercase it. So H,   L and C are all lowercase. If we try to compare  capitalized letter to its lowercase letter, it   actually does not come out to be equal. So that's  why I'm adding this lower in there. Let's look at   our different cases again. So if feedback is H,  so basically, we're saying okay, if it's too high,   then that means we want to adjust our upper bound  is a very guess, is too high. Like, you know, if   we're guessing out of 10, and we guess eight, the  other person says, Oh, that's too high, that means   out nine and 10 cannot be the numbers, that would  mean that we need to adjust our upper bound, our   upper bound is actually going to be what we just  guessed, minus one. Because for example, if we get   eight, then we know it's between one and seven  if eight is too high. And now if the feedback   is L, we know that our low bound has to be guess,  plus one, right? Because it can't be that low   number. And of course, we can make that an LS LS  makes it a little bit cleaner, because feedback   can only be h, or it can be L, like it can't be  both of them. And of course, if it's correct,   we don't have to have an if statement for that.  Because our while loop kind of takes care of that.   So at the very end, of course, when we  exit our while loop, that means that   the computer has guessed our number correctly.  Print, yay, the computer, guess your number.   Let's put the number in there correctly. And  so I'm going to put a guess, in this f string,   because so that means that outside of this  for loop, this variable guess is actually   the last thing that the computer had guessed.  Which means that you know, if it's correct,   then that is our secret number. All right. So  basically, one other thing that I've noticed   is random dot Rand and will actually throw  an error if low and high are the same number.   So we can do a couple of things, we could  theoretically put this statement up here that   prevents this loop from continuing if low equals  high, because if low and high are the same number,   that means that you've narrowed it down,  right? If you're saying eight is too low,   and your new low is nine, and then you're saying  10 is too high, so then your new highs nine,   well, that means that the computer has actually  narrowed down the number to nine. But if we break   too early, so if we're saying and low does not  equal high, then we don't actually iterate over   this loop. When our low is nine or higher is nine,  right? We just break and we say, Oh, the computer,   yes, your number correctly. But the thing is, we  actually want the user to say that the computer   has chosen it correctly. So that's why we can't  actually have that statement in there. Instead,   what we want is we want to say if low does not  equal high, then our guests is a random number   between low and high. Otherwise, so this means  if low does equal high, otherwise, our guests is   equal to one of them. So let's just say whoa, I  mean, it doesn't really matter. This could also   be high, because low is equal to high. Alright,  so then our feedback actually puts this number   into here and it prompts the user to say, hey,  that's, that's right. So then at the very end,   we're saying okay, the computer guessed your  number guess correctly. All right, let's try this.   file. Oh, shoot, and you can, let's say  our new secret number is six. So that's   too low. Seven. Oh, that's too high.  Six. Okay, that's correct. Yay.   And you know, we can even  play this with like 1000.   Alright, so for our secret number, let's actually  do the price of aetherium, which is approximately   392. Okay, so Python three main.pi 640, that's  too high to blow, too high, too low, too high.   Close, we're getting closer, oh 393, that's  a little bit too high, too low 392. What   the computer guess our number correctly, look  at that the computer has guessed our number   correctly. Alright, so that's it, just using some  functions and some while loops through, we're   actually able to get our computer to guess our  random number. And for us to be able to guess   our computer's random number. So now when we're  bored, we can play this guessing game. Whoo.   So the next beginner project idea is rock  paper scissors. This one's super simple,   but it's a step up from the previous one.  Here, we're going to be using random. So we   definitely want to import random, and we're  going to be using a function. So basically,   we want some user input, right, because  we want to play against the computer.   So the user is going to put an input, let's use  our for rock, p for paper, or s for scissors.   And then the computer is also going to choose. And  here we're going to do random choice because we   have our three different choices, our P and S. So  now the computer is going to randomly choose one   of these choices. Once we know the user's choice  and the computers choice, we can come up with some   rules in order to determine who wins. So the first  rule is if the user and the computer have both the   same choice, then it's a tie. In this game,  we know that rock beats scissors, scissors,   beats paper, and paper beats rock. So let's  define a helper function is when to see who wins.   And here I'm going to say player versus opponent.  And this will return true if the player wins.   And now we're just going to use  this little rule that we had.   See, so if the player is rock, and the  opponent is scissors, or if the player   is scissors, and the opponent, paper, or  so now we have three conditions, right?   Or the player is paper. And the opponent is rock  that we know that the player has won. So we're   going to return true. So now we're going to ask  up here if the user has one, so is when user or   computer so the computer is opponent and the user  is a player, then return you one, actually, we're   going to return, it's a tie up here. And then  otherwise, we're just going to return you lost,   because if the computer one that we lost, here,  you'll notice that I don't have an if statement   before this last return. And the reason for that  is because if you've already passed these two   cases, and after each of these cases, the function  ends right here, or in this case, if you one,   then it ends right here. The only way that we can  ever reach this line is if we didn't go through   any of these, which is the same, it just saves  you an extra line of code instead of saying else,   or instead of saying if is when computer comma  user, because the only way we get to this line   is if this is true, so we don't even need  that line. So here we're going to print play.   And here I'm actually going to add a  line break and say, what's your choice?   Now let's see what this looks like. What's your  choice are for Rock Paper Paper, Esther scissors.   Think I'm gonna go with scissors.  Oh, I lost play. Rock I won.   So the first thing that we have to do for hanging  man is we have to choose a random English word.   So I actually went on Stack Overflow, and I  found this very relevant question how to pick   a random English word from a list. And if you  scroll down a little bit, there's this like JSON   file that's linked. So I'm just going to click on  that. And when I open it, there's all of this text   And basically what this is, is it's just a very  long list of words that we can use for hang man.   So I can copy and paste this entire list of  English words into a Python file. And I can   assign it to the variable words, which we can use  in our hangman game later. So now I can open a   hang in file. And I know that I want to be able to  choose randomly from this word list. So I'm going   to import random. And then also, I know that I  want the word list that I just made. And I called   my file words that py. So in my hangman file, I'm  going to say from words, which is words.py import   words. And that second words is just this  variable words. So now if I print out words   in my hangman file, I would be able to get that  entire list of words that I just copy and pasted.   So the first step in actually getting  our computer to play Hey, man with us   is the computer has to figure out a word for us  to guess. So we just got this entire list of words   into this Python file. And now we just  have to randomly select a word from it.   But you'll notice if you look through this word  list that some of them actually have spaces,   and dashes in the middle of the word, which we  can't exactly guess in Python, or in hangman.   So we actually have to keep choosing a word until  we get a valid word that we can guess and hang in.   So in order to do that, I'm going to define  a function called get valid word. And I'm   going to pass it a list of words. So the first  thing I'm going to do is assign, you know the   word to random dot choice words. And what random  choices it takes in a list and it randomly chooses   something from that list. So I'm just going to  get a random word from this list. And I'm going to   make a while loop saying while dash or space is  in this word, keep choosing the word. So what this   while loop does is, as long as the statement is  true, it just keeps iterating back and forth until   it's not true anymore, which means that when  it stops iterating, we'll get a word that   doesn't have a space or a dash in it. And then  finally, we're just going to return that word,   we need to be able to keep track of which letters  we've guessed and which letters in the word we've   correctly guessed, we also need a way to keep  track of what is a valid letter, and what is   it. So now we're going to set that up, I'm going  to have word letters a variable that saves all   the letters in a word as a set. And this will  use as a way of keeping track of what's already   been guessed in the word. And then I'm going to  have an alphabet. And basically, I'm just going   to import this already predetermine list of like  uppercase characters in the English dictionary.   And then I'm going to have an empty set called  newsletters, which I will use in order to keep   track of what the user has guessed. Alright,  so now we're going to get some user input.   So basically, what we can do is we can just  ask for user input and Python directly.   And if we run this in Terminal, then the  user can type in, you know, a character.   And we can use that as input. So we're going  to save that as a letter. And I'm just going   to uppercase this because I'm just going to  do everything in uppercase. A lowercase a and   Python is different than an uppercase A. So if you  try to test equality between those two strings,   it actually won't be equal. So I'm just  going to do everything in uppercase.   And basically, if I'm going to, I'm  going to say, Okay, if this is already,   if this is a valid character in the alphabet  that I haven't used yet, that I'm going to   add this to my use letters set. And then, if  the letter that I just guessed is in the word,   then I'm going to remove that letter from word  letters. So every single time I guess correctly,   then this word letters, we're just keeping track  of all the letters in a word, decreases in size.   And then if this user letter that the user just  entered his and use letters, then that means   that they've already used it before, and it's  an invalid guess. So I'm just going to print   something saying, You literally just guessed that  word for that letter. Otherwise, that means that   you know, they typed in something that's not in  the alphabet, and it's not in the newsletters   that they've already guessed. So that just means  that they've typed it in a wrong character. And   we're going to print an error message saying  you didn't type in about Out character.   So now that we can get the user input, we want the  user to be able to keep guessing until they get   the word. So in this case, we're going to be using  a loop. And loops are basically just a way to,   you know, loop around your code and iterate. So,  in this specific case, I want to use a while loop,   because I want the user to just to keep  guessing until they actually guessed the word.   And because every single time we're removing a  letter from word letters, which is a set of the   letters in the word that we haven't seen yet,  I'm just going to keep decrementing that so   the condition that I have to satisfy for when the  user gets all the letters in the word is when the   length of word letters is actually equal to zero.  So while the length of word letters is greater   than zero, I'm going to keep iterating through  this input until they guess all the letters.   So my while condition is going to be while the  length of word letters is greater than zero,   iterate. So let's just add that in there.  So before we can actually play this game   of paying man, we need two things that we  need to tell the user. So the first thing is   what letters they've already used, so that they  can keep track of what they've already guessed.   So we're just going to have a simple print  statement. And then we're going to, say,   space dot join us letters. And what the start  join does is it turns this list into, or iterable,   into a string, separated by whatever the  string is before the dot join. So in this case,   each of these letters will be in  a string separated by a space.   The second thing that we need to do is we need  to tell the user what the current word is,   but with dashes where the characters that they  haven't guessed are. So in this case, I'm going to   first create a list where every single letter  that they've guessed, is shown, and where all   the letters that they haven't guessed, are just  dashes. And then I'm going to take that list. And   I'm going to join it with a space just like above  so that we can create a string using that list.   In that game, I literally could have  guessed as many times as I wanted to.   So let's make this a little bit more fun.  Let's introduce the concept of lives and to   hang and because usually and hang man, you  can only guess until the guy's dead, right.   So let's say that live, let's say you get six  lives. So the first thing we have to do is,   if the user has a letter in Word letters,  then you want to remove the letter.   But if they don't, then that's when you want to  take away a life. So with my logs variable, which   is set to six at the beginning, I'm just going to  subtract one there, and I'm going to tell the user   that your letter, user letter is not in the  word. And then everything else should stay   the same. Now at the very beginning, I'm going  to say where the, where I show the user the   letters that they've already used, I'm gonna, I'm  just going to tell them, you have x lives left.   And then you know, they can guess the letter.  And right now our while loop condition is set to   as long as they still have to guess more  letters in the word they keep playing. But   now we have another condition, right, we have  the condition of lives. So as long as either a   they haven't won yet, which is when the length  of the word letters is greater than zero, or B,   when they haven't died yet. So up here, we're  going to add another condition in this while loop,   we're going to say while the like the word letters  is greater than zero, and lives greater than zero,   then we want them to be able to guess this means  that as soon as they either when, when they,   when they've guess all the letters, then they  exit this while loop or when they've died when   lives equals zero, they exit this while loop. So  at the very end, right now we're telling them that   they've guessed the word correctly. But now that's  not the condition anymore for this while loop.   We also have an aspect of lives. So if  the lie equals zero, then they actually   died. So we say sorry, you died, the word was  blank. Otherwise, in this LC ms, we can say,   yeah, you guess the word. So now let's try again  paying man with all these different components.   Now we're going to create a command line version  of tic tac toe with various types of players. So   either a human can play, or the computer can play.  So humans can play as a computer, humans can play   against each other, or the computer can even play  against the computer. Let's get started, we're   going to split up our player and our game into two  separate classes. So that when we actually play,   we can create a game and then we can tell the  game, hey, this is my x player, and this is   my o player. So the first thing we're going to do  is create a file player.py. And up here, I'm just   going to tell you guys right away, we're probably  going to need math and random, so I'm just going   to import them right now. We're going to have a  bass player class and in this class, we're going   to initialize it with the letter that the player  is going to represent. And this is either x,   or Oh, so that's cross are not in official like to  Tac Toe terms. So self dot letter is going to be   letter. And we want all players to be able to get  their next move. So here, I'm going to say define,   get move, self comma game. And I'm just going to  pass because while this is our bass player class,   and on top of that, we're going to build a random  computer player. And we're going to build a human   player here, we're going to use inheritance in  order to create a random computer player and a   human computer player that builds on top of this  bass player object. And so in our initialization,   we have to initialize the superclass. So we're  going to say super dot init letter. And what   that's going to do is it's going to call this  initialization and the superclass, which is   the player and define get move. So in our  get move function, let's hold off on this for   now. Same thing for the human player. In this  human player, our superclass is still player,   we're going to initialize the same way that we did  the random computer player, and then we're going   to find get move, and again, self comma game. And  let's also come back to this, let's first go and   define the game to see exactly what we're dealing  with when we pass in the game. Let's create   another file. Let's call this one game.py. So in  game.pi, we're going to find class tic tac toe.   And so in this class, what are we going to need,  we're going to need a board, right? Because our   tic tac toe, it's a three by three board. Let's  create that board. For our board, let's just use   a list of length nine, that'll represent the  three by three board. And what we can do is we   can assign an index in this length nine list to  each of the spaces. And then that will represent   our board. What I'm also going to do is I'm  going to have this variable self current winner   that will keep track of whether or not there is  a current winner in this game. And if there is,   Who is it? Well, let's first of all be able to  print the board, right, we're going to want to   see like what's in this board. So for each row,  and here, let's split this up into the rows.   So self dot board, this is indexing into our  length nine list, and then this i times three.   So we're doing i in range three, right? So this  i times three to i plus one times three. So   basically that's saying like which group of three  spaces are we choosing? Is it the first one second   one or third one, and that that represents the  row indices 012. That's the first row indices 345.   That's the second row and then 678, that's the  third row. For each row. What we're going to do   is we're going to print and these are just going  to be some separators. So let's add these and then   dot join row is just saying like join them in a  string where the separator is this vertical line.   So you guys don't have to worry too much about  print board because I don't think it actually   like, contributes much to the logic of the game.  It's just how do you print this? Okay, and then   here for print board numbers, well, this is static  method because it's, it doesn't relate to any   specific board, we don't have to pass in a self.  What this means is, we're just going to print out   which numbers correspond to which spot. And so  for example, here, you can see it's 012, etc. And   so our number board is going to be string, and  then whatever is for each eye in range. Again,   this is a row, right? This number board might seem  kind of scary. But if we think about this for Jane   range three, so that's J equals 012. Here, this  range is j times three, and then j plus one times   three. So this is the exact same range that we  saw up here for each row. So what this is saying   is, essentially, just give me what indices  are in the rows for each of the rows, this   is going to come out to like 012, that's one sub  array, and then 345, that's another sub array, and   then 678, we're going to concatenate the strings  the same way that we did above in print board.   Okay, so now let's actually dig a little deeper  into the logic of the game. Given this board,   we're representing the empty spaces with  the space, we're going to need to know   what are the available moves  after you make a move, right,   so we're going to return a list and this is going  to be a list of indices. So let's actually expand   this out. And then I'm going to show you guys  how to do the list comprehension for it. Let's   initialize moves to an empty list. And then let's  say for icon x, and enumerate self dot board,   enumerate is going to essentially create a  list and assign tuples that have the index   comma the value at that index. So here we have  zero comma x, one comma x and then two comma Oh,   in the support loop, we're going  through each of these tuples.   And we're assigning the first item in the tuple to  I The second item to x. so we can say if x equals   Actually, let's call this spot, because that might  be a little bit more intuitive if spot equals   space. And we know that this is an empty space.  And we know this isn't available to move. So we're   going to append that index, because we want to  know which spaces are available, we're going to   append the index of that spot to moves. And they  at the end, we're going to return moves. Another   way to write this is a list comprehension. And  that would look something like this, I for icom   a spot in enumerate self dot board, if spot equals  space. So this is essentially just condensing this   entire for loop into a single line. It's saying  for icom a spot and in numerating, the board,   if the spot is space, then put AI into this list,  and then we're going to return the entire list.   Easy little one liner makes the code clean. Okay,  so now that we have that function, let's define   get move for our players. So the square that we're  going to choose for the random computer player,   while we're literally going to just choose  a random spot on the board that's empty.   So let's just do random dot choice, which  is going to choose one thing in a list at   random. And we're going to pass in game,  which is our board, game dot available   moves. Again, it's just going to get a random  valid spot. Okay, so the human player, we want   the human to be able to choose a spot based on  some input that we pass in through terminal,   we want the user to keep iterating until they  achieve a valid square. Initially, we're gonna   say valid square equals false. And then the value  is not because the user has an input value yet,   let's say while not valid square, so while valid  square is false, r square is going to be input   and then self dot letter. So x or o player  turn, because we want the user to actually   look at Terminal and not get confused by whose  turn it is. And input move zero through nine.   So what we're going to do is we're going to  incorporate a series of checks to make sure that   this is actually a valid number that we can put  in. So here we're going to wrap it in a trench.   So for the tribe, we're going to say  value. So this Val equals int of square,   remember square is this input that the user has  been put, if we can't cast this to an integer if   we can't cast this to a number, so if they input  like XYZ for square, it's going to raise an error   when you try to cast it to an integer and then  the second part If the value that they give you   is not in gamed out available moves in the list of  available moves, then we can raise a value error.   And so essentially, if either one of these  things goes wrong, then we know it's not valid,   right? If we pass both of those, and we can say  valid square equals true, because it's valid, then   we're going to catch this value error. And we're  going to say, print invalid square, try again.   And so this is going to repeat the loop, we're  going to get the input for the square again,   and we're going to repeat this checker. At the  very end, once we've gotten a valid square,   we're going to return that value at the end. So  it's going to be the human players. Next move.   Okay, so we have our player. So let's now  continue working on our game. So that we   can start playing a game of tic tac toe, we have  part of a representation of a tic tac toe board.   Let's, in order to get the rest of the  functions that we need, let's define a   function called play outside of this class, where  we're passing in a game, an X player, an O player,   and I'm going to pass in this extra variable print  game that's just going to be set to true or false.   And if it's true, it'll print out all the steps.  So this is like if you want to play against it.   But later on, if we want the computer to play  against itself, or like a bunch of iterations,   we don't need to see the computer print out every  single game. So then we can toggle that to false.   If we're printing the game, then we're gonna say  game dot print board numbers, right, because then   we can see which numbers correspond to which spot  and the starting letter, let's just assign that x.   I don't know if that's like, what two tackle  actually starts with, but we're just gonna say x.   Alright, so now while the game still has  empty squares, so while the game is still   like incomplete, we're just going to keep  iterating, right, and we don't have to worry   about the winner. Because the output of this  play, let's just return the winner, we don't   have to worry about continuing this loop, because  we'll break out of it with that return statement.   So in order to check whether the game still has  empty squares, let's create a function within the   class called empty squares, pass in self. And what  we're going to do is we're going to check if there   are any empty squares on the board. So we can  just say return space in self dot board. And space   and self dot board will become a Boolean, empty  squares will just return a Boolean of whether or   not there are empty spaces in the board. And we  might need to know the number of empty squares.   So I'm just gonna say okay, we can  return the length of available moves,   which will return this list. And so we  can just count how many empty spots there   are. We could also say self dot board count,  because this is a list, self dot board count,   and then just space. So that will count  the number of spaces in the board.   All right, so while they're empty squares,  we want to get the move from the appropriate   player. So if the letter equals O, then  we're going to ask the player to get move.   And if not, oh, that means it's x, then we're  going to ask the x player to get the move.   Alright, let's define a function  to actually make a move.   Now that we've gotten the player to get  their next move, we go back up to our game.   And we say define make move. When we make a  move, we need information about what square   the user wants their move to be at. And then  what letter the player is. So we know like   what to assign that square, if the move is valid,  then we make the move, and then we return true.   If it's not a valid move, then we return false.  Nothing should ever be an invalid move. But just   in case if self dot boards square is empty, so  if this This means if at that space on the board,   nothing's there yet, then we assign that letter  to that given square, and we return true. If   that doesn't pass, then we return false.  Okay, so let's put this into our play loop.   So if game dot make move, so if this is valid, if  we want to print the game, we're going to print   letter make some move to square, blank, and  some square let's make an F string there.   And we're gonna say game dot print board, because  we want to see a new representation of the board,   where this spot has now been claimed by this user.  And here, this is just an empty line that we're   going to print. Okay. After we made our move, we  need to alternate letters. So here we're going to   assign letter equal to O if the old letter was x,  otherwise we assigned it to x. And this basically   a different way to rewrite this would just be if  letter equals x, then the new letter is though   otherwise the newletter is x. That's exactly what  we're doing here. We're just switching players.   Okay, but wait, we don't, we're not actually  checking anywhere if anybody wants. So what if   we want, if you think about it, the only time that  you should win a game is like right after you make   a move, right? If you won, if you want a game, you  should win on that move. So we're going to go back   to make move. And after we've placed the letter  on that board, we can toggle current winner   to the winner if there is one. So let's make  another function that will check for the winner.   So after we've made this move, if self dot winner,  and then we're going to pass in our last move,   because that's the one that's going to be  our winning move, right? If self dot winner   then we can assign current winner equal to that  letter. Welcome back to The winner function. But   suppose that we have this checker. So then after  making this move, if we have a current winner,   we can check for the current winner before we  switch letters. And if there is a current winners,   which means, which means that if current winner  is not set to none anymore, then a letter has one,   and we can end the game because then we  can just return the winner of the game.   So in this game, we're going to  return the winner if there is one,   and if there isn't, then we're going to  return none. So that means none as a tie.   And we're going to return the letter of  the winner. So here if game current winner,   well, it was letter, turn, so we can just  return letter, the letter that gave us the win.   Okay, so then also, let's just add in the  non for a tie right now. So at the bottom,   we can say if print game, then after this while  loop is over, we can just print, it's a tie.   All right, now we got to go back and actually  create this function that'll check for a winner,   right? So we can define winner and  then input the square and the letter.   And we know that in tic tac toe, we're a  winner if there's three in a row, anywhere,   but we have to check all the possibilities,  whether that's in the row, column or the diagonal.   Alright, so first, let's check the row. So  the row index, which row it's at is going to   be whatever square that you give it, divided by  three, and then rounded down, right, so that's   what this right here is. So that double dash is  just saying how many times three go into square   row is going to be self dot board. And here we're  going to see this indexing again. But this is   essentially saying, given the row index, get the  row. So here rows is going to be a list of the   items in the row that we've selected. And we can  say, if all. So this is going to be all is saying   like if everything in this list is true, then  this comes out to true otherwise, it comes out   to false. So for all and then, within this list,  we're gonna do another list comprehension. So for   every spot on the row, we're checking whether or  not that spot equals the letter, because that's   how we're checking for three in a row. So if, and  then if all the things in this row are equal to   that letter, so that means that we have three  in a row in this row, then we can return true.   If not, then we keep going right. So then let's  check the column next. And we're going to use   very similar logic. So the column index is okay  divided by three and then take the leftover,   so that's going to tell us which column we were  in the columns is going to be the self dot board.   And here we're going to do another little indexing  trick. But if we take the column index, and then   for every single row, so  that's I, for every single row,   if we add the column index, and we essentially  get every single value in that column, right,   and we're going to put that in a list, and that's  going to be our column. So here column is just   going to get everything in the column where  we just move to. And again, just like above,   we're going to use this if all checker and instead  of row we're just going to replace it with column.   So if everything in the column is equal to the  letter, then we return true. Okay, so now finally,   if that doesn't come out to true, we're going to  check our diagonals. Intuitively, we can kind of   see that the only way to win a diagonal is if  you placed a move that was along a diagonal   here, we're going to check if the square that we  had just moved to is actually an even number 02468   These are the only moves possible because these  are the only these are the diagonal spaces.   So if we assigned 012 to the top row 345678, it's  pretty easy to see that the top left is zero,   the middle is four, and the bottom right is  eight. And then the other diagonal would be two,   four, and six. So that's why here we're  checking if the squares are visible by two.   So that that's basically saying it's even, then  this diagonal one, we're gonna say four is 048.   So this is the top left to bottom right diagonal.  So we're going to put the things in the board that   correspond to 04, and eight into this diagonal  one. And the same thing for diagonal two,   but instead, it's two, four, and six. So this  is the top right to the bottom, left, diagonal.   And once again, we're going to use this if  checker and say if every single spot equals   a letter in the diagonal, so diagonal one,  return true. And again, for this diagonal to,   if every single spot equals a letter in  diagonal two, we're going to return true.   And at the very end, if all these checks fail,  then we don't have a winner. So we return false.   So yeah, that's our Tic Tac Toe game right there.  And so now let's actually play this game. So if   name equals main, if name equals main, first,  we're going to make the x player equal to human   player and assign it the letter X. So actually,  at the very top, we have to go back and we have to   import human player and random computer player  from our player file. Otherwise, this game.py file   has no idea what's in player.pi. But if we add in  this like, import at the top, that we actually got   our human player, and we get our random computer  player. So for our x player, we're going to create   a human player, and we're gonna initialize  it with the letter x. And then our o player,   we're going to make that our random computer  player and assign that an O. And then our game   is going to be tic tac toe, let's just  call that T. And then we're going to say t   equals an instance of tic tac toe. And we're going  to play tic tac toe. So this is a game x player,   a player and then we're going to set  print game equal to true right here.   Alright, so let's pull up a terminal and  let's play a game. So Python three game.pi.   Alright, so first, I want to move to  four, because I want to be in the middle.   Okay, it's saying it's a tie. That's weird. But  oh, makes a move to square seven. Let's try to   go fix this. It's a tie. So if we go back  into our loop, we actually see that print,   it's a tie is still within this while loop.  And that's not right, what we need to do is   actually on indented to make it fall outside  the while loop. So it's only after there are   no more available spots, which means that there  is a tie Are we going to print, it's a tie.   First, we're going to go again, square four.  Oh is making a move to square five. Okay,   so I actually don't like how as  soon as I said, Okay, go to for   the computers like print out its move immediately.  So what I'm going to do is during this while loop,   so for every single iteration that we switch  on and off, I'm going to add in a tiny pause.   And I can do that by calling time dot sleep. And  let's just say 0.8, that's 0.8 seconds. And at the   very top, we have to import time in order to make  this work. So here, we're going to do a little   tiny break to make things a little bit easier  to read essentially. And let's try rings again.   So we make us move to square four. l makes a move  to square six. And let's try the top left. So   00 goes to three and we want  that bottom right. So let's do   908 we actually have to fix that text too, though.  Okay, so we see that we win though. Alright,   let's go back into the code.  And it should actually be   in a player dot pie here. We're just going to edit  this. It's actually zero to eight. Okay, save it.   So we were able to actually detect that it was  an invalid square and that we had to try again.   So yeah, that is our bare bones  Tic Tac Toe implementation.   Alright, so we created a game  of tic tac toe in Python.   And we created a human player and  we created a random computer player.   But can we do better? Can we make it so that  the computer literally never loses? Maybe ties,   but never loses? And the answer is yes. So  let's take a look at how we're going to do that.   minimax is a decision making algorithm built off  of a Maximizer and minimizer concept. Basically,   you're trying to maximize your win while your  opponent is trying to minimize their loss.   Now, in a game of tic tac toe, we can step through  each state, and see how minimax might help us win   and become victorious. In mini Max, we are trying  to find the best move to make, we can determine   this by trying out all the moves, and figuring  out which one is most optimal. There's something   called a utility function, which is basically a  measurement of how valuable the final result in   that tree is. Now let's take a look at an example  using a partially completed game of tic tac toe.   So in this current board, it's X's turn. And  obviously, the goal is to maximize x since we   want to win. So the first step is to put down  an X in every single possible potential move.   You'll notice that in the middle, we actually  won the game because we formed three in a row.   Now let's talk about this utility  function for a little bit.   Since we want to win, we want our utility to be  positive, since this is a positive value to us.   Now, in addition, I have this factor of three,  because I want to win in as little steps as   possible. So how I got this number is I took  the remaining squares on the board and added   one so that if you did win, you still ended up  with a positive value and not zero. And then I   multiplied it by either plus one or minus one,  depending on who the winner was. So for example,   if Oh had actually won in this situation, with two  squares left, then I would have done negative one,   times two plus one, three, which is negative  three. So moving on from there, we want to map   out all the possible scenarios of gameplay.  So continuing this tree, we have this layer,   and then this layer until the board is filled, or  until somebody has won. Now let's add the utility   function for all of these. Since Oh, one on  the left, we're going to do negative one,   times one plus one, since there's one  square left, which gives us negative two.   In the second one, nobody wins, and  it's a draw, so the value is just zero.   Now on the right, the first one, we went again,  but in this case, we don't have any empty squares.   So we're just going to multiply one by one.  And then on the right, on the far right,   it's a draw again, so we have a value of  zero. Now that we have these utility values,   we can propagate them back up to  find the most optimal path to take.   So at the very bottom level, we have a Maximizer  function, because it's X's turn, there's actually   no decision to be made in the bottom row,  because there's only one option one path to take.   In the second row, it's his turn, and we assume  that Oh, we'll be taking their most optimal path,   which means that we want to minimize the value  that o has. And in this case, on the left hand   side, it's between negative two and zero.  And since negative two is less than zero,   the left gets assign a value or utility value  of negative two, the middle is still three   because there's no additional options after  that. And on the far right, we're choosing   between one and zero. And since zero is less  than one, the far right has a utility of zero.   And the next stage, it's back to X's turn, and  we want to maximize x between negative two,   three and zero. Obviously three is a maximum,  so we would choose that middle path. So now we   know what the most optimal solution is in order  to win in the least number of steps possible.   Alright, so for our implementation, we are  going to create a genius computer player.   And this of course, is going to take  player as a superclass once again,   and here we're going to initialize it the  same way we initialize our other two players.   So in our unbeatable computer player, we also  want to get money. And get move is where all   the magic is gonna happen. At the very beginning,  if all the spaces are available, let's just say,   grab a random spot and just go there. So  we're just randomly going to choose one.   Otherwise. Alright, so now we're going to get  the square based off of the minimax algorithm   that we described. So because of the nature of the  algorithm and how it's recursive, we're going to   define a function minimax, outside of our get move  function, but we're going to call that from here.   So self dot minimax. And we're going to need to  pass in the game and the letter of the player. So   we know that we can win enough the other player.  So at the very end, we return the square that   was returned from our algorithm. And now let's  define the algorithm here. So define minimax,   and then self commerce date, comma, player.  So the reason why I wanted to call the state   and not game was because at every single  iteration of minimax, we pass in a representation,   a screenshot of the game in that state. So I'm  just calling it state, it's just a variable name,   you could call it s, you could call it game, you  call it whatever, I'm going to call it state,   because in my head, we're passing in states,  we're passing in screenshots of the game.   Alright, so the max player is going to  be yourself because you want to maximize   your score. So it's going to be self dot  letter. And then other player is going to be   other players. So whatever the letter is not. So  first, we want to check if the previous move is   opener. Alright, so when we have recursion, we  always need a base case. And this base case is,   well, at the very end of things. Where  are we at. So here, we want to see,   you know, was there a winner in any of the states  that we've passed in, so we know that in our game,   we have a current winner. So if the current  winner is equal to whatever other player is,   then we should return the position. And the score  these we need to keep track of both of these   things for the algorithm to work. So we're going  to turn this into a dictionary, so the position is   none. And the score well, so this is the formula  that I was talking about earlier, we're going to   multiply one times the State DOT number of empty  squares, because we want to maximize the number of   empty squares, we want to get to a win as soon as  possible. plus one, if the other player is the max   player, right? Otherwise, we're going to do the  exact same thing, but multiplied by negative one.   So LS negative one and then State  DOT number of empty squares,   and then plus one. Okay, so if there's no  winner, but if there are empty squares,   well, that means that nobody's won. So our score  is going to be neutral, it's going to be zero.   And the position again, will be none, because we  didn't move anywhere. Alright, so these are our   base cases. Alright, so now here, we're going to  get into the algorithm. So if the player is a max   player, then we're going to initialize a variable  best, and this is going to be a dictionary, that's   going to save the best position to move and the  best score. And because this player is going to   be the max player yourself, you want to maximize  that every single time step. So you're comparing   every single score to the score, and you're trying  to increment it. So that means that we want to   initialize it to the lowest possible score. So at  least one iteration will beat that score. If we   initialize it to negative infinity, anything  that's defined is going to beat that score.   If the player is not the max player, then we want  the position to still be initialized to none.   But the score we want to initialize infinity,  because we're trying to minimize at every single   point. So we're trying to decrease that. So we  have to initialize to like the highest possible   value. So for every single possible move in the  available moves, we're going to do a few things.   So the first step is we're going to make  a move, and we're going to try that spot.   So in step two, we're going to recurse using  many Mac's to simulate a game after making   that move. So what happens, like from there on  if we make that move? Alright, so step three,   we're going to have to undo that move so that  we can try the next one in a future iteration,   right. The fourth and final step is  we need to update the dictionaries,   if necessary. So if your score from that possible  move, actually beats the current best score,   then we want to replace that dictionary with  whatever we get from that possible move. Alright,   so let's get into implementing these. So for step  one, we want to call our State DOT make move,   and this is going to be whatever possible And the  player that's making that move. So player, right,   and then our simulated score is going to be, well,  we just made that move. So now we're going to pass   the new state into mini max again. And so here,  I'm going to call self dot mini max state comma,   and then we're going to alternate players.  So it's going to be the other player.   Step three, we undo the move. So at that possible  move on the board, we reset it to an empty space.   And then we set the state current winner back  to none. So this is undoing whatever move that   we just did, and the simulated score. Okay, so  remember that at the very end, we return this   position and then not right, so we actually  have to set what position we just moved to.   So here, our simulated score position actually  equals the possible move that we've just passed   in. Otherwise, this would kind of get messed up  from like the recursion part. Alright, so now in   our fourth and final step, we say if the player  is the max player, if the sim score is actually   greater than our best score, then we replace this  best dictionary with the sim score dictionary.   Otherwise, this means that your players  actually the mid player and your sim score,   if it's less than your best score, we again  replace our best dictionary with the same   score because we've successfully gotten a lower  score. And so what we're doing is we're trying to   maximize the max player, but minimize the  other player. And at the very, very end,   after we've tried every single possible step,  then our best score, this best dictionary   will contain the best next possible move, and  the best score that can arise from it right,   it ends up returning a dictionary of the position  and the score. So in order to use that in our get   move for our genius computer player,  we have to actually index for position,   and then that'll return the square the  position where we're actually going to go.   Oh, actually, this should be class. Sorry,  that was a little mistake from my end.   All right. And now instead  of random computer player,   let's try playing against the genius computer  player. And we have to of course, import that.   Let's start a game, we're going to go to the  middle square, so for and we get this air.   So let's go back to our code. And where do we  call that? Where does this air coming from?   So we actually said we're missing  an ASP right here. small mistake.   So let's try rewriting this after we fix  that. So four, they go to zero, let's go to   the bottom left looks pretty good. And that  is square six. So let's go to square six.   All right, they go to square two. So we  got a block, we got to go to square one,   they kind of forced our hand one. Alright, they go  to seven. So this, this is going to be a tie game,   right? So no matter where we go, I mean, yeah,  it's a tie. Right? Let's try again. And I'm going   to show you how this algorithm is actually going  to make a move cleverly, to a spot where, like,   it'll win. So it's, I'm just going to show  you, it's going to go there in the middle.   So let's go to the left and see what happens.  So that's where six, the algorithm knows,   to take that bottom spot to win. And here, what  we actually can do is, we can set this genius   computer player to play against a random computer  player. And what I'm going to do is actually   print turn print game to false. And make this  play a bunch of times. So we're gonna keep track   of number of x wins, oh wins, and ties. And then  we're gonna say like, let's run this 1000 times.   Remember that play passes back whoever wins,  right? Alright, so I'm actually going to put   this time dot sleep in print game, otherwise,  it's going to be kind of it's going to slow   it down unnecessarily. So at the very end, our  result is going to be whatever place that data   because that's the winner. So if the result  is x, then we're going to increment x wins   plus equals one. If the result is Oh, then  we're going to increment o wins by one.   And then now if it's none, so that means x doesn't  win or doesn't win the we're going to increment   ties by one and then at the very end, we're gonna  print like who won what, right so after 1000   iterations, we see x wins. x wins. We see oh wins.  Oh wins. And then we see ties number of ties.   Alright, let's try running this 1000 times.  This actually takes a while to run. So let's do   a little bit of magic called video editing. And  bam, we see that after 1000 iterations, we see   0x, one 793, a wins, and 207 ties. And you  can run this with the human with the random   computer player as x or Oh, but if you're  playing against a genius computer player,   you will realize that it never loses. It  only wins and it only ties but it never   loses. You can run this with like a  million iterations and it will not lose.   Before we implement binary search, let's actually  understand what binary search is binary search   algorithm is a divide and conquer algorithm,  which actually helps you search an ordered list   faster than just scanning every single element  and asking, Hey, is it Is this it? Is this it.   And what I mean by dividing conquer is that  binary search essentially works like this. So   assume that we have some list of ordered elements  from least to greatest. And we're trying to see   if this target is in the list, and if it is, then  return the index of where it is. So essentially,   we're searching this list for this target. So what  we can do in binary search is we can go to that   middle element of this list, and we can ask, Hey,  is the target equal less than or greater than this   middle element? If it's equal to then Well, we've  found it right. But if it's less than one, then we   know that it actually has to be on the left side  of that element. And we can completely disregard   searching anything greater than that element,  so we can completely disregard the right hand   side of that list. And now vice versa,  if it's greater than that middle element,   then we only have to search the right half  of the list. And now, again, we can reiterate   on that one section. So we divide and then we  conquer that one section. So in that left side,   let's say that our target is smaller than so let's  say Our target is seven, and seven is less than   15. So on that left hand side, what we can do  is we can redo the exact same thing, take the   middle of that left hand side, our target is less  than, greater than or equal to if it's equal to,   we're done, we found it. If it's less  than, again, we look at the left hand side,   if it's greater than that, we look at the right  hand side. But up to that middle point where we've   already checked these, we're limiting ourselves  to that left hand side of the array. Let's say   that our target is actually greater than this next  middle. And so then we look again on that right   hand side of the array. And you can imagine how,  with a really, really big array, we keep dividing   in half every single time, because eventually,  it'll either be the midpoint of a bigger array,   or we'll come down to like a sub array of like  size one. And then we found our element there.   So in this project, I'm actually going to prove  that binary search is faster than naive searching   by naive search, I just mean, you're iterating  through the entire list. And you're asking, Hey,   does this value cool our target? What about here,  here, here, here, here, and so on. And so you're   basically asking every single element  until you hit whatever your target is.   So now you've searched we're scanning the entire  list asking if it's equal to the target. If it is,   then we return the index. If not, then we return  negative one. So let's define naive search, we're   going to give it a list L and a target. So for  i in range, length l. So for every single index,   if l at that index is a target,  then we return that index.   Otherwise, we've gone through the entire  list, nothing's there, we return negative one.   For example, our l could be one 310  12, right? And if 10 is our target,   then we're saying okay, for the first  I, so if I will zero or element numbers,   one that does not equal the target, keep going.  So then three, the three equal target, no,   keep going. Alright, so now we're at index two.  Okay, well, 10 equals the target. So we return   to and if it's not in there, then we end  up returning negative one at the very end.   Okay, so then binary search uses again,  divide and conquer. So we will leverage   the fact that our list is sorted  in order to make our search faster.   So let's define binary search and then  give it again a list L and a target.   Alright, so here I'm going to provide  another example and I'm actually To add   one more element in here, so it's one longer  than our previous example. So 135 1012. And   let's say we're searching for 10. Again. And so  here, we're just saying, okay, it should return   three, index three, because 10 is at index  three. So the first thing that we have to   do is we have to find our midpoint. So our  midpoint is going to be the length of this list,   and then divided by two, but rounded down and this  double dash here, this means this means how many   times to go into length, right, so that's going to  give us approximately the index of the midpoint.   So now, if l at this midpoint, so this list  at the midpoint is equal to the target,   then we can return that midpoint  right there, because that's our index.   Now, if the target is less than the value at that  midpoint, so our targets 10, our values five,   so this is comparing 10, less than five, right?  Which is not true. But if it were, again, this is   saying like chop off half of the list, and iterate  over only one section of it. So we're going to   recurse. So we're going to use binary search  again, on that one section that we're given,   which here would be one comma three, if this value  if this statement had been true. So again, we're   gonna have to pass in some list, and I'm just  gonna leave this as l For now, we have to divide   it, we're not dividing anything right now. But  I'll get back to it. So then in the L statement,   well, this means that the target has to be  greater than whatever values at that midpoint,   so we only check what's to the right of it. Right.  So then we do another binary search. All right,   now these two, I told you guys, I would get back  to the fact that we're going to divide it in a   bit. And what we can do is, we could theoretically  say, okay, actually just pass in that half of the   array, so we could index L, so that it's the  left or right hand side, but then we just have   to add the index back in another way is that we  can add in low and high into our binary search,   and these are going to be the lowest indices  to the highest indices that we search.   And then here, when we recurse, we can say the low  is equal to the current low, but the new high is   going to be the midpoint minus one. And then for  the other side, we can say the low is now going to   be, well, the next one after the midpoint, all the  way until whatever the original high value was,   and again, low and higher indices. So these are  all the indices in our list that we can check. And   these are just bounds on the indices. Alright, so  first, if low is none, then let's set low to zero   because we want low to be the lowest possible  index that we can check. And then high if high   is none, high is going to be the highest possible  index that we can check, which is length L minus   one. All right, and then for our midpoint, instead  of just the length of L, we're going to change   this to low plus high because remember, this  is the lowest indicee plus the highest indicee.   So the average of those two would be whatever  index is in the middle. So that's our midpoint.   How do we know that our targets not even  in the list, what we can do is we can say,   All right down here every single time Our  target is to the left of the midpoint,   we're actually subtracting one from the high. And  then every single time Our target is to the right   of the midpoint, we're adding one to the midpoint  for the low. So if the high bound is ever less   than the low bound, that should never happen,  theoretically, if this were iterated properly,   the only time is when it can't find it, though the  target is not in the list, then we return negative   one. So that's our case of you know, it's it's  not in this list. Alright, so if name equals main,   then let's create a list 135 1012. Let's  make the target equal to 10. And then let's   print naive search of this list and then the  target. And then also binary search for that.   Alright, opening terminal. Let's run the script.   And we see both of them return three. All right,  now let's do a little bit of timing analysis to   show you guys that it actually works to not check  the entire list. Alright, so let's set legs to   10,000. And so here we're going to just build a  random sorted list of life 10,000. Let's say the   values in our sorted list, let's initialize it to  a set first. And then while the length of the set   is less than length, well, we're going to add some  random integer. And just to have bounds on this,   let's do something like negative three times the  length of the list and then all the way till three   times the length of the list. So that gives us  a range of like Negative 30,000 to 30,000 for   our algorithm to just choose a random  number and add it into this list.   Alright, so then after this is  done, then we're going to say,   okay, make the sorted list into a list, and  then sorted. So that's what sorted is. So and   then we're going to reassign this to the variable  sorted list. And then we're going to import time,   because well, we're gonna want to time  how long it takes for each of those.   And how we're gonna do that is we're gonna say,  okay, start equals time, that time, so that gets a   time right now. And then we're going to call naive  search on the sorted list, and get some target.   And let's actually say, let's iterate  through every single item in this list,   and try to find that item in the list. So  for target in the sorted list, so that means   we're going through the inherits word list  and making everything the target, and then   running naive search on that one target. So we're  basically running naive search 10,000 times here.   And the end time is going to be again  time dot time, at that spot. And so   then the knife search time is actually  just the end time minus the start time.   And so we can actually do this per  iteration if we divide it by length. So   for each iteration, on average, it's going to be  n minus start, and then divide that by length,   number of seconds. And again, we're gonna  do the exact same thing for binary search,   but make it binary search. So let's run that.   Okay, we see that naive search takes approximately  like point 443, like millisecond, so that's   443 microseconds, whereas binary search, I  mean, it takes 6.8 microseconds. So let's   compare that that's like 6.8, compared to 400,  something for a nice search. So yeah, basically,   if you ever have to search a sorted list, never  search every single item. I'm going to show you   guys how to build a command line version of  Minesweeper that looks something like this.   We're going to be using recursion and classes  to build our game. Now, before we get started,   I just want to say that I'm building a very  bare bones command line version of this game,   because I believe that when you're learning  how to code, if you actually want to learn how   to translate your ideas and algorithms into  Python, the bulk of that is going to be in   actually implementing the game, not figuring out  how the UI works. I think that the UI while it's   important, it is somewhat secondary, to actually  learning the coding process and the algorithmic   process that's involved with building these games.  Let's start off by defining the play function.   So here, our goal of this function is to play  the game. So we're going to find play pass in a   dimension size, which is going to be the size of  the board, and the number of bombs on the board.   Alright, so in step one, we're going to create  the board and plant the bonds. In step two,   we're going to show the user the board and ask  them where they want to go. And now step three,   well, if the location is a bomb, then we show  the game over message because they just dug   where there was a bomb and but if the location  is not a bomb, then we dig recursively until   each square is at least next to a bomb, right? So  you think about how Minesweeper works if you dig   somewhere, and it's empty, and everything around  it is empty, then you keep digging until you get   to a number and that number represents that that  square is next to a bomb. And then in step four,   we repeat steps two and three until there are  no more places to dig. And then we've achieved   victory. Alright, so right now we're just going to  say path because we'll get back to this function.   Okay, so let's take advantage of our  object oriented programming tools that   we have in Python. And let's create a board  object to represent the Minesweeper game.   So this is where we can say, create a new object,  or dig here, or render this game for this object.   Let's define a class called board. And here we're  going to initialize it with the dimension size,   and the number of boards. So let's keep track  of these parameters because they're going to   be helpful later on. So let's assign self doubt,  dimension, size, dim size to the dimension size   that was passed in. And then self dot number of  bombs to the number of bombs that will pass in.   And then we're going to create the board. But  let's get back to that. And at the very end,   we're going to initialize a set to keep track of  which locations we've uncovered which locations   we've dug in where the user has gone. So self dot  dog is going to be an empty set. Okay, and then   let's create the board. So let's actually use a  helper function. So self dot board equals self   dot make new boards. And here we're going  to plant the bombs to. So let's define that.   Alright, so we're going to find, make  new board, pass and self. And basically,   this is going to construct a new board based  on the dimension size and the number of bombs   that we pass in. And there are a bunch of  different representations that we can use,   that can be like a list of lists where each  sub list is just a row of this board. So here,   we're going to generate a new board, this board  is going to equal it's going to be none and   then repeat that dimension size number of times,  because that's how long we want this list to be.   And then we're going to have dimension size  number of these lists so that we can get   a square board. And so this creates an array that  looks something like this, it's just going to   be a board where it's non non non non non etc,  for whatever dimension size that we define it.   So then next, we have to plant the bonds. So here,  we're going to say bombs planted equals zero,   we're just going to use a while loop. And we can  say, while bonds planted is less than cell phone   number bombs, we can pick a random location  for the bomb, right, so let's actually go up   here and let's import random. And now for  the location, we're going to do random dot   Rand int, and somewhere between zero and CELTA  dimension, size squared minus one. So you can   think about this logic as like, we're literally  assigning a number from zero, you know, to the   number of spots on the board, and we're assigning  each spot on the board its own unique ID. And   then this random dot Rand n is returning a random  integer n, such a is between the bound A and B. So   a would be zero, B would be the largest ID in that  list. And then here, we want to actually get the   row and the column of that ID that we've chosen  from this random selector. So we're going to do   the location and then this double slash self  dot dem size. And what this is going to do,   it's going to say, how many times is my dimension  size, go into whatever location that I've chosen,   that's going to be the row that we're indexing in.  And then now, once we have the row, how do we know   which column we have to divide by the dimension  size, and then whatever index is leftover,   that's going to be how far into that list, we  have to index in order to find the column. So   once we have the row index and the column index,  we can index into the board. And then we can say,   if board and then row column, we're going to  index into that specific row column location   on the board, if it equals a bomb, so the stars  what we're going to use to represent the bombs,   then this means that we've actually planted  a bomb there already. So we're not going to   increase bombs planted, right? Instead, we're  just going to keep going. And this is actually   the reason why I'm using a while loop and not a  for loop. Because in a for loop, you know, every   single time we skip, we're like continue, we're  still counting that as an iteration. But here,   I only want to increment when I actually get  something that's not a bomb yet. And then I plant   the bomb. So yeah, that's why I'm using a counter.  And that's why I'm saying, hey, check it, this is   a bomb, if it is keep going. If not, then we're  actually going to plant the bomb. And then we're   going to increment this counter bombs planted. And  at the very end, I'm going to return the board.   Alright, so that is making our new board  we're going to plant the bombs right there.   Alright, so what other information is useful?  Well, we want to know, at each spot on this board,   how many bonds are around that spot that's going  to help us when we choose where to actually   dig right when the user input something, well, how  do we know where you know whether or not we should   keep digging around it? And yes, we can implement  a check at each point where we say like, oh,   if we did here, we're going to check all its  neighbors and we're going to dig again and,   you know, so on. But we can also just assign  values to every single space on the board that   represents How many bonds are in the neighboring  spaces. So let's call that assign values to board.   So here let's define assign  values to board and pass in self.   Alright, so now that we have the bombs planted,  we're assigning a number zero through eight   for all the empty spaces that don't have  bombs. And this is basically representing   how many neighboring bombs are  there, we can pre compute these,   and it'll save some effort checking what's  around that square later on. Basically,   we want to check every row and every column.  So for our end range, self dot dimension, size,   for C and range self that dimension size, this is  going to be the row index and the column index.   So if the item at the board, so if, at those  indices on the board, it's a bomb, we're going to   continue, right, because we don't want to actually  override any of the bombs that we've planted.   But if it's not, then we pass this if statement,  and then we say, okay, for this location on the   board, let's create a new function called get num  neighboring bonds, pass in the row index and the   column index. And then this function is going to  give us the number of bombs that is surrounding   that row, comma, column. Alright, so let's define  this define get number of neighboring bombs, we're   passing in the row and the column. Like if you're  confused of why I have our comma see up top,   and then row comma call, these are just variable  names, you just have to make sure that they match   where you're actually calling them. So  for example, when I call the function,   I'm passing it r comma C, because I've defined  R, and I've defined C in my for loop. So those   are variables that I've defined. And now  when I create this new function, I can   call the parameters that get passed in whatever I  want, right. And so here, the R would correspond   to the row and the C would correspond to the  column. So now let's iterate through each of the   neighboring positions and sum up the number of  bombs. So here, I've kind of imported a list   of all the neighboring positions, you can see  that top left is row minus one column minus one,   and middle is row minus one column, you know, and  so on. And so we're going to check all of these,   and we have to make sure that we don't go out  of bounds. So that's just a little reminder.   Okay, so first, we're going to initialize  the number of neighboring bombs. So just to   a variable set to zero, this  is going to be our counter.   And then we're gonna say for our in range row  minus one row plus one. And then keep in mind   that due to the nature of the range function in  Python, we have to add a plus one to the end.   And then same thing for the column for C and  range column minus one column, plus one plus one.   That should be plus. Alright, so basically, what  we're doing here is for the current row that we're   at, we're checking below and above. And then for  the current column, we're checking to the left and   to the right. And so when we sum up all these  combinations, we get every little piece of the   three by three grid. And then we can say, if  r equals the current row that we've passed in,   and if sequels called the column that we've  passed in, this is basically saying, like this   is our original location, we don't actually have  to check this. So we continue. But if it's not,   if self dot board at RC equal to star, so that  means that there is a bomb at that location,   that means that we have a neighboring bomb, right,  and so we can increment number of neighboring   bombs by one. And then at the very end, after  we've gone through all the neighbors, we're just   going to return the total number of neighboring  bombs. Now we have to go back up here and we have   to make sure that we don't actually go out of  bounds, right, because row What if rho is zero,   what if we're checking the first row row minus one  is going to be negative one that's out of balance.   Here, we're gonna add a max statement just to make  sure that you know row minus one, if it ever goes   past negative one, we're going to take zero every  single time we go below that zero bound. And then   for the upper bound, we're going to do the same  thing. We're in take the men of rho plus one, and   then self dot dimension size, minus one because  that is the maximum index that we can go, right.   And then of course, we're gonna use the exact  same logic for the columns, just like this.   solve some spacing stuff. And so yeah, now  we've got our bounds checking a we can return   the number of neighboring bonds. Alright,  let's go back to our play function now.   So step one is creating the board and planning  the bonds. So what we can do is we can say the   board equals an instance of this board  class, and then we're going to pass in   the dimension size. And the number of bombs  that we've passed into this play function.   And this is going to automatically, you know,  go through that initialization function. And   it's going to initialize the board and plant the  bombs and create an empty set for dog, and so on.   Alright, so now part two, we're going to show  the use of the board and ask where they want   to dig. And then we're gonna check if the  location is a bomb is not a bomb, we're going   to dig recursively. So let's actually go back  and let's implement some of these functions,   so that we have them, you know, handy when  we need them. So let's define a function   called dig within the board class. And we  can dig at a certain row and column index.   So we're digging at whatever  location the user has specified.   And let's return true if it's a successful dig.  And then a false. If we've actually dug a bomb,   it's game over and we've lost. So there are a few  scenarios here, right either, you know, we can dig   somewhere and we hit a bomb, and then it's game  over, we can dig out a location with neighboring   bombs. And then you know, we finish the day  because we've uncovered a number that's not zero.   But we might also be digging at a spot where  there are no neighboring bonds. And in that case,   we want to dig its neighbors until we actually  get somewhere where there are neighboring bombs.   So the first thing that we want to do when  we dig at a row, comma column, is we want   to add a tuple to self dot dug to make sure that  we're keeping track of where we've actually dug.   And then we're going to check the  board at that row and column. So   in our first scenario, if it's a bomb,  we return false if there's a bomb dog.   Now, if we check that space, and you know, it's a  number that's greater than zero, that means that   we've dug out a location with neighboring bombs.  And we finish the dig. So we just return true   because we did not take a bomb. So now if at that  row and column on the board, it's not a bomb,   it's not a number greater than zero, it  means that that spot is equal to zero,   right? So here, we're going to use the same  logic from get number of neighboring bombs,   where we're checking for the neighbors. And let's  paste that down here. So here, we're gonna check   R and C for all the neighbors. And so if r comma C  is in self dot dog, then we continue, because this   is basically saying, you know, don't dig where  you've already dug. That's pointless, right?   But after that, if it's not, then we dig at  that location. So we pass in our commissie   into this dig function again. And  we continue through all of this,   there shouldn't be a way where we ever get to a  bomb, right? Because we should always be stopping   at some square right before a bomb. So at  the very end, we're going to return true.   So I'm just going to add one more thing to this  Minesweeper game. This underscore underscore   string underscore, underscore. And so this is a  magic function, where if you call print on this   board, it's going to you know, it's going  to print out whatever the string function   returns. And so here, what we're going to want to  do is we're going to want to return a string that   shows a board to the player. And I'm going to go  over part of this function, but part of it was   kind of just like, like, if you inspect the code,  you'll be able to tell what we're kind of doing.   Okay, so first, we're going to create a new array  that represents what the user should see. So let's   call this visible board. So visible board is  going to be well, first, let's just create an   empty board, just as we did above, so that's going  to be our listing list. And it's going to be a sub   list of size, dimension size. And we're gonna  have dimension size number of those lists. So   now for every single row, and for every single  column, we're gonna use this for loop again.   If that row, comma column isn't self dot  dog, that means a user has dog at that spot.   So visible board at that row, and that column is  going to be whatever the actual board value is.   But if it's not dug already, then this is  actually just going to be a space because   the user shouldn't be able to see what's at  that location yet, they haven't dug there.   And we're going to put this entire board  representation in a string. Now what you   can do is you can just honestly return like a  string dot join, and then just this visible board.   In this code, I'm going to make it a little bit  cleaner. And this is all that this stuff here   is doing. It's just some formatting code.  You can look through it if you want, but   I'm just telling you right now, that it's just  completely formatting to make it look prettier   and to make it print out nice. And honestly, I  believe that knowing how to implement Minesweeper   is a lot more important to learn than learning how  to print out a representation of the game. Okay,   so now if we look at steps two, three, and four,  well, step four is basically repeating steps two,   and three, until there are no more places to dig.  So that kind of sounds like a while loop to me,   right. And here, what we're going  to do is we're going to say, well,   while the length of bore dug, so all the places  that you've dug, remember that this is a set,   so there are no duplicates, while the length of  the set is less than the board at dimension size,   squared, because that's how many spaces total  there are on the board minus number of bombs, then   we're gonna allow the user to play because it  means that they still have empty spaces on the   board where they can dig that are not bombs.  So the first thing we're going to do is we're   going to print the board. And we're gonna  ask the user, where would you like to dig?   And we're going to input this as row comma  call. So something like zero comma three.   And now, here, I'm going to use a regex split. So  that's what our e dot split is. It's saying input,   where would you like to dig, this is going to  return a string, and we're going to split that   string by this regex. And so this comma is  going to say, okay, detect any commas. And   then this parentheses slash slash s, well, this is  saying any whitespace, so any spaces that you see,   and the star at the end is going to say, zero  or more of those. So essentially, this is saying   match any part of this string that matches, you  know, just a comma, or a comma space, or a comma   space space, whatever the user types, we're going  to split that. So then we can handle something   like zero comma 00, comma space zero, or zero  comma spaces to space zero, right. And here we   have the import party. So let's go back to the top  and import our E so that we can split our string.   Okay, so now that we've split our input, we now  know what row and column the user is trying to   dig. So we can assign row and column to the user  input at zero and the user input at negative one.   The reason why we use negative one is sometimes  it's ru dot split has some fluff on the inside   of this list. And so if we know the row and  the column are at the beginning and the end,   then why not just take the first  and the last item in this list,   and I'm going to use it, because  we want these to be integers.   So now let's do some bounds checking if rho  is either less than zero or greater than board   dimension size, or if column is less than zero  greater than or equal to the dimension size,   we're out of bounds. So here, we're going to print  invalid location, try again. And we're going to   continue so that we repeat this loop over again,  until the user inputs A valid row and column.   But if the user did input something valid,  then we did get that location. So we can call   board dot dig at row, comma call. And so now we've  already implemented this part. So we don't have to   actually worry about the mechanisms of actually  digging. We know that war dot dig is going to   return true if we've dug successfully and false If  not, and so we can assign a variable called Safe,   whether or not our dig was safe. So whether  or not we've uncovered a bomb or not, right.   So at the very beginning, we're actually going to  say, safe is true, because at the very beginning,   we haven't done anything, you know,  we're safe, we have all of our lives.   And so, if not safe anymore, well, this means  that we've dunk a bomb. And that's bad. We're   gonna call break, because this means Game Over,  we shouldn't be continuing this loop anymore,   we shouldn't be allowing the user to dig. So we're  going to break out of that while loop. And now,   at the very end, there's two ways to exit this  while loop right? Either you've won and there's   no more spaces on the board where you can dig,  or you've dug a bomb. Nothing safe anymore.   And yeah, rip. So let's check which one.  If we're still safe, this means that we've   just run out of spaces today, we've dug  every single possible spot to dig. And so   we've actually won let's print. Congratulations,  you are victorious. Alright, but on the other   hand, if we're not safe, that means that we've  dug a bomb, and we can print. Sorry, game over.   and here we can actually reveal the whole board.   So we're gonna assign board dog to every single  possible value of our commissie on this board.   So this double for loop in this list  comprehension here is just saying,   take every single possible r comma c value of  this board and put it in this list, the very end,   we're going to print the board. And so this  is going to reveal every single possible spot.   Now let's call the play function  to actually play the game.   And we're going to put this in a name equals main  if statement, because this is just good practice.   It's basically saying like if you have a massive  project, but you only want to run this file,   the stuff underneath name equals main will only  run if you type in Python, three minesweeper.pi.   If you have a bunch of imports from bunch  of other files, it's not going to run any   of the code under name equals main in those files,  you're only running what's under name equals main   in that one file. Alright, so let's play the game.  First, let's stay get, I don't know 00. So here,   you see that we've dug at 00. It was zero. So that  means that you know, there were no bombs nearby.   And so we kept digging until you know, there  were some bombs nearby. So for our next spot,   let's just do four comma six. And then let's try  that bottom right corner. So nine, comma nine.   And you'll see that this actually dug a lot. So it  recursively dug everything that you see that zero,   it dug until it hits some spot that was  not zero. And if we look at this spot,   right here, three comma seven. Well, this  is actually, you know, very clearly a bomb,   right? So let's dig there on purpose. So we get  through seven, and it says sorry, game over.   And it actually reveals that yes, this was a  bomb. And this was the entire map of our game   to begin with. There you have it, a  command line version of Minesweeper.   next project is a Sudoku solver. In this tutorial,  you'll be able to see how we can use recursion to   solve any valid Sudoku puzzle. Okay, so the first  thing that we want to do is we want to define our   function solve Sudoku, and we want to pass in  our puzzle. Basically, this function is going   to solve Sudoku using a backtracking technique.  So our puzzle that we pass in is a list of lists   where each enter list is actually a row in the  Sudoku puzzle. So basically, this represents the   nine by nine puzzle. And we're turning whether  or not the solution exists. But in this code,   remember how lists are mutable. So we're actually  mutating this puzzle to be the solution if the   solution exists. So the first step is I'm actually  going to see where on the puzzle I can go. So as a   human, when we're playing Sudoku, we typically  go from where we have the most information,   whether it's the column that's most filled out,  or the row or the little tiny three by three box.   But because we have a computer, we don't have  to do that, what we can do is we can assign a   number to any open space on the board. And then  we can try essentially every single combination,   as long as it's valid. And when we see that it's  not valid, we can actually go back and say, oh,   let's not try three. Let's try four instead.  And if you think about the entire puzzle,   you can essentially come up with  like, every single combination, oh,   it doesn't work from there. Okay, well,  let's take a step back and try all the   combinations there. If none of those  work, then we take another step back,   and try all the combinations there, and so on. And  our computers actually powerful enough to do that.   So that's the technique that we're going to use  here. So our first step is actually to choose   somewhere on the board. To make a guess, in order  to do this, I'm going to create a helper function   called Find Next empty and pass in the puzzle.  So I can find the open spaces on the board.   So here, I'm going to define Find Next  empty passing puzzle. And essentially,   this function is going to find the next row  column on the puzzle that's not filled yet. And   in our puzzle, we're representing any open spaces  with negative one. So we basically want to return   the next space, that equals negative one. So we're  going to return the index of the row. So that's   if this is a list of lists, the first index that  we return is the location in that first list   that are empty spaces that the second value  that we're returning is within that row,   which index is it app. And then of course,  there might be a situation where our entire   board is filled, and there's no empty spaces left.  In that case, we're going to return a tuple non   common none. So keep in mind that we're actually  zero indexing. So we're starting from zero   and our last index is eight. So essentially, what  I can do is I can just go in order, I can say,   hey, check each row and then check each column.  And whatever the first empty space, you get I'm   just going to return the row comma column value of  that. So here I can do for each row in range nine,   so I'm iterating through my nine rows. And then  I can say for that row for each column value   in range nine, so that's my zero through eight.  If the puzzle and then here's how we index,   we pick out the row. And then within that row, we  use C to index again and get the column. So here,   this double indexing basically is returning the  item in the arthro and the C's column. And then   if that equals negative one, then basically  return that Farsi. Otherwise, we return   non common none. If we've iterated through this  entire puzzle, and nothing equals negative one,   then that means that there's no spaces in the  puzzle left, so we can return non common none.   Okay, so then the second step from there is,  well, if there's no word left, we're going to   be implementing some validation checks of like  whether our guests is actually valid or not. And   so if we filled out this entire puzzle, then that  means we're actually done. So here, I'm gonna say   if rho is none, so remember that above, we return  non common none. And then that first none gets   assigned to grow, the second none gets assigned  to call, and so we only have to check one of them.   Now, if row is none, then we can return true  because we've actually solved our puzzle.   But if we haven't, then we can keep  going. Alright, step two, is basically   if there's a place to put our guests, then  we want to come up with a guest between one   and nine. And we want to actually try all of  them until we find a combination that works.   So I'm going to say for gas in range one comma 10.   We start the next step, step three,  which is checking if this is a valid gas.   Okay, so here I'm going to use  another helper function is valid.   And I'm going to pass in the puzzle, guess,  row and column because those, those are the   key pieces of information that we need. In  order to determine whether or not this guess   at this row and column is valid in our puzzle.  So those are the four parameters that we need.   And here I'm going to define the function  is valid. And this basically figures out   whether the guess at that row or column of the  puzzle is valid. And so if there's no conflicts,   then we consider it valid. And then we  return true. We returned false if it's not.   So now we have to follow Sudoku rules. If our  guests equals anything that exists in that row,   or the column already, or even the little three by  three matrix that it's in, then it's not valid. So   let's actually start with the row because that was  the easy one, right? Every single list within our   puzzle represents a row. So if we have the row  index, then we can just say that the row values   are equal to the puzzle index at the row. So if  our guess is in row values, then we can return   false. All right, now the columns, the columns  are a little bit trickier because we actually vary   which row we're indexing into, but we index at the  same spot within each row. So what we can do is we   can create a new list called column values. And  we can say, for each row, I can say for iron rage   nine, so that will go through all the rows, I'm  going to append the value at puzzle at the I throw   at the call column. And so another way to write  this actually is using a list comprehension. Ryan   say take puzzle and then index into I and then  within that row index into call, and then do that   for i in range nine. And then that's essentially  going to build the exact same list. So then,   if the guess is in those values, then we return  false because it means that it's in our column.   And then now this little three by three square  matrix. So this parts a little bit trickier,   because we actually have to figure out where in  the three by three grid we are. And so to do this,   what we're going to do is we're going to find the  starting index of the row of that three by three   matrix, and then we're going to find the starting  column index of that three by three matrix.   And then we're going to say for each row  for each of the columns within that three,   we're going to iterate. So what we can do in  order to find this is actually take the row   index and divide it by three, but throw away the  remainder. What is like, for example, if I have   one divided by three, that comes out 2.333. So the  base, or whatever you want to call it is zero. And   then five divided by three, well, the remainder  is two, but three goes into five one time.   So I'm going to return one. So that I can take  that and I can figure out if it's in the first   set of three rows, the second set of three  rows, or the third set of three rows. And   then of course, in order to get like the actual  index of that, I have to multiply that value by   three. And then it's the exact same logic  for the columns. So when I get row start,   I'm trying to get the start value of these chunks,  right. But then when I'm getting the column,   I'm getting the start value of these chunks,  maybe it's the other way around on YouTube.   When I have both of the starts, I can  say, Hey, now we're going to iterate   through this. So I can say for our end range,  row, start comma, row start plus three, because   we want to iterate through the three rows for C  and range call start to call start plus three,   because we want to iterate through three columns,  if the value of the puzzle equals our guess,   so that means our guess is already in this three  by three matrix. So we just have to return false.   And now at the very end, if we've passed all these  checks that we haven't returned false yet, that   means that while it is valid, and we can return  true. Alright, so let's close those functions.   Okay, now back to our code. So if is valid is  true, then we want to actually place that guess,   on the puzzle at that row, comma column. So what  we can do is we can say puzzle index at the row   index at the column is now equal to our guests.  So we're actually mutating this puzzle array.   So now in step four, we're going  to recursively call our function.   Because if I guess one number, then that number  is actually mutated in my list of lists. And I   can pass that in as my puzzle. And then the  next value becomes mutated, and then so on,   until we reach the very end. So that's  essentially what we're doing here.   We're just solving this entire thing with this new  guests in our array. So if that comes out as true,   then we know that we've actually solved  our Sudoku puzzle so we can return true.   But of course, there's also the case where,  where this is valid check might not be valid.   And there's also this case of well, what if we  didn't solve the Sudoku when we pride that guests   in the row and column. So then, in this case,  we actually need to backtrack, we need to say,   hey, so this guess was wrong. Let's reset it and  move on to the next guess. So here, I'm going to   say puzzle row call equals negative one, because  we didn't successfully place anything there.   So we're essentially just resetting the value at  this row and column. And now you can imagine this   for loop is going to go over, you know, all the  possible values 123456789 for every single empty   spot along this entire puzzle, right. So that  means we're literally trying every single possible   combination for the Sudoku. So in our last step,  if we've tried every single combination possible,   and none of them work, then that means  that we actually can't find a solution.   So this puzzle is unsolvable. And  then we're going to return false.   Alright, so let's actually test this to prove that  it works. Okay. So Python three sudoku.pi, we see   that it comes out as true. And this is our board.  So let's try resizing this to see if we can like,   actually view this as a board. Okay,  there we go. Let's do a couple of checks,   just to make sure that like, our solution is  actually true. So in this first box up here,   let's do 123456789. Alright, and then this column,  you have 123456789 in this row, 123456789. Okay,   so that's pretty convincing that like, this  is actually a good solution. Okay, so a couple   of notes about my implementation. recursion is  confusing recursion kind of makes your brain hurt.   I think it might be better understood this  way. Think about solve Sudoku as a black box,   it should be able to mutate the input puzzle,  so that it's a solution if it's a valid input   puzzle. Now, if it's not a valid input puzzle,  well, then it should be able to identify that   because we've tried every single combination  for that puzzle. So when we make a new guess   we can pass This new guests as a puzzle into  our solve Sudoku function. And if it's solvable,   then we know that our guests was the correct  guests. And we've actually reached a solution.   Now, if it's not solvable, well, then we know that  that guests that we passed in, it's not a solvable   Sudoku solution. So we can say, okay, that wasn't  the right guess. So now let's move on to the next   one. And this is how we kind of go through this  entire puzzle, and mutate the Sudoku array that   we originally passed in to be the correct answer.  I hope that clears things up for you guys.   This next project is going to deal with editing  images in Python, I've prepared some starter code,   if you go to this link down below the one that's  for pi Photoshop, you can click this download   code, you can either download the zip file, or you  can get clone it if you know how to do that. And   let's take a look at what's in this code. So here  I've prepared for you a lake and a city image. And   so we're going to actually be editing these images  and doing like, cool things on those using Python.   So in the png.py file, this is some code  that Johan Rochelle put together. And I just   copy and pasted this from online. Essentially,  what it is, is it's a PNG reader and a writer.   And what that means is while the writer is a PNG  encoder in Python, and then the reader is a PNG   decoder in Python. So it takes a PNG image, and  it decodes it into like a Python array. And vice   versa. For the writer, it takes a Python array,  and it writes it to a PNG file. Pretty cool.   Alright, so now in this image class, this is some  code that I've prepared for you. And we can see in   this initialization, you can either initialize  it with x pixels, y pixels and num channels.   And that will initialize to an empty array  of zeros. Or you can import a file and this   image will represent whatever file that you've  imported. So here we have the input path and   the output path. These are just the folders  for the inputs and the outputs. And here we   have a checker to see if the user is actually  passing x pixels, y pixels, and num channels.   So if it has, we assign those values, and then  we create an empty array essentially, by the way,   number of channels just means like, for example,  typically, when we work with images, we work with   RGB channels, so that's red, green, and blue. And  so that's three channels. That's what we're going   to be using today. And then x pixels and y pixels  will describe the size, the actual physical size   of the image. So here, we're initializing  these to all zero. And this is going to be   a NumPy array of the size, x pixels, y pixels,  num channels. So you can think of this command as   kind of just creating a three dimensional matrix  with dimensions x pixels, y pixels, num channels,   and it's initialized to all zero. That's  essentially what self dot array is initialized to   when you pass in x pixels, wide pixels and  num channels. So if there is a file name,   then we actually read that image from this helper  function, read image and set that to the array.   And then x pixels, y pixels and num channels will  set to that array dot shape. At the very end,   we're going to add this elf statement. Because if  the user hasn't passed in X, Y and num channels,   or if they haven't passed in file name, then we're  actually going to raise a value error saying you   have to input one of those options. Okay, so let's  go over the read image function. So read image,   you have to pass in a filename. And this gamma,  you don't have to worry too much about that. It's   just a way to encode and decode it so that your  operations are not exactly linear. And so here,   I'm using PNG reader, this is from the PNG  file, and I'm passing in the file name, I'm   going to read it as a float. And then here, we're  just going to do a bunch of like resizing things.   I mean, I've given you guys these functions for  a reason. It's because I don't think that they're   critical in understanding how the actual photo  manipulation works. So then in this right image,   so this function call will write  whatever this image represents   to a PNG file, and we're clipping it to between  zero and one. The reason for that is because   when we transform it back into the alpha file,  we're going to scale everything from zero to 255.   And so we're going to do a little bit of reshaping  and write it out to the output file using the PNG   writer. And we're going to resize this array  because we did a little bit of Free shaping,   but we want to keep it in the same representation,  right, we don't want to actually mutate our   representation of the array. So down here, we're  just going to do a quick test to see that this,   like import and export works. So we're going  to call image equals image dot file name. And   let's use the lake. And all we're going to do  is we're going to right to the output file,   we're going to right image test dot png. And  what we should see is that test dot png should   be identical to Lake dot png, because we haven't  manipulated the array at all. So let's try that.   Okay, so test dot png, this is the same image. And  so where the bulk of our code is going to be is in   this transform.py file, we're going to implement a  couple of things here, the first thing that we're   going to implement is adjust brightness.  So how do we adjust the brightness here?   Basically, when we adjust the brightness, we  want to scale each value of the pixel by some   amount. factor that's a value greater than zero is  basically how would you want to brighten or darken   the image by if the factor is less than one, then  we're darkening. And if it's greater than one,   then we're brightening. So first, we have  to figure out how big exactly this image is,   so that we can iterate through each pixel. And so  first, we get image dot array dot shape, because   remember that we've stored our values  in self dot array for that image.   Alright, so basically, we're getting the x y  pixels, and then we're getting the channels. Okay,   and then basically, we're going to make  an empty image so that we don't actually   mutate this one that we're passing in. So this  new image is going to be x pixels equals x pixels,   y pixels equals y pixels. And then num channels  equals num channels. So it's going to be the exact   same size of the array that we pass in. But now  we're just going to be mutating this new image,   so that we don't change the original one. This  is maybe the most intuitive way to do this,   it's non vectorize. If you don't know what that  means, don't worry about it, I'll show you in a   bit. But essentially, we're going to iterate for  every single pixel and x pixels for every single   y pixel. And then for every single value of the  channel. So literally, you can imagine this 3d   matrix and you're iterating through each  individual value. And then for that value,   well, we have to adjust the brightness  by some factor. So we're going to say   new image. And we're going to take the array,  and then we're going to index into whatever   position that we're currently at. So x, y c. So  at index x, y c, we're going to set this equal   to our original image that array at  x, y, z, so that corresponding pixel   and then multiply that by the factor that  the user has input. And then at the very end,   we're just going to return the new image. So let's  actually try this first, see that it works. Here   at the very bottom, I've provided already a little  bit of code that tells you, alright, load the lake   and load the city. So let's lighten the lake  for example. So let's say Brian m equals adjust   brightness lake and then some factor greater  than one. So let's just do 1.7. And then we're   going to write this image to brightened dot png.  So let's try that. So Python three transform.pi,   and we get this image that's slightly brighter,  we can compare this to the lake. If we move   these side by side, you'll notice that  the brain one is like slightly brighter.   So let's actually try also  darkening so dark and image equals   adjust brightness. And then let's make the  factor 0.3. And let's save this as darkened.   And now running that again. Right, we get the  darkened image here. So we can tell that this   is darkened from our original image. And  let's compare these side by side again.   Right so the darkened image does look darker.   Okay, so I mentioned earlier that this is a non  vectorized way to do it. And this is because   this is the most intuitive like this is behind  the scenes if you are brightening or darkening   something you have to adjust every single  pixel value and increase or decrease it.   Alright, so one faster way to do it. Is the  vectorized version. So we said before that these   are NumPy arrays, but the strength of this such  array is that, okay, it's NumPy. But I've always   read it as not B. But basically, the strength  of this array is that you can vectorize these   operations. So if you want to add a constant,  if you want to multiply by some scaling factor,   you can directly just call that array, and then  times that factor, it's significantly faster than   iterating through using a for loop. And we can  see that this does the exact same thing if we   just let it run on the darkened image. So let's  do dark in image two. Let's call the Transform.   Alright, we get this darker image two. And this  looks the exact same as our darkened image.   Let's move on. Okay, we're going to adjust the  contrast now. So when we adjust the contrast,   we're going to be doing the same thing where we  want to create a new image copies so that we can   put new values in without modifying the original  image. We're going to be repeating this for x,   y, and z thing because even if you can vectorize  things, I like this way of just showing you guys   what's actually going on. Here, we're going  to index at x, y, z, that position again in   the array of the new image. So what adjust  contrast does is it adjust the contrast   by increasing the difference from the user defined  midpoint by some amount, factor. So essentially,   if your point is above the factor, then you  take that difference, you scale it by factor,   and then you add back whatever the midpoint was.  Same thing for the other side. So basically,   what you're doing is given this midpoint,  you're making the difference from the midpoint   greater. So we're going to take the image  array, and we're going to take the value at   x comma y comma z, subtract out the midpoint,  and then scale that by the factor factor.   And then we're going to add the midpoint back in.   Alright, and then of course, we return that  new image. And just to show you guys what the   vectorized version would look like, it's just new  image dot array equals the image dot array minus   mid, which is a constant. So it's taking that  entire array, subtracting this made from every   single value in that array, scaling that entire  array by factor, and then adding back a constant   mid. So it's literally taking every single item  in that array and adding the midpoint back in.   Alright, so now let's try adjusting the contrast  of this like image. So let's do increase contrast   equals adjust contrast Lake two, because remember,  the the higher the scaling is, the more contrast   we have, right. And let's do the mid points 0.5,  because we're working on a scale of zero to one   for these images. And now we're going to write the  image, let's call it increase contrast that PNG.   And I'm going to do the same thing,  but let's decrease the contrast now.   So I'm just going to do the same  thing except instead of two,   I'm going to pass in scaling factor 0.5.  And here, let's just call this decrease   contrast. And we're going to write this to  decreased contrast dot png. Let's run this.   Okay, so let's compare these. So this is our  original, and then this is a decreased contrast.   So you can see that it's significantly grayer.  And this gray just means that the contrast has   decreased. And everything's closer to being the  same color, which just happens to be great. And   now this is the increased contrast, you can tell  that like, I mean, the contrast has really been   increased, the colors are a lot more drastic in  this one, right. Okay, so the next thing that   we're going to implement is a blur for the image.  So in the blur, we pass in a kernel size. And this   kernel size just means how wide Do you want this  blur to be? Because essentially, what we're doing   when we're blurring is we're taking that pixel and  averaging it with its surrounding pixels. And so   if the kernel size is for example three, then that  just means we're taking a pixel and we're applying   this kernel around it, so it should be taking the  left and the right neighbors and top and bottom,   the four diagonal corners. For example, a kernel  size of 15 would take the seven to the left,   the seven to the right, and the seven to the  top and bottom and everything in that square.   Alright, so once again, we are going to create  a new image to make a copy to and We're just   going to use a naive implementation of iterating  through each neighbor and then taking the average   at the end, there is a faster way to do it. But  this again is more straightforward to understand,   it's more straightforward to figure out what  we're doing, the faster way to do it would be   to incorporate some sort of, like memorization,  which means so for example, what we would do is we   would move like along the x axis, and every single  time instead of resetting every single neighbor,   we just get rid of one column, and then we add  in the next column, and so on. And that would   decrease the number of operations that we actually  need. But, again, this is more straightforward. So   we're going to use this way for now. First, we're  going to create a variable total equals zero. And   this is going to keep track of what the total of  all the summations of the surrounding pixels are.   And, of course, we need to know how many neighbors  we actually have to go for. So we're going to find   neighbor range as how many times does to  go into the kernel. So how many neighbors   to one side do we need to look at  essentially, is what this represents.   And here, we're going to say, for each exci in  the range, x minus neighbour range to x plus   neighbor range. And remember that we  have to add this plus one, because range   goes from the lowest to the highest minus  one, right? That's just how Python works.   It doesn't include the end of the range. So you  may think that this is all good to go. But what if   x minus a neighbor range is actually less than  zero, then it would go out of bounds. So here,   we're going to add a little bit of bounds  checking. So we're gonna say take the max   of x minus neighbor range, or zero. So for  example, if x minus a range is negative,   then we would say, okay, no, cut it off at  zero. And same thing for x plus neighbor range,   we want this to be the minimum of the maximum  value that we can take, which would be x pixels   minus one. And the reason why we do minus  one is because x pixels is the length right,   and we have to subtract the one because that's the  highest possible value that we can actually index   into. Remember that Python, we do zero indexing.  So then again, we're going to do the same thing   for the Y neighbors. And we're going to  keep these bounds because they are the same,   but instead of x pixels, we do y pixels. And then  we do y plus the neighbor range, every single time   we go through a new neighbor, we want to add  that value from the past an image to our total.   And then at the very end, we can say our new  image at that specific index is equal to the total   and then divided by the total size of the  kernel. So how many things did you just sum over,   we have essentially a box of size nine, right  nine elements in that box. So we have to square   our curl size, and then divide our  total by that. And so that just gives   us the average value over that pixel at its  neighbors. And then we return this new image.   Okay, so I'm actually going to run  this blur on the city because the city,   it has more lines in it, it's  more obvious if it's blurred.   So let's do a blur with size three, blur  three equals blur city, comma three,   and then we're going to write image and call it  blur k three. And now I'm going to do the same   thing with a kernel size of 15. Just so that  I can show you guys the difference between   using a kernel size three, four blur, and using  a kernel size 15 for a blur. So let's run that.   Okay, so our blur of three is done. And  you can see that it looks slightly blurred.   When you compare it to the original, so our  blur, we know that our blur is doing the job,   and it's still running for the 15. Again,  this is not the fastest way to do it.   And the higher your kernel sizes, the slower  the more this is going to make a difference.   It looks like our 15 is now done. Okay, so let's  open that. And now we see that this is like   noticeably much more blurred than our original.  And the reason is literally just because we've   taken more pixels into account when we've  created this average for that one new pixel spot.   Okay, so actually this blur  that we've implemented above,   we've actually implemented  applying a kernel to an image.   And so what that means is we're taking a matrix  and we're applying it to every single pixel, and   summing up whatever values in that matrix times  whatever value is at the corresponding pixel.   So in this blur above, it's a kernel of size n by  n. And each value is actually one over n squared.   All right, let's see how we can create a function  apply kernel. So we can take in any kernel,   and we can apply it to our image. So we're going  to assume that the kernel is square, first thing   that we're going to do is we are going to, again,  paste the code that we had above. And here, our   kernel size is slightly different, because we're  not passing that in. Instead, we have a 2d NumPy   NumPy, 2d NumPy array that represents a kernel  that will use the kernel size is just one   dimension of the kernel 2d array. So we can just  say kernel dot shape, zero, we're going to keep   this iteration through the neighbor range. And  so here, we need to actually find what value of   the kernel corresponds to that pixel that we're  at. So x k is actually whatever exci we're at,   which is representing you know, x  minus that neighbor range, right?   So we're actually going to add that neighbor  range back in and subtract x. And you'll see   that what this does, is essentially, it's  centered around x y, right? So at x, y,   that would be the center of the entire kernel. But  now we're trying to shift the zero, for example,   up to the top left corner. So that's, that's that  those are the operations that we're doing here.   If you draw it out, it makes a lot more sense.  All right, and then for why we're doing by I,   plus a neighbor range, and then subtracting y from  it. Okay, so then the value at the kernel would be   Colonel and then index at x k, and YK. And  we add to our total, this variable total,   we add the image at that index x i y, I see. But  then we multiply it by the kernel value from our   kernel. And so then the new image, that array  is x, y, z, and that is equal to whatever the   sum of all of these are. And then of course,  we're going to return the new image. So let us   so I'm going to, so I'm going to show this  to you guys, on an edge detection kernel.   It's called the sobelle. kernel. So in the  x direction, it's going to be this array   121000, negative one, negative two, negative one,  and this y kernel will be the same, except there   will be some values or switch. So I can write this  in a 3d format that's a little bit easier to see.   And so we're applying this over every single  pixel in our image. And now here's the y's.   Alright, so you see, these are almost the same  thing, right? Let's apply this kernel to the city.   So let's call that civil x apply kernel city.  And then so we'll x kernel. And then we're   going to write this to edge x dot png, we're  going to do the exact same thing for the Y   kernel. And now you'll see why I called  these x and y. So let's run this.   We go here, and we look at the city on  one side. And now let's look at this   edge x. So you can see that this edge x  really like I mean, look at that horizontal   line right there. It's an X edge detection  filter. And now let's take a look at edge y.   So you can see how this one really highlights  the Y edges, right, the edges in the y direction.   It would be really cool if we could just put  these together and create an edge detection   filter. And that's exactly what we're going to do.  Next, we're going to combine these make an edge   detection filter for our image. So here, we're  going to combine images, image one and image two.   So one thing here is the size of image one and the  size of image two have to be the exact same thing,   the arrays have to be the exact same  dimensions. And we're going to again,   copy this shape and create a new image. And  we don't need any of that kernel stuff. But   basically what we're going to do is we're going  to take the value from image one, square it   the value from image to square it, add these two  together and then take the square root of the sum.   We have x y and C and index at the new image  is going to be it's going to be whatever is at   that index in image one squared plus whatever  is at that index and image two squared and then   the entire quantity, square root it So this to  the power of one half is just square root. And   at the end, we're going to return a new image.  And up here we are getting an error because this   should actually be a image one or image two, it  doesn't matter, they should be the same shape,   right? We said that, like when we  defined the function, let's try it on   sobelle, x and y. So uncomment some of this  stuff. And at the very end, we're going to do   soble x, y equals combine images, so about  x, and Sobell y. And so then symbol x y   dot right image, and let's call this edge  x, y dot png already. So let's run this.   So let's set all of these next to each other.  So on the bottom right, we have the original   image, then we have the x and the y filters. And  now check this out. So this is the images combined   the filters combined. And you can see that this  is a pretty cool edge detection filter. And let me   try to actually like zoom in, make this a bigger  image. So this is our image. And check that out.   I mean, you see all the edges in the image,  basically. Pretty cool. Look at that skyline.   And so yeah, using all of these  techniques, you could literally   implement Photoshop, in Python. Pretty cool.   So the last project I have  for you guys is what I call   graph composer. And it's kind of like an  introduction to AI. The idea of graph composer   is derived from a Markov chain. And so in a Markov  chain, you have a node that represents a value,   and it has an arrow pointing to maybe  another node that represents another value.   And that one might be pointing to another  node, which might point back to the first one,   and so on. So you kind of create this entire  network of nodes and directed edges with weights.   In our graph composer, what we're going to do  is we're going to take the text file, and we're   going to transform every single word in that text  file to a node, and then we're going to connect it   to whatever words follow that specific word. So  here's a little snippet about how these Markov   chain graph models actually work. Given a text,  I can generate a graph from the text where all   of the words are represented by vertices, and then  there's a directed edge from each word to the word   that follows in the text. Now the weight of the  edge would just be the number of times that the   new word follows the word that you just connected  it to. So let's take an example sentence,   how about I am subscribed to y cubed, and I  am loving it. so here we can take the letter I   and we can make it a vertex. And now we can  connect an edge with wait one 2am because an   follows I one time so far, and then subscribed, we  are connecting subscribe to an with the directed   edge of wait one, two, y cubed. And Okay, so  now things get a little bit interesting because   after this last, and it goes back to I, we already  have a vertex representing the word eye on our   graph. And so and is going to connect directly  to that vertex that's already in the graph,   okay, but then we have another occurrence of I  Am. So instead of creating another vertex for AM,   we're going to increase the value the  weight of that edge that's currently   there. So instead of one, we're turning  that into two, and then we can continue on   so am is already connected to subscribed. But now  loving also follows AM. So we're going to create a   new vertex for the word loving and assign that  a new edge with weight one, and then of course   it and now it gets connected to loving. So this  would be the graph that represents the sentence.   I am subscribed to y cube, and I am loving it. So  with all the songs of an artist that I've chosen,   I have basically created this like huge graph of  all the words as vertices and edges connecting   them to the words that follow. Okay, so now in  order to generate my poetry, I can randomly choose   a starting word by randomly choosing a starting  vertex, and then I can traverse the graph based   on the edges. So these edges are kind of rules for  which word you can go to next you can only follow   the arrows So here's an example. What I mean  by that, let's take the graph that we just saw.   And let's say that our starting word is y. So  I've got y, there's only one arrow out and to   cube. So my generating is going to be y cubed. And  because and is the only word that follows cubed.   And then of course, I because is the only thing  that follows. And, and then Am I right. So y   cubed, and I am well, now we have two arrows  out of and we have an arrow to subscribe, and   an arrow to loving, we can actually choose either  of these paths. And in my script, I've left that   up to randomness. So that's where these weights  come into play these edge weights come into play,   the higher weighted an edge is, the more likely  that path will get chosen. And this is how I can   generate these sentences all stitched together,  I'm going to show you guys how to actually   implement this in Python. First thing that we're  going to do is we're going to go to this code   that I've already prepared for you. What you can  do here is you can download the code over here,   you can download the zip file, or if you know how  to get clone. Go ahead and do that. Let's take a   look at what's actually in these files. Here. I  have two empty files compose up hi and graph.py.   Under songs I have, well I have a bunch of text  files that represent song lyrics. And we'll get   to those a little bit later. But basically,  we can generate lyrics using our little Markov   chain model. I also have under texts, this  Harry Potter Sorcerer's Stone text file,   and so we'll be able to see how we can actually  generate some text based off of Harry Potter as   well. And in lyrics.py, you guys don't really  have to worry about this. This is just a scraper   that, you know, you input some songs and then the  artists name and it'll scrape lyrics genius. For   those lyrics. Basically, it'll download this exe  and save it in the files that you guys saw before.   So graph.pi and compose up higher fd, because  while those are the things that I'm going to   show you guys how to implement. Let's start with  graph.pi. Also, guys, just letting you know that   in this tutorial, I will make mistakes. I wanted  to show you guys this because I wanted to let you   know that it is very, very normal to have bugs  in your code. It's very normal to make mistakes.   And the important part is to actually know  how to fix them. So just keep that in mind   while you're watching this tutorial. Okay, so in  graph dot pie, this is where we're actually going   to have our Markov chain representation. And,  you know, we know that in this Markov chain,   we're probably going to need randomness. So let's  import random right, now, we're going to define   the graph in terms of vertices, naturally, let's  create a class called vertex. First thing that   we're going to do, we're going to initialize  it, so define a knit, and we pass in a value.   Now this value is going to represent our word  from the text here, we can set self dot value   equals value. So whatever the vertex value is,  that's just going to be the value, that's going   to be the word that it represents. And here, I'm  going to have a dictionary called adjacent. And   what this adjacent dictionary is going to do, it's  going to keep track of you know which vertices   are connected to this vertex. And so those are  going to be our keys. And then the value of that   node is going to be our weight, the weight of the  edge from our current vertex to the adjacent one,   let's create a function called add edge  to. And so we have to pass in a vertex,   because we need to know which vertex we're drawing  the edge to. And let's create a weight of zero,   we can allow the user to manipulate the  weight, so let's pass in the weight.   But you know, we can set it to zero initially,  just in case you don't want to pass it anything   right, what we're going to do is we're going  to put this vertex in the adjacent dictionary,   and the value is again going to be the weight.  So this is all we have to do. Every single time   we're parsing our text, whenever we see a word,  go to another word that's already in its adjacent,   what we want to do is we want to increment that  edge, right? So here, we pass in the vertex. And   then we can say self, adjacent and vertex equals  self dot adjacent, get vertex, comma zeros. And   so this doc yet is just saying, if this vertex  is a key that's currently in self dot adjacent,   we're going to get the value of that vertex.  If it's if it doesn't exist, then we're just   going to default make it zero, and then we add  one. And so this add edge two is basically adding   an edge to the vertex that we're inputting with  some weight. Whereas this increment edge, we're   incrementing, the weight of the edge from  our current vertex to whatever vertex that we   give it. Alright, now that we have a bit of our  vertex representation, we can put this together   in a graph. So let's create another class called  graph. And we're going to of course initialize   this and we're just going to initialize this to  an empty dictionary. Have vertices. And the reason   why we do that is so that whenever we encounter a  new word, we can look it up in this dictionary and   then get the vertex object from this dictionary.  So this is going to be a string to vertex mapping.   Alright, so let's define a  function get vertex values.   And this is basically saying like what are the  values of all the vertices. In other words,   let's just return all the possible words that we  have in the graph. So what we can do is we can   return the set of self dot vertices, keys, and  this is just going to return all the words that   we've encountered so far. And then we can create a  function to add a vertex into our graph. So like,   for example, whenever we encounter a new word, we  want to add a vertex. So when we create a vertex,   we of course have to pass in a value, that's going  to be the word that it represents. We're going to   do self dot vertices value, equal old vertex of  that value. So we create a new vertex object. And   we're putting it in this string to vertex mapping.  And of course, we want to define get vertex,   because sometimes we'll just have a word and we  want to get the vertex object that it represents.   So if we pass in the text, the word value,  Well, okay, we want to return self dot vertices,   and then whatever is that that value, right,  because in this dictionary, we're mapping it to   the vertex and returning that object. But what if  the value isn't actually in the graph. So in that   case, what we want to do is we want to actually  add it in because if we're asking get vertex of   that value, well, it doesn't hurt to ever add  it. So if the value is not in self dot vertices,   we're going to add, we're going to  call self dot add vertex, that value,   we're just going to create  a new vertex for that value.   And then of course, return it afterwards. And the  most powerful part of this Markov chain is that   when you're at a node, you can say, Okay, get next  word, but based on these weight mappings, here,   we can create a function called get next word,  and pass in the current vertex. And what it's   going to do, it's going to first find whatever  vertex object corresponds to that current vertex.   So we can say self dot vertices, and  then the current vertex dot value.   And now let's create a function called Next  word, under this first text object. And what   we're going to do is we're going to randomly  select a Next word, but based on weights.   Alright, so if we actually go to look at the  random documentation, we see that there is this   function called random dot choices where  you pass in a list, give it some weights,   and it will actually choose randomly, but based on  the weights, so we're going to use that idea here.   Let's return random dot choices and pass in self.  Okay, but then how do we know what do we even pass   in? Right? Let's introduce this concept of  a probability map, we're going to map each   word to its probability, but put them in separate  lists. Alright, in this function for each vertex,   comma weight, and self dot adjacent dot  items, remember that self dot adjacent   is a dictionary that has each vertex and  then maps it to the corresponding weight.   Let's create two new lists to keep track of  the neighbors, and then the neighbor weights.   And so here, for every single vertex,  comma weight, what we're going to do is   we're going to append the vertex to self dot  neighbors. But we're gonna append the weight   to self dot neighbor weights. And so then we  can easily pass these into random dot choices.   So here, we can do random dot choices, self  dot neighbors, self dot neighbor weights.   All right, we actually see that random dot choices  returns a list. So we'll have to index and get   you know, there's it's a list of size one, but  we still have to get the first item in the list.   So we have to index zero. Now we can get our  next word. But where are we generating these   probability maps. Under graph, we can create a  function called generate probability mappings.   That'll get all the probability mappings of  every single vertex. Here, we're going to say,   for every vertex in self dot vertices dot values.  Well, what we're going to do is we're going to   call that vertex and we're going to say, Hey,  get the probability map. And so then as soon   as we call that function, every single vertex  will be initialized with the probability map.   And that is our graph representation. So now let's  move over to compose that pie. Let's think about   what we actually need to do here. Well, we need to  get the words from the text right and we need to   create a graph where the values of the vertices in  that Graph are those words. And then for X number   of words that's defined by the user, we need to  get the next word. And then we'll just show those   results to the user. So let's put all of these  inside a main function. Let's start with step one,   getting the word from the text, we can create a  function called get word from text, very original,   and pass in the path to whatever text that we're  trying to get the words from, we can use this   command with open text path, comm R. R stands for  read as F. Well, we can read everything in that   text, if we call F dot read and assign that to a  variable text. So this is going to be a string.   And now what we want to do is we kind of  want to split across all the whitespace   and then join it with one single whitespace.  So what this is going to do is like,   if there's like multiple lines, like, you  know, indents, whatever, it just creates, like,   it gets rid of all those and  replaces it with the single space.   So text, that split is going to split all of that,   you know, whitespace, whatever it is, tabs,  spaces, enters and replace it with a space.   So for example, text that looks like this would  become text that looks like this with only spaces.   Right? And then what we're going to do  is we're going to lowercase everything,   because it's easier to compare everything  when it's lowercase. And then now,   let's not try to deal with punctuation because  stuff can get a little bit complex, right?   There are cases where you might want to add  a period, but it's not actually the end of   the sentence might be an abbreviation. Like, for  example, Mr. Brightside, but Mr is not actually   the end of the sentence. So what we're going to  do here is we're just going to remove all the   punctuation. And we can do that by calling string  dot make trans that's make translation string,   we can import string, that's the Python package,  string dot punctuation is just going to be you   know, any of the punctuation that you can see in a  string. And what we're going to do is replace that   with empty strings. So here's something like,  Hello, it's me might become Hello, it's me.   And then, of course, we want to split all  the words. And we're going to do that by just   splitting on spaces again. So we can call text dot  split, then we're just going to return the list of   words. So return words. So under step one, we can  say words equals, get words from text, and then   pass in the path to for example, let's use Harry  Potter. So text slash HP Sorcerer's Stone, that's   the name of the text file dot txt. That's step one  right there. Now the next thing we want to do is   make a graph using those words. So let's define  a function, make graph and pass in the words.   Here, we have to import the graph and  the vertex from this graph.pi file.   So up here from graph, import graph, comma vertex,  and then G, let's assign this to a new graph.   And for each word, in words, we're going to check  that the word is in the graph. And if it's not,   then we add it. And so when we're going through  this word list, if we come across a new word,   then we want to check the previous word, if it  exists, which it should unless you're like the   very first word in the full paragraph. So if  there was a previous word, then we add an edge   if it didn't already exist in the graph.  Otherwise, we increment the weight of the   existing edge by one. And then we set our  word to the previous word, and we iterate.   So now remember that like, in order to get  the next word, we have to set the probability   mappings. And so this is a great place to do  it right before we return the graph object   in our make graph function. So let's start  in this implementation. For word in words,   we're going to check that the word is in the  graph. And if not, then we're going to add it.   So let's drag graph.pi over here, so  we can look at both simultaneously.   Okay, so you'll see that in get vertex, we  actually add the vertex already. So all we   need to do is we can say word vertex equals graph  dot get vertex and then that word, if there was a   previous word, then we add an edge if it doesn't  exist in the graph, otherwise, increment the   weight by one. So here let's actually create  a previous word variable and assign it to non   because at the very beginning, there is a previous  word. Here we're going to check the previous word   then previous word dot increment edge, word.  vertex, right, because what this is going to do,   it's going to increment that edge between  the previous word and the word vertex by one.   And here the increment edge already does  that for you. Because we've implemented   that in our vertex already. Now here, all  we have to do a set previous word equal to   whatever this word is. So that in our next  iteration, we have access to the previous word.   And we keep doing that for all words. And at the  very end, we can say g dot generate probability   mappings generate all the probability mappings  and then return that graph. Alright, so step two,   G equals make graph. And then we pass in the  words that we got from get words from text.   Now step three, we want to get the next word  for X number of words as defined by the user.   Let's create a function compose, given a  graph and given the words and some length,   let's just say 50. For now, we're going to  create a composition. And this is at first   going to be an empty list every single time that  we generate a new word, we're just going to put   it into this list composition. And what we can  say is that we'll look we have the words list,   let's just get some random word from this words  list. And, you know, grab that vertex from G. And   this is where we're starting. So for however  many iterations in the length that the user   has defined, we're just going to iterate and  we're going to keep getting the next word right   here, we can say composition dot append, and  then this word, which is the word vertex,   we're going to append the value of that vertex,  because remember, we can't actually append   the vertex and have that legible, we have to  append what word that vertex corresponds to.   And then now our next word is going to be g  dot get next word, given the current word.   So here, we can say word  equals g dot get next word,   and word. And what we're going to do is replace  this word variable and keep getting the next one.   At the very end, we're just  going to return our composition.   Right. Now down here in our main function,  again, we can say our composition equals compose,   we can pass in G, we can pass in words. And  then we can pass in some parameter length   override that we can say 100. for the heck  of it, we don't want to just return a list,   let's actually return a string. So we can join  this list of words by a space. And so this is   going to return a string where all the words  and composition are just separated by a space.   So now let's run this function and generate.   Okay, and because we're returning this  competition, we're not printing it.   Let's print whatever Maine returns. And  that's how we're going to see our composition.   Alrighty, so first, we can try running. And look  at that random is not defined. I forgot to define   that. So I go back up here, and I'm going to  import random. Save that and run it again.   Alright, so now, none type has no attribute  value. So this means that this word, dot value,   word is somehow none. So how in the world do we  fix that? To let's go back into our graph code.   And take a look at what's going on. It could  be g doc at vertex or G dot get next word,   one of those is probably returning  none. So let's open graph.pi.   And if we look at, get next word, okay, here,  we're calling Next word, but Oh, look, we're   never actually returning a value. And so that's  our bug. Let's add a return statement there.   And let's try running this again. And there we  go. It worked. Let's read this. This is built   off of our Harry Potter text. Do you are  some interesting so unfair that strangers?   They were going to let her to squeeze  him? I want to look at it had one who   has always Maroon tailcoats orange eyes away.  Just hope of his last look back to her. Anyone   else is very well, no answer. Professor Clairol  had been a bundle of white a Clearfield Harry Ron.   Alright, so this is kind of cool. But clearly  this, you know, it's some gibberish. And the   reason for that is just because our implementation  of simply a Markov chain is not very intelligent,   right? We're kind of just randomly choosing given  this word Pick a next word. One way that we could   make it better and more slightly like English,  is instead of saying like, hate this word,   maybe choose like the previous like three words,  right and then pick the next word based off of the   previous three words, and so on just so that it  has some sort of memory, so it doesn't jump around   as much. But now, maybe you're interested in Can  we do this with the songs that I have in here,   and I'm going to show you exactly how to  implement that. We can edit a couple of things,   but keep most of the logic the same. If we go  into like one, I'm Billy Eilish song, for example,   you'll see that we have this like chorus verse  thing in brackets. And that's obviously not like   part of the song. So we're going to remove like  the bracket and the text inside of it. We can   do that with a regex again. So what we're going  to do is we're going to say, hey, substitute,   and then this funky expression, which I'm going  to explain just a bit, but substitute that with   a space anywhere in the text, it's saying this  is a left bracket, this is a right bracket,   and here, this dot plus, so the dot means any  character, and plus means one or more. So this   means if there's one or more characters inside  the brackets, then replace any version of that   with the space in the text. And so here,  in order to use this, we have to import   our UI. And let's reformat some of this stuff,  okay. And so the rest of this should be the same,   because we still want to get rid of whitespace,  we still want to get rid of punctuation.   But instead of just, you know, one file name,  we actually have multiple, right in this folder.   And one way that we can like just have Python  read that folder, rather than having to type out   every single file name. If we import LS, and we  go down here, we can actually walk through this   folder and find all the file names within  that folder. So let's do that right here.   Okay, so for song file, in here, we're going to  use Oh s dot list, Dir. So that's list directory,   songs, and then we're gonna pass in an artist  name. Okay, so here, we're gonna use f string,   passing the artist. And then in Maine,  we're gonna pass in the artist. So what   this is going to do is, if you pass in this artist  name to align with that file name, for example,   Billy underscore Eilish, then, we're going to  list every single file that's under that folder.   And here, you know, for Green Day, you have  all these for Linkin Park, you have all these,   and so on. Alright, so after I get all the song  files, I can now call get word from text and pass   in this path songs, dash artists dash,  and then whatever the song file is.   So here, I'm going to put that in here song file.   So this is just going to get every single  song file and like, go through and get the   words from that. And up here, I'm going  to define words equals an empty list.   And then every single time we get a song's  words, we're just going to add that to the words   list. So we can extend by whatever  song words is. And so now down here,   we want to input the artist. So let's  input Taylor Swift. Let's try running this.   Okay, so we're getting an error. And usually I  would just Google this error. Honestly, this isn't   one that I'm super familiar with. Let's actually  print what the song files are. So we can figure   out which one it failed at. And so here, if we run  this, we actually see that it failed at this file   called dot d s store. And so this is just some  cash that's stored under this directory. It's not   actually a song file itself. And so we can just  say, like, if this equals dot d s store, then   continue because we're just going to keep going  the loop. And so if we run composer.pi again,   look, there's our Taylor Swift masterpiece.  I remember thinking, are we in red, because   they're you breathless, huh? Or it's time you need  to calm down. You're sorry for it used to hit you,   again, even if it's such a chance to paper  airplanes flying flying, and I've never   looked back together, who, etc. Again, this  is kind of gibberish. We could make it more   intelligent. But for now, as a beginner project,  this is pretty cool. you're generating paragraphs   based off of some vocabulary that you're  inputting through songs. or Harry Potter, etc.   If you enjoy this video be sure to subscribe to  my channel follow me on instagram and twitter   at Kylie y Yang if you guys are interested in  live coding sessions, where you know they're not   pre planned like these tutorials, you should  definitely follow me on Twitch. Kylie Yang.   Alright, hope to see you guys around. I hope you  guys enjoyed my videos. And yeah see you later

Channel: freeCodeCamp.org

Views: 1,177,863

Rating: 4.950448 out of 5

Keywords:

Id: 8ext9G7xspg

Length: 180min 29sec (10829 seconds)

Published: Wed Dec 09 2020