Loved the generalizing of the solution at the end there, but I wonder, what if we adjust the number of people rather raft can carry? That expands the number of movement vectors we get so I can imagine that we would get different solutions. Is there any point at which we would need more rafts, or does that stop once one extra person can get on?
Thanks galacticfish! Oooh, bigger rafts is an interesting variation to try. I think it actually wouldn't be too hard to test - I'd just have to add more legal moves to my array, which right now is (1,0,1), (2,0,1), (0,1,1), (0,2,1), (1,1,1). Tetrachart brings up an interesting point though, that 2 Dinos could eat a Santa while on the raft haha My guess is, once we have a raft that can hold 4 creatures, you can just shimmy along the diagonal (2D + 2S cross, 1D + 1S come back, repeat over and over)
Adding capacity should just change the previous constant in n - 2 rafts yeah? as in n - x where n is amount of santas and x is raft carry capacity. Well kinda. I'm not enough of a math kid to add a stipulation that the sum must be at least 1, but other than that it should be correct. Any added capacity should just push the middle gap problem one step further away.
@@carykh Could possibly change the nom nom condition from strictly greater than to greater than or equal to and then to greater than or equal to Santas - 1. I do fear, however, that the same patterns will arise on the edge cases (where size is 1 off nom nom threshold). And I assume there is a way to procedurally calculate moves rather than hardcoding them to an array. Another expansion could be of adding like a rock-paper-scissors equivalent (idk the specifics), but that’ll get rid of the 3 dimensions. Perhaps have a graph of graphs and at some point (if you delve into 5 or 6 dimensions) just display the result(s) instead. Love this graph theory approach!
Pretty neat visualisation, would be a fun project (for me, or someone else) to write a solver using these heuristics, given an 'n' input, output an array of vectors of each step Also, I guess you chose this version of the puzzle (or, TED-Ed) because its the easier one to visualize and reason about, while the other versions are more nuanced, like the one with the farmer, wolf, goat, and cabbage, or the one with a whole family that is super weird
Thanks PinkorCyan! Yeah, I did feel lucky when I realized this version of the puzzle only has 3 dimensions, when many other variations could easily have 5, 10, 15. Interestingly, the wolf+goat+cabbage one (which is arguably more well-known) actually has a 3D representation I found on Wikipedia! (but it's designed slightly differently)
1:32 Ha, I knew you would slip and call em Yoshi's at least once! Cool Yoshi models btw, honestly clicked for the Yoshi, wondering what it was doing here in a puzzle video
So great! I feel like I'm actually understanding the world in extra dimensions. P.S. I still show your scale of the universe to my students every term.
Thanks Ben! Oh wow, it's really cool to hear that my Scale of Universe is still playing a small part in students' education 😃 (One of these days the students themselves will be younger than the website, aaaaaa)
@@flyingduck91 agreed, but it *feels* like extra dimensions, probably because as he stated in the video, we're used to looking at the problem from only one particular perspective, not all at once.
Love this visualization, that it generalizes to an arbitrary number of dinos, santas, and rafts, and that you can be confident you didn't miss any alternate solutions! :) Fantastic video!
I've been working on a similar thing, making data visualizations for the puzzle "signpost". the terminology of graph types that you mentioned will definitely be useful to me. thanks!
would never think to see so many tautologies of the river-crossing puzzle being fleshed out in one comfortable niche since this interpretation of the experiment would agree in every aspect
I was thinking about the river puzzle quite recently. Nice to see a mathematical explanation behind it. I love math (except when I was taking soul-crushing classes in college)! Also, it's nice to be early for a video.
There's a variation on this puzzle I saw a while back that is probably easier. You are a farmer with a Wolf, Chicken, and bag of corn. You must cross a river with a boat that only you may paddle and may only hold one item. If the Wolf is ever left alone with the Chicken you die and if the Chicken is left with the Corn you die. The Wolf may never eat the Corn however. [Solution Below] The solution would be to row the chicken over first then come back with nothing, then to row the wolf over and come back with the chicken (the wolf doesn't eat the chicken since you are there) then take the corn immediately back to the wolf and go back then take the chicken across.
hey cary! im going into highschool soon and ive been watching your videos all throughout middle school! your videos got me interested in programming and ive been learning python! thanks for inspiring me so much and I want wait for the next upload!
Really cool visualization. I remember playing a game like that as a kid, except it was with sticks, wolves, goats and cabbages. I don't think it would be possible to make it into a similar graph if there are more than 2 kinds of creatures
It can be done, but it gets harder to visualize because each new type of creature becomes its own axis (for example, the one you described would be a 4d graph) Numberphile did a visualization on the 1 wolf, 1 sheep and 1 cabbage version Edit: here's the link ua-cam.com/video/ZCVAGb1ee8A/v-deo.html
from the thumbnail i somehow thought this was a veritasium video until i was like “wait that sounds like cary!” lmao anyways that’s a pretty (and) elegant solution ngl, cool work!
The puzzle i heard of as a kid had a farmer, fox, chicken and a bag of corn. For some reason he wants to take the fox with him. And no it's not a pet trained fox it does want to eat the chicken. And oh boy the chicken eats fast so not leaving it with the corn. Also. The farmer needs to be on every trip, the fox is also not trained to control the raft.
Easy solution. Get trees from the forest (on fire so be careful!) and build a second raft. 2 rafts that can carry 3 people. 2 X 3 is 6 so everyone goes free!
I was playing with nice sounding chord progressions and I went to hooktheory to find if mine was already used. I proceeded to get distracted and I went to see what is the most common chord progression in A minor. I then found your more lasers and thought to myself that your profile picture was familiar. It seems I have seen some of your videos before and now I am here.
I've always known this puzzle as wolf-sheep-cabbage puzzle. If wolf and sheep are left alone, wolf will eat the sheep. And sheep will eat the cabbage if they're alone. Farmer needs to get them from one side to the other. Raft supports 2 creatures and farmer is always 1 of them
That is a different puzzle, although it does have some similarities and it could most likely be applied to one of these graphs, just with the vectors being (1,1,0,0), (1,0,1,0), and (1,0,0,1), as well as the legal positions being different. It would be difficult to visualise due to it being in four dimensions, though
So this is what you've been doing since the Marker and Coiny plush vid... Jeez louise, Cary, the term "jack of all trades" barely scratches the SURFACE of your abilites. You can animate, voice act, program, teach...is there anything you CAN'T do?!
I wonder what the state space will look like if the raft can contain three creature? My guess is it'll be very cluttered lol Also if we generalize the puzzle to include more types of creature that devour each other in a rock-paper-scissor like fashion does that mean we have to use a four dimensional graph? (which defeats the purpose of visualization but still) I have thought about this puzzle before but never increase the number of rafts. What a nice potential puzzle spaces you've explored, and it fits with the visualization very well as well!
Loved the generalizing of the solution at the end there, but I wonder, what if we adjust the number of people rather raft can carry?
That expands the number of movement vectors we get so I can imagine that we would get different solutions. Is there any point at which we would need more rafts, or does that stop once one extra person can get on?
I mean theses also the consideration of if the Dino eating Santa caveat should be applied also on the rafts as well.
Thanks galacticfish! Oooh, bigger rafts is an interesting variation to try. I think it actually wouldn't be too hard to test - I'd just have to add more legal moves to my array, which right now is (1,0,1), (2,0,1), (0,1,1), (0,2,1), (1,1,1). Tetrachart brings up an interesting point though, that 2 Dinos could eat a Santa while on the raft haha
My guess is, once we have a raft that can hold 4 creatures, you can just shimmy along the diagonal (2D + 2S cross, 1D + 1S come back, repeat over and over)
@@carykh You should do a short with the increased carrying capacity of each raft.
Adding capacity should just change the previous constant in n - 2 rafts yeah? as in n - x where n is amount of santas and x is raft carry capacity.
Well kinda. I'm not enough of a math kid to add a stipulation that the sum must be at least 1, but other than that it should be correct. Any added capacity should just push the middle gap problem one step further away.
@@carykh Could possibly change the nom nom condition from strictly greater than to greater than or equal to and then to greater than or equal to Santas - 1. I do fear, however, that the same patterns will arise on the edge cases (where size is 1 off nom nom threshold). And I assume there is a way to procedurally calculate moves rather than hardcoding them to an array. Another expansion could be of adding like a rock-paper-scissors equivalent (idk the specifics), but that’ll get rid of the 3 dimensions. Perhaps have a graph of graphs and at some point (if you delve into 5 or 6 dimensions) just display the result(s) instead. Love this graph theory approach!
Santa should fly on his sleigh across the river
The last 9 word TWOW-Mission.
@@asheep7797 the Nine Words Of Intelligence
I watched 3 seconds of your video confessional and I now know that the description "the sun kid" makes sense.
genius
@@IMC_123 NWOI
omg this is such an interesting way to visualise the puzzle! i wonder what other similar puzzles look like on a similar graph
but you believe the ted-ed riddle is wrong?
@@ioium299 what
I’ll keep this in mind next time I’m visiting the North Pole in the Cretaceous period
As a Yoshi, I’m glad carykh is finally giving us some representation.
True. I'm a Yoshi rights activist.
Ditching Yoshis off a cliff should be illegal
@@polyplayerYoshi is popular on Super Mario Galaxy 2 that doesn’t exist on 3D All Stars Back in March 31st 2021
@@PrideEepy64 im talking about super mario world
@@polyplayer I know but I was also referring to another part of Yoshi in Super Mario Galaxy 2
I am aware of Yoshi cliff in Super Mario World
8:20 no way!!!!!
Jokes aside, this is a really cool visualization of this problem that I never would’ve thought of. Great video as always!
every state that can be explored hazbin
and hazbin 🥶🥶🥰🤩🤩😘🥳😘😍🤩😘🤪😝😝🤤😜🤤😛😏😜😔🥲😍😗😍😗😌😚🤣
I like how it shows these visualizations can offer insights that are hard to see by just thinking through it.
8:56 dang that got deep really quick...
Had to solve this problem in college using PROLOG. Never fully understood how that worked.
Love this new style of video editing, Cary! I can tell you had fun with little bits like the "so wasteful" voice in the background lol
Pretty neat visualisation, would be a fun project (for me, or someone else) to write a solver using these heuristics, given an 'n' input, output an array of vectors of each step
Also, I guess you chose this version of the puzzle (or, TED-Ed) because its the easier one to visualize and reason about, while the other versions are more nuanced, like the one with the farmer, wolf, goat, and cabbage, or the one with a whole family that is super weird
Thanks PinkorCyan! Yeah, I did feel lucky when I realized this version of the puzzle only has 3 dimensions, when many other variations could easily have 5, 10, 15. Interestingly, the wolf+goat+cabbage one (which is arguably more well-known) actually has a 3D representation I found on Wikipedia! (but it's designed slightly differently)
8:58 Cary's getting too real :P Love the video!!
1:32 Ha, I knew you would slip and call em Yoshi's at least once! Cool Yoshi models btw, honestly clicked for the Yoshi, wondering what it was doing here in a puzzle video
i love the visualization, i never would have thought about it this way. your videos are the best
I love your algorithm videos and how you explore the concepts visually, so glad to see them return!
So great! I feel like I'm actually understanding the world in extra dimensions. P.S. I still show your scale of the universe to my students every term.
Thanks Ben! Oh wow, it's really cool to hear that my Scale of Universe is still playing a small part in students' education 😃
(One of these days the students themselves will be younger than the website, aaaaaa)
extra dimensions? this is just 3d
@@flyingduck91 agreed, but it *feels* like extra dimensions, probably because as he stated in the video, we're used to looking at the problem from only one particular perspective, not all at once.
Now that I think about it, is a scale of the universe website with 3d models ever possible?
@@drenz1523i guess? It's just replacing anything 2d with 3d models besides stuff like text and ui
It would take AGES but would be possible
I am really loving this method of visualization, it’s just one of the simplest
0:42 “None of these creatures can swim.”
(Childhood Memories of Winter plays)
Love this visualization, that it generalizes to an arbitrary number of dinos, santas, and rafts, and that you can be confident you didn't miss any alternate solutions! :) Fantastic video!
1:17 “-in their journey, the Dinosaurs can’t help but eat the Santa, killing him.”
(Childhood Memories of Winter plays)
I would really love to see this with other bridge crossing problems like the lamp and torch one!
Yoshis: flutterjump across the river
Santas: use their sleigh to fly over the river
Raft: :(
move #1. move 2 dinos | move #2. move 2 santas | move #3. move the remaining santa and dino
1:30 He got tired of saying dinosaur and finally saved our souls
I've been working on a similar thing, making data visualizations for the puzzle "signpost". the terminology of graph types that you mentioned will definitely be useful to me. thanks!
would never think to see so many tautologies of the river-crossing puzzle being fleshed out in one comfortable niche since this interpretation of the experiment would agree in every aspect
this is really satisfying to watch! seeing how you dissected the graph to show the solution was cool
i keep on forgetting that rdl members exist outside of rdl and being surprised
@@DPS-2004 i keep forgetting that rdl exists
Yeah this video makes it so much easier to understand than the ted ed video especially with the higher level crossings
I was thinking about the river puzzle quite recently. Nice to see a mathematical explanation behind it. I love math (except when I was taking soul-crushing classes in college)!
Also, it's nice to be early for a video.
This is amazing! Especially the generalization part.
There's a variation on this puzzle I saw a while back that is probably easier.
You are a farmer with a Wolf, Chicken, and bag of corn. You must cross a river with a boat that only you may paddle and may only hold one item.
If the Wolf is ever left alone with the Chicken you die and if the Chicken is left with the Corn you die. The Wolf may never eat the Corn however. [Solution Below]
The solution would be to row the chicken over first then come back with nothing, then to row the wolf over and come back with the chicken (the wolf doesn't eat the chicken since you are there) then take the corn immediately back to the wolf and go back then take the chicken across.
Happy 2023, Cary. That one is a nice puzzle there.
That is a very cool way to find the solution! And you mentioned the graphics library you used, thanks for that either!
Thanks for the quality content!
10/10 content
Excellent video about an excellent solution 👍. I hope you will keep making videos like this!
It is really interesting to see these type of videos after a semester in college full of classes with stuff like this
the whole of the universe tends towards entropy, and this is just one example. you're welcome. 10 points to me.
Very nice visualization and generalization!
Happy 26th birthday Cary Huang!
Insane visualization !! Great work !
Happy birthday Cary!
hey cary! im going into highschool soon and ive been watching your videos all throughout middle school! your videos got me interested in programming and ive been learning python! thanks for inspiring me so much and I want wait for the next upload!
Yoshi: how do we get across this river
Santa: I know graph theory
Yoshi: why?
Santa: I've solved the traveling salesman problem
This video was pretty interesting as I stuggled with the puzzle before, this video help me though. Very cool graphing from the origin
I remember learning something like this in class one actually.
Ted-ed is exactly why I know this! One of the first riddles I’ve learned AND solved actually!
You are the very last person I would expect a hazbin hotel reference from.
Not complaining though
I realized the Hazbin Hotel reference with Angeldust!
3:51 This bit reminds me of the part of jan Misali's video on regular polyhedra, specifically the part about zig-zag/skew polygons
i love how you expanded the problem
Happy late birthday Cary!!!!
Really cool visualization. I remember playing a game like that as a kid, except it was with sticks, wolves, goats and cabbages. I don't think it would be possible to make it into a similar graph if there are more than 2 kinds of creatures
It can be done, but it gets harder to visualize because each new type of creature becomes its own axis (for example, the one you described would be a 4d graph)
Numberphile did a visualization on the 1 wolf, 1 sheep and 1 cabbage version
Edit: here's the link
ua-cam.com/video/ZCVAGb1ee8A/v-deo.html
I didn't expect this to be coded in Processing . I knew it was capable but not that capable!+
*Yoshi is eating Santa*
DEATH P.A.C.T. (Both Past and Present): Not on our watch
Beautiful!
hey there micheal
real
7:23 😢 edge count
I love graph theory
from the thumbnail i somehow thought this was a veritasium video until i was like “wait that sounds like cary!” lmao
anyways that’s a pretty (and) elegant solution ngl, cool work!
0:39 FIREY UNDERWEAR!? That’s my kidnapper!
Oh look it’s yoshi! Hi yoshi!
Anywho, this is a great visualization of the river crossing puzzle!
900 IQ way to tackle the problem
1:23 the echo🤩🤩
another day of carykh beating TED-Ed at problem solving :)
wtf? kary KH science video again? finally!
im just happy to see that you also use processing
i really love the “comin to getcha moves”
thanks for the 3 am upload while I'm awake with covid, appreciate it my man
I am so stupid I didn’t understand this but it was very entertaining to see you figure everything out!
This is such a good way to visualize
Never seen this version of the puzzle before. Think the only one I heard of was about a fox, a chicken, and some grain 🤔
You just had to throw in the brief has Hazben Hotel referencesI love it
This is a fantastic visualization! Cheers
I love the visualization
The puzzle i heard of as a kid had a farmer, fox, chicken and a bag of corn. For some reason he wants to take the fox with him. And no it's not a pet trained fox it does want to eat the chicken. And oh boy the chicken eats fast so not leaving it with the corn.
Also. The farmer needs to be on every trip, the fox is also not trained to control the raft.
Love the video, nice use of visualization!
no santas were harmed in the making of this
Out of everything, you did Santas and dinosaurs.
your videos are always so cool i don't know what else to say
Easy solution.
Get trees from the forest (on fire so be careful!) and build a second raft.
2 rafts that can carry 3 people.
2 X 3 is 6 so everyone goes free!
The fact he knows what hazbin hotel is is definitely new information
0:40 this is the most cursed firey i have ever seen. Fire boiii
A fire w/ a baby dipar
No it's firey underwear
Me and my homies when we have 30 santas 30 dinosaurs but only 27 rafts: :(
1:30 as a fellow yoshi im glad he showed us some respect
Clicked for the Yoshi, stayed for the graph theory.
6:54 “There’s ZERO Santas.”
(Surprised trombone sound)
I never knew you conveniently had 3 dinosaurs and 3 santas!
Very glad the santa eating dinosaurs are extinct by now would have been disastrous for christmas.
"n Santas and n dinosaurs can cross iff we have n-2 rafts"
...that would imply 2 Santas and 2 dinosaurs can cross without any raft at all
or 1 Santa and 1 dinosaur can cross not only without any rafts, but with a tfar (negative raft)
1:08 "The dinosaurs still have this biological urge to eat humans."
-> Sorry, they don't. They had never the opportunity to develop such an urge 😉
So confusing that it confused my house down
Graph theory gets a bad rap; this approach feels a lot more "right" than the guess-and-check method of searching. Also haha love the allegory
I was playing with nice sounding chord progressions and I went to hooktheory to find if mine was already used.
I proceeded to get distracted and I went to see what is the most common chord progression in A minor. I then found your more lasers and thought to myself that your profile picture was familiar. It seems I have seen some of your videos before and now I am here.
0:41 cary reveals the actual reason why i stopped using cyshi
The puzzle solution hurts my head even more
I've always known this puzzle as wolf-sheep-cabbage puzzle. If wolf and sheep are left alone, wolf will eat the sheep. And sheep will eat the cabbage if they're alone. Farmer needs to get them from one side to the other. Raft supports 2 creatures and farmer is always 1 of them
That is a different puzzle, although it does have some similarities and it could most likely be applied to one of these graphs, just with the vectors being (1,1,0,0), (1,0,1,0), and (1,0,0,1), as well as the legal positions being different. It would be difficult to visualise due to it being in four dimensions, though
I like this MetaPerspective solving
So this is what you've been doing since the Marker and Coiny plush vid...
Jeez louise, Cary, the term "jack of all trades" barely scratches the SURFACE of your abilites.
You can animate, voice act, program, teach...is there anything you CAN'T do?!
I am always exited when he uploads
1:31 Cary accidentally said Yoshi
I wonder what the state space will look like if the raft can contain three creature? My guess is it'll be very cluttered lol
Also if we generalize the puzzle to include more types of creature that devour each other in a rock-paper-scissor like fashion does that mean we have to use a four dimensional graph? (which defeats the purpose of visualization but still)
I have thought about this puzzle before but never increase the number of rafts. What a nice potential puzzle spaces you've explored, and it fits with the visualization very well as well!
Noo!!! Now no one will have Christmas presents!
Huh, this very neat way seeing this puzzle.
Hey! These are three YOSHIS! Not dinosaurs!
Totally true
But yoshis are dinosaurs demselves😑😑😑😑😑