Subtitles prepared by human
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
Watch, read, educate! © 2021