23
\$\begingroup\$

The 3Blue1Brown Youtube channel released a video a year ago called "Why do colliding blocks compute pi?" which describes a model where a block A of mass \$a\$ slides into a block B of mass \$b\$, which then pushes block B into a wall, causing it to bounce off the wall and then collide again with block A.

The miracle of this process is that if \$a/b = 10^{2n-2}\$ the number of total collisions (both between A and B and between B with the wall) is given by the first \$n\$ digits of \$\pi\$.


Example output

+-------+---+--------+
| a     | b | output |
+-------+---+--------+
| 1     | 1 | 3      |
| 2     | 1 | 5      |
| 3     | 1 | 5      |
| 4     | 1 | 6      |
| 5     | 1 | 7      |
| 10    | 3 | 6      |
| 7     | 2 | 6      |
| 9     | 2 | 7      |
| 1     | 2 | 3      |
| 1     | 5 | 2      |
| 100   | 1 | 31     |
| 10000 | 1 | 314    |
+-------+---+--------+

(These values were calculated using this web applet from Reddit user KyleCow1. Please let me know if I've made any mistakes.)


Challenge

Your challenge is to take two positive integers \$a, b \in \mathbb N_{>0}\$, and output the number of collisions in this scenario. Your program should be able to handle all \$a, b \leq 10\,000\$. This is a challenge, so the shortest program wins.

\$\endgroup\$
  • \$\begingroup\$ can we input b,a instead of a,b? \$\endgroup\$ – ngn Jan 29 at 3:00
  • 2
    \$\begingroup\$ ..or a+ib as a complex number? \$\endgroup\$ – ngn Jan 29 at 3:06
  • 1
    \$\begingroup\$ Sure, either of these inputs is fine. \$\endgroup\$ – Peter Kagey Jan 29 at 7:15
  • \$\begingroup\$ @ngn in what way would the complex number help? \$\endgroup\$ – RGS Jan 29 at 7:51
  • 3
    \$\begingroup\$ @RGS if your language has a concise way of getting the argument of a complex number (the "theta"), then arctg(b/a) could be theta(a+ib), but i'm not sure it would help much in this case, as b/a is under a sqrt \$\endgroup\$ – ngn Jan 29 at 8:00

13 Answers 13

9
\$\begingroup\$

Jelly, 10 9 bytes

My first Jelly submission :')

÷½ÆṬØP÷Ċ’

-1 byte thanks to Mr.Xcoder

Uses the formula as in the video. Receives the input flipped; OP gave permission. It probably has room for further golfing, so be sure to give me feedback!

÷½        divide b by a and take square root
  ÆṬ      take the ArcTan of that; then
      ÷   divide
    ØP    pi
          by the number we had.
       Ċ  Round up
        ’ and subtract one

Try it online

\$\endgroup\$
  • 3
    \$\begingroup\$ 9 bytes. This gives a different result for the pair 3,1->5 (test case #3), but the current 10-byter wrongly gives 6 due to floating point inaccuracies, so it's actually a "fix" too :) \$\endgroup\$ – Mr. Xcoder Jan 29 at 11:00
  • \$\begingroup\$ @Mr.Xcoder thanks for your feedback! \$\endgroup\$ – RGS Jan 29 at 13:21
12
\$\begingroup\$

APL (Dyalog Classic), 18 16 bytes

¯1+⌈○÷¯3○.5*⍨⎕÷⎕

Try it online!

rendered as the equivalent {¯1+⌈○÷¯3○.5*⍨⍵÷⍺} in the tio link, to facilitate testing; means evaluated input; and are the arguments to an anonymous function

$$\left\lceil\frac\pi{\textrm{arctg}\sqrt\frac ba}\right\rceil-1$$

(that's the formula from the video. i recommend watching it. it's well explained and the animations are great for building intuition.)

\$\endgroup\$
  • \$\begingroup\$ You could go Extended for .5*⍨ \$\endgroup\$ – Adám Jan 29 at 13:41
9
\$\begingroup\$

JavaScript (ES7),  41  39 bytes

Takes input as (a)(b).

a=>b=>3.14159265/Math.atan((b/a)**.5)|0

Try it online!

How?

Instead of using a ceil function and subtracting \$1\$, we deliberately use a slightly underestimated approximation of \$\pi\$ and floor the result with a bitwise OR.

For \$a,b\le 10000\$, it was empirically proven to give the same results as this safer 44-byte version:

with(Math)f=a=>b=>ceil(PI/atan((b/a)**.5))-1

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I'm assuming you tried reducing the number of decimal places in your pi approximation? I'm quite sad because 355/113 is a really nice approximation of pi and would allow you to golf even more. \$\endgroup\$ – RGS Jan 29 at 14:30
  • 1
    \$\begingroup\$ @RGS That's correct. Going from memory here, but I think I need either 3.14159264 or 3.14159265. \$\endgroup\$ – Arnauld Jan 29 at 14:36
  • \$\begingroup\$ The simplest fraction in that range is 99378/31633, which isn't short enough to golf, unfortunately \$\endgroup\$ – isaacg Jan 29 at 20:40
5
\$\begingroup\$

Haskell, 32 bytes

a#b=ceiling(pi/atan(sqrt$b/a))-1

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Mathematica, 30 29 bytes, 25 characters

⌈Pi/ArcTan@Sqrt[#2/#]⌉-1&

Try it online

-1 byte thanks to ExpiredData

Uses the formula explained in the video.

\$\endgroup\$
  • 3
    \$\begingroup\$ You can just use # instead of #1 \$\endgroup\$ – Expired Data Jan 29 at 12:05
  • \$\begingroup\$ @ExpiredData thanks :D \$\endgroup\$ – RGS Jan 29 at 13:20
4
\$\begingroup\$

Excel, 35 37 bytes

-2 bytes thanks to @Chronocidal

=CEILING(PI()/(ATAN((B1/A1)^.5)),1)-1
\$\endgroup\$
  • 1
    \$\begingroup\$ You seem to have an unnecessary set of brackets around ATAN, for 35 bytes \$\endgroup\$ – Chronocidal Jan 31 at 15:11
3
\$\begingroup\$

C (gcc), 63 \$\cdots\$ 47 46 + 3 (compiler flags) = 49 bytes

f(a,b){a=ceil(acos(-1)/atan(sqrt(b*1./a)))-1;}

Try it online!

Saved 11 12 bytes thanks to ceilingcat!!!

Using the formula from the video ngn recommended.

\$\endgroup\$
3
\$\begingroup\$

Ruby, 49 43 bytes

->a,b{(-1.arg/((a*b)**0.5+b.i).arg).ceil-1}

Try it online!

-5 thans to G B, nicely done

-1 replacing 1i*b with b.i

\$\endgroup\$
  • \$\begingroup\$ I suppose it would be acceptable to take floats as input so that ->a,b{(Math::PI/Math.atan((b/a)**0.5)).ceil-1} works -- but you may want to ask the OP. \$\endgroup\$ – Arnauld Jan 29 at 10:03
  • \$\begingroup\$ You can use -1.arg for Math::PI \$\endgroup\$ – G B Jan 29 at 15:45
  • \$\begingroup\$ And ((a*b)**0.5+1i*b).arg is the same as Math.atan(b**0.5/a**0.5) \$\endgroup\$ – G B Jan 29 at 16:24
2
\$\begingroup\$

05AB1E, 30 bytes

/t©ažq;‚Δ{ÐO;ż®‹èsO;‚}нžqs/î<

Try it online!

Almost definitely golfable..

Implements the formula but because 05AB1E doesn't have arctan we have to calculate it, this does it by bisection.


Explanation

/t                                - sqrt(a/b)
  ©                               - store this value
   ažq;‚                          - the array [0, pi/2] 
        Δ                         - repeat until the array passed in does not change
         {Ð                       - sort then triplicate array 
           O;ż                   - arctan of the average of the array (bisection)
               ®‹                 - is this greater than the sqrt(a/b)? 0 if so 1 if not
                 èsO;‚            - Take the index from the current two guesses and combine with their average
                      }н          - Stop looping and get the first value
                                  - (this should be close enough to arctan(sqrt(a/b))
                        žqs/      - push pi then divide it by the atan(sqrt(a/b)) guess
                            î<    - ceil and decrement
\$\endgroup\$
1
\$\begingroup\$

Python 3, 55 bytes

lambda a,b:ceil(pi/atan((b/a)**.5)-1)
from math import*

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Rust, 59 bytes

|a:f64,b:f64|(f64::acos(-1.)/(b/a).sqrt().atan()).ceil()-1.

Try it online!

\$\endgroup\$
1
\$\begingroup\$

AWK, 56 55 bytes

{x=atan2(0,-1)/atan2(($2/$1)^.5,1);$0=int(x);$0-=$0~x}1

Try it online!

I know I can save a few bytes by hardcoding Pi to some arbitrary precision, but I'm not sure how accurate it is outside of the provided test cases.

\$\endgroup\$
0
\$\begingroup\$

PHP, 46 bytes

<?=ceil(pi()/atan(($argv[2]/$argv[1])**.5))-1;

Try it online!

Not very original I guess, applying the formula from the video..

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.