Cyclic Redundancy Little Challenge

Thread Starter

MrAl

Joined Jun 17, 2014
6,488
Hi,

I am posting this as a little challenge so maybe i can get better ideas.

The code is to be written so that it can detect a series of redundant code execution where the code is quite simple.

First we have:
if conditionA then
DoA()
elsif conditionB then
DoB()
end if
(note because of the 'if' and 'elsif' it is possible to NOT execute either one);

As you can see there are simply two conditions A and B, and the point is to detect say 5 recurrences of sequential execution of A then B or B then A. If either get executed two times in a row (like A A or B B) or neither gets executed then the count is to be reset so that it only detects A B or B A recurrences. In fact, if it just detects AB recurrences that would probably be good enough.

So it would have to detect AB AB AB AB AB or BA BA BA BA BA
and if at any time we get neither of those (AB or BA) or we get AA or BB we reset the count and start all over again.

The code would of course have to at least include a count say 'cnt' and it would increment on AB or BA and reset on AA or BB or Neither AB or BA.

A last requirement is that the count of recurrences has to be able to be increased or decreased, like say from 3 to 100 for example rather than just 5. This would be done manually not in the program (like "if cnt=10 then Reset()").

This is to be used in a larger program.
See what you can come up with :)
 

WBahn

Joined Mar 31, 2012
24,693
There are NOT just two conditions, there are three conditions. You said it yourself -- it is possible to not execute either one. Since that conditions matters, it has to be accounted for.

How are you detecting which subroutine was executed and how is that detection accounting for the possibility that neither was executed?

Whichever executed first in a given sequence will eliminate the possibility of the other sequence chain happening

For instance, if B occurs first, then either five successive occurrences of BA will happen or the system will get reset -- it is impossible to see five occurrences of AB before one of those two things happen.

Although this assumes that once you detect the five occurrences of BA that you stop looking. You haven't specified what happens once you detect the desired number of sequences. Do you reset? Do you continue on as if nothing was detected? What?

For instance, if you have

ABABABABABABABABABABABA

What should this system produce?

Imagine modifying your code so that each possible path outputs exactly one symbol into a data stream.

if conditionA then
DoA()
Flag(A)
elsif conditionB then
DoB()
Flag(B)
else
Flag(C)
end if

Now you just need to keep track what the last flag was and a couple of counters.

If (flag == C)
countAB = countBA = 0

if (flag == A) and (lastflag = B)
countAB++
else
countAB = 0

if (flag == B) and (lastflag = A)
countBA++
else
countBA = 0

This should properly account for something like

ABABBABABABABABA

in which the third B in the sequence disrupts the running ABAB sequence and resets that counter but ALSO counts as the first B in the start of a new BA run.
 

Thread Starter

MrAl

Joined Jun 17, 2014
6,488
Hi,

Thanks for the input.

Yes there are three conditions in total, two of which have to be checked for recurrence.

After it detects AB AB AB AB AB or BA BA BA BA BA the code should exit.
Of course if a reset occurs, then it starts to count again.
Yes it is true that if AB then we cant see BA because then we would be seeing BB so that resets.
Also, if we see BA and then AB then we saw AA so it resets.
It only exits after five AB's or five BA's in a row ... anything else resets.

The problem comes up with a block of code that calculates a number where once it calculates through A it goes to B and then back to A then back to B again, naturally. So it never actually settles on one number. Detcing this condition means that instead of exiting at say 0.0000 it jumps back and forth betwen +0.0001 and -0.0001 and if it does that five times in a row we assume it is done even though it actually has two very close solutions (in reality they will actually be within probably 1e-16 of each other).
 

WBahn

Joined Mar 31, 2012
24,693
Hi,

Thanks for the input.

Yes there are three conditions in total, two of which have to be checked for recurrence.

After it detects AB AB AB AB AB or BA BA BA BA BA the code should exit.
Of course if a reset occurs, then it starts to count again.
Yes it is true that if AB then we cant see BA because then we would be seeing BB so that resets.
Also, if we see BA and then AB then we saw AA so it resets.
It only exits after five AB's or five BA's in a row ... anything else resets.

The problem comes up with a block of code that calculates a number where once it calculates through A it goes to B and then back to A then back to B again, naturally. So it never actually settles on one number. Detcing this condition means that instead of exiting at say 0.0000 it jumps back and forth betwen +0.0001 and -0.0001 and if it does that five times in a row we assume it is done even though it actually has two very close solutions (in reality they will actually be within probably 1e-16 of each other).
You keep putting things in pairs, but there is nothing in your description of the system that indicates that there is any natural pairing.

If you have AB AB AB, that you have BOTH AB and AB pairs in the sequence.

If it exits as soon as it sees five alterations (be it AB five times or BA five times), then how about something like

Code:
threshold = 5
priorPass = '.'
count = 0
while (count < threshold)
   evaluate conditionA and conditionB
   if conditionA then
      DoA()
      if priorPass == 'B'
         count++
      else
         count = 0
      priorPass = 'A'
   elsif conditionB then
      DoB()
      if priorPass == 'A'
         count++
      else
         count = 0
      priorPass = 'B'
   else
      priorPass = '.'
      count = 0
   end if
end while
If you are using C, you can tighten this up a fair amount

Code:
threshold = 5
priorPass = '.'
count = 0
while (count < threshold)
   evaluate conditionA and conditionB
   if conditionA then
      DoA()
      count = (priorPass == 'B')? count + 1 : o;
      priorPass = 'A'
   elsif conditionB then
      DoB()
      count = (priorPass == 'A')? count + 1 : o;
      priorPass = 'B'
   else
      priorPass = '.'
      count = 0
   end if
end while
You could also play a game with bitbanging XOR and pingponging a couple of flags, but I don't know that it would save much, if anything, in the end.
 

Thread Starter

MrAl

Joined Jun 17, 2014
6,488
You keep putting things in pairs, but there is nothing in your description of the system that indicates that there is any natural pairing.

If you have AB AB AB, that you have BOTH AB and AB pairs in the sequence.

If it exits as soon as it sees five alterations (be it AB five times or BA five times), then how about something like

Code:
threshold = 5
priorPass = '.'
count = 0
while (count < threshold)
   evaluate conditionA and conditionB
   if conditionA then
      DoA()
      if priorPass == 'B'
         count++
      else
         count = 0
      priorPass = 'A'
   elsif conditionB then
      DoB()
      if priorPass == 'A'
         count++
      else
         count = 0
      priorPass = 'B'
   else
      priorPass = '.'
      count = 0
   end if
end while
If you are using C, you can tighten this up a fair amount

Code:
threshold = 5
priorPass = '.'
count = 0
while (count < threshold)
   evaluate conditionA and conditionB
   if conditionA then
      DoA()
      count = (priorPass == 'B')? count + 1 : o;
      priorPass = 'A'
   elsif conditionB then
      DoB()
      count = (priorPass == 'A')? count + 1 : o;
      priorPass = 'B'
   else
      priorPass = '.'
      count = 0
   end if
end while
You could also play a game with bitbanging XOR and pingponging a couple of flags, but I don't know that it would save much, if anything, in the end.
Hi,

Yeah i like that 'priorPass' concept i'll use that thanks.

I now also realize there is no direct 'Copy Code' function here we have to select the code block to copy just like any other text. Some sites have that which makes it faster/easier to copy the code block.
 
Top