Algorithm for finding the intersection of two or more songs

Question

Suppose we have a bunch of radio stations, and each radio plays the same song over and over again on the loop. Can I sync all songs from all radio stations? Can we find a time when we hear all the songs from the start?

For simplicity, we will say that we have only two radio stations.

I have the following formulas:

c and z represent the length of the song in seconds. a and x represent the current position in the song (in seconds) S represents the synchronization time of C and Z. (When both songs start at the same time)

For example:

Song 1 a = 17 : the time before the song ends. b = 8 : the rest of the song. c = a + b which is the full song in seconds. And Song 2 x = 8 : the time before the song ends. y = 9 : the rest of the song. z = 8 + 9 which is the full song in seconds. Song 1 : a + ( a + b) => S Song 2 : x +(( x + y ) × n) => S Song 1 : 17 + ( 17 + 8) => 42 Song 2 : 8 + ((8 + 9)) = 25 So in order to synchronize song 2 with song 1 we have to multiply (x + y) by two and add x to it. Song 2 : 8 + ((8 + 9) x 2) => 42 So S = 42 and so the two songs will synchronize after 42 seconds. 

Now this first example is the simplest. For other cases, I would have to multiply z and c by more than two to get the corresponding S.

I have a few other inputs, and I tried to come up with an algorithm that would return S to me, but I had no luck with that.

Here is what I came up with so far:

 c = a + b a = 16 b = 4 c = 20 s = 216 

and

 z = x + y x = 12 y = 5 z = 17 s = 216 S is the LCM of c and z 

In the first example, S was found as follows:

 s = x +(z × n) n = ( s − x ) ÷ b 12 + ( 17 × 12) = 216 

and

 s = a + (c × n) n = ( s − a ) ÷ b 16 + ( 20 × 10 ) = 216 

I came up with two formulas below. Based on the value of S. But I need to figure out a way to search for n without actually using S. Or, in other words, I need to find out how many times I have to multiply (a + b) by n and (x + y) by n to get S.

 n = ( s − a ) ÷ b S = x + ( y × n) 

But these formulas obviously will not work because they require S. And we cannot use this because it must be the result of the formula that I am trying to come up with.

Here are some examples for some calculations:

 a2 = 52 b2 = 4 c2 = 56 s2 = 276 x2 = 60 y2 = 12 z2 = 72 s2 = 276 

Here is a situation where it will never be synchronized:

 A1 = 14 B1 = 4 C1 = 18 S1 = Never synchronizes A2 = 19 B2 = 5 C2 = 24 S2 = Never synchronizes 

And here is a situation where the songs are already in sync:

Case 1

 A2 = 17 B2 = 0 C2 = 17 S4 = 0 A3 = 25 B3 = 0 C4 = 25 S4 = 0 

Case 2

 A4 = 0 B4 = 13 C4 = 13 S4 = 0 A5 = 0 B5 = 21 C5 = 21 S5 = 0 

I was thinking about using the least common plural, but I'm not sure how to implement it in this situation or if this is the right solution for this problem.

The algorithm I want to find should also work if there are more than two songs. For example, finding S for 3 or 4 songs.

The main problem with this algorithm is to solve two songs Synchronize or not, the calculation itself is not so complicated. could you help me? thanks in advance

Answer 1

The smallest common multiple of c and z is the interval between consecutive moments that are synchronized by songs (if they are synchronized at all). This means that if we can determine once, we can find the rest by adding (or subtracting) a multiple of LCM. To find this time (and indeed, LCM), use the advanced Euclidean algorithm to find integers T, U that satisfy the equation

  (c - a) + T*c = (z - x) + U*z 

which is equivalent when substituting V = -U in

  T*c + V*z = (c - a) - (z - x). 

Find GCD c and z detail, make sure it divides (c - a) - (z - x) , then multiply the Bézout coefficients by ((c - a) - (z - x))/GCD(c, z) .

Answer 2

I wrote this code with the logic that I mentioned in the comments. The basic idea is to find the integers n1 and n2 such that (n1 * c) - (n2 * z) = (xa)

A brief explanation of how I came to this equation:

s1 = a + (n1 * c)

s2 = x + (n2 * z)

We need s1 = s2

=> a + (n1 * c) = x + (n2 * z)

=> (n1 * c) - (n2 * z) = (xa)

We need to find n1 and n2 that satisfies the above equation. A solution exists if and only if GCD c and z divides (xa) .

Please note: this logic works for two stations.

Here is my code.

 #include <stdio.h> void findVal(unsigned int a, unsigned int c, unsigned int x, unsigned int z) ; unsigned int getGCD(unsigned int n1, unsigned int n2); int main() { findVal(2, 37, 3, 43); return 0; } void findVal(unsigned int a, unsigned int c, unsigned int x, unsigned int z) { unsigned int n1 = 0; unsigned int n2 = 0; unsigned char foundVal = 1; unsigned int s1 = a; unsigned int s2 = x; //No need to find n1 and n2 if songs are already at the starting point. if((a == c) && (x == z)) { s1 = 0; s2 = 0; } //No need to find n1 and n2 if remaining times are same. else if(a != x) { //Remaining times are not same. foundVal = 0; //Find GCD of c and z. unsigned int gcd = getGCD(c, z); //There is a solution only if the difference of x and a is divisible by the gcd. if(0 == (xa) % gcd) { for(n2=1; n2<(unsigned int)-1; n2++) { unsigned int temp1 = (z*n2)+(xa); if(0 == temp1%c) { n1 = temp1/c; s1 = a + n1*c; s2 = x + n2*z; foundVal = 1; break; } } } } if(1 == foundVal) { printf("Found n1[%u] n2[%u] s1[%u] s2[%u]\n", n1, n2, s1, s2); } else { printf("Could not find n1 and n2\n"); } } unsigned int getGCD(unsigned int n1, unsigned int n2) { while(n1!=n2) { if(n1 > n2) n1 -= n2; else n2 -= n1; } printf("GCD = %u\n",n1); return n1; } 

Output:

 Found n1[21] n2[18] s1[793] s2[793] 

Answer 3

I came up with a workaround to sync more than two songs, but it will take a long time!

• If the current positions of all songs are 0 , then they are already synchronized.
• If the remaining length of all songs is the same , they will sync after this remaining length.
• If these tests above (for trivial cases) fail, we use a heuristic approach:

We can use an object for each song with the following properties:

• current position, x
• remaining length, y
• total length, z = x + y
• reproduced length, p

We create one such object for each song. The values x and y are entered by the user, z calculated, and p initialized to x .

 create a Min-Heap for the objects based on their `p` values. for ( i = 1; i <= some_reasonable_value_like_10000; i++ ) { if (the `p` values of all objects are same) then break from the loop else increase the `p` value of the root of Min-Heap by `z` value of the corresponding object (and heapify, if required) } if ( i <= some_reasonable_value_like_10000) return `p` value of any object! 

In most cases, this algorithm will take exponentially, but is useful if there are many songs. In addition, it does not depend on the primitiveness or divisibility of the parameters.

Greetings and suggestions on the algorithm are welcome!