Coding Challenge

Happy Pi Day! To celebrate I attempt to compute the digits of Pi using the “collisions” method, thanks to 3Blue1Brown for the idea! Code: thecodingtrain.com/challenges...
🕹️ p5.js Web Editor Sketch: editor.p5js.org/codingtrain/s...
🎥 Previous video: • Coding Challenge #138:...
🎥 Next video: • Coding Challenge #140:...
🎥 All videos: • Coding Challenges
References:
📄 Playing Pool with Pi: www.maths.tcd.ie/~lebed/Galpe...
💥 Elastic Collisions: en.wikipedia.org/wiki/Elastic...
📓 Euler Method: en.wikipedia.org/wiki/Euler_m...
🥧 Additional Pi Day Code Examples: github.com/CodingTrain/Pi-Day...
Videos:
👁️‍🗨️ The Block Collision Puzzle: • The block collision pu...
🔢 Pi and Bouncing Balls: • Pi and Bouncing Balls ...
⭐️ Member-Exclusive Pi Day Prep: • Member Only - Pi Day Prep
🔴 Coding Train Live 172: • Coding Train Live 172:...
Related Coding Challenges:
🚂 #95 Approximating the Value of Pi: • Coding Challenge 95: A...
🚂 #140 Leibniz Formula for Pi: • Coding Challenge #140:...
🚂 #156 Peeking Inside Pi: • Coding Challenge #156:...
🚂 #161 Estimating π from Random Numbers with Euclid's Algorithm: • Coding Challenge 161: ...
🚂 #169 Pi in the Sky Game: • Coding Challenge 169: ...
Timestamps:
0:00 Introduction!
1:51 Basic code of the structure
7:00 Simulating elastic collision between two blocks
12:03 Simulating the wall
13:59 Adding the clack!
14:29 Counting the collisions!
18:09 Adding timesteps to control approximation
24:12 Adding constraints to speed up animation
26:47 Watching collisions upto 11 digits of pi!
28:46 Other methods to simulate elastic collisions and things to try!
30:50 Fake outro (and a special Pi Day song!)
Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound
🚂 Website: thecodingtrain.com/
👾 Share Your Creation! thecodingtrain.com/guides/pas...
🚩 Suggest Topics: github.com/CodingTrain/Sugges...
💡 GitHub: github.com/CodingTrain
💬 Discord: thecodingtrain.com/discord
💖 Membership: kzbin.infojoin
🛒 Store: standard.tv/codingtrain
🖋️ Twitter: / thecodingtrain
📸 Instagram: / the.coding.train
🎥 Coding Challenges: • Coding Challenges
🎥 Intro to Programming: • Start learning here!
🔗 p5.js: p5js.org
🔗 p5.js Web Editor: editor.p5js.org/
🔗 Processing: processing.org
📄 Code of Conduct: github.com/CodingTrain/Code-o...
This description was auto-generated. If you see a problem, please open an issue: github.com/CodingTrain/thecod...
#3blue1brown #elasticcollision #piday #eulermethod #p5js #javascript

[@guitoo1918]

This method is not time sensitive. Because of conservation of momentum and energy, Euler integration is not an issue. The problem is that when a collision happens, you let the 2 objects intersect with themselves and the wall. This leads to the small cube slowly drifting through the wall. If you just snap back the cubes positions after a collision, you should be fine. Technically the pieces don't even need to move, you just have to count the collisions respecting the alternating order of wall and cube collisions.

[@Peds013]

I came to see if this comment was here, not too write it myself, but because I didn't think it was a problem but wanted to get confirmation :-)

[@thetastefultoastie6077]

The problem here is that we don't know if the blocks collided until it's too late and they're already overlapping. So we must reduce the time step to be notified earlier of a collision occurring. You're suggestion of overwriting the position of the blocks breaks a few laws of physics and will introduce an additional source of error without actually fixing the original issue. There are two solutions: 1. Upon detecting overlap, compute how far back to reverse the simulation until the blocks are just touching. Do so, and then compute the collision and continue. 2. Before moving the blocks, measure the distance to the next collision. If this is less than the sum of the velocities then advance the simulation by a fractional time step such that they just meet. Then compute the collision and continue. In physics engines, method 1 is called a discrete simulation, advancing by a fixed time step and solving intersections retro-actively, very common in video games as it's relatively cheap to compute. Method 2 is called continuous collision resolution and is more computationally expensive and so sees less use in video games (Fun fact: this method was used in Diablo 3's bespoke physics engine to give us that sweet ragdoll physics)

[@guitoo1918]

@@thetastefultoastie6077 The only thing that matters to get an accurate result is the order of wall and cube collision. And it's only decided by the sign of the relative speed of the small cube. As long as you maintain that order, anything goes. Position doesn't matter much as long as you ensure the correct order.

[@TheCodingTrain]

Ah, thank you for this discussion. Indeed I did not explain this properly, oy! @Tasteful, if you would like to write a new comment (essentially what you wrote above) that is stand-alone I can pin it. I will address this during my live stream and maybe try to make a new version?

[@Peds013]

@@thetastefultoastie6077 I understand what you're saying, but this isn't a time dependant problem, and can be solved analytically. Therefore the only reason for the time stepping should be visualisation, not too get the answer. The visualisation could be solved simply with the fix above but it means it'd run faster without grinding to a halt.

[@justinhoffmann216]

I love that the video length is Pi (31:41)! Happy #PiDay!

[@MaxPicAxe]

Was this intended?

[@augustemmery-funch620]

@@MaxPicAxe yes

[@DigitalMonsters]

Holy crap I didn't notice this, I love when youtubers take the time to add little easter eggs xD

[@anthonytonev1357]

We have a mission - lets make the likes 3 141

[@anthonytonev1357]

@Shreerang Vaidya let the sharing begin #Piday #Collisions #JavaScriptbenchmark

[@gordonchan4801]

15:30 FUNDAMENTAL THEOREM OF ENGINEERING

[@justanotherhotguy]

Gordon Chan You had 3.14 likes but now you have 3.15

[@Lord2225]

e=pi=3

[@Lord2225]

and sin x = x ofc

[@JoseGonzalezUwU]

g/3 = pi = e = 3

[@NStripleseven]

Jose Gonzalez ah yes, g/3

[@sidalisaadi1961]

Calculates Pi On Pi day ... with a Pi long video ... how committed someone can be?

[@tregi]

dont forget eating pie and singing the pi song

[@anandsuralkar2947]

Lol

[@anandsuralkar2947]

@@tregi yup

[@charadremur333]

Pi commited

[@mohammadazad8350]

approximately pi long

[@mebamme]

27:14 It goes like this, the wall, the block, the drawing loop, the ticking clock, the baffled Dan programming Pi collisions 🎶

[@dingalong14]

You should be proud of yourself

[@YesIKnowSillyName]

That's amazing

[@harryfox4389]

p5 js p5 js

[@msclrhd]

The baffled Dan composing Pillelujah! Pillelujah, Pillelujah, Pillelujah, Pillelujah.

[@KnakuanaRka]

What is that to the tune of?

[@alliseth15]

the video length is 31:41 this is just excessive

[@all69stoff]

And also: Unexpected and a Coincidence (maybe)

[@mebamme]

It's amazing how accurate you got it! Even having seen the 3blue1brown video, I was blown away by how the digits of Pi appeared, and the correct ones to boot! And all with so little code.

[@rageace3942]

engineers: "that's kinda like pi, 3!"

[@charadremur333]

A few feet is no issue!

[@Brahvim]

`3!` Hmm, "Three factorial"? (That's `27`!) r/unexpectedfactorial? :wheeze:

[@memerboi69.0]

timestamp: 15:30

[@brando3465]

@@Brahvim I’ve never looked at a comment and wanted to make a comment about how awful it was until now. I don’t care that it was over a year ago, that was one of the worst things that I have read in my entire life. Please, never let any words escape from your head again, whether verbal, digital, or pen and paper. Your thoughts do not deserve to be heard.

[@Brahvim]

@@brando3465 _Thanks._ I've always talked to people about my KZbin comments sounding cringe anyway. _Well this one was just stupid,_ and I'll have to make sure I make less of these. KZbin is _just not_ the place for me to do these things, maybe. ...thanks.

[@sirnicoosokhan4056]

You could also use this way: console. log(Math.PI);

[@andrewzhang8512]

Mahdi Nicoo that wouldnt be fun

[@RubyPiec]

@@andrewzhang8512 r/wozzles

[@Slinx92OLD]

@@andrewzhang8512 r/woooosh

[@sangeetamankani5612]

Man For this you deserve 3,141,592,653,589,793,238,462,643,383,279,502,884,197,169,399,375,105,820,974,944,592,307,816,406,286,208,998,628,034,825,342,117,067 subscribers. And No I didn't copy-paste or see and type it. I remember 100 digits of PI using ASAP Science's song '100 digits of PI '!!

[@zelioz848]

Oh god.

[@Carlosdreaming]

What an amazing video as always! The video edition is every time getting better too. Great work!!! Thanks!!!

[@WildAnimalChannel]

Knowing the velocity of both blocks, you could calculate the point in space and time where they collide. So you don't need time steps at all! (Except for animation purposes). If the time until collision is above say 1/60th of a second you could use a time step for animating. In fact that would give you a nice iterative formula for pi. (That would converge quite slowly!)

[@colinjava8447]

Yeah I didn't use time or distance at all in my program to count collisions. It might seem like the small block could get crushed between the wall and big block if the big block is really big but I think what happens is there is trillions of small collisions that occur slowing the big block down enough so the crushing can't happen. At least in a mathematical model.

[@technodruid]

Man, it's really cool you just see the physics through the math, like with hypothesising what the m=1 scenerio is. You're quite the polymath!

[@bapolino733]

In the last few videos, your editing was so nice. If possible, please keep it up like this!

[@nitinrangarajan7809]

This is frickin amazing :D Math and Computer Science are just so amazing! Happy Pi Day everyone

[@funkahontas]

Agree !!! Pi is such a magical number , so mind bending where and how people come up with different ways to find it ! It's everywhere too !! Happy Pi day ! :D

[@yentlvandamme]

All your videos are awesome! But this one must be one of the coolest and funniest I've ever seen!

[@ItsDrike]

26:52 I love the song, you should upload a video just with the song

[@markuzj.k9445]

Best PI day ever. Thank you so much dan!!! It would be cool to see if you graph velocities like in the 3b1b video

[@nikensss]

I watched the videos from 3blue1brown when they were released and I also absolutely fell in love with the clacking, hahaha! I like seeing I'm not the only weirdo in this world :3

[@followthetrawler]

That clack sound is the same as the clack that Clackers made, a toy from the late 60's that used to break kids wrists :) Good article on Wikipedia about them. Super video!

[@mosk11tto]

Oh the concept is from 60s, I used to have one of those like almost 10 years ago

[@nikkiofthevalley]

That want dark, very quickly.

[@sanderbos4243]

Props to the editor on this one. This is my favorite episode!

[@avi12]

29:47 The difference between float/double and BigDecimal, as well as the difference between int/long and BigInteger, is that using primitive types, the JVM is allocating a chunk of memory just for that primitive type's previously-set boundary, while as a for BigInteger/BigDecimal, the JVM is directly using the memory to store the bytes, which naturally results in a bigger usage of memory for the application. If you have a lot of RAM and you need high-precision for numbers, you can safely use BigInteger/BigDecimal. Just be careful not running into Infinite loops!

[@Blananas2]

Thanks for blowing my mind with this fact all over again. :)

[@Xnoob545]

12:27 We can think of the wall as 256 high bedrock

[@carlwheeser140]

Oddly enough, I actually did this a couple months ago! I coded the collision thingy! Neat

[@8mrLuka8]

This is one of the best channel on KZbin!

[@XKCDism]

I am liking the new editing style

[@TheNutSlush]

This is my favorite video you've done!

[@justkeerat]

I did this in processing myself and after 7 digits it was just too slow.. I can't believe it went till 9 digits at such a good speed. But it's super impressive. I love how we all enjoy coding mathematical ideas that just make programming fun😂❤️

[@MarsCorporations]

A Good way would be to calculate the "exact" collision point. Then you could calculate the amount of time that the small block needs to hit the wall, add v*time to both, calc exact collision point, repeat.

[@ShaolinMonkster]

One of the most respected youtube channels. You are amazing.

[@haval00]

I loved that getting pi , and pi song and eating pi , thank you so much ❤❤❤

[@loic.bertrand]

The editing on this video is amazing !

[@RogieWoah]

I loved that video, glad you could remake it!

[@axeleblaze6691]

Amazing video as Usual!!! Always learn a lot from your Channel !!

[@danielstefanescu4555]

Very cool Daniel. Interesting the creativity that you have.

[@lion2808]

Nice hint with the video length (31:41) And offcours awesome video as always I find it cool how you are so motivated and you actually made me want to learn a few digits of PI myself so I made an app that lets you train PI like a vocabulary trainer. I think you would like it

[@OonHan]

AMAZING DEMONSTRATION!

[@ahmedelselly2553]

man i was feeling depression because i field to learn advanced javascript and u made me more interested in it u made me change my mind

[@samkimber6747]

You can also simulate/calculate pi in different bases by adjusting the mass ratio between the blocks! You get pi in base ten if the ratio is 10^2^n, you can do binary with 2^2^n, hex with 16^2^n, etc. You have to convert from base 10 to the target base, of course.

[@portalsrule1239]

I was just about to do the same thing! Good work! Happy PI day!

[@theaveragecoder6182]

when I study too much , I just take a break and watch your videos . Great work , you are making this world a better place by making silly mistakes ;)

[@ahmedsonbaty6818]

Awesome Video man !

[@JordanMSeverns]

this is the coolest thing ive ever seen in my life

[@jgcodes2020]

+3Blue1Brown needs to see this. Extremely laggy and inefficient, but extremely elegant.

[@adrieloliveira1463]

This is awesome!

[@fergusmgraham]

Good stuff Mr Shiffman!

[@anantmishra9813]

The best crossover, EVER!

[@itsnottylor4011]

That rendition of Hallelujah was beautiful.

[@fNktn]

awsome as allways :) only thing missing is having the block scale based on their mass

[@bridgest99]

This may be my favorite Pi video ever!

[@skepticmoderate5790]

You could make the number of time steps dependent on the distance to the wall. That would speed up the longer calculations significantly.

[@AngelGonzalezM]

You make me feel happy. Thanks

[@musicdudejoe263]

Thank you for the serenade in pi, much appreciated.

[@phemartin]

god i love this guy! awesome job!

[@user-sq9fw6kf1l]

Dude you are awsome!!! continue the good work

[@bobingstern4448]

The song was the best thing ever, you should make an album!

[@Naej7]

I love the clacking too !

[@justcallmesteve9123]

Thanks m8 i was thinking about that video for a while now.

[@benjy6306]

:D I tried to make this simulation when it came out and it it worked but was rly buggy because there box went on the the other side of the "wall" thing Thank you so much :D

[@techbytefrontier]

Ok, so you were singing with the amazing grace melody. gotcha , divine number.

[@shaileshrana7165]

This is your best video. I love it.

[@tekoreypy]

Awesome name "collision clacking magic wonderfull thing!" , That's the coolest name ever!

[@dawnstudios7813]

A podcast with Grant and Dan in it has the potential to break the Internet.

[@moiquiregardevideo]

I think that using the speed of both blocks after the last collision can bring more digits to pi ; possibly up to 8 digits for 64 bit double floating point. The slope of that line represent the best rational approximation to get a few more digits of pi. The current code compute 10 digits of pi and double are 18 digits total. One extra twist of optimization could be to avoid redrawing the cubes if they didn't move by a whole integer, which is one pixel. We expect no more than 1 order of magnitude improvement here. This code reminds me the bresingham algorithm to draw circles using integers only.

[@santhosh6700]

Belated pi day wishes dood,...I am new subscriber...thank u for made this video...I am gonna make this concept in unity(using c#)

[@TheCodingTrain]

Oh cool! please share when you do!

[@RicoGalassi]

another awesome video!

I love it when you normalize the speed of the video just to make us listen your pi song hahdhahshhsjjsdjjdjd so nice

[@mannyc6649]

The reason why Euler integration is normally approximate is because it assumes v to be constant throughout a time step, resulting in setting x += v, where in theory it should be x+= integral of v dt. In this case the objects are moving conserving momentum, so v is a piecewise constant function and, as long as the time step is smaller than the smallest distance between two consecutive collisions, the algorithm will give exact results.

[@yurisugano6638]

so glad I am alive to see this

[@christianjt7018]

That was an awesome project :)

[@joaovictormendes2293]

That was amazing

[@alastairleith8612]

amazing Π fun. I'd like ou to show basic workings for how physics formulas are derived. it's not that hard to run through conservation of momentum and energy quickly. years since I did it but we only had calculators and spreadsheets to do such models in those days!

[@RedHair651]

cursed uppercase pi

[@pashevka]

This is wonderful

[@BloodyScythe666]

phantastic how this works. would be interesting how this correlates to a circle

[@luisisaurio]

Watch 3blue1brown’s video

[@syedmuhammadaliraza3069]

the video was fab and the song was terrifying 🤣😂

[@kossboss]

The man can code and serenade!

[@AJMansfield1]

30:10 For the optics method, the trick is to use complex numbers to represent the angles, rather than explicitly dealing with angles or relying on any kind of trig function. Using the small angle approximation you can construct a complex number for a particular angle 𝜃 as just 1+𝜃i, and then n*𝜃 is (1+𝜃i)^n. Here's a quick python implementation: ideone.com/T4UCnV For the kinematics method, instead of a fixed timestep you can directly compute the time until the next collision as dt = (x1+w1-x2)/(v2-v1) and make that as one single step; then to animate it you can either interpolate between timesteps or you can have a separate fixed-timestep integration that you re-seed from the main integration at each collision. This also lets you play the clack sounds at a more granular time resolution rather than forcing it to be quantized to the animation framerate. If you're interested I have a python implementation of this that works for an arbitrary number of blocks in an arbitrary number of dimensions, including an interpolation mechanism. At this point I don't have anything for generating the actual animation, but I can at least plot graphs: gist.github.com/AJMansfield/00d69e1488c2b1eb56b8c4da2ca739dc Alternately, you can even forego tracking the block positions altogether, since we already know what order the collisions happen in and the position doesn't figure into the momentum transfer equation. If you take this route you can also simplify things even further and perform the momentum transfer as a single matrix multiply rather than as a number of separate steps. Here's another quick python implementation of this method: ideone.com/jPBh8C

[@TheCodingTrain]

Wow, thanks for this thorough explanation and code samples! Much appreciated!

[@NonTwinBrothers]

Very nicely edited video

[@pbenikovszky1]

Hi Daniel, great video as always, lovely stuff :) Did you consider using BigInt in JS for this challange? Maybe you can go for 20 digits :D

[@TheCodingTrain]

I did consider it! I have some videos coming out soon where I experiment with this idea! (using BigDecimal in Java)

[@pbenikovszky1]

@@TheCodingTrain great, can't wait, I love your videos :)

[@Aimnos]

What I thought about doing is: instead of doing a simulation that checks collision through coordinates, you could just evaluate whether the blocks will collide or not or if the smaller block will hit the wall, like so (block 1 is the smaller one, with speed v1 and block 2 is the bigger one, with speed v2): if v1 > 0 and v1 < v2, the blocks will never collide again; if v1 < v2, block 1 will hit the wall; if neither is true, blocks 1 and 2 will collide with each other and change speeds based on the formula. Based on this idea, I created a program in C++ that does exactly that, but by 11 digits the imprecision got too big and the results stopped matching :\

[@ziomanzo]

you must have a common ancestor with the nutty professor 😂

[@RAWRCoding]

Really interesting video :D

[@hankhill-]

I love you. Great video!!!

[@slugginatubb]

I love how I understand all the coding stuff he is doing but I suck at coding myself

[@nileshshukla298]

Your videos time also represent first 4 digit of pi😁😁😁.. love your video 🙌🙌🙌

[@NghiNguyen-ug8ur]

why does the visualization video of 3blue1brown is so smooth?

[@philippg6023]

Well because its a visualisation Video ; ) maybe he pre calculated it so basically he rendered the video

[@m.sierra5258]

@@philippg6023 Yes, he does prerender everything. It's a python library he wrote himself. I mean, why should he play it live? It's a video, after all, playing it live and recording it would be a waste of precision and smoothness.

[@anandsuralkar2947]

Yup

[@phy6geniuxYTcreations]

It's MANIM. 😁 Mathematical Animation Engine written by Grant Sanderson.

[@NStripleseven]

Your computer must be insane to be able to handle that whole thing in any reasonable amount of time.

[@Domzies]

We have an anual competition at our college, where people recite the numbers of pie, last year a 12 year old girl recited over 900 decimal numbers

[@tonik2558]

You can speed up the calculations by a lot if you just set timeSteps to 6 ** (digits - 1), instead of 10 ** (digits - 1). You won't miss any counts, I've tested it with 11, and it didn't miss a single number.

The most effective way to calculate Pi by far.

[@ForEverybody]

You are awesome all the time.

[@anshumanbharadwaj2966]

The "Never forget the this dot" sticker on your laptop, LOL

[@tedp9146]

This was the first thing I ever programmed in Processing!

[@chriscalver8595]

great video

[@grevel1376]

it was really exciting

[@jorditoral8478]

Just started with programming and so, and I have one doubt. What is the purpose of writting "return newV" in the bounce function?

[@archiegarg1958]

This guy is more of a comedian than a programmer

[@Bruno-ds8ze]

Amazing

[@julilopbal]

Dan be like: * clack * *NOICE*