The Beauty and the Strings

Question

This originally appeared in Facebook's hacker cup 2013. Solving it was fun, though I find myself looping through similar data quite often.

Challenge:

Print the maximum beauty of strings.

Specifications:

The beauty of a string is the sum of the beauty of the letters within.
The beauty of each letter is an integer between 1 and 26, inclusive, and no two letters have the same beauty.
Lettercase is irrelevant.
Your program should accept as its first argument a path to a filename.
Each line in this file has a sentence.
Print out the maximum beauty of each sentence.

This means calculate the maximum possible beauty a string can have. e.g. In test case, "AbBCcC" assign 26 to C, as it occurs the most in the string, followed by 25 to B, and 24 to A. For a maximum beauty of 152.

Solution:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class BeautifulStrings {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner input = new Scanner(new File(args[0]));

        while (input.hasNextLine()) {
            printMaximumBeauty(input.nextLine());
        }
    }

    private static void printMaximumBeauty(String line) {
        System.out.println(
            computeMaximumBeauty(line
                .replaceAll("[^a-zA-Z]", "")
                .toLowerCase()
                .toCharArray()
            )
        );
    }

    private static int computeMaximumBeauty(char[] line) {
        int beauty = 0;
        int beautyVal = 26;
        int count = 0;
        Set<Character> uniqueCharacters = new HashSet<>();
        List<Integer> appearanceCounts = new ArrayList<>();

        for (char c : line) {
            uniqueCharacters.add(c);
        }

        for (char u : uniqueCharacters) {
            for (char c : line) {
                if (u == c) {
                    count++;
                }
            }

            appearanceCounts.add(count);
            count = 0;
        }

        Collections.sort(appearanceCounts, Collections.reverseOrder());

        for (int i : appearanceCounts) {
            beauty += i * beautyVal--;
        }

        return beauty;
    }
}

In an attempt to reduce the amount of loops and work done I thought of a different implementation for computeMaximumBeauty. I think maybe there's a way to do it all in one stream, but I'm not yet well versed with Java 8 (unfortunately all the Java challenges from the challenge site, CodeEval, require Java 7). This isn't a comparative review, so feel free to pick the better one (or both) and pick at its weaknesses or suggest complete alternatives if this approach misguided.

private static int computeMaximumBeauty(char[] chars) {
        int beauty = 0;
        int beautyVal = 26;
        Map<Character, Integer> beautyMap = new HashMap<>();
        Map<Character, Integer> valueSorted;

        for (char c : chars) {
            beautyMap.put(
                c, beautyMap.containsKey(c) ? beautyMap.get(c) + 1 : 1
            );
        }

        valueSorted =  beautyMap.entrySet().stream()
            .sorted(comparing(Entry::getValue))
            .collect(toMap(
                Entry::getKey,
                Entry::getValue,
                (e1, e2) -> e1, LinkedHashMap::new
            )
        );

        beautyVal -= valueSorted.size() - 1; 

        for (Map.Entry<Character, Integer> e : valueSorted.entrySet()) {
            beauty += e.getValue() * beautyVal++;
        }

        return beauty;
    }

Sample Input:

ABbCcc  
This is from Facebook Hacker Cup 2013.  
Ignore punctuation, please :)  
Sometimes, test cases are hard to make up.  
CodeReview is love. CodeReview is life.

Sample Output:

152
551
491
729
724

Answer 1

Unit testing

Hi again @Legato, I'll probably bug you with unit testing until you start writing them ;-)

@Test
public void test_ABbCcc() {
    assertEquals(152, computeMaxBeauty("ABbCcc"));
}

@Test
public void test_This_is_from_Facebook_Hacker_Cup_2013_() {
    assertEquals(551, computeMaxBeauty("This is from Facebook Hacker Cup 2013."));
}

@Test
public void test_Ignore_punctuation__please___() {
    assertEquals(491, computeMaxBeauty("Ignore punctuation, please :)"));
}

@Test
public void test_Sometimes_test_cases_are_hard_to_make_up_() {
    assertEquals(729, computeMaxBeauty("Sometimes, test cases are hard to make up."));
}

@Test
public void test_CodeReview_is_love__CodeReview_is_life_() {
    assertEquals(724, computeMaxBeauty("CodeReview is love. CodeReview is life."));
}

The first implementation

It's good that the logic is decomposed to 2 methods (as opposed to not decomposed at all).

The printMaximumBeauty method converts the input string to char[]. I think it would be better to pass the string to computeMaximumBeauty and let it do whatever it wants with it. For the record, there's a trade-off when converting to a char[] as opposed to accessing characters with .charAt(index):

• Converting to char[] creates a new array, so doubles the space
• Accessing characters with .charAt(index) incurs a boundary check every time

The computeMaximumBeauty method is very inefficient:

• It iterates over the characters once to find unique ones
• For each unique character it iterates over the characters again to count

You could combine these two steps.

You also incur some performance penalty due to autoboxing / unboxing, but that may be negligible.

Lastly, don't declare variables at the top. Java is not C. Declare variables the latest possible, and in the smallest scope possible. For example count could be declared in the for loop where it's used, and then you wouldn't need to reset it in every cycle.

The second implementation

This method counts the appearances better, by doing it one pass. Note that this line will do two map lookups when c is already in the map:

beautyMap.containsKey(c) ? beautyMap.get(c) + 1 : 1

First in .containsKey, then again in .get. To reduce the lookups, you can do one .get and a null-check.

When calculating the beauty, you iterate over entries, but use only the values:

for (Map.Entry<Character, Integer> e : valueSorted.entrySet()) {
    beauty += e.getValue() * beautyVal++;
}

If you don't need the keys, then it would be better to iterate over the values instead of the entries. And if you don't need the keys here, then probably you don't need them at all. So instead of a map, a list would have been enough, and probably simplify your logic.

This implementation also declares variables at the top, which is not so good. And it also incurs some performance penalties due to autoboxing / unboxing.

Suggested implementation

Here's an alternative implementation that's simpler. It uses the fact that there can be at most 26 unique values, so the appearance counts can be stored in a simple int[].

private int computeMaxBeauty(String text) {
    String sanitized = text.replaceAll("[^a-zA-Z]", "").toLowerCase();

    int[] counts = new int[26];
    for (int i = 0; i < sanitized.length(); ++i) {
        ++counts[sanitized.charAt(i) - 'a'];
    }

    Arrays.sort(counts);

    int sum = 0;
    for (int i = 25; i >= 0 && counts[i] > 0; --i) {
        sum += counts[i] * (i + 1);
    }
    return sum;
}

Answer 2

In your Java 8 version, you are significantly overcomplicating it.

Let's take a look at the basic question... maximum beauty is accomplished when the most common character has the largest score, the next most common has the next highest score, and so on, descending. Technically, there is no reason to know which character is the most common, just how many times it appears.... This is a trick.

This can easily be accomplished by using a simple array of integers, we will call counts. In to this array, we record how many times each letter appears.

Then, we sort the array to find out which letter is most common, and so on. There's a neat trick, that if we sort the counts in an ascending order, then the most common character count will be the last member of the array, which is index 25.... and the next most common count will be at index 24....

So, we can multiply the count, by the index + 1, to get the score for that character.

In Java8, this can easily be accomplished using some regex to throw out meaningless characters, and then some simple math and a sort to do the rest.

private static int beautyMax(String sentence) {
    int[] counts = new int[26];
    String clean = sentence.replaceAll("[^a-zA-Z]+", "").toLowerCase();
    IntStream.range(0, clean.length()).map(i -> clean.charAt(i) - 'a').forEach(i -> counts[i]++);
    Arrays.sort(counts);
    return IntStream.range(0, 26).map(i -> counts[i] * (i + 1)).sum();
}

This same logic is easy in traditional Java...

private static int beautyMax7(String sentence) {
    int[] counts = new int[26];
    for (char c : sentence.toLowerCase().toCharArray()) {
        if (c < 'a' || c > 'z') {
            continue;
        }
        counts[c - 'a']++;
    }
    Arrays.sort(counts);
    int sum = 0;
    for (int i = 0; i < counts.length; i++) {
        sum += counts[i] * (i + 1);
    }
    return sum;
}

On further reflection, the looping example above (as opposed to the streaming one), will be faster because it does not do the String regex, etc. and does not have an intermediate String value. The same logic in Streams, with 'continue' type logic, would be implemented with a filter(...), but we could/should also avoid the toLowerCase...:

private static int beautyMax(String sentence) {
    int[] counts = new int[26];
    IntStream.range(0, sentence.length())
        .map(i -> (int)sentence.charAt(i))
        .map(c -> (c >= 'a' && c <= 'z')
                ? (c - 'a') 
                : ((c >= 'A' && c <= 'Z') ? (c - 'A') : -1 ))
        .filter(i -> i >= 0)
        .forEach(i -> counts[i]++);
    Arrays.sort(counts);
    return IntStream.range(0, 26).map(i -> counts[i] * (i + 1)).sum();
}

Answer 3

I'm going to assume that you implemented the right thing (the spec is a bit open to interpretation).

For now, I just have a couple of small things about readability:

Naming

Some of your variable names are rather vague.

• i is only acceptable as an index variable. But that's not how you use it, which is extremely confusing. appearanceCount would be a lot better.
• short variable names generally hurt readability. I would write c and u out.
• What is the difference between beauty and beautyVal? Possibly better names might be accumulatedBeauty and currentBeautyValue. And both should be defined a lot further down in the method, so that the reader doesn't have to care about them until they are actually relevant, thus increasing readability.
• What does count count? I think the number of times each character appears? First of, it should not be defined at the method level, but at the lowest level possible (inside the first for loop, this also gets rid of one of the count = 0 assignments). Then it could be called uniqueCharacterOccuranceCount, or just occuranceCount (the rest should be obvious from the context).

Comments

I always appreciate method level JavaDoc comments, to get a small overview of what a method does, what arguments it accepts, and what it returns. It makes it a lot easier to see what's going on.

Misc

• Extract Code to methods: I would extract the counting of unique characters to its own method.
• using -- inline can be confusing, I would just add it in the next line.
• I already mentioned this in the Naming part, but as you do it quite often, I'll add it here as well for emphasis: you should define variable names in as small a scope as possible, as late as possible. For another example: you declare Map<Character, Integer> valueSorted at the top of your method, but do not use it for quite a while, which hurts readability.