[Laser] Firing squad synchronization problem 

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.

imagine being sentenced to death by a robot autocracy, and the last thing you see before you die is your executioners just grooving

“Yeah, we had some budget cuts this year, so we can’t go with the executioner robots.” “What are we using, then?” “The dancers.”

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

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!".

“Here’s a robot firing squad” is possibly the most ominous first line in any RU-vid video

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.

"pause if you want to think about it" Meanwhile on the screen: "problem proposed in 1957, solution found in 1967" Think i'll pass.

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?

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.

This video felt like some kind of AI is trying to trick me into progamming a dissident-killing subroutine for it.

Prisoner: *Dances along to the beat* Warden: *Dances along to the beat* Shooters: *Dancing along to the beat* Prisoner: *Dances away slowly*

I love how more rules kept being added so that when he was wrong, he wasn't wrong

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.

This is probably the most random video I've ever watched and I loved every second of it.

no clue what i just watched but i can tell whoever came up with it is a genius

I've been sentenced to death but robocop over here can't stop doing fortnight dances to taunt me.

the more green-lit generals i see, the more nervous i get.

Engineers: “Just make them all shoot once a signal is given, these constraints do nothing but hamper their functions.” Mathematicians be like:

Middle of an odd squad general is an absolute chad. Coolest robot in the squad by far

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!

as a programmer the only issue I see is giving them a beat that is perfectly synchronous so we can do this fast

n=17 is my favorite. The pirouettes and the high notes make me giggle. Maths is beautiful AND deadly. I love it.

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!

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

8:05 Imagine this is the last thing you see before you die.

Ive seen this algorithm before with just colored cells, but its so much easier to visualize with the robots.

The last bit with the music just had me smiling crazily and don't know why, it bought a lot of happiness

mathematicians are the type of guys to go "heres a simple problem" and then add 20 more rules once you get it right

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*

Can we have 10 hours of these robots please

Now we just need twenty people to learn the choreography for this and do it as a stage performance.

imagine being executed and the firing squad does a little jiggle before killing you

Why did you private this video? I watched it halfway before going to sleep and waking up to see you had made this video private.

"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

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.

Everytime the robots shoot I'm hearing a friendly voice saying: "Now you are dead."

hello merge sort type solution, very cool to see you here!

The mathematical precision of them trying to decide when to kill you is so detached it’s scary. But also I want to dance

Wow, this is a really clever solution, and the procedural animations are impressive! Thank you!

Wow, this is probably the most clever logic puzzle I’ve ever seen.

6:40 when the laser sound effect said "ch" i felt that

0:00 "Heres a robot firing squad" in a happy and upbeat tone

For some reason this is the funniest thing I've seen this week.

Such a fascinating problem and solution!

All the while, whatever was in the path of 100 robots decided to take a nap and then just leave

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.

Its like a terrifying robot timer. You know its getting closer to shooting you, but you never know exactly when it will

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.

Wow blue moon today, udiprod uploads

A classic divide and conquer approach. I love the solution, it's beautiful.

4:56 when you find the nerf dart that you lost in 2010

Good RU-vid algorithm! A video I would have never found but needed.

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.

Lmao "this is a robot firing squad" being the first thing, sounds like Mark Zuckerberg and his buddies dislike my being alive.

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."

Imagine being a soldier and you approach 11 robots and they just have a synchronized dance session before opening fire

uncanny how cheerful the video is for being about a firing squad

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.

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.

This has to be the most upbeat tune I've heard while being executed by firing squad

Imagine being on the receiving end of this, just watching the robots do a dance number and knowing once all the robots finish you’re dead

This is a perfect example of a more advanced Turing machine. Great video

everyone gangsta till the robots start doing their funny dance

Imagine you're sentenced together. You get dragged out in front of a squad of robots armed to the teeth, but they just stand there until one gets knocked on the head, and an entire interpretive dance routine happens.

"Oh look honey, they're dancin" "Darling we need to leave right now"

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.

mathematician: now do it in 2-D rectangle, or generalize to n-D hypercuboid.

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.

Imagine getting lined up against a brick wall as a POW during the human/android war and the last thing you see is a bunch of robots doing a funky little dance before executing you in perfect unison.

Executions in 2050: "The firing squad is ready when I find that video again!"

Imagine being executed and this Music starts playing

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!

Everybody gangsta until the fire squad robots start dancing

I keep forgetting about this video and then it pops up again in my recommended a random day

The dancing at the end was so cute lol

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.

I don't know how youtube brought me here but I'm glad I get to see the robots do a nice dance before they shoot me with lasers.

I don't remember my Rhythm heaven toy soldier gameplay having 16 buttons to press

What would happen if we initially hit two robots on the head who are following these rules?

Welcome back Udiprod, I just watched the first half and I'm considering solving it on my channel.

Enemy soldier:"why are they dancing" Enemy general:"Oh shit!"

Suddenly, Boston Dynamics teaching their robots to dance doesn't seem so innocent.

That drum fill between the runs makes me feel strange feelings.

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.

Pov you are a war criminal and are being treated to a funky robot dance

If ever I have to face a robot firing squad, I'm not requesting a blindfold. That way I'll die laughing before any shots get fired.

The robot dance number of death! Glad to see you showed it with primes too.

Here is the full list of states as used in this video. I'm gonna abbreviate left with L, right with R, hand with H and foot with F. The 3 different levels of a foot signal are simply numbered. 1. Idle 2. RH 3. LH 4. RF1 5. RF2 6. RF3 7. LF1 8. LF2 9. LF3 10. Right General (RH + RF1) 11. Left General (LH + LF1) 12. Double General (RH + LH + RF1 + LF1) 13. Squatting2 (RF2 + LF2) (A double general transitions to this state) 14. Squatting3 (RF3 + LF3) (Same as above) 15. Turned around (A robot turns around when they recieve two hand signals, independant of the surrounding foot signals) 16. Weapon up (RH + LH) (A turned-around robot always transitions to this state)

Everybody who would like to say something about what they have done this weekend please raise your hand. All the toddlers in kindergarten: 6:55

I think you could have made some of the double leg signals cause the robots to float. I wouldn't have minded

This video went straight over my head… but I loved it

The guy being executed is watching his emotionless robotic executioners do a funny little dance before blasting him to bits

I love how they dance before they execute me

I love finding such random videos

im just picturing a prisoner scentenced to death by fireing squad, goes out for his final moments, and just hears this marching band and sees a bunch of robots dancing lol.

I love this channel

In the future, this strategy will be adapted in real Robot combat.

General: The robots should be firing now commander Commander: One robot skipped the national anthem therefore having all of them repeat it.