Predecir una colisión: ¿El ladrón se escapará?

Step Hen 08/17/2017. 15 answers, 1.157 views
code-golf decision-problem

Piensa en un camino como una línea numérica, comenzando en 0 y continuando indefinidamente:

................................................................. 

Hay dos coches en la carretera: C y R C es el policía que está tratando de atrapar a R , el ladrón. C comienza en 0 y R comienza en alguna parte de la carretera:

C.............................R.................................. 

El policía ya se está moviendo - está persiguiendo al ladrón. Él tiene una velocidad constante. El ladrón se metió en el coche. Está acelerando. Cada tick, la velocidad del ladrón aumenta por su aceleración.

Digamos que la velocidad del policía es 7 y la aceleración del ladrón es 1 . Si el ladrón comienza a los 30 , esto es lo que el camino se vería como cada tick:

C.............................R..................................
.......C.......................R.................................
..............C..................R...............................
.....................C..............R............................
............................C...........R........................
...................................C.........R...................
..........................................C........R.............
.................................................C........R...... 

Después de la última marca de arriba, la velocidad del ladrón es igual a la del policía, y todavía está por delante. Dado que el policía se está moviendo a una velocidad constante y el ladrón sigue acelerando, el ladrón se escapa, por lo que la salida de un valor verídico. Sin embargo, si la velocidad del policía había sido 9 ...

C.............................R..................................
.........C.....................R.................................
..................C..............R...............................
...........................C........R............................
....................................C...R........................
.............................................X................... 

... entonces el policía atrapa al ladrón antes de que el ladrón pueda escaparse (marcado con la X ), por lo que sale un valor de false.

Tu tarea

Dadas tres entradas - la velocidad del policía, la posición del ladrón, y la aceleración del ladrón - determinan si o no el ladrón conseguirá lejos.

Reglas

  • El policía siempre empieza en 0 .
  • Todas las entradas serán enteros positivos.
  • El policía coge al ladrón si, después de cualquier señal, la posición del policía es mayor o igual que la posición del ladrón.
  • El ladrón se aleja cuando aún no ha sido capturado y su velocidad es mayor que la del policía.
  • Su programa debe terminar después de la salida.
  • El ladrón acelera antes de mover cada garrapata.

Casos de prueba

Cop Speed, Robber Position, Robber Acceleration -> Output 

7, 30, 1 -> truthy
9, 30, 1 -> falsey
2, 1, 3 -> truthy
100, 100, 50 -> truthy
60, 60, 20 -> falsey
10, 1, 1 -> falsey
10, 50, 2 -> truthy
11, 50, 2 -> truthy
12, 50, 2 -> truthy
13, 50, 2 -> truthy
14, 50, 2 -> truthy
15, 50, 2 -> truthy
16, 50, 2 -> falsey
17, 50, 2 -> falsey
18, 50, 2 -> falsey
100, 451, 10 -> truthy 

Referencia Implementación de Python 3 que crea un visual también: ¡ Pruébalo en línea!

Esto es , por lo que la respuesta más corta en bytes gana.

5 Comments
Step Hen 08/11/2017
Sandbox (eliminado)
8 Magic Octopus Urn 08/11/2017
Ohhhh ... esto no es un reto de policías y ladrones; eso tiene más sentido.
TehPers 08/11/2017
¿Se garantiza la entrada en el formato dado, o podemos tomar entrada en cualquier formato que queramos (como robber acceleration, cop speed, robber position lugar)?
Step Hen 08/11/2017
@TehPers lo que quieras (consistente cada vez), pero si estás haciendo algo diferente decirlo en tu respuesta
2 Neil 08/11/2017
Solicitud de caso de prueba: 100, 451, 10. (Las respuestas no coinciden en el resultado).

15 Answers


Leaky Nun 08/11/2017.

Python 3 , 29 bytes

 lambda s,p,a:(a-2*s)**2<8*a*p 

Pruébelo en línea!

Explicación

La posición del policía en el tiempo t es st .

La posición del ladrón en el tiempo t es a(t)(t+1)/2 + p .

La distancia firmada entre el policía y el ladrón es (a/2)t^2 + (a/2-s)t + p .

Nunca llega a cero si el discriminante es negativo, siendo el discriminante (a/2 - s)^2 - 4(a/2)(p) = [(a-2s)^2-8ap]/4 , Mismo signo que (a-2s)^2-8ap .

3 comments
3 Mr. Xcoder 08/11/2017
+1 Debería haber hecho el puño de Física :))
Magic Octopus Urn 08/11/2017
Pruébelo en línea! - Puerto desvergonzado a 05AB1E para 9 bytes (puedes tomarlo, ya que soy malo con Física, y probablemente no podría hacer una explicación justa).
Mark S. 08/13/2017
¿No falla esto para el caso de prueba "100, 451, 10 -> verdad"?

ETHproductions 08/11/2017.

Japt , 13 bytes

²/W-V-U 

Prueba en línea!

Explicación

U , V y W son las entradas implícitas. Primero, con Uo0W creamos el rango [0, W, 2*W, ...] hasta que alcanza U x entonces suma esto, lo que da hasta qué punto el ladrón viaja antes de llegar a la velocidad del policía. Lo llamaremos r .

Ahora, ¿hasta dónde llega el policía en este tiempo? Podemos calcular esto usando U * (U // W - 1) , que puede ser reordenado a (U * U) // W - U Llamaremos esto c .

Ahora para el paso final: ¿el ladrón se escapa? Todo lo que necesitamos hacer aquí es comprobar si c < r + V , o reordenado, c - V < r .


TehPers 08/11/2017.

Cubicamente , 61 bytes

$:7(U1R3U1F3D2*1-1/1)6+7$-77*6$(-77777777D2F1U3R1U3!0{<0%6&}) 

Pruébelo en línea! Para que esto funcione en TIO, es posible que necesite reemplazar & con &1 debido a un error en el intérprete.

Este es un puerto sin vergüenza de la respuesta de la Nudista Leaky . La entrada está en la forma a s p , donde a es la aceleración del ladrón, s es la velocidad del policía, p es la posición del ladrón.

Si la aceleración es demasiado alta, esto fallará. No sé qué tan alta de una aceleración este programa apoyará, pero sé que no es mayor que 1260 . El factor limitante es que almacena la aceleración en el cubo y comprueba si el cubo se resuelve comprobando sólo si la suma de la cara superior es 0 (una verificación incompleta). Parece que funciona para la aceleración = 50, pero no he probado para ver lo alto que puede conseguir.

Cómo funciona

$:7(U1R3U1F3D2*1-1/1)6
$:7                             Store the first number in the notepad
   (                )6          Loop until notepad is 0
    U1R3U1F3D2                  Rotate the cube a certain way
              *1-1/1            Subtract 1 from the notepad

+7$-77*6                
+7                              Add first input to the notepad
  $-77                          Subtract second input from the notepad twice
      *6                        Multiply the notepad by itself (square it)

$(-77777777D2F1U3R1U3!0{<0%6&})
$                               Get next input
 (                            ) Loop indefinitely
  -77777777                     Subtract third input 8 times
           D2F1U3R1U3           "Unrotate" the cube
                     !0{     }  If the top face is 0
                        <0        Check if notepad < 0, store in notepad
                          %6      Output notepad as number
                            &     End the program 

Mr. Xcoder 08/11/2017.

Pyth , 11 bytes

Esto los toma en este orden: Robber Acceleration, Cop Speed, Robber Position separada por una nueva línea (como se muestra en la suite de pruebas).

<^-QyE2*8*E 

Test Suite o Try it online!


Mr. Xcoder 08/11/2017.

Pyke , 14 bytes

Puerto de la respuesta de Python de totalhuman . Devuelve 1 para verdades y 0 para falsas.

hQee-XQ1@Qe*}< 

Try it here!


Explicación

hQee-XQ1@Qe*}< - Full program with implicit input added in the beginning (which automatically splits the components)

h              - First input
 Qee           - Last Input halved (through integer division)
    -          - Subtact the above
     X         - Square.
             < - Is smaller than?
      Q1@      - The second input
         Qe*   - Multiplied by the last input
            }  - Doubled 

Pyke , 15 bytes

Mi primera respuesta Pyke! Puerto de mi solución Pyth , que se inspira en la presentación de Python Leaky . Devuelve 1 para verdades y 0 para falsas.

eQh}-XQe8*Q1@*< 

Try it here!


Explicación

eQh}-XQe8*Q1@*< - Full program with implicit input added in the beginning (which automatically splits the components)

e               - End; last input in this case
 Qh             - The first input
   }            - Double
    -           - Subtact the above
     X          - Square.
              < - Is less than?
      Qe        - Last Input
        8*      - Times 8 
             *  - Multiplied by
          Q1@   - The second input. 

Erik the Outgolfer 08/12/2017.

Jalea , 9 bytes

_⁵Ḥ¤²÷÷8< 

Pruébelo en línea!

Puerto de Leaky Nun's Python 3 respuesta.

(Programa completo) Toma argumentos en orden de acceleration, position, speed .


Mr. Xcoder 08/11/2017.

Python 2 , 62 bytes

 P=s=0;S,p,a=input()
while(s=S 

Pruébelo en línea!


itdoesntwork 08/11/2017.

Ruby , 29 27 25 bytes

 ->c,p,a{(a-c-c)**2<8*p*a} 

Pruébelo en línea!

Conseguimos de 29 a 27 robando la idea de multiplicar ambos lados por 4. (Leaky Nun's python answer)

Obtenido de 27 a 25 por la eliminación de parens alrededor de parámetros lambda (gracias totalmentehuman)

4 comments
2 Conor O'Brien 08/11/2017
¡Bienvenido a PPCG! Usted puede golf su respuesta un poco renombrando su función de hit a h o similar. También puedes guardar algunos bytes cambiando de un método a un proc, como así: ->c,p,a{(c-a*0.5)**2<2*p*a}
1 Leaky Nun 08/11/2017
También es necesario reemplazar la collision en su enlace TIO con el nombre del método correcto.
totallyhuman 08/11/2017
Pssst, mira su nombre de usuario. :PAG
1 totallyhuman 08/11/2017
Estoy bastante seguro de que no necesita los paréntesis alrededor de c,p,a .

Kamil Drakari 08/11/2017.

C # (.NET Core) , 33 bytes

 (v,p,a)=>v/a*v 

Pruébelo en línea!

Me siento como si esto fuera por alguna parte, pero pasa por todos los casos de prueba por lo que es posible que simplemente no hay casos de prueba donde el policía llega al ladrón de una sola garrapata, o podría funcionar a pesar de mis reservas.


totallyhuman 08/11/2017.

Python 2 , 31 30 29 bytes

-1 byte thanks to Mr. Xcoder.

Empezó como un puerto de la respuesta Ruby .

 lambda c,p,a:(c-a/2)**2<2*p*a 

Pruébelo en línea!

4 comments
1 Mr. Xcoder 08/11/2017
.5 lugar de 0.5 > _>
totallyhuman 08/11/2017
Haha, pensé que sería justo que mucho al puerto. Gracias XD!
itdoesntwork 08/11/2017
a/2 usa la división entera, ¿podría esto salir mal?
totallyhuman 08/11/2017
Utiliza división entera. Aunque no he calculado matemáticas (para ser honesto, no estoy seguro de poder hacerlo), funciona para todos los casos de prueba.

Mr. Xcoder 08/11/2017.

Swift 3 , 55 bytes

Tenga en cuenta que declaré la variable t porque la expresión sería demasiado compleja para ser resuelta en un tiempo razonable de lo contrario (¡culpa de Swift!).

 func f(a:Int,b:Int,c:Int){let t=c-2*a;print(t*t<8*c*b)} 

Test Suite.

or 55 bytes , equivalente al cierre exacto (necesito la última parte porque es un constructo complejo):

 {let t=$2-2*$0;return t*t<8*$2*$1}as(Int,Int,Int)->Bool 

Test Suite.

Swift 3 , 57 bytes

 func f(a:[Int]){let t=a[2]-2*a[0];print(t*t<8*a[2]*a[1])} 

Test Suite.


Neil 08/11/2017.

Python 2 , 30 bytes

 lambda c,p,a:c/a*(c-a+c%a)/2 

Pruébelo en línea! El policía tiene c/a garrapatas en el que para atrapar al ladrón, después de lo cual ha acelerado el policía. En la primera garrapata el poli gana c-a en el ladrón mientras que en la última garrapata sólo gana c%a . Así, el total que puede obtener el policía es el producto del número de garrapatas y la distancia media por garrapata. Esto es simplemente comparado con el liderazgo inicial del ladrón.


Jakob 08/12/2017.

TI BASIC (serie TI-83/84), 18 bytes

Prompt C,R,A
(A-2C)²<8RA 

Otro puerto de la influyente solución Ruby de itdoesntwork .

Ejecución

El orden de entrada es la velocidad de los policías, la posición de los ladrones, la aceleración de los ladrones.

C=?7
R=?30
A=?1
               1 

Neil 08/13/2017.

Retina , 79 bytes

\d+
$*
$
;
{`(1+);
$1;$1
,(1+;(1+))
$2,$1
1`(1+),\1
$1,
.*,,.*

^(1+),.*;\1.*
1 

Pruébelo en línea! Explicación:

\d+
$* 

Convertir la entrada en unary.

$
; 

Hacer espacio para la velocidad del ladrón.

{`(1+);
$1;$1 

Acelerar al ladrón en cada paso.

,(1+;(1+))
$2,$1 

Aleja al ladrón del policía.

1`(1+),\1
$1, 

Mueve al policía hacia el ladrón.

.*,,.* 

¿Ha pillado el policía al ladrón?

^(1+),.*;\1.*
1 

¿El ladrón ha acelerado al policía?


officialaimm 08/13/2017.

HighResolutionMusic.com - Download Hi-Res Songs

1 Alan Walker

Diamond Heart flac

Alan Walker. 2018. Writer: Alan Walker;Sophia Somajo;Mood Melodies;James Njie;Thomas Troelsen;Kristoffer Haugan;Edvard Normann;Anders Froen;Gunnar Greve;Yann Bargain;Victor Verpillat;Fredrik Borch Olsen.
2 Sia

I'm Still Here flac

Sia. 2018. Writer: Sia.
3 Cardi B

Taki Taki flac

Cardi B. 2018. Writer: Bava;Juan Vasquez;Vicente Saavedra;Jordan Thorpe;DJ Snake;Ozuna;Cardi B;Selena Gomez.
4 Little Mix

Woman Like Me flac

Little Mix. 2018. Writer: Nicki Minaj;Steve Mac;Ed Sheeran;Jess Glynne.
5 Halsey

Without Me flac

Halsey. 2018. Writer: Halsey;Delacey;Louis Bell;Amy Allen;Justin Timberlake;Timbaland;Scott Storch.
6 Lady Gaga

I'll Never Love Again flac

Lady Gaga. 2018. Writer: Benjamin Rice;Lady Gaga.
7 Bradley Cooper

Shallow flac

Bradley Cooper. 2018. Writer: Andrew Wyatt;Anthony Rossomando;Mark Ronson;Lady Gaga.
8 Bradley Cooper

Always Remember Us This Way flac

Bradley Cooper. 2018. Writer: Lady Gaga;Dave Cobb.
9 Kelsea Ballerini

This Feeling flac

Kelsea Ballerini. 2018. Writer: Andrew Taggart;Alex Pall;Emily Warren.
10 Mako

Rise flac

Mako. 2018. Writer: Riot Music Team;Mako;Justin Tranter.
11 Dewain Whitmore

Burn Out flac

Dewain Whitmore. 2018. Writer: Dewain Whitmore;Ilsey Juber;Emilio Behr;Martijn Garritsen.
12 Avril Lavigne

Head Above Water flac

Avril Lavigne. 2018. Writer: Stephan Moccio;Travis Clark;Avril Lavigne.
13 Khalid

Better flac

Khalid. 2018. Writer: Charlie Handsome;Jamil Chammas;Denis Kosiak;Tor Erik Hermansen;Mikkel Stoleer Eriksen;Khalid.
14 Lady Gaga

Look What I Found flac

Lady Gaga. 2018. Writer: DJ White Shadow;Nick Monson;Mark Nilan Jr;Lady Gaga.
15 Deep Chills

Run Free flac

Deep Chills. 2018.
16 Dynoro

In My Mind flac

Dynoro. 2018. Writer: Georgi Kay;Feenixpawl;Ivan Gough.
17 Charli XCX

1999 flac

Charli XCX. 2018. Writer: Charli XCX;Troye Sivan;Leland;Oscar Holter;Noonie Bao.
18 NCT 127

Regular (English Version) flac

NCT 127. 2018.
19 Lukas Graham

Love Someone flac

Lukas Graham. 2018. Writer: Don Stefano;Morten "Rissi" Ristorp;Morten "Pilo" Pilegaard;Jaramye Daniels;James Alan;David LaBrel;Lukas Forchhammer Graham.
20 Rita Ora

Let You Love Me flac

Rita Ora. 2018. Writer: Rita Ora.

Related questions

Hot questions

Language

Popular Tags