/******************************************************************************
 *  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));
        }
    }
}