/******************************************************************************
* Name: Jeremie Lumbroso
* NetID: lumbroso
* Precept: N/A
*
* Partner Name: N/A
* Partner NetID: N/A
* Partner Precept: N/A
*
* Description: A solution to the Fall 2016 COS 226 Programming Exam.
*
* This exam is inspired by the 2013 startup what3words,
* which implements a geocoding system allowing the use of
* three words to reference any of 57 trillion 3 meter by 3
* meter squares on the earth.
*
* This solution, as a bonus, can be extended for larger
* dimensions (i.e., tuples of more than three words).
* TRY CHANGING THE VALUE OF D!
*
* Orders of growth:
* - constructor: N log N time N space
* - decode: log N time 1 space
* - encode: 1 time 1 space
*
* We use a symbol table implemented using balanced trees;
* the run time thus can be improved by instead using:
* - a hash table (log N factor becomes 1);
* - a trie (log N factor becomes k, where k is the length of
* longest word that is stored).
*
* Sample execution:
*
* $ java-algs4 What3Words words5-knuth.txt < testW3Wtiny.txt
* which.which.which 0
* below.stows.epees 1111111111
* until.beaks.clink 1234567890
*
******************************************************************************/
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.ST;
import java.lang.IllegalArgumentException;
public class What3Words
{
// [Bonus] Filename of original dictionary (for error reporting)
private static String dictionary;
// [Bonus] Number of words per "tuple"
private final static int D = 3;
// Number of words from the dictionary used as a basis
// (we define this as a long to be able to detect overflow errors)
private int N;
// Mapping of the index (of a line in the dictionary file) to a word
private String[] intToWord;
// Mapping of the words to their index in the file
//
// (can be done more efficiently with a TrieST<Integer>(), seen later in
// the course which can provide lookup in ~k where k is the size of the
// prefix of the string---rather than order of growth log N, which is
// what we have with this symbol table, implemented by a balanced tree).
private ST<String, Integer> wordToInt = new ST<String, Integer>();
// Useful constants
private static boolean OVERFLOW = false;
private static final boolean CHECK_MAX = false;
private static final int MAX_TUPLES = Integer.MAX_VALUE;
private static final int MAX_WORDS = (int) Math.pow(MAX_TUPLES,
1. / (double)(D));
public What3Words(String filename) {
dictionary = filename;
// Read in all strings
In in = new In(filename);
intToWord = in.readAllLines();
N = intToWord.length;
// [Bonus] To check this bound, we have to cast N as a long to ensure the
// product does not overflow (otherwise this check would be useless!)
OVERFLOW = ((long)N)*((long)N)*((long)N) >= MAX_TUPLES;
if (CHECK_MAX && OVERFLOW)
throw new IllegalArgumentException("dictionary '" + dictionary + "' " +
"contains too many words; not all " +
"tuples can be numbered with " +
"integers (max value: " +
MAX_TUPLES + "; max words: " +
MAX_WORDS + ")");
// Map the words back their index in the file
for(int i = 0; i < N; i++) {
String word = intToWord[i];
if (wordToInt.contains(word))
throw new IllegalArgumentException(word + " in dictionary '" +
dictionary + "' is a duplicate");
wordToInt.put(word, i);
}
}
public int decode(String[] words)
{
int result = 0;
// Let a, b and c be the integers corresponding to the provided words
// here we compute:
//
// ((a * N)*N + b)*N + c = a*N^2 + b*N + c
//
// this could be done with a one line of math, but to make it possible
// to extend this class to more than D=3 dimensions, we use an algorithm
// called "Horner's method" which minimizes the number of additions and
// multiplications that are made---and is the most efficient way of
// computing a real polynomial:
//
// https://en.wikipedia.org/wiki/Horner's_method
for(int i = 0; i < D; i++) {
if (!wordToInt.contains(words[i])) {
// If we don't check to see if the word exists, then the call to
// wordToInt.get will fail, so there will be an exception anyway;
// but it is nicer for our user that he gets an exception from
// our class, if the problem is predictable, that way the user
// does not think this might be an issue with the library we are
// using (in this case, the algs4 symbol table)
throw new IllegalArgumentException(words[i] + " used in a tuple " +
"was not in the original " +
"dictionary '" + dictionary + "' " +
"with which this class was built");
}
result = result * N + wordToInt.get(words[i]);
}
// This simpler answer is also valid:
//
// int num1 = wordToInt.get(words[0]);
// int num2 = wordToInt.get(words[1]);
// int num3 = wordToInt.get(words[2]);
//
// result = (num1 * N * N) + (num2 * N) + num3;
return result;
}
public String[] encode(int k)
{
String[] words = new String[D];
int temp = k;
// [Bonus] Check we can encode this integer with the current dictionary.
if (!OVERFLOW || k >= N*N*N)
throw new IllegalArgumentException(k + " cannot be encoded with the " +
"dictionary '" + dictionary + "' " +
"because it does not have enough " +
"words");
// As above, this answer can extend to more than D=3 dimensions
// but we also provide a simpler answer below (which is what was
// expected).
for(int i = D-1; i >= 0; i--) {
// Separate 'temp' into the remainder and quotient by N.
int remainder = temp % N;
int quotient = temp / N;
words[i] = intToWord[remainder];
// Set 'temp' to be equal to the quotient
temp = quotient;
}
// This simpler answer is also valid:
//
// int num3 = k % N;
// int num2 = ((k - num3) / N) % N;
// int num1 = (((k - num3) / N) - num2) / N;
//
// words[0] = intToWord[num1];
// words[1] = intToWord[num2];
// words[2] = intToWord[num3];
return words;
}
// Helper method---in Java 8, this is String.join(sep, strings)
private static String String_join(String separator, String[] strings)
{
if (strings == null || strings.length == 0)
return "";
String result = strings[0];
for(int i = 1; i < strings.length; i++)
result += separator + strings[i];
return result;
}
public static void main(String[] args)
{
What3Words w3w = new What3Words(args[0]);
while (!StdIn.isEmpty()) {
// Read word from StdIn
int k = StdIn.readInt();
// Encode
String[] words = w3w.encode(k);
String tuple = String_join(".", words);
// Output result (and redecoded value)
StdOut.print(tuple);
StdOut.println(" " + w3w.decode(words));
}
}
}
