Evaluate whether string is in alphabetical order or reverse alphabetical order

Question

Purpose

This problem comes from this question on the dailyprogrammer subreddit.

Basically, the task is to write an implementation that identifies if the characters in a String are in

• Alphabetical order (A to Z)
• Reverse Alphabetical order (Z to A)
• Neither Alphabetical nor Reverse Alphabetical order ("abba")
• Both Alphabetical and Reverse Alphabetical order (only one distinct character in String)

Implementation

public class StringCharactersInAlphabeticalOrderEvaluatorImpl implements StringCharactersInAlphabeticalOrderEvaluator {
  private final List<Character> charactersFromAtoZ;

  public StringCharactersInAlphabeticalOrderEvaluatorImpl(final List<Character> charactersFromAtoZ) {
    this.charactersFromAtoZ = charactersFromAtoZ;
  }

  @Override public AlphabeticalOrderState evaluateAlphabeticalOrderOfCharacters(final String candidate) {
    final char[] stringChars = candidate.toUpperCase().toCharArray();
    int index = 0;
    boolean fromAtoZ = true;
    boolean fromZtoA = true;
    while (index < stringChars.length - 1) {
      if (charactersFromAtoZ.indexOf(stringChars[index]) > charactersFromAtoZ.indexOf(stringChars[index + 1])) {
        fromAtoZ = false;
      }

      if (charactersFromAtoZ.indexOf(stringChars[index]) < charactersFromAtoZ.indexOf(stringChars[index + 1])) {
        fromZtoA = false;
      }

      index++;
    }

    if (!fromAtoZ && !fromZtoA) {
      return AlphabeticalOrderState.IN_NEITHER_ALPHABETICAL_NOR_REVERSE_ALPHABETICAL_ORDER;
    }

    if (fromAtoZ && fromZtoA) {
      return AlphabeticalOrderState.IN_BOTH_ALPHABETICAL_AND_REVERSE_ALPHABETICAL_ORDER;
    }

    if (fromAtoZ) {
      return AlphabeticalOrderState.IN_ALPHABETICAL_ORDER;
    }

    if (fromZtoA) {
      return AlphabeticalOrderState.IN_REVERSE_ALPHABETICAL_ORDER;
    }

    throw new RuntimeException("unexpected character string");

  }
}

Feedback

I'd like feedback on my implementation, specifically

• Am I missing any corner cases? Am I over-specifying my cases (for example, the BothAlphabeticalAndReverseAlphabetical case)?
• Is this the most efficient way of implementing a solution? Is there a better implementation technique (particularly when it comes to my if statements, which I'm not in love with).

Answer 1

I think that your solution is overengineered. I don't think that there is much reason to define a StringCharactersInAlphabeticalOrderEvaluator interface, containing one evaluateAlphabeticalOrderOfCharacters(String) method. Do you plan to write an implementation other than StringCharactersInAlphabeticalOrderEvaluatorImpl? Is there even any reason to have an object at all?

To be fair, different languages have different collation rules. For example, in Spanish, the letter ñ follows n, and, until the rules were simplified in 1994, the digraph ch was treated as a letter between c and d, and ll was treated as a letter between l and m. However, if we were going to get fancy and generalize, I would recommend doing it "properly", using a Collator.

This exercise, though, is marked as "easy". It looks like "ASCIIbetical" order is good enough: we don't have to consider case folding, digraphs, diacritics, Unicode surrogate pairs, or locale-specific rules. For that, we can just compare the code points using char subtraction or Character.compare(char, char).

You have implemented evaluateAlphabeticalOrderOfCharacters() as a monolithic function, which violates the Single Responsibility principle. There isn't much advantage to having it do two kinds of ordering checks and classify the result into four categories. You would be better off exposing two independent checks. In fact, by splitting it up, you might save a few loop iterations, since each loop could exit early as soon as it detected an out-of-sequence character.

Suggested solution

The principal functions in this class are isAlphabeticalOrder() and isReverseAlphabeticalOrder(). They both delegate to a isMonotonic() helper function to avoid code duplication. There is a classifyOrder() helper to produce the result strings to be printed in main().

I've used CharSequence rather than String, as a hint that the string is to be interpreted more as a sequence of characters. I think that a List<Character> would be overkill.

import java.util.Scanner;

public class AlphabeticalOrderChecker {
    private static int ASCENDING = +1,
                       DESCENDING = -1;

    private static boolean isMonotonic(CharSequence cs, int trend) {
        for (int i = 1; i < cs.length(); i++) {
            if (trend * Character.compare(cs.charAt(i - 1), cs.charAt(i)) > 0) {
                return false;
            }
        }
        return true;
    }

    public static boolean isAlphabeticalOrder(CharSequence cs) {
        return isMonotonic(cs, ASCENDING);
    }

    public static boolean isReverseAlphabeticalOrder(CharSequence cs) {
        return isMonotonic(cs, DESCENDING);
    }

    private static String classifyOrder(CharSequence cs) {
        boolean asc = isAlphabeticalOrder(cs);
        boolean desc = isReverseAlphabeticalOrder(cs);
        return (asc && desc) ? "IN ORDER AND REVERSE ORDER" :
               (asc)         ? "IN ORDER" :
                      (desc) ? "REVERSE ORDER" :
                               "NOT IN ORDER";
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String s = sc.nextLine();
            System.out.printf("%s %s\n", s, classifyOrder(s));
        }
    }
}

Answer 2

A few things I noted:

1. Descriptive variable names are good, but code that fits in a monitor's width is even better, and I think you are erring on the too long side. E.g. AlphabeticalOrderEvaluator is probably descriptive enough, and for a method of such a class, evaluateOrder is probably also good enough.
2. char variables can be compared directly, no need to go through the cumbersome process of finding their index in a list.
3. I think your code is not doing what you want it to, as you are forgetting all history and characterizing the string by whatever order the last two characters follow.

With these in mind, and leaving your code structure unchanged, your main function's main loop could be rewritten as:

@override
public AlphabeticalOrderState evaluateOrder(String candidate) {
    final char[] stringChars = candidate.toUpperCase().toCharArray();
    int index = 0;
    boolean fromAtoZ = true;
    boolean fromZtoA = true;
    while (index < stringChars.length - 1) {
        fromAtoZ &= stringChars[index] <= stringChars[index+1];
        fromZtoA &= stringChars[index] >= stringChars[index+1];
    }
    ...
}

You can optimize this quite a bit, e.g. by breaking early out of the loop if both fromAtoZ and fromZtoA are false. And you can make your code more explicit by using explicit if statements, rather than &= operators, which may feel a little too terse.