GAME OF FIFTEEN IN PYTHON FROM SCRATCH - CS50 on Twitch、EP.28 (GAME OF FIFTEEN IN PYTHON FROM SCRATCH - CS50 on Twitch, EP. 28)

字幕表動画を再生する

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 Board.py.
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 board.py, main.py, 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 images.google.com.
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 Board.py,
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 board@--
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, py.mean.py 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 draw.CS50.io.
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, youtube.com/cs50 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 you can have s2 just be an empty set.
Right?
COLTON OGDEN: Yeah.
RODRIGO DABOIN SANCHEZ: OK.
COLTON OGDEN: [INAUDIBLE] .
RODRIGO DABOIN SANCHEZ: [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 you used on this one?
RODRIGO DABOIN SANCHEZ: Here it's 40.
COLTON OGDEN: OK.
RODRIGO DABOIN SANCHEZ: 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 GitHub.com 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 twitch.tv/CS50tv.
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.