Igualdad de oscilación

15

Tenemos objetos que oscilan entre dos puntos enteros, [l, r]a la velocidad de una unidad por unidad de tiempo, a partir de lel t=0. Puedes asumir l < r. Por ejemplo, si un objeto oscila [3, 6], entonces tenemos:

t=0 -> 3
t=1 -> 4
t=2 -> 5
t=3 -> 6
t=4 -> 5
t=6 -> 4
t=7 -> 3
t=8 -> 4

Etc. Pero los objetos oscilan continuamente, por lo que también tenemos t=0.5 -> 3.5y t=3.7 -> 5.3.

Dados dos objetos que oscilan entre [l1, r1], [l2, r2]determine si alguna vez hay un tiempo ttal que los dos objetos compartan la misma posición. Puede tomar l1, r1, l2, r2en cualquier formato conveniente y generar cualquier valor verdadero / falso.


Entradas de verdad:

[[3, 6], [3, 6]]
[[3, 6], [4, 8]]
[[0, 2], [2, 3]]
[[0, 3], [2, 4]]
[[7, 9], [8, 9]]

Entradas de falsa:

[[0, 3], [3, 5]] 
[[0, 2], [2, 4]]
[[5, 8], [9, 10]]
[[6, 9], [1, 2]]
[[1, 3], [2, 6]]
orlp
fuente
así que es una ola puntiaguda, no una sinusoide, ¿verdad?
HyperNeutrino
Como referencia, este desafío se refiere a este juego , donde debes detectar si es posible saltar de un bloque a otro.
user202729
@HyperNeutrino Correcto.
orlp
¿Puede el valor falso ser 0verdadero y ser un número entero positivo o deben ser consistentes? Aún más, ¿puede ser falsa la lista vacía y la verdad puede ser cualquier lista no vacía?
Sr. Xcoder
3
Una buena prueba falsa es [[1,3],[2,6]]: esto falsifica la heurística "los intervalos se superponen y no tienen la misma longitud".
Misha Lavrov

Respuestas:

6

Casco , 13 bytes

VEΣUẊeTmȯ…¢mD

Toma entrada en formato [[l,r],[L,R]] . Devuelve 0para instancias falsas y un entero positivo para instancias verdaderas. Pruébalo en línea!

Explicación

Las ideas principales son

  1. Una colisión solo puede ocurrir en una coordenada entera o media entera.
  2. Es suficiente simular el sistema hasta que se encuentre una repetición de dos estados consecutivos.

Aquí está el código anotado.

VEΣUẊeTmȯ…¢mD  Implicit input, say [[0,2],[2,3]]
       mȯ      For both pairs do:
           mD   Double each: [[0,4],[4,6]]
          ¢     Cycle: [[0,4,0,4..],[4,6,4,6..]]
         …      Rangify: [[0,1,2,3,4,3,2,1,0,1,2..],[4,5,6,5,4,5,6..]]
      T        Transpose: [[0,4],[1,5],[2,6],[3,5],[4,4],[3,5],[2,6]..
    Ẋe         Adjacent pairs: [[[0,4],[1,5]],[[1,5],[2,6]],[[2,6],[3,5]],[[3,5],[4,4]]..
   U           Prefix of unique elements: [[[0,4],[1,5]],[[1,5],[2,6]],[[2,6],[3,5]],[[3,5],[4,4]]..[[1,5],[0,4]]]
  Σ            Concatenate: [[0,4],[1,5],[1,5],[2,6],[2,6],[3,5],[3,5],[4,4]..[1,5],[0,4]]
VE             Index of first pair whose elements are equal (or 0 if not found): 8
Zgarb
fuente
Slick answer. ¿Por qué necesitas duplicar cada uno? ¿Es para convertir la afirmación "las colisiones solo pueden ocurrir en enteros o medios enteros" en "las colisiones solo pueden ocurrir en enteros"?
Jonás
@ Jonás Sí, exactamente.
Zgarb
2

JavaScript (ES6), 104100 bytes

Una implementación ingenua que solo ejecuta la simulación. Toma (a, b, c, d) como 4 variables distintas.

(a,b,c,d)=>(g=(X,Y)=>x==y|x+X==y&(y+=Y)==x||(x+=X)-a|y-c&&g(x>a&x<b?X:-X,y>c&y<d?Y:-Y))(1,1,x=a,y=c)

Casos de prueba

Arnauld
fuente
2

Wolfram Language (Mathematica) , 77 69 61 bytes

If[#>#3,#0[##3,#,#2],(z=GCD[x=#-#2,#3-#4])Mod[x/z,2]<=#2-#3]&

Una función pura que toma los cuatro argumentos l1, r1, l2, r2como entrada: por ejemplo, [0,3,2,4]cuando los intervalos son [0,3]y [2,4].

Pruébalo en línea!

Cómo funciona

Para obtener un punto [a,b]cercano a un punto adentro [c,d], suponiendo a<c<b<d, queremos un múltiplo impar b-adentro b-cde un múltiplo par de d-c. Si b-atiene más factores de 2que d-c, podemos hacer que esto suceda exactamente: habrá un momento en que el primer punto esté en by el segundo punto esté en c, y entonces estamos en buena forma. Si no, entonces lo mejor que podemos hacer es el MCD de b-ay d-c.

Misha Lavrov
fuente
1

JavaScript (ES6), 89 bytes

(a,b,c,d)=>[...Array((b-=a)*(d-=c)*4)].some((g=e=>i/e&2?e-i/2%e:i/2%e,i)=>a+g(b)==c+g(d))

Toma l1,r1,l2,r2como argumentos separados. Explicación: Se garantiza que la simulación se repetirá después de las (r1-l1)*(r2-l2)*2unidades de tiempo (o un factor de la misma); gcalcula el desplazamiento del objeto apropiado después de las i/2unidades de tiempo, por lo que idebe variar hasta (r1-l1)*(r2-l2)*4.

Neil
fuente
1

05AB1E , 12 10 14 bytes

+4 bytes para manejar rangos negativos

Devuelve 0 si es falso o un entero positivo de lo contrario

Usa la idea de Zgarb de de duplicar valores para facilitar la detección de la misma posición

Gracias a @ Zacharý por señalar mis errores

ÄZU\·εXиŸ}øüQO

Pruébalo en línea!

Explicaciones:

ÄZU\·εXиŸ}øüQO 
ÄZU\            Store in X the largest absolute number in the lists
    ·           Double lists ([3,6],[4,8] => [6,12],[8,16])
     ε   }      For each...
      X             Push X
       и            List-repeat that much times ([6,12]*12 => [6,12,6,12,6,...])
        Ÿ           Rangify ([6,12,6,...] => [6,7,8,9,10,11,12,11,...])
          ø     Zip lists ([6,7,8,...],[8,9,10,...] => [6,8],[7,9],[8,10],...)
           üQ   1 if both elements of a pair are equal, 0 otherwise
             O  Sum result list (=0 if the same position is never shared)
                Implicit output
scottinet
fuente
No creo que esto funcione para grandes rangos de listas, porque 100 parece bastante arbitrario.
Zacharý
@ Zacharý Gracias! Lo arreglé de una manera muy ineficaz, ya que ahora las listas se repiten demasiadas veces. :-)
scottinet
En realidad, esto podría no funcionar todavía (no me molestaré en averiguar cómo, porque tomaría demasiado tiempo, y honestamente, las listas tendrían que ser un rango pequeño y un rango ENORME de lo que creo que no funcionará) )
Zacharý
@ Zacharý Debería funcionar para enteros positivos arbitrarios, ya que el peor de los casos sería [[0,n],[n-1, n]]e incluso en ese caso, la segunda lista se repetiría suficientes veces (y más) para que la primera alcanzara su límite superior. Pero olvidé tener en cuenta los números negativos: [[-100, 1], [0, 1]]no funciona. Arreglando a un costo de 4 bytes :-(
scottinet