Elastic collisions between blocks

23

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.

Peter Kagey

Posted 2020-01-29T02:06:00.733

Reputation: 2 789

can we input b,a instead of a,b? – ngn – 2020-01-29T03:00:29.253

2..or a+ib as a complex number? – ngn – 2020-01-29T03:06:14.850

1Sure, either of these inputs is fine. – Peter Kagey – 2020-01-29T07:15:35.130

@ngn in what way would the complex number help? – RGS – 2020-01-29T07:51:10.183

3@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 – ngn – 2020-01-29T08:00:36.663

The case where b=1 is now on the OEIS as A331859.

– Peter Kagey – 2020-02-04T22:00:55.343

Answers

9

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

RGS

Posted 2020-01-29T02:06:00.733

Reputation: 5 047

39 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 :) – Mr. Xcoder – 2020-01-29T11:00:19.447

@Mr.Xcoder thanks for your feedback! – RGS – 2020-01-29T13:21:13.507

12

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

ngn

Posted 2020-01-29T02:06:00.733

Reputation: 11 449

You could go Extended for .5*⍨ → √

– Adám – 2020-01-29T13:41:51.267

9

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!

Arnauld

Posted 2020-01-29T02:06:00.733

Reputation: 111 334

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. – RGS – 2020-01-29T14:30:13.867

1@RGS That's correct. Going from memory here, but I think I need either 3.14159264 or 3.14159265. – Arnauld – 2020-01-29T14:36:32.683

The simplest fraction in that range is 99378/31633, which isn't short enough to golf, unfortunately – isaacg – 2020-01-29T20:40:31.783

5

Haskell, 32 bytes

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

Try it online!

Asone Tuhid

Posted 2020-01-29T02:06:00.733

Reputation: 1 944

4

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.

RGS

Posted 2020-01-29T02:06:00.733

Reputation: 5 047

3You can just use # instead of #1 – Expired Data – 2020-01-29T12:05:19.177

@ExpiredData thanks :D – RGS – 2020-01-29T13:20:55.600

4

Excel, 35 37 bytes

-2 bytes thanks to @Chronocidal

=CEILING(PI()/(ATAN((B1/A1)^.5)),1)-1

Wernisch

Posted 2020-01-29T02:06:00.733

Reputation: 2 534

1You seem to have an unnecessary set of brackets around ATAN, for 35 bytes – Chronocidal – 2020-01-31T15:11:37.227

3

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

Asone Tuhid

Posted 2020-01-29T02:06:00.733

Reputation: 1 944

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. – Arnauld – 2020-01-29T10:03:38.367

You can use -1.arg for Math::PI – G B – 2020-01-29T15:45:12.353

And ((a*b)**0.5+1i*b).arg is the same as Math.atan(b**0.5/a**0.5) – G B – 2020-01-29T16:24:20.770

3

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.

Noodle9

Posted 2020-01-29T02:06:00.733

Reputation: 2 776

2

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

Expired Data

Posted 2020-01-29T02:06:00.733

Reputation: 3 129

1

Python 3, 55 bytes

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

Try it online!

Jitse

Posted 2020-01-29T02:06:00.733

Reputation: 3 566

1

Rust, 59 bytes

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

Try it online!

Asone Tuhid

Posted 2020-01-29T02:06:00.733

Reputation: 1 944

1

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.

rootbeersoup

Posted 2020-01-29T02:06:00.733

Reputation: 111

0

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

Kaddath

Posted 2020-01-29T02:06:00.733

Reputation: 449

Asked: 2020-01-29T02:06:00.733

Viewed: 2 808 times

Active: 2020-01-31T20:50:05.180