This video is VERY important because it adds more, and perhaps so far the most conclusive evidence to the lore that the voice is NOT the Bird but rather they are two distinct entities
I was a pilot for many years and as you'd expect we use a lot of maps flying around the world. When they get folded too many times the corners start to fail, and the map starts to come apart. I flew with one clever chap who figured out how to get around this - He simply scrunched the map up into a ball when we were done with it, so the fold lines didn't get used all the time. Weird, but it worked.
Scrolls for maps have a practical limit: the width of the map. They're also heavy,. So from a conservation pov: good choice. But usability? Not so much.
@@bartrammeloo5046 You could fold and roll your map. Plus, I'm pretty sure I've seen scrolls that were only the writing material? Maybe some of them had block rollers on the ends, but I'm sure not all were that way.
I can't believe you didn't mention the best part about "boustrophedon", which is that it's commonly translated to "as the ox plows", directly describing the kind of covering problem that's being solved by robot vacuums!
isnt that also the description for how greek texts were written or something? left to right and right to left so your eyes dont have to jump back over a large gap each time
@@ovencake523 It is! "Boustrophedon" is the form of writing where, when you get to the end of the line, you just start from that end one line down and head back (including writing the letterforms backwards). That's where I (and most people) learned the term from - it's an incredibly interesting, like, "writing direction" that a language can have
@@deltamico Sort of! In most ancient examples, where boustrophedon writing is mainly seen, this was done when carving writing into stone, so that's not as much of a problem (and for some examples, like writing across a massive wall, you can see why someone would want a system where you don't have to keep walking back and forth between lines). That said, there are some modern scripts that do actually use a boustrophedon writing direction, such as Avoiuli (though unfortunately I'm not super familiar with that example).
It comes from ancient greek writing in one direction and then flipping so the guy carving the rock wouldn’t have to go all the way to the beginning to keep writing after finishing a line
Paper folding maths is one of those XKCD 1831 things that feel easy until you try them. Thanks for making these videos, I would have never heard about all of this without you.
Seeing the number of possible ways to fold a map, then I can finally rest knowing, I wasn't bad at folding the instructions manual and mathematicians also don't know how to fold a map.
Boustrophedon was a super oldschool way of writing, our Latin teacher had an extra credit assignment once where you had to transcribe using it. There are no spaces, reading direction changes every line as well as letters flip horizontally, and words that are cutoff at the end of a line are just continued on the next in the other direction. It's wild.
As as survivor of 6 years of Latin, same. Also, for anyone else chiming in, the original term comes from Ancient Greek: βουστροφηδόν, boustrophēdón, a composite of βοῦς, bous, "ox"; στροφή, strophḗ, "turn"; and the adverbial suffix -δόν, -dón, "like, in the manner of" - that is, "like the ox turns [while plowing]". Yet another occasion of Romans "borrowing" from Greece.
@ clearly I haven’t read them recently enough, since I even forgot the species name :) I just remembered Artemis cutting them up into “normal” lines for his translation software.
@physicsforthebirds you're awesome for making them! I always look forward to your videos. Even if I think I have a general understanding of the topic, you somehow bring a fun fact into each one that no one else really talks about - which is usually the real world application of why a physics problem is important to solve. I kind of wonder if the map folding solution can also explain The Traveling Salesmen problem.
About that thing at the end about vacuum robot path-finding. My parents have had three robots I helped set up and fix. None really follow either of the path algorithms you suggest. - The first was an early Roomba, as far as I could tell it was completely random. Walk straight until it hits something, back up, spin around anywhere from 90 to 180 degrees either side, repeat. It didn't even have a smart way to find the charger, it would just turn off the vacuum but keep doing this until it could see the charger's beacon. Though it did have the spiral mode if you put it on a spot and hit a button, but it wouldn't get the whole room. - Second was a RoboMow. It was random too, but it would follow an "invisible fence" wire back to the dock at least. It also had a remote control like an RC car, buuuuut then they broke the remote control in the app and then never brought it back... - The newest is a Bissel wet/dry vacuum with a mop attachment. (I wonder how it knows what carpet is and where not to bring the mop?) It does attempt that zig-zag pattern, but it isn't perfect. It doesn't go parallel to the walls, it doesn't go all the way to the wall if it starts in the middle of the room, it doesn't really compensate for bumping into a chair and forgets what direction it was going in... But it's doing *something* right, when it mopped the kitchen I didn't see any dry areas except for where it couldn't reach.
The original Roombas used a random walk combined with a measurement of the average distance between collisions to estimate how long to run. There was no guarantee that the entire floor would be covered, but it was good enough most of the time.
Hi Physics for the Birds Ornithologist and mariner here. Wrapping my head around the numbers, I got one question for you (had two until I started folding paper and numbering them myself this morning) 1 Cancelled question 2 At certain size there will be material constraints (yeh I get it, it's math), you can at least simulate paper thickness and yes is it a fold if the paper curls around in a tube? Ie. turning ratio for vacuum robots too. A fold is super efficient as technique, but if you travel on the edge of a fold, it is incredibly inefficient to not short cut edges. Ie. the moment we aren't in paper no more, how to estimate when to soften the waypoints? (Think rute calculation for commercial ships) just a thought
I recall seeing a news report about the young woman who developed an equation to find the maximum number of folds you can put in a piece of paper. She had to answer exactly the issues you raise in your second question.
My roomba does not appear to follow a map folding pattern all of the time. When it reaches a new zone, it starts moving in a curve with a relatively large radius of curvature. The roomba will bump into an object and then turn with an angle that looks suspiciously like some fraction of the golden ratio ~137 deg. I have not measured this but I suspect the turn angle is irrational to prevent the roomba from getting caught in a repeating path across the floor and to guarantee that it will (eventually) cover every bit of area.
My hands are itching to give it a shot, and see if I can get it running on a good server from my uni XD Just checked, and students can use our high-performace-cluster for free. Interesting... I first need to finish a graded project though
this feels like an incredibly easy problem for a gpu to do unfortunately i have no clue how to write in a gpu based programming language, nor do i know how to write asynchronous/parallel code lol
The approach I would take, if a map were a checkerboard (8X8) to be folded only along all the 7 horizontal and 7 vertical borders ("creases") that fell between two rows or between two columns (not that I would have any idea what "fold it along the line at its edge" would mean anyway), would be to try cope with the fact that you can't just assign unique numbers 1 through 14 to unique creases and then believe that there are as many ways to fold a map as there are to put 14 objects in an order. The problem is that if you fold along a crease that is one square inwards from a square, you've only eliminated one crease from all future creases to fold. But if you choose a crease that is two folds in, then you end up stacking the crease to its left on top of the crease to its right. They've become one possible future crease-location. You started out with 14 possible choices, picked one (eliminating it, leaving 13) but also eliminated 1 more future choices because two choices have merged to become one choice. So you have only 12, not 13, possible moves left. But this elimination of 2 choices applies only if your first choice is 1 inside from the edge. Start by folding a crease TWO from the edge, and you stack TWO remaining choices on top of two others. This means that you had 14 choices before you started, executed ONE of them, but not have only ELEVEN choices remaining. It seems to me that maybe it'd be easier to start with a folded map that shows only one checkerboard square when it's lying on a table (another square touching the table). What are all the possible results that can be achieved by unfolding only the last fold made?
10:55 - I wondered for a long time what a "booster-feed-on" pattern was. It turns out it's "boustrophedon". The boustrophedont was some kind of big powerful dinosaur, that, as you can guess from the "dont" ending its name, has a distinct kind of tooth. Cavemen had to use this dinosaur for plowing because the ox wasn't domesticated (or maybe not even evolved) yet. (A lot of Indo-European words for "ox" come from a root "bos" that is named after the boustrophedont). The boustrophedonts always wanted to get the plowing done as fast as possible, and so turned around at the end of a row and pulled the plow over the next row walking the opposite direction as they had just walked to plow the previous row. There were some scribes in the ancient Mediterranean and Sumerian worlds who, rather than carving or writing every line always left to right, or always right to left, wrote every-other line left-to-right and the other lines right-to-left, like an ox or dinosaur plowing a field, turning around and going the other way rather than always going back to the same end of a line or row. There's no example of an ancient Assyrian typewriter where the end-of-line lever makes the carriage go all the way back to the beginning for the next line, instead of just reversing the gearing and typing the next line in the opposite direction. This way of writing back-and-forth is known as "boustrophedon".
HURRAY! Another Physics for the Birds vid!!! seriously, love your content... I watch a lot of science/physics/math channels... yours is by far my favorite! :) Thank you!
There are videos that are very informative and interesting and then there are videos like yours. You make it very interesting and also cozy and cute at the same time. I don't only feel intrigued watching your videos, I feel comforted and good.
If I could give some constructive feedback? Lower/less harsh tones for the bird squeaking would be highly appreciated. It may be just me not jiving with the audio and not an issue with most other viewers though. Thank you for the wonderful video 💜
It's not obvious, but this is an absurd way of checking if the number is even. It assumes that the programming language it was written in divides integers into other integers (so 5/2 = 2 and 5/2*2 = 4, not 5), which is NOT an assumption you should make while writing pseudocode!
@@physicsforthebirds It is weird today for sure, but I wouldn't necessarily call it absurd. It is more or less exactly the rigorous definition of divisibility.
I guess it makes sense if the language used had limited operations, e.g. only +,-,*,/ and no %/"modulo" operator. But even in that case, just write a mod() function for it please.
I really like your videos and these cool problems you always bring up. And i was wondering, how do you find these niche problems? Are problems that you already heard of or do you find them searching?
Many of my videos are things that I notice myself and then they turn out to be real problems, and many are things that I find while reading. This one was something I read about, I think I first got interested when I saw it on Wikipedia's list of "unsolved math problems". In any case, each of my videos involves lots of searching through citations and books and trying to solve things myself to get interesting examples. I always put the most relevant references in the description, so feel free to explore it yourself!
@physicsforthebirds wow, thanks for answering! I didn't know about that page of Wikipedia but I will definitely look at it! I'm a Data Science student and it's gonna be fun trying to advance in some of these problems.
Hi! Just wanted to say this was an incredibly charming video, very well presented. It struck a great balance between being too technical and being too general/wishy woshy with details.
6:35 - I'm really glad to find out that the On-Line Encyclopedia Of Integer Sequences keeps track of sequences of integers, but, further, I'd like to know if we have to buy it as a paper book or can we just find it on-line?
7:45 uhhhhh, no? Are there actually programmers who would voluntarily use such a font? I'd consider the ability to clearly distinguish between 1, l, I, and | (and also 0 and O) to be a pretty basic and essential feature of any decent font used for programming
Hi, this was another great video! I am curious, so the problem seems to be set up in such a way that one would expect todays computers to be able to compute the number of folding for more n than was previously known in the 60’s. However, through the process of trying to get a modern computer to solve the problem, your code wasn’t able to run properly. If you were able to get your code to run properly do you think this would output more values of map foldings for a given n?
My code, which was based off of Sean Irvine's code in the description, did work. Sean used this code to calculate up to a 7x7 a few years ago (and the original paper in the 60s calculated up to 5x5 if I remember correctly). He might say somewhere what hardware he ran it on, but I wouldn't be surprised if it was his personal setup. If people dedicated more advanced hardware to this problem for some reason, I'm sure they could do better, but there are many, many sequences of integers that need to be calculated!
As a hobby origamist, paper folding feels like this impossibly deep rabbithole with infinite knowledge waiting at the end. You can do so many things and it lets you visualize a bunch more, and in general it gives you an intuition of space that you wont find on digital media.
Lucida Console is by far the best monospaced font. I used to be a Courier stan, until I realized that readability was trash compared to LC. LC just works better as a vector font, and it uses sarifs in the best way possible. As a plus, it looks better on modern IDEs, and is less grating on they eyes somehow. LC FTW.
I have a Roborock and my friend has a Roomba, both are pretty new, and the Roomba has the vaccum dock, so it should be a higher end model. The Roomba seems to always have a random pattern (although my friend says it has the house mapped), but the Roborock always circles the outline of each room and then fills it in with the Boustrophedon pattern (thanks for making me look this up). It even rotates the pattern and repeats if you have it do multiple passes. Obstacle avoidance is done with both lidar and the bumper, and it just moves around the object until it can resume the path.
Since we're talking about folding maps, there's a specific way of folding a map that prevents it from tearing at the creases, it's called Miura fold, you should check it out. It's even used to fold solar panels of spacecrafts!
I think the roomba problem the way you described it, can be compared with maze generation or snake bots. Code bullet made a video about snake, where it follows a hilbert-like path (iirc) and then chooses shortcuts to get to the apples faster. The maze algorithm I saw (in another video) started with a space filling path, and then changed some paths into walls and vice versa semi-randomly.
When I was a Sinclair Spectrum programmer in the 80s I always had variables called i and o, equal to the constants 1 and 0 respectively. That was because numbers, even single-digit ones, took up 5 bytes of memory each, while single-letter variables took up one byte each. Yes, my programs were hard to read, but at least I didn’t use SGN PI for 1 and NOT PI for zero.
Randomness seems to help in the actual real world for problems like robot vacuums that need to visit all points. Many use an algorithm like “go straight until you hit a wall, turn a random amount in place, then go again.” Deterministic path planning can break; if you get stuck a little bit, then you lose the whole process. Randomness gives robustness of having a chance that all points would eventually get visited even if your measurement or process gets disrupted.
That works well enough in the real-world application, but the problem of trying to visit each spot once and only once would be virtually impossible with random direction selection. Moving about randomly is inefficient as it will cross the same areas multiple times and could take a very long time to hit every area (the more areas it's already touched, the less and less likely it becomes for it to get to untouched areas).
I'm sure there's a graph somewhere. Also it weirdly reminds me of vector multiplication, idk why. Now I started to think about how this would scale in N dimensions, damn
"Boustrophedon" is an ancient Greek word and means zigzag. Actually, it means "like the ox plows" and describes, especially in epigraphy, a way of writing where the first line is read from left to right and the second from right to left. What is it good for? If a text is written on a long wall, you only have to take half as many steps to be able to read everything. Fun fact of the day!
The bird sounds like a whole flock combined. Like a meta-consciousness running on several birds at the same time to speed up the computation necessary to contribute to this video.
This feels exactly like the problem of finding an equation for prime numbers. Each additional step, whether it be the construction of the number line or a valid fold pattern, seems to add a new "fundamental" property to the system that can only be checked algorithmically with some O(n) that is greater than linear.
11:00 Boustrophedon doesn't mean zig-zag, it means "as the ox plows" as in plowing a field. Zig-zag has sharp points as the ends, boustrophedon has 90° turns.
Did the math take into consideration the crease direction as a constraint? Like if the map was creased and folded in 1 direction, you avoid folding in the opposite direction. When a single line is creased in just 1 direction, you can't fold perpendicularly to that line before folding the line itself. Even with both directions mixed in a single line, it would also constrain what folds to make before that as to avoid overlapping creases that are same-direction before the fold and opposite each other after the fold.
In 6th grade I asked my math teacher if you could math out origami patterns and he said "yeah, probably." I had never seen an honest reaction from a mathematician before then
Hey the video is soo great, but please lower or change a bit the bird voice part, because it's very hard to concentrate and read properly. But anyway, the concept for future implementation of optimal pathfinding in autonomous routing is very interesting!
You called the ways to fold it mountain and valley style. Finally someone who knows what it's actually called. Sick and tired of everyone calling it hamburger and hot dog style. You don't even fold hamburgers!
I'm fairly certain "mountain" and "valley" refer to convex and concave foldings, respectively. Whereas "hotdog" and "hamburger" refer to whether the larger or the smaller edge of the paper is being folded in half: smaller edge is being folded = hotdog, longer edge being folded = hamburger
Another example could be a 3d printer doing a layer's solid infill pattern. The nozzle needs to move back and forth filling the area, but it has to fit within the 2d shape of the layer and you want to minimize the amount of time the nozzle travels without pushing out filament.
Hello, the code @9:35 makes sense to me and seem to be equivalent. I am confused about only one if condition (the hardest one perhaps lmao). This is how I understand the code: "delta = c[i, l] - c[i, m] d[i, l, m] = 0 if m != 0 then if delta is even then if c[i, m] is 1 then d[i, l, m] = m else d[i, l, m] = m - P[i-1] else if c[i, m] == p[i] > m + P[i-1] > l then #this is the if condition I only partially understand lmao. d[i, l, m] = m else d[i, l, m] = m + P[i-1]" My best guess for the if condition is there must've been a typo lol. What do you think? Cause if they f-ed up 1 and l then they can do a mistake like this too? Edit: I am a robotics masters (hopefully a PhD student soon) and cleaning robots are dumb af. Most of these papers are just for cases when you want to try out a new algo for funsies. That being said some companies do have fancy algorithms. PS, I think you have irked my curiosity and I think you have gained a subscriber. Hoping to see more cool videos from you!
These kinds of pseudocode are oftentimes just the _worst_ for readability. Once spent several weeks trying to understand a piece of pseudocode in a paper like this and it turned out to be just a heuristic search, basically a variation on A*, but it was so riddled with symbols defined five pages earlier that it was near incomprehensible
Would it be possible to model the folds by showing the corner of each square as a gradient of color, such that each fold along a given axis increases the Hue or Saturation based on the number of folds in a given direction with a split should it flip directions, like tree rings. This way you can run a color comparison analysis to identify duplications that erroneously increase the count? Think of it like folding a burrito. You fold in the left, bottom, right, and roll it up. It doesn't matter what orientation the ingredients are in, as you've oriented them based on your reference frame.
Bang-on right! At first I thought "Isn't that just like guessing to jiggle a 'Z' fold just right?" But I realized you mean to roll up two turns _so that the ends line up_ before squishing. That is not only pretty good but-for infinitely thin paper-perfectly exact.
I didn't care for the bird's staticky little voice (your voice is much more enjoyable) but otherwise, incredible video! Your illustrations were very clear. Well done!
You wanna know a secret? The bird's voice _is_ mine... (speaking syllables that python splices together to form English words that are transcribed into Japanese kana and then pitch-shifted to match actual bird calls)
What’s strange is if you care about the entire folding process, tracking the order you make every fold in rather than just the finished product, counting the number of foldings becomes so much easier: The folds can be done in any order: on an mxn sheet of paper, there are (m+n-2)! different orders, and at each step, you can fold the paper one of two ways, so 2^(m+n-2). In general, a piece paper with n folds can be folded in n!*2^n ways! You’ll get several of the same maps at the end, so this doesn’t actually solve the problem in the video, but it’s about the journey, right?
The industry I work in has a bad habit of using the letter I next to the digit 1 so I feel your pain there. I really wish the default font in every app differentiated these three letters. 1Il
You said in the video that it would take between 3 and 10 years to get an 8x8. Do you know if the algorithm is parralelizable? Then maybe we can split it between 100 computers and get it done in half a year.
I believe the most common algorithm for robot vacuums is random. It just goes in a direction until it hits something, then turns a few degrees, and continues like that. Finding it's way home is similar, but it uses some sort of signal, perhaps IR to track it's goal once it randomly gets close.
![เปิด อาณาจักร หมื่นล้าน "สาระตั้ม" l [Nickynachat]](http://i.ytimg.com/vi/3XE0nPF4YkQ/mqdefault.jpg)
This video is VERY important because it adds more, and perhaps so far the most conclusive evidence to the lore that the voice is NOT the Bird but rather they are two distinct entities
it's called physics FOR the Birds, not physics BY the Birds...
Schizo
@@theminecraft4202 well what if one assumes that it's most plausible that birds are best taught by their fellow birds?
HMM? WHAT THEN?
@@hopperdown811wtf are you on about
I'm not convinced
I was a pilot for many years and as you'd expect we use a lot of maps flying around the world. When they get folded too many times the corners start to fail, and the map starts to come apart. I flew with one clever chap who figured out how to get around this - He simply scrunched the map up into a ball when we were done with it, so the fold lines didn't get used all the time.
Weird, but it worked.
I guess that's why scrolls were invented.
Scrolls for maps is genius
Scrolls for maps have a practical limit: the width of the map. They're also heavy,. So from a conservation pov: good choice. But usability? Not so much.
@@bartrammeloo5046 You could fold and roll your map. Plus, I'm pretty sure I've seen scrolls that were only the writing material? Maybe some of them had block rollers on the ends, but I'm sure not all were that way.
Heresy!
I can't believe you didn't mention the best part about "boustrophedon", which is that it's commonly translated to "as the ox plows", directly describing the kind of covering problem that's being solved by robot vacuums!
isnt that also the description for how greek texts were written or something? left to right and right to left so your eyes dont have to jump back over a large gap each time
@@ovencake523 It is! "Boustrophedon" is the form of writing where, when you get to the end of the line, you just start from that end one line down and head back (including writing the letterforms backwards). That's where I (and most people) learned the term from - it's an incredibly interesting, like, "writing direction" that a language can have
So both lefties or right handed peeps will smudge their letters
@@deltamico Sort of! In most ancient examples, where boustrophedon writing is mainly seen, this was done when carving writing into stone, so that's not as much of a problem (and for some examples, like writing across a massive wall, you can see why someone would want a system where you don't have to keep walking back and forth between lines). That said, there are some modern scripts that do actually use a boustrophedon writing direction, such as Avoiuli (though unfortunately I'm not super familiar with that example).
It comes from ancient greek writing in one direction and then flipping so the guy carving the rock wouldn’t have to go all the way to the beginning to keep writing after finishing a line
Paper folding maths is one of those XKCD 1831 things that feel easy until you try them.
Thanks for making these videos, I would have never heard about all of this without you.
there really is an XKCD comic for everything huh?
I can't believe I got the reference. Maybe I really am a giga nerd after all
I HATE that I'm a big enough nerd to not have to google that
Thank you for the wonderfu1 video as a1ways, Physics Bird.
1o1
1mao
did you lose the L key
@@user-qw9yf6zs9t
It's a reference to the video.
Seeing the number of possible ways to fold a map, then I can finally rest knowing, I wasn't bad at folding the instructions manual and mathematicians also don't know how to fold a map.
That pseudocode was clearly written with FORTRAN in mind IMO
Boustrophedon was a super oldschool way of writing, our Latin teacher had an extra credit assignment once where you had to transcribe using it. There are no spaces, reading direction changes every line as well as letters flip horizontally, and words that are cutoff at the end of a line are just continued on the next in the other direction. It's wild.
Oh, like the fairy language in Artemis Fowl
As as survivor of 6 years of Latin, same. Also, for anyone else chiming in, the original term comes from Ancient Greek: βουστροφηδόν, boustrophēdón, a composite of βοῦς, bous, "ox"; στροφή, strophḗ, "turn"; and the adverbial suffix -δόν, -dón, "like, in the manner of" - that is, "like the ox turns [while plowing]". Yet another occasion of Romans "borrowing" from Greece.
@@kaitlyn__L No, Gnommish spirals outward. (Well, at least _Classical_ Gnommish.)
@ clearly I haven’t read them recently enough, since I even forgot the species name :) I just remembered Artemis cutting them up into “normal” lines for his translation software.
Hey all, stop what you're doing. There's birds doing physics
You guys are so awesome for watching these
@physicsforthebirds you're awesome for making them! I always look forward to your videos. Even if I think I have a general understanding of the topic, you somehow bring a fun fact into each one that no one else really talks about - which is usually the real world application of why a physics problem is important to solve.
I kind of wonder if the map folding solution can also explain The Traveling Salesmen problem.
Yeah, I know. We’re right here.
@@physicsforthebirds
"No _you're_ breathtaking!"
who are they doing physics for? themselves? seems selfish...
The birds can SPEAK!? the plot thickens...🐦🐦
The plot chickens
The flock thickens
About that thing at the end about vacuum robot path-finding. My parents have had three robots I helped set up and fix. None really follow either of the path algorithms you suggest.
- The first was an early Roomba, as far as I could tell it was completely random. Walk straight until it hits something, back up, spin around anywhere from 90 to 180 degrees either side, repeat. It didn't even have a smart way to find the charger, it would just turn off the vacuum but keep doing this until it could see the charger's beacon. Though it did have the spiral mode if you put it on a spot and hit a button, but it wouldn't get the whole room.
- Second was a RoboMow. It was random too, but it would follow an "invisible fence" wire back to the dock at least. It also had a remote control like an RC car, buuuuut then they broke the remote control in the app and then never brought it back...
- The newest is a Bissel wet/dry vacuum with a mop attachment. (I wonder how it knows what carpet is and where not to bring the mop?) It does attempt that zig-zag pattern, but it isn't perfect. It doesn't go parallel to the walls, it doesn't go all the way to the wall if it starts in the middle of the room, it doesn't really compensate for bumping into a chair and forgets what direction it was going in... But it's doing *something* right, when it mopped the kitchen I didn't see any dry areas except for where it couldn't reach.
The original Roombas used a random walk combined with a measurement of the average distance between collisions to estimate how long to run. There was no guarantee that the entire floor would be covered, but it was good enough most of the time.
A moving average would make sense in that case
I loved “higher-dimensional paper” being said so casually
I adore his sense of humor. I still giggle about "Think back to the time when you were a single fertilized cell-a zygote."
the kind of videos I watch youtube for, I'm always amazed at how silly questions like this one may lead you into a rabbit hole
For the valuable contributions you have made to the flock, I wish you plentiful good and many shiny things.
and yet my dad always puts the atlas back together with perfect precision
Yet another W for the Meat Thinkers
You can reconstruct a fold from a O(log(creasts)) memory
I'm so genuinely happy that you made a new video. Thank you and I'm sure it will be amazing.
Hi Physics for the Birds
Ornithologist and mariner here. Wrapping my head around the numbers, I got one question for you (had two until I started folding paper and numbering them myself this morning)
1 Cancelled question
2 At certain size there will be material constraints (yeh I get it, it's math), you can at least simulate paper thickness and yes is it a fold if the paper curls around in a tube? Ie. turning ratio for vacuum robots too. A fold is super efficient as technique, but if you travel on the edge of a fold, it is incredibly inefficient to not short cut edges. Ie. the moment we aren't in paper no more, how to estimate when to soften the waypoints? (Think rute calculation for commercial ships)
just a thought
I recall seeing a news report about the young woman who developed an equation to find the maximum number of folds you can put in a piece of paper. She had to answer exactly the issues you raise in your second question.
Absolutely fascinating! Love your content man, awesome balance with the technical details.
My roomba does not appear to follow a map folding pattern all of the time. When it reaches a new zone, it starts moving in a curve with a relatively large radius of curvature. The roomba will bump into an object and then turn with an angle that looks suspiciously like some fraction of the golden ratio ~137 deg. I have not measured this but I suspect the turn angle is irrational to prevent the roomba from getting caught in a repeating path across the floor and to guarantee that it will (eventually) cover every bit of area.
13:06 i would never call a variable a single letter so dw no "l"''s for me
This was fun. I wonder if you posting this video will have a direct result of someone discovering the 8x8 number.
Will probaly do so.
All you need is a couple people going "it can't be that hard", making a relatively efficient implementation and running it on a high end computer
My hands are itching to give it a shot, and see if I can get it running on a good server from my uni XD
Just checked, and students can use our high-performace-cluster for free.
Interesting...
I first need to finish a graded project though
this feels like an incredibly easy problem for a gpu to do
unfortunately i have no clue how to write in a gpu based programming language, nor do i know how to write asynchronous/parallel code lol
The approach I would take, if a map were a checkerboard (8X8) to be folded only along all the 7 horizontal and 7 vertical borders ("creases") that fell between two rows or between two columns (not that I would have any idea what "fold it along the line at its edge" would mean anyway), would be to try cope with the fact that you can't just assign unique numbers 1 through 14 to unique creases and then believe that there are as many ways to fold a map as there are to put 14 objects in an order. The problem is that if you fold along a crease that is one square inwards from a square, you've only eliminated one crease from all future creases to fold. But if you choose a crease that is two folds in, then you end up stacking the crease to its left on top of the crease to its right. They've become one possible future crease-location. You started out with 14 possible choices, picked one (eliminating it, leaving 13) but also eliminated 1 more future choices because two choices have merged to become one choice. So you have only 12, not 13, possible moves left. But this elimination of 2 choices applies only if your first choice is 1 inside from the edge. Start by folding a crease TWO from the edge, and you stack TWO remaining choices on top of two others. This means that you had 14 choices before you started, executed ONE of them, but not have only ELEVEN choices remaining. It seems to me that maybe it'd be easier to start with a folded map that shows only one checkerboard square when it's lying on a table (another square touching the table). What are all the possible results that can be achieved by unfolding only the last fold made?
Your Videos are always such a pleasure to watch with all the detail you put in them, like the map as a background. Thank You!
Hooray one of my favorite niche channels that teach math with real world examples posted a new video!
10:55 - I wondered for a long time what a "booster-feed-on" pattern was. It turns out it's "boustrophedon". The boustrophedont was some kind of big powerful dinosaur, that, as you can guess from the "dont" ending its name, has a distinct kind of tooth. Cavemen had to use this dinosaur for plowing because the ox wasn't domesticated (or maybe not even evolved) yet. (A lot of Indo-European words for "ox" come from a root "bos" that is named after the boustrophedont). The boustrophedonts always wanted to get the plowing done as fast as possible, and so turned around at the end of a row and pulled the plow over the next row walking the opposite direction as they had just walked to plow the previous row. There were some scribes in the ancient Mediterranean and Sumerian worlds who, rather than carving or writing every line always left to right, or always right to left, wrote every-other line left-to-right and the other lines right-to-left, like an ox or dinosaur plowing a field, turning around and going the other way rather than always going back to the same end of a line or row. There's no example of an ancient Assyrian typewriter where the end-of-line lever makes the carriage go all the way back to the beginning for the next line, instead of just reversing the gearing and typing the next line in the opposite direction. This way of writing back-and-forth is known as "boustrophedon".
HURRAY! Another Physics for the Birds vid!!! seriously, love your content... I watch a lot of science/physics/math channels... yours is by far my favorite! :) Thank you!
There are videos that are very informative and interesting and then there are videos like yours. You make it very interesting and also cozy and cute at the same time. I don't only feel intrigued watching your videos, I feel comforted and good.
I love the pauses before the unit measurement. Reminds me of my favorite icarly quote.. "3, 4... maybe 5"
I wasn't expecting the video to turn out how it did and it was super interesting!
12:42 never have I been more excited to watch my roomba clean.
If I could give some constructive feedback? Lower/less harsh tones for the bird squeaking would be highly appreciated. It may be just me not jiving with the audio and not an issue with most other viewers though. Thank you for the wonderful video 💜
Wait, what does the "if" in the second line at 9:39 do? it tests if == /2 *2 !? How can that possibly make any sense?
It's not obvious, but this is an absurd way of checking if the number is even. It assumes that the programming language it was written in divides integers into other integers (so 5/2 = 2 and 5/2*2 = 4, not 5), which is NOT an assumption you should make while writing pseudocode!
@@physicsforthebirds It is weird today for sure, but I wouldn't necessarily call it absurd. It is more or less exactly the rigorous definition of divisibility.
I guess it makes sense if the language used had limited operations, e.g. only +,-,*,/ and no %/"modulo" operator. But even in that case, just write a mod() function for it please.
I, too, like to present "the following pseudocode:" followed by exact assembly implementation.
I really like your videos and these cool problems you always bring up. And i was wondering, how do you find these niche problems? Are problems that you already heard of or do you find them searching?
Many of my videos are things that I notice myself and then they turn out to be real problems, and many are things that I find while reading. This one was something I read about, I think I first got interested when I saw it on Wikipedia's list of "unsolved math problems". In any case, each of my videos involves lots of searching through citations and books and trying to solve things myself to get interesting examples. I always put the most relevant references in the description, so feel free to explore it yourself!
@physicsforthebirds wow, thanks for answering! I didn't know about that page of Wikipedia but I will definitely look at it!
I'm a Data Science student and it's gonna be fun trying to advance in some of these problems.
Hi! Just wanted to say this was an incredibly charming video, very well presented. It struck a great balance between being too technical and being too general/wishy woshy with details.
In my experience, robot vacuums really limit the amount of efficiency in their route in favor of just covering areas many times over just to be safe.
6:35 - I'm really glad to find out that the On-Line Encyclopedia Of Integer Sequences keeps track of sequences of integers, but, further, I'd like to know if we have to buy it as a paper book or can we just find it on-line?
Love this channel, the topics you cover are so niche, but exactly the kind of interesting topics I wonder about!
I legit grt excited for this 🎉❤
I never thought this much about folds before. Thank you mr. Bird
7:45 uhhhhh, no? Are there actually programmers who would voluntarily use such a font? I'd consider the ability to clearly distinguish between 1, l, I, and | (and also 0 and O) to be a pretty basic and essential feature of any decent font used for programming
The outro music is wonderful! did you write it?
Yep, the music I use is mine, made for these videos. We'll see if I ever release it alone.
Hi, this was another great video! I am curious, so the problem seems to be set up in such a way that one would expect todays computers to be able to compute the number of folding for more n than was previously known in the 60’s. However, through the process of trying to get a modern computer to solve the problem, your code wasn’t able to run properly. If you were able to get your code to run properly do you think this would output more values of map foldings for a given n?
My code, which was based off of Sean Irvine's code in the description, did work. Sean used this code to calculate up to a 7x7 a few years ago (and the original paper in the 60s calculated up to 5x5 if I remember correctly). He might say somewhere what hardware he ran it on, but I wouldn't be surprised if it was his personal setup. If people dedicated more advanced hardware to this problem for some reason, I'm sure they could do better, but there are many, many sequences of integers that need to be calculated!
@@physicsforthebirds Sean Irving version is based on a C implementation by Fred Lunnon, the original paper author, which is corrected from the paper.
As a hobby origamist, paper folding feels like this impossibly deep rabbithole with infinite knowledge waiting at the end. You can do so many things and it lets you visualize a bunch more, and in general it gives you an intuition of space that you wont find on digital media.
Lucida Console is by far the best monospaced font. I used to be a Courier stan, until I realized that readability was trash compared to LC. LC just works better as a vector font, and it uses sarifs in the best way possible. As a plus, it looks better on modern IDEs, and is less grating on they eyes somehow. LC FTW.
I have a Roborock and my friend has a Roomba, both are pretty new, and the Roomba has the vaccum dock, so it should be a higher end model. The Roomba seems to always have a random pattern (although my friend says it has the house mapped), but the Roborock always circles the outline of each room and then fills it in with the Boustrophedon pattern (thanks for making me look this up). It even rotates the pattern and repeats if you have it do multiple passes. Obstacle avoidance is done with both lidar and the bumper, and it just moves around the object until it can resume the path.
Since we're talking about folding maps, there's a specific way of folding a map that prevents it from tearing at the creases, it's called Miura fold, you should check it out. It's even used to fold solar panels of spacecrafts!
Im so happy you are back
I think the roomba problem the way you described it, can be compared with maze generation or snake bots. Code bullet made a video about snake, where it follows a hilbert-like path (iirc) and then chooses shortcuts to get to the apples faster. The maze algorithm I saw (in another video) started with a space filling path, and then changed some paths into walls and vice versa semi-randomly.
i absolutely love content like this
When I was a Sinclair Spectrum programmer in the 80s I always had variables called i and o, equal to the constants 1 and 0 respectively. That was because numbers, even single-digit ones, took up 5 bytes of memory each, while single-letter variables took up one byte each. Yes, my programs were hard to read, but at least I didn’t use SGN PI for 1 and NOT PI for zero.
fascinating vid. i always assumed there would be an equation about combinatorics, but i learned something new :)
Randomness seems to help in the actual real world for problems like robot vacuums that need to visit all points. Many use an algorithm like “go straight until you hit a wall, turn a random amount in place, then go again.” Deterministic path planning can break; if you get stuck a little bit, then you lose the whole process. Randomness gives robustness of having a chance that all points would eventually get visited even if your measurement or process gets disrupted.
That works well enough in the real-world application, but the problem of trying to visit each spot once and only once would be virtually impossible with random direction selection. Moving about randomly is inefficient as it will cross the same areas multiple times and could take a very long time to hit every area (the more areas it's already touched, the less and less likely it becomes for it to get to untouched areas).
Nice vid as always!
Yes, Mr. the Birds, I also enjoy Folding Ideas.
I'm sure there's a graph somewhere.
Also it weirdly reminds me of vector multiplication, idk why.
Now I started to think about how this would scale in N dimensions, damn
"Boustrophedon" is an ancient Greek word and means zigzag. Actually, it means "like the ox plows" and describes, especially in epigraphy, a way of writing where the first line is read from left to right and the second from right to left. What is it good for? If a text is written on a long wall, you only have to take half as many steps to be able to read everything.
Fun fact of the day!
The bird sounds like a whole flock combined. Like a meta-consciousness running on several birds at the same time to speed up the computation necessary to contribute to this video.
BABE WAKE UP MY FAVORITE TH-camR JUST DROPPED ANOTHER BANGER
babe wake up new Physics for the Birds upload
Thank you very much for the video. It’s a surprisingly interesting topic :D
13:00 this reminds me of the punchline at the end of the intro to Dylan Beattie's "Art of Code".
Tom Scott showed the origami they used for spacecraft solar panels that only take 1 axis to fold/unfold. It's quite genius for a quick map
Sure, this appeared just when I got hyperfocused on paper planes. (Dammit now I have 2 hyperfoci what do I do)
This feels exactly like the problem of finding an equation for prime numbers. Each additional step, whether it be the construction of the number line or a valid fold pattern, seems to add a new "fundamental" property to the system that can only be checked algorithmically with some O(n) that is greater than linear.
11:00 Boustrophedon doesn't mean zig-zag, it means "as the ox plows" as in plowing a field. Zig-zag has sharp points as the ends, boustrophedon has 90° turns.
I get so excited when I see a new bird upload
1oved this one now l wanna see someone compute 8x8 on a DS
This video got me thinking about folding things
Did the math take into consideration the crease direction as a constraint? Like if the map was creased and folded in 1 direction, you avoid folding in the opposite direction. When a single line is creased in just 1 direction, you can't fold perpendicularly to that line before folding the line itself. Even with both directions mixed in a single line, it would also constrain what folds to make before that as to avoid overlapping creases that are same-direction before the fold and opposite each other after the fold.
These are always great!
The variable being lowercase "l" is the plot twist I did not see coming. :'D
man i guess you could say that variable choice was a big l
In 6th grade I asked my math teacher if you could math out origami patterns and he said "yeah, probably." I had never seen an honest reaction from a mathematician before then
Hey the video is soo great, but please lower or change a bit the bird voice part, because it's very hard to concentrate and read properly. But anyway, the concept for future implementation of optimal pathfinding in autonomous routing is very interesting!
This is why you take the gigachad approach. Scrunch it into a ball and throw it into the back seat.
You called the ways to fold it mountain and valley style. Finally someone who knows what it's actually called.
Sick and tired of everyone calling it hamburger and hot dog style. You don't even fold hamburgers!
I'm fairly certain "mountain" and "valley" refer to convex and concave foldings, respectively.
Whereas "hotdog" and "hamburger" refer to whether the larger or the smaller edge of the paper is being folded in half: smaller edge is being folded = hotdog, longer edge being folded = hamburger
Another example could be a 3d printer doing a layer's solid infill pattern. The nozzle needs to move back and forth filling the area, but it has to fit within the 2d shape of the layer and you want to minimize the amount of time the nozzle travels without pushing out filament.
Hello, the code @9:35 makes sense to me and seem to be equivalent. I am confused about only one if condition (the hardest one perhaps lmao). This is how I understand the code:
"delta = c[i, l] - c[i, m]
d[i, l, m] = 0
if m != 0 then
if delta is even then
if c[i, m] is 1 then
d[i, l, m] = m
else
d[i, l, m] = m - P[i-1]
else
if c[i, m] == p[i] > m + P[i-1] > l then #this is the if condition I only partially understand lmao.
d[i, l, m] = m
else
d[i, l, m] = m + P[i-1]"
My best guess for the if condition is there must've been a typo lol. What do you think? Cause if they f-ed up 1 and l then they can do a mistake like this too?
Edit: I am a robotics masters (hopefully a PhD student soon) and cleaning robots are dumb af. Most of these papers are just for cases when you want to try out a new algo for funsies. That being said some companies do have fancy algorithms.
PS, I think you have irked my curiosity and I think you have gained a subscriber. Hoping to see more cool videos from you!
A bird complaining about monospace l's and 1's in a map folding video talks about snake for 1/10th of the video.
XD great video!
Physics bird os still around, I can rest easy
These kinds of pseudocode are oftentimes just the _worst_ for readability. Once spent several weeks trying to understand a piece of pseudocode in a paper like this and it turned out to be just a heuristic search, basically a variation on A*, but it was so riddled with symbols defined five pages earlier that it was near incomprehensible
i can fold a map into a hilbert curve? i thought the point of folding was to take up less space, not fill it!
HES BACK!
It is absolutely hilarious to me that the paper might be wrong in this specific place for so long
Love the video!
Would it be possible to model the folds by showing the corner of each square as a gradient of color, such that each fold along a given axis increases the Hue or Saturation based on the number of folds in a given direction with a split should it flip directions, like tree rings.
This way you can run a color comparison analysis to identify duplications that erroneously increase the count?
Think of it like folding a burrito. You fold in the left, bottom, right, and roll it up. It doesn't matter what orientation the ingredients are in, as you've oriented them based on your reference frame.
The insight that 2d paths are just folded string blew my mind.
4:43 there is a pretty good way to fold into 3 without 2 extra folds. By rolling it.
Bang-on right! At first I thought "Isn't that just like guessing to jiggle a 'Z' fold just right?" But I realized you mean to roll up two turns _so that the ends line up_ before squishing. That is not only pretty good but-for infinitely thin paper-perfectly exact.
Loved the bird looking unimpressed
I didn't care for the bird's staticky little voice (your voice is much more enjoyable) but otherwise, incredible video! Your illustrations were very clear. Well done!
You wanna know a secret? The bird's voice _is_ mine... (speaking syllables that python splices together to form English words that are transcribed into Japanese kana and then pitch-shifted to match actual bird calls)
@physicsforthebirds Dang, I've been bamboozled! Very creative process though
wanna know another secret? the “human” voice is just bird calls pitched down and restructured to approximate English sounds
What’s strange is if you care about the entire folding process, tracking the order you make every fold in rather than just the finished product, counting the number of foldings becomes so much easier:
The folds can be done in any order: on an mxn sheet of paper, there are (m+n-2)! different orders, and at each step, you can fold the paper one of two ways, so 2^(m+n-2).
In general, a piece paper with n folds can be folded in n!*2^n ways! You’ll get several of the same maps at the end, so this doesn’t actually solve the problem in the video, but it’s about the journey, right?
The industry I work in has a bad habit of using the letter I next to the digit 1 so I feel your pain there.
I really wish the default font in every app differentiated these three letters. 1Il
great. now I'm gonna spend all night figuring out how to fold a map into a spiral
I will always subscribe for mathy folding shit, especially if it's got nightmare pseudocode in it. Thank you.
ill try it!
i feel like this video is gonna trigger enough attention that someone figures out a like sublinear/constant alg
You said in the video that it would take between 3 and 10 years to get an 8x8. Do you know if the algorithm is parralelizable? Then maybe we can split it between 100 computers and get it done in half a year.
Does something like Folding@Home, where you are calculation folding proteins, use the same math? Or is it something different?
I was taught to fold a map only two ways, and I only remembered the accordion one. Probably just stick to that if you can't shove it all into your bag
I believe the most common algorithm for robot vacuums is random. It just goes in a direction until it hits something, then turns a few degrees, and continues like that. Finding it's way home is similar, but it uses some sort of signal, perhaps IR to track it's goal once it randomly gets close.