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