Jouer au billard

17

Dans ce code de golf, vous devrez déterminer la direction du tir le plus court qui touche exactement n coussins avant de tomber dans une poche.

La table de billard est une table de billard 6 poches avec les caractéristiques suivantes:

  • Les dimensions sont variables ( a x b )
  • Pas de frottement: la balle roulera pour toujours jusqu'à ce qu'elle tombe dans une poche
  • Les poches et les balles sont presque nulles. Cela signifie que le ballon ne tombera dans la poche que s'ils ont la même position.
  • La balle est placée dans le trou en bas à gauche au début (mais n'y tombe pas)

3 coussin

Créez un programme ou une fonction complète qui prend les dimensions ( a , b ) de la table et le nombre de coussins à frapper n en entrée et renvoie l'angle en degrés du chemin le plus court atteignant exactement n coussins avant de tomber dans une poche.

  • a > 0
  • b > 0
  • 0 <= n <10000000
  • 0 < alpha <90 (en degrés) précision: au moins 10 ^ -6

exemples :

avec a = 2, b = 1, n = 1, il y a trois chemins possibles: (1) (2) (3) sur la figure suivante. le nombre (1) est le plus court donc la sortie doit être atan (2) = 63,43494882292201 degrés

1 coussin

La solution pour a = 2, b = 1, n = 4 est atan (4/3) = 53.13010235415598 degrés

4 coussins

échantillons d'essai:

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

C'est le golf code / billard: le code le plus court gagne!

Damien
la source
La balle doit-elle frapper exactement les n coussins, ou du moins les n coussins?
Peter Taylor
@PeterTaylor exactement n coussins
Damien
N'est-ce pas le chemin le plus court toujours dans les deux sens entre le haut et le bas du côté gauche puis dans l'un des trous du milieu?
Eumel
non, regardez l'exemple 2 1 4. Ce chemin est sqrt (25) = 5 long alors que votre solution est sqrt (26)
Damien

Réponses:

11

Python 2.7, 352 344 281 octets

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 octets grâce à @Dschoni

Explication: au lieu de calculer les coups de coussins, j'ajoute n tables et je prends les nouveaux trous comme valides: billard la bordure / les trous noirs est l'original, la bordure / les trous verts est la valeur valable pour n = 1, la bordure / les trous rouges est la valeur valide pour n = 2 et ainsi de suite. Ensuite, je supprime les trous invalides (par exemple la flèche bleue pour n = 1). Je vais avoir une liste de trous valides et leurs coordonnées, puis je calcule leur distance par rapport au point initial, puis l'angle de la plus petite distance.
Notes:
a = 4,76, b = 3,64, n = 27 - donnez 52,66286, en essayant de comprendre pourquoi corrigé et enregistré 8 octets dans le processus = D
a = 43, b = 21, n = 10005 - prend ~ 80 secondes ( mais donne le bon angle)

version lisible:

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
Barre
la source
Vous pouvez enregistrer un octet en supprimant l'espace dans : degrees
Morgan Thrapp
Je n'ai aucune idée du fonctionnement de votre réponse (mathématiquement) mais je pense que vous pouvez gagner 1 octet en supprimant l'espace après les deux points. :) (Ce que @MorganThrapp a dit)
basile-henry
2
Ce chemin est valide, mais ce n'est pas le plus court dans tous les cas, par exemple avec 2 1 4 ..
Damien
Cela suppose également cela b < a. Cela pourrait facilement être corrigé en obtenant le minimum / maximum de aet bbien.
user81655
fixe (sorta)
Rod
3

Haskell, 133 117 octets

Voici ma mise en œuvre:

Avec une table 2x1, un chemin atteindra exactement n coussins avant d'entrer dans une poche si: (x-1) / 2 + (y-1) == n et x, y sont mutuellement premiers. où x, y sont la distance de la balle sur les axes horizontal / vertical.

Les chemins sont les mêmes avec une taille de table arbitraire, il nous suffit donc de mettre à jour les longueurs et les angles avec (a, b) et de garder le plus court. La longueur du chemin est sqrt ((x * a / 2) ^ 2 + (y * b) ^ 2) et l'angle est 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
Damien
la source