POV: you and your N-1 human friends watch a squad of robot overlords doing a funny dance in order to synchronize their movements perfectly so they can execute all of you at the exact same time
The weird thing about these types of videos is that visually you can see it work, follow it, and it appears simple. But there are likely pages of math computations that prove this out that never get shown. I'd never follow it, but I'd like to see the math behind it.
@@jjwkoesterI prefer phrasing that as "You have truly understood a complex concept when you can describe it in a simple manner." It feels more positive, in my opinion :)
My thoughts went to waveform interference; the robots act as a medium where you’d normally use water for a demonstration. Eventually the waves bounce enough times to synchronize a “destructive” wave, clearing the signal.
I cannot stop laughing at the idea of someone who’s been sentenced to death by robot firing squad, screaming bloody murder while these robots just boogie down to upbeat royalty free music
Its important to have all the robots fire at the same time so that any individual robot won't feel guilty from knowing they had pulled the killing shot.
Nah they can't see past their neighbors nor remember the past, I think they're gonna sleep well tonight after their neighbor signals that it's nighttime. xD
Sometimes the solution to a problem is not solved with careful study and experimention, but with a singular flash of insight. For instance, Archimedes' "eurika" moment, or Newton an the apple.
Thanks for that comment! I felt extremely stupid thinking for many hours and being stuck with some sort of binary counting for a long time. Now I feel extremely proud to have found a solution at all. The solution I found in the end is pretty similar to the one presented in the video.
Huh, that's a neat solution. Mine was to use an iterator at the end of the line, but I'm not sure if that breaks the "finite poses" rule: - Build an arbitrary list of poses greater than the number of robots. - Robot 1 assumes the pose that says "I am number 1!" - Each idle robot looks to its right and assumes the pose one higher than that (unless right is also idle). - When you get to the end, you've counted all the robots! - The last robot (which sees a blank space next to it) begins ticking down through all the poses ("blank left & not idle = my pose - 1"). - Each other robot, when it sees a robot with the same pose on its left, ticks down one pose. - When the robots declare "We are number 1!" ("I am number 1 & left is number 1") they're ready to tick over into "Firin' ma lazor!".
needs to work for ANY finite size of squad, but you have to define A finite amount of poses in your solution. If you can find a finite quantity that is greater than any other finite quantity, hit me up.
It does break the finite poses rule, as there must be one finite set of poses and rules that works for ALL finite squads, -- so no matter how many poses you have, there is a squad with more robots than you have poses.
@@aa01blue38yeah but i can also come up with one more pose than your biggest squad. even with countably infinite robots i could come up with countably infinite poses and one more
Imagine being on death row for committing several war crimes, and you're sentenced to death via firing squad. As an extra punishment, they have you executed via 128 robot soldiers that do this, and at 15 BPM
Alright, let’s take out some math and see how long it would take. Seeing as the BPM is 15, one beat will take 4 seconds, so we will multiply the number of beats by 4 to get the time in seconds. We now check if 128 is a perfect power of 2. It is, being the 7th power of 2. We don’t need any double general rules. The first hand signal will take 3n/2 beats to propagate to the end and back to the middle. Our squad is 128 robots, so 3(128)/2 = 192 beats. Our squad is now split into subsquads of 64 robots. 3(64)/2 = 96 beats. 192 + 96 = 288 beats so far. Now we have subsquads of 32. But here’s where we employ a neat trick. Because our squad size has been divided by 2 each time, so has our number of steps to division. We can simply divide the previous number of steps by 2. 96 / 2 = 48 beats. We can verify this fact by also evaluating the old steps formula. 3(32)/2 = 48 = 96 / 2. 288 + 48 = 336 beats so far. Subsquads of 16. 48 / 2 = 24. 336 + 24 = 360 steps so far. Subsquads of 8. 24 / 2 = 12. 360 + 12 = 372 beats so far. Subsquads of 4. 12 / 2 = 6. 372 + 6 = 378 beats so far. Subsquads of 2. 6 / 2 = 3. 378 + 3 = 381 beats so far. Now we simply add 1, representing our final firing order, to get a grand total of 382 beats from start to firing. Now let’s evaluate the time in seconds. We simply multiply our number of beats by 4 to get 1528 seconds. Now how long is that in seconds _and_ minutes? One minute is 60 seconds, so we divide 1528 by 60, keeping the remainder as the number of seconds. We get our final answer of an insane *25 minutes 28 seconds.*
However, due to a design flaw, in the time the robots take to finish the sequence and set up for firing, the prisoner has already broken free from their restraints, disarmed the guards and escaped over the side of the wall.
You think you can escape them? They may be slow and limited to finite state machine commands, but they are immortal and relentless. Better to die by the merciful hand of a laser gun than huddling in a dark cave dreading your coming doom
We went from sorting robots to laser firing squads. Amazing. Is there a cut version of just the "dancing" robots out there? Did you hand-animate each squad or did you create a utility to do these in practice animations for you?
Ah, thank you for the reply. I'll glad if you do release one eventually. I may or may not imagine a tool that can synchronise the firing squad(s) to any song given a BPM and be laughing much too hard at all the inappropriate results. Dang it, now I want to see "Robot execution synched to _I Will Survive_". I hope you enjoy the thought as much as I do.
One thing to point out here is that since the state transitions of each robot only depend on their immediate neighbors, you don't have to have any knowledge of how big the pool of robots is. But if you added a little bit of memory, you could probably arainge it so that once the synchronization event takes place, every robot knows what their position in the line is, up to some limit.
I just wrote this out replying to a different comment, and it does work, and faster than the video's algorithm. You can just use a 128-bit number that guarantees it can store the number of computers in the system (64 bits is almost certainly sufficient and 16-32 bits is overkill in most real cases, but there aren't even 2^128 atoms in the observable universe, so it's guaranteed). Each robot has 128 "legs" with two states (representing a single 128-bit number), then the "hands" tell it whether the signal is coming, going or idle. So computer 1 gets the start signal, says "leaving", "1" to its neighbor. The neighbor sees "leaving", adds 1 to the count and propagates "leaving", "2" to the next neighbor. This proceeds to the last computer, which holds the final count of computers, "N". After the right-hand neighbor is set to "leaving", the current computer can return to idle or just sit in the current state. The final computer sees that it's final and switches to "returning", "N". The penultimate computer sees "returning" and also switches, but subtracts 1 from the current count to be "returning", "N-1". This repeats back to the beginning. The difference on the return trip is that after the state is "returning", each computer counts down by 1 every tick. So the "returning" signal will hit computer 2 when the count is "2", but every computer to its right will also have counted down to 2. As computer 1 sets its state to "returning", "1", computer 2 counts down once to "1" (along with all the other computers). Now, all the computers count down once to zero and fire. Alternately, they could all fire at 1, and computer 1 knows to fire next tick if the computer to its right says "returning", "2" this tick. For N=11, the video took 34 ticks, where mine will do it in 21 ticks (10 "leaving" ticks, then 11 "returning" ticks, since the last computer can transition from idle directly to "returning", "N" and skip the "leaving" tick). Even better is if whatever method you're using to synchronize ticks just counts all the computers each time and you can just store the total computers plus a given computer's place in line. Then *any* computer can originate the signal and start the count based on the farthest distance from it (a middle computer would start at N/2, for example). If one computer sends a signal after another already did, but before it knows about the signal, all computers seeing both signals can just use the lowest count.
As a musician I very much appreciate that you synced the music, it annoys me to no end when stuff like this is put to random music that doesn't sync and it takes work to sync something like this so well, I owe my life to you.
I'd like, but I'm afraid that I might cause an unsigned integer overflow to 0. If there is no integer overflow though, I will like because I was wrong. (back when it was at 255 likes)
Actually this is a real engineering problem. Its from computer science, and the practical considerations are (Surprisingly enough) in computers. When computers are involved, each machine can be far enough away that only adjacent machines on the network can talk, and synchronisation of certain tasks can be important. This is the engineering side of it. It's a bit like the two generals problem - its seems silly to talk about, and like its just a problem for the sake of logic and maths, but its something that actually needs to be considered when dealing with computer networks.
@@KavsLockedOut daisy chain a bunch of computers together, have first one connected to the server and then have them try play epic dubstep hardest beat drop (not clickbait) (almost died) (shot my neighbors cat with a sawed off) (working 2021) (working free robux) (no survey) (no virus) simultaneously if you mess up it's just going to sound like a loud cacophonous mess rather than a loud mess
@@KavsLockedOutLong distances in areas with lots of interference could do that easily. Networks of low power devices (not full computers) that can't afford to be constantly transmitting - to name two situations. A slightly different situation is in digital logic circuits - a circuit built on the transistor level. Memory requires a fair number of transistors to make work, but logic states are much easier. Connecting everything to everything may not work just based on space - transistor circuits can be absurdly small.
Executioner: "If you can figure out how to make this robot firing squad fire simultaneously using only body language from neighbors, we'll commute your sentence." Prisoner: "Logic problem? Ugh, just kill me." *robots dance* Prisoner: "Ohhhh, that's ho- *LASERED*
I like that the leg signal is basically the countdown. In the time it takes for it to move from the first to the last robot, all the other signals would have been set to fire
The best part of this is that there's actually a practical application for simultaneous mechanisms. As long as their clocks are synchronized, pinging the nearest two devices with your state and updating accordingly should allow for simultaneous firing of whatever thing needs to be simultaneous. And if you put it in a machine, the order could carry across the line and back nearly simultaneously!
"there's actually a practical application for simultaneous mechanisms" "whatever thing needs to be simultaneous" Sorry bud but you're not making the greatest point. This argument does prove however that this could happen in real life, so it is a step toward making this useful.
Almost as though almost every analogue mechanical device is consistently simultaneous, and this is a superflulous example. You've really not said anything here that isn't already implied, and frankly I've lost some faith in the intelligence of humanity.
@TailExchange can you trust that clock tough? are you sure your thread is not pushed to the back and almost forgotten about when the others are having fun. or when you're communicating with other systems and somehow their message takes a freaking long time to arrive... I'm not stressed working with multi-threaded web services, what are you talking about :p
If every robot can measure time and can perform actions instantly, it should be pretty easy - every robot performs action exactly on beat, to act as a basic synchronous clock. Before starting the execution dance, they sync their clocks. The leftmost robot sends out a sync signal with no information. It gets passed like the "hand up" signal in the video, bounces back and comes back to the leftmost robot. Every robot automatically syncs their clock to the robot left of them. Only after leftmost robot receives the returned sync signal, the main execution dance begins.
"Many years later, as he faced the firing squad, Colonel Aureliano Buendía was to remember that distant afternoon when his father bonked a robot on the head" -one hundred years of solitude
Imagine being in death row and the executioner starts arkwardly dancing while everyone is super serious. I would die laughing sooner than he would have shot me down lol
Meanwhile in terminator 5: „Mom? Why are the robots dancing?“ „Oh no, we are dead in 20 seconds! Give me one last hug“ „I love you mom“ „I love you son“ .... One eternity later Piu piu piu
Why the leg has three stages: the hand signal must travel three times faster than the leg signal because it has to travel three halves while the leg signal only one so that they meet in the middle.
And multiple leg signals to handle even or odd amount of squad members since with an odd amount you will have a single person in the middle but with an event amount there will be 2 middle men
I thought about splitting the problem along the middle of the line, but I didn't think about sending a signal that is 3 times slower than another. Beautiful solution!
Here I was trying to solve the problem not knowing you could have a leg and a arm state separate from one another, you made it sound and look like it was all one state.
@Michael Darrow I know. But Wolfram studied the 2 states 1 dimensional and infinite cells cellular automata. The video shows us a 1 dimensional, finite cells and more than 2 states.
I like how this video presents this as a logic or math puzzle but doesn't ever give us the whole picture we need to solve it until *we're already* at the solution.
I like how the music and the dancing is all cute to watch, but what they're actually doing is getting ready to kill you, since your point of view is that of the condemned. XD
Before the moment to pause and think about it, you probably should have explained that a robot could give two signals simultaneously, and explained that a signal could take more than one beat. Also, how many signals are allowed? If the number of signals is as arbitrary as the number of robots (can change with the number of robots), then the solution is easy. (Though the wording seems to imply that the number of states needs to be the same between all robot numbers?) The robots only need to know the signal of the robot to their right. It will be a countdown starting with a signal representing the number of robots. When a robot sees a numbered signal next to it, on the next step, it gives the signal of n-1. This repeats until the signal of countdown has propagated to all robots and they all fire.
There is no limitation on signals, as "signals" are just our human way of thinking about this. The problem description only mentions a finite number of states and a finite number of transitions, which has nothing to do with signals. Every combination of a hand signal, foot signal, including direction, is a completeley seperate state with accordingly completely seperate transitions. It is easy to describe them all by thinking of them as individual "signals". This is why a large portion of the video is about handling odd numbers of robots, as it is not obvous how these signals are combined in such edge cases. Of course the number of states and transitions should not be dependant on the number of robots, since you can not pre-program that behaviour. If you programmed it for 1000 robots, but then had to do it with 1001 robots, you would need to reprogram all robots to allow for the extra states and transitions.
This is one of those lesson introductions one of my old professors would use right before launching into the history of statistical mechanics and how simple models can show phase changes in materials.
Thanks for posting. This is just about the proudest I've ever been of solving a logic puzzle. The crazy thing is that as complicated as the solution is, most of it is actually forced by the constraints of the puzzle. There are a few different ways of dealing with parity issues. But most parts of the solution are provably required.
I have a copy of the 'Computation' book by Minsky-- college text book. This problem is basically the only thing I specifically remember from the book and it has always intrigued me. When I saw the video title I knew immediately what the topic was about. I'm still, to this day, curious what the 2n-2 step solution is. The book claims the soldiers in that solution have 1000's of states, but the link in the description says "Optimal solution: The fastest solution to this problem uses 2n-2 steps. There’s a proof this is the best possible time. It uses also only 6 states. It is not known whether this is optimal or not."
This excellent! Very well presented, and it brought back happy memories of reading Edsger Dijkstra's paper, "Self-Stabilizing Systems In Spite of Distributed Control", back in the day. Thank you.
Before I watch the solution: My idea is to start with two chain reactions moving with different speeds to the right. One that moves right every beat and another one that moves forward every third beat by cycling through three different states. The faster one bounces when it hits the right end of the line, which means the “waves” will meet each other exactly in the middle. When the waves hit each other, they should release four waves, two to the right and two to the left with similar speeds as in the beginning. This will essentially divide the line into two equal parts in which the process will be repeated, diving the line into smaller and smaller similar pieces. We want the robots to fire when the line can’t be divided any further. The robots notices this when two fast waves collide right next to slower beams, which indicates that the beams collided right after they got released. This is by no means a complete solution, but I don’t think the details matter that much.
That's essentially the solution in the video. Count the number of states that the robots use. Now try to do it in as few states as possible and in the shortest time possible. A friend of mine solved that as a PHD thesis. Unfortunately a second researcher was faster in publishing his solution. 6 states is current minimum, 5 states are not proven to be possible or impossible yet.
I didn't even attempt to solve it, but my first instinct was "set up some sort of wave that constructively interferes at the end". I was missing the two other critical insights: send two waves at different speeds and make them collide. Also, I want to see a 200 robot execution.
Would be nice to see the truth tables, or the Karnaugh maps, how you build and solve the logic process. Thank you for this. I once used a Johnson counter (one for each robot) and a logic array to build it.
At first I was having trouble grasping it, but everything came together by the. Then I just watched it several more times because it's such a fun video.
The interesting thing here is, unless I’m mistaken, this task was solved by humans. I’d love to know how many iterations it would take for an average computer to solve the problem starting with no prompting except for the arm, leg and body movements. In other words by A.I.. I would have guessed it would have taken many hundreds of thousands of iterations before even the simplest problem would be solved. What do other people think ? I’ve seen other channels where problem solving is taken on by computers, and sometimes the results are quite amazing, but most take hours.
2D: Assuming each robot can see the 8 neighbours around it, and that the lower left robot is the one that gets activated at the start, do the following: The robots on the lower row of the rectangle perform the hand and foot signals as shown in the video, up until they all turn into generals. The robots in the row above will notice that all robots below them have turned into generals. At this point, they will simply perform the exact same dance going vertically. Eventually ALL robots will become generals and they shoot. It should be easy to see how this can be generalized to any number of dimensions.
"We need to do something in sync, which is a challenge because they can only see their neighbors. Anyway, to solve this problem, let's assume they're magically synchronized to an ethereal drum beat."
I have a simple solution which might be a bit cheaty, but here it is: You could create a sequential counting system with the positions of arms and legs: starting at bottom-dead-center to represent the value of zero. Rotating the limb one radian clockwise would be adding one, and rotating the limb one radian CCW would be subtracting one. Since the amount of radians in a circle is irrational, you will never have two identical values. The first robot sets it's leg to a value of 1. The leg value travels down the line with each robot increasing the previous leg value by one. Once the last robot receives the signal, it will set it's arm to the same value of the leg. Each robot will copy the arm value of the adjacent robot, minus one. When the arm is at a value of zero, fire. Since you would only need as many values as there are robots, and the amount of robots is finite, the amount of states is therefore finite.
not a bad solution, but it doesn't fit the constraint of 'finite set of states that work for any number of robots', you need a different sized set for each number of robots, or an infinite set if you want it to handle any number.
It's odd I came across this when I did, I had just come up with a similar solution for syncing groups of objects via signal transferring when I was programming, although my solution was a bit more crude than this. Great stuff!
![Halting Problem & Quantum Entanglement 2020 Breakthrough result [MIP*=RE]](http://i.ytimg.com/vi/2H8629BCbkM/mqdefault.jpg)
“Yeah, we had some budget cuts this year, so we can’t go with the executioner robots.”
“What are we using, then?”
“The dancers.”
Hey, at least they’re programmable
I think it‘s the different way a round
how are there TWO replies and 2k likes
The Clone Wars in a nutshell!
Roger Roger Now launching, Just Dance!
POV: you and your N-1 human friends watch a squad of robot overlords doing a funny dance in order to synchronize their movements perfectly so they can execute all of you at the exact same time
I like how this post accounts for people with no friends lol
What a lovely story
@@art1637 According to the description N>=3. You will need at least 2 friends.
@@emielverbeeren8181So if I have 0 or 1 friends I cant be executed by groovy robots? :(
imagine being sentenced to death by a robot autocracy, and the last thing you see before you die is your executioners just grooving
The war of the sorting robots
"Sargent, give the order."
"Yes sir."
*Bonk*
"What are they doing, Sargent"
"Grooving, sir"
The goofiest dystopia.
If it's execution by groovin robots I'd be more than willing to accept my fate
Instead of being blindfolded, you get a nice visual before you get fucking murdered.
The weird thing about these types of videos is that visually you can see it work, follow it, and it appears simple. But there are likely pages of math computations that prove this out that never get shown. I'd never follow it, but I'd like to see the math behind it.
The weirder part is THIS is the more difficult to understand version 🤣
There’s a quote that says “if you can’t explain something simply, then you don’t understand it well enough”
@@jjwkoesterI prefer phrasing that as "You have truly understood a complex concept when you can describe it in a simple manner." It feels more positive, in my opinion :)
@@Catman_CMand in general fairness, more correct.
My thoughts went to waveform interference; the robots act as a medium where you’d normally use water for a demonstration.
Eventually the waves bounce enough times to synchronize a “destructive” wave, clearing the signal.
I cannot stop laughing at the idea of someone who’s been sentenced to death by robot firing squad, screaming bloody murder while these robots just boogie down to upbeat royalty free music
well it's more or less an abstraction of the Colonel Bogey March, hardly royalty free style.
“Here’s a robot firing squad” is possibly the most ominous first line in any RUclips video
LMAO
Tom Scott
*proceeds to activate robot firing squad that is facing towards you*
But very effective
“vsauce, Michael here”
Its important to have all the robots fire at the same time so that any individual robot won't feel guilty from knowing they had pulled the killing shot.
Guitly, or perhaps satisfied
Nah they can't see past their neighbors nor remember the past, I think they're gonna sleep well tonight after their neighbor signals that it's nighttime. xD
nooo u can’t just break the first law of robotics
machine gun goes brrr
@@kaidatong1704 if nobody saw it its not a crime
@@happmacdonald that nighttime bit got mw
"pause if you want to think about it"
Meanwhile on the screen: "problem proposed in 1957, solution found in 1967"
Think i'll pass.
Sometimes the solution to a problem is not solved with careful study and experimention, but with a singular flash of insight. For instance, Archimedes' "eurika" moment, or Newton an the apple.
@@extraintelligence I think OC accepts he isn't Archimedes or Isaac Newton
@@kurumi394 not with that attitude.
@@extraintelligence Not with that name, either
Thanks for that comment! I felt extremely stupid thinking for many hours and being stuck with some sort of binary counting for a long time. Now I feel extremely proud to have found a solution at all.
The solution I found in the end is pretty similar to the one presented in the video.
Huh, that's a neat solution. Mine was to use an iterator at the end of the line, but I'm not sure if that breaks the "finite poses" rule:
- Build an arbitrary list of poses greater than the number of robots.
- Robot 1 assumes the pose that says "I am number 1!"
- Each idle robot looks to its right and assumes the pose one higher than that (unless right is also idle).
- When you get to the end, you've counted all the robots!
- The last robot (which sees a blank space next to it) begins ticking down through all the poses ("blank left & not idle = my pose - 1").
- Each other robot, when it sees a robot with the same pose on its left, ticks down one pose.
- When the robots declare "We are number 1!" ("I am number 1 & left is number 1") they're ready to tick over into "Firin' ma lazor!".
It specifically mentions a squad of any FINITE size, so I would argue your solution is more elegant and exactly where my head went with this one!
needs to work for ANY finite size of squad, but you have to define A finite amount of poses in your solution.
If you can find a finite quantity that is greater than any other finite quantity, hit me up.
It does break the finite poses rule, as there must be one finite set of poses and rules that works for ALL finite squads, -- so no matter how many poses you have, there is a squad with more robots than you have poses.
@@aa01blue38yeah but i can also come up with one more pose than your biggest squad. even with countably infinite robots i could come up with countably infinite poses and one more
we are... number... One...?
*Props to the cameraman for standing there and being shot with lasers so many times just to get us this awesome video!*
everybody gangsta until the firing squad starts dancing
imagine youre been sentenced to firing squad and you have to stand there watching for 30 min while they dance and figure out when to fire
This is a pretty effective intimidation tactic
It's like being executed by the Ginyu Force.
@@pvic6959 They do a full musical number about their lives as members of a firing squad, and your death comes on the last beat of the song.
I don't think anybody gangsta if your on the receiving end of the firing squad
Imagine being on death row for committing several war crimes, and you're sentenced to death via firing squad. As an extra punishment, they have you executed via 128 robot soldiers that do this, and at 15 BPM
Stop trying to escape! We have to reset the process every time you do that.
I would love this. thank you.
The fucking suspense that would create
Alright, let’s take out some math and see how long it would take.
Seeing as the BPM is 15, one beat will take 4 seconds, so we will multiply the number of beats by 4 to get the time in seconds.
We now check if 128 is a perfect power of 2. It is, being the 7th power of 2. We don’t need any double general rules.
The first hand signal will take 3n/2 beats to propagate to the end and back to the middle. Our squad is 128 robots, so 3(128)/2 = 192 beats.
Our squad is now split into subsquads of 64 robots. 3(64)/2 = 96 beats. 192 + 96 = 288 beats so far.
Now we have subsquads of 32. But here’s where we employ a neat trick. Because our squad size has been divided by 2 each time, so has our number of steps to division. We can simply divide the previous number of steps by 2. 96 / 2 = 48 beats.
We can verify this fact by also evaluating the old steps formula. 3(32)/2 = 48 = 96 / 2.
288 + 48 = 336 beats so far.
Subsquads of 16. 48 / 2 = 24. 336 + 24 = 360 steps so far.
Subsquads of 8. 24 / 2 = 12. 360 + 12 = 372 beats so far.
Subsquads of 4. 12 / 2 = 6. 372 + 6 = 378 beats so far.
Subsquads of 2. 6 / 2 = 3. 378 + 3 = 381 beats so far.
Now we simply add 1, representing our final firing order, to get a grand total of 382 beats from start to firing.
Now let’s evaluate the time in seconds. We simply multiply our number of beats by 4 to get 1528 seconds.
Now how long is that in seconds _and_ minutes? One minute is 60 seconds, so we divide 1528 by 60, keeping the remainder as the number of seconds. We get our final answer of an insane *25 minutes 28 seconds.*
and the first cycle is a sike
However, due to a design flaw, in the time the robots take to finish the sequence and set up for firing, the prisoner has already broken free from their restraints, disarmed the guards and escaped over the side of the wall.
@@Warze And that's why you don't drink while designing your robotic executioners.
You think you can escape them? They may be slow and limited to finite state machine commands, but they are immortal and relentless. Better to die by the merciful hand of a laser gun than huddling in a dark cave dreading your coming doom
Rearrange them into a circle so that the left leg signal can never meet the right hand signal.
@@stelcxantisto nah just make this the josephus problem and get it over with
Just get one robot
We went from sorting robots to laser firing squads. Amazing.
Is there a cut version of just the "dancing" robots out there? Did you hand-animate each squad or did you create a utility to do these in practice animations for you?
Thanks! It's procedural animation. Yes, a cut version is a nice idea, I'll consider doing that with a few more runs.
Ah, thank you for the reply. I'll glad if you do release one eventually.
I may or may not imagine a tool that can synchronise the firing squad(s) to any song given a BPM and be laughing much too hard at all the inappropriate results. Dang it, now I want to see "Robot execution synched to _I Will Survive_". I hope you enjoy the thought as much as I do.
@@udiprod i need a version without a beats, just a nice continuus flow of dance and moves.
One thing to point out here is that since the state transitions of each robot only depend on their immediate neighbors, you don't have to have any knowledge of how big the pool of robots is. But if you added a little bit of memory, you could probably arainge it so that once the synchronization event takes place, every robot knows what their position in the line is, up to some limit.
The entire point of this is that no such construct is needed.
That said it has "memory", as a whole unit.
I just wrote this out replying to a different comment, and it does work, and faster than the video's algorithm.
You can just use a 128-bit number that guarantees it can store the number of computers in the system (64 bits is almost certainly sufficient and 16-32 bits is overkill in most real cases, but there aren't even 2^128 atoms in the observable universe, so it's guaranteed). Each robot has 128 "legs" with two states (representing a single 128-bit number), then the "hands" tell it whether the signal is coming, going or idle.
So computer 1 gets the start signal, says "leaving", "1" to its neighbor. The neighbor sees "leaving", adds 1 to the count and propagates "leaving", "2" to the next neighbor. This proceeds to the last computer, which holds the final count of computers, "N". After the right-hand neighbor is set to "leaving", the current computer can return to idle or just sit in the current state.
The final computer sees that it's final and switches to "returning", "N". The penultimate computer sees "returning" and also switches, but subtracts 1 from the current count to be "returning", "N-1". This repeats back to the beginning.
The difference on the return trip is that after the state is "returning", each computer counts down by 1 every tick. So the "returning" signal will hit computer 2 when the count is "2", but every computer to its right will also have counted down to 2. As computer 1 sets its state to "returning", "1", computer 2 counts down once to "1" (along with all the other computers).
Now, all the computers count down once to zero and fire. Alternately, they could all fire at 1, and computer 1 knows to fire next tick if the computer to its right says "returning", "2" this tick.
For N=11, the video took 34 ticks, where mine will do it in 21 ticks (10 "leaving" ticks, then 11 "returning" ticks, since the last computer can transition from idle directly to "returning", "N" and skip the "leaving" tick).
Even better is if whatever method you're using to synchronize ticks just counts all the computers each time and you can just store the total computers plus a given computer's place in line. Then *any* computer can originate the signal and start the count based on the farthest distance from it (a middle computer would start at N/2, for example). If one computer sends a signal after another already did, but before it knows about the signal, all computers seeing both signals can just use the lowest count.
@@GeekOfAllnessyou're using memory to run in linear time, whereas the memory-less version runs in log time. Not so strange.
Since they have no memory all they know is that since they’re not a general yet the group must be bigger
the more green-lit generals i see, the more nervous i get.
Probably because you are the prisoner from abusive AI usage (AI torture for music generation)
POV: You get killed by the robot firing squad after committing genocide on 2 music AIs
TIL cary watches udiprod
The living legend himself
I keep seeing you in every comment section lol
This video felt like some kind of AI is trying to trick me into progamming a dissident-killing subroutine for it.
Lol
Lmfao
no bueño
Skynet: "Dammit, they're onto us!"
As a musician I very much appreciate that you synced the music, it annoys me to no end when stuff like this is put to random music that doesn't sync and it takes work to sync something like this so well, I owe my life to you.
I agree.
The only problem is that the robots dance in 3/4 and the music is in 4/4.
@@emil.pettersson05 that's called an ostinato, looks like it's intentional here, so no problem :)
@@emil.pettersson05 anything can be a waltz if you try hard enough
How do you want to pay?
Football star: gets brutally injured.
The cheerleaders; 7:20
I am so incredibly grateful that you finished off the video by just giving an opportunity to watch the robots do their thing a few times. Cool stuff!
I've been sentenced to death but robocop over here can't stop doing fortnight dances to taunt me.
Brilliant!
Until he finishes dancing
Ironically, Robocop is now in fortnite
@@ITSMRFOXYIt's fortnight, Fortnite is the kids version
r/brandnewsentence
Prisoner: *Dances along to the beat*
Warden: *Dances along to the beat*
Shooters: *Dancing along to the beat*
Prisoner: *Dances away slowly*
I'd like, but I'm afraid that I might cause an unsigned integer overflow to 0. If there is no integer overflow though, I will like because I was wrong. (back when it was at 255 likes)
@@legendgames128 Yes you're very clever, this is youtube.
@@squidgelad1983 but that was a joke, a programing joke
@@legendgames128 Gosh dang it, take your like, you fellow programming punster of a mad lad.
@@legendgames128 I assume 32-bit integers are used, not 8-bit, the real question is, what happens when we exceed 4.29 Billion likes
Engineers: “Just make them all shoot once a signal is given, these constraints do nothing but hamper their functions.”
Mathematicians be like:
Yeah if the whole process is started off by hitting the first robot why not just hit all of them at the same time 😂
Actually this is a real engineering problem. Its from computer science, and the practical considerations are (Surprisingly enough) in computers. When computers are involved, each machine can be far enough away that only adjacent machines on the network can talk, and synchronisation of certain tasks can be important. This is the engineering side of it.
It's a bit like the two generals problem - its seems silly to talk about, and like its just a problem for the sake of logic and maths, but its something that actually needs to be considered when dealing with computer networks.
@@samfriend3675 what situation would result in only adjacent clients be able to talk in a network?
@@KavsLockedOut daisy chain a bunch of computers together, have first one connected to the server and then have them try play epic dubstep hardest beat drop (not clickbait) (almost died) (shot my neighbors cat with a sawed off) (working 2021) (working free robux) (no survey) (no virus) simultaneously
if you mess up it's just going to sound like a loud cacophonous mess rather than a loud mess
@@KavsLockedOutLong distances in areas with lots of interference could do that easily. Networks of low power devices (not full computers) that can't afford to be constantly transmitting - to name two situations.
A slightly different situation is in digital logic circuits - a circuit built on the transistor level. Memory requires a fair number of transistors to make work, but logic states are much easier. Connecting everything to everything may not work just based on space - transistor circuits can be absurdly small.
no clue what i just watched but i can tell whoever came up with it is a genius
This is probably the most random video I've ever watched and I loved every second of it.
Executioner: "If you can figure out how to make this robot firing squad fire simultaneously using only body language from neighbors, we'll commute your sentence."
Prisoner: "Logic problem? Ugh, just kill me."
*robots dance*
Prisoner: "Ohhhh, that's ho- *LASERED*
I like that the leg signal is basically the countdown. In the time it takes for it to move from the first to the last robot, all the other signals would have been set to fire
Not quite. If a robot becomes a double-general while queuing the leg signal, the leg signal is delayed by one beat.
@@DJChiefX197 The point still stands, since the final robot only fires when that final leg signal reaches the end of the line.
@@ryannorthup3148 heh, the point still _stands_
@@ValeBridges heh
@@ryannorthup3148 Puns!
The best part of this is that there's actually a practical application for simultaneous mechanisms. As long as their clocks are synchronized, pinging the nearest two devices with your state and updating accordingly should allow for simultaneous firing of whatever thing needs to be simultaneous. And if you put it in a machine, the order could carry across the line and back nearly simultaneously!
Mmmm, except you fail at the synchronized clocks. Alternatively, you already had a method to synchronize all devices.
"there's actually a practical application for simultaneous mechanisms"
"whatever thing needs to be simultaneous"
Sorry bud but you're not making the greatest point.
This argument does prove however that this could happen in real life, so it is a step toward making this useful.
This is fragile because it supposes that all of your machines are reliable.
Almost as though almost every analogue mechanical device is consistently simultaneous, and this is a superflulous example. You've really not said anything here that isn't already implied, and frankly I've lost some faith in the intelligence of humanity.
@@loganduncan1259 This is an example of swarm behavior, try again.
I love how more rules kept being added so that when he was wrong, he wasn't wrong
those were all part of the solution
Honestly the idea that the robots won't fire their weapons until every single one of them has been promoted to general is hilarious to me.
as a programmer the only issue I see is giving them a beat that is perfectly synchronous so we can do this fast
@TailExchange can you trust that clock tough? are you sure your thread is not pushed to the back and almost forgotten about when the others are having fun.
or when you're communicating with other systems and somehow their message takes a freaking long time to arrive...
I'm not stressed working with multi-threaded web services, what are you talking about :p
I want to see a simulation where each robots propagate their signal at very slightly different rate and see how bad the desync is gonna be..
@@Elizhium maybe set a time when the beat should start and have a hardcoded beat?
If you had a server, you wouldn’t need the dancing.
If every robot can measure time and can perform actions instantly, it should be pretty easy - every robot performs action exactly on beat, to act as a basic synchronous clock.
Before starting the execution dance, they sync their clocks. The leftmost robot sends out a sync signal with no information. It gets passed like the "hand up" signal in the video, bounces back and comes back to the leftmost robot. Every robot automatically syncs their clock to the robot left of them.
Only after leftmost robot receives the returned sync signal, the main execution dance begins.
"Many years later, as he faced the firing squad, Colonel Aureliano Buendía was to remember that distant afternoon when his father bonked a robot on the head"
-one hundred years of solitude
Can we have 10 hours of these robots please
Yes just a stream where after firing it adds another robot
@@walksanator 10/10 would watch
Please
follow up problem: "at 2 beats per second, what number of robots would take (closest to) 10 hours to fire?"
@@walksanator Oh that's a nice programming challange
Imagine being in death row and the executioner starts arkwardly dancing while everyone is super serious. I would die laughing sooner than he would have shot me down lol
Amazing. It's incredible to see what can be accomplished with ratios and 3n.
Imagine being sentenced to death by firing squad during the robot uprising, and your last sight is a bunch of robots dancing to coordinate your demise
Ive seen this algorithm before with just colored cells, but its so much easier to visualize with the robots.
Now we just need twenty people to learn the choreography for this and do it as a stage performance.
The audience might not like the plot twist at the end.
@@hueyiroquois3839 Dead men tell no tales
@@hueyiroquois3839 What are they gonna do about it?
@@hueyiroquois3839 Maybe, but they won't live to tell the tale. (Hides mousin negate behind back)
...why... 🤦♂️
n=17 is my favorite. The pirouettes and the high notes make me giggle.
Maths is beautiful AND deadly. I love it.
This will probably get recommended again over 6 years. See ya there.
8:05 Imagine this is the last thing you see before you die.
id die amused and that wouldnt be terrible lol
They be groovin'
I'd be pretty amused
Imagine a future where they need 20 coordinated robots to kill you.
sometimes I come back to this video just to watch from 8:05 onwards
Meanwhile in terminator 5:
„Mom? Why are the robots dancing?“
„Oh no, we are dead in 20 seconds! Give me one last hug“
„I love you mom“
„I love you son“
....
One eternity later
Piu piu piu
A Group Of Rebels Moves The Robots From The Beginning To The End Cyclically, Resulting In Them Being Completely Relocated.
@@AssistantCoreAQI „Error, arm signal from right == True and left leg stretched == True not found! Nuclear self destruct in 3, 2, 1“
Why the leg has three stages: the hand signal must travel three times faster than the leg signal because it has to travel three halves while the leg signal only one so that they meet in the middle.
Thank you!
good comment.
That's genius!! Thanks for explaining it to my stupid mind! Now I can truly appreciate the solution!
And multiple leg signals to handle even or odd amount of squad members since with an odd amount you will have a single person in the middle but with an event amount there will be 2 middle men
I thought about splitting the problem along the middle of the line, but I didn't think about sending a signal that is 3 times slower than another. Beautiful solution!
A classic divide and conquer approach. I love the solution, it's beautiful.
Two uploads in a century? God has blessed us
For some reason this is the funniest thing I've seen this week.
Wow, this is a really clever solution, and the procedural animations are impressive! Thank you!
Here I was trying to solve the problem not knowing you could have a leg and a arm state separate from one another, you made it sound and look like it was all one state.
This is a perfect example of a more advanced Turing machine. Great video
Thought this was going to be an impossible problem, but it wasn't. Very neat!
Wow, this is probably the most clever logic puzzle I’ve ever seen.
The mathematical precision of them trying to decide when to kill you is so detached it’s scary. But also I want to dance
Absolutely based that you brought this version back.
imagine being executed and the firing squad does a little jiggle before killing you
Such a fascinating problem and solution!
Wow blue moon today, udiprod uploads
It's always a great day!
It looks like those Wolfram cellular automata, but with finite set of cells in the horizontal axis and with more than 2 states.
It means that this is just 1D automata.
@@charlz-darvin Yes, like all wolfram's automata
@Michael Darrow I know. But Wolfram studied the 2 states 1 dimensional and infinite cells cellular automata. The video shows us a 1 dimensional, finite cells and more than 2 states.
The last bit with the music just had me smiling crazily and don't know why, it bought a lot of happiness
uncanny how cheerful the video is for being about a firing squad
Imagine a army battle vs 2000 or so of these guys
And the enemy is polite enough to wait for them to finish
"Alright, Alright, I'll Wait A Week For You All To Align.. -Sigh.- Someone Knocked The Middle One Over, We Have To Restart It."
It's amazing to see how people can find ways to emulate things like memory and recursion in such simple and restricted systems like this.
All the while, whatever was in the path of 100 robots decided to take a nap and then just leave
I could watch these full runs for hours. It's hypnotizing.
I like how this video presents this as a logic or math puzzle but doesn't ever give us the whole picture we need to solve it until *we're already* at the solution.
I like how the music and the dancing is all cute to watch, but what they're actually doing is getting ready to kill you, since your point of view is that of the condemned. XD
"I love these random educational videos from years ago this is from what? 6 years ago?"
> Last week
Woah, more than one video posted in a year? THIS IS AMAZING!!!
Good RUclips algorithm! A video I would have never found but needed.
Middle of an odd squad general is an absolute chad. Coolest robot in the squad by far
Lmao "this is a robot firing squad" being the first thing, sounds like Mark Zuckerberg and his buddies dislike my being alive.
4:56 when you find the nerf dart that you lost in 2010
Before the moment to pause and think about it, you probably should have explained that a robot could give two signals simultaneously, and explained that a signal could take more than one beat.
Also, how many signals are allowed? If the number of signals is as arbitrary as the number of robots (can change with the number of robots), then the solution is easy. (Though the wording seems to imply that the number of states needs to be the same between all robot numbers?)
The robots only need to know the signal of the robot to their right. It will be a countdown starting with a signal representing the number of robots. When a robot sees a numbered signal next to it, on the next step, it gives the signal of n-1. This repeats until the signal of countdown has propagated to all robots and they all fire.
There is no limitation on signals, as "signals" are just our human way of thinking about this. The problem description only mentions a finite number of states and a finite number of transitions, which has nothing to do with signals. Every combination of a hand signal, foot signal, including direction, is a completeley seperate state with accordingly completely seperate transitions. It is easy to describe them all by thinking of them as individual "signals". This is why a large portion of the video is about handling odd numbers of robots, as it is not obvous how these signals are combined in such edge cases.
Of course the number of states and transitions should not be dependant on the number of robots, since you can not pre-program that behaviour. If you programmed it for 1000 robots, but then had to do it with 1001 robots, you would need to reprogram all robots to allow for the extra states and transitions.
here's the problem to your method, what specifically is "n"? the problem assume that number isn't known
This is one of those lesson introductions one of my old professors would use right before launching into the history of statistical mechanics and how simple models can show phase changes in materials.
Thanks for posting. This is just about the proudest I've ever been of solving a logic puzzle. The crazy thing is that as complicated as the solution is, most of it is actually forced by the constraints of the puzzle. There are a few different ways of dealing with parity issues. But most parts of the solution are provably required.
The new rhythm heaven game looks amazing!
the visual cues seem a bit complicated
I'm not gonna get better then a OK
I have a copy of the 'Computation' book by Minsky-- college text book. This problem is basically the only thing I specifically remember from the book and it has always intrigued me. When I saw the video title I knew immediately what the topic was about. I'm still, to this day, curious what the 2n-2 step solution is. The book claims the soldiers in that solution have 1000's of states, but the link in the description says "Optimal solution: The fastest solution to this problem uses 2n-2 steps. There’s a proof this is the best possible time.
It uses also only 6 states. It is not known whether this is optimal or not."
This excellent! Very well presented, and it brought back happy memories of reading Edsger Dijkstra's paper, "Self-Stabilizing Systems In Spite of Distributed Control", back in the day. Thank you.
Everytime the robots shoot I'm hearing a friendly voice saying: "Now you are dead."
0:00 "Heres a robot firing squad" in a happy and upbeat tone
Before I watch the solution:
My idea is to start with two chain reactions moving with different speeds to the right. One that moves right every beat and another one that moves forward every third beat by cycling through three different states. The faster one bounces when it hits the right end of the line, which means the “waves” will meet each other exactly in the middle.
When the waves hit each other, they should release four waves, two to the right and two to the left with similar speeds as in the beginning. This will essentially divide the line into two equal parts in which the process will be repeated, diving the line into smaller and smaller similar pieces.
We want the robots to fire when the line can’t be divided any further. The robots notices this when two fast waves collide right next to slower beams, which indicates that the beams collided right after they got released.
This is by no means a complete solution, but I don’t think the details matter that much.
That's essentially the solution in the video. Count the number of states that the robots use. Now try to do it in as few states as possible and in the shortest time possible. A friend of mine solved that as a PHD thesis. Unfortunately a second researcher was faster in publishing his solution. 6 states is current minimum, 5 states are not proven to be possible or impossible yet.
Sure bud
This has to be the most upbeat tune I've heard while being executed by firing squad
Welcome back Udiprod, I just watched the first half and I'm considering solving it on my channel.
This looks like the most elaborate yet entertaining way to execute someone
So, I thought this was going to be a physics video, not a logic one. I just accepted the idea of futuristic executions without any concern.
I didn't even attempt to solve it, but my first instinct was "set up some sort of wave that constructively interferes at the end".
I was missing the two other critical insights: send two waves at different speeds and make them collide.
Also, I want to see a 200 robot execution.
Would be nice to see the truth tables, or the Karnaugh maps, how you build and solve the logic process. Thank you for this. I once used a Johnson counter (one for each robot) and a logic array to build it.
everyone gangsta till the robots start doing their funny dance
At first I was having trouble grasping it, but everything came together by the. Then I just watched it several more times because it's such a fun video.
Imagine being sentenced to death and you see a firing squad dancing to happy music before they all shoot.
The interesting thing here is, unless I’m mistaken, this task was solved by humans. I’d love to know how many iterations it would take for an average computer to solve the problem starting with no prompting except for the arm, leg and body movements. In other words by A.I.. I would have guessed it would have taken many hundreds of thousands of iterations before even the simplest problem would be solved.
What do other people think ? I’ve seen other channels where problem solving is taken on by computers, and sometimes the results are quite amazing, but most take hours.
hello merge sort type solution, very cool to see you here!
mathematician: now do it in 2-D rectangle, or generalize to n-D hypercuboid.
I know this is a joke but the problem was actually solved for squares, rectangles and cubes in 1974 bc mathematicians are just Like That
2D: Assuming each robot can see the 8 neighbours around it, and that the lower left robot is the one that gets activated at the start, do the following:
The robots on the lower row of the rectangle perform the hand and foot signals as shown in the video, up until they all turn into generals. The robots in the row above will notice that all robots below them have turned into generals. At this point, they will simply perform the exact same dance going vertically. Eventually ALL robots will become generals and they shoot.
It should be easy to see how this can be generalized to any number of dimensions.
"We need to do something in sync, which is a challenge because they can only see their neighbors. Anyway, to solve this problem, let's assume they're magically synchronized to an ethereal drum beat."
This is also a decent example of how a resonance chamber works if you think of each limb position as a harmonic series
I have a simple solution which might be a bit cheaty, but here it is:
You could create a sequential counting system with the positions of arms and legs: starting at bottom-dead-center to represent the value of zero. Rotating the limb one radian clockwise would be adding one, and rotating the limb one radian CCW would be subtracting one. Since the amount of radians in a circle is irrational, you will never have two identical values.
The first robot sets it's leg to a value of 1. The leg value travels down the line with each robot increasing the previous leg value by one. Once the last robot receives the signal, it will set it's arm to the same value of the leg. Each robot will copy the arm value of the adjacent robot, minus one. When the arm is at a value of zero, fire.
Since you would only need as many values as there are robots, and the amount of robots is finite, the amount of states is therefore finite.
not a bad solution, but it doesn't fit the constraint of 'finite set of states that work for any number of robots', you need a different sized set for each number of robots, or an infinite set if you want it to handle any number.
It's odd I came across this when I did, I had just come up with a similar solution for syncing groups of objects via signal transferring when I was programming, although my solution was a bit more crude than this. Great stuff!
Damn. More crude than this? What they use? Smoke signals? 🤣
Uninterrupted runs of various sizes: 6:46
"We have some constraints that make this simple task difficult"
Typically those constraints are emotions.
Imagine being a soldier and you approach 11 robots and they just have a synchronized dance session before opening fire