Classy

Via the ICPC Pacific Northwest 2015 Division Finals.

Classy Problem

The problem statement goes thus:

"In his memoir So, Anyway. . . , comedian John Cleese writes of the class difference between his father (who was “middle-middle-middle-lower-middle class”) and his mother (who was “upper-upper- lower-middle class”). These fine distinctions between classes tend to confuse American readers, so you are to write a program to sort a group of people by their classes to show the true distinctions."

You receive a list of names, one name per line, in an input file, with various combinations of the words upper, middle, and lower attached to each.

Upper class is the highest, and lower class is the lowest.

But there can be distinctions within a class, so upper-upper is a higher class than middle-upper, which is higher than lower-upper.

However, all of the upper classes (upper-upper, middle-upper, and lower-upper) are higher than any of the middle classes.

Within a class like middle-upper, there can be further distinctions as well, leading to classes like lower-middle-upper-middle-upper.

When comparing classes, once you’ve reached the lowest level of detail, you should assume that all further classes are the equivalent to the middle level of the previous level of detail.

So upper class and middle-upper class are equivalent, as are middle- middle-lower-middle and lower-middle.

Classy Specification

Input

The first line of input contains n (1 ≤ n ≤ 1,000), the number of names to follow. Each of the following n lines contains the name of a person (a sequence of 1 or more lowercase letters ‘z’–‘z’), a colon, a space, and then the class of the person. The class of the person will include one or more modifiers and then the word class. The colon, modifiers, and the word class will be separated from each other by single spaces. All modifiers are one of upper, middle, or lower. It is guaranteed that the input is well-formed. Additionally, no two people have the same name. Input lines are no longer than 256 characters.

Output

Print the n names, each on a single line, from highest to lowest class. If two people have equivalent classes, they should be listed in alphabetical order by name.

Java Comparators

See Java/Comparators. This was implemented using a custom comparator for a Person class, which wrapped a class consisting of a list of Strings (the titles) and labels (the Person's name) provided in the input file. These had a custom compareTo function defined to follow the specifications of the problem.

Code

import java.util.*; 
import java.io.*;

public class Classy { 

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

		// Read the input file: new Person for each line
		int n = Integer.parseInt(s.nextLine());
		ArrayList<Person> people = new ArrayList<Person>();
		while(s.hasNextLine()) {
			String line = s.nextLine();
			String[] deets = line.split(" ");
			Person p = new Person(deets);
			people.add(p);
		}

		Collections.sort(people);
		for(Person p : people) { 
			System.out.println(p);
		}
	}
}

class Person implements Comparable<Person> {
	private String name;
	private ArrayList<String> titles;

	/** Person constructor - pass in a String array with the deets. */
	public Person(String[] deets) { 
		name = deets[0];
		// Remove : from name
		name = name.substring(0,name.length()-1);

		// initialize list of classes 
		titles = new ArrayList<String>();
		for(int i=1; i<deets.length-1; i++) { 
			titles.add(deets[i]);
		}
		// Last word will be "class", so ignore.
	}
	/** Compare a person to another person. 
	 * Just compare their titles in alphabetical order. */
	public int compareTo(Person p2) { 

		Stack<String> st1 = new Stack<String>();
		Stack<String> st2 = new Stack<String>();

		// Add names to stack, left to right
		for(String title : this.getTitles()) {
			st1.push(title);
		}
		for(String title : p2.getTitles()) { 
			st2.push(title);
		}

		// Compare each name, from right-to-left.
		// If stack 1 not empty, pop item, otherwise "middle"
		// If stack 2 not empty, pop item, otherwise "middle"

		int max = Math.max(this.getTitles().size(), p2.getTitles().size());
		for(int i=0; i<max; i++) {

			// From the right
			String s1, s2;

			if(!st1.isEmpty()) {
				s1 = st1.pop();
			} else {
				s1 = "middle";
			}

			if(!st2.isEmpty()) {
				s2 = st2.pop();
			} else {
				s2 = "middle";
			}

			// Return the first non-zero value
			int res = s2.compareTo(s1);
			if( res != 0 ) {
				return res;
			}
		}

		// if we reach here, there was a tie.
		// use names as tie breaker.
		return this.getName().compareTo(p2.getName());
	}
	public String getName() { return name; }
	public ArrayList<String> getTitles() { return titles; }
	public String toString() { return getName(); } //+ ": "+getTitles().toString(); }
}