ISC Practicals and Theory - Word Potential Sort

This program reads a sentence, separates it into words, finds the potential of every word (the sum of the alphabet positions of its letters) and prints the words in ascending order of potential. The words are extracted with charAt(), indexOf(), length() and substring() only, and the sorting is written by hand. Everything is written in the main method.

Definition

The potential of a word is the sum of the positions of its letters in the alphabet: A = 1, B = 2, ... Z = 26. Capital and small letters count the same, so a and A are both 1.

• Ab has potential 1 + 2 = 3, and ba has potential 2 + 1 = 3.
• Zoo has potential 26 + 15 + 15 = 56.
• programming has potential 16 + 18 + 15 + 7 + 18 + 1 + 13 + 13 + 9 + 14 + 7 = 131.

In this program a character that is not a letter (a digit, a comma, a hyphen) is ignored, that is, it adds 0. So Hi, has potential 8 + 9 = 17 and 12 has potential 0.

The sentence must end with ., ? or !, after the spaces at the two ends of the line have been removed with trim(). That terminator is not part of any word. Words are separated by one or more spaces. Any other punctuation inside the sentence stays attached to its word.

If two words have the same potential, they stay in the order in which they were typed. This is called a stable sort.

Algorithm

1. Read the sentence into sent and remove the spaces at its two ends with trim(). If it is empty, or does not end in ., ? or !, print INVALID INPUT and stop.
2. Remove the terminator: s = sent.substring(0, len - 1). Create the arrays w (the words) and p (their potentials), both of size 50, and set n = 0.
3. Cut out the words: with i from 0, skip a space; otherwise e = s.indexOf(' ', i) is the space that ends the word (or the end of the sentence if there is none). If n is already 50, set tooMany = true and stop; otherwise store s.substring(i, e) in w[n], add 1 to n and continue from i = e.
4. If tooMany is true, print the message that 50 words is the maximum. If no word was found (n == 0), print INVALID INPUT.
5. Find the potential of every word: add c - 'A' + 1 for each capital letter c and c - 'a' + 1 for each small letter. Characters that are not letters (digits, commas) are ignored. Store the sum in p.
6. Print every word with its potential.
7. Sort with an insertion sort: take the word kw with potential kp and shift every greater potential one place to the right (p[j] > kp), then place the word in the gap. A word moves left only past a strictly greater potential, so words of equal potential keep their original order.
8. Print every word with its potential again, now in ascending order.

Program

The while loop in main extracts the words, one loop finds the potentials, and the insertion sort arranges the arrays w and p together.

import java.util.Scanner;

/* Program WordPotential reads a sentence, separates it into words without
   split() or StringTokenizer, finds the potential of every word (sum of the
   alphabet positions of its letters) and prints the words in ascending order
   of potential. */
public class WordPotential
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a sentence: ");
        String sent = sc.nextLine().trim();          // trim() removes the spaces at the two ends
        int len = sent.length();
        boolean valid = false;                       // true if the sentence ends with . ? or !
        if (len > 0)                                 // an empty line is invalid
        {
            char last = sent.charAt(len - 1);        // the terminator
            valid = last == '.' || last == '?' || last == '!';
        }
        if (!valid)
        {
            System.out.println("INVALID INPUT");
            return;
        }
        String s = sent.substring(0, len - 1);       // sentence without terminator
        int sl = s.length();
        String w[] = new String[50];                 // the words of the sentence (at most 50)
        int p[] = new int[50];                       // p[i] stores the potential of the word w[i]
        int n = 0;                                   // number of words extracted
        boolean tooMany = false;                     // true if the sentence has more than 50 words
        int i = 0;                                   // index of the character being examined
        while (i < sl)
        {
            if (s.charAt(i) == ' ')                  // extra space: skip it
                i++;
            else
            {
                int e = s.indexOf(' ', i);           // the space that ends this word
                if (e == -1)                         // no space left: word ends with the sentence
                    e = sl;
                if (n == 50)                         // array is full
                {
                    tooMany = true;
                    break;
                }
                w[n] = s.substring(i, e);            // the word, from i up to e - 1
                n++;
                i = e;                               // continue after the word
            }
        }
        if (tooMany)
            System.out.println("Too many words. Maximum 50 words allowed.");
        else if (n == 0)
            System.out.println("INVALID INPUT");
        else
        {
            for (int a = 0; a < n; a++)              // potential of every word; other characters are ignored
            {
                int sum = 0;
                for (int b = 0; b < w[a].length(); b++)
                {
                    char c = w[a].charAt(b);
                    if (c >= 'A' && c <= 'Z')
                        sum = sum + (c - 'A' + 1);   // capital letter
                    else if (c >= 'a' && c <= 'z')
                        sum = sum + (c - 'a' + 1);   // small letter
                }
                p[a] = sum;
            }
            System.out.println("Words with their potential:");
            for (int a = 0; a < n; a++)
                System.out.println(w[a] + " = " + p[a]);
            // insertion sort: a word moves left only past a strictly greater potential,
            // so words of equal potential keep their original order (stable sort)
            for (int a = 1; a < n; a++)
            {
                String kw = w[a];                    // word being inserted
                int kp = p[a];                       // its potential
                int j = a - 1;
                while (j >= 0 && p[j] > kp)          // shift greater potentials one place right
                {
                    w[j + 1] = w[j];
                    p[j + 1] = p[j];
                    j--;
                }
                w[j + 1] = kw;                       // place the word in its position
                p[j + 1] = kp;
            }
            System.out.println("Words in ascending order of potential:");
            for (int a = 0; a < n; a++)
                System.out.println(w[a] + " = " + p[a]);
        }
    }
}

Variable description table

Sample input and output

Enter a sentence: I love Java programming.
Words with their potential:
I = 9
love = 54
Java = 34
programming = 131
Words in ascending order of potential:
I = 9
Java = 34
love = 54
programming = 131

Enter a sentence:   Ab   ba cd  Dc a  Zoo!
Words with their potential:
Ab = 3
ba = 3
cd = 7
Dc = 7
a = 1
Zoo = 56
Words in ascending order of potential:
a = 1
Ab = 3
ba = 3
cd = 7
Dc = 7
Zoo = 56

Enter a sentence: Go?
Words with their potential:
Go = 22
Words in ascending order of potential:
Go = 22

Enter a sentence: Hello
INVALID INPUT

Enter a sentence: Hi, ok 12.
Words with their potential:
Hi, = 17
ok = 26
12 = 0
Words in ascending order of potential:
12 = 0
Hi, = 17
ok = 26

Enter a sentence: Go?   
Words with their potential:
Go = 22
Words in ascending order of potential:
Go = 22

Dry run

Input: Ab ba cd Dc a Zoo! (two spaces at the start). The program trims them, so sent is Ab ba cd Dc a Zoo!. The terminator ! is removed, so s has 21 characters.

Extraction (i is where a word starts, e where it ends):

Potentials: Ab = 3, ba = 3, cd = 3 + 4 = 7, Dc = 4 + 3 = 7, a = 1, Zoo = 56. So p = 3, 3, 7, 7, 1, 56.

Insertion sort (p after each value of i):

The final order is a = 1, Ab = 3, ba = 3, cd = 7, Dc = 7, Zoo = 56. This is the same as the real run of the second sample above, and the equal potentials Ab, ba and cd, Dc kept their typed order.

Variations

1. Sort by length "Write a program to read a sentence and print its words in ascending order of length."
2. Alphabetical order "Write a program to arrange the words of a sentence in alphabetical order."
3. Highest potential "Write a program to print the word of a sentence that has the highest potential."
4. Palindrome words "Write a program to count the words of a sentence that are palindromes."