17
\$\begingroup\$

In this code golf, you will have to determine the direction of the shortest shot that hits exactly n cushions before falling into a pocket.

The billiard table is a 6 pocket pool table with the following characteristics:

  • Dimensions are variable (a x b)
  • No friction : the ball will roll forever until it falls into a pocket
  • Pockets and ball sizes are almost zero. This means that the ball will fall in the pocket only if they have same position.
  • The ball is placed at the bottom left hole at the beginning (but doesn't fall in it)

3cushion

Create a full program or function that takes the dimensions (a,b) of the table and a the number of cushions to hit n as input and returns the angle in degrees of the shortest path hitting exactly n cushions before falling into a pocket.

  • a > 0
  • b > 0
  • 0 <= n < 10000000
  • 0 < alpha < 90 (in degrees) precision : at least 10^-6

examples :

with a = 2, b = 1, n = 1 there are three possible paths : (1) (2) (3) on the following figure. the number (1) is the shortest so the output should be atan(2) = 63.43494882292201 degrees

1cushion

The solution for a = 2, b = 1, n = 4 is atan(4/3) = 53.13010235415598 degrees

4cushions

test samples :

a = 2,    b = 1,    n = 1,       -> alpha = 63.43494882292201
a = 2,    b = 1,    n = 2,       -> alpha = 71.56505117707799
a = 2,    b = 1,    n = 3,       -> alpha = 75.96375653207353
a = 2,    b = 1,    n = 4,       -> alpha = 53.13010235415598
a = 2,    b = 1,    n = 5,       -> alpha = 59.03624346792648
a = 2,    b = 1,    n = 6,       -> alpha = 81.86989764584403
a = 4.76, b = 3.64, n = 27,      -> alpha = 48.503531644784466
a = 2,    b = 1,    n = 6,       -> alpha = 81.86989764584403
a = 8,    b = 3,    n = 33,      -> alpha = 73.24425107080101
a = 43,   b = 21,   n = 10005,   -> alpha = 63.97789961246943

This is code/billiard golf : shortest code wins!

\$\endgroup\$
  • \$\begingroup\$ Does the ball have to hit exactly n cushions, or at least n cushions? \$\endgroup\$ – Peter Taylor Dec 16 '15 at 19:40
  • \$\begingroup\$ @PeterTaylor exactly n cushions \$\endgroup\$ – Damien Dec 16 '15 at 19:41
  • \$\begingroup\$ isn´t the shortest path always back and forth between the left side top and bottom and then into one of the middle holes? \$\endgroup\$ – Eumel Dec 17 '15 at 8:55
  • \$\begingroup\$ no, look at the 2 1 4 example. This path is sqrt(25) = 5 long whereas your solution is sqrt(26) \$\endgroup\$ – Damien Dec 17 '15 at 9:49
11
\$\begingroup\$

Python 2.7, 352 344 281 bytes

from math import*
def l(a,b,n):
 a*=1.;b*=1.
 r=set()
 for i in range(1,n+3):
  t=[]
  for k in range(1,i):
   for h in[0,.5]:
    x=(i-k-h)
    if 1-(x/k in r):r.add(x/k);t+=(x*a,k*b),
 d=(a*n+1)**2+(b*n+1)**2
 for x,y in t:
  if x*x+y*y<d:d=x*x+y*y;o=degrees(atan(y/x))
 return o
  • -16 bytes thanks to @Dschoni

Explanation: instead calculating the cushions hits, I'm adding n tables and taking the new holes as valid : billard Black border/holes is the original, green border/holes is the valid for n=1, red border/holes is the valid for n=2 and so on. Then I remove the invalid holes (e.g. the blue arrow for n=1). I'll have a list of valid holes and their coordinates, then I calculate their distance from initial point, and then the angle of the smaller distance.
Notes:
a=4.76, b=3.64, n=27 - give 52.66286, trying to figure out why fixed, and saved 8 bytes in the process =D
a=43, b=21, n=10005 - takes ~80 seconds (but gives the right angle)

readable version:

from math import *
def bill(a,b,n):
    a=float(a)
    b=float(b)
    ratios = set()
    for i in range(0,n+2): # Create the new boards
        outter = []
        j=i+1
        for k in range(1,j): # Calculate the new holes for each board
            #y=k
            for hole_offset in [0,0.5]:
                x=(j-k-hole_offset)
                if (x/k) not in ratios:
                    ratios.add(x/k)
                    outter.append((x*a,k*b))
    min_dist = (a*n+1)**2+(b*n+1)**2
    for x,y in outter:
        if x*x+y*y<min_dist:
            min_dist = x*x+y*y
            min_alpha=degrees(atan(y/x))
    return min_alpha
\$\endgroup\$
  • \$\begingroup\$ You can save a byte by removing the space in : degrees \$\endgroup\$ – Morgan Thrapp Dec 16 '15 at 19:21
  • \$\begingroup\$ I have no idea how your answer works (mathwise) but I think you can gain 1 byte by removing the space after the colon. :) (What @MorganThrapp said) \$\endgroup\$ – basile-henry Dec 16 '15 at 19:23
  • 2
    \$\begingroup\$ This path is valid, but it's not the shortest in all cases, for example with 2 1 4.. \$\endgroup\$ – Damien Dec 16 '15 at 20:13
  • \$\begingroup\$ This also assumes that b < a. That could easily fixed by getting the minimum/maximum of a and b though. \$\endgroup\$ – user81655 Dec 16 '15 at 21:31
  • \$\begingroup\$ fixed  ( sorta ) \$\endgroup\$ – Rod Dec 17 '15 at 12:02
3
\$\begingroup\$

Haskell, 133 117 bytes

This is my implementation:

With a 2x1 table, a path will hit exactly n cushions before going into a pocket if: (x-1)/2 + (y-1) == n and x,y are mutually primes. where x,y are the distance of the ball over horizontal/vertical axes.

Paths are the same with arbitrary table size, so we just have to update lengths and angles with (a,b) and keep the shortest. Path length is sqrt((x*a/2)^2+(y*b)^2) and angle is atan((y*b)/(x*a/2))

z=toEnum
f a b n=minimum[[z x^2+r^2,180/pi*atan(r/z x)]|x<-[1..2*n+2],y<-[n+1-div(x-1)2],r<-[2*b/a*z y],gcd x y<2]!!1
\$\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.