The challenge
Consider a “word” as any sequence of capital letters A-Z (not limited to just “dictionary words”). For any word with at least two different letters, there are other words composed of the same letters but in a different order (for instance, STATIONARILY/ANTIROYALIST, which happen to both be dictionary words; for our purposes “AAIILNORSTTY” is also a “word” composed of the same letters as these two).
We can then assign a number to every word, based on where it falls in an alphabetically sorted list of all words made up of the same group of letters. One way to do this would be to generate the entire list of words and find the desired one, but this would be slow if the word is long.
Given a word, return its number. Your function should be able to accept any word 25 letters or less in length (possibly with some letters repeated), and take no more than 500 milliseconds to run. To compare, when the solution code runs the 27 test cases in JS, it takes 101ms.
For very large words, you’ll run into number precision issues in JS (if the word’s position is greater than 2^53). For the JS tests with large positions, there’s some leeway (.000000001%). If you feel like you’re getting it right for the smaller ranks, and only failing by rounding on the larger, submit a couple more times and see if it takes.
Sample words, with their rank:
ABAB = 2
AAAB = 1
BAAA = 4
QUESTION = 24572
BOOKKEEPER = 10743
The solution in Java code
Option 1:
import java.math.BigInteger;
import java.util.*;
public class Anagrams {
public BigInteger listPosition(String word) {
Map<Character, Integer> map=new HashMap<Character, Integer> ();
BigInteger fac=new BigInteger("1");
BigInteger ans=new BigInteger("1");
BigInteger count=new BigInteger("0");
for(int i=word.length()-1;i>=0;--i) {
count=count.add(new BigInteger("1"));
fac=fac.multiply(count);
if(map.get(word.charAt(i))==null)
map.put(word.charAt(i),0);
map.put(word.charAt(i),map.get(word.charAt(i))+1);
fac=fac.divideAndRemainder(new BigInteger(String.valueOf(map.get(word.charAt(i)))))[0];
for(Character c:map.keySet()) {
if(c<word.charAt(i)) {
ans=ans.add(fac.divideAndRemainder(count)[0].multiply(new BigInteger(String.valueOf(map.get(c)))));
}
}
}
return ans;
}
}
Option 2:
import java.math.BigInteger;
import java.util.*;
public class Anagrams {
public BigInteger listPosition(String word) {
int len = word.length();
ArrayList<Character> letters = new ArrayList<>(len);
for(int i = 0; i < len; ++i)
letters.add(word.charAt(i));
Collections.sort(letters);
BigInteger count = BigInteger.ONE;
for(int i = 0; i < len - 1; ++i) {
char cword = word.charAt(i);
int j = i;
char clast = '\0';
char ccurr;
while((ccurr = letters.get(j)) < cword) {
if(ccurr != clast)
count = count.add(calcPossibs(letters, i, j));
++j;
clast = ccurr;
}
if(j > i) {
letters.remove(j);
letters.add(i, ccurr);
}
}
return count;
}
private BigInteger calcPossibs(ArrayList<Character> letters, int i, int j) {
HashMap<Character, Integer> map = new HashMap<>();
for(int k = i; k < letters.size(); ++k)
if(k != j) {
Character c = letters.get(k);
Integer count = map.get(c);
map.put(c, count == null ? 1 : count + 1);
}
BigInteger result = BigInteger.ONE;
for(int k = letters.size() - i - 1; k >= 2; --k)
result = result.multiply(BigInteger.valueOf(k));
for(Integer v : map.values())
for(int k = v; k >= 2; --k)
result = result.divide(BigInteger.valueOf(k));
return result;
}
}
Option 3:
import java.math.BigInteger;
import java.util.HashMap;
import java.util.SortedMap;
import java.util.TreeMap;
import static java.math.BigInteger.ONE;
import static java.util.stream.Collectors.toMap;
public class Anagrams {
private static final HashMap<Integer,BigInteger> cache = new HashMap<>();
private static BigInteger factorial(int n) {
BigInteger ret;
if (n == 0) return BigInteger.ONE;
if (null != (ret = cache.get(n))) return ret;
ret = BigInteger.valueOf(n).multiply(factorial(n-1));
cache.put(n, ret);
return ret;
}
private static SortedMap<Character, Integer> getCountMap(String word) {
return word.chars().boxed().collect(toMap(i -> (char) i.intValue(), i -> 1, Integer::sum, TreeMap::new));
}
private static BigInteger countPermutation(String word) {
return getCountMap(word).values().stream().reduce(factorial(word.length()), (res,n) -> res.divide(factorial(n)), (a,b) -> a.add(b));
}
public BigInteger listPosition(String word) {
BigInteger pos = ONE;
for (char ch : word.toCharArray()) {
for (char ch1 : getCountMap(word).headMap(ch).keySet()) {
pos = pos.add(countPermutation(word.replaceFirst("" + ch1, "")));
}
word = word.replaceFirst("" + ch, "");
}
return pos;
}
}
Test cases to validate our solution
import static org.junit.Assert.assertEquals;
import java.math.BigInteger;
import org.junit.Test;
public class AnagramTest {
@Test
public void testKnownInputs() {
Anagrams anagram = new Anagrams();
assertEquals("Position for 'A' incorrect", BigInteger.ONE, anagram.listPosition("A"));
assertEquals("Position for 'ABAB' incorrect", BigInteger.valueOf(2), anagram.listPosition("ABAB"));
assertEquals("Position for 'AAAB' incorrect", BigInteger.ONE, anagram.listPosition("AAAB"));
assertEquals("Position for 'BAAA' incorrect", BigInteger.valueOf(4), anagram.listPosition("BAAA"));
assertEquals("Position for 'QUESTION' incorrect", BigInteger.valueOf(24572), anagram.listPosition("QUESTION"));
assertEquals("Position for 'BOOKKEEPER' incorrect", BigInteger.valueOf(10743), anagram.listPosition("BOOKKEEPER"));
assertEquals("Position for 'IMMUNOELECTROPHORETICALLY' incorrect", new BigInteger("718393983731145698173"), anagram.listPosition("IMMUNOELECTROPHORETICALLY"));
}
@Test
public void testRandomInputs() {
Anagrams anagram = new Anagrams();
anagram.listPosition("A");
assertEquals("Hey, now, get out of my private methods!", 0, GetOut.getAccess());
String random = ranWord(25);
for(int i = 0; i < 10; i++) {
BigInteger calculated = GetOut.listPosition(random), actual = anagram.listPosition(random);
assertEquals("Incorrect list position for: " + random, calculated, actual);
random = ranWord();
}
}
private char ranChar() {
return "ABCDEFGHIJKLMNOPQRSTUVWXYZ".charAt((int)Math.floor(Math.random() * 26));
}
private String ranWord() {return ranWord((int)Math.ceil(25 * Math.random()));}
private String ranWord(int length) {
StringBuilder word = new StringBuilder();
for(int i = 0; i < length; i++) {
word.append(ranChar());
}
return word.toString();
}
}