15
\$\begingroup\$

We have objects that oscillate between two integer points, [l, r], at the speed of one unit per time unit, starting at l on t=0. You may assume l < r. For example, if an object oscillates on [3, 6], then we have:

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. But objects oscillate continuously, so we also have t=0.5 -> 3.5 and t=3.7 -> 5.3.

Given two objects oscillating between [l1, r1], [l2, r2], determine if there is ever a time t such that the two objects share the same position. You make take l1, r1, l2, r2 in any convenient format, and output any truthy/falsy values.


Truthy inputs:

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

Falsy inputs:

[[0, 3], [3, 5]] 
[[0, 2], [2, 4]]
[[5, 8], [9, 10]]
[[6, 9], [1, 2]]
[[1, 3], [2, 6]]
\$\endgroup\$
  • \$\begingroup\$ so it's a pointy wave not a sinusoid, right? \$\endgroup\$ – HyperNeutrino Oct 23 '17 at 16:40
  • \$\begingroup\$ For reference this challenge refer to this game, where you have to detect if it is possible to jump from one block to the other. \$\endgroup\$ – user202729 Oct 23 '17 at 16:42
  • \$\begingroup\$ @HyperNeutrino Correct. \$\endgroup\$ – orlp Oct 23 '17 at 16:49
  • \$\begingroup\$ Can the falsy value be 0 and truthy any positive integer or must they be consistent. Even more, can falsy be the empty list and truthy be any non-empty list? \$\endgroup\$ – Mr. Xcoder Oct 23 '17 at 17:10
  • 3
    \$\begingroup\$ A good falsy test is [[1,3],[2,6]]: this falsifies the heuristic "the intervals overlap and are not the same length". \$\endgroup\$ – Misha Lavrov Oct 23 '17 at 20:32
8
\$\begingroup\$

Python 2, 69 bytes

l,r,L,R=input()
d=r-l;k=1
while(R-L)*k%d:k+=1
print r-L>=k%2*d/k<=R-l

Try it online!

\$\endgroup\$
6
\$\begingroup\$

Husk, 13 bytes

VEΣUẊeTmȯ…¢mD

Takes input in format [[l,r],[L,R]]. Returns 0 for falsy instances and a positive integer for truthy instances. Try it online!

Explanation

The main ideas are

  1. A collision can only happen at an integer or half-integer coordinate.
  2. It's enough to simulate the system until a repetition of two consecutive states is encountered.

Here's the code annotated.

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
\$\endgroup\$
  • \$\begingroup\$ Slick answer. Why do you need to double each? Is that to turn the statement "collisions can only happen at integers or half integers" into "collisions can only happen at integers"? \$\endgroup\$ – Jonah Oct 23 '17 at 22:15
  • \$\begingroup\$ @Jonah Yes, exactly. \$\endgroup\$ – Zgarb Oct 24 '17 at 6:04
2
\$\begingroup\$

JavaScript (ES6), 104 100 bytes

A naive implementation that just runs the simulation. Takes (a, b, c, d) as 4 distinct variables.

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

Test cases

let f =

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

console.log('Truthy')
console.log(f(3, 6, 3, 6))
console.log(f(3, 6, 4, 8))
console.log(f(0, 2, 2, 3))
console.log(f(0, 3, 2, 4))
console.log(f(7, 9, 8, 9))

console.log('Falsy')
console.log(f(0, 3, 3, 5))
console.log(f(0, 2, 2, 4))
console.log(f(5, 8, 9, 10))
console.log(f(6, 9, 1, 2))

\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 77 69 61 bytes

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

A pure function taking the four arguments l1, r1, l2, r2 as input: e.g., [0,3,2,4] when the intervals are [0,3] and [2,4].

Try it online!

How it works

To get a point in [a,b] close to a point in [c,d], assuming a<c<b<d, we want an odd multiple of b-a within b-c of an even multiple of d-c. If b-a has more factors of 2 than d-c, we can make this happen exactly: there will be a time when the first point is at b and the second point is at c, and then we're in good shape. If not, then the best we can do is the GCD of b-a and d-c.

\$\endgroup\$
1
\$\begingroup\$

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

Takes l1,r1,l2,r2 as separate arguments. Explanation: The simulation is guaranteed to repeat after (r1-l1)*(r2-l2)*2 time units (or a factor thereof); g calculates the offset of the appropriate object after i/2 time units, so i needs to range up to (r1-l1)*(r2-l2)*4.

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 12 10 14 bytes

+4 bytes to handle negative ranges

Return 0 if falsy, or a positive integer otherwise

Use Zgarb's idea of doubling values to make same position detection easier

Thanks to @Zacharý for pointing out my mistakes

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

Try it online!

Explanations:

Ä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
\$\endgroup\$
  • \$\begingroup\$ I don't think this will work for large list ranges, because 100 seems pretty arbitrary. \$\endgroup\$ – Zacharý Oct 25 '17 at 22:52
  • \$\begingroup\$ @Zacharý Thanks! I've fixed it in a very ineffective way, since now lists are repeated way too many times. :-) \$\endgroup\$ – scottinet Oct 26 '17 at 10:23
  • \$\begingroup\$ Actually, this might not work still (I won't be bothered to figure out how, because it would take too long, and honestly, the lists would have to be a tiny range and a HUGE range from what I think won't work) \$\endgroup\$ – Zacharý Oct 26 '17 at 10:48
  • \$\begingroup\$ @Zacharý It should work for arbitrary large positive integers, since the worst case would be [[0,n],[n-1, n]] and even in that case, the second list would be repeated enough times (and more) for the first one to reach its upper bound. But I forgot to take negative numbers into account: [[-100, 1], [0, 1]] does not work. Fixing it at a cost of 4 bytes :-( \$\endgroup\$ – scottinet Oct 26 '17 at 11:59
0
\$\begingroup\$

Java (OpenJDK 8), 81 bytes

(l,r,L,R)->{int d=r-l,k=0;for(;(R-L)*++k%d>0;);return(r-L<R-l?r-L:R-l)>=k%2*d/k;}

Try it online!

Reusing xnor's Python algorithm.

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