Find/simplify overlapping modulo

Question

I have some code solving today's "Advent of code part 2". https://adventofcode.com/

I have currently many hardcoded modulo conditions, is there any simple way to reduce the number of conditions?

Since in general you can skip checking x % 4 == 0 if you already checked x % 2 == 0. But I have a hard time figuring out how to simplify when there is addition involved. Any suggestions or resources I can look up?

if (delay % 6 == 0)
{
    return false;
}

if ((delay +1) % 2 == 0)
{
    return false;
}

if ((delay +2) % 4 == 0)
{
    return false;
}

if ((delay + 4) % 6 == 0)
{
    return false;
}

if ((delay + 6) % 14 == 0)
{
    return false;
}

if ((delay + 8) % 8 == 0)
{
    return false;
}

if ((delay + 10) % 14 == 0)
{
    return false;
}
if ((delay + 12) % 10 == 0)
{
    return false;
}
if ((delay + 14) % 10 == 0)
{
    return false;
}
if ((delay + 16) % 14 == 0)
{
    return false;
}
if ((delay + 18) % 10 == 0)
{
    return false;
}
if ((delay + 20) % 10 == 0)
{
    return false;
}
if ((delay + 22) % 22 == 0)
{
    return false;
}
if ((delay + 24) % 22 == 0)
{
    return false;
}

if ((delay + 26) % 18 == 0)
{
    return false;
} 

if ((delay + 28) % 14 == 0)
{
    return false;
}

if ((delay + 32) % 14 == 0)
{
    return false;
}

if ((delay + 36) % 16 == 0)
{
    return false;
}

if ((delay + 40) % 14 == 0)
{
    return false;
}

if ((delay + 44) % 32 == 0)
{
    return false;
}

if ((delay + 50) % 18 == 0)
{
    return false;
}

if ((delay + 56) % 26 == 0)
{
    return false;
}
if ((delay + 58) % 26 == 0)
{
    return false;
}
if ((delay + 60) % 26 == 0)
{
    return false;
}

if ((delay + 62) % 22 == 0)
{
    return false;
}

if ((delay + 64) % 26 == 0)
{
    return false;
}

if ((delay + 66) % 26 == 0)
{
    return false;
}

if ((delay + 68) % 26 == 0)
{
    return false;
}

if ((delay + 70) % 26 == 0)
{
    return false;
}

if ((delay + 74) % 26 == 0)
{
    return false;
}
if ((delay + 76) % 26 == 0)
{
    return false;
}
if ((delay + 80) % 26 == 0)
{
    return false;
}

if ((delay + 88) % 26 == 0)
{
    return false;
}

doSomeComputation...

what is the question exactly, check if the number is divisible? — styx, Dec 13 '17 at 14:06
@Sefe I believe what the OP means is that if you test `x % 2 == 0` and return then there's no need to test `x % 4 == 0` after that because anything divisible by 4 is also divisible by 2. — juharr, Dec 13 '17 at 14:22
@juharr But that's what he's already doing. Dropping the second test (which is actually not in the actual code provided) will change the semantics of the code. And that's what he clearly doesn't want. — Sefe, Dec 13 '17 at 14:26
@juharr, exactly, and that was only an example since i don't understand how to do it when there is a '+' involved. Question is are there any redundant checks, and if there are how can it find them? — Viktor Mellgren, Dec 13 '17 at 14:47
Would you mind providing the exact link to the challenge you are coding? — dumetrulo, Dec 13 '17 at 15:35
@dumetrulo: not sure if part 2 is available if you havn't solved part 1, but here goes: https://adventofcode.com/2017/day/13 — Viktor Mellgren, Dec 14 '17 at 08:39

score 0 · Answer 1 · answered Dec 13 '17 at 17:35

I am assuming that delay is always nonnegative. If that is not guaranteed by your inputs, you can replace the modulus call with a version that fixes it, as in this answer. That said, the logic you posted could be replicated with this:

const int lcm = 1441440;
int[] residues = new int[]
{
    1924,
    92644,
    132964,
    223684,
    354724,
    395044,
    616804,
    657124,
    788164,
    878884,
    1009924,
    1050244,
    1181284,
    1272004,
    1312324,
    1403044
};
if (!residues.Contains(delay % lcm)) return false;

Explanation of how to generate it: lcm is the least common multiple of the numbers you are modding by. You can get that by asking WolframAlpha or any number of other ways. The constant residues can be obtained by simply iterating over all the residues mod lcm and checking which ones pass the logic as you have it written already. The following code is what I used to print them out, where the function myPass is just the logic that you provided above.

for (int i = 0; i < 1441440; ++i)
   if (myPass(i))
       Console.WriteLine("i = {0}", i);

Explanation of why it works: If delay is an integer and m is a positive integer and n is a positive integer that is divisible by m, then the value of delay % m is equal to (delay % n) % m. An example: suppose an integer delay has delay % lcm == 1924. Then we have that delay % 6 is equal to (delay % lcm) % 6 which is 1924 % 6 which is 4. Similarly, as long as delay % lcm is a value i in the hard-coded list of residues which we tested to match all of the various conditions in your ifs, then we know that delay matches them, too, because--for whatever m a particular if was testing against--we generated our list in such a way that we already know that i % m matches the condition, and now we have that (delay % m) == (delay % lcm) % m) == i % m.

Note: this approach is only feasible because your set of conditions excludes many residues of only small moduli. If there were, for example, one outlying condition comparing against a large prime, the list of residues could easily become too large to handle.

Find/simplify overlapping modulo

1 Answers1