// Program to print out combinations of strings that appear in a dictionary.
// The program makes use of a Dictionary object and prompts for a file name
// with the strings to consider for forming words.

import java.io.*;
import java.util.*;

public class Jumble {
    public static void main(String[] args) throws FileNotFoundException {
        // prompt for file name
        Scanner console = new Scanner(System.in);
        System.out.println("Welcome to the CSE143 Word Jumble Program");
        System.out.println();
        System.out.print("What file of strings do you want to use? ");
        String fileName = console.nextLine();

        // read strings into a list
        Scanner input = new Scanner(new File(fileName));
        List<String> options = new ArrayList<>();
        while (input.hasNext()) {
            options.add(input.next());
        }

        // construct the dictionary
        Dictionary words = new Dictionary();
        
        System.out.println("Jumbles of length 3:");
        printJumbles(words, options, 3);
        System.out.println();

        System.out.println("Jumbles of any length:");
        printJumbles2(words, options);
        System.out.println();

        System.out.println("Jumbles of any length with no repeated strings:");
        printJumbles3(words, options);
    }

    // Prints all sequences of strings chosen from options and using the given
    // number of words that are words in the dictionary.
    public static void printJumbles(Dictionary words, List<String> options,
                                     int numWords) {
        printJumbles(words, options, numWords, "");
    }

    // Explores all combinations of strings from options that can be used to
    // form a word in the given dictionary.  The parameter soFar keeps track of
    // the current string being considered and the parameter choices indicates
    // how many choices are left to make.
    public static void printJumbles(Dictionary words, List<String> options,
                                     int choices, String soFar) {
        if (choices == 0) {
            if (words.contains(soFar)) {
                System.out.println(soFar);
            }
        } else {
            for (String word : options) {
                printJumbles(words, options, choices - 1, soFar + word);
            }
        }
    }

    // Prints all sequences of strings chosen from options and that are words
    // in the dictionary.
    public static void printJumbles2(Dictionary words, List<String> options) {
        printJumbles2(words, options, "");
    }

    // Explores all combinations of strings from options that can be used to
    // form a word in the given dictionary.  The parameter soFar keeps track of
    // the current string being considered.  The method assumes that soFar is
    // the prefix of at least one word in the dictionary.
    public static void printJumbles2(Dictionary words, List<String> options, 
                                     String soFar) {
        if (words.contains(soFar)) {
            System.out.println(soFar);
        }
        for (String word : options) {
            String newString = soFar + word;
            if (words.containsPrefix(newString)) {
                printJumbles2(words, options, newString);
            }
        }
    }

    // Prints all sequences of strings chosen from options and that are words
    // in the dictionary and using each string at most once.
    public static void printJumbles3(Dictionary words, List<String> options) {
        printJumbles3(words, options, "", new TreeSet<>());
    }

    // Explores all combinations of strings from options that can be used to
    // form a word in the given dictionary using each string at most once.  The
    // parameter soFar keeps track of the current string being considered.  The
    // method assumes that soFar is the prefix of at least one word in the
    // dictionary.  The parameter used keeps track of which strings are
    // included in soFar.
    public static void printJumbles3(Dictionary words, List<String> options, 
                                     String soFar, Set<String> used) {
        if (words.contains(soFar)) {
            System.out.println(soFar);
        }
        for (String word : options) {
            String newString = soFar + word;
            if (!used.contains(word) && words.containsPrefix(newString)) {
                used.add(word);
                printJumbles3(words, options, newString, used);
                used.remove(word);
            }
        }
    }
}