Mykybo Mykybo - 9 months ago 64
C Question

Messages synchronization algorithm

We have two infinitely repeating messages consisting of characters a-z. Each character takes a different amount of time units to transmit; a=1, b=2, c=4, d=8,e=16 ..., character | tells us current position in the message. Our job is to say how many units of time it will take to synchronize the two messages. Synchronization means that both messages begin at the same time.


We have message 1: ea|babab

and message 2: d|abaca

therefor we know that message 1 is bababea and message 2 is: abacad.

The messages will be synchronized in 42 units of time:

ea|bababea| = 42

d|abacad|abacad| = 42

Example 2:
message1: |acabbaaa message 2: |dcbabaaaa.

Solution: 0, because they are already synchronized.

We want to come up with an algorithm which will calculate the time until first synchronization occurs.

I am writing this in C. I have basically everything done, except for the algorithm itself.

I think this could maybe be done using extended Euclidean algorithm.

Answer Source

I have answered a different question but I think solution to this problem is exactly the same. You need to solve the equation m1Offset+(m1Len * intN1) = m2Offset+(m2Len * intN2)

There are some conditions to be satisfied to have a sync point. Please refer to the question and answer for more details.

In the code below,

  • m1Len and m2Len: Length of messages m1 and m2 respectively. Ex: for "ea|babab" length is length of "bababea"=25 and in message "d|abaca", length of "abacad"=17
  • m1Offset and m2Offset: Initial offsets. Ex: In message "ea|babab", "ea" is offset, which is equal to 17. Similarly in "d|abaca", "d" is offset, which is equal to 8.

  • m1Time and m2Time should be equal and that is the first sync time.

Here is my code.

    #include <stdio.h>

    void findVal(unsigned int m1Offset, unsigned int m1Len, unsigned int m2Offset, unsigned int m2Len) ;

    int main()
        findVal(17, 25, 8, 17);
        return 0;

    void findVal(unsigned int m1Offset, unsigned int m1Len, unsigned int m2Offset, unsigned int m2Len) {

        unsigned int  n1       = 0;
        unsigned int  n2       = 0;
        unsigned char foundVal = 1;
        unsigned int  m1Time   = m1Offset;
        unsigned int  m2Time   = m2Offset;

        //No need to find n1 and n2 if msgs are starting from beginning.
        if(((m1Offset == m1Len) && (m2Offset == m2Len)) || ((0 == m1Offset) && (0 == m2Offset)))
            m1Time = 0;
            m2Time = 0;

        //No need to find n1 and n2 if offset times are same.
        else if(m1Offset != m2Offset)
           //Offset times are not same.
           foundVal = 0;
           for(n2=1; n2<(unsigned int)-1; n2++)
               unsigned int temp1 = (m2Len*n2)+(m2Offset-m1Offset);
               if(0 == temp1 % m1Len)
                    n1 = temp1/m1Len;
                    m1Time = m1Offset + n1*m1Len;
                    m2Time = m2Offset + n2*m2Len;

                    foundVal = 1;

        if(1 == foundVal)
            printf("Found n1[%u] n2[%u] m1Time[%u] m2Time[%u]\n", n1, n2, m1Time, m2Time);
            printf("Could not find n1, n2, m1Time, m2Time\n");


Found n1[1] n2[2] m1Time[42] m2Time[42]