Making a Java -code more efficient, USACO

Question

I am trying to complete the first exercise of USACO.

How can you make the following code more efficient?

It seems that the current problem in the program is that its execution takes too much time.

Thank you for suggesting the first four sets of improvements! I made a few edits based on your comments.

5th edition of the code

   /*
    * Problem: USACO Your Ride is Here
    * 
    * To print GO if this if -loop is true "if ( ( index[0] % 47 ) == ( index[1] % 47 ) )"
    * else STAY
    *
    * It calculates the product of letters' indexes in the alphabets such that
    * A -> 1, B -> 2, ... , Z -> 26
    *
    */

class PlanetUfo {
// initial data
String[] groups = {"COMETQ", "ABSTAR"};
String[] comets = {"HVNGAT", "USACO"};

// to count the index
private void countIndex ( String group, String comet ) {
    // to have two PlanetUfo.words in the array
    String[] name = { group, comet };
    int[] index = new int[100];

    // to go though the PlanetUfo.words one by one in the block of the array
    for ( int k = 0; k < name.length; k++ ) {
        System.out.println("K:n arvo on " + k);
        // to save each letter to an array
        char[] words = name[k].toCharArray();

        int sum = 1;
        // to loop through each character in the word
        for ( int i = 0; i < words.length; i++) {
            System.out.println("Inside the loop");
            // to loop through the alphabets
            char[] alphabet =
            {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
            for ( int j = 0; j < alphabet.length ; j++ ) {
                if ( alphabet[j] == words[i] ) {
                    sum = sum * (j + 1);
                    index[k] = sum;
                    System.out.println("Found " + alphabet[j] + " in " + name[k] + " (index = " + (j+1) + ")");
                    break;
                }
            }
        }
    }

    if ( ( index[0] % 47 ) == ( index[1] % 47 ) )
        System.out.println("GO");
    else
        System.out.println("STAY");
}




public static void main (String[] args) {
    PlanetUfo planetufo = new PlanetUfo();

    // to count the index for name1 and name2
    for ( int i = 0; i < planetufo.groups.length; i++ ) {
        planetufo.countIndex( planetufo.groups[i], planetufo.comets[i] );
    }

    System.out.close();
    System.exit(0);
}
}

USACO gives me the following error although the program works in my computer

Run 1: Execution error: Your program exited with exit status `1'.

      ------ Data for Run 1 ------
    COMETQ 
    HVNGAT 
      ----------------------------

      Your program printed data to stderr.  Here is the data:
      -------------------
      Exception_in_thread_"main"_java.lang.NoClassDefFoundError:_ride
      -------------------

Answer 1

You are referencing planetUfo.letters, but I do not see 'letters' declared anywhere in the class or method.

Answer 2

The variables have to be in scope at the place where you refer to them. In your case, in line 35 you are referring to a variable called letters, but that's a local variable in the main() method. It's not visible outside the main() method.

Make letters a member variable of the class instead of a local variable in main().

The variable index which you are referring to in line 42 is not declared anywhere, so the compiler doesn't know what you mean by index.

Answer 3

A few notes:

• Your letters variable is local to your main method, so it can't be accessed as planetUfo.letters.

• Your index variable doesn't seem to have been declared anywhere.

• planetUfo is a bad name for a class. By convention, classes in Java should start with a capital letter.

Edit: In response to your updated code, here are a couple of additional notes:

• You have the following code:

  int[] index = new index[100];
  

  What you really want is this:

  int[] index = new int[100];
  

  Since the type of the new object you are trying to declare is int[], not index[] (there is no type called index in your program, so that fails).

• If you declare your countIndex method as static, it can only access class variables that have also been declared as static. So either declare the letters variable as static, or don't declare the countIndex method as static.

Answer 4

> planetUfo.java:31: cannot find symbol 
> symbol  : variable letters location:
> class planetUfo
>                     while ( planetUfo.letters[j] != words[i] ) { 
>                                      ^ planetUfo.java:35: cannot find symbol

You've declared the variable letters in the main method.

The scope of that variable is in that method. It is invisible inside the "countIndex" method of planetUfo.

To make it visible you can declare it as a "class" variable using the "static" access modifier.

public class PlanetUfo { 
   static char letters[] = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};

Or declare it as an "instance" variable:

public class PlanetUfo { 
   char letters[] = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};

The difference is, there will be only one copy of "letters" is you use the static modifier ( pretty much like a global var in C ) or there will be one copy of "letters" if you declare it as instance variable.

In either case the invocation will be legal you just have to type is as:

while ( letters[j] != words[i] ) {

As for:

> symbol  : variable index location:
> class planetUfo
>                         index[k] = sum;
>                         ^ planetUfo.java:42: cannot find symbol

You are trying to use the array named index that you didn't declare anywhere you may try one of:

words
letters
or 
name

Who are valid array declarations.

Perhaps you have to go a step back and think what you want in first place, probably there will be better/easier ways. What is the expected output in your case?

Answer 5

Your specific problem is because you're trying to access a non-static class property (letters) from within the static countIndex method.

Either make letters static, or preferably make countIndex non-static and call it from main like this:

PlanetUfo planetUfo = new PlanetUfo();
for ( int i = 0; i < groups.length; i++ ) {
    planetUfo.countIndex( groups[i], comets[i] );
}

Answer 6

If you declare a method as static, it can only access elements of the class that are also declared as static. So you need to declare letters[], groups[] and comets[] as static:

static char letters[] = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};

// initial data
static String[] groups = {"COMETQ", "ABSTAR"};
static String[] comets = {"HVNGAT", "USACO"};

Anyway, your method seems to do a relatively simple thing in a convoluted way. Care to explain what is your method supposed to do?

Answer 7

as everyone wrote, you can't access Letters because it is a local variable in main(). Beyond the other suggestions, you can always do this instead of declaring an array of Letters:

int len = 'Z'-'A'+1
for ( int j = 0; j < len ; j++ ) {
      while ( 'A'+j != words[i] ) {
              ...
      }
}

Answer 8

It looks like, as of your third revision, your index[] array is still out of scope. You declare it inside a nested for() loop, but then you try to use it after the loops are closed. With your code right now, index[] will be inaccessible after the end of the "middle" for() loop. However, you are trying to access it after the end of the outer loop, which is causing the "cannot find symbol" errors.

The easiest solution would be to declare it outside of the for() loops, such as directly below this line:

String[] name = { group, comet };

If you declare it there, then index[] will be in scope for the duration of the method's execution.

EDIT: In response to your fifth revision, concerning the code's efficiency, Here are some tips:

I went ahead and went through all the code to try to figure out what exactly it did. It appears as if you are passing in two Strings to countIndex, taking the numeric value of each character in each String (where A = 1 and Z = 26), muliplying all the numeric values together for each String, and finally modding both Strings by 47 and checking to see if the results are equal. Is that correct?

If that's the case, then try these suggestions:

First, you are creating the index[] array with a size of 100. However, I'm not sure of what the purpose of this is. When you go through all the loops, since name has a hard-coded length of 2, that means k will never be bigger than 1. Thus you are only utilizing the zeroth and first indices in index[], and never more. Thus, you should safely be able to change index[]'s declaration to be like this:

int[] index = new int[2];
    // or
int[] index = new int[name.length];

Second, you probably don't need the sum variable, since index[k] will always be the same value. You can safely treat index[k] as you would sum, initializing index[k] to 1 and incrementing the value during the loop like so:

index[k] = 1;

...

if ( alphabet[j] == words[i] ) {
    index[k] *= (j + 1);
    System.out.println("Found " + alphabet[j] + " in " + name[k] + " (index = " + (j+1) + ")");
    break;
}

Finally (and this will be the part that makes it speed up a lot), the inner two loops are inefficient because you have to traverse the alphabet array for every character. You can use some properties of characters to make the inner two loops condensed to one loop:

for (int k = 0; k < name.length; k++) {
    index[k] = 1;
    for (int i = 0; i < name[k].length(); i++) {
        index[k] *= (Character.getNumericValue(name[k].charAt(i)) - 9);
    }
}
// much prettier!

This obviously makes some assumptions about what is allowable input (since you haven't told us yet what the purpose of this program is), but I hope this helps.

Answer 9

In the 4th edition of the code, you asked about an infinite loop. I took the liberty of stepping back and trying to figure out what you were actually trying to do. I would do it differently if starting from scratch, but here is a working version of with minimal changes to what you've got already. Enjoy!

class PlanetUfo {
    // initial data
    String[] groups = {"COMETQ", "ABSTAR"};
    String[] comets = {"HVNGAT", "USACO"};

    // to count the index
    private void countIndex ( String group, String comet ) {
        // to have two PlanetUfo.words in the array
        String[] name = { group, comet };
        int[] index = new int[100];

        // to go though the PlanetUfo.words one by one in the block of the array
        for ( int k = 0; k < name.length; k++ ) {
            System.out.println("K:n arvo on " + k);
            // to save each letter to an array
            char[] words = name[k].toCharArray();

            int sum = 1;
            // to loop through each character in the word
            for ( int i = 0; i < words.length; i++) {
                System.out.println("Inside the loop");
                // to loop through the alphabets
                char[] alphabet =
                {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
                for ( int j = 0; j < alphabet.length ; j++ ) {
                    if ( alphabet[j] == words[i] ) {
                        sum = sum * (j + 1);
                        index[k] = sum;
                        System.out.println("Found " + alphabet[j] + " in " + name[k] + " (index = " + (j+1) + ")");
                        break;
                    }
                }
            }
        }

        if ( ( index[0] % 47 ) == ( index[1] % 47 ) )
            System.out.println("GO");
        else
            System.out.println("STAY");
    }




    public static void main (String[] args) {
        PlanetUfo planetufo = new PlanetUfo();

        // to count the index for name1 and name2
        for ( int i = 0; i < planetufo.groups.length; i++ ) {
            planetufo.countIndex( planetufo.groups[i], planetufo.comets[i] );
        }

        System.out.close();
        System.exit(0);
    }
}