COLTON OGDEN: All right. Good morning, good
afternoon, good evening, depending on where you are in the world. This is CS50 on Twitch. My name is Colton Ogden,
and I’m joined today by? RODRIGO DABOIN SANCHEZ:
Rodrigo Daboin Sanchez. COLTON OGDEN: And Rodrigo has
joined us before on stream– well, he joined us
yesterday– yeah, while we were doing a little bit of Minesweeper. And it’s sort of tangentially
related to today in that today we’re covering a game, right? So what are we talking about today? RODRIGO DABOIN SANCHEZ:
Today’s Game of Fifteen. So if you were here
yesterday, you would have remembered us showing the little visual
of what it looks like when it’s solved. But yeah, we’ll talk about it and– throughout the whole stream. And it’s essentially just what
is a board game in a fiscal form. But we’re doing it terminal based so
just printing out onto the terminal. And you’re just trying to
unshuffle a board of numbers so that it goes from 1 to 15
with an empty slot at the end. And we’ll see what that looks like. COLTON OGDEN: The first time
I think you were on stream, was it for Super Mario Brothers? RODRIGO DABOIN SANCHEZ: Yeah,
I think it was for Mario. So I’ve been on stream
twice just playing games– figured I had to come on it, actually. COLTON OGDEN: There was Zelda, right? You also did Zelda with us? RODRIGO DABOIN SANCHEZ:
I did Zelda as well. COLTON OGDEN: Yeah. We did a couple of streams last
year, towards the holiday season. We ended up doing some
actual, proper Twitch content. Normally, people play games on Twitch. We program games on Twitch often. Why don’t you tell people about
[INAUDIBLE] your experience at Harvard so far– what you’re studying, how
long you’ve been here. RODRIGO DABOIN SANCHEZ: Sure, yeah. I’m a junior right now, about
to start spring semester. And studying computer science– kind of a newbie in the field
because for the longest time, I thought I was going to do math. And then when I was
in my freshman year– actually, the– yeah– no, the beginning of
my sophomore year, I realized I didn’t really like
math as much as I thought I did. And CS, instead, was
kind of related to math while still more entertaining for me. So I switched to that. And I’d had just a couple of
years of experience with CS before that, mostly
with Java, Mathematica. And so I just took CS50 as a freshman. And here I am, two years
later, working for CS50, so– COLTON OGDEN: Awesome. Well, it’s good to have you. You also worked with me
for the games course. RODRIGO DABOIN SANCHEZ: That’s true. COLTON OGDEN: You and I worked together. We taught the games course last– you were in during the
summer version, correct? RODRIGO DABOIN SANCHEZ: Yeah. COLTON OGDEN: Yeah,
not the spring version. Yeah. And that was awesome. Yeah. That was really cool. Some folks in the chat I think are
actually taking the games course online right now. One of the person’s name,
[INAUDIBLE],, and I’m not sure if they’re in the chat at the moment. Let’s look at the chat,
actually– just make sure we’re caught up with everybody. So we have Harvey Neto from Brazil. So hello, Harvey. Good to see you. RODRIGO DABOIN SANCHEZ: Bon dia. COLTON OGDEN: I’m not sure if
Harvey’s been in this chat before. So welcome, if this is your first time. Oh, indeed. Yeah. Now they’re a first time follower
as well as of a few minutes ago. So Harvey, thank you for the follow. And also TaserHD, thank
you for the follow. [INAUDIBLE],, is on, Bella_Kirs,
[INAUDIBLE]—- hello from Germany. Hello, [INAUDIBLE]. Good to have you with us. That’s a new name as well. Edwine21 says hello. That’s a new name. Whipstreak23, Nate, hello. Thank you for joining us today. [INAUDIBLE], hello from Egypt. A lot of new names today. A lot of representation around
the world, which is great. Love it. Andre’s very kindly
giving everybody hello. Bhavik’s not here. Oh, that’s a good point. Bhavik’s not here. That’s unfortunate. Hope he joins. I did realize that we forgot
to post a pub yesterday. We pubbed today. We didn’t pub this one yesterday. So hopefully that’s not the reason why. If so, that’s on me. So I apologize for not doing that. But we’ve mentioned it on
stream before, certainly. And then again– and
in case I do forget, which I won’t, about tomorrow’s. Tomorrow, David’s doing
a stream on Render 50. So tune in for that one for sure. And glad that all of you are here
today that have tuned in right now. Let’s see who else we have. We have Forsunlight. Hello, Forsunlight. Bella_Kirs, Twin Tower Power. Are we going to get to see Rodrigo
bless us with his knowledge today? Why don’t you answer that question. RODRIGO DABOIN SANCHEZ: You know, it’s– knowledge is a funny thing. No. Yeah, yeah. We’ll get to see a little
game that– it’s actually inspired from a previous CS50P set. But it was coded in C. And so I
decided to do it from scratch in Python and implement a solving
algorithm for it. So it’s inspiration from the old, but
some of it is from scratch from me. So we’ll see. COLTON OGDEN: Yeah, we didn’t do– we’ve done Game of Fifteen historically. But within the last couple of years– I’m not sure if it’s the last two years
that we haven’t, or just the last one year. I think it might be the last two years. We’ve switched it out for music and
something else this last semester. RODRIGO DABOIN SANCHEZ: When
I took it as a freshman, that was the last year
that we had it as a pset. COLTON OGDEN: OK. Was that two years ago? Three years ago? RODRIGO DABOIN SANCHEZ: Yeah, 2016. COLTON OGDEN: OK. So the last two years, we
haven’t actually done it. But it’s nice to bring it back. There’s a lot of– you can go into
old versions of the course on YouTube and whatnot and see that that
course– or that problem set existed. Will the stream with David
tomorrow be at the same time? I can tell you right now. No, tomorrow the stream is
going to be at 3:00 with David. So tune in for that one at 3:00 PM. Harvey Neto, hello. Who is from Brazil. Forsunlight, I’ll try to listen only. Everybody say computer science. Martian Mars Boy says yes. And that’s a new name that I haven’t– I don’t think I recognized. We should make a group on
WhatsApp, says Harvey Neto. Everybody’s super enthusiastic. Tuxman29, thanks for joining. And– oh, there’s Bhavik at the bottom. He’s here. He was just a couple of minutes late. Well, I shouldn’t say
a couple minutes late– a couple minutes later
than everybody else. We haven’t actually started
the implementation yet, but glad to see Bhavik
there as a regular. And Tuxman says studying CS
in Montreal because of CS50X. That’s awesome. Cool. I’m going to bring us to the shot
of your computer, which is just, at this moment, an empty terminal. And I’m going to let you
take control at this point and guide us through what
you want to illustrate. So go for it. RODRIGO DABOIN SANCHEZ: All right. Well, let’s just– let’s– for
those who are not familiar– actually, I can do this
from the terminal now. So if I write a bunch of just
random things in the terminal that you haven’t seen before– I like aliases a lot,
and so actually I can– COLTON OGDEN: So GC for Google Chrome? RODRIGO DABOIN SANCHEZ: Yeah. I might have some jobs right now,
so let me just exit out of that. But if I actually open up Atom here,
I have some nice little aliases. So I’m really lazy, and I don’t
like typing things out very long. So for committing to git, I
have gcm instead of having to write git commit, blah, blah, blah. COLTON OGDEN: Oh, I like that. RODRIGO DABOIN SANCHEZ:
So just random things. I don’t have to write the same
thing over and over again, so– COLTON OGDEN: I should
probably do that too. RODRIGO DABOIN SANCHEZ: If I navigate
pretty quickly in the terminal, it’s just because I kind of saved
future me the headache of writing all this stuff unnecessarily. But OK. So here I am. What I was going to do
is show everyone who hasn’t seen Game of
Fifteen what it looks like. COLTON OGDEN: Oh, good idea. That’s a good image on the right. I like that. The 15 puzzle. And some people might
know it as 15 Puzzle. That’s– maybe it’s a more– RODRIGO DABOIN SANCHEZ:
Might be a little bit small. COLTON OGDEN: –popular name. RODRIGO DABOIN SANCHEZ: Yeah, 15 Puzzle. So this is what it looks
like when it’s solved. It’s, like I was alluding
to before, a two by two– like a 2D array type of thing,
where you have 16 empty tiles. And then 15 of them are filled up
with tiles numbered 1 through 15. And so what you’re trying to do in
the physical board game is just– they’re not– they don’t
start off solved like this. They’ll start off in some scrambled way. And you’re trying to move the
tiles down, and to the left, up, and right so that you end
up with this configuration. And we’re going to do
this on the terminal. So that’s about it. COLTON OGDEN: Tuxman says I
was teaching coding to kids, and a phrase that they always use,
coding is the art of being lazy. RODRIGO DABOIN SANCHEZ: Exactly. I always tell everyone,
being lazy is the best feature a programmer can have as long
as they still get their work done. COLTON OGDEN: Yeah, I
kind of agree with that. Rabin Gaire also says hello there. So, hello Rabin– Rabine. Good to have you with us. What were you going to say? RODRIGO DABOIN SANCHEZ:
Yeah, because being lazy makes you look for the most
efficient solution, the one that takes the least amount of work. COLTON OGDEN: There’s that
quote from Bill Gates. It’s like, he’ll always choose
the lazy programmer– or whatever, the lazy worker, because they’ll get the
job done with the least amount of work. RODRIGO DABOIN SANCHEZ: Right COLTON OGDEN: I don’t know if
that’s actually a real quote. I feel like I hear it
all over the place. RODRIGO DABOIN SANCHEZ: So what I’m
doing right now is I am just creating– COLTON OGDEN: So touch,
to be clear, is a– RODRIGO DABOIN SANCHEZ: Right. So right now, I’ve just created two
new files using the touch command. And it just creates
an empty file for you. You give it the name. And so here it is now in my
text editor, which is Atom– which is a different
one than Colton uses. COLTON OGDEN: Right. RODRIGO DABOIN SANCHEZ: I
don’t remember which one– COLTON OGDEN: Yeah. I use VS Code. But they’re very similar. They’re sort of electron based, modern
text editors with a very well supported plug-in system– plug-in ecosystem. VS Code has some built-in debugging
stuff, which is pretty cool. RODRIGO DABOIN SANCHEZ: That’s nice. COLTON OGDEN: V1Rani’s in
the chat saying, hey, guys. Been here yesterday, decided
to stop by today as well. So thanks for popping in again. Glad to have you with us. RODRIGO DABOIN SANCHEZ: For sure. And I know we don’t do a lot of
Python coding on the stream, right? COLTON OGDEN: Not yet at least. RODRIGO DABOIN SANCHEZ: Not yet. COLTON OGDEN: It would
be nice to do more of it. I know that for sure. A lot of people are into Python. I love Python. I don’t use it in the context of game
programming, but yeah, absolutely. I think we should definitely
have more Python stuff. So this is a good step
in that direction. RODRIGO DABOIN SANCHEZ:
And so with Love2D, which is what Colton usually
uses when we’re creating a game, you have the update and the render
and the load and everything. But with Python, you don’t get
that kind of a built-in behavior. You have to implement it yourself. And so in Python, if
you want to do something as simple as printing, hello, world– or just hello, you literally just
write it in whatever file– usually it’s called main. And then if you run it here,
you would write Python 3. But once again, I’m lazy. So I just write py. And that’s how you
execute a Python program. So all of a sudden, we have
our first Python program. And before I jump into the actual
coding itself, what I like to do is build myself a little roadmap. So what I’m going to do is create
another file called plan.txt. And I just like to write out what I need
to implement the program before I just dive into it. That way, it’s kind of like
writing a rough draft of a paper before you– or an essay
before you dive into it. COLTON OGDEN: Yeah, absolutely. I do that too– actually, a lot– when I’m working on a
larger project and like some of the ones you’ve done on stream– like something that’s
maybe more representative of a real world game code base. It’s very easy to get lost in– RODRIGO DABOIN SANCHEZ: Yes. COLTON OGDEN: –figuring out
where you want to go next. So having a– some sort of to-do– I mean, essentially, it’s
the idea of just a to-do– RODRIGO DABOIN SANCHEZ:
It’s a to-do list– COLTON OGDEN: –list, generally. RODRIGO DABOIN SANCHEZ: –basically. COLTON OGDEN: I mean, we
use Asana for work, which is a great tool for to-do list stuff. And it’s that sort of idea– people that can keep track of all
the individual things they do. I feel like it’s easier
to stay on top of stuff. RODRIGO DABOIN SANCHEZ: So I’m
just making a checklist here, things that we need. And if we– oh, I got rid
of the image, didn’t I? If we go back to– COLTON OGDEN: Lancemaker is saying,
dude, I have a huge Excel table, and I have to crush it down for work. I’m using Python since I suck
at Excel, and Python also. But still, Python is pretty comfy. RODRIGO DABOIN SANCHEZ: So if we’re kind
of taking a look– oh, what was that? COLTON OGDEN: They’re basically just
saying they have a huge Excel table and they have to crush it down for work. They’re going to use Python instead
of Excel because Python’s pretty nice. RODRIGO DABOIN SANCHEZ: Yeah, Python
gives you a lot of flexibility. And we actually– David teaches
a class at the business school that starts off in Excel, then
talks about database languages, and then moves on to Python. And it’s just kind of like the different
things that you use these tools for. And obviously Python gives
you a lot of flexibility, so– but, yeah. So if we’re looking at
this board right now, and we’re thinking about if we’re
writing a video game version of this, what do we need in order to code this? The first thing that comes
to mind is, well, we actually need a way to represent
the board, right? And so I preemptively created
a file called But in the plan, let’s
just jot to ourselves, we’re going to need a 2D array,
probably, to represent the board. And then we’re going to be,
obviously, moving it around a lot as we try to solve the game. And we should ideally keep
in mind an image of what the game looks like when it’s solved. So maybe we’re also going to
need a 2D array to represent the solved board or the goal. All right. If we take another look at
this, we see that there’s always going to be this empty slot. And as we shift tiles down or right, to
the left, it’s kind of moving around. So it might be useful to keep track
of the position of this empty tile. So if we think about a 2D array, this
might be position 0, position 1, 2, 3. And then this is row 0. And then this is row
1, position 0, 1, 2, 3. So we’ll probably want to
keep track of this empty slot because if we think about how we’re
going to implement shifting tiles, what we’ll probably want to do
is just swap the location of the empty tile with the tile in the
direction that you’re trying to move. So it’ll be nice to have a
reference to that position. So we’ll need a location variable
to keep track of empty tile. COLTON OGDEN: The chat’s curious about
your distro of Linux, by the way. Do you want to share? RODRIGO DABOIN SANCHEZ: Oh, yeah. I have– lsb_release dash a– Ubuntu 18.10 cosmic. COLTON OGDEN: Nice. RODRIGO DABOIN SANCHEZ: And I
actually have to give a shout out to one of my co-workers, Karin Zedan. He helped me. I was actually using Windows before. And I wasn’t very familiar
with the Windows terminal. And what I had to do instead
was download a batch subsystem that ran Linux on Windows. And it was nice for a while,
but it’s still kind of growing, and it hasn’t implemented all
the features that it needs. So some things that I wanted
to run on it, didn’t work. And eventually, I decided
to dual boot my computer. So this computer is actually running
Windows and Linux, but separately. And so when I shut it
off and turn it on, I can pick which operating
system I want to use. COLTON OGDEN: That’s pretty cool. RODRIGO DABOIN SANCHEZ:
So yeah, it’s pretty nice. I can program in my
Ubuntu, and then if I want to do Microsoft Word or whatever,
I can switch over to Windows. So you know, that’s nice. So where were we? Yeah, so we’re talking
about things that we need. We’ll probably want to be
able to see the board somehow. So we want function to
display board on screen. Let’s see. What else do we need? We probably need– if we want
to make moves with the keyboard, we’ll probably need
some sort of listener– listener for keystrokes. Which, remind me, does that
come built into a Love2D, right? COLTON OGDEN: It does. RODRIGO DABOIN SANCHEZ: It does? COLTON OGDEN: Yeah. Love2D has a function
called love.keypressed, which is a callback function
that Love will trigger. There’s a hook in the executable
that is always pulling for input. And whenever it gets any keystroke
or any interface, mouse, keyboard, joystick, whatever, it goes
through all the callback functions that you’ve registered
via love.keypressed. Well, it goes through all
the callback functions it has registered and then
calls the logic you’ve defined within those callback functions. RODRIGO DABOIN SANCHEZ: Yeah. So that’s pretty nice. In Python, when I was tinkering
around with the idea for this game, I actually realized that I was going
to have to download a library in Python to help me keep track
of a keyboard listener. So we’ll have to take a look at
what library to use for that. And the game’s not too complicated. So basically the last
things we’ll likely need is just, if we want to solve the game,
maybe a function to solve the game. And then how do we know that we’re done? We probably want some sort of
“game over” screen or something. And I think that’s a pretty
good starting point, right? This is a nice little to-do list. We can knock these out one by one. COLTON OGDEN: I usually
do my “game over” screen, ultimately, very, very last– once I’m on stream at least. RODRIGO DABOIN SANCHEZ: Yeah. I mean, it’s not really
like a functional thing that the program needs, but
it’s kind of like a nice, OK– COLTON OGDEN: It’s a nice way
to package it up with a bow and be like, oh, here’s a game
that’s actually complete, more or less– or at least feels complete. RODRIGO DABOIN SANCHEZ: Exactly. So OK. We saw that with Python, essentially
you just kind of write things down and you can run it, because
it’s an interpreted language. And so I propose that we actually
start by modeling the board. And let’s actually put this to-do
list down here so we can refer to it. COLTON OGDEN: So Lance Maker’s
question is, are you printing the state of the board on the terminal? Or will you be rendering images? RODRIGO DABOIN SANCHEZ:
So the board will just be text based on the
terminal, just a simple– as much as– you see,, plan.txt here. You would just see like 1, 2,
3 4, 5, 6, 7, blah, blah, blah. That would be the board,
kind of like in a square. Just by default, I have it so
that when I clear my screen, I have my directory listed, like
all the components and stuff. But if you actually don’t want
that, you can have that gone too. COLTON OGDEN: Quite a bit easier to
start implementing something like that too, compared to making all the
artwork you need to make otherwise. RODRIGO DABOIN SANCHEZ: Yeah. We saw yesterday how long it
took to make sprites and stuff. COLTON OGDEN: And those
were simple sprites too. And then making games like this,
you can focus more on the gameplay so you don’t have to spend as much
time on the resource development. And games like rougelikes,
for example, are very rich in terms of
what you can do with them. But they’re Ascii art. So they take one thing, put no emphasis
on it, and then put a lot of emphasis on everything else. It’s like pros and cons, you know? RODRIGO DABOIN SANCHEZ: So
what I’m doing right now is I’m just creating a class. And we briefly talked
about that yesterday. COLTON OGDEN: We’ve mentioned
object-oriented programming. We haven’t gone into tremendous
detail on the mechanics of it with what inheritance
is, what polymorphism is. RODRIGO DABOIN SANCHEZ:
Essentially what we said yesterday was that writing
a class is kind of like writing a blueprint for something. So if you want to represent an object– in this case, we want
to represent the board. So we want to have some sort of
idea and code of what a board is. We can envision that– things that a board can do is make
moves, render itself, randomize itself, check if it has matched a
goal state of some kind, if we want to attribute a function
for the board to solve itself. These are all things that a
board should be able to do. So what I’m doing is I’m writing a
class to make the blueprint of what a board is and what properties it
might have and what methods or actions it can take, et cetera. COLTON OGDEN: Essentially let’s
us define a new data type, where that new data type is, instead
of being an integer or a string, it’s something that’s a little bit more
representative of something we might find in the real world–
a board, for example. In computer science, there is no
intrinsic data type that is a board. But we can define– RODRIGO DABOIN SANCHEZ: Exactly. COLTON OGDEN: –roughly
speaking in an abstract way, the different pieces of information and
the functions that we might associate with a board, sort of lump them together
so we can think about boards versus the numerical information
we would need to keep– have a representation of that. RODRIGO DABOIN SANCHEZ: And so I just– I was kind of typing a little
bit while you were explaining. And this is touching
on what we were talking about yesterday about the constructor,
which is different syntax in Lua. But essentially when you create a
board, you define it as a new data type. And you actually want to– In Python, there is such a
thing as an int, I guess. They’re a number. And there’s a difference between the
theoretical existence of a number and then actually having the number 4,
like writing x equals 4 or something. So we can have this
blueprint of what a board is, but then we actually want to create one. And then when we create one, we
want to attribute properties to it. And so that’s what the
constructor is going to be doing. So this kind of may be a
little bit foreign syntax– def underscore, underscore,
init, self is essentially the syntax for starting to
define the constructor in Python, where self is just referring
to the board object itself. And so what we’re referring
to here in the plan is that we need a way to represent
the board and solve the board. So the goal– so the
solved state, if we want to have it look something like this, I
propose making a 2D lists of some kind. And since we know that we want to
print the board onto the terminal, I’m just going to go ahead and
make the numbers just strings. And the nice thing about this
is that I can preemptively put a space between the number
because I know if later on I’m going to have a number like 10,
that’s going to take up two character positions. Whereas if I have single
digit numbers, they’re not going to be aligned in the same way. COLTON OGDEN: Right. RODRIGO DABOIN SANCHEZ:
So I’m preemptively trying to make sure that they
line up by keeping them in text. COLTON OGDEN: That’s cool. RODRIGO DABOIN SANCHEZ: So yeah. This is me creating the board
right now in the solved state. COLTON OGDEN: Kind of much
like creating sprites. Speaking of that, V1Rani was
saying, those sprites yesterday. Slytherin 2. Because remember the snake? The 2 looked like a snake. RODRIGO DABOIN SANCHEZ:
Oh, yeah, yeah, yeah. That was funny. COLTON OGDEN: And Nacleric,
have you played Dwarf Fortress? I have played Dwarf
Fortress– not a lot, though. It’s got a pretty
tremendous learning curve. Have you played Dwarf Fortress? RODRIGO DABOIN SANCHEZ: I have not. COLTON OGDEN: Have you
heard of Dwarf Fortress? RODRIGO DABOIN SANCHEZ:
I am– most of the games I play are very few in number. COLTON OGDEN: Gotcha. RODRIGO DABOIN SANCHEZ: I play FIFA. COLTON OGDEN: That’s a
nice way of saying no. RODRIGO DABOIN SANCHEZ: Yeah. [LAUGHTER] COLTON OGDEN: That’s a
very political way of– RODRIGO DABOIN SANCHEZ: I love games,
but I don’t play them that often. COLTON OGDEN: Yeah. RODRIGO DABOIN SANCHEZ:
Well, that’s a lie. I play the same games a lot. COLTON OGDEN: Are you
familiar with rougelikes. Do you know what that is? [INAUDIBLE] RODRIGO DABOIN SANCHEZ: Actually–
well, do you want to explain? COLTON OGDEN: So if I can– I’ll show you an image
here on a separate laptop. So So this is what a roguelike looks like. It’s kind of like– have you ever seen an image like this? Look something like that? RODRIGO DABOIN SANCHEZ: It
kind of makes me think of– what’s it called? Everyone plays it nowadays. The World of Warcraft
or something like that. I don’t know. COLTON OGDEN: Yeah, not quite. Or like this, where everything just
kind of looks like Ascii artwork. Have you seen the games like that? RODRIGO DABOIN SANCHEZ:
This is all new to me. COLTON OGDEN: Oh, OK. Well, we can maybe talk
about it another time. Dwarf Fortress is a type
of roguelike, sort of. But it’s much deeper
roguelike than most roguelikes are and much more flexible and much
more catered towards building things. But yes, to answer Nacleric
question, I have played it– only a little tiny bit. A class is a struct on
steroids says Andre. Yeah, in a sense. Kind of. Depends on the language I think. Bhavik Knight, why not use loops? I’m guessing we probably are going
to be using loops at some point. RODRIGO DABOIN SANCHEZ:
Yeah, they’re probably referring to me making this board. COLTON OGDEN: Oh, yeah. RODRIGO DABOIN SANCHEZ: I’m just like– COLTON OGDEN: Yeah, that’s fair. Yeah, you could do it
with a loop, I guess. RODRIGO DABOIN SANCHEZ: I’m only
ever going to have to do it once. COLTON OGDEN: This– you visually
can– if you’re a programmer, you visually can see–
there’s a point to be made about visually being able to see
exactly what the data structure looks like. And so I actually agree
with this decision to draw everything out with strings. It’s just a lot more readable. RODRIGO DABOIN SANCHEZ:
It helps me visualize. Now I can see this is
the shape of the board. COLTON OGDEN: One thing
I probably would do is I’d probably do that, just
because– that it’s perfectly aligned. RODRIGO DABOIN SANCHEZ:
Yeah, that’s true. And it’s– COLTON OGDEN: A little bit like that. RODRIGO DABOIN SANCHEZ:
Especially because alignment is important in Python. It won’t care about this so much. But if I don’t have this indented
properly, it’s not going to– COLTON OGDEN: Oh, yes, yes. An important– RODRIGO DABOIN SANCHEZ:
It’s not going to like it. COLTON OGDEN: –thing
for those new to Python. Indentation is crucial. You absolutely need
layers of indentation to let the interpreter actually
work and run your program. RODRIGO DABOIN SANCHEZ:
Questions in the chat? COLTON OGDEN: No, I don’t think any– so dunder proto, anyone
here got the reference? I’m not sure what that
is a reference to. And then MOBA games, V1Rani is asking. I used to play League a bit and Dota. Have you played MOBA games at all? League or Dota? RODRIGO DABOIN SANCHEZ:
League of Legends. That’s what I was thinking. Not World of Warcraft. No, actually. COLTON OGDEN: Oh, I got you. OK. Yeah, a little bit. A little bit. Too many games in the world. Way too many games. RODRIGO DABOIN SANCHEZ: So
what I’m doing right now, I created this solved
state for the board. And what I did after that is, I
imported from the copy library this method– or this
function called deepcopy. And the whole point of that is I
know that the board is ultimately going to get shifted around. And instead of writing this
all over again or doing a loop, I just essentially figured I
would just make a copy of the goal and then shuffle it later. Because if we think
about this game, it’s not necessarily going to be solvable
from any configuration of the board. So the way that I want to solve it is
I want to start from a solved state and then make, I don’t know, like
100 random moves in any direction. That way, I know I’m starting
from a position of a solved board, making legal moves only,
shuffling the board that way. COLTON OGDEN: Right. RODRIGO DABOIN SANCHEZ:
So in order to do that, I just want the board– which
is going to change eventually– start off being in the same
configuration as the goal. I don’t want to change
the goal because I’m going to need it to compare whether
the current board is the goal. So that’s why I’m making a copy. And the reason I’m using deepcopy
method is because what it does is it recursively copies lists that
also contain lists, for example. So– COLTON OGDEN: Just saying
self.board equals self.goal. We just make a reference–
basically a pointer to self.goal, and then he changes to self.board. RODRIGO DABOIN SANCHEZ: Exactly. COLTON OGDEN: Before you
change it to self.goal. RODRIGO DABOIN SANCHEZ:
If I do something like this, what Python
is going to understand is that these two variables
are referring to the same– COLTON OGDEN: Same data structure– RODRIGO DABOIN SANCHEZ:
The same data structure. So if I change one, the other
one will be updated as well. And I want to avoid that. So I’m basically making a separate
copy of the board from the position– the starting position of the goal. And I’m making sure that I am avoiding
the issue of having only references to the lists within the list by doing
this deepcopy, which recursively makes sure that I copy everything. COLTON OGDEN: That’s very smart. RODRIGO DABOIN SANCHEZ:
Then I’m also starting to track the location of
the empty space, which I have just chosen arbitrarily
to denote with these underscores. And I know this is 0, 1, 2, 3. And then this is 0, 1,
2, 3– so column and row. Maybe we can have something
like max col and max row. COLTON OGDEN: Rabin is asking,
deepcopy should be inefficient, right? RODRIGO DABOIN SANCHEZ: Maybe
with a very large data structure, but this is so small that I don’t think
it’s going to really make a difference. COLTON OGDEN: Yeah. This is a tiny data structure. Making 1,000 copies of this data
structure wouldn’t– you wouldn’t even notice any speed change probably. But if it were hundreds of thousands of
rows in a database type data structure, then yeah, I could see that
being very inefficient. RODRIGO DABOIN SANCHEZ: This actually,
semantically, I think is backwards. Max row, max col. And I am going to
go ahead and have these constants be– well, they’re constant, be equal to
4– even though I know the index is 3, because I can imagine myself wanting to
loop things repetitively from 0 to 3. And with the Python range function,
the parameter that you pass into it is not inclusive. So if I pass in a range of 4,
it’s going to give me 0, 1, 2, 3. And so it’ll just be nice having
these constants for semantic purposes. COLTON OGDEN: The Last Kek was saying,
why not just Control C and Control V? For any self.goal, self.board. Pretty funny. RODRIGO DABOIN SANCHEZ: Oh, yeah. [LAUGHTER] That would accomplish the same
purpose, but programmatically, it’s not necessarily great design
to just copy and paste. COLTON OGDEN: Dry principle. RODRIGO DABOIN SANCHEZ: Yeah. COLTON OGDEN: Very important. RODRIGO DABOIN SANCHEZ: It’s more
of a me being a stickler, kind of. And so we won’t worry about this yet– not jump into the moves just yet. OK. So we have an array to
represent the broad, an array to represent the solved board. COLTON OGDEN: Last Kek,
we know you’re joking. We’re just messing with you too. RODRIGO DABOIN SANCHEZ: Let’s see. I maybe just want now to make sure
that everything’s working so far. So I may want a way to
print this to the screen. And Python has another one of these
funky class names called repr, for representation– like how do I want this board to be
represented if I print it or something? So it’s just a list that contains lists. So I can imagine doing
something like, for i in range of the max
number of rows, for j in range of the max number of columns. Then I want to just print– we called this self.board– at positions i and then j. COLTON OGDEN: Often, you’ll see y, x,
x, y for 2D data structures as well– RODRIGO DABOIN SANCHEZ: True. Yeah. We can do that. It’s the same thing. But whatever. COLTON OGDEN: It’s fine. i, j is also fine. RODRIGO DABOIN SANCHEZ:
Then if you notice– if I just open up the Python
interpreter right here, if I print something as simple as hello,
I get knocked down to the next line. But if I include this
additional parameter called end, which denotes what I want at the end
of the print statement– by default, it’s a new line– you’ll see that when I didn’t have
it, it knocked me down one peg. And here the prompt is the same– in the same line. So if I know I want to print the
column side by side, then I– when I’m iterating, probably don’t
want that new line behavior by default. COLTON OGDEN: Oh, V1Rani was
mentioning you have spaces in these double digit numbers here. RODRIGO DABOIN SANCHEZ: Oh,
that’s– yeah, that’s true. Thanks for keeping up. That would have been fun
to see after we printed it. COLTON OGDEN: Yeah. That one’s fine. The 9’s fine. You can put– RODRIGO DABOIN SANCHEZ: True. COLTON OGDEN: –a space there. RODRIGO DABOIN SANCHEZ: Good point. OK. COLTON OGDEN: Thanks,
V1Rani, for mentioning that. RODRIGO DABOIN SANCHEZ:
Thanks for looking out. Yeah, sweet. COLTON OGDEN: Aeroman
was asking, just joined. What are we doing today? We are doing Game of
Fifteen, a prior CS50 pset, but we’re doing it in Python. Traditionally, we’ve done it
in C, at the Command line. And then Rabin is saying, in JS,
we call the prototype methods with underscores dunder methods. So they call those funky methods
dunder repr, dunder init, et cetera. I have heard that as well, yes. RODRIGO DABOIN SANCHEZ: So
I’m returning an empty string here because the repr function,
by default, must return something. And so I’m not going to
store this value anywhere. This is just– if I don’t
include it, Python will complain. OK. So right now we have
a board with a goal– an initial starting board– and
then we have a way to print this. So in the main screen, let’s
just do something like b equals– we’re probably going
to have to import this. So from the Board, which is
the name of our Python file– from Board, we want to import– it’s this kind of funky syntax because
the file name is called, and so this is referring
to the file name. And now what I’m importing
is referring to– if I want to import any methods or classes
or whatever, we have a Board class. So we’re going to
import the Board class. And then here we can do something
as simple as b is set to– we’re going to define a Board. And then we can print b if we
want and see what it looks like. All right. Unless I screwed something up, let’s
see what happens if I run main. Name “goal” is not defined. Oh, LOL. So that’s what the self keyboard is for. This is called self.goal,
and I just put in goal. So thanks, Python, for
watching out there. OK. So interesting– we have
1, 2, 3, 4, 5, 6, 7, 8. And now these are kind
of jammed together. So we might want to put some
spaces in between these. COLTON OGDEN: Aeroman was
asking, what terminal is this? I am new to Python, so
can you suggest where do I get this terminal or platform
where you are writing this code? RODRIGO DABOIN SANCHEZ: What terminal? Oh– COLTON OGDEN: Or platform. RODRIGO DABOIN SANCHEZ:
I configured my terminal. So by default, it didn’t look like– it wasn’t purple and stuff. But in– let’s see. Do I have my other– where’s my– here we go. Come on, Atom– not highlighting. COLTON OGDEN: I mean,
what we can probably say is that it’s terminal with a
specific bashrc or bash_profile, whatever. I forget what it is that customizes
your Command Prompt in your– we’ve talked earlier, 18.10 or
18.08 Linux– or Ubuntu Linux, something like that. RODRIGO DABOIN SANCHEZ: Yeah,
I’m on Linux Ubuntu 18.10. And so there’s the bash dot– or the
.bashrc file that helps you customize all this. And so I wanted different things
to be in different colors. So I knew– so the name of my
current directory is in blue. And then my user name is in green. Everything else is in purple. And if I’m in a GitHub repo, it will
show me the branch I’m on in yellow. But maybe that’s a topic
for another stream– how to customize a terminal or so. COLTON OGDEN: V1Rani’s asking, is
“self” similar to “this” in JS? JavaScript. RODRIGO DABOIN SANCHEZ: Is what? COLTON OGDEN: Is “self” similar
to “this” in JavaScript? RODRIGO DABOIN SANCHEZ: Oh. Yeah, it’s similar. And– oh, that looks
a little bit better. In Python, the whole
point of it is that– this is the wrong–
let’s just close this. In Python, the whole point
is that if you’re in a class, the class is a blueprint. And so let’s say we have
a blueprint for a house. The house itself, if it has
some things that it can do, it’s going to refer to itself
using the “self” keyword. The typical example for classes
that I’ve heard used is a car. A car should have a color property. It should have functions like
it can drive, it can break. It can do all these things. And so when you’re writing a class
that maybe is going to represent a car, you can say self.color because
if you instantiate multiple cars, you can imagine you want one to be red,
or one to be green, one to be blue. So the “self” emphasizes that you’re
talking about the current instantiation of the object. So– COLTON OGDEN: “This” is a bit
weird in JavaScript because– I mean, I haven’t
stated this in a while, but for example, every function
has its own “this” scope. So it’s a little bit weird. If you call “this” within a
function that’s within an object, “this” is actually the
function and not the object. I believe that’s the case. I ran into this issue fairly recently. And the chat was talking
about how they’re having issues with “this” in JavaScript. And yeah, it’s a bit weird in ES5. The “self” in Python
is much more consistent and I think easy to understand. But yeah, not arrow functions. Yeah, arrow functions
don’t have that problem. That’s correct. RODRIGO DABOIN SANCHEZ: All right. So so far, so good, right? We have a 2D array to
represent the board. So maybe we can get rid of
this and put this over here, or something like– things we have. And then we have a way to
represent the solved goal. So let’s put this on here as well. We have this location variable
to keep track of the empty tile, although we haven’t used it yet. We have a function to display
the board on the screen. OK. So this might be a reasonable
time to look for a listener. And what I’m going to do
right before that is– you can have the main– or whatever Python file
that you want to run, you can have it run just kind of
without having to do any main methods or anything like that. But it’s annoying if you want to
have different functions that run it different– like at specific times. Because anything that you have, just
in that outermost layer right here, is always going to
run by default. And so if you want to wait to
execute some things, it might be favorable to
put it in a main function. So what I’m going to do for now is I’m
going to just create a main function, def main. And then all it’s going to do for
now is print the board, I guess. I want the board as a
global variable for now in case I want to refer to it outside
of the main function at some point. And then if you have a main
function, you have to– I mean, you can do something as
simple as calling main right now, but the convention in
Python is to write this more cryptic looking statement called if
name equals equals main, then run main. And what this does is,
essentially if you’re importing this file
to a different file– so if this is going to be a
helper file for some reason, it won’t execute the code in that one. And if you’re just in this
one importing other stuff, it knows that this is the main file. And so it’s going to
call the main function. But we usually just wave
our hands at the syntax. All we know now is that this should,
in theory, accomplish the same thing as before, which it does. OK. So now let’s look for
a keyboard listener. And the one that I was toying
around with is called pynput. And this is for those who may not
have ever heard this before, I wanted to point at the documentation. But it’s just this small, little library
that supports listening for the mouse and then listening for the keyboard. For the purposes of this
project, I guess we’re not going to be doing much with the mouse. But it does have a way to monitor the
keyboard and control the keyboard. And then it handles errors and such. COLTON OGDEN: TheLastKek
says, got to go. CS50TV. Love the stream. Cheers. Thanks, Last Kek, for joining us. RODRIGO DABOIN SANCHEZ: Thank you. COLTON OGDEN: See you
on the next stream. Andre is saying, JavaScript’s
“this” is a bit strange. But yeah, it is. In ES6, they made it
a little bit more, I think, consistent with
other programming languages. And to Andre’s point, in C-like
languages– like, for example, Java– this is a bit more
like “self” in Python. And then Aerospace Man–
or Aeroman123 was saying, I’m working with a
supercomputer in Barcelona running aerospace aerodynamics and
CFD simulation using open foam. And then people were saying,
oh, that actually makes sense. That’s why your name is Aeroman123. JS is lexcially scoped,
but when you want something similar to dynamic
scoping, “this” gives us that. On arrow functions, there
is no “this” defined on the scope, so it goes up the scope
and attaches itself with parents “this” definition. I have to reread on all
that for the JS stream. That should be coming
up in a couple of weeks. And then Putevoditell was a new viewer
from yesterday– says, hello, everyone. Tomorrow there will be
a stream because today I will not be able to be on
this wonderful channel. Well, I hope you can join
us for tomorrow’s stream. Glad to have you with us. Yeah. Think we’re all caught up now. RODRIGO DABOIN SANCHEZ: All right. COLTON OGDEN: So while I was
doing that, you programmed the– RODRIGO DABOIN SANCHEZ: Well, no. It’s– they– in the
documentation, they have, hey, if you want to control
the keyboard, for example, this is how you press and release
keys or whatever manually. But if you just want to listen for
the keyboard, you just copy this code. You have to import the library, I think. I don’t think it comes by
default in the terminal. I think I had to install it with pip. And then once you have it, you
can import the keyboard method. And all that it has is
kind of similar to Love2D now, where you’re listening
for when people press keys. It has a method that fires when people– or when someone– a user
presses a key and one that fires when they release that key. And here’s kind of the
actual listening portion. And if you read through it, you
see that you pass in the methods that you’re going to be using. So they’re going to be using
an onPress and onRelease. And what I did was, I just
kind of put this in our file where I imported from py
input, the keyboard function. I defined the onPress
and onRelease key exactly as they had in their documentation. And then in the main function– in the main method, I
started the listener. So that it’s constantly listening. And– COLTON OGDEN: It takes the
place of like a, while true. RODRIGO DABOIN SANCHEZ: Yeah. Yeah. And the only other thing is
that in the documentation they say the way you can stop
the listener, you can pass it– you can basically broadcast
some special codes. But more simply, you can return false. So in this default behavior
that they have here, if what the user press was the
Escape key, they just return false. And so if we want to just run their
code and see what that looks like– I press Enter to execute
the file in the program and its realized that I press Enter. So if I press Up– the terminal has this kind of annoying
behavior where if you press some keys it gives you this annoying thing. But here’s their feedback
key.up has been released. If I press a alphanumeric
key, a is pressed– and the terminal has this
annoying echo, so we’re going to want to silence
that during our program. Because we won’t want it to display what
key we’re pressing every single time. But yeah, I can just do
something as simple as Escape now and it says Escape
key has been released. And if we take a look at the code,
that is exactly what this does is whenever you print, whenever you
press a key, it just tells you such and such key was pressed. If it was alphanumeric, and
then if it was not alphanumeric, it tells you that it was a special key. And you know, it just
prints which when you press. And when you released, it
tells you that you released it. And then if what you
pressed the Escape key, it kills the listener, which
basically terminates the program because that’s the last thing
happening and our main method. So yeah. Now what we want to do is adapt this
so that we can essentially have moves that we can make in the game. COLTON OGDEN: It’s kind of like
Love2d, like you’re saying, it gives you the ability to like
check basically, oh, it’s constantly looking for input, sort of almost like
behind the scenes, but in this case we have to [INAUDIBLE]
to find that behavior. And then if you press– if it
checks for the specific code, and if that code is equal
to escape, or whatever, you can decide to quit
the game, or you know, do some sort of movement of the– to
change some value of your data structure to actually make the game playable. And also, thanks Putevoditell
for the host, much appreciated. RODRIGO DABOIN SANCHEZ: So
now we can basically just get rid of some of the
stuff that they were doing. And then I don’t know, here we can– we want to do something I guess. So we can print, hello for
now, just as a placeholder. And what we want, is whenever the user
presses the Escape key, that seems reasonable to want to stop the program. So we can also– we’ll
probably want to be listening, if we look at the board,
we imagine the empty space as kind of what we’re going
to control moving around. Let’s say that we want the behavior
where if we press the Left key the empty space swaps with
the number to its left. So here we would swap with 15. And then if we press Up, it goes
to 12, and so on and so forth. So we haven’t actually implemented
moves in the board yet, but what we can do for now to
make sure that this is working, is just print like left, or
print up, and right to make sure that we have something working. So– COLTON OGDEN: Sanity checking. RODRIGO DABOIN SANCHEZ: Right. Sanity checking. So right now I’m going to say,
if keyboard. key up is pressed, I’m just going to print, up. And then even though, you know, ideally
you’re not supposed to copy and paste code, sometimes you just gotta. COLTON OGDEN: Who suggested that
up above, I forgot who that was. That was, oh, that was
TheKek, TheLastKek, who did that, which is funny. RODRIGO DABOIN SANCHEZ: And here we go. So in theory now, if we press
up, right, down, or left, the program will tell us
what key we’ve pressed. And then, later on, we’ll
replace this with actual behavior of moving in the board. And– COLTON OGDEN: It is an important step. Make sure that you’re actually
checking for the right things. And that it’s triggering that– sort of like penciling
in your application. Like filling in, like that, your
sketch with the actual color, or the actual paint, or however
you want to analogize it. But we do that even when we
program games to prevent stream. Like a typing game, we did that. We put all the labels and all the
text everywhere with like mock data. And this is something like people
in web development do a lot too. They’ll make a static– if they’re
like trying to make a dynamic web page, they’ll put everything that’s
static, that would represent what the website would look like ultimately. And then actually flesh it out
with the JavaScript, or the Ajax, or whatever that they would normally
do to make it actually truly dynamic, or whatever. RODRIGO DABOIN SANCHEZ: Did I miss
anything in the chat or anything? COLTON OGDEN: No. No. No. No. RODRIGO DABOIN SANCHEZ: OK. Yeah. So, so far we have what we
were talking about before, the annoying echo that we’re
going to have to get rid of. But we see now, that when I was
pressing the up key, it was printing up. When I was printing left,
it was printing left. Down is pressing down. [BELL DINGING] Right it was printing right. COLTON OGDEN: Sorry, if that was loud. I forgot to mute my phone. RODRIGO DABOIN SANCHEZ: For
now, let’s go back to the board. And we will probably want to implement. So we have a listener
for key keystrokes, now we want a function in the board
that will allow us to make moves. So we kind of alluded to this
earlier how we want to create moves. If we’re taking a look at the
board, if I press the left, I’m going to want to swap
with the element to my left. If I press up, I’m going to want
to swap with the element above me, and so on and so forth. The only tricky thing is, even
though this looks like a square this isn’t necessarily a square memory. This is, if we recall, and we’d
find this, this is a list of lists. So we will have to be careful with what
indices we’re adding and subtracting when we do this. But I propose that we start– it’s going to be very repetitive if we
have very similar behavior for making a move to the left, very similar
behavior for making move up, and the only thing
that’s changing is, you know, whether you’re
adding to the column, or you’re adding to the row index. So what I propose is having
just a general function for making a move where we’re
going to have some place holder variables, x and y. So let’s do that. Let’s create a move function. It’s going to have to
take in itself again. Ideally– we could do this in two ways. We could have it refer
to self.board every time, but later on, if we want to make a
kind of like artificial intelligence solve function, that
solves itself, that’s going to be annoying
because we’re going to have to search different possibilities. And so if we start off with an
initial composition of the board, we’re going to want to
basically make four copies of it because we can move
up, right, down, left. And if the move function is
always referring to self.board– like if we move up, then it’ll
update self.board for everything. So I propose that we allow a
parameter in the move function where we can just pass in whichever
board we want to make the move on. And then in the main .py file, we can
just pass in the objects board for now. OK. So we’ll also want to keep track
of the location of the empty space. And then since we know
that the way we’re going to swap elements
in our list of lists is by adding and subtracting
to the indices of the list, we’ll want to pass in like an x
and a y, like you were saying. This seems like it
should be comprehensive. And if we want to just test out, you
know, how does swapping work in Python? If I open up the interpreter
again, and I have– usually what you would imagine
is you would have something like, you know, x=1, and then y=2. And then, if you want
to swap x to be y, you would have to have some sort of
temp variable, maybe set to 0. And have something like,
temp=x and then let’s see– COLTON OGDEN: x=y, y=x. RODRIGO DABOIN SANCHEZ: x=y. COLTON OGDEN: y=temp,
sorry. x=y, then y=temp. RODRIGO DABOIN SANCHEZ:
And now y=temp. And so what this would do, is now if
I see what x is, x has 2, y has 1. But in Python, we actually
don’t need this middleman. Because we can do something
as simple as this– if I have x=1, and y=2, we
can have something like x,y=y,x. Which is very, very nice. COLTON OGDEN: Yeah in
Lua2, which is super cool. RODRIGO DABOIN SANCHEZ: In Lua as well? COLTON OGDEN: Yeah. RODRIGO DABOIN SANCHEZ: So yeah, now we
have x having the previous value of y, and y having the previous value of x. So that’s just how swapping works in
Python, for those who didn’t know. That’s going to be something that
we’ll probably want to do here. And let’s just go
ahead and jump into it. So we know that we’re
going to be accessing a board that’s a list of lists. So we want [email protected]– and when we move– let’s go back here. When we move this tile we’re
starting off at the position– the empty position that we have
at which we’re passing in here. So let’s say– and the way that
we define the empty position is, by default, the board
is going to be at 3, 3, this won’t matter when we shuffle it. But we were going to have the
location of the empty space tract with this variable, so
we’re going to have– on the x, it’s going to tell
us what index in the row it is. So like, this is row
0, row 1, row 2, row 3. And the y component it’s going to
have what index in the columns it is. So this is 0, 1, 2, 3. So we’re going to want to refer to
the location at position 0 for the x. And then the empty location
at position 1 for the y. All right. And this is going to be the empty slot. So this is basically
like our first thing. Then the next thing
that we want to swap, is either the tile above it, to the
left, to the right, or below it. So since we want this to be a general
move function where later we’ll have something like def move up, and
then def move right, and def move down, and def move left, where all these
essentially just call the move function with some parameter, some xy. What we want to do, is if we’re adding– if we’re moving up,
we will want to add– or no, we will want to subtract
1 from the rope position. And if we want to move
to the left or y, we’ll want to subtract or
add to the y position. So we can do this– we can do all this logic of whether
it’s supposed to be minus or plus and which one is supposed to be,
in these abstracted out methods, such that in the– so move
up would look something like what we would pass in
the board and the e_loc. And then we would pass
in something like– if we’re moving -1,0
something like this. So here in the actual move
function, we would only have to worry about adding x and y,
whatever they may be, to the index. So this is going to look
something like e_loc 0+X. X could be negative or positive. And then e_loc at position 1 + y. All right. Now we’re running out of space. So this backslash in Python, let’s
us kind of move on to the next line without having to worry
about the end of a thought. OK. So here, essentially,
we have on the left hand side of the swap, the position of the
board that contains the empty space. On the right hand side,
we have the position of the board that is, you
know, some relative distance from the empty space based on
whatever we input to be x and y. So if in like this move up example,
we’re putting in -1 for x, and 0 for y, that means that moving
up this right hand side will be the empty
location -1 at the same y. Which if we look at this– if this is empty location 3, 3– empty location -1 will be, and the x
component will be 2, so it’s a 0, 1, 2. And then, it’s same y component. So that’ll be the same. That’ll be the 12. So yeah. That looks like we have about right. And so now what we essentially
want to do, like we did x,y=y,x. Is swap this. COLTON OGDEN: Reverse them. RODRIGO DABOIN SANCHEZ:
Reverse the order. COLTON OGDEN: Virani was
was saying, “I just learned how to construct dynamic web pages
with Express and EJS templates,” That’s awesome. We’ll probably actually have a
stream on that in the near future after we get past the CSS, JavaScript,
Bootstrap, jQuery, all that fun stuff. We’ll probably go into
Node.js, and therefore Express. Bhavik_Knight, in reference
to your temp swap example, with saying the temp=0 line was
actually redundant. in way I think. Yeah, because you could just
do temp=y or whatever. But I think you were just trying
to illustrate that like temp– I guess maybe in reference
to other languages where it would have a temp variable,
I can see you would usually send it to something by default.
And then he was asking, “can we do nested
class within the board? Like a class move with up, down,
right, left, that inherits from move?” RODRIGO DABOIN SANCHEZ: I don’t
remember if you would put it inside. I know you can definitely
do inheritance. But I don’t recall having seen
an example of a class written within a class like that. COLTON OGDEN: I think you can. It’s been a while since I’ve
actually needed to do that in Python. I don’t think I would do
it in this example though. I don’t think abstracting the idea
of a move really saves as much. RODRIGO DABOIN SANCHEZ: OK. So far so good. And then what we did here was we update
the position of the empty location. Because if we just swapped it– so let’s
pretend this is what we’re swapping. We swap position 3, 3 with
position 2, 3 If we move up, we want the location of the empty
space to be updated as well. We don’t want to refer to 12
as the empty location now. So we’re also adding to the–
and this is kind of syntax for like updating something. So like if I opened up the terminal
again, Python, and then I have x=1, I could do something
like x=x + 1 to get 2. But I could also do x +=
1 to add 1 and update it. So now it’s 3. So this +=essentially means add,
you know, whatever it is to it, and then update the value. So what I’m doing here now
is making sure I also update the position of the empty
space with the x and the y. The only other thing that
comes to mind– and then, of course, I’m returning the updated
board and the updated location. The only thing that comes to mind,
is if we look at this example again, where we’re in this
configuration, even though it’s solved, we could imagine that
the users in a corner. So like the empty
location is in a corner. And then, say, it’s at
the bottom right corner, the user tries to move
it to the right, or down, and those locations don’t exist. So– COLTON OGDEN: We, had that [INAUDIBLE]
yesterday with Minesweeper too. When we were doing the
pre-calculation for all of the nodes. RODRIGO DABOIN SANCHEZ: It would
be an easy thing to miss out. Like to just forget to code it. And then, you know, something breaks. So before we actually do the
swapping we should probably check. So yeah, swap update, empty location. And then up here we’re
going to check legality. You know hashes are how
you comment in Python. So the way we can do this is if the
empty locations, the x component plus x, because x could
be positive or negative. So if this is less than
0, or if, but whoops, you don’t have to write, if, twice. If the empty locations,
x component plus x, is greater than 3, because
0, 1, 2, 3, that it’s the 4, so if it’s greater than 3, or if we have
something similar for the y component plus the y is less than zero, or
it’s less or greater than 3 + y. COLTON OGDEN: It’s arguable that
like a namedtuple might have been appropriate for the location too. So instead of having to index and
a 0, you could just do like .x, .y. RODRIGO DABOIN SANCHEZ: True. Yeah. We haven’t really used it much yet so
you may as well go ahead and do that. We can have this be like– or even a dictionary right? COLTON OGDEN: Yeah. A dictionary would work too. RODRIGO DABOIN SANCHEZ: Be like row. And then this could be column. And then here– COLTON OGDEN: So maybe just replace
every 0 with, row, or column. RODRIGO DABOIN SANCHEZ: Ans
this will be easier if I just– yeah, this semantically, is
probably easier to read as well. COLTON OGDEN: I would’ve probably
done the namedtuple with .x. and you could do .row as well. Just to save like readability. Just because it gets a little bit
cluttered here with all these brackets, square brackets. I would’ve probably just made an
empty location and namedtuple. And I have to remember
the exact syntax for it. Because I don’t find
occasion to do it a lot. But there is a– I don’t actually remember if
they made it a native 3.7 or 2.6, just like part of the core language. Because normally you have to– here it is, namedtuple. So you make a namedtuple,
call it, in this case, you could just call
it whatever you want. Which takes in and has
an x and y, like that. And then from every– every time you want
to do that afterwards, you can just say like right here, see
how this is p.x and p.y and you would have the same– that would be
e_loc and then e_loc.x and e_loc.y. It might be a little bit
too much at this point to go back and
retroactively do all that. Especially if you’re like– you’ve mentally already constructed
it with the 0,1 index model. But it’s a nice thing that
they’ve recently started. It’s recently started becoming
pretty trendy with Python. RODRIGO DABOIN SANCHEZ: Yeah. I can see how that would be pretty nice. Yeah. So we could– COLTON OGDEN: You can revert, if
you want, back to the old 0, 1, if that’s easier. RODRIGO DABOIN SANCHEZ: I could see the
semantic value of doing it this way, but I mean, you know, if we’re– COLTON OGDEN: I wouldn’t blame
you for- I wouldn’t blame you. It’s kind of like a brand new like,
wrench to kind of throw into it. So if you want to– if you want to keep it
as it was totally fine. RODRIGO DABOIN SANCHEZ: But I
mean– so here we are again. Wait, I mean, the first location–
so the 0 is referring to the rows, and the 1 is location to the columns. OK. So we’re back where we started. And here we have the
position of the board, of the empty location here
where we’re swapping to. And then we’re changing the position. We’re updating the position
of the empty location. We’re returning the updated board
in the updated, empty location. Here we’re checking
if the move is legal. So if basically we’ve
checked if adding x or y– x or y to the x and y
components of the empty location exceeds, or like goes through
an index that doesn’t exist. We don’t want to do anything. So maybe we just returned the
board and the location as it is. COLTON OGDEN: “Guys, are you
planning on about explaining advanced concepts in Python,
and things like decorators, comprehensions, generators,
in one of your future streams? You guys have a great teaching skill.” First of all, thank you very
much for the compliment. We would definitely like to do
a more advanced Python streams. Veronica is, per what
Bhavik_Knight said, doing a stream in the
near future on and more– well, the stream is called, “A Hundred
Cool Things in Python, Part 2”. We already did in Part
1, where we covered about 40 different small things. We’ll probably do that
again with a future stream. No concrete plans on all
of those necessarily, but doing a more structured
advanced Python stream would be pretty fun and pretty cool. So we’ll little different
take a look at doing that. So thanks for the suggestion. RODRIGO DABOIN SANCHEZ: Now that
we have this general move function, I’m trying to go ahead and update
these to look how they should. So if we know the move
function is returning the updated board and
location, we’ll also want to return whatever this returns. And now we’ll have to change the
x’s and y’s for this each time. OK. So moving up, that’s
subtracting 1 from the row. Moving to the right is leaving the
row alone, adding 1 to the column. Moving down is adding 1 to the
row, leaving the column alone. And then moving left is leaving
the row alone, and subtracting 1 from the column. So in theory we should have
a working way of moving here. OK? So now that we have this, we can
probably update in the main .py file. What happens when we release the key? The only other thing, though, is that
even if we override this behavior to actually make the moves, we
are only ever printing the board at the beginning of the main function. So we wouldn’t actually
see anything change. So we might want to write a function
for the board that just kind of like refreshes the terminal
screen and re-displays it. Something like def refresh. And for this, actually,
if we remember what this– what the terminal
looks like when we were writing the left key, the down key, the
up key, it would give us a little echo. So if we actually
import up here from OS– let’s import system. So that we can clear the
terminal screen programmatically. That way we get rid of
whatever it was previously. And we can just see the latest
version of what we have. We can have in the refresh
method that we’re going to write, we can have the board class
programmatically clear the terminal screen so that in the un-press,
instead of printing hello, every time that we press anything– whoops. Let’s put this here just for my sake. Any time that we press the key,
we will call the refresh method, so that it will clear the
terminal, get rid of any echo that the terminal is
going to display for us. And then here, after
whatever we do, we’re also going to call the refresh method
so that after we press up, or down, or right, or left, it will re-display. So what this will do, is
it will clear the screen, and then we’ll want it to
display the board itself. So we already have a function
that prints the board, so we can just print self. All right. And maybe what we can do since– yeah. This is probably sufficient. So here we have, after we release
a key, we’re clearing the screen, printing the board. Whenever we press a key, we’re clearing
the screen, printing the board. I guess we don’t need to
listen to, print this here, but we’ll leave it for now. All right. And now the only thing that’s missing is
actually writing the moves to the keys. OK. All right. So here, what we’ll
want to do, is we have– we’ll want to– if we take a look
at what our move function does, is it returns the
board and the location. So what we want to do is call– and so it does this return
the board and location. So we’ll want to say b.board, b.– and it’s actually kind of confusing
because I named this, empty location. So let’s just have this be the
same name so I don’t get confused. OK. So b.e_loc, this is going to take
the value of calling b.move up. And it’s going to take in the
board, the empty location, and I think that’s all that it needs. Yeah. Because we took care of the rest. All right. Just for incremental testing, let’s
see what happens when I run this. All right. And e_loc is not– COLTON OGDEN: And crash. RODRIGO DABOIN SANCHEZ: –defined. Ha ha! Perfect. Where do we have e_loc
not being defined? Oh! Where is– here. I named this just Loc instead of e_loc. So I’m trying to use a
parameter that doesn’t exist. All right. COLTON OGDEN: That
will mess you right up. RODRIGO DABOIN SANCHEZ: Now, we actually
have the parameters named properly. And here, I actually specify
the right names, I believe. OK. Let’s try this again. All right. So we notice when I press Enter,
the whole screen was cleared and now we just have the board. So it’s the foc– the center of attention. OK. There we go. So we pressed Up key, and
we have been able to move. COLTON OGDEN: Nice. RODRIGO DABOIN SANCHEZ:
I’ll press Escape to quit so that we can
finish implementing this in the other directions as well. All right. COLTON OGDEN: It’s
nice CLI interface, all things considered too,
rather than having like, you press a key to say I want to
move up, and it has a menu or whatever, and then it like reprints the board
below that, refreshing the CLI. RODRIGO DABOIN SANCHEZ: I think the way
that the old Pset and CS50 used to be, was that it would prompt you. Do you want to move up, left, down,
and right, and then you would type it. And then it would reprint
the board below that. COLTON OGDEN: Yeah, exactly. RODRIGO DABOIN SANCHEZ:
It was kind of annoying. COLTON OGDEN: A little more of
a traditional way of doing it, I think, but also easier to understand. Because you don’t have
to go through like, you know, refreshing in the
terminal, doing asynchronous input, that sort of thing. Right? RODRIGO DABOIN SANCHEZ: We
can actually take a look at what it looks like if we
don’t refresh on key press. So if I, you know, if I just
don’t include this, I think, pass keyword makes it do something? COLTON OGDEN: Pass
keyword will do nothing. Correct. RODRIGO DABOIN SANCHEZ: And so up
is up, right is right, down is down, left is left. OK. So if I don’t refresh the terminal,
we get something like this– COLTON OGDEN: Oh. OK RODRIGO DABOIN SANCHEZ:
Where every time that I press a key, you see like down is b,
up is a, left is d, and then right is c, for some reason. So the terminal is
always printing this if I don’t clear the screen on key press. So that’s why I wanted
to just preemptively do that so we could avoid that. And also, obviously, if I
don’t clear the screen here– so actually let’s just do this. Let’s get rid of this comment now. And if, within the refresh method
itself, I don’t clear the screen and we run it– COLTON OGDEN: Wasn’t this
easier in the Game of Fifteen, asking for which number
you wish to move? There’s only one empty
field on the board. RODRIGO DABOIN SANCHEZ: That’s true. COLTON OGDEN: There’s no ambiguity. RODRIGO DABOIN SANCHEZ: That’s what it
was, which number did you want to move? And so the way this
one is going to work, is you just press with the arrow keys. You move the– COLTON OGDEN: I like
that because it’s nice. You don’t have to think too much about– RODRIGO DABOIN SANCHEZ: And you
can do it more quickly as well. COLTON OGDEN: Yeah. Much more quickly. RODRIGO DABOIN SANCHEZ: And
here, we’re not refreshing. They’re like, we’re not
clearing the terminal. So we get all this junk. Right? So that’s kind of a headache. So that’s why we want to go ahead
and clear this anytime that we press a key so that we don’t have to
see, oh, which key did they press? And also, what did the previous
board look like, or whatever? OK. So, so far so good. And just, you know, just to confirm that
we have the behavior that we wanted to. Oh, you know what? I don’t like that. I don’t like how when
you run the program– py main. You have that kind of
like visual thing where it like the prompt was there, and
then the board, and then it was gone. So at the beginning of the main
method, let’s just go ahead and instead of printing b,
let’s just call it b.refresh. COLTON OGDEN: Nice. OK. RODRIGO DABOIN SANCHEZ: OK. So now as soon as we run the
program it’ll clear everything. OK. That looks better. COLTON OGDEN: That looks better, yeah. That looks nice. RODRIGO DABOIN SANCHEZ:
We should probably have something like, I don’t know,
it just seems kind of lonely. Let’s say something like, print,
welcome to the game of fifteen. And maybe that’ll look
a little more friendly. OK. COLTON OGDEN: Cool. RODRIGO DABOIN SANCHEZ: We should
probably put a space in between. COLTON OGDEN: Yeah. Probably. But it’s nice. Nice little touch. If you were really pro, you
would have like game of fifteen, and like big ASCII art. RODRIGO DABOIN SANCHEZ: Yeah. COLTON OGDEN: You could
get like– you can get– I think there’s websites
where you can copy and paste ASCII art if you like
type it in, they’ll give you a text string you can copy. That’d be pretty cool. RODRIGO DABOIN SANCHEZ:
So we essentially have a workable version right now. If I’m at the left most corner and
I keep pressing left and nothing’s happening, if I’m at
the right most corner and I keep pressing right nothing’s
happening, same if I’m down and I’m pressing down,
nothing’s breaking. COLTON OGDEN: Nice. RODRIGO DABOIN SANCHEZ: And if I’m up– OK. So– COLTON OGDEN: Is the boundary locked? RODRIGO DABOIN SANCHEZ: So far so good. We’re locked into our board. We can’t move outside of it. We can make moves. So nice. We have basic board
function to make moves. You know what I didn’t write
in the things that we need? We need a way to randomize the board. COLTON OGDEN: There we go. Yeah. Because then they’re going to start off
every game and it’s going to be solved. RODRIGO DABOIN SANCHEZ:
It’s already solved. Yeah. OK. So that seems like a good candidate
for another board function, or board method. You know, functions and methods
are essentially the same, except methods are
functions inside of class. I think that’s the distinction. COLTON OGDEN: Yep. RODRIGO DABOIN SANCHEZ: So what
I alluded to at the beginning, is a way that we want to
randomize the board such that it’s solvable is, we want it
to start from a solid configuration and then make n number
of moves to randomize it. So let’s make another
pseudo constant here and call it like, shuffle
magnitude or something. And just to keep it simple so that,
you know, I can at least still solve the game without having to play
for a considerable number of times, let’s just self shuffle it
like, I don’t know, ten numbers. COLTON OGDEN: One time. RODRIGO DABOIN SANCHEZ:
Yeah, we have a 50% chance of starting in a winning move because
it can be to the right or down. COLTON OGDEN: Well yeah. You could do boundary
constraints on your shuffles such that it wouldn’t consider it
a shuffle if it tries to move– RODRIGO DABOIN SANCHEZ: True. COLTON OGDEN: –outside of the bounds. But– RODRIGO DABOIN SANCHEZ: Yeah. COLTON OGDEN: For the
sake of simplicity. RODRIGO DABOIN SANCHEZ: I mean,
if we just make it, you know, if we make the magnitude
large enough that I don’t think it will really matter. COLTON OGDEN: Choose down 100 in a row. RODRIGO DABOIN SANCHEZ:
What are the odds, right? OK. So we have the constructor,
the printing, let’s just– I don’t like how it’s all blue. I’m kind of like weird
about some things. Clear the screen and print the board. There, now there’s a
nice little separator. See, now I’m thinking about it. Now I’ve got to do it for all of them. You know? Represent the board. And then here– COLTON OGDEN: There are
some streamings where I don’t even comment my code because
I just completely forget to do so. I try to be better about it. But– “Just get a linter to remind
you of that,” says MKloppenburg. Yeah. It’s a good point. RODRIGO DABOIN SANCHEZ: Checks. Let’s just say, makes legal move. COLTON OGDEN: The linters that are
integrated into the text editors too– I can get one for– I think you could definitely
get one for Atom and VS Code. It’ll actually show you on the left
side of the screen, in your file here, if you have issues. You can do like pep8 linters. And you can also do like syntax
linters and things like that. It’s pretty cool. RODRIGO DABOIN SANCHEZ: OK. So we want this shuffle
function method that randomizes board using succession of legal moves. So that way, we know for sure
that it’s going to be solvable. All right. We’ll probably need the
random library, I guess. Yeah. So let’s go ahead and import that. What’s it like from
a,b,c, d,e f,g,h,i,j– COLTON OGDEN: I think
you just import random. RODRIGO DABOIN SANCHEZ: No. I like having them alphabetized. Right? Wait. Harvard student doesn’t know
the order of the alphabet. Does r come before or after o? COLTON OGDEN: Comes after o. RODRIGO DABOIN SANCHEZ: Ah-ha. See? We’re just human. From random import, random. COLTON OGDEN: I would say because
English is your second language. RODRIGO DABOIN SANCHEZ: That’s true. COLTON OGDEN: I’ll give you a pass. But Spanish uses the same
alphabet, don’t they? Same order? RODRIGO DABOIN SANCHEZ: Yeah. But it has some different letters. COLTON OGDEN: So you
don’t get an excuse. RODRIGO DABOIN SANCHEZ: It’s a
total different thing, you know? COLTON OGDEN: Kind of. Maybe. I’ll give you that one. I’ll give you that one. RODRIGO DABOIN SANCHEZ: So,
from the random library, there’s a function called randint,
that gives you a random integer. And I think we talked
about this in your stream yesterday also, that you should
generally seed your random number generator so that you keep getting
different results each time that you run it. COLTON OGDEN: Which you want to
test specific corner cases, but yes. RODRIGO DABOIN SANCHEZ: True. Good point. OK. So I think, now if we
go back to our shuffle– COLTON OGDEN: R.B was asking,
“In Ruby, the convention is that you write code such
that you don’t need to comment. Is there something like this in Python? As far as it goes, writing a lot of
comments in Ruby is bad practice.” RODRIGO DABOIN SANCHEZ: What? COLTON OGDEN: It’s a bit strange. I mean, I’m not too involved
in the Ruby ecosystem. What I imagine they’re
probably referring to, is writing self documenting code, in
the sense that your variables are clear. RODRIGO DABOIN SANCHEZ:
Oh, yeah, So like I mean– COLTON OGDEN: Function names are clear. RODRIGO DABOIN SANCHEZ: We
couldn’t name these anything. Right? We can name this like
self.tomoato and self.pear. And, you know, it would’ve worked
as long as he kept track of it. Can you tell him hungry? No I’m just kidding. COLTON OGDEN: We just had some
awesome curry katsu– katsu curry, which is pretty good. Yeah, I think, I mean, I
wouldn’t go so far as to say don’t comment your code at all in Ruby. I feel like that’s kind
of a silly convention. Especially if you’re
writing in algorithm that’s of moderate complexity. I don’t think any amount
of self documenting code is going to make everything 100% clear. Like, if you’re doing, I don’t know,
like, recursive maze generation algorithm or something
in Ruby, I don’t think there’s any amount of
variable naming and convention that’s going to save a programmer
from knowing exactly what’s going on, not knowing exactly what’s going on. So I would say don’t
worry too much about that. In Python, definitely use
comments when they make sense. And I think this should apply
to most programming languages. And I have to look into
Ruby and see why they’re saying that because I don’t know
the ins and outs of the language quite as much as I know
Python’s as a language, but my instinct is that they’re
referring to variable names and some of their syntax that sort of
makes it clear whether something is a Boolean expression,
or a Boolean function. Like the question mark that you can use
for function names and stuff like that. But, yeah, I would say use comments
but make your variables and functions and lay out of your code sort
of obvious what’s going on. As much as you can. Right? RODRIGO DABOIN SANCHEZ: Bhavik
is asking, “Magnitude of 100 won’t necessarily mean that we have to
do 100 moves to solve the game, right?” So yeah. That’s– I mean you’re completely right. The magnitude that I’m
referring to, is like how many moves are we going to make before
we present the board to the user so that, you know, it’s at least
not in the solved configuration. COLTON OGDEN: It could
theoretically be 0. Because it could
theoretically shuffle it, and then, shuffle it all back
there and back to the beginning. RODRIGO DABOIN SANCHEZ: Yeah. COLTON OGDEN: It’s not– yeah. It’s– RODRIGO DABOIN SANCHEZ: Like, I
mean, in a shuffle magnitude of 10, it’s not that crazy to
think that they’ll move, you know, up and then left. But then they’ll move down and right. And then move up and then back down. And that by the end of
the 10 moves they’ll end up right exactly where you started. COLTON OGDEN: I don’t
know how you would compute like, just how many moves it would
take from that starting point, that 100 magnitude. Because I can visualize, like, the
algorithm kind of going back and forth. And I can imagine there’s
multiple ways, probably, to move the things to get
it back in the same position if it’s like, kind of making
moves in the same area. I don’t know 100%. But I would imagine
that that’s probably– it probably doesn’t map anywhere close. “Self documenting code is code
without comments,” I wrote– code without comment– wait. “Self documenting code equals
code without comments.” I wrote, “nasty spaghetti code
equals code without comments.” Someone else wrote, “True, true.” “Mathematically the game must maintain
its invariant to be solvable.” RODRIGO DABOIN SANCHEZ: Yeah. That’s why we don’t want to just
randomize the whole list of lists. Because then we might end up with
a configuration that can’t actually be solved. COLTON OGDEN: Yeah. That’s true. RODRIGO DABOIN SANCHEZ: OK. So what I was doing initially
in the shuffle method, is first I seeded the
random integer generator. And then I thought to myself
something along the lines of, OK, for 0, till however
magnitude is, I probably want to pick a number
between 0 and 3, or 1 and 4, and have that map to
one of these functions. Right? So like maybe getting
0 means you move up. Getting 1 means you move right,
2 move down, 3 move left. Then I realized I probably needed
some data structure to do that. So I’m going up here and I’m creating a
data structure that does exactly that. So the nice thing about
dictionaries in Python is that the keys can be anything. That can be like strings or
ands or whatever, what have you. So I’m going to have a
dictionary called moves, which is going to be like a dictionary
of legal moves that I can make. And so if the key is 0, I’m
going to have it be self.move up. I don’t want to include
the parentheses because I don’t want it to actually execute. I just want to kind of delay that. COLTON OGDEN: Using function
pointers, basically. RODRIGO DABOIN SANCHEZ: Basically, yeah. And then I’m going to have 1.2. And if you’re curious about why a
mapping like random numbers to this, it’s like I think of up, right, down,
and left, it’s kind of like north, east, south, and west. And so, just in my mental compass,
I start up here and then kind of move clockwise. That’s why I’m going up,
right, down, left, 0, 1, 2, 3. COLTON OGDEN: I go
up, down, left, right. RODRIGO DABOIN SANCHEZ: You
go up, down, left, right. COLTON OGDEN: Yeah. I think it’s because
up, down go together, and then left, right go together. And so I just see them– RODRIGO DABOIN SANCHEZ: That’s valid. COLTON OGDEN: –sequentially. RODRIGO DABOIN SANCHEZ: Yeah. For me it makes sense to
go in the cyclical way. COLTON OGDEN: I can I
can visualize that too. RODRIGO DABOIN SANCHEZ: Oh, I forgot
to refer to the fact this is– COLTON OGDEN: Rabine, I might take a
look at that style guide at some point, and then maybe we’ll do a
Ruby stream in the future too. RODRIGO DABOIN SANCHEZ:
Sefl.move down and then 3 is going to refer to self.move left. I cheated. OK. All right. So that seems reasonable. 0 self, move up, 1, move right,
2 move down, 3 move left. OK. So now in the shuffle method,
I’ve seeded the generator. I am going from 0 to
whatever magnitude I wish. And then choosing a random
ends between 0 and 3. And now I’m going to have
it do something like– let’s see, self.moves– COLTON OGDEN: Add 0 to 3, inclusive? RODRIGO DABOIN SANCHEZ: Yes. Self.moves at i, and now I
want to actually execute it. Remember that move up, move right, at
all, take in the board and the location that we’re going to update. So I’ll have to pass in
self.board here, and self.e_loc. That’s what I named it, right? Yes. OK. COLTON OGDEN: I agree with Andre
saying, “Comments aren’t necessarily aimed at explaining what code
is, but why it’s doing it.” Yeah. And I agree that no amount of self
documenting code can help with that. Like I said, you have
to understand what’s going on in the programmer’s
mind and there are algorithmic sort of map mental mapping. Right? Like that could– you could
conceive of a problem abstractly in a way that’s not even representative
of any programming language construct, but you have to use the programming
language to sort of create that. Like creating a data structure,
using that data structure, in a particular way. Visualizing a problem
in a particular way. The what versus the y,
that’s essentially it. Yeah. RODRIGO DABOIN SANCHEZ:
All I’ve done now is I’ve just made sure that the first
thing I do is shuffle the board. So when we actually rerun this now,
I have a key error, which is great. Not intended. So in line 48 and shuffle, key error. Oh, LOL. I did not mean to do i, I meant to do m. So what I was doing is I was
essentially indexing into moves as long as the loop went from 0 to
whatever, and what I meant to do was each time that the
loop iterates, m is going to take in a random
value between 0 and 3. And that’s the position
that I want index into. OK. All right. So– I mean, obviously, this
is randomized in some way. It doesn’t look super random
because it’s only 10 moves. But if I do this like 1,000 times, then
that definitely looks more shuffled. I don’t really like that the blank
space is starting kind of anywhere. And like it’s fine. Right? We know it’s solvable. But just like us aesthetically,
I like the idea of it starting in the bottom
right corner area. COLTON OGDEN: Sure. Yeah. RODRIGO DABOIN SANCHEZ: So I’m
going to do something that’s not really necessary per say, but– COLTON OGDEN: You mean, like move
the underscore to the bottom right no matter where it is. RODRIGO DABOIN SANCHEZ:
And so obviously, I don’t want to just swap its location
with whatever supposition 3, 3, because that could potentially
break the solvability of the board. COLTON OGDEN: Right. Yeah. You have to actually move it
there, the same way you do it– RODRIGO DABOIN SANCHEZ: Right. So I’m going to just, you know,
at most, if we run this again– so at most, I would have to
move it down 1, 2, 3 times. And then let’s say it started up here,
I would have to move 1, 2, 3 down. And then 1, 2, 3, to the right. So we could just write– COLTON OGDEN: Are you
just going to call self.– are you going to call move three
times to the right, three times down. RODRIGO DABOIN SANCHEZ: Yeah. So for i in range, like,
max number of rows, I might just do self.moves down is 2. Slef.moves at 2. Self.board, self.e_loc. And then, I’m going
to do the same thing. Even though it’s
syntactically the same thing, semantically, you know, just thinking,
I’m going to move the columns. And right is 1, up right. COLTON OGDEN: So this is of like
the what versus the y, right? Like this is a good example of
why comment would be useful here. Like you know exactly what’s going
on here, I mean, roughly speaking, it’s a little abstract. But it’s like, you
don’t maybe understand the reason for why they’re doing
this, and so somebody in their comment would be like, we want to make
sure that the underscore starts at the bottom right every
time for aesthetic purposes. Like I don’t know how you’re going
to communicate that necessarily with just pure syntax. RODRIGO DABOIN SANCHEZ: Mm-hmm. COLTON OGDEN: Like that’s a human sort
of aesthetic desire more than anything else. So yeah, that’s to
Andre’s point, I think that’s an example, a good example
as to illustrate using comments that are based on the why, not the what. RODRIGO DABOIN SANCHEZ: Right. And even– so I I’ve worked as a TF
for CS50, and I had to grade code. And so previously, you
know, we have graded on correctness, design, and style. Where correctness is,
does the program work? Style, is like, is it
formatted properly? Does it contain any
sort of comments at all? And design, is you know, how
efficiently was it written? Some decisions that went into it. But one of them, is like, how
useful are the comments, right? Because the comments could
just be cluttering up the code if they’re meaningless. And one of the things we say
is, if you’re writing a comment, don’t just restate what you can
clearly read in the code itself. Tell us like, what the what the
decision making process was behind. Like why are you doing this? So I could have easily
written a comment here that says, you know, make three
moves down, make three moves right– that’s just kind of restating this. But what I’m doing here is, you
know, I optionally, I just want to– or maybe, for aesthetic
purposes– for aesthetic purposes, move the empty space to
a lower right corner. So even though the code is legible,
you might be like, uh, OK, why? But the comment says, oh, this is what
the person that coded this wanted. COLTON OGDEN: You got to know what the
programmer is thinking when they’re writing the application so that you
can get into their frame of mind and understand the problem
they’re trying to solve. RODRIGO DABOIN SANCHEZ: So now
we see that the board is shuffled and we’re starting in
the lower left corner– lower right corner. Yes. English isn’t my first language, so. COLTON OGDEN: Yeah, left
and right, you know. RODRIGO DABOIN SANCHEZ: OK. Great. And just third time–
three times is a pattern. Is that the saying? COLTON OGDEN: What is it? RODRIGO DABOIN SANCHEZ: If you do
something three times it’s a pattern. Or like if something
happens three times. COLTON OGDEN: Oh, yeah RODRIGO DABOIN SANCHEZ:
Like once is an accident, two is a coincidence,
three is a pattern. Something like. COLTON OGDEN: Yeah. RODRIGO DABOIN SANCHEZ:
I don’t know actually if that’s the saying in Spanish,
or if that’s a saying in English. COLTON OGDEN: Is that
a saying in Spanish? RODRIGO DABOIN SANCHEZ: I have no idea. I don’t know. OK. So we’re making some good progress here. We have managed to randomize the board. So all we have left is a function to
solve the game, and a game over screen. Solving the game is going to be
a little bit annoying, I guess. So we can leave that last. Unless we kind of do
like a temporary, kind of like, cheat, where we
say, hey, def solve self. All we’re going to do is say,
like, self.board=deep copy of self.goal right? Like this is kind of like
a dumb way to solve it. Right? Right now. COLTON OGDEN: Hey, solved. RODRIGO DABOIN SANCHEZ:
Or if we do this, oh– COLTON OGDEN: It would
be cool if over, if like, you have a timer that just kind of
like does the moves individually for the solve algorithm or whatever. RODRIGO DABOIN SANCHEZ:
Well, what I am hoping to– I think we’ll have time. Is I want to write– so instead of having this cheap kind
of like cheating solve function, is replace this with Breadth-first
search algorithm that will search for the correct path to take. And then solve the game for us. I think we’ll have time to do that. Because all we have left is, you
know, check game over screen. And– COLTON OGDEN: Oh, did you type
a self.board with an ‘ed’? You know what they’re saying? RODRIGO DABOIN SANCHEZ: Not really. COLTON OGDEN: Oh, they
were saying something– I think– RODRIGO DABOIN SANCHEZ: Self.bored. COLTON OGDEN: Wasn’t
sure if they had it– of you had written that
as a typo or something. RODRIGO DABOIN SANCHEZ:
I guess I can check. Well, I mean, Python
will tell me, right? If I’m referring to a
variable that doesn’t exist. COLTON OGDEN: If you’re assigning
it to something, though, I wouldn’t consider that
a syntactical error. Right? RODRIGO DABOIN SANCHEZ:
Let me control p.solve. COLTON OGDEN: Or if you’re
saying something to it, it would just consider that
a new variable declaration. RODRIGO DABOIN SANCHEZ: No. I think they’re trolling. COLTON OGDEN: I think were trolling. Thanks for the troll,
BlueBooger, we appreciate it. RODRIGO DABOIN SANCHEZ: OK. So we are going to test now. So I just arbitrarily mapped the
solve function to the Shift key. So now let’s see if we
rerun this and press Shift. OK. So we have solved the game. COLTON OGDEN: Good job. RODRIGO DABOIN SANCHEZ: All right. So we probably now– it’ll be a lot faster to just
implement game over than solve. So we can do that ideally by
checking whether the goal is equal to the board somewhere. So I’m thinking we can have it be– let’s see, let me
refer to my notes here. Something that we do
pretty often is refresh. So, OK, here’s a thought,
here’s what past me thought of. We can have it check– since we know that the last
thing in our main function, right, is the keyboard listener. If we want the program to
end we have to return false. We have to give this kind of
like signal to the listener, return false, like, OK, stop. So what we can do is,
since, what we always do is refresh every
time we press a key, we can include in the refresh method,
a check for whether the goal is the same as the board. And then have the refresh
method return true or false. Where if kind of, you
know, counter-intuitively, if the game is over, and like solved. You return false. So that the listener quits. Otherwise, you return
true, so that it continues. So let’s do that. OK. Let’s go to refresh, here. And let’s have it do this– after it welcomes you and clears
the screen and everything– here, let’s just check
something like, if self.goal, which is the original list of lists that
we created, if this is=to self.board, return false. So that we terminate the listener. Otherwise, just return true. OK. Yes. And here now, what we can do
now, is just return refresh. Or if you’d return true to this
listener and it doesn’t do anything– so here, what we can also
do is just return b.refresh. Wait. What am I doing here? Oh, if the game is over. Here, return, b.refresh. Actually, I don’t think
I need to do this here. I think this would be sufficient. Right? OK. Let’s try this out. And now if I solve, OK, it’s done. So we might want to give it like
a, congrats you won, type of thing. So here we’ll say if the board– is kind of like more intuitive for me to
ask the question the other way around. I don’t know why? If the board is equivalent
to the goal, print, Congrats! You won! COLTON OGDEN: Nice. RODRIGO DABOIN SANCHEZ: And maybe
like separate it a little bit from the board. Then we fire that message. And here– COLTON OGDEN: Then it will end. Right? RODRIGO DABOIN SANCHEZ: –we will say, if we solve it, Congrats! You won! Game is over. COLTON OGDEN: You can
test it manually too. If you were like to it only
do like five, or maybe let’s three shuffles or whatever. RODRIGO DABOIN SANCHEZ: Let’s bring
down the shuffle magnitude to like five. It’s very likely that we’ll have
to rerun it a few times in case we automatically win. COLTON OGDEN: Yeah. RODRIGO DABOIN SANCHEZ: Yeah. Like see, we just started and won. COLTON OGDEN: See, it
doesn’t quit there. See that? RODRIGO DABOIN SANCHEZ:
That’s interesting. COLTON OGDEN: So there’s a slight bug. RODRIGO DABOIN SANCHEZ:
But that time it did. COLTON OGDEN: Oh, did you rerun it? RODRIGO DABOIN SANCHEZ:
Yeah, I just did. This time it didn’t. COLTON OGDEN: I’m not
sure why that’s the case. RODRIGO DABOIN SANCHEZ:
This time it didn’t as well. Interesting. COLTON OGDEN: Looks
like most of the time– are you sure you reran it? RODRIGO DABOIN SANCHEZ: And look,
that time I reran it, and it did quit. That’s so strange. COLTON OGDEN: Yeah, that is a bit weird. It’s doing it every single time too. Like you’re winning every time, almost. RODRIGO DABOIN SANCHEZ:
Let’s increase the magnitude. COLTON OGDEN: Oh, are you hitting shift? RODRIGO DABOIN SANCHEZ: I only– no. I was just– Oh, was I? I was hitting shift. Was I? No. COLTON OGDEN: I don’t know. RODRIGO DABOIN SANCHEZ:
I don’t remember. All right. The chat will tell us. COLTON OGDEN: Now you can
try and solve it, right? RODRIGO DABOIN SANCHEZ: It’ll
be funny if I can’t, right? COLTON OGDEN: I mean, it’s
not an easy game to do, right? RODRIGO DABOIN SANCHEZ: Congrats! You won! COLTON OGDEN: OK. So we know it works. RODRIGO DABOIN SANCHEZ:
I’m pretty sure that wasn’t the optimal way to solve it. COLTON OGDEN: Probably not. RODRIGO DABOIN SANCHEZ: OK. Good. So our game over screen is working. Right? Now we will implement a
more robust solve function that uses Breadth-first search. So maybe people in the stream may not
be familiar with Breadth-first search. Maybe what we need to
talk about that first. Solves the game using
Breadth-first algorithm. Let’s just pull up a
tree and talk about it. Binary tree. Maybe it doesn’t have
to binary– search tree. Search tree. OK. COLTON OGDEN: It’s a little hard to
see in the chat, or in the stream. RODRIGO DABOIN SANCHEZ: How’s this? COLTON OGDEN: Oh, that’s good. RODRIGO DABOIN SANCHEZ:
So this is just– for those who are not familiar with
search algorithms, the purpose of them is if you’re trying– in the context of maybe
like AI or something– if you’re trying to like,
for example, in our game, let’s say this is the
state of the board, and we want like an artificial
intelligence to solve the game for us. It’s going to take this initial
kind of screenshot of the game and then it’s going to have to search
through different possibilities that it could foresee if
it makes certain moves. So obviously, you know, the AI would
have four possible moves to make here. If you can move up,
left, down, or right. Obviously, if it moves down to
right, it’s not going to do anything. But it won’t know that until it does
it and sees the new state of the game. If it moves up, we’ll
have something like this. And then this will be
like a new possibility and from here it can move
up, left, right, down, again, and so on and so forth. And so in the context
of a search tree we can model the game as a
tree, where the root, which is the very first element in the
tree, is the initial starting point of the game. And then instead of having only
two directions here, maybe it has four branches, one four
up, down, left and right. And then if it makes a move
up, it’s at this new state of the game, where once again, it’s
faced with, it can move up, down, left, right. And so you can envision this tree with
four branches each time, progressively getting larger and larger. And so the way that
Breadth-first search works– so pretend that our goal state is
to 7, at some point down the line it’s going to get to a point
where the screenshot of the board is actually 1, 2, 3, 4, 5,
6, 7, 8, 9, 10, 11 whatever. Let’s pretend it’s the 7. The way that Breadth-first search works
is first it starts, it checks the root. Then if that’s not the goal,
it checks, you know, this node. Every kind of like circle in
this tree is called the node. Then it check this node. Then it will check this one. And then if neither of
these are the goals, it will move on to the
next level of the tree. And check this, this, this,
until it checks this, and then finally gets here. That’s opposed to another algorithm
called Depth-first search, where it just goes all
the way down one branch. So like, let’s say the AI
says, I’m going to move up. And it’s going to keep, you know,
going down that like, path in the game without even considering what
would have happened if it had moved to the left as its first move. Then once it reaches the conclusion,
which actually might be really, really long if, you know, in the
original state of the game all you have to do to win is move left
for some reason, or move up, or down. But if you move in a
different direction, you have to like do a bunch
more moves or whatever. So Depth-first search could potentially
take like a really long time if it goes down the wrong branch. Whereas Breadth-first search
is just going to be like, OK, I’m going to try moving up. That wasn’t the win. Let me try moving left. That wasn’t the win,
and so on and so forth. So we’re essentially
going to just be kind of traversing a tree level by level
as opposed to branch by branch. COLTON OGDEN: To that note, Bhavik had
said, “Does Breadth-first search always take fewer steps than
Depth-first search?” RODRIGO DABOIN SANCHEZ: No. Because what if the goal was– COLTON OGDEN: Number one or whatever? RODRIGO DABOIN SANCHEZ: Well,
in this example, it would be. But we can draw, right? I like going to this blank slate. And then, it’s for
typing, but I have some– so like, oh, this is an
old thing that I had. COLTON OGDEN: Wouldn’t it funny
if there was like something like really blasphemous? RODRIGO DABOIN SANCHEZ: No. I don’t– I don’t condone
blasphemous activity. Erase all. OK. COLTON OGDEN: You could
I was also RODRIGO DABOIN SANCHEZ: Oh, really? COLTON OGDEN: Yeah. Oh, but you have a touch screen too. That’s sick. RODRIGO DABOIN SANCHEZ: Yeah. COLTON OGDEN: I didn’t know that
this was touchscreen tablet. RODRIGO DABOIN SANCHEZ: So
if we can imagine kind of like a tree where you
have a really long branch, and then maybe like, a lot of
other branches per level, right? And then these each had
like a lot of branches, whatever, blah, blah, blah, blah. Using Breadth-first
search, you would have to search this one, then this one,
then this one, then this one, then this one, then this one, and this
one, this one, and this one, this one, this one, until you got here. Whereas if you use
Depth-first search you would just, whoop, automatically get
to the end and be like, oh, that’s it. But by the same token, if the goal
state is over here for some reason, Death-first search would
look through this branch, then it would look through this
one, then through this one, and through this one, this
one, until it finally got here. Whereas Breath-first search would
check this, this, this, this, and then find it. So depending on the– COLTON OGDEN: Way the tree is set up. RODRIGO DABOIN SANCHEZ: –on
the way that the tree set up. One is faster than the other. So I just arbitrarily
was like, OK, let’s just use Breath-first search to search. OK. COLTON OGDEN: BlueBooger had
mentioned that Red Blob Games website has excellent tutorial on
Pathfinding and Python and game programming. I think I actually checked
out that once in a long time ago when I was getting more into
like procedural generation algorithms for like rougelikes and stuff. They have, I think if
it’s the same website, they have a lot of really
cool resources on that. So yeah, definitely check that out. RODRIGO DABOIN SANCHEZ: All right. So let’s give it a crack. Let’s try to implement this. Right? Where’s my editor? Here it is. COLTON OGDEN: Oh, Bokkengro, “You
guys should add a description to your stream.” Yeah. That’s a good point. We should. Thank you for mentioning that. I will I’ll do that soon. “Are you guys just two random
dudes doing Python tutorials, or what is this?” Yeah. So this is– so CS50
is a course at Harvard that has a YouTube channel and
Facebook and all this stuff. And we’re kind of an extension of that. We’re based at Harvard,
and Harvard University. And we have access to a bunch of people
here that all know a lot of stuff. So, Rodrigo, is a CS
student here at Harvard. And he whipped up this Game of
Fifteen problem set from a prior year, and he’s doing it in Python. I do game programming. We’ve got David J Malan, who hosts, who
sort of lectures CS50, and sort of mans the ship, so to speak, does
a whole bunch of other stuff. So, yeah, definitely check us out. Watch some of our prior vlogs. Go to our YouTube channel, if you’re curious about our lectures and whatnot. We do a lot of different stuff. So we’re just kind of new to twitch. So growing our presence
on this platform. RODRIGO DABOIN SANCHEZ: Also, I want
to touch on something that I just saw someone write in the chat. Where let’s say we have an example–
so the comment was from Andre, Breadth-first search is
exhaustive and it will certainly find the shortest path. So that’s a good point. Say we have, like especially
in the type of game, where you have multiple ways
of arriving to the same state. Right? Like earlier– do I
still have an example here where I could have probably gone
left, up, and down, and you know, won the game, but I went in the
other direction like a few more times and finally won it. So we have multiple ways of
getting to the same state. Some of them will be
shorter than others. And so let’s pretend that we
have multiple goal states. So maybe square is the goal state. And so we can win the game either
by making one move, or making three. So Depth-first search will find this
solution, which is potentially longer. But Breadth-first search,
since it goes level by level, it checks every node at each level. So it will inevitably find
the shortest solution. Whereas Depth-first search
might find another solution, but it might be longer, for example. And there are certain– what’s it called? Possibilities, where one branch might
go on indefinitely and so Depth-first search never checks any other
part of the tree or something. Another note about
Breadth-first search is it’ll find the shortest path to victory. OK. Good note. OK. So what we’re going
to do is since this is going to be probably a
more lengthy function, is we’re going to map it out first. We’re going to write
what we’re going to do. So we want to have– one thing that we want
to avoid is like getting stuck in some sort of infinite
loop, where we make a say– we want to remember
states we’ve been in. Right? We don’t want to we don’t want the AI
to start off at some starting state, make a few moves, end up right
where it was at the beginning, and then check the same moves
that he had checked before, and then, you know, get stuck making
the same pattern over and over and over again. So we’ll probably want, you
know, like a searched list, where we can store configurations
that we’ve been in before. We’ll also want what is
known as a fringe, which is essentially kind of
like a queue of like, nodes that we are waiting to check out. So like in the tree that I
drew out, if in the first level there’s four different nodes, so
like, going up, right, down, or left, will want to just put those in the
queue for things that we can do. And then check those,
you know, one at a time. So we’ll want to actually
make this a queue. And we’re going to need
to import from q that is after, no that is before r, right? COLTON OGDEN: Q is right before r. RODRIGO DABOIN SANCHEZ: Yeah. COLTON OGDEN: Q, r, s,
t, u, v, w, x, y, and z. RODRIGO DABOIN SANCHEZ:
So we’re going to import– LOL. We’re going to import the queue
class from the queue library. And we’re going to have our fringe be q. If you wanted to do that first
search I think you would use a stack, because then it’s last
in, first out, right? But anyway, let’s not go
down that rabbit hole. So we’re going to use the q
to do Breadth-first search. And I wish I would stop erasing– here we can use this tree. If we use a q, the way
that we do this is, we’re going to check the current node. We’re going to say, is
this the goal state? If it is we can just break out, return
the path that we took to get there. If it’s not, we want to
check its successors, right? Or its children. COLTON OGDEN: So every node then,
just a copy of the board, basically? RODRIGO DABOIN SANCHEZ: Essentially. It’s like a copy of the
board, and we’re also going to want to store like the current
path that we’ve taken to get there. So that at the very end, we can return
that path and then make those moves. And that way we can
actually visually see the program solving it step by step. Instead of– COLTON OGDEN: Wow, this could
get pretty large, couldn’t it? If you’re adding a copy of the board
every node, every time we make a move. RODRIGO DABOIN SANCHEZ:
It’ll get large, which will– COLTON OGDEN: What’s the
mental memory– have you measured the memory cost for
like 1,000 shuffled boards? RODRIGO DABOIN SANCHEZ: So I
was actually messing around with that earlier, and
originally, before I did this I had to be the shuffle
magnitude set to 10,000. And so I was like, man, I am
pretty sure I wrote this correctly, but like, it’s returning anything. And then I was like, I should
print, you know, all the nodes. And so I just see, for like
minutes, it’s scrolling. Like all this different
stuff it’s thinking. So I lowered the magnitude
to be like five moves and then it just like
solved it pretty quickly. COLTON OGDEN: I wonder if
you can like discard prior– like set prior nodes
of the tree to nothing because you’re caching the path. And have that still work. Would that work? RODRIGO DABOIN SANCHEZ: Yeah. So that’s what we want to
have this searched list for, that I have initialized here. So we can keep track of
things that we’ve seen before. Such that if we see them, we
don’t look at that successors. We just stop looking at
that branch altogether. COLTON OGDEN: Right. RODRIGO DABOIN SANCHEZ:
And that should help. OK. So we want to keep track of states
of the game that we’ve seen already. We want to have a queue of like
nodes that we’re going to check out. Like moves that we can make
from the current position. And then we want to have
a root for the tree. So like the initial
starting point is going to be whatever the current board is. COLTON OGDEN: Yeah. RODRIGO DABOIN SANCHEZ: OK. So now what we want to do is add– COLTON OGDEN: How, what we– are we
using the queue to represent the tree? That’s just the current
level of the tree, right? The searched for the fringe? RODRIGO DABOIN SANCHEZ: The
queue will hold all of the– so like in this example,
what we’ll do first, is we’ll add the root to
the tree– to the queue. And then we’ll pop it from the queue. Check whether it’s the goal node. If it is, we’ll return. If it’s not, we will say OK, if
we haven’t seen the state before, go ahead and add to the list
of states that we’ve seen. And then after we do that,
we will find its successor. So we’ll see, where can we go from here? Then we’ll store all of its
successors in the queue. And then for, you know, kind of
repetitively for each new successor we’ll be like, OK,
we’ll pop the first one. queue FIFO, q is first in, first out. So this one would be like, OK, we’ll
pop this from the queue and we’ll say, is this the goal state? And if it’s not, then we will
you know check its successors, add them to the queue. But then since it’s a
queue, we’ll move on to the one that was
added after this one. COLTON OGDEN: I see. So it’ll never– so what’s hinging on
making this work is we will never, ever see the same state again
in what we’re solving. RODRIGO DABOIN SANCHEZ: Right. COLTON OGDEN: Like, otherwise,
this would be impossible. RODRIGO DABOIN SANCHEZ: Yeah. COLTON OGDEN: OK. That makes sense. RODRIGO DABOIN SANCHEZ: We will use
this list to keep track of things that we’ve seen. So we don’t get stuck infinitely
making the same pattern of moves, never making it happen. COLTON OGDEN: I wonder how much– so that I could see
taking all our memory too. Like how much memory
do you think it takes to store every possible
permutation of the board? How many– first of all, how many
possible permutations of the board are there? RODRIGO DABOIN SANCHEZ:
So let’s see, we have 16– is it like 16 factorial? COLTON OGDEN: I don’t know what– I don’t know what it would be. RODRIGO DABOIN SANCHEZ:
Because it could be– it could be you know– COLTON OGDEN: Because I don’t know
if you can, strictly speaking, get– you can’t get every possible
numerical permutation on here because it has to follow a pattern. Like the invariant has
to stay consistent. RODRIGO DABOIN SANCHEZ: True. Yeah. So less than 16 factorial. COLTON OGDEN: Yeah. It would be less than that. But I don’t know what the
number actually would be. But it’s interesting. RODRIGO DABOIN SANCHEZ: I’m sure we
can– it’s a quick Google search. How many possible configurations
of Game of Fifteen? COLTON OGDEN: Or Fifteen Puzzle. It might be known by Fifteen
Puzzle, more frequently. RODRIGO DABOIN SANCHEZ:
Ah, I can’t type. How many different possible
combinations are in the Fifteen Puzzle? COLTON OGDEN: [INAUDIBLE]. RODRIGO DABOIN SANCHEZ: 10 to the 13. COLTON OGDEN: 10 to the 13. So, OK. So there’s 10 to the 13 board positions. Those are all the strings that
are two bytes each, right? So this is interesting. Now, what I have the instinct to do is
to hash all the potential positions, right? To take that data structure, that
list data structure, and hash it. And then store the
hashes in a dictionary. And that way you can immediately
check to see whether that hash exists in the dictionary. Right? Because how are you checking
prior positions now? Are you just going over every single
one of them and comparing them? Is it with equals? equals, equals. RODRIGO DABOIN SANCHEZ: I’m saying,
like if current board not in search of lists. COLTON OGDEN: OK, so you are
doing equals, equals effectively. OK. That’s what that essentially– RODRIGO DABOIN SANCHEZ: That’s probably
why it takes so long for larger. COLTON OGDEN: Yeah. RODRIGO DABOIN SANCHEZ: As
it gets longer and longer. COLTON OGDEN: So what
you can do is you can hash– if you hash those lists, right? That data structure, find a way
to hash it, and deterministically get it to hash. You could store them in a dictionary and
then do constant-time look up of that. RODRIGO DABOIN SANCHEZ: Dictionaries
are constant-time right? COLTON OGDEN: Well, are
roughly constant-time. Yeah. So that would almost be very fast. RODRIGO DABOIN SANCHEZ:
And actually, if we– what’s it called? If we used to set for the searched
instead of a list, that would be– searched is constant-time
look up in Python, I believe. COLTON OGDEN: In a set? Yeah. Yeah, it is. Because they hash it underneath the– RODRIGO DABOIN SANCHEZ: So
we could use a set instead of a list, which I have to– COLTON OGDEN: What if– can you– I don’t know if you
can– well, I guess you can hash. That’s what I’m saying,
the tricky part would be finding a way to hash [INAUDIBLE]
like that deterministically. That’ll be the tricky part. RODRIGO DABOIN SANCHEZ: You know
something we could do is we could– COLTON OGDEN: You could turn it into
a string and then hash that string. You could– by– if you– because the board is always going
to be a different string, right? You could literally just
make a string of the board as it is laid out with the brackets. RODRIGO DABOIN SANCHEZ:
Like 1, 2, 3, 4– COLTON OGDEN: Yeah, with the brackets. Because then you would ambiguously
have 11, and stuff like that. RODRIGO DABOIN SANCHEZ: True. True. COLTON OGDEN: So if you
do that, if you flatten the ne– flatten your list into
a string with the brackets, you can hash those strings. Those you can then store in a set, or
you can store them in a dictionary. But sets would work fine as well. And then you get almost
constant-time look up for those. RODRIGO DABOIN SANCHEZ:
And so the only thing that we’re going to be
changing this algorithm is how we’re representing
the search list, right? COLTON OGDEN: Yeah. The search is no longer
list, it’s going to be a set. And every time you get a– you
are looking at a brand new– set is not indexed. Be aware of that. RODRIGO DABOIN SANCHEZ: That’s fine. We won’t need the check indexes. COLTON OGDEN: What was I going to do? Oh, I was going to check
to see what 10 to 13 was. 10 to the 13 is equal to– RODRIGO DABOIN SANCHEZ:
More than a trillion. COLTON OGDEN: That’s a big number. Yeah, it’s like– what is that? A thousand, million,
billion, 10 trillion. RODRIGO DABOIN SANCHEZ: 10 trillion. COLTON OGDEN: So 10, you could have
10 trillion different nested lists– RODRIGO DABOIN SANCHEZ:
Here’s what I’m thinking. COLTON OGDEN: –that you’re doing
an if statement on in your thing. RODRIGO DABOIN SANCHEZ: Here’s
what I think would be fun. Here’s what– COLTON OGDEN: Well, I mean– And that’s– is that potential–
that’s just for the sake of the Fifteen Puzzle. Right? RODRIGO DABOIN SANCHEZ: Yeah. COLTON OGDEN: That’s insane. RODRIGO DABOIN SANCHEZ: Here’s
what I think would be fun. Let’s implement that using
a list, see like at what point it starts getting really long,
then change the search list to be– COLTON OGDEN: Oh, sure. We could time it. Yeah. RODRIGO DABOIN SANCHEZ: Yeah. And then we could just– COLTON OGDEN: That would be sick. Let’s do that. RODRIGO DABOIN SANCHEZ: Because
we’ll have like a working version. And then, you know,
once that’s done, we can mess around and see like
how much of an impact we can make just by changing the search. COLTON OGDEN: Yeah. Yeah. Yeah. RODRIGO DABOIN SANCHEZ: OK. That sounds fun. COLTON OGDEN: That does sound fun. RODRIGO DABOIN SANCHEZ: OK. OK. So like we were saying,
we want to have some data structure in which we keep track of
all the states that we’ve searched. We want a fringe to be keeping
track of all the different moves that we want to try. And we want to kick off
the tree with a root. So the root is going to
be the current board. And now what we want to
do is we want to add our, you know, our root to
our kind of like tree. So the way that I wanted to do
this was making a dictionary, where we’re going to have a couple things. We’re going to have the board
that we’re keeping track of, and that’s going to be the root. Then we’re going to keep track
of the empty spots location. And that’s going to be the
current empty spot location. And we also want to
keep track of the path that we’ve taken to
reach the current state. So at the root, we’re going
to have the current board– I guess I don’t need to write this out
as it’s own separate variable, right? OK. So originally, so now this is the root. Because the node isn’t just
going to be the board itself. It’s going to be kind of like a
struct containing some information. We’re going to store the current board,
the current location of the empty spot, and then the path that we’ve
taken to reach this node. The root node, we’ve taken no steps
to reach it so the path is just empty. And here it doesn’t matter
whether we use a list because we’re only going to be adding
like some small number of moves to get– we’re not going to do like more than
probably a couple of hundred moves to solve it, I think. I’m sure this is solvable
in a few number of moves. OK. So now we’re going to kick off an
indefinite loop using, while true. This is where we’re actually
going to start searching the tree. So the first thing we want
is kind of like a base case that we just want to quit if– and let’s just write this out
so we know what we’re doing. Quit if no solution is found. Which we should never
have to worry about, but in case, this is important
to write when you’re writing it for the first time, in case you
accidentally introduce a bug into your code, and then
your algorithm doesn’t work, this way at least you break out of
the loop once the queue is empty. So if fringe.empty– and the fringe is
just a native Python q and so instead of like nq, dq, and whatever, what
have you the methods are put empty and I think, get. So this checks whether
the fringe is empty. And here we’re just going to
return an empty path like nothing. OK. So that’s kind of our base case. So now what we’re going to do is
we’re going to dq to the current node from the fringe. So node is going to be fringe.get. Get is the q function that will return
the current first element in that q, And we’ll put it in this node variable. All right. And so let’s write out the
algorithm– inspect current node. All right. Now we want to check, is the
current node the goal state? So quit if node contains goal. All right? Here we’ll check if node at the
board position is self.goal. We’ll return the path
that node contains. So ultimately, what we
want the solve function to do for us is to return like the
list of steps that we need to take. The list of moves that we need to
make in order to solve the game. So if we find that the board in the
current node matches the goal board, we’re just going to return the path
that is attributed to that board. COLTON OGDEN: Hey! How’s it going? RODRIGO DABOIN SANCHEZ: And we
have, David, joining on the stream. COLTON OGDEN: The mystery guest. DAVID: Nice to see everyone. COLTON OGDEN: So we’re doing
a Game of Fifteen in Python. Currently we’re on the solver right now. So where we talked about it earlier–
we’re doing a sort of like a Breadth DAVID: Breadth. RODRIGO DABOIN SANCHEZ:
Breadth-first search. COLTON OGDEN: Breadth-first search. DAVID: Still hung up on that, huh? Why don’t we do a Depth-first search. RODRIGO DABOIN SANCHEZ:
Well, don’t worry. Earlier I was asking Colton
what order the alphabet is in. So there’s that. DAVID: Oh, did you go with alphabetical? RODRIGO DABOIN SANCHEZ:
I tried to, yeah. DAVID: Nice to see everyone though. I look forward to seeing this. COLTON OGDEN: We’re doing
an interesting experiment. So right now we have basically a– this whole algorithm hinges on
checking prior states of the board because the board can only
ever be in one state at a time while we’re solving it. And basically, we can,
instead of, assembling this massive list of
prior states and checking to see if we’ve already seen that state. We can hash the state of the board
as a string and store that in a set and then do constant-time
look up of that hash string. And see how that comparison
actually ends up [INAUDIBLE] time, how much time we save. RODRIGO DABOIN SANCHEZ: But
first, we’re restoring everything in the list to see like what
the difference in time is. If we start off with the
list, versus something that’s going to have confidence– COLTON OGDEN: Because this
list is going to be massive. Especially if we’ve done 1,000 steps
to get to the permutated board. DAVID: But you’re just
using these hashes to determine if it’s
in a one configuration? COLTON OGDEN: If we’ve encountered
this state before while we’re going through the actual algorithm of– DAVID: Oh, at which point, you’d– just so you’re analyzing
the answers that– COLTON OGDEN: We are. Exactly. Yeah. DAVID: Oh, OK. OK that’s, good. I a little nervous there. Because if you pre compute all these
hashes, that’s like infactorial. COLTON OGDEN: Oh yeah. Yeah. No. It’s like 10 trillion different ones. No. No we would, no. We would not do that. Actually, we just looked it up
on the calculator right there to figure out the exact number. DAVID: Oh, my god. You have to think about where
to put the commas there. COLTON OGDEN: Yeah. Nice. DAVID: All right. Well, let me leave you to it. But, good to see everyone. I’ll hop on the chat and looking
forward to seeing this develop. COLTON OGDEN: Cool. RODRIGO DABOIN SANCHEZ: Sweet. COLTON OGDEN: Thanks for hopping over. RODRIGO DABOIN SANCHEZ: All
righty, so, so far we, OK, we have dq’d the root from the q. And we are inspecting
whether it is the goal state. If it is, we are returning
the path that it contains. Otherwise, if it’s not, we want to
add the CurrentNode to our search set, which right now is a list. And then put its children in the fringe. So if the root node
isn’t the goal, we want to add it to the list of
search states that we’ve seen. And then we want to put
its children in the fringe so that we can repeat this
process again with them. COLTON OGDEN: Right. RODRIGO DABOIN SANCHEZ:
So the way we’re going to do that is we’re going to check,
if node board, not in search, which is what we’re
going to change later. COLTON OGDEN: I mean, we can still–
it’s still going to be not in search, right? Because you’re doing it through–
you’re going to look in a set, though. RODRIGO DABOIN SANCHEZ: Yeah. Yeah. We’re going to change
what search looks like. Which will dramatically– COLTON OGDEN: This will actually
be pretty much identical. RODRIGO DABOIN SANCHEZ: Which is nice. Which is why something as simple as
what data structure sure you’re using can completely change the runtime
of your code, or the efficiency. COLTON OGDEN: Oh, yeah. 100%. RODRIGO DABOIN SANCHEZ: OK. So we’re going to go ahead
and append to the search list the current board that we’re seeing. COLTON OGDEN: Also, it’s funny that
Asli was lurking this whole time. So glad to know that you’ve
been in the chat, Asli. Everyone is saying hi to David. If you use Dijkstra’s shortest path
alogorthm on a graph with all the edges it just becomes breadth first search. Yeah. I don’t know too much about it. I have to reread up on Dijkstra. It’s been a long time since I
looked at any of that stuff. RODRIGO DABOIN SANCHEZ: All right. So now we’re going to want some
function to extract the successors from our current node, right? So let’s just pretend that we
have a successors function. COLTON OGDEN: Are all
the successors going to be up, down, left,
right, from that one node? RODRIGO DABOIN SANCHEZ: Right. Yeah. OK. So for child and successor,
which we have to write. Successor doesn’t exist right now. We’re going to say, if the child– I don’t know, now we’re
getting into territory where we haven’t determined
the behavior of successors yet. So actually, let’s just
go ahead and define it. So that, you know. For child and successors, we want to
check whether one of those children is already in the search list
so we don’t add it to the queue. Otherwise, if the successors of the
current node isn’t in our search set, we will add them to the queue. Because say for example, that we’re
starting at the lower right corner. And this is the result
of moving to the right. That would be exactly
the same as this one. So we don’t want to even consider this. And so that will save us the time
of putting this in the queue. So we will skip this and go to that
next one, which maybe like go up or something. So let’s define– let’s
define a successor’s, maybe like a helper function within here
itself, within the solve function. [CHIME ALERT SOUND] COLTON OGDEN: Very
interesting to understand most of things those guys are saying. No, it’s OK. I mean, we’ve gotten into a little
bit of algorithmic territory and I’m not even that good at
algorithms and data structures. I’ve learned a few things
over the years and I should study upon it a
little bit more detail, but this is all good stuff
to kind of be aware of. Just like using the right data, take
that away from the stream if anything. Use the right data for the job. Try to look for it, you know, when
you’re manipulating data like this and doing thousands upon
thousands of potential iterations and all of those things take up data,
that’s an opportunity to optimize. And, Asli, I totally understand. I have off days, as well, all the time. But thanks for tuning in on the lesson. Being around and still
absorbing the material. That’s really like a huge thing. And that’s something I
think that’s important, especially in like language learning. It’s just absorbing sort of passively,
you know, passive media ingestion. Or at least, in this
context, like CS, vernacular and just kind of getting
input, you know, input sources. It’s super important. RODRIGO DABOIN SANCHEZ: All right. So for the successor’s
function, we know that we’re going to want four separate boards. Because one of them
we’re going to move up, one of them we’re going to move left,
one of them we’re going to move down, one of them we’re going to move right. So maybe not like the
nicest way possible. I’ve made four copies of a board
and I’ve stored them in a list. Same thing for– COLTON OGDEN: How large is this
queue going to be at max, by the way? Because we’re popping off the queue
every time we check something right ? Or are we just adding to the queue
and never getting rid of the– RODRIGO DABOIN SANCHEZ: No. We’re popping– every
time that we inspect a node we’re popping it from the cube. COLTON OGDEN: OK. So when might we expect 8. Then we inspect 3. We pop 8 and add 1 in 6,
after the 10, in this case? RODRIGO DABOIN SANCHEZ: We do. Pop 8. We add 3 and 10 to the queue. COLTON OGDEN: Then we go to 3. We pop 3, add 1 and 6 to the
queue go to 10 and then do that. OK. I see. Got it. RODRIGO DABOIN SANCHEZ:
So at most we’re only ever having two, less than
two levels of the tree. COLTON OGDEN: Yeah. I mean it can get large later, but
it’s not going to be like insane. RODRIGO DABOIN SANCHEZ: Yeah. Nice. OK. So blah, blah, blah. e_loc,
and e_loc, and e_loc. So as I kind of referred
to earlier, deep copy, helps for recursively copying the list. But if you just if you know you’re
working with a shallow list that’s only one level, you can make a copy just
by using the List function in Python. That gives you a list. And OK. So now what we’re going to do is we
want to say, like, for example, the– and we can clean this up later. But for now just– COLTON OGDEN: I wonder, I wonder if,
even here, instead of deep copying, like using the hashes. Like the– sorry, I
didn’t mean to do that. –using the string hashes. Because all you’re doing– I mean, eventually we’ll do
the new algorithm, right? Like these– what we’re doing is we’re
just comparing these, ultimately, to what we’ve already
seen in the thing, right? And comparing it to board, but
we can have a hash at the board as well, right? To solve the board, I mean. RODRIGO DABOIN SANCHEZ: True. Yeah. Yeah. The only reason– the
only thing though is that we actually need to make a move. We need a– well, this is the
current state of the board, and so we want to see what
it looks like if we move it– COLTON OGDEN: Oh, yeah, you’re right. RODRIGO DABOIN SANCHEZ:
So the only way we can make a move is an actual list of lists. COLTON OGDEN: Unless you wrote a
function that could take the hash and do it on the hash. RODRIGO DABOIN SANCHEZ: Yeah, that would
be a little bit more work, I think. OK. So here, what we want to
do, is say, self.move up. And we’re going to
have this be the same. We’re passing in the
board’s move up function, and we’re passing in the location of
the empty spot to the move up function. So we’ll have this be here. All right. And let’s clean this up
later, but for now, let’s just do this for the other ones. Just because I want to have time
to mess around with the other ideas that we’ve had. And this one we’ll be moving
right, this one moving down, this one will be moving
left, and here we have 0, 1, 2, 3, and 0, 1, 2, 3 yeah. A loop might be better for this. OK. And so now, what we’ll
want to return is– this is going to be the children. So we’ll want to return potentially
a list of lists where here, we’re going to contain the board, position 0. COLTON OGDEN: Bokkengro, thank
you very much for the follow. I think I missed somebody else? Apologies. [INAUDIBLE],, thank you very
much for the follow as well. Much appreciated. RODRIGO DABOIN SANCHEZ: So I
didn’t talk about how I want to– how you want to– what’s it called I didn’t
talk much about how I want to represent the path list. And the way that I want to do it is have
it be with numbers like we did before. So 0 means up, 1 means right,
2 means down, and 3 means left. So that’s what I’m doing here. . I am returning as the
kind of like children, I am returning the current board, if
you move up or in whatever direction. The look– the current
location of the empty spot, if you go in whatever direction. And then what direction
you moved in as an integer. So here I’m saying, board if you move
up, empty location if you move up, and the fact that we moved up. COLTON OGDEN: Right. Because that’s the information
that represents the path we took to get to the actual thing. Because we’re going to
return that eventually. And how are you returning that? Is it just going to be a data
structure that just gives you the list of directions in order? Given the– RODRIGO DABOIN SANCHEZ: Yeah. It’s just a list. So then the path will look something
like, I don’t know, 0, , 3 0, up until it solved the thing. And we’ll see– we’re just
going to iterate over that list. And kind of how we
shuffled the board, we’re just going to loop through all those
results and refer to this dictionary up here. COLTON OGDEN: And it would be cool
if you got the end result of that. And then you have the starting
state of the board and then like a function that like
performed every step every like 200 millisecond or whatever,
so you can watch it. Oh, OK. That’s good. That’s cool. RODRIGO DABOIN SANCHEZ: OK. So now we know that successor’s is going
to take in a board and the location. So node at board and node at e_loc,
which I think is what we called it. Yes. And what is it? Why did it change colors here? I’m curious. Did I close down this list? Wait a minute. This list here closes that. And then this closes– interesting. I think I have some extra
brackets that I don’t need. OK. So now this is closing that. This is closing this. This is closing that. This is closing this. And then this is closing that. OK. That looks better. All right. So now we know that the
node is going to take in– that the successor sticks in a board
and the location, which in the node we have a board key and a location key. So now the child is going to be a
list containing a board, a location, and then the direction. So we want to check if we’ve
not seen the board in the child. So if child is 0, not in searched,
we will add that child to the fringe. So we will put, in the fringe,
a dictionary containing board. And then have this be
child, deposition 0. And then e_loc look is going
to be child at position 1. And we’re going to have path be– here’s what we’ve got to
remember the parents path. So it’s going to have to be the
path of the current node, plus child that index 2 in list form so that
we can concatenate these lists. So I’m doing essentially
something that looks like, if I have x is a list containing
1, 2, and 3, x + 4 will give me 1, 2, 3, 4. And so that’s how I’m going to
update the paths throughout the tree. So this might be like the current
node, and then the children is going to be either 0, 1, 2, 3. And so we’re going to add it
as a list to the existing path. And that’s what is going on here. All right. So now I believe this should
return to us the path to victory. So what we’ve got to do is
check in our main function, where we have currently
right here, if we press Shift where it’s going to solve. We want to store the path. So we’re going to potentially store
this in a variable called moves. And if we want to be really fancy we
can print something like, thinking, because we might take a few seconds. OK. So we’re going to have
the path right here. We know that we have to return
false when we want to stop– when we want to quit the program. So I’m going to preemptively have this
variable called persist, which is true, because we we’re going to want to
refresh the board with each move that we make. So we want to keep refreshing
such that we’re returning true. But once it’s done, we
want to quit the program. Actually, do we need to do this? I don’t think so. OK. Let’s just do this. Let’s say for m in moves,
so for move, in the moves that we need to make to win, we’re
going to refer to the moves dictionary that we have in the board, right here. COLTON OGDEN: Shout out to Brenda,
by the way, for joining the stream. A little late Brenda, you’re all right. But that’s OK. Like everyone is saying,
better late than never. Glad to have you with us. We’re getting to the
really cool stuff here in a second where we actually compare
running time of a sort of, I would say, naive implementation, just caching
prior states of the board in string– in lists and strings. And then memoizing them
for when David walked in. That was a much better word than
how I was trying to describe it. RODRIGO DABOIN SANCHEZ: So after we make
a move, will want to refresh the board. And then we actually have to
import from the time library. Important sleep. So that we can have the terminal
sleep for just a second, so we can actually see
the move being made. Right? And then it’ll finish doing this. And it’ll return refreshed. OK. Unless we missed something, let’s– oh, let’s make sure that the
shuffle magnitude isn’t too big. It’s just 10 right now. OK. Let’s see what happens if we run main. We automatically won. COLTON OGDEN: Nice. RODRIGO DABOIN SANCHEZ: OK. So here it is shuffled a little bit. Right? And if we press Shift, it’s thinking. COLTON OGDEN: So this was– so it’s
not, in this case, showing you a like, live figuring out the solution. This is, it knows the solution
and then it’s doing it. It’s actually doing the one
solution, that it found. RODRIGO DABOIN SANCHEZ: Right. We could also print the– we could print the solution list, but I
mean, it would just look like numbers. So the user wouldn’t really
necessarily know what it means. COLTON OGDEN: Right. Yeah. Yeah. Yeah. No, this is super cool. RODRIGO DABOIN SANCHEZ:
But you’ll see now that if we increase the shuffle
magnitude to say, even I don’t know, 20. COLTON OGDEN: Just to
get a little bit lengthy. I mean we can get rid
of the– probably the– RODRIGO DABOIN SANCHEZ: Oh, wow. That was quick. But I don’t think it shuffled that much. Some of the moves must have been– actually, it looks
almost like the same– the same moves. That was– COLTON OGDEN: That’s pretty funny. Yeah. RODRIGO DABOIN SANCHEZ: All right. COLTON OGDEN: This is
a little bit shuffled. RODRIGO DABOIN SANCHEZ: Yeah. So now like all of a sudden,
it’s thinking a bit longer. And we can start to play around
with changing the searched data structure from the list to something
a little bit faster to search. So something with constant-time
look up or near there. Because I mean, already you’re kind
of looking at this like, ah, man. COLTON OGDEN: It’s thinking. It’s thinking for a while. RODRIGO DABOIN SANCHEZ: OK. So while this thinks, do you want to– COLTON OGDEN: Yeah. Let’s do the memoized
solution because that sounds like it would be way faster. RODRIGO DABOIN SANCHEZ: So here we are. You we’re recommending
using a set, right? COLTON OGDEN: Yeah. Set. I mean, I originally
proposed dictionary, but somebody wrote and recommended set,
and that actually makes more sense, because all we’re doing is seeing
that it’s inside of a container. Right? And they all are unique just
per virtue of what they– I mean, I guess it doesn’t matter. In the dictionary it
would be the same way. But, set, sounds like it would be fine. RODRIGO DABOIN SANCHEZ:
We have found sets. COLTON OGDEN: But what we need to do
is we need to serialize the string, or I don’t know if
serializer is the right word, but we need it to take the
representation of the list, stringify it, and then use that as
the hash or the index into the set. And we need to make sure we preserve the
brackets in that string, just because the– like you could have a situation
in which you have maybe like– would this be the case necessarily? Yeah. Like 11, 12, versus like 11, 2, 3, 4. Like it doesn’t know if that’s 1,
12, 3, 4, or 11, 2, 3, 4, you know? So you do need to keep
the brackets in there to preserve ambiguity in
certain situations, I think. RODRIGO DABOIN SANCHEZ: Right. COLTON OGDEN: So let’s
definitely do that. RODRIGO DABOIN SANCHEZ: I was
just re-familiarizing myself with set notation. COLTON OGDEN: Oh, yeah. Yeah. A lot of the data structures will
have kind of a uniform interface. Just because like– I forget
what they call it– the Python, like they have a term for it. Like all the core like, dunder
functions they define that let you have similar behavior
across data structures. And you can like define them yourself. RODRIGO DABOIN SANCHEZ: OK. So let’s say we have a
set based on this list. If we want to add elements to it I think
it’s s.add, like if we wanted to add 4, and then we can say 4
in s, and that’s true. But 5 in s should be false. But if we do s.add 5. and then we do 5 in s. And then s.empty,
potentially, is a function? No. I don’t remember how to check. COLTON OGDEN: You could
just say s is equal to set. RODRIGO DABOIN SANCHEZ: No. I’m checking, like checking, if– COLTON OGDEN: Oh, if it is empty? RODRIGO DABOIN SANCHEZ:
But I don’t think we actually do this in the algorithm. COLTON OGDEN: No, I don’t think we do. No you’re only doing
that with the queue. Right? RODRIGO DABOIN SANCHEZ: And I believe
[INAUDIBLE] is empty. COLTON OGDEN: You can
also construct with some– there’s another way to do it, I think. RODRIGO DABOIN SANCHEZ:
OK so now we have search does a set, which means
here, instead of search.append we’ll have search.add and we’ll have
to change the representation of what we’re adding. COLTON OGDEN: Yeah. So node board is going to have to
be equal to the string or the– yeah, just the string of the– RODRIGO DABOIN SANCHEZ: I wonder– COLTON OGDEN:
–representation of the board. RODRIGO DABOIN SANCHEZ:
–if we have a list of lists like 1, 2, and then 3, 4 here. If we do str b. That sufficient. COLTON OGDEN: Yeah. That seems pretty good. RODRIGO DABOIN SANCHEZ: OK. COLTON OGDEN: You’re going to get some– the extra bytes no matter actually. Yeah. RODRIGO DABOIN SANCHEZ: Let
me make sure we’re not using– COLTON OGDEN: Yeah. So you could just construct– you could
just do a string of node board there. RODRIGO DABOIN SANCHEZ: Right here. COLTON OGDEN: Yeah. RODRIGO DABOIN SANCHEZ: Yeah. str node board. And that means the actual node
contains the board, which is good. In case it needs to
move it up and stuff. COLTON OGDEN: And I think you
need to do if stream node board not it search there too, right? Fuck, sorry, I keep doing that. I just cursed on stream. Sorry. RODRIGO DABOIN SANCHEZ: That’s OK. COLTON OGDEN: Bleep. Bleep. Sorry. That was inappropriate– that
was, yeah, that was a slip. RODRIGO DABOIN SANCHEZ: All right. So if node board has a string. It’s not in searched. And the same here. If the string format of the child
is not in searched, let’s see, is there anything– is there really anything
else we got to do here? I don’t think so. Board– we are– yeah. I don’t know. I think that’s it. Right? We just changed them all the
strings and put them in a set. COLTON OGDEN: I think so. RODRIGO DABOIN SANCHEZ: So let’s try– COLTON OGDEN: I’m curious
how much to think– how much– what was the number
that you set it to before when it had to think for a long time? RODRIGO DABOIN SANCHEZ: The
one that we did on stream? COLTON OGDEN: We just did, yeah. RODRIGO DABOIN SANCHEZ:
I haven’t changed it. It is at 20. COLTON OGDEN: It was 20 and
it was taking that long? RODRIGO DABOIN SANCHEZ: Yeah. Remember that the first
one was pretty quick, but it’s because I think the shuffle
was nicer, like closure to goal state. COLTON OGDEN: Wow. RODRIGO DABOIN SANCHEZ: So let’s– COLTON OGDEN: Is this
thinking right now? RODRIGO DABOIN SANCHEZ: No. I was like wait. Did we already win? But no, it’s 9, 11, 12. OK. Wow. OK. COLTON OGDEN: That was fast. Instantly. OK. So if we keep bumping it up. RODRIGO DABOIN SANCHEZ:
Let’s see if we do– COLTON OGDEN: So to be clear,
we just took the algorithm, the Breadth-first search algorithm,
and we changed it from being sort of I guess not linear– I guess linear search in
terms of looking at the data, but we brought it and made
it into a set, I guess. So this one’s slow. What was the number that
So it’s thinking. But I feel like it hasn’t yet reached
the number of the amount of time that it thought for the one that
was 20, when it was still a list. COLTON OGDEN: Mmm. Wait, what? RODRIGO DABOIN SANCHEZ: And
if you look at this board, it’s actually decently shuffled. Right? 5, 1, 7, 3– COLTON OGDEN: Oh, yeah. RODRIGO DABOIN SANCHEZ: 2, 10, 6, 4– 9, 14, 12, 8. So it’s not like– for the other one– COLTON OGDEN: It’s finished now though. RODRIGO DABOIN SANCHEZ:
It’s done now– yeah. COLTON OGDEN: That was
still reasonably fast. RODRIGO DABOIN SANCHEZ: And
that was 40 shuffled moves. Right? And so we can even just
see how long it takes to solve it to kind
of get a sense for how many moves it’s been having to make. COLTON OGDEN: So it’d
be cool to do like a– that was even then many moves, but
I mean it had to go through the tree and figure that out. RODRIGO DABOIN SANCHEZ: But
Breadth-first search always finds the shortest path to victory. COLTON OGDEN: Right. Yeah. RODRIGO DABOIN SANCHEZ: So I wonder if
we kick this up even to, I don’t know, 80? COLTON OGDEN: Oh, man, that’s
going to take a long time. I feel like it’d be cool to do like
a time before and after, you know, like to see. RODRIGO DABOIN SANCHEZ: True. COLTON OGDEN: Because it
feels like, I mean, 40, it solved it in a fraction
of the time it took– RODRIGO DABOIN SANCHEZ:
To solve it for 20. COLTON OGDEN: –to solve it for 20. Yeah. So I’m not sure what it would be, like,
how much time we’ve actually saved. But it’s clear that we’ve saved a lot. RODRIGO DABOIN SANCHEZ: Yeah. We’ve definitely saved some time. I mean, I guess for comparison, if
this, you know, doesn’t take forever, we can put it back to a list and see
that it basically never finishes. Right? COLTON OGDEN: Yeah. You could do like a 20 one. Spartangtr, thank you
very much for following. RODRIGO DABOIN SANCHEZ:
What have the people in the chat have been saying
while we’ve been doing this? COLTON OGDEN: There’s some
conversations going on amongst people. I haven’t been following– RODRIGO DABOIN SANCHEZ: Because this
is a perfect time to talk to the chat now, while this is thinking. COLTON OGDEN: Yeah. True. True. True. So we shouted out Brenda
for coming into the chat. Talking about Coursera courses. And then some folks left. Oh, Bhavik was saying, print the number
of the steps in the length of the path. So we could just– we can see actually, how
many times it’s doing it. Right? RODRIGO DABOIN SANCHEZ: True. COLTON OGDEN: Because that will help
us get a better idea of just how long the algorithm is too. RODRIGO DABOIN SANCHEZ: So clearly, even
with making this a string in the set, this is– 80 shuffled moves is still– COLTON OGDEN: It’s still a long time. RODRIGO DABOIN SANCHEZ: Yeah. COLTON OGDEN: Yeah. I’m sure we’re saving a tremendous
amount of memory though. RODRIGO DABOIN SANCHEZ: For sure. COLTON OGDEN: Because
like, if you were thinking about how much memory you needed to
store to write those lists of lists. RODRIGO DABOIN SANCHEZ: Yeah. COLTON OGDEN: That was probably a lot. RODRIGO DABOIN SANCHEZ: A
string would take less for sure. Yeah. Yeah. Yeah. Yeah. COLTON OGDEN: Well, a hash string. It’s not even a string that’s being
stored, it’s a hash of a string. Yeah. 0 of 1 versus 0 of n, clearly. Yeah. Not quite 0 of 1, but the actual– that’s the look up of the hashed string,
but the actual Breadth-first search is still going to take a long time. RODRIGO DABOIN SANCHEZ: Yeah. This might be a little
bit too much for it. COLTON OGDEN: Virani is saying,
“This is just some magic.” RODRIGO DABOIN SANCHEZ: It is cool
though, to like, just sit back and then watch it figure itself out right. Yeah? But yeah. COLTON OGDEN: It be cool if
you could have a counter here. You could keep refre– I mean, I guess I would slow the
application down a little bit. RODRIGO DABOIN SANCHEZ: Yeah. Like anything where it has to do with
printing while you’re in the loop, it’s going to really slow it down. That’s why I waited to do the searching
first, so it’s as quick as possible. And then do the refreshing the
screen after it’s figured it out. COLTON OGDEN: That make sense. RODRIGO DABOIN SANCHEZ:
Because I mean we could. We could have an updated counter. But then that would just slow it down. COLTON OGDEN: That would skew
the performance a little bit. Yeah. Mmm. RODRIGO DABOIN SANCHEZ:
But I mean, other than that, that’s the Game of
Fifteen that I had ready to present. COLTON OGDEN: Yeah. No, it’s great. It was cool. It was cool that we got
a chance to actually go into like algorithms and data structures
a little bit, make it a little bit more theoretical, and actually
apply it to something. I got to stretch it a little bit. But yeah, no, it was awesome. RODRIGO DABOIN SANCHEZ:
We can probably even see– COLTON OGDEN: Oh, yeah,
and they’re saying if you can push it to GitHub
they want to actually get a chance to tinker with it. RODRIGO DABOIN SANCHEZ: Oh, yeah. I actually already have
in my GitHub, the– let’s go on my profile. My GitHub is coderigo17. COLTON OGDEN: Good name. RODRIGO DABOIN SANCHEZ: I
already have the Game of Fifteen here as one of my repositories. COLTON OGDEN: What’s the link? I’ll type it in the chat. So that’s And this
is without the change though. Do you want to commit, or maybe
do a branch that has the memoized? I mean, I guess it’s easy enough
to make the change on the string. Yeah, you could just do that. RODRIGO DABOIN SANCHEZ: I mean, yeah. All I had to do was put
str in the two places? No, the three places. Oh, and we changed it to a set. So it’s not too bad. COLTON OGDEN: Yeah. That’s not bad at all. That’s something that if the
viewers are going to tinker with the data structures based– RODRIGO DABOIN SANCHEZ: If you
follow that does it get to it? COLTON OGDEN: It should, yeah. Let me check and make sure. RODRIGO DABOIN SANCHEZ: Yeah. There it is. COLTON OGDEN: Is a public? RODRIGO DABOIN SANCHEZ: Yeah. Everything that I do is public. COLTON OGDEN: Cool. Cool. RODRIGO DABOIN SANCHEZ: Yeah. COLTON OGDEN: Everything except
the private things that you do. RODRIGO DABOIN SANCHEZ: Well,
the only things that are private are things that I don’t own. COLTON OGDEN: It’s feel thinking, geez. RODRIGO DABOIN SANCHEZ: I don’t know. COLTON OGDEN: I mean, even
if it does finish, we wont know how many moves
it took, necessarily, without watching the whole thing. So yeah, that’s unfortunate. RODRIGO DABOIN SANCHEZ:
But if it does finish, the fact that the stream is
recorded, and then people can go back and watch it, means
that if you’re really curious, you can skip to whenever
this finishes thinking. And then actually count. But yeah. I don’t know. COLTON OGDEN: That was awesome. RODRIGO DABOIN SANCHEZ: Is there
anything else that people in the chat want to talk about
while we wait this out? Or if this takes too long,
we may just have to– COLTON OGDEN: Yeah. Well, we might cut it short here, you
know, if we don’t have any questions and it takes a bit longer. But that was awesome. Thanks for coming onto the
stream and putting this together. You know– RODRIGO DABOIN SANCHEZ: It was fun. COLTON OGDEN: It was cool. It was fun for me to participate in. I don’t do a lot of algorithmic
programming, at least more on academic side. So this felt like an academic
exercise, which was cool. And I liked the fact that we kind of
took a jump and dived a little bit more into analyzing the
performance of the application and figuring out ways to do that
using just simple data structures. Not even really going out– not
even changing the algorithm, just changing the fact
that we were using a set– RODRIGO DABOIN SANCHEZ: Right. COLTON OGDEN: –instead of
a list of lists of lists. Right? RODRIGO DABOIN SANCHEZ:
It would have been interesting to see how
much longer it takes using Depth-first search, or something. COLTON OGDEN: Yeah. RODRIGO DABOIN SANCHEZ: But,
you know, one thing at a time. I mean, I’m hoping to be back on the
stream at some point in the future. COLTON OGDEN: Yeah. RODRIGO DABOIN SANCHEZ: Classes
are about to start next week. So I don’t know. I don’t know what that
will look like for me. But you know, if I end up doing
something for one of my classes that I think is cool, I can kind
of take inspiration from that and do something in a similar spirit. COLTON OGDEN: Yeah. Let me know. And then we can get you back up here. And I know, that you’re
always game for, if we play some Super Nintendo or something. RODRIGO DABOIN SANCHEZ: Yeah. If there’s games. COLTON OGDEN: [INAUDIBLE] or NES because
you seem to be pretty into those. You were there for both of those. MKloppenburg saying, maybe an
algorithms stream or something. I mean, it would tie-in
to this a little bit. RODRIGO DABOIN SANCHEZ: Yeah. It would be. We could talk more
about different types. I’m actually about to
take algorithms classes. Because that’s what I’m mostly
interested in is an algorithms. I do enjoy coding. But the part of coding that I enjoy
isn’t like, looking up to syntax, and getting the syntax right. Right? It’s the actual problem solving portion. COLTON OGDEN: Yeah. That’s the most important thing. I mean there’s tremendous– I wish this actually was more of
a dramatic change in performance. I mean, it might be, ultimately. It might be a dramatic change in
performance, relatively speaking, and we just– it’s because
it’s just so much that we have been able to see it through. We have to time it and we’d have to see. Like the 10 versus the 20. RODRIGO DABOIN SANCHEZ: If someone in
the chat is, you know, very into this, they could time this using the
list version, which is in the repo. And then maybe– it won’t
be much trouble for me to add an additional push, having
it be set and on the string, and then compare the two afterwards. And let us know next time or something. Yeah. COLTON OGDEN: That would be awesome. MKloppenburg is saying, your
water looks like it’s boiling. Green screen magic? Maybe. RODRIGO DABOIN SANCHEZ: I only like
drinking 212 degree Fahrenheit water. COLTON OGDEN: Yeah. Boiling water. Bella_Kirs, our pleasure
Bella, thanks for tuning in. And to MKloppenburg and thank
you Bhavik for the kind words. Appreciate it. Virani, thank you. Yeah, a few minutes, says Bhavik
It’s taking a little bit of time. Tomorrow we’re going to
be taking a look at Ren– yeah. is it Render 50, which is a PDF
tool, or take source code files, and a lot of text editors don’t really
let you print, or expert, to PDF from your text editor. But what we needed was a way,
I mean David, especially, needed this for lecture, to
be able to print source code and be able to look at
it while giving lecture, have it nicely formatted on the page,
and a few other different cool things. And so just using Python, previously the
tool was written in PHP but we took it, we made it in Python,
and completely redid it. And so we’ll have a little
bit of look at that tomorrow. So we’re getting more into the
Python stuff, which is cool. Today was Python. Veronica will be on stream in the
near future with Python as well. And I’m sure we’ll have
other folks that are on stream for Python related content. RODRIGO DABOIN SANCHEZ: And
the stream tomorrow is at 3:00. Right? COLTON OGDEN: Oh, yeah. The stream tomorrow is at 3 PM. It’s not at 1:00. So 3:00 PM Eastern Standard time. I’ll push an event notifi– it’s already
on an event on the Facebook page, but I’ll post another
post to kind of pub it. And then it’ll go on
Reddit, Twitter, et cetera. You’ll see it. Tune in. It’s going to be good time. David is going to be hosting that one. David J Malan. Yeah. Going to be an excellent,
excellent time. RODRIGO DABOIN SANCHEZ: This would
be a dramatic time for it to finish. But I don’t know if it will. COLTON OGDEN: Yeah. I don’t know if it will either. It’s going to be a long time. RODRIGO DABOIN SANCHEZ: It’ll be
like the end of Inception, you know, where the coin is spinning,
or the totem is spinning and you don’t know if
it’s going to stop. And they end it. COLTON OGDEN: Well, it looks like
we have a little bit of content that we can keep going off of. So Bhavik says, you Ubuntu looks dope. Oh, MKloppenburg, you’re right. You’re right. I don’t think we officially
ever confirmed the time at 3:00, and so I kept it as a draft. But it’ll go up tonight for sure. And then the– I guess when I make it
an event, I’ll post it to the Facebook group
and all that stuff. And then I’ll also start creating
events for next week streams. We have a few lined up
for next week as well. That’s going to be a good time. Kareem, next week’s going to Flask. I’m going to CSS next week. Dave and I are going to
do code reviews next week. Minesweeper– it’s going to
be a good week next week. Yeah. It’ll be a good time. I was going to look at– what was this? Bhavik was saying, you’re
a Ubuntu who looks dope. What desktop are you using? RODRIGO DABOIN SANCHEZ:
As in the Ubuntu version? COLTON OGDEN: Yes. I guess the Ubuntu, and if you have a
graphical window manager or whatnot. Like what you’re using for that? RODRIGO DABOIN SANCHEZ:
I’m on 18.10 Ubuntu. And I’m actually, ironically enough,
I’m not like a computer person. Right? So like– COLTON OGDEN: That’s OK. A lot of people have this, I
think, stereotyped perception that all CS people are also
like computer technicians. RODRIGO DABOIN SANCHEZ: It’s definitely
something that I want to improve on. COLTON OGDEN: Yeah. I think it’s definitely valuable. I mean, like, computer
parts aren’t really hard at all to understand, or to use. But I mean, like
troubleshooting hardware issues, I think that’s something that takes
a lot of experience and training and stuff, and so CS people usually
do are you familiar with the software side, the hardware side
is not really something they necessarily have to interact with. RODRIGO DABOIN SANCHEZ: But I do know
that it’s 18.10 and I had to configure my bash rc to have it look the way–
that my terminal look the way it does. But other than that, yeah,
I’m not too knowledgeable. But– COLTON OGDEN: That’s all right. No one is going to hold
you accountable for that. I don’t think. This is an awesome stream. Appreciate it again. Like part of me wants
to keep trying to– RODRIGO DABOIN SANCHEZ: I know. COLTON OGDEN: –prolong it just
so we can see if it finishes. RODRIGO DABOIN SANCHEZ: It would be
funny if as soon as we cut the stream it ends. Right? COLTON OGDEN: Yeah. That would be pretty funny. Yeah. Asli, our pleasure. Ronnie was excited to see it finished. Ronnie you should take
it and run it yourself. Clone off of GitHub and try it out. And then see, maybe time it, use the
time function at the command line, or whatever, on a mac or a Linux. I’m not sure what it is PC. RODRIGO DABOIN SANCHEZ:
The current version is still using a list for the searched. COLTON OGDEN: Right. Yeah, so you’d have to
switch it to the set version in order to see what that
performance difference would be. Virani says, too bad it’s too late. Maybe I’ll watch the VOD,
referring it to tomorrow’s stream. Yeah, definitely watch the VOD. All these videos go up on to YouTube. I’m going to very tragically transition
as back to the full shot here. We’re going to say that
maybe this won’t actually finish by the time the stream is over. Ah, geez. BeastKris, “turned in too late today.” Don’t worry, the video is
going to be on YouTube. So it’ll be on YouTube
within a couple hours. You’ll be able to see, watch it in
its entirety as all of our videos are. And what I was going to say was if
you are watching this on YouTube, you can tune in to CS50. It’s Twitch channel on Every week we have programming
videos from scratch. I do game programming. Rodrigo came in today to do some Python. David’s going to come in tomorrow
to also show us some Python stuff. And more I guess to talk about making
applications using pre-built software, because we did use a lot
libraries for that application. But yeah, a pleasure as always. Thanks everybody who tuned in today. We’ll catch you tomorrow at 3 PM Eastern
Standard time with David for render 50 so thanks again Rodrigo
you for coming in today. RODRIGO DABOIN SANCHEZ:
Thank you for having me. COLTON OGDEN: Much appreciated. We will see all of you later. Have a good rest of your day.


  1. Emrul Zawad January 25, 2019 at 3:51 am

    ๐Ÿ˜ฎ wants more on AI

  2. Emrul Zawad January 25, 2019 at 3:52 am

    Colton, Could you able to do one twitch on neural networks?

  3. ibra him January 25, 2019 at 3:54 am

    great work thanks ๐Ÿ˜ƒ

  4. Christer Nilsson February 10, 2019 at 11:06 pm

    Some comments on the code:
    Most important is the use of A* to speed up the solver.

  5. Charbel Sarkis February 14, 2019 at 7:31 pm

    Mathematica? That's what we learn in my university.

  6. Limitless 1 October 15, 2019 at 8:53 pm

    Awesome stream
    Thanks from uploading it ๐Ÿ™‚

Leave a Comment

Your email address will not be published. Required fields are marked *