Four Semesters of Computer Science in 5 Hours, Part 2 Graphs Solution

[00:00:00]
>> Brian Holt: Hopefully, you had some time traversing some graphs. We're gonna talk about now how to do it.
>> Brian Holt: We wanna go to the exercise.
>> Brian Holt: Okay, so,
>> Brian Holt: Looking at this.
>> Brian Holt: Yeah, I will implement this very functionally in nature, just again, that's how my brain tends to break down things.

[00:00:34] I don't know if it's Stockholm syndrome or what, but after you're doing things and so many times in a certain way, it's just kind of keep doing it that way. But you could definitely solve this in a less functional style. I was struggling with how to show people how to do these sorts of things, like should I break it down to a more ideative approach.

[00:00:50] And I always land back on is like, I think this is a useful way to show people how to write code, even if it's not necessarily the central focus. You'll kind of begin to be more exposed to these sorts of things, so good and bad, I am sure.

[00:01:05] It makes it a little bit more cognitive load to understand it.
>> Brian Holt: So first thing I'm gonna do is I'm going to construct my queue. So let queue equal, and I'm gonna just put my ID as the first thing in the queue, okay? And then I'm gonna create a new set.

[00:01:37] So you could just do this totally with just a plain old JavaScript object, that's totally fine. I'm gonna do with a set, because this is what sets were created for, so might as well use it. A set, one you should go check out version one of this course.

[00:01:52] I feel like I haven't said that enough, so I'm gonna say it again. I talk all about what sets are, but the short version is that they are business like this amorphous cloud of data that you throw things into and you ask later, does this contain this? Like a Bloom filter but this will definitely give you a yes or no answer, definitively yes or no.

[00:02:11] So what I'm gonna do is I'm gonna throw IDs in here that I've seen before, so I do not process them again, right? And then I'm going to keep an object called jobs, and I'm just gonna make that a plain old JavaScript object. You could do this with a map, but I'm not going to.

[00:02:28] I'll put it that way, you could. So what I'm gonna do here is I'm gonna do a for loop. So let i equal 0, and then i is going to be less than or equal to degrees of separation I++. I think I set up here to count yourself.

[00:03:02] Yes, count initial IDs own job in the title as well. So probably should have said that out loud. Now I am saying it out loud, but hopefully you get it up there. So that's why I'm able to go up. So I'm gonna start at 0 and then go 2, 4.

[00:03:17] It's cuz I'm gonna count myself. I am not separated from myself, as far as I know, that's impossible. So we're gonna start with that. And we're gonna up to that degree of separation, okay? And we're gonna do some functional foo on this and see what that looks like.

[00:03:35] So q is going to equal to q, the first thing we're gonna do is adopt filter. So this is like the last one that I haven't talked about, filter is I'm gonna apply a function to everything in a array. Things that are true stay in the array and things that are returned false are removed from the array, right?

[00:03:56] Make sense? So the first thing I'm gonna do is I'm gonna remove everything that I've seen before. So filter ID and return things that have not been seen before.
>> Brian Holt: Right?
>> Brian Holt: And this is an implicit return in JavaScript. So this is the same as saying,
>> Brian Holt: Right?

[00:04:27]
>> Brian Holt: So this is just the shorthand for that.
>> Brian Holt: It's a little less dense, that's why I like that. Okay, then I wanna transform every item in this list from the ID to the actual user object, right? So I'm gonna do a .map and do getUser. Some people have a hard time kind of parsing that, so just to show you what that looks like, it would be the same as doing ID, return ID, right?

[00:05:02] So it would be taking that parameter and feeding it into getUser, right, which is the same as doing that, right? Because you are just taking a parameter and passing it in, so you don't have to create this extraneous function. How do we feel about that, is that okay?

[00:05:19] So it's gonna take a list of IDs, like one, two, three, four, and then it's gonna be afterwards an array of user object one, user object two, user object three. So that's what's happening here. We okay with that?
>> Brian Holt: Okay.
>> Brian Holt: Then we'll gonna do here another map.

[00:05:40]
>> Brian Holt: So I'm gonna have user objects here now.
>> Brian Holt: So what I'm gonna do here, I'm think I'm gonna say jobs user.title equals jobs user.title. So, [COUGH] jobs, this is everything that I've seen before, right? If I've never seen this user's title before, I'm gonna need to add it to my object, right?

[00:06:13] And if I have seen it before, then I need to increase it by one, right? So if I've seen that before, then I just want to add one, and if not then I want to make it one, right? You could do this with an if statement. I'm gonna do it with what's called a turn array.

[00:06:28] Hopefully, you've seen these before, but if not, it's basically a compressed if statement. So if I've seen it before, then add one, let's just make this a little bit smaller. And if I haven't seen it before, then do just one. So again, turn your smushed together if statements.

[00:06:51] This asks a question, does this exist? If true, then it's the first thing, if it's false it's the second thing. So the first thing here, if it's true, if it does exist, then add one. And if it doesn't exist, then it is one.
>> Brian Holt: It's all dense, but cool.

[00:07:13]
>> Brian Holt: Next we're going to say seen.add, user.id, right? Because we don't want to process this user.id ever again. We processed it once and now it's done. And then we're going to return user.
>> Brian Holt: I know someone is out there who's very functionally inclined saying you're doing side effects on a map, and you should be doing that, in that voice actually.

[00:07:42] Which is true, typically inside of maps you don't wanna do side effects which is basically modifying state of the outside world, right, I'm modifying jobs. I'm doing all that, and then I'm just returning user at the end. The reason why I'm doing this versus doing it for each, is four h does not return an array at the end and map does.

[00:08:02] So I can keep doing my functional stuff below here, whereas if I did four h I would have to stop and restart again, and I didn't wanna do that. So that's why for whatever functional person out there is scoffing at me, you can keep scoffing but I don't care doesn't hurt.

[00:08:20] So now I've done that. Now I've added it to my jobs object. And now what I wanna do is I wanna transform this from this map of numbers to the map of their connections, right? So I have a bunch of user objects that have a bunch of connections.

[00:08:47] I've already processed all the users in that particular queue, and I want to go and do the next level down, right? So what I'm gonna do is I'm going to get the users.
>> Brian Holt: And then I'm going to transform that into the user.connections.
>> Brian Holt: Right? But now I have an array of arrays, which I don't really want.

[00:09:17] I just want a flat array, does that make sense? Cuz whatever you return here is what gets put in the array, and right now it's just an array of arrays and that's not what I want. So ideally, we'd wanna be able to call flatten here which doesn't exist yet, cuz it's gonna call smush and I'm not bitter.

[00:09:33] It's not like I've already talked about this today. I'm gonna imprint, flat would be perfect cuz that would work exactly like I would want it to, but we're just gonna do it in terms of reduce because that works. So you're gonna have acc and users. And I'm going to return acc.concat users.

[00:09:57]
>> Brian Holt: And that should work. I don't think you even need the seed, nope, you shouldn't. So,
>> Brian Holt: Cool. Questions about that?
>> Brian Holt: So now after we've done all of that, queue will now be the next iterations amount of user connections, right? So thinking about that, we're gonna start off with just my ID, right?

[00:10:27] So it's gonna filter anything out it's seen before, which is nothing. It's never seen anything before. It's gonna turn my connection, so let's just pretend it's 30 I think is the first one down here, right, so it's user 30. So this is just going to be an array of 30.

[00:10:41] Let's just put a comment there, so you can see it, right? Here, it will do nothing because it's never seen anything, so do nothing. Now it's going to be ID 30, title blah, right? So it's gonna be that object.
>> Brian Holt: Here, it's still gonna be the same array as before, but there were side effects, right?

[00:11:09] So we did a bunch of stuff off on the side
>> Brian Holt: Okay, now this is going to be an array of arrays of all of it's various connections, right? And then what we're going to get back here is just 1, 2, 3, 4, right? So it's going to flatten that array down to one flat array of all of user 30's connections.

[00:11:38] We follow kind of the progression there? Does that make sense? So again, you could totally implement this without using mat filter and reduce. But to me, I find this preferable code. But you can disagree with me and we'll just fight about it, and that's okay. So now it's going to go do this for all the degrees of separation.

[00:12:02] After this four loop completes, I will have this jobs object that's just going to be, the key will be in various amounts of jobs and the numbers will be how many times I saw the jobs. So now I just need to get the one that was seen the most, right?

[00:12:20] Good? Good so far? Okay, so what I'm gonna do down here is more functional bullshit, I'm just kidding, functional programming
>> Brian Holt: So object.keys, all right, so let's start here. Jobs is going to be, the thing that we're gonna get out of this is jobs that's the important thing.

[00:12:54] Jobs is going to be this object, where it's gonna have like dev is gonna be like 50 and designer, it's going to be like 30, right? Etcetera, etcetera, etcetera. Now we need to pull out of this, the one that was seeing the most amounts of times, right? The job title, that was seeing the most amount of times.

[00:13:20] So object key is going to give me back all of these, right, as an array. So now I have this array of job titles. And what I want to do is I want to return,
>> Brian Holt: First, what I'm gonna do here is job and I'm going to return tupple, a tupple, that's the name of the data structure.

[00:13:44] It's just like an array of two, right? Apparently, it's pronounce tupple I was told, I don't care. I'm gonna hold on to tupple till I die, and I will fight you about it.
>> Brian Holt: So what I want is I want an array of two. I wanna have both the job title and how many times I saw it, right?

[00:14:04] So it's gonna be job and then job's job, [LAUGH] right? So this is going to be, using our example above, it's going to be dev50, right? So now I can sort these based on which one I saw the most amount of times, right? So I'm kind of creating these intermediary data structures.

[00:14:27]
>> Brian Holt: Now I'm just gonna run a really dumb sorting function, so a and b.
>> Brian Holt: And indent that a little bit. So I'm just gonna say, If a of one, cuz one a of one, right, is going to be 50, right? So we're comparing the numbers versus each other, that's what we care about.

[00:14:49] Is greater than b of one, then return negative one.
>> Speaker 2: So my question is, why were you doing the object.keys instead of object.entries?
>> Brian Holt: That's for-in loop, the answer is it probably both works. I am just so used to using object.keys that,
>> Brian Holt: Yeah, today I learned. I think you could use either one of them.

[00:15:25] It looks like here, I'm gonna guess that object.keys works. Yeah, this is ES 2017. So object keys works a little bit sooner, but that's whatever, right? They both work. So thanks for teaching me something.
>> Brian Holt: Cool, so sort. I think you've probably all seen this .sort method before.

[00:15:52] It's been in JavaScript since forever. Sometimes, if you need to you can tell it how to sort things. So I'm telling it to sort based on the first item in these arrays, because it's going to be a bunch of these pairs. This is gonna be 1, and this is just how you write them.

[00:16:10] If a is greater than you return negative one. If b is greater,
>> Brian Holt: Then you return a positive number. It actually doesn't matter. Negative number, a positive number, and then if they are equal then you return zero.
>> Brian Holt: It's important that you do it this way, otherwise things are going to get way out of order.

[00:16:35] And it's also important that you return zero or it's gonna be less effective than it could have been, less efficient rather, okay? So at the end of this, I'm gonna have a list of these like pairs of items, right? And the top one is going to be the one that was seen the most, right?

[00:16:54] So I wanna take the zero element, which is going to be dev50, right? And I wanna take the zero element of that, which is going to be 0, right? So if I return that, it's going to give back dev, which is ultimately what we wanted. How do we feel about that?

[00:17:14] Did we follow kind of like the progression of steps that we got there? So for some of you this might be like an entirely new paradigm of programming this way. I'll tell you this is how I try and write most of my code. But you could, go ahead.

[00:17:31]
>> Speaker 3: Is there a reason you didn't just do a reduce on that and grab whatever's the biggest value?
>> Brian Holt: You could totally put this in terms of reduce as well, yeah. They'd be roughly the same efficiency as well. But I applaud that you're thinking like that, I think that's great.

[00:17:53]
>> Brian Holt: So I think this should work as is, let's give it a shot.
>> Brian Holt: And cool, you should be seeing that. So let's go ahead and give it the extra cut at once and see what happens.
>> Brian Holt: And it gets every user within a seven degrees separation.
>> Brian Holt: Questions about this?

[00:18:30]
>> Brian Holt: Or is your brain kind of melting out one side of the ear? Okay, cool, me too. [LAUGH] Let's bond together and get through this. [LAUGH] I thought it was funny that the most common job title of the network Geological Engineer. That's very realistic. This is actually modeled after real world things, just kidding.

[00:18:52] Okay, so any questions about graphs in general? Conceptually, do we follow what's kind of happening here that we're just kind of going down one layer each time until we reach our desired degree of separation and then just kind of racking those up? That's the important thing that I really want you to take away from this.