What is wrong with my checksum algorithm?

Question

I am doing some practice problems for a competition and I have been working on this algorithm like all day. If you want to read the whole problem here it is, but I will give you a short explanation because it is kind of a long problem.

Problem:

You have to verify ID numbers by plugging the ID number into a checksum. The ID needs to be converted to base-10 before you can plug it into the algorithm. The ID number starts out as letters:

Z = 0, Y = 1, X = 2, W = 3, V = 4

I am not having trouble with the conversion from these letters to base-10, my conversion code is good so I'll show you the next part of the problem:

Part 2:

Once you have your base-10 ID number you need to plug it into the following algorithm:

Note: each ID number MUST be 8 digits long, 0's will precede a number that is not at least 8 digits.

checksum = F(0, d0) X F(1, d1) X F(2, d2) ...

So to simplify:

checksum = F(n, dn) X F(n+1, dn) ...
where n is the index of the digit

What is most important here, is that X is not the operation * (multiply). X is it's own operation defined later.

Note: The most significant digit seems to be d7 but I'm not sure, the problem is not very clear about it.

---

Here are the definitions for f(n1, n2), g(n) and the operator X:

f(n1, n2) =

g(n) =

operator X:

I assumed mod is the same thing as % in my code, I was not sure if there was another mod operation I am not familiar with.

My Structure

This is how I decided I wanted to solve the problem:

1. Convert the base-10 number into int[8]
2. Put each digit of the int[8] through f(n, dn)
3. Use the X operator to then combine them all together.

My Code

Here are my algorithm functions. I can comment them if they are confusing somewhere, but they really follow the algorithm listed above exactly.

/*
 * This will return the checksum of the id.
 * Formula: F(0, d0) X F(1, d1) ...
 * 
 * F(n, dn) where n is the current index.
 * X != * (multiply)!! X is a defined operator
 */
public static int getChecksum(int[] id)
{
    int result = 0;

    for(int x = 0;x < id.length;x++)
    {
        if(x == 0)
            result = fOfxd(x, id[x]);
        else{
            result = opX(result, fOfxd(x, id[x]));
        }
    }

    return result;
}

public static int gOfx(int x)
{
    return GOFX[x];
}

public static int fOfxd(int x, int d)
{
    switch(x)
    {
        case 0:
            return d;
        case 1:
            return gOfx(d);
        default:
            return fOfxd(x - 1, gOfx(d));
    }
}

public static int opX(int num1, int num2)
{
    if(num1 < 5 && num2 < 5)
        return (num1 + num2) % 5;
    if(num1 < 5 && num2 >= 5)
        return (num1 + (num2 - 5)) % 5 + 5;
    if(num1 >= 5 && num2 < 5)
        return ((num1 - 5) - num2) % 5 + 5;
    return (num1 - num2) % 5;
}

public static final int[] GOFX = {1, 5, 7, 6, 2, 8, 3, 0, 9, 4};

Now, here is my main(String args[]) code:

Note: You can assume the functions parseBase10, and toArray are functioning properly. I have checked them with the input / output examples in the problem.

public static void main(String args[])
{
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    while(true)
    {
        int ids = 0; // how many ids are we checking?
        try
        {
            ids = Integer.parseInt(reader.readLine()); // get user input

            String[] list = new String[ids]; // will hold all of the ids

            for(int x = 0;x < list.length;x++)
                list[x] = reader.readLine(); // reads all of the ids we will be checking

            for(int x = 0;x < list.length;x++) // lets check the ids individually now
            {
                String stringID = list[x]; // the string representation of the id
                int base10 = parseBase10(stringID);
                int[] id = toArray(base10);
                int checksum = getChecksum(id);

                System.out.println(stringID);
                System.out.println(base10);
                System.out.println(Arrays.toString(id));
                System.out.println(checksum);

            }
        }catch(Exception e){e.printStackTrace();}
        break;
    }
}

Want to compile it yourself?

Here is my full (unedited) code:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main 
{
    public static void main(String args[])
    {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        while(true)
        {
            int ids = 0; // how many ids are we checking?
            try
            {
                ids = Integer.parseInt(reader.readLine()); // get user input

                String[] list = new String[ids]; // will hold all of the ids

                for(int x = 0;x < list.length;x++)
                    list[x] = reader.readLine(); // reads all of the ids we will be checking

                for(int x = 0;x < list.length;x++) // lets check the ids individually now
                {
                    String stringID = list[x]; // the string representation of the id
                    int base10 = parseBase10(stringID);
                    int[] id = toArray(base10);
                    int checksum = getChecksum(id);

                    System.out.println(stringID);
                    System.out.println(base10);
                    System.out.println(Arrays.toString(id));
                    System.out.println(checksum);

                }
            }catch(Exception e){e.printStackTrace();}
            break;
        }
    }

    /*
     * This will return the checksum of the id.
     * Formula: F(0, d0) X F(1, d1) ...
     * 
     * F(n, dn) where n is the current index.
     * X != * (multiply)!! X is a defined operator
     */
    public static int getChecksum(int[] id)
    {
        int result = 0;

        for(int x = 0;x < id.length;x++)
        {
            if(x == 0)
                result = fOfxd(x, id[x]);
            else{
                result = opX(result, fOfxd(x, id[x]));
            }
        }

        return result;
    }

    public static int gOfx(int x)
    {
        return GOFX[x];
    }

    public static int fOfxd(int x, int d)
    {
        switch(x)
        {
            case 0:
                return d;
            case 1:
                return gOfx(d);
            default:
                return fOfxd(x - 1, gOfx(d));
        }
    }

    public static int opX(int num1, int num2)
    {
        if(num1 < 5 && num2 < 5)
            return (num1 + num2) % 5;
        if(num1 < 5 && num2 >= 5)
            return (num1 + (num2 - 5)) % 5 + 5;
        if(num1 >= 5 && num2 < 5)
            return ((num1 - 5) - num2) % 5 + 5;
        return (num1 - num2) % 5;
    }

    /*
     * This will convert a number to an array equivalent of that number
     * The result will be 8 digites long with leading 0's if possible.
     * 
     * EX:
     * 12345 = {0, 0, 1, 2, 3, 4, 5, 6}
     */
    public static int[] toArray(int value)
    {
        int result[] = new int[8];

        for(int x = result.length - 1;x >= 0;x--)
        {
            result[x] = value % 10;
            value /= 10;
        }

        return result;
    }

    /*
     * converts a String sequence and converts it to a base 10 equivalent.
     * Z = 0, Y = 1, X = 2, W = 3, V = 4
     * 
     * EX:
     * YY = 11(base-5) = 6(base-10)
     */
    public static int parseBase10(String string) throws Exception
    {
        int multiplier = 1;
        int result = 0; // in base 10

        for(int x = string.length() - 1;x >= 0;x--)
        {
            char letter = string.charAt(x); // the letter we are parsing
            int value = -1; // initial value, set to -1 to check for parsing error

            for(int y = 0;y < VALUES.length;y++)
                if(letter == VALUES[y])
                    value = y; // letter found in VALUES[]

            if(value == -1)
                throw new Exception("Could not parse: " + letter); // the specified letter was not found

            result += (multiplier * value);
            /* ^^ this moves the value to the correct digit place by using a multiplier:
             * EX:
             * 
             * current result: 45 (base-10)
             * new value to parse: 2 (base-5)
             * 45(base-10) + (2(base-5) * 25(base-10)) = 245 <-- correct output
             */

            multiplier *= 5; // sets up multiplier for next value
        }

        return result;
    }

    public static final char[] VALUES = {'Z', 'Y', 'X', 'W', 'V'};
    public static final int[] GOFX = {1, 5, 7, 6, 2, 8, 3, 0, 9, 4};
}

---

Here is the input I am giving my problem:

6
WYYXWVZXX
YWYWYYXWVZYY
YWYWYYXWVZYX
YYZWYYXWVZYX
YXXWYYXWVZXW
XYXWYYXWXYY

Here is what I get:

WYYXWVZXX
1274262
[0, 1, 2, 7, 4, 2, 6, 2]
2  *0*
YWYWYYXWVZYY
81352381
[8, 1, 3, 5, 2, 3, 8, 1]
0
YWYWYYXWVZYX
81352382
[8, 1, 3, 5, 2, 3, 8, 2]
4
YYZWYYXWVZYX
59868007
[5, 9, 8, 6, 8, 0, 0, 7]
0
YXXWYYXWVZXW
73539888
[7, 3, 5, 3, 9, 8, 8, 8]
5  *0*
XYXWYYXWXYY
22520431
[2, 2, 5, 2, 0, 4, 3, 1]
3  *0*

Where you see the *0*'s is where I am supposed to be getting 0, but I am getting a different value. Where is my checksum algorithm messing up?

Reading all of that feel free to ask for clarification on any part of my code.

Answer 1

BUG 1

The error is subtle. First of all, the digit description in the problem is: d7 d6 ... d1 d0 that means, d0 is the unit value of the decimal number.

Then, they say that F is left associative, and describe the process as :

F(0,d0) x F(1,d1) x F(2,d2) x ... x F(6,d6) x F(7,d7)

that means, you must first apply F to the operator to d0. BUT when you create the int array, the element at the 0 index is d7 , and since in this case the order matters, you get a wrong result.

To solve, you just have to reverse your int array rapresentation of the decimal value.

BUG 2

The second mistake is in the operation modulo 5. As you can read in the note of the problem, they say :

Note that -4 mod 5 = 1.

So copy-pasting hte operator x is a mistake. Change it with:

public static int opX(int num1, int num2)
{
    if(num1 < 5 && num2 < 5)
        return (num1 + num2) % 5;
    if(num1 < 5 && num2 >= 5)
        return (num1 + (num2 - 5)+5) % 5 + 5;
    if(num1 >= 5 && num2 < 5)
        return ((num1 - 5) - num2+20) % 5 + 5;
    return (num1 - num2 +10) % 5;
}

and you'll get the expected result.

Here is the result with both bugs fixed :

1274262
[2, 6, 2, 4, 7, 2, 1, 0]
0
YWYWYYXWVZYY
81352381
[1, 8, 3, 2, 5, 3, 1, 8]
0
YWYWYYXWVZYX
81352382
[2, 8, 3, 2, 5, 3, 1, 8]
1
YYZWYYXWVZYX
59868007
[7, 0, 0, 8, 6, 8, 9, 5]
0
YXXWYYXWVZXW
73539888
[8, 8, 8, 9, 3, 5, 3, 7]
0
XYXWYYXWXYY
22520431
[1, 3, 4, 0, 2, 5, 2, 2]
0

EDIT

For a more general solution of the BUG 2, check Martijn Courteaux answer.

Answer 2

Your mod logic is broken. The website says:

Note that -4 % 5 = 1.

In Java, this is not true: (-4) % 5 == -4. So implement your own mod(int a, int b) method:

public static int mod(int a, int b)
{
    while (a < 0) a += b;
    while (a >= b) a -= b;
    return a;
}

Or a more performant implementation as suggested by @durron597:

public static int mod(int a, int b)
{
    a %= b;
    return a < 0 ? a + b : a;
}

This is really important since you will have negative values here
(Eg: assume num1 = 5 and num2 = 4):

if(num1 >= 5 && num2 < 5)
    return ((num1 - 5) - num2) % 5 + 5;