[ Silence ] >> Alright everybody, welcome to the walkthrough for Pset 4 or sudoku which is a very, very fun Pset. On case interview, we're wondering if the musical is beforehand. If you recognized it, then you are as nerdy as I am because that was in fact Dubstep remixes of video game songs. So yeah, awesome! So today I will first be going over the distribution code which a lot--there's a lot of it so I'm hoping not to overwhelm you. And then each of the things you have to do a sudoku, so how to move the cursor around, how to input numbers, blanks, make sure the users are allowed to do that and then checking if the board has been won. So just a reminder, it mentions this in the Pset spec. But if you're used to using gedit and the little terminal window below gedit to run and compile your programs you probably don't wanna do that with sudoku just because the board takes up more pixels than that little terminal window is gonna allow, unless you stretch it up so high you're editing one line of code at a time which is good for procrastination but it's not that productive. So just a recap of the basic rules of sudoku, you wanna have one number in every single square on the board. So it's 9 by 9, there are 81 squares, so in every row there needs to be one of each number, so the numbers 1 through 9, no duplicates, same thing for every column. And then this 9 by 9 board is divided into nine 3 by 3 squares and you wanna have one of those numbers in each of those 3 by 3 squares. So let's just go through the distribution code, so there is a lot like 600 lines-ish but that's not so scary 'cause we'll go through all of it right now. So it's not scary I promise. So first inside of Main, it does things that, you know, you're used to Main doing for you kind of what happened in 15.C. We just did some things like [inaudible] the board, doing some error checking. And then it's also gonna have this Main game loop where it's gonna be asking you for some input and you're gonna respond to that input. So you don't have to worry about any of those things. There's also a new construction in C that we're seeing in this Pset. It's called the case switch statement. So a lot of times in C you'll see something like this. If, you know, this something--this letter is an A then do something, if it's a B then do something else, if it's a C then do something else. And this can get kind of annoying to type, it's kind of more words than it needs to be. So kind of an easier reading compressed way of writing this is a case switch statement. So your first block here switch and then some variable. And this is the variable that was being used in every single one of these if else if, so it' kind of redundant to have to keep typing that variable. So now you're gonna say, if C is the letter A, so in the case, that is an A then there is a colon there and then you could have all of your statements. You can have if statements in there, printfs whatever you want. And then once you're done, you're gonna say break. So that keyword is also used to do something like break out of a while loop or a for loop. In the case switch statement, it's the same word and that means that this is the end of the case A and now we can move on to the case that it's a B and do something else and break and then so on and so forth. So one thing to note is that everything after these cases has to be integers, so you notice that I have chars here, chars they're just integers, right? Because they're just gonna be immediately converted to their ASCII value which is an integer, so I can't do something like a string here. Only numbers but that's so common in C that we decided to introduce a new construction for it. So questions on case switch? Yup? >> You know how you had it set to C equals A and you have an operation like a C is less than A or greater than A or something like that? >> So, in the case switch segment, you can only do equality. So with the, if and else if you can do things like an and or and less than and all that but case switch statement is so simple that it's really just equality. Believe it or not this is pretty common thing that you're gonna need to do in C, yup? >> Can you have more than one line of code in these cases? >> So can you have more than one line of code in each of these cases? Yes. It's only gonna stop as soon as you hit that break. So this do something could be a hundred lines of code, you probably don't want it to be 'cause that's not the best design in the world but you can keep going until this break statement. We'll take a look at how we use case switch in Main already, yup? >> How do you--how do you handle the else cases? >> So how do you handle the else cases? So we'll take a look at that later, but there's basically a special case that says if none of these are true. So that's effectively our umbrella else. Another question over here? Yup? >> Are there curly braces for each case or will it [inaudible]? >> So that's a good question, are there curly braces for each case? So there are curly braces around the switch and this is definitely not like what we've seen in C before. So instead of curly braces you're gonna have this colon after the case and then you're kind of end curly brace is the break statement. So everything between a colon and a break is what you're gonna do in each of the cases. But the switch itself is enclosed in curly braces. So definite a little bit unlike what we've seen before, but it's a little bit easier to read and shorter to type. Other questions? Okay, so also written for you is this global structure. So in our game of 15 we had one global array and that just represented the board. Now in sudoku we could do something like that but we also need to keep track of some other things. In the game of 15, we kind of just had one board, right? If you typed in 15-4, you're always gonna get the same board. In sudoku on the other hand, we have a whole bunch of boards for you. So something like, what board am I on, is something you need to keep track of. We also need to keep track of something like, where is my cursor, right? I can move the cursor around the board and it's gonna change X and Y coordinates and I need to be able to keep track of that somewhere. So we could have created a bunch of global variables and just put all those things as a separate variable. But what we consider a better design is to use something called a struct. And a struct is basically a container for a group of variables. So G, this global variable G is a struct. Meaning inside of G, I have a bunch of different variables. Now, unlike arrays in which everything in my array has to be the same type, if I say int A it's gonna have all ints. Inside of a struct, I can have a bunch of different types which I happen to have in this struct. I have a couple of ints, I have an array of ints, maybe a string. So inside of G, there are a few pertinent ones, so Y and X are gonna be the row and the column of the cursor. So, unlike the game of 15 where we just say, "What number do you wanna move?" In sudoku we're gonna allow the user to move their cursor around and then type a number, and then wherever the cursor is, that's where the number is gonna go. So we also have to represent the board somewhere, so just like in the game of 15, our board is a two-dimensional array. So, it's gonna work exactly the same as it did in the game of 15. We also have the top left coordinates of the board, which we'll get into and then the number, just what game will I play in right now? So if your implementation works on every number except 1, you can find out where it's not working on, but hopefully that doesn't happen. So some other pertinent functions, we'll also take a look at detail. This restart game, so this is going to start a new game but restart might be a little bit of a misnomer because it's going to start the game that's based on whatever board is specified in the G dot number. So if I changed that struct, to say I want a different board now, then call restart game, it's not gonna reload the same board but it's gonna load whatever board is specified in that global struct. So we also have these four drawing functions, and these handle drawing different parts of the board. So the borders handles like the plus and the pipes and the minus signs and make it look pretty. The grid logo numbers, they're kind of self explanatory here. So we also have this show cursor function which we'll take a look at and basically what that's gonna do is it's gonna set the position of the cursor to somewhere in the board based on what you set at the cursor location in terms of row and column. You can also show a message to the user with show banner. This is gonna take a string and it's gonna display whatever message you send it. Now if you don't wanna display that message anymore, you could just hide it with hide banner. So let's take a look at this actual distribution code. So, up here, we are first including the sudoku.hfile, so inside of that we don't have any definitions of things, but if we open up sudoku.h, so we just have some defined statements. So--you know, the colors we're using, you might wanna change something like author, hypothetically, and then just down here we're setting up, you know, what colors are gonna be used. So we don't have to keep typing in whatever numbers these actually represent. So now, we're including a bunch of library functions, one of which is this new one called ncurses which we'll take a look at a lot--take a look at in more detail shortly. So now we're doing this super fancy defined statement, you don't have to worry about what the heck all that means. That's in a few weeks. And so now, here is this global struct, so we have the current level, the board's number, and here's that int board. So notice again it's just 9 by 9, it's a fixed size and this is just a two-dimensional array, so a grid of what our board is gonna be. So, let's jump down into Main. So here's all of our prototypes, so incase you need to remember, oh like is there a functions in sudoku that already exists or do I have to write this again? You might just wanna flip up to this prototype sections instead of going through all 600 lines of code. So this is just a handy--every function we've written for you is listed right here. So here we go, so once again, just a lot of our C checking, the user supply the right amount of arguments, whatever, figure out what kind of board they wanted, in this case there are three levels, debug which is a pretty much solve board, [inaudible] which is kind of an easy board to solve, and then Leap [phonetic] which is the hardest board to solve, not the hardest but among the hardest, so again just error checking, don't have to worry about that. So now, what we need to do is, again, just board loading, nothing fancy, so this is if the user says what board they want and down here, well they didn't say what board we want then we're just gonna pick one randomly, yup? >> I have a question about the code that was a few lines up? >> Sure. >> It says ampersand G number ampersand C, I don't understand why--why it's doing that. >> Sure, so what is this sscanf thing? So this is something that were actually used in GetInt or GetString. We're using this sscanf function and what this does is gonna say "I wanna take some string". In this case the string I'm looking at is rgv2. Now I wanna look for a number and a character and I'm gonna save those in G dot number and G dot character. So once this scanf is done, those two variables are gonna contain whatever this percent D and percent C turned out to be. So it's kind of the backwards of printf. In printf we said here's a percent D, I want you to substitute what I tell you for percent D. This is kind of the other way around. This is saying "Okay, I have some string and I wanna look for that first match in percent D. I'm gonna save it in G dot number." Same thing for this character so why do we keep looking for this character? Well this is kind of a cool little trick to make sure that it's a number. So if this is a number, then only that percent D is gonna filled. Five anything after it and that's gonna trigger that percent C. Now what sscanf returns is the number of things that were read in. So the only way to make sure that I know that this is a number is for only one of percent D, percent D to be filled--and percent--percent D, present C. So percent D is always gonna be filled first and if only that was red that means I typed in a number and there's nothing after it, like there's no decimal, there's no letter I have to have typed a number. So that s just a fancy way of checking like we do in GetInt to make sure that the user actually typed in a number. And we'll see more of what these ampersand things means this week in lecture and section, so yes, so when in doubt just comment that's literally all we're doing, make sure ends a number nothing else, other questions? Yup? >> What is fprintf? >> So what is fprintf? So this is unlike printf which just automatically prints to the terminal like the standard output it's called, like what the terminal is. This just allows you to print somewhere else. So this is something called standard error. So just instead of print it to the terminal, you're gonna print to some error thing that when we run our automated tests it's gonna look to try to read in standard error and see if this is printed. So this just says, don't print out to the screen, print somewhere else in this case to standard error. So again stuff like, this you don't necessarily need to totally understand in order to write sudoku, just take our word for it that we're kind of loading up the board. So now we're starting up ncurses which is this library we'll take a look at later. And now we're kind of getting to code that makes a little more sense. So we're calling this restart game. So even though a game hasn't been started yet, we're calling restart game because like I said it's gonna load the game based on whatever value is stored inside of G. So notice up here, we're storing that value inside of G dot number so now I come down here to restart game? I'm good to go to load some game because we specified what I want to do. So if this fails then we just kind of wanna shut down and say I--for some reason that failed, I don't really know what you did. And then you wanna draw the game for the first time. So this draw all is basically just gonna take each one of these individual draw functions and call them. So instead of having to type them out every time we have one function that calls some group of functions. So now we're in to something that looks very much like what we had in the game of 15. So just refresh the screen make sure that everything is good to go, we've drawn everything and now we see this new function to get the user's input. So before we're using something like GetInt now we're using this getch or getchar and so we're just asking the user to type in some character, so this is defined in ncurses this graphical library. So this isn't something we wrote for you, it's something someone else wrote for you and still gave to you but all this is gonna do is return a single character that the user typed in. So if I type in A in the keyboard this is gonna return the character, a char, A. So now we just want to capitalize it so if someone is playing sudoku with their caps lock on because they just yelled at someone on the internet, then we can still allow them to play and not have to worry about handling lower case N and then handling an upper case N is being the same thing. So now here's the switch statement, so we're switching over this character. So in every single one of these case statements I'm gonna be comparing it to the CH which is again the character the user just typed in. So in the case that it's an N I'm going to start a new game. So here we're just setting the number, we're saying I want a random new game, make sure it's not too high and we're gonna restart the game based on what that number is. So now this break signifies that I'm done. After I hit an N I don't wanna do anything below this break. So in R you'll notice that it's pretty like the exact same thing except for what line is different or missing. [ Inaudible Remark ] >> Exactly this one that changes G dot number. So if I call restart game G dot number, the board I'm using hasn't changed, I'm just gonna reload the same board. So there is the difference between starting a new game and restarting the same game. I'm just not changing the currently loaded board which is based on this global structure called G. And finally we're using our fancy control macro but you don't need to worry about how that works and whenever the user hits control L, it just forces the screen to be redrawn so this can be helpful if you're debugging or something like that. So now, after we've taken the action, we just want to log the move for the purposes of automated tests and keep going until the user types in a Q. So remember that after all this we're just in a do while loop. So you can take a look at this, if you actually click that brace and scroll down, it will highlight the brace that it matches so I'm inside, so that's the end of my do statement and now here's the condition for it to keep going. So as soon as I type a Q this is not gonna continue to loop and I'm gonna break outside of the code which is down here. So questions on how this loop is going? Basically, continually asking the user for a letter, if that letter is a Q then we're getting out of here, if it's another letter then we're taking action based on these case statements. Yup? [ Inaudible Remark ] >> Right. [ Inaudible Remark ] >> Yes, so restart game, if we look up here into our prototypes we have bool restart game. So this function's gonna return a Boolean. It's either gonna be true or false. So in the case that there is some error restarting the game, like you deleted that bin file because you wanted to see what would happen, then this is going to return false and in the case that it returns false we just wanna send some error message to the user saying, you know, something went wrong. So when we say this if not restart game we're still calling this function. So everything inside of this function is going to get executed and then we're looking at its return value. It's a little less explicit 'cause you're used to seeing maybe like bool X equals restart game and then looking at X but this is just kind of a way of shortcutting that. We're gonna look at whatever this returned and then if it's true or false take action accordingly. Okay, back down here so now once the user types Q we're just gonna clear the screen and say thanks for playing, so questions on main? Okay, so just as a word of warning, you are gonna have to kind of modify main or some of the other functions we've written for you. There's no--unlike 15 where we gave you like--just write your code for in it right here and it's gonna work, we promise. You do kind of have to modify functions like main in order to add the functionality that we're asking you to add. So now we're getting into the drawing functions and let's take a look at the ncurses library before we try to wrap our heads around those. So before we do so because GDB is awesome we want you to be able to use GDB for this Pset but as soon as you fire up sudoku you'll notice it kind of takes over the entire screen. So let's just walk through really quickly how we can still use GDB with our program. So if we have our plans and we open up a terminal window and so notice that I'm using the full terminal not the little one inside of gedit, so if I see the int of my Pset 4, there's my sudoku, now I can run sudoku debug 1. So you notice this kind of took up the whole screen. There is no word GDB can kind of go. So I loaded this debug board, you notice there's only one space that's not solved because we have a single dot. So now let's say I wanna use GDB. What I can do is up in the terminal, go up here to File and Open Tab. And so just like Firefox's tab or Chrome, your terminal can have tabs so you don't have to open up a new window. Now over on this tab, I wanna find out where sudoku is running so to do that I'm gonna type in P-I-D of and then the name of my program, so sudoku. So this says there is some process running on my system. If you use Windows and you ever hit Control Alt Delete you can see that long list of processes. So each of one those processes has a unique ID. So in this case, I'm running some process called sudoku because I just typed in dot slash sudoku. So I wanna get the number that identifies that process. So in this case its 2220 so as long as sudoku is running, this number is not going to change. So instead of starting up a new sudoku, we wanna tell GDB, "Actually I just want you to attach to that already running process." So to do that, we're gonna say, GDB then sudoku and now we're gonna specify that process that we just got back from pidof so 2220, hit Enter and now we get some random text, don't worry about that. So now let's set a breakpoint. So we're gonna say "Break on restart game". So this says as soon as I hit the function restart game, I want you to pause so in GDB I can do things like printf variable and step through the code. So I say "break restart game" breakpoint one if you wanna verify that that actually worked we can say "info break" and you see we have one breakpoint it's located at restart game which happens to be defined on line 489. >> And so now when we ran this GDB we actually paused the execution of our existing sudoku program. So if I just type in continue, that means it's gonna be--it's gonna continue to run. So now we're basically sitting inside of our do while loop inside of main and we're waiting for the user to type something. So because I put a breakpoint in restart game let's type in an action that's gonna restart the game, so let's just say N. So you notice over here that my text turned red for a second, which means there's new output in this tab. So if I switch over to here, we can see we're back into our normal GDB state, so I can see the line I'm about to execute, if I wanna see the source code around that I can say "list" and here is exactly where I am inside of the running sudoku program in the other tab. So does that make sense to everybody? [ Inaudible Remark ] >So when--why do we say continue? So when I have said GDB, sudoku and then the pid that paused it. So before I can actually do anything I need to say, "Okay, keep going now." So that's the only reason I said continue so we wanna continue until we hit some breakpoint where I said break restart game and that's my breakpoint, other question? Yup? >> So how do you link sudoku to the other tab? >> So how do we link through that other tab? If you remember--so let's just get out of here. So remember we did two things. We first started sudoku, then we came over to this new tab and we said pidof sudoku and this is gonna return the unique number that represents the sudoku program that I'm running. Now when I'm say GDB that number, that process ID 2220 that's gonna say "Don't run sudoku again" but there's an already running sudoku and it's located at 2220. So I want you to go and debug that rather than starting a new one. So now we're attached to this other tab, other questions? Okay, so really quickly, whoa. [ Pause ] >> So the problem set mentions, you know, just using GDB like that but there's an actual really cool feature of GDB that allows you to browse the source code as you're running it. So this is the TUI or Text User Interface. This is just a much cooler way of using GDB that David didn't tell you about. So now that you're all glad you came to the walkthrough I can say, GDB sudoku 2220 and add in this -tui for text user interface. Now when I hit Enter, oh-ho, oh ho ho, we have this new output so again it tells us to hit Enter and we do, all right. So now let's just say the same thing we said before so we can say, break restart game. We have our breakpoint just like we did before and now let's continue. So now again we're continuing, we're waiting for the user to do something. So we come back over to this other tab, we're gonna try to trigger that restart game so I'm gonna hit "N" there is my red, oh yeah that's cool. So now we can see exactly where we are in the code above our GDB prompt. So if I do something like next you can see up here that I'm stepping through everything. So now let's say I wanna go into draw numbers if I say "step" now I'm inside of this draw numbers program and this is this sodoku.c that you're working with. Now if I type next just keep going I'll put a couple of numbers you come over to this other tabs you can actually see we're drawing the numbers step by step. Yup? >> So what's the difference between continue and next just next just one by one? >> So what's the difference between continue and next? So that's a good question. So continue is going to keep the program going until you hit another breakpoint. So if I had another breakpoint somewhere else or even it came back to restart game and I said continue, it's only gonna stop at a breakpoint. If I just say next, it's only gonna go one line at a time. So notice here actually even though I just hit next I can keep hitting Enter and effectively going to next, well if you don't type anything at the GDB prompt it's gonna do the last thing that you told it to do. You know the short cut if you don't want to type next you can just type "N" it will do the same thing, question? >> Is the breakpoint an error in the code? >> So is a breakpoint in error in the code? So breakpoint is just a little stop sign inside of your code. That says when sudoku is running, once I hit this line I want you to stop because I want to be able to do things like see where I am inside of the source code or print out variables like if I wanna know what the current value of ice I can just say printi and I can know currently that I equals zero. Now let's see, let's find out what J is. So, if we print J. Now J is six and we go back over to sudoku that kind of makes sense. Because, I'm in the first row and I'm in the 0, 1, 2, 3, 4, 5--0, 1, 2, 3, 4, 5 and we're about to print the sixth column. So breakpoint is not necessarily an error, it's just a place where you want to stop. It could be a line number or a function, question? Yeah? >> Is this a classified breakpoint or is that [inaudible]? >> So you do--do you have to specify a breakpoint? So yeah, so if you don't specify any breakpoints and just say run, that's gonna be the equivalent of just running it without GDB 'cause it's not gonna have any place to stop. So until you tell the program when to stop and when to be able to step through the program line by line, it's just gonna run normally. So, if you wanna break on main, you can just say be--create a new breakpoint on main. And so this is gonna say before you go anywhere immediately stop and let me step through line by line, other questions, yup? >> Can you use next without using continue? >> So, can you next without using continue? Sure, I mean if I just say next then I can go to the next line, right, or if I restarted--if I restarted GDB, just said the same thing. I'm gonna break on restart game? 'Cause now when I say continue, okay we're gonna continue until we hit this breakpoint and so at that point I can say next, next, next, next, next and I don't necessarily have to type continue. If that's what you mean. >> I'm sorry I'm still confused why you continue at all, so if you didn't put continue when are you gonna run off to that breakpoint? >> Right. So, when we run GDB and this is kind of a special case, it wasn't--it didn't do this before but because we're doing the special thing where we're attaching to an already running program, when we say, GDB, sudoku and then give the pid it's pausing it. So, until I say continue it's paused. So, once I say continue it's gonna say okay, keep going now and all the breakpoints I've created are now active and they're live and they're gonna stop the code. So, just yeah, so before you do anything in this special two-tap thing just say continue. After you set up all your breakpoints and then you'll be good to go, yup? >> So, do you have to put the breakpoints in your source code? >> So, do you have to put the breakpoints in your source code? So, the breakpoints are defined by GDB so once I quit GDB which I can. As I quit, all of my breakpoints are now gone. Whoa, okay so the G--breakpoint is something that GDB creates as it's running your code. It doesn't actually modify the dot C file itself and there's no way of putting in a breakpoint into the dot C file. But these are kind of thing you create on the fly as you're running GDB. Are there debugging questions, yup? >> Can you put a breakpoint in the dot H file? >> So, can you put a breakpoint in the dot H file? So, generally in the header files there's no executable code. It's just kind of like definitions of things and define statements so none of that is ever gonna really be executed as a line of code. So, typically you're only gonna put them in the dot C files, other questions, yup? >> Breakpoints will they generally always be in main? >> So will breakpoints always be in main? Not necessarily, so when we came over here, we created a breakpoint inside of restart game. So I can also put a breakpoint at an arbitrary line number like instead of maybe I don't wanna break let's go down here to--so let's just come right here. So, let's just say I wanna break out this line. So if I say, break 168 it's gonna break at that line. So this isn't necessarily in main and it's not necessarily at the beginning of a function but I can kind of break wherever I want. If you wanna do something quick and just step through it immediately you don't wanna go to any functions you just say break main, that's just gonna allow you to kind of start of fresh, just, you know, print everything, go line by line you don't have to worry about jumping to functions or anything but you don't to have to say break main, it's just one way of using GDB to pause immediately. If that's what you wanna do, yup? [ Inaudible Remark ] >> Yeah, so the difference between next and step. So let's go back into restart game. And, again I'm gonna say continue because I paused it, come back over here restart the game with N and now we're here. So, if I say step then I'm going to jump into the function load board. So if I say right here step, I'm now inside the function load board. So now, if I say name so S printf this is just a function. If I say step, I'm suddenly gonna be inside of S printf. But for our purposes that's not very helpful, so if I say next instead we're gonna kind of jump over that function and execute it all at once. >> So, step says I wanna go into the function and execute that function line by line. Next says that function is just one line execute it and be done with it. Are there last GDB questions? [ Inaudible Remark ] >> So if you're inside of a do while loop when you wanna kind of get out of it so that's where continue comes in handy. So, if you have this really long while loop and you just wanna pause maybe at the beginning instead of hitting next, next, next, next, you can just say create a breakpoint at the beginning of that loop and say continue. And then, you can jump right back to the start of that while loop if that's where your breakpoint is. All right so let get out of GDB with Q say yes, and that's it for GDB. All right, so now let's take a look at ncurses. So, this is the graphical user interphase library. So, we're not quite at the level of web pages with buttons or actual programs that you would run like Microsoft word but this is a lot nicer than the game of 15. So, what basically the advantage of ncurses is that we can print to anywhere on the terminal. So, in the game of 15 when we had that function draw, we need to draw the board one row at a time. Once you're finished printing a row, we better hope you printed it right 'cause there's no going back. We already printed it. With ncurses you can say I want an X at the 10th row and the 70th column and it's just going to put it there. So ncurses, it's operating on row--a row column basis which I kind of like, but I guess David doesn't based on the Pset. We're--maybe we're used to working XY so just remember ncurses always row, column. So, a couple of good functions in ncurses, one is the move function, this is gonna take the cursor and put it to wherever you want on the terminals. So the first argument is the row second argument is the column. Now, if you wanna write something to the screen you're gonna use this move add stir, move add [inaudible]. This is gonna say I want the cursor to go to some location on the screen again my row and my column or my Y and my X and I want you print a single character or a single string. So, if I say move to you know zero, zero and then I wanna print--print like the letter A then I could say move add stir, zero, zero A says "I want this character in this place on the screen." No longer do I need to printf things in order. So, this other function we're getting input we saw earlier because getch or this getch is a way of getting a character from the user. So, when they type in numbers on the screen, it's going to get the char representation of those numbers. So, a one is not going to be a one. It's going to be a one in those singe quotes. So, ncurses also build in some constants for characters that otherwise don't have like a letter representation like the arrow keys. So this key underscore up and the same with down left and right are defined constants inside of ncurses. And this says whenever the user types an arrow key it's the same as them typing one of these numbers. So when you say getch you can actually determine if they pressed an arrow key which you can't really do if you we're just using something like GetIint. And so finally, this control L not defined by ncurses but something we wrote ourselves. So, questions on how we're getting input from the user or how to use these, yup? [ Inaudible Remark ] >> So, if I type--so what happens if I want a number and I use getch. So, this is going to take in the character representation of the number. So, remember that nine is different than "9". So, if I type in a nine into getch, it's gonna give me back the character nine, so character in this case not meaning letter but being the char data type in C which represents a single symbol on the computer. Does that make sense? Okay. Other questions? [ Inaudible Remark ] >> So, the single quotes you remember, is how we define a char, and C, or a char. I don't even know how to pronounce it but just a single character whether that be a letter or a number. So this translates to the ASCII values between zero and 127 and just making sure we cave in these quotes distinguishes the ASCII value one which is some non-printable character and the character one which is the printable one. So this is just like in Pset 2 when you had to deal with converting an A to some number or some number to it's actual ASCII number. Other questions, yup? [ Inaudible Remark ] >> So, inside of sudoku if you--we go back to what it looks like? When we run it, when we hit the arrow keys we wanna be able to move this letter green guy around. So we need to detect if the user typed in a left, or an up, or down, and the way we do that is we just compare it to these defined constants. So, if I call getch and the user types in an arrow key. It's gonna return this constant key up or key down left or right. So, we can just--we don't even have to worry about what these numbers are--what these constants actually represent. We can just say if the character is the key up then I wanna do something, so comparing it to these instead of comparing it to some number or character. Okay, so now we've covered the distribution code and the library we've been using so here is our to-do list for this Pset. You wanna be able to move the cursor around once we have the user be able to move their cursor we wanna allow them to input some number. After they input the number we wanna be able to tell them if it's definitely wrong or some illegal move in Sudoku. Then, once we have that working we want to allow the user to erase their number. So make sure that if they made a mistake and they wanna get rid of their choice they can do that. And finally, check if the board is one and once the board is one, stop the user from playing anymore. So, remember this function show cursor is going to move the cursor based on the--based on the values of g.y and g.x. So, all the show cursor function does is it calls this ncurses move function which is pretty complicated when you actually look at all the math we're doing. But all you need to worry about is changing the Y and the X inside of this global struct because as soon as I call show cursor it's going to read those values that you changed and set the cursor according to those values. So you don't have worry about calling the move function itself. When I actually wrote this Pset I didn't figure this out and so I had all this crazy ncurses code which is terrible. So, instead of trying to worry about that, you just need to change the values inside of this global variable and call show cursor. That's gonna read those values and put the cursor back. So now, when you look at this board it's a little confusing what we mean when we say, you know, X and Y is 4. So, inside of our board we just have nine rows across and nine columns down. So zero, zero is not this plus sign or it's not the top of the terminal window. It's just the first number in the grid. So this at the end here is board 2A, row 2 column 8, I mean there's not that many characters in the row because we have spaces, we have pipes, and all that kind of thing. But as far as your board representation is concerned those don't exist. We only care about what numbers are in each of the spaces, yup? >> So, are the corners, the pipes and all that stuff is sort of outside of the array? >> Yes, so are these corners and pipes and stuff, so the array doesn't even know they exist. So these are gonna be drawn in one of those different draw functions that we looked at. So, similarly with the cursor if I have it in the middle of the board, I'm in row 4 column 4. Even though I have a bunch of space at the beginning and these minus signs so just keep in that in mind as you're writing your code. Even though we have all these pretty aesthetics as far as those global variables inside the structure are concerned it's just a 9 by 9 grid and there's no fancy aesthetics. So questions based on that? >> So it just shows the cursor in the center of the board to start off with? >> Yes. So yes, so it's starts off in the center of the board, other questions? Okay so--yup? [ Inaudible Remark ] >> So this, so when you just fight--when you do a git clone on Pset 4 and you just fire up sudoku, this is what you get. So, all of these are already done for you. And the way that we're displaying this is with the ncurses library. So, if you flip through all the draw functions, you'll see lots of moves and move ad characters and stuff like that. So, it's just a set of a real--like a lot of functions that someone else wrote for you that allows you to do things like this a lot easier, so that's our board. So, now let's take a look at how we would move it. So in order to move the cursor, all we need to do is change that Y and X. So, pressing a different arrow is gonna do a different thing, right? We're gonna need to make Y go up or down or make X go up or down. Because we can only move in one direction at a time and don't worry about diagonals and we're only changing one of these at a time. So right now, if we go back to main, you'll notice that it only has a few cases. If we go too far, way too far, so here in main we have the case that you hit an N, the case you hit an R, and the case you hit a Control L. So, here is probably where I wanna put the case in which I had the key up, what do I want to do? So, you probably wanna write some function that says if I hit something that's not already defined I wanna take some action. >> So one thing to keep in mind if we don't want allow the user to move the cursor off the board, so that includes moving, you know, into the edge or moving over to the D in sudoku. And we just wanna make sure that the user stays within this 9 by 9 grid area. So before you just arbitrarily like blindly make X bigger every time you wanna make sure that you're still within the board before you can make X larger. So, questions on how we can go about moving the cursor, yup? >> You can go back one slide [inaudible]? >> So when we move--when we hit some arrow key, we just wanna modify this global struct and change the X and Y and then the next time we call show cursor, the cursor's gonna move because that's what that function does, just reads those values and changes the cursor, yup? >> Do you have to modify the case switch so that if we use your [inaudible] left, right, up or down then the case switch automatically changes? >> Exactly, so we need to modify this case switch in adding some new cases because this, everything inside of this case switch is everything the user can possibly do which right now is NR control L. So, if we wanna allow the user to press some button we just need to add a new case and define what pressing that button does. Other questions on moving the cursor? Okay, so now let's take a look at inputting numbers. So, remember that we need to take the numbers 1 through 9 as input and these are not going to be returned from getch as the number one, it would be returned as the character one, so just remind if our ASCII works. Quotes one is not one, quotes one is instead quote zero, plus one. So you can still do these things like add a character to an integer and it will work fine. But just remember that when the user types one, if you think that's gonna be the integer value one, then your code's gonna be little bit off. So, representing the board is gonna be very similar to what we did in 50. Board is going to be these two dimensional grid and inside of board IJ is gonna be the number at row I column J because ncurses works in YX not in XY. So, you know that the cursor is always at row g.y column g.x. So, if we change the value of the board at IJ it's gonna change the number that's displayed. However, if we just changed it immediately that's not actually gonna change what's displayed on the terminal because that's not changed until we explicitly call one of our draw functions. So those draw functions are just gonna look at what's stored inside of this board and iterate through it and print out whatever is there basically. So again, we don't need to use this ncurses function move add character ourselves we can just change the board and redraw it using some redraw function that was written for us. But keep in mind that as far as efficiency is concerned if I just a type in a number, I probably don't need to change all the plus signs and the minus signs. So just make sure you're using the right draw function but you can kind of look at each of them, they're self-explanatory just make sure you're not redrawing things that you don't need to redraw 'cause that's a little bit of a ding on efficiency. So, one thing we need to keep in mind is we can't allow the user to change the numbers that came with the board. Else I would just saying 1, 2, 3, 4, 5, 6 and I'd win really fast. So, once the game has started we need some way of remembering which numbers were already on the board. So, if I go and try to change a number that was already on the board, your program says nope, can't do that. So just a tip, if I have some array like say it was called a G dot board for some reason and I just tried to set it equal to some other array, that's not going to work. So, you need to figure out a way to effectively copy your original array into some other array that you keep track of somehow and before you change any space, make sure that you're allowed to change it. So, questions on how that would work? Cool. So inside of our case switch statement to make things a little easier you can actually do something like this and combine cases. So, this says in the case of an A, or in the case of a B, or in the case C, I wanna take some action. So instead of saying case A, have some code, copy paste that into case B, copy paste that into case C, we can combine them just like this. So this is effectively A, or B, or C. So as I mentioned before we also have a special case called default and that's going to be the else. The if, none of these cases are true, I still wanna do something. It's gonna jump to this default case automatically. So questions on how I'm combining these cases here? You'll find this to be super helpful. All right, so now just a word about design. As you're designing your code, you wanna try to factor out as much code as possible. And what do I wanna mean by that? So if you find yourself, you know, writing the same three lines of code all over the place which you may, you kind of wanna factor that out into some function that you can reuse so instead of copying and pasting code all over the place which is a very, very nice temptation, what you wanna do is try to design functions that are reusable so I can use this function here and even though this case is a little different I can still use my function here because it takes some argument or something like that. And, also rather than going in and having all of your codes stay in main you probably wanna create your own functions. So in 15, we did that for you. We said here's the function called init, it's probably a good size for a single function put your code there. In this case we're not really holding your hand that much but what we do wanna do is take our changes and kind of consolidate them into separate functions, that from the existing code we can just call that function instead of just adding swats of code to our main or the draw numbers or whatever it is you need to modify. So, questions on inputting a number, yup? >> Can you go over again about the arrays and why we can't use an array? >> So you can't--so you can use an array and you probably want to. But if I want to take array one and make a copy of array 2. So, I have this existing array, array 2 and I wanna copy it into array 1. I can't just say array 1 equals array 2 because this is just a pointer right? So, it's just a reference to some memory address. So, if I do this I just make array 1 and array 2 point to the same memory address I didn't actually copy the values. So, if I change array 1, array 2 is gonna change too because they're just looking at the same location. So you need to explicitly copy your array. Other questions on inputting numbers, yup? >> The user is inputting something that we're thing that that's a char? >> Yes. >> You need to store that into the array with int array? >> Yes. >> So how is that working? >> So we need to convert a char into an int. So, this is very similar to what we did in Pset 2 with our [inaudible], we needed to convert some char into an int. So we're gonna do the same thing here. The user types in a 1, we need to actually store a 1 inside of our board not ASCII value of 1. Other questions, yup? >> Will you use the A-tui [phonetic] function to do that? >> So, would you use the -tui function to do that? So, A-tui takes some string, returns an integer so we're not taking strings, we're taking single characters so we basically need to look at the ASCII table and say, "what value do I need to add or subtract in order to get from quote zero to just the number zero?" Other questions on inputting numbers? Okay, so now for kind of the meat of the problem set. Determining if a move is legal so in this case, after we--and we enter any number, we need to check if that's a legal move. And if it's not a legal move we wanna use this show better function and say this is wrong. So, just--to avoid some confusion if I type in a wrong move and I show the banner it's wrong and then I type in a right move, my banner is gone. And a few set makes this very explicit, it doesn't need to persist. But every time there is an illegal move, so the banner and it just on it's like consider move by move. You don't need to look at it if there's still an illegal move on the board. Just if it's a legal move show the banner if it's not a legal move, don't show the banner. So here are the three rules again to make sure the move to be legal. The number doesn't already exist in the same row, the number doesn't already exist in the same column, and the number doesn't already exist in the same 3 by 3 block. So we need to check each of these cases. There might be a temptation to get a little fancy here. My advice is you don't because there a lot of things that you're like, "Oh this probably works, right?" And it probably doesn't unfortunately. There are very few fancy ways of doing this so I'd advice you to actually check each of these cases exclusively. There isn't some mysterious design thing that you should be picking up on. You need to check all these cases. So let's take a look at the row and the column case. So we know that a user just inputted a number into G dot board, g.y, g.x 'cause that the row and the column of a cursor. So whenever we make a change, that's where the change just happened. So in order to check everything in the same row and everything in the same column, we just need to have some iterator over the row and over the column. So, we need to check if we just inputted something into zero, zero, we need to check 0, 0, 0, 1, 0, 2, 0, 3, 0, 4 and similarly in the other direction. So if the number is already found we know the move is illegal. So questions on what I mean by legality here? So just if it's already in the row or it's already in the column and we know the row in the column that these are inputted then we know it's an illegal move and we need to show the banner. >> So, here's what I mean by that. So if I just inputted this dot, here is my row everything in row zero and the column is going from zero to 8 and inside of my column, that second part of my array stays the same and my rows are going again from zero to 8. Does that make sense? So, a harder one is the 3 by 3 block. So notice that the board is divided into these contiguous 3 by 3 blocks so there are 9 of them. So, if I input something onto this first block I only need to check this first block. I don't need to come down here, if I inputted something on the top left corner. So, the way that we're gonna check that block, is we need to figure out where that blocks starts. So let's say that I--we just know that let's say I inputted something in the middle. I can't just go 3 columns over, 3 rows down because then we'd be kind of combining blocks here. So, even though it's a 3 by 3 block it is not one of the 3 by 3 blocks. So in order to do that, we need to determine where each of the 3 by 3 block starts which sounds like a job for division very similar to what we did in Pset 1 with making change. So, after we determine the top left of the block then at that point we can just go 3 columns over, 3 rows down, and just look for that numbers. So we need to actually iterate through that 3 by 3 block and look at 9 numbers and look if there's something that's already inputted. So, questions on how we can do that, yup? [ Inaudible Remark ] >> Yeah. >> What did you mean by that? >> So just--let's say that I inputted, let's say that this board was totally blank, or there are just a few numbers and I make a move. And that could be at that point, it could be a legal move. But it could be the wrong move like I later find out that, that 6, was supposed to be a 5 but at the time 6 was still legal. So you're not checking if it's wrong, you're only checking if it's illegal or comp, you know, obviously wrong. So just a subtle distinction there that because in order to check if something's wrong, you actually need to solve the board which is the hacker Pset, so unless you wanna trick yourself into doing a hacker Pset, just remember what that means, yup? [ Inaudible Remark ] >> So, inside of--so G is our global structure so the structure has a container for multiple variables so one of those variables is board, just a two dimensional array and two other integers, separate integers Y and X. And, g.y is always the position of the cursor, that row of the cursor and g.x is always the column of the cursor. So, after you implement moving the cursor, you're gonna make--you wanna make sure that those values always contain where the cursor is. And so now, that's how I can figure out what value the user just changed or value I need to change on the board, yup? >> So, every time the user moves a cursor we think that they're actually inputting a number? >> So not necessarily. So the user can--moving the cursor is different than inputting a number. When I move the cursor I wanna change this g.y and this g.x. When I input a number I don't wanna change where the cursor is, I instead wanna change the board based on where the cursor currently is. So depending on if they entered in a number or hit an arrow key we wanna do two different things, both modifying the struct but modifying different parts of the struct. Other questions? Okay. So, that's move legality so we also wanna allow the user to remove their number especially if you're as bad as sudoku as I am. So, the problem said specs, problem said specs says, we wanna be able to delete the number if we hit the backspace, the delete key, the dot, or the zero. So, again ncurses comes in with these fancy constants. Key backspace, Key DC for delete dot or the number zero so it just as a note as your--right in your palm set, and you notice that "Oh, my key DC doesn't work", or something like that. Don't worry about it it's just your computer and cursors isn't ready for your computer yet. The Pset mentions this in a footnote but if you just--just make sure you look at all four of these cases in order for deleting a number and don't worry if something like Key DC doesn't work. Zero and period should definitely work though. And so you notice you probably wanna do the same thing based on multiple cases again. Unlike we saw before, we can combine these cases and only take one action instead of saying case key backspace, copy paste, case key DC, copy paste and stuff like that. So inside of draw numbers you'll notice that a blank is represented by a zero, so when we delete a key all we need to do is set the board not equal to whatever the user typed but a zero. So, questions on blanks? So again, just remember we can't delete numbers that we came with--that came with the board. Now, remember I said factoring a common code, this is something you need to do in two cases, the user inputs a number and then makes sure that I'm allowed to change it. User inputs a blank. I didn't make sure I'm allowed to change it. So writing a reusable function here is gonna make our code much better designed. We're doing the same thing in two pretty different moves, deleting a number and adding a number? We still need to do the same thing so we can call the same function. So just a couple of lot of other questions, is inputting a blank always legal, is it necessary check for legality, and can I do need to check as the game as one if I just removed the number. So things like that, okay you think about efficiency. I'll leave the answers to those to you. So that's how we need to input a blank. So any questions on what we need to do there? >> It's always the last one? [ Inaudible Remark ] >> Right. So just--this thing about efficiency like do I need to necessarily check things? If I just removed a number do I need to necessarily check if the game is one now? Just things like that to make your code a little bit more efficient. [ Inaudible Remark ] >> Well no, what I'm saying is let's say that as a user, I just typed in a blank. >> Yeah. >> As the program, did the user--it did--by inputting a blank. Did the user just win? Definitely not because the board needs to be filled, so just little efficiency things like that like if I just--if I just deleted the number, I definitely didn't win. But if I just input a number, I might have just input the last number. And when I'm inputting a blank, I definitely didn't just--that was at my last move. So just things little efficiency things like that, not necessary to correctness but they might be handy for design. Other questions? So finally, we wanna check to see if the game is won. And in this case, you wanna freeze the game and don't allow the user to make anymore moves except for starting a new game--quitting. So the game is won under these four conditions: if every square is filled in and every row contains one of each number, every column contains one of each number and every three by three block contains one of each number. So, every time the user makes a move, it's then time to check if the game is won. So, when you're thinking about how you're gonna implement this and efficiency, you only need to look at every row and column once. There's no need to look at the same column twice if you've already verified that that column is okay. So there are couple ways you could do this. You could check to see if you found every number. You now, have something like in array of numbers, zero through nine. And every time I--yeah, zero through nine or one--zero through eight or one through nine, depend on how you set it up and just say, "Okay. I found a one, that's a check mark. I found the two, check that off." Then once you've gone through the column, see if you've check off every number or you could do something like see how many times you see each number. And if you ever see a number twice then it's definitely not won. So there are bunch of different ways to do this but it all boils down to keeping track of what you've seen in a single row or column and making sure that that's good to go before you move on to the next row or column. So using an array here is probably a good way to approach this. And again, this is where you have the tendency to maybe I can get fancy here, don't. Similarly, we only need to check every three by three square once. So there's no need to keep checking one if you've already looked at that square, so you notice that we we're thinking about move legality, we probably already wrote a function to see if there's about like having a given three by three block is valid. So that's just one way of thinking about designing your code. I'm doing similar things and checking if the move is legal and checking if the board is won. So, design your functions to be reusable. And so, just another efficiency question, you notice we have these four conditions. Do we really need to check the first one if the last three are true? I don't know. So just--lest you forget, reuse as much code as possible. It'll make your Pset much more elegant and better designed. And you'll get more points and we'll be happy. So any questions on checking if the board is won? Yup? >> Should we be checking like every move or should we wait until the whole board is--? >> So should we be checking every move or shall we wait for the whole board to be filled. That's a question for you unfortunately. You know, which--which way do you think is more efficient, or which way is the code more elegant, which way is gonna run more efficiently, you know, determine when your one is checked. Okay, so just to recap, the question was do we need to only check if one after every move for or do we need to--or can we just wait until we know every square is filled in? That's kind of a question for you. Which of those ends up to be more efficient based on your code, is it more efficient to look at every square and then see if it's won or is it more efficient to every time you make a move even if it's the first move, look at every single square. So that's up to you. And as you run your code, you know, you'll probably make a decision, oh this one is way better, I'm gonna do that. Other questions on the Pset as a whole? Yup? >> You said checking every numbers like doing a search and you said don't be fancy. So, when you're looking at efficiency, you wanna see like really efficient searches or--or can you really just be like looking through like [inaudible]? >> So what do I mean by don't get fancy? So I do mean--so I don't mean like trying to binary search the sudoku. That's not what we mean by efficient. But things like I'm gonna multiply every number and see if it equals this. That's like a fancy thing. That's not gonna work, so don't do that. So, just stick to these--stick to those three rules. Let's say you're doing fancy like actually check if every number is there. >> Okay. So efficiency isn't necessary if you like smart researchers or everything and like binary [inaudible]? >> Right. So I mean in this case, we can't really binary search it right? It just doesn't really apply to this problem and so, yes. So based on this problem, the most efficient way we can do this is to actually look at every square. >> Okay. >> Instead of trying to do some like I just discovered this and I made a breakthrough in sudoku algorithm. Just look at every single one. Other questions on the piece that has a whole? Yup? >> You recommend implementing each of these features in the order that you listed them? >> Yes, I do. And in fact that's why I listed them in that order. I do recommend [laughter] implementing them in this order and that should be a numbered list. That's actually my fault. So yes, so, implementing in this order is kind of just a logical way of stepping through it and the functions that you wrote in the beginning steps, you'll probably end up using in the functions you wrote in the later steps. So, reusable code is kind of our goal with this Pset. So just before--you don't--remember that you need to implement one of these additional features which I've listed here and won't read to you 'cause you can read--just make sure you do at least one of these. If you wanna do more than one, go for it. Become your TF's favorite student but last questions on sudoku. Yup? [ Inaudible Remark ] >> Sure. So, when you input a number, so, could we just go like back to how we can reuse code and something like checking or inputting a blank? So, when we inputted number. We need to make sure that the number that we're trying to--the space we're trying to change did not come with the board. Now when we input a blank, we need to make sure that the number we're trying to delete did not come with the board. So if you just have some generic function that said, "Does this--did the space come with the board?" Then you can reuse that in the multiple--multiple parts of the problem that you're trying to solve. So that's what I mean by a reuse code. Write some function once and use it as much as your heart desires. Are there questions on anything sudoku? All right, then that's it for the walkthrough and good luck with Pset 4.