Coding Challenge #68: Breadth-First Search Part 1
ฝัง
- เผยแพร่เมื่อ 22 พ.ค. 2024
- In this two part challenge, I implement the Breadth-First Search algorithm in JavaScript. My demo application is "6 Degrees of Kevin Bacon" (finding the closest relationship between Kevin Bacon and another actor). Code: thecodingtrain.com/challenges...
🕹️ p5.js Web Editor Sketch: editor.p5js.org/codingtrain/s...
Other Parts of this Challenge:
📺 Breadth-First Search Part 2: • Coding Challenge #68: ...
🎥 Previous video: • Coding Challenge #67: ...
🎥 Next video: • Coding Challenge #69: ...
🎥 All videos: • Coding Challenges
References:
📕 The Nature of Code Part 2 (Spring 2017) - Intelligence and Learning: github.com/shiffman/NOC-S17-2...
📕 Nature of Code: github.com/nature-of-code/noc...
🥓 The Oracle of Bacon: oracleofbacon.org/
🗄 Breadth-First Search on Wikipedia: en.wikipedia.org/wiki/Breadth...
📘 Grokking Algorithms: www.manning.com/books/grokkin...
Videos:
🚂 My Video on Associative Arrays: • 5.2: Associative Array...
🚂 My Video on Prototypes: • 9.19: Prototypes in Ja...
🔴 Coding Train Live 88: • Live Stream #88: Sessi...
Related Coding Challenges:
🚂 #65 Binary Tree: • Coding Challenge #65.1...
🚂 #98 Quadtree: • Coding Challenge #98.1...
Timestamps:
0:00 Introducing today's topic: Breadth First Search
2:42 6 Degrees of Bacon
4:45 Node object
6:40 Let's Code!
8:02 Graph Object
9:44 Read the data
12:28 Attach a method to the graph object using prototype
16:52 Add an edges function
17:38 Determine whether actor node already exists
Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound
🚂 Website: thecodingtrain.com/
👾 Share Your Creation! thecodingtrain.com/guides/pas...
🚩 Suggest Topics: github.com/CodingTrain/Sugges...
💡 GitHub: github.com/CodingTrain
💬 Discord: thecodingtrain.com/discord
💖 Membership: th-cam.com/users/thecodingtrainjoin
🛒 Store: standard.tv/codingtrain
🖋️ Twitter: / thecodingtrain
📸 Instagram: / the.coding.train
🎥 Coding Challenges: • Coding Challenges
🎥 Intro to Programming: • Start learning here!
🔗 p5.js: p5js.org
🔗 p5.js Web Editor: editor.p5js.org/
🔗 Processing: processing.org
📄 Code of Conduct: github.com/CodingTrain/Code-o...
This description was auto-generated. If you see a problem, please open an issue: github.com/CodingTrain/thecod...
#breadthfirstsearchalgorithm #sixdegreesofkevinbacon #javascript #p5js
![MOBYE - มีใจทำไมไม่จีบ (ASAP) [Official MV]](http://i.ytimg.com/vi/dCOdz92FU18/mqdefault.jpg)
Just a random thank you... Both your enthusiasm & teaching methodology make a world of difference to learning many of these concepts. It truly is addictive...
You're such a great teacher! You make learning this stuff interesting. A+
You are an artist. Best artist :P
You're so excited, this is great! (also paused the video and spent 5 minutes playing on oracle of bacon. I don't know why)
Adderall jk
Google also has this "easter egg" where you can search for "Bacon number" followed by the actor's name for similar results.
This was the most entertaining video I've ever watched
you're not stiffman Daniel you are stuff man
I'm a great fan of you man
DealerMark Bikes haha we all are fans of "stuff man" ☺️
Great video, super helpful, thank you!
These videos are awesome. Thank you.
Amazing, Mainting an instance variable for visited nodes was a good idea, it prevents key errors in hash maps, Great Thanks!
For anyone who's interested, here is some benchmarks of Breadth-First Search implemented in a few languages: (averages over a few runs)
nodejs (v6.10.3) : 0m0.065s
c++ (clang version 5.0.0) : 0m0.003s
go (go1.9.1) : 0m0.002s
Hey Daniel!
Thank for these amazing videos. I love your enthusiasm. I need that in order to learn. Almost done with my CS degree but its great to see these implementations. I just bought the book Grokking Algorithms that you mentioned. Cannot wait to read it. Thank you for these videos. I'm excited to watch the rest of the series!
Regards,
Jose Ortiz
Glad to hear!
You'll be disappointed, trust me pal.
Again, at 18:30, you need to put line 27 inside the condition block. Because Graph.addNode does two things, push the node to nodes and add it to the set. While the latter makes no difference if the node is added twice, the former will create duplicates within the nodes array.
great content as always!
I love Your Videos A lot specially coz of regular uploads!!
This is great!! Thank you!
Can you do a video on dynamic programming?
You found a bug I see.
This is amazing-thank you!
great teaching
Love these videos! By the way, what color theme do you use for your Atom editor? It is very pleasing to the eye holes.
I think it's the default theme
I love watching these even though I'm absolutely terrible at programming, most if not all of it is jibberish to me :D
Right there with you Dan P
I want to learn so bad but I'm struggling to find the motivation because I'm so bad at it atm lol
well, you might try other languages then javascript, some people like python, some like ruby, some like C, i like something called livecode.
Hey you could start learning to program! It's an amazing world. I saw you said you need motivation, I used to be like you a few years ago! If you need help or advice let me know :)
saw that you had some C videos, i like that as a old turbo C programmer :-)
wish a was better in english and not a boring old guy, making tutorial in programming looks like a great thing to do
My copy of Grokking Algorithms is in the mail, looking forward to it!
I recently started using js's object oriented programming features and i like it. You can do sth like this:
class Node {
constructor(something){
this.value = something;
}
}
node = new Node(value)
Hi. Just want to say I love you and do you do live streams? If so when and where? I would love to watch you live but I don't get any notifications and stuff so please help me out anyone?
At 19:16, you can simply write : if (!actorNode) { ... } It is not only the JavaScript-way of testing "truthy" values, it prevents the case where null !== undefined. (Also, === is preferred to == because JavaScript's loose type syntax (ex: 0 == '' is true, but 0 === '' is false)
I think the graph.addNode(actorNode) should also go inside the if (actorNode == undefined) condition, otherwise you are pushing the actor node
multiple times in your this.nodes array in graph object.
can u maybe in your intellegence and learing or as a coding challenge do a simulation of an ecosystem? maybe with a genetic algorithm or some kind of other algorithm i dont know yet, that u can teach in the video :) also thanks for all the things i learned through you
Is there an updated version of this in 2021?
which application you are using so that i can start immediately pls help
common use some ES6 features. I want to see class {} notation!
Can you solve ICPC ASIA World Final 2014 D(Game Stategy) problem, please make video on that
I don't know if this has happened before but this is the first time I've noticed it. Your hair slightly transparent and it keeps putting me off xD
Jacob JG lol. His green screen skills are so much better than mine.....but now it's all I can see too...
what have you done...
searches himself for k.bacon. lolol, you are fun!
What is the name of the book and the author?
var movies = data.movies; is coming out as null/undefined for me. Am I missing something?
Can anyone help me with the json file? Do I have to type it watching the video? That one is missing from the github repo
In sketch.js: graph.addNode should be inside the if
Hey, I don't know if you respond to comments on old videos, but I had some confusion about why you did the movies as their own nodes rather than the edges between actors. That's the way I thought it would be done and I'm confused why you chose to have movies be their own nodes. Thanks!
This is a great question and I think my decisions here were somewhat arbitrary just to demonstrate the idea of BFS.
The Coding Train okay, thanks for the reply! Your videos are a big part of what made me want to go into computer science and I really appreciate it
@17:53 the Time complexity jumps n^2. Any other ways to do this?/
Actually reading from hash table is O(1) unless there are collisions. So time complexity is still in order of n not n^2 .
hey can you please make some great "create js" tutorials as you made p5.js tutorials (those videos is very helpful and awesome)
Subhojit Mondal that's a great idea :)
Breath-first VS. Death-first
I guess this stuff has already been fixed but you don't need to add the actor node to the graph if it's returned by getNode. Also calling the argument in getNode 'actor' is a bit ugly as that object can be used to store anything, not just actors. Something like 'key' would make more sense.
Any links to the code and the .json file so I can code along ?
Everything is here! thecodingtrain.com/challenges/68-breadth-first-search
This is how I visualize a graph. Free to use: editor.p5js.org/tvm389/sketches/BkZdUgSgE
hm still no bacon links tho
What did you study?
He's a professor at the Interactive Telecommunications Program at NYU's Tisch School of the Arts :)
Oh, don't mention him "Computer Science" ;) haha
loadJSON() does not work on file protocol
@Jose Garza Yes .. loadJSON() works on live-server.. You can install the npm package
you picked quite complicated example with movies and actors. Would be much easier to explain BFS with a simpler nodes ( say a subway stations ) IMHO. Still like your videos, and thanks for your time recording them!
1:08 did Alice just move?
claire as well, just shortly after.
where I can find file kevinbacon.json ?
You don't even need to have the file if you use:
data = loadJSON("raw.githubusercontent.com/CodingTrain/website/master/CodingChallenges/CC_068_BFS_kevin_bacon/kevinbacon.json")
github.com/nature-of-code/NOC-S17-2-Intelligence-Learning/blob/master/week1-graphs/P2_six_degrees_kevin_bacon/bacon.json
Man you look like the Professor from Money Heist !
Can you please provide the movies json
Everything should be here! If something is missing please file a github issue. thecodingtrain.com/CodingChallenges/068.1-bfs-kevin-bacon.html github.com/CodingTrain/website/issues
@@TheCodingTrain its saying page not found now
@@warhammer48 the website changed! It's here now: thecodingtrain.com/challenges/68-breadth-first-search
google also gives you bacon numbers :D
Does this man know how much effect he make to peopel lives ?
coding challenge is to do it in vanilla js
you remind me of mat from achievement hunter XD
it's gif.
little cup of tea? no, i carry my used coffee and espresso grains out in 4lb tubs. definitely get good coffee, i don't believe in cheap or dark. i like the full bean as lightly cooked as possible, has the most caffeine. and quality bean. i like butterflies from my espresso. cheap coffee is always a waste of money. and i learned what it's like to almost die from not enough sugar they had to give me a tube of sugar paste to get my heart normal, i don't buy zero sugar anything anymore. lots of sugar in my coffee, low sugar cults are the most dangerous thing i've seen now. i buy monsters and other stuff not just for vitamin but even more so for the sugar, we really need that stuff. much more so with protein and exercise said my extra protein is why i needed more sugar. takes sugar to process protein too. coffee is a very magical bean. and a $350 7 stage purifier with reverse osmosis and add 7 minerals back in. it's what you see everyone try, buying mineral packets for espresso water, mines what they are really after tho, xD pulls out the chlorine and fluoride with carbon filtering from coconut shell and at least 600+ more chemicals. sometimes tea, more often coffee and espresso.
Kalman filter
Shiffman => use some webpack and es6 style of classes or typescript etc ... it's more fun than raw vanilla js
kevinjason.bcon
The inventor of the gif format himself pronounces it jif, so it's jif
no. if everyone says it as gif, then it is gif.
like how americans and brits say tomato. in america the way to say it is different from in england, regardless of how it was originally said
This video came out on the day I handed in an assignment of which did a degrees of separation for wikipedia XD
Shameless promotion :p > github.com/Hobgoblin101/Wiki-Web/releases/tag/v1.0.0
Lol you forgot the correct method declaration on node.js:9 @ 16:44 but when you switched back to the file @ 18:37 it was magically fixed! Nice try Mister Coding Train ( ;
The "G" in Gif is soft. It's pronounced like the peanut butter.
Stop trying to make it .jif, it's not going to happen!
I really dont think using that platform is helpful. You spend time in things not related to the problem . Causing people with less context to have a bunch of really not useful information, and making them to lose the focus.
You shoud do this in only one javascript file where all the pieces are together and are easy to relate.
my 2 cents.
Kalman filter
Kalman filter
Kalman filter