[Laser] Firing squad synchronization problem

แชร์
ฝัง
  • เผยแพร่เมื่อ 25 มี.ค. 2021
  • The video shows a theoretical problem in computer science and a solution for it. It is presented as a riddle, but note it's not easy to solve.
    The shown solution is based on the first solution proposed for this problem. It requires ~3n steps, and 17 states.
    See list of states and some additional information here: www.udiprod.com/firing-squad-...

ความคิดเห็น • 2.2K

  • @defaultusername9596
    @defaultusername9596 3 ปีที่แล้ว +5173

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

    • @samuelding7854
      @samuelding7854 3 ปีที่แล้ว +92

      Hey, at least they’re programmable

    • @koltrol4370
      @koltrol4370 ปีที่แล้ว +10

      I think it‘s the different way a round

    • @Totally_Bonkers
      @Totally_Bonkers ปีที่แล้ว +4

      how are there TWO replies and 2k likes

    • @ctdaniels7049
      @ctdaniels7049 ปีที่แล้ว +2

      The Clone Wars in a nutshell!

    • @t-rex1019
      @t-rex1019 ปีที่แล้ว +1

      Roger Roger Now launching, Just Dance!

  • @ya_boi_salami
    @ya_boi_salami 3 ปีที่แล้ว +13139

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

    • @thepiratepeter4630
      @thepiratepeter4630 3 ปีที่แล้ว +347

      The war of the sorting robots

    • @yonatanbeer3475
      @yonatanbeer3475 3 ปีที่แล้ว +693

      "Sargent, give the order."
      "Yes sir."
      *Bonk*
      "What are they doing, Sargent"
      "Grooving, sir"

    • @TheJamesM
      @TheJamesM 3 ปีที่แล้ว +264

      The goofiest dystopia.

    • @godlikefish1193
      @godlikefish1193 3 ปีที่แล้ว +141

      If it's execution by groovin robots I'd be more than willing to accept my fate

    • @unexpected2475
      @unexpected2475 3 ปีที่แล้ว +27

      Instead of being blindfolded, you get a nice visual before you get fucking murdered.

  • @nicholasdarrylh.9062
    @nicholasdarrylh.9062 ปีที่แล้ว +1363

    i enjoy how a lot of the sync-related problems go "yea ok just split the big group into the little group"

    • @r3ked272
      @r3ked272 ปีที่แล้ว +50

      Smaller groups are easier to work with, so if we can make a small group out of a big one, we can make the problem easier
      At least I think so

    • @MrOrcaCat
      @MrOrcaCat ปีที่แล้ว +20

      that was my algorithms class in a nutshell

    • @egegoogog1608
      @egegoogog1608 11 หลายเดือนก่อน +19

      recursion recursion recursion

    • @250minecraft
      @250minecraft 11 หลายเดือนก่อน +14

      Divide and conquer

    • @Kackpuh
      @Kackpuh 10 หลายเดือนก่อน +3

      Yes, that's literally how you solve pretty much any problem ever.
      Especially problems where all you have is one bit of information, because you can only work with that one.

  • @joshuapowers4623
    @joshuapowers4623 3 ปีที่แล้ว +554

    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.

    • @MadScientist267
      @MadScientist267 11 หลายเดือนก่อน +30

      The weirder part is THIS is the more difficult to understand version 🤣

    • @jjwkoester
      @jjwkoester 10 หลายเดือนก่อน +4

      There’s a quote that says “if you can’t explain something simply, then you don’t understand it well enough”

    • @Catman_CM
      @Catman_CM 10 หลายเดือนก่อน +16

      ​@@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 :)

    • @ralexcraft990
      @ralexcraft990 9 หลายเดือนก่อน +2

      @@Catman_CMand in general fairness, more correct.

    • @TheRestedOne
      @TheRestedOne 9 หลายเดือนก่อน +4

      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.

  • @henrycgs
    @henrycgs 3 ปีที่แล้ว +1501

    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

    • @art1637
      @art1637 3 ปีที่แล้ว +75

      I like how this post accounts for people with no friends lol

    • @noone-nj6ps
      @noone-nj6ps 3 ปีที่แล้ว +5

      What a lovely story

    • @emielverbeeren8181
      @emielverbeeren8181 3 ปีที่แล้ว +21

      @@art1637 According to the description N>=3. You will need at least 2 friends.

  • @jackeea_
    @jackeea_ 3 ปีที่แล้ว +8846

    everybody gangsta until the firing squad starts dancing

    • @pvic6959
      @pvic6959 3 ปีที่แล้ว +341

      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

    • @forregom
      @forregom 3 ปีที่แล้ว +126

      This is a pretty effective intimidation tactic

    • @ClokworkGremlin
      @ClokworkGremlin 3 ปีที่แล้ว +62

      It's like being executed by the Ginyu Force.

    • @alansmithee419
      @alansmithee419 3 ปีที่แล้ว +75

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

    • @traceyjacobsen8544
      @traceyjacobsen8544 3 ปีที่แล้ว +17

      I don't think anybody gangsta if your on the receiving end of the firing squad

  • @klobiforpresident2254
    @klobiforpresident2254 2 ปีที่แล้ว +474

    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?

    • @udiprod
      @udiprod  2 ปีที่แล้ว +191

      Thanks! It's procedural animation. Yes, a cut version is a nice idea, I'll consider doing that with a few more runs.

    • @klobiforpresident2254
      @klobiforpresident2254 2 ปีที่แล้ว +28

      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.

    • @HidekiShinichi
      @HidekiShinichi 10 หลายเดือนก่อน +2

      ​@@udiprod i need a version without a beats, just a nice continuus flow of dance and moves.

  • @TegukiSix
    @TegukiSix ปีที่แล้ว +41

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

    • @bushbaby4421
      @bushbaby4421 11 หลายเดือนก่อน +10

      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!

    • @Poldovico
      @Poldovico 10 หลายเดือนก่อน +12

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

    • @nuh_uh210
      @nuh_uh210 9 หลายเดือนก่อน +3

      That’s a neat solution. My solution was:
      if you are an officer, fire
      if you are not an officer, fire
      All of them have fired at the same time.

    • @aa01blue38
      @aa01blue38 6 หลายเดือนก่อน

      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.

  • @seanproctor7830
    @seanproctor7830 3 ปีที่แล้ว +5509

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

  • @EarlHare
    @EarlHare 3 ปีที่แล้ว +8743

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

    • @extraintelligence
      @extraintelligence 3 ปีที่แล้ว +754

      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.

    • @kurumi394
      @kurumi394 3 ปีที่แล้ว +1571

      @@extraintelligence I think OC accepts he isn't Archimedes or Isaac Newton

    • @extraintelligence
      @extraintelligence 3 ปีที่แล้ว +720

      @@kurumi394 not with that attitude.

    • @Orlandofurioso95
      @Orlandofurioso95 3 ปีที่แล้ว +259

      @@extraintelligence Not with that name, either

    • @eilmiv
      @eilmiv 3 ปีที่แล้ว +168

      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.

  • @littlegamedude6351
    @littlegamedude6351 ปีที่แล้ว +11

    Football star: gets brutally injured.
    The cheerleaders; 7:20

  • @edwardblair4096
    @edwardblair4096 ปีที่แล้ว +41

    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.

    • @MadScientist267
      @MadScientist267 11 หลายเดือนก่อน +2

      The entire point of this is that no such construct is needed.
      That said it has "memory", as a whole unit.

    • @GeekOfAllness
      @GeekOfAllness 11 หลายเดือนก่อน +1

      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.

    • @Poldovico
      @Poldovico 10 หลายเดือนก่อน +1

      ​@@GeekOfAllnessyou're using memory to run in linear time, whereas the memory-less version runs in log time. Not so strange.

    • @mayday8413
      @mayday8413 10 หลายเดือนก่อน

      Since they have no memory all they know is that since they’re not a general yet the group must be bigger

  • @shaunyap4090
    @shaunyap4090 3 ปีที่แล้ว +4159

    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

    • @jebediahkerman8245
      @jebediahkerman8245 3 ปีที่แล้ว +445

      Stop trying to escape! We have to reset the process every time you do that.

    • @ZaHandle
      @ZaHandle 3 ปีที่แล้ว +180

      “Okay how about this, give me a flag and when i raise it you guys shoot. I’m not gonna stand here waiting for you guys to shoot”

    • @Yui714
      @Yui714 3 ปีที่แล้ว +17

      I would love this. thank you.

    • @blarghinatelazer9394
      @blarghinatelazer9394 3 ปีที่แล้ว +66

      The fucking suspense that would create

    • @The_Epicness9000
      @The_Epicness9000 ปีที่แล้ว +179

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

  • @25usd94
    @25usd94 3 ปีที่แล้ว +17830

    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.

    • @iwomartofel1849
      @iwomartofel1849 3 ปีที่แล้ว +706

      Guitly, or perhaps satisfied

    • @happmacdonald
      @happmacdonald 3 ปีที่แล้ว +1138

      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

    • @kaidatong1704
      @kaidatong1704 3 ปีที่แล้ว +307

      nooo u can’t just break the first law of robotics
      machine gun goes brrr

    • @usernametaken017
      @usernametaken017 3 ปีที่แล้ว +90

      @@kaidatong1704 if nobody saw it its not a crime

    • @nondescripthandle212
      @nondescripthandle212 3 ปีที่แล้ว +23

      @@happmacdonald that nighttime bit got mw

  • @Quincunx_5
    @Quincunx_5 ปีที่แล้ว +1

    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!

  • @roblxplyr2017
    @roblxplyr2017 ปีที่แล้ว +2

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

  • @EnUsUserScreenname
    @EnUsUserScreenname 3 ปีที่แล้ว +2186

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

  • @i_teleported_bread7404
    @i_teleported_bread7404 3 ปีที่แล้ว +7278

    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.

    • @i_teleported_bread7404
      @i_teleported_bread7404 3 ปีที่แล้ว +264

      @@Warze And that's why you don't drink while designing your robotic executioners.

    • @52flyingbicycles
      @52flyingbicycles 3 ปีที่แล้ว +122

      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

    • @stelcxantisto
      @stelcxantisto 3 ปีที่แล้ว +103

      Rearrange them into a circle so that the left leg signal can never meet the right hand signal.

    • @user6122
      @user6122 3 ปีที่แล้ว +21

      @@stelcxantisto nah just make this the josephus problem and get it over with

    • @SoupEarthOfficial
      @SoupEarthOfficial 3 ปีที่แล้ว +13

      Just get one robot

  • @Mark-fc7tu
    @Mark-fc7tu ปีที่แล้ว +6

    Amazing. It's incredible to see what can be accomplished with ratios and 3n.

  • @50shadesofmycow
    @50shadesofmycow ปีที่แล้ว +1

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

  • @brady1407
    @brady1407 3 ปีที่แล้ว +813

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

    • @legendgames128
      @legendgames128 ปีที่แล้ว +11

      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)

    • @squidgelad1983
      @squidgelad1983 ปีที่แล้ว +5

      @@legendgames128 Yes you're very clever, this is youtube.

    • @memegumin
      @memegumin ปีที่แล้ว +2

      @@squidgelad1983 but that was a joke, a programing joke

    • @Epic_Droid
      @Epic_Droid ปีที่แล้ว +2

      @@legendgames128 Gosh dang it, take your like, you fellow programming punster of a mad lad.

    • @theRPGmaster
      @theRPGmaster ปีที่แล้ว +1

      @@legendgames128 I assume 32-bit integers are used, not 8-bit, the real question is, what happens when we exceed 4.29 Billion likes

  • @Moley1Moleo
    @Moley1Moleo 3 ปีที่แล้ว +398

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

    • @DepletedLithium
      @DepletedLithium 3 ปีที่แล้ว +2

      Brilliant!

    • @Terraqueo22
      @Terraqueo22 ปีที่แล้ว

      Until he finishes dancing

    • @ITSMRFOXY
      @ITSMRFOXY ปีที่แล้ว

      Ironically, Robocop is now in fortnite

    • @cye2310
      @cye2310 ปีที่แล้ว

      ​@@ITSMRFOXYIt's fortnight, Fortnite is the kids version

  • @cobalius
    @cobalius 2 ปีที่แล้ว +3

    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

  • @derfastimmerzustimmer8635
    @derfastimmerzustimmer8635 10 หลายเดือนก่อน

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

  • @carykh
    @carykh 3 ปีที่แล้ว +8383

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

    • @ultrio325
      @ultrio325 3 ปีที่แล้ว +301

      Probably because you are the prisoner from abusive AI usage (AI torture for music generation)

    • @mayabartolabac
      @mayabartolabac 3 ปีที่แล้ว +194

      POV: You get killed by the robot firing squad after committing genocide on 2 music AIs

    • @keithplayzstuff2424
      @keithplayzstuff2424 3 ปีที่แล้ว +33

      TIL cary watches udiprod

    • @urble
      @urble 3 ปีที่แล้ว +8

      The living legend himself

    • @Chumpatrol1
      @Chumpatrol1 3 ปีที่แล้ว +2

      I keep seeing you in every comment section lol

  • @ColCoal
    @ColCoal 3 ปีที่แล้ว +4439

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

    • @jebediahkerman8245
      @jebediahkerman8245 3 ปีที่แล้ว +345

      Yeah if the whole process is started off by hitting the first robot why not just hit all of them at the same time 😂

    • @samfriend3675
      @samfriend3675 3 ปีที่แล้ว +602

      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
      @KavsLockedOut 3 ปีที่แล้ว +41

      @@samfriend3675 what situation would result in only adjacent clients be able to talk in a network?

    • @arielsproul8811
      @arielsproul8811 3 ปีที่แล้ว +300

      @@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

    • @samfriend3675
      @samfriend3675 3 ปีที่แล้ว +121

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

  • @danielyuan9862
    @danielyuan9862 ปีที่แล้ว

    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!

  • @georgeofhamilton
    @georgeofhamilton ปีที่แล้ว +15

    Absolutely based that you brought this version back.

  • @undefined6947
    @undefined6947 3 ปีที่แล้ว +2055

    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.

    • @frocco7125
      @frocco7125 3 ปีที่แล้ว +15

      I agree.

    • @emil.pettersson05
      @emil.pettersson05 3 ปีที่แล้ว +52

      The only problem is that the robots dance in 3/4 and the music is in 4/4.

    • @undefined6947
      @undefined6947 3 ปีที่แล้ว +90

      @@emil.pettersson05 that's called an ostinato, looks like it's intentional here, so no problem :)

    • @user6122
      @user6122 3 ปีที่แล้ว +58

      @@emil.pettersson05 anything can be a waltz if you try hard enough

    • @scottilewis3753
      @scottilewis3753 3 ปีที่แล้ว +3

      How do you want to pay?

  • @alansmithee419
    @alansmithee419 3 ปีที่แล้ว +403

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

    • @hueyiroquois3839
      @hueyiroquois3839 3 ปีที่แล้ว +147

      The audience might not like the plot twist at the end.

    • @PokeShadow77
      @PokeShadow77 3 ปีที่แล้ว +86

      @@hueyiroquois3839 Dead men tell no tales

    • @SniperOnSunday
      @SniperOnSunday 3 ปีที่แล้ว +24

      @@hueyiroquois3839 What are they gonna do about it?

    • @aiosquadron
      @aiosquadron ปีที่แล้ว +7

      @@hueyiroquois3839 Maybe, but they won't live to tell the tale. (Hides mousin negate behind back)

    • @MadScientist267
      @MadScientist267 11 หลายเดือนก่อน

      ...why... 🤦‍♂️

  • @DeltaSix_YT
    @DeltaSix_YT ปีที่แล้ว +1

    This will probably get recommended again over 6 years. See ya there.

  • @FurryNonsense
    @FurryNonsense 11 หลายเดือนก่อน +1

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

  • @bustahwoalf2858
    @bustahwoalf2858 3 ปีที่แล้ว +680

    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

    • @DJChiefX197
      @DJChiefX197 ปีที่แล้ว +42

      Not quite. If a robot becomes a double-general while queuing the leg signal, the leg signal is delayed by one beat.

    • @ryannorthup3148
      @ryannorthup3148 11 หลายเดือนก่อน +22

      @@DJChiefX197 The point still stands, since the final robot only fires when that final leg signal reaches the end of the line.

    • @ValeBridges
      @ValeBridges 11 หลายเดือนก่อน +19

      @@ryannorthup3148 heh, the point still _stands_

    • @ryannorthup3148
      @ryannorthup3148 11 หลายเดือนก่อน +7

      ​@@ValeBridges heh

    • @thetiredladdy
      @thetiredladdy 10 หลายเดือนก่อน

      @@ryannorthup3148 Puns!

  • @Nauctshea
    @Nauctshea 3 ปีที่แล้ว +376

    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*

  • @jonathanpallotto8227
    @jonathanpallotto8227 ปีที่แล้ว

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

  • @G.Aaron.Fisher
    @G.Aaron.Fisher ปีที่แล้ว

    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.

  • @mrmimeisfunny
    @mrmimeisfunny 3 ปีที่แล้ว +470

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

    • @pvic6959
      @pvic6959 3 ปีที่แล้ว +49

      id die amused and that wouldnt be terrible lol

    • @FlashDrive356
      @FlashDrive356 3 ปีที่แล้ว +21

      They be groovin'

    • @shoam2103
      @shoam2103 3 ปีที่แล้ว +12

      I'd be pretty amused

    • @tykjpelk
      @tykjpelk 3 ปีที่แล้ว +9

      Imagine a future where they need 20 coordinated robots to kill you.

    • @erinboyle2889
      @erinboyle2889 3 ปีที่แล้ว +5

      sometimes I come back to this video just to watch from 8:05 onwards

  • @rootabeta9015
    @rootabeta9015 3 ปีที่แล้ว +98

    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

  • @maccrew612
    @maccrew612 11 หลายเดือนก่อน

    Good TH-cam algorithm! A video I would have never found but needed.

  • @onebigchumptm4729
    @onebigchumptm4729 ปีที่แล้ว +1

    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

  • @zlodevil426
    @zlodevil426 3 ปีที่แล้ว +1147

    Can we have 10 hours of these robots please

    • @walksanator
      @walksanator 3 ปีที่แล้ว +138

      Yes just a stream where after firing it adds another robot

    • @eclipse_darkpaw
      @eclipse_darkpaw 3 ปีที่แล้ว +37

      @@walksanator 10/10 would watch

    • @yonatanbeer3475
      @yonatanbeer3475 3 ปีที่แล้ว +5

      Please

    • @leondost3575
      @leondost3575 3 ปีที่แล้ว +42

      follow up problem: "at 2 beats per second, what number of robots would take (closest to) 10 hours to fire?"

    • @redyau_
      @redyau_ 3 ปีที่แล้ว +5

      @@walksanator Oh that's a nice programming challange

  • @Elizhium
    @Elizhium 3 ปีที่แล้ว +840

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

    • @Elizhium
      @Elizhium 3 ปีที่แล้ว +140

      ​@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

    • @spiralhalo
      @spiralhalo 3 ปีที่แล้ว +87

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

    • @martysh1226
      @martysh1226 3 ปีที่แล้ว +8

      @@Elizhium maybe set a time when the beat should start and have a hardcoded beat?

    • @ivarangquist9184
      @ivarangquist9184 3 ปีที่แล้ว +35

      If you had a server, you wouldn’t need the dancing.

    • @wojtek4p4
      @wojtek4p4 3 ปีที่แล้ว +12

      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.

  • @Jeff-ku9bq
    @Jeff-ku9bq 3 ปีที่แล้ว

    I could watch these full runs for hours. It's hypnotizing.

  • @druid_zephyrus
    @druid_zephyrus 3 ปีที่แล้ว +1

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

  • @PRIMEVAL543
    @PRIMEVAL543 3 ปีที่แล้ว +130

    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

    • @AssistantCoreAQI
      @AssistantCoreAQI 3 ปีที่แล้ว +6

      A Group Of Rebels Moves The Robots From The Beginning To The End Cyclically, Resulting In Them Being Completely Relocated.

    • @PRIMEVAL543
      @PRIMEVAL543 3 ปีที่แล้ว +2

      @@AssistantCoreAQI „Error, arm signal from right == True and left leg stretched == True not found! Nuclear self destruct in 3, 2, 1“

  • @sinom_00
    @sinom_00 3 ปีที่แล้ว +206

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

  • @explorer47422
    @explorer47422 ปีที่แล้ว

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

  • @PavloPravdiukov
    @PavloPravdiukov ปีที่แล้ว

    Great, now I know a solution to a problem I haven't heard of before!

  • @TheRabbitPoet
    @TheRabbitPoet 3 ปีที่แล้ว +203

    "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

  • @purple.7953
    @purple.7953 3 ปีที่แล้ว +116

    i like how they have to get hit in the head with a squeaky hammer to activate

  • @iavv334
    @iavv334 ปีที่แล้ว +3

    This is also a decent example of how a resonance chamber works if you think of each limb position as a harmonic series

  • @SomeoneYouDontKnowOfficial
    @SomeoneYouDontKnowOfficial ปีที่แล้ว +1

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

  • @MorningDusk7734
    @MorningDusk7734 3 ปีที่แล้ว +1070

    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!

    • @Sylfa
      @Sylfa ปีที่แล้ว +28

      Mmmm, except you fail at the synchronized clocks. Alternatively, you already had a method to synchronize all devices.

    • @officersoulknight6321
      @officersoulknight6321 ปีที่แล้ว +22

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

    • @Henfredemars
      @Henfredemars ปีที่แล้ว +13

      This is fragile because it supposes that all of your machines are reliable.

    • @loganduncan1259
      @loganduncan1259 ปีที่แล้ว +7

      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.

    • @DrakeOola
      @DrakeOola ปีที่แล้ว +3

      @@loganduncan1259 This is an example of swarm behavior, try again.

  • @Marcox385
    @Marcox385 3 ปีที่แล้ว +23

    Two uploads in a century? God has blessed us

  • @thelastcrusader5439
    @thelastcrusader5439 ปีที่แล้ว

    So glad TH-cam answers questions i didnt know I wanted to ask

  • @Barquevious_Jackson
    @Barquevious_Jackson 10 หลายเดือนก่อน +1

    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.

  • @finnaginfrost6297
    @finnaginfrost6297 3 ปีที่แล้ว +44

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

  • @BlackM3sh
    @BlackM3sh 3 ปีที่แล้ว +87

    Thought this was going to be an impossible problem, but it wasn't. Very neat!

  • @_ramar
    @_ramar 2 ปีที่แล้ว +3

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

  • @PatrickPease
    @PatrickPease 11 หลายเดือนก่อน

    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.

  • @SorryBones
    @SorryBones 3 ปีที่แล้ว +46

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

  • @XCSme
    @XCSme 3 ปีที่แล้ว +329

    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.

    • @sebasfavaron
      @sebasfavaron ปีที่แล้ว +11

      Thank you!

    • @TG-to5nf
      @TG-to5nf ปีที่แล้ว +6

      good comment.

    • @HypnosisBear
      @HypnosisBear ปีที่แล้ว +11

      That's genius!! Thanks for explaining it to my stupid mind! Now I can truly appreciate the solution!

    • @DrakeOola
      @DrakeOola ปีที่แล้ว +1

      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

  • @MillMoxx
    @MillMoxx ปีที่แล้ว +1

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

  • @mikes8155
    @mikes8155 11 หลายเดือนก่อน

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

  • @247flashgames
    @247flashgames 3 ปีที่แล้ว +113

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

  • @ivarangquist9184
    @ivarangquist9184 3 ปีที่แล้ว +48

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

  • @rre9121
    @rre9121 9 หลายเดือนก่อน

    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.

  • @jupitersky
    @jupitersky ปีที่แล้ว

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

  • @isaach.1135
    @isaach.1135 3 ปีที่แล้ว +31

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

  • @niemandwirklich
    @niemandwirklich 3 ปีที่แล้ว +130

    Such a fascinating problem and solution!

  • @hamburgerbroz6439
    @hamburgerbroz6439 ปีที่แล้ว +2

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

  • @SkooterBrother
    @SkooterBrother ปีที่แล้ว +1

    I love finding such random videos

  • @nowhed
    @nowhed 3 ปีที่แล้ว +70

    Wow blue moon today, udiprod uploads

    • @Huntracony
      @Huntracony 3 ปีที่แล้ว +1

      It's always a great day!

  • @Nemmy72
    @Nemmy72 3 ปีที่แล้ว +44

    Imagine a army battle vs 2000 or so of these guys
    And the enemy is polite enough to wait for them to finish

    • @AssistantCoreAQI
      @AssistantCoreAQI 3 ปีที่แล้ว +1

      "Alright, Alright, I'll Wait A Week For You All To Align.. -Sigh.- Someone Knocked The Middle One Over, We Have To Restart It."

  • @meep2k
    @meep2k 3 ปีที่แล้ว

    the explanation for this logic problem is so convoluted

  • @mayanightstar
    @mayanightstar ปีที่แล้ว

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

  • @rodrigoappendino
    @rodrigoappendino 3 ปีที่แล้ว +85

    It looks like those Wolfram cellular automata, but with finite set of cells in the horizontal axis and with more than 2 states.

    • @charlz-darvin
      @charlz-darvin 3 ปีที่แล้ว +4

      It means that this is just 1D automata.

    • @rodrigoappendino
      @rodrigoappendino 3 ปีที่แล้ว

      @@charlz-darvin Yes, like all wolfram's automata

    • @rodrigoappendino
      @rodrigoappendino 3 ปีที่แล้ว +2

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

  • @bajooder5518
    @bajooder5518 3 ปีที่แล้ว +7

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

  • @soup5344
    @soup5344 ปีที่แล้ว +1

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

  • @NVUSAttitude
    @NVUSAttitude ปีที่แล้ว

    these videos are unbelievably interesting to watch and think about

  • @them4309
    @them4309 3 ปีที่แล้ว +23

    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

  • @darthvader2994
    @darthvader2994 3 ปีที่แล้ว +6

    "I love these random educational videos from years ago this is from what? 6 years ago?"
    > Last week

  • @cowcrusader
    @cowcrusader 3 ปีที่แล้ว +1

    Imagine being sentenced to death and you see a firing squad dancing to happy music before they all shoot.

  • @LydellAaron
    @LydellAaron 9 หลายเดือนก่อน

    You can see the wave mechanics. Awesome video

  • @personman4011
    @personman4011 3 ปีที่แล้ว +27

    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.

  • @Xzanah
    @Xzanah 3 ปีที่แล้ว +12

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

  • @colevilleproductions
    @colevilleproductions ปีที่แล้ว +3

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

  • @dred_dreamr
    @dred_dreamr ปีที่แล้ว +1

    The enemy squad when they catch me reloading:

  • @protondium_8927
    @protondium_8927 3 ปีที่แล้ว +16

    The new rhythm heaven game looks amazing!

    • @EthanTheGamer77
      @EthanTheGamer77 3 ปีที่แล้ว

      the visual cues seem a bit complicated
      I'm not gonna get better then a OK

  • @thejbo777
    @thejbo777 3 ปีที่แล้ว +6

    Woah, more than one video posted in a year? THIS IS AMAZING!!!

  • @naturally_rob
    @naturally_rob ปีที่แล้ว +1

    "We have some constraints that make this simple task difficult"
    Typically those constraints are emotions.

  • @o_sch
    @o_sch ปีที่แล้ว +1

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

  • @TheSpookiestSkeleton
    @TheSpookiestSkeleton 3 ปีที่แล้ว +5

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

  • @pqul2828
    @pqul2828 3 ปีที่แล้ว +3

    I loved this puzzle! Great visualization as always, I'm looking forward to the next video!

  • @somedude8380
    @somedude8380 10 หลายเดือนก่อน +2

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

  • @CarlosFloresP
    @CarlosFloresP 11 หลายเดือนก่อน

    That is so interesting. Really loved the video

  • @johnvriezen4696
    @johnvriezen4696 3 ปีที่แล้ว +6

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

  • @lgrantcdg
    @lgrantcdg 3 ปีที่แล้ว +7

    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.

  • @Leekodot15
    @Leekodot15 ปีที่แล้ว +6

    I think it would have been cooler ti split the firing state into multiple states, for aesthetic purposes only. A preparation state, an aim state, and a fire state, for example. Having the entire protocol being linked to firing will make it so that nothing is changed in terms of solution, as each step must be performed in order, while also making it so that the robots don't just make an ugly snap to firing. This also makes the protocol to be played to the beat. But hey, that's just me.

  • @sur2823
    @sur2823 ปีที่แล้ว

    A clever way to sync a state machine, visualized with robots! Awesome