// WordUtils.java
// Andrew Davison, ad@coe.psu.ac.th, Dec.2022

/* Main topics:
     * lists of 2- and 3- letter common words

     * partitioning a string

     * generating subsets of a string

     * permutating a string
       (3 versions: recursive, iterative, and using
        a factoradic representation of n, so the 
        sequence of permutations can be generated 
        incrementally rather than as one (too large) list);
            - the Factoradic version is used in 
              Anagrams.java and FactPermutes.java

     Note: the subset and permutations functions can take 
     Function arguments to apply a boolean test to a word 
     before it is added to the list of output words.

     * load a dictionary made up one word per line
       (e.g. words.txt)

     * methods for working with a grid of characters

     * general string methods: print, remove duplicate 
       characters, shuffle characters

     * parsing of integers and longs

  Usage:
    > compile WordUtils.java
    > run WordUtils
         -- runs a couple of tests
*/


import java.io.*;
import java.io.*;
import java.util.*;
import java.util.function.Function;


public class WordUtils
{
  private static final String DICT_FNM = "words.txt";
  private static final String ALPHABET = "abcdefghijklmnopqrstuvwxyz";

  private static final int NUM_PRINT_COLS = 5;


  public static final ArrayList<String> COMMON_TWOS = 
      new ArrayList<>( List.of(
        "in", "of", "to", "is", "it", "on", "no", "us", 
        "at", "un", "go", "an", "my", "up", "me", "as", 
        "he", "we", "so", "be", "by", "or", "do", "if", 
        "hi", "bi", "ex", "ok", "am"
     ));
  // https://www3.nd.edu/~busiforc/handouts/cryptography/cryptography%20hints.html
  // https://www.playosmo.com/kids-learning/common-two-letter-words/

  public static final ArrayList<String> COMMON_THREES = 
      new ArrayList<>( List.of(
    "and", "fix", "own", "are", "fly", "odd", "ape", "fry", "our", "ace", 
    "for", "pet", "act", "got", "pat", "ask", "get", "peg", "arm", "god", 
    "paw", "age", "gel", "pup", "ago", "gas", "pit", "air", "hat", "put", 
    "ate", "hit", "pot", "all", "has", "pop", "but", "had", "pin", "bye", 
    "how", "rat", "bad", "her", "rag", "big", "his", "rub", "bed", "hen", 
    "row", "bat", "ink", "rug", "boy", "ice", "run", "bus", "ill", "rap", 
    "bag", "jab", "ram", "box", "jug", "sow", "bit", "jet", "see", "bee", 
    "jam", "saw", "buy", "jar", "set", "bun", "job", "sit", "cub", "jog", 
    "sir", "cat", "kit", "sat", "car", "key", "sob", "cut", "lot", "tap", 
    "cow", "lit", "tip", "cry", "let", "top", "cab", "lay", "tug", "can", 
    "mat", "tow", "dad", "man", "toe", "dab", "mad", "tan", "dam", "mug", 
    "ten", "did", "mix", "two", "dug", "map", "use", "den", "mum", "van", 
    "dot", "mud", "vet", "dip", "mom", "was", "day", "may", "wet", "ear", 
    "met", "win", "eye", "net", "won", "eat", "new", "wig", "end", "nap", 
    "war", "elf", "now", "why", "egg", "nod", "who", "far", "net", "way", 
    "fat", "not", "wow", "few", "nut", "you", "fan", "oar", "yes", "fun", 
    "one", "yak", "fit", "out", "yet", "fin", "owl", "zip", "fox", "old", "zap"
  ));
     // https://www.playosmo.com/kids-learning/3-letter-words-for-kids/



  public static List<List<String>> partitions(String s)
  /* partitions("ABC") returns
       [["ABC"], ["A", "BC"], ["AB", "C"], ["ABC"]]
     https://stackoverflow.com/questions/42730364/recursive-method-to-generate-all-partitions-of-a-string
  */
  {
    List<List<String>> ps = new ArrayList<>();  // hold all partitions
    if (s.length() == 1) {
      ps.add(new ArrayList<>());
      ps.get(0).add(s);
    }
    else {
      for (List<String> ptt : partitions(s.substring(1))) {
        // loop through all partitions made without first char
        List<String> part1 = new ArrayList<>(ptt);  // copy partition
        part1.set(0, s.substring(0, 1) + part1.get(0));
                     // include first char in partition
        ps.add(part1);

        ptt.add(0, s.substring(0, 1));
                     // add first char as new partition
        ps.add(ptt);
      }
    }
    return ps;
  }  // end of partitions()



  private static ArrayList<String> subsets(String s)
  {  return subsets(s, WordUtils::goodWord);  }


  public static ArrayList<String> subsets(String s,
                            Function<String,Boolean> isValid)
  /* Loop through the number of subsets to generate
     all the possible strings.
     https://codesam.blogspot.com/2011/03/find-all-subsets-of-given-set.html
  */
  {
    ArrayList<String> words = new ArrayList<>();

    char[] chs = s.toCharArray();
    int numChars = chs.length;
    int numSubsets = (1 << numChars);

    ArrayList<Character> someChs = new ArrayList<>();
    for(int i = 0; i < numSubsets; i++) {
      int bitmask = i;
      someChs.clear();
      int pos = numChars - 1;   // work right-to-left in chs[]
      while (bitmask > 0) {
        if ((bitmask & 1) == 1) // a 1-bit means use that char
          someChs.add(chs[pos]);
        bitmask >>= 1;  // drop right most bit from mask
        pos--;
      }
      Collections.reverse(someChs);
      if (!someChs.isEmpty()) {   // skip empty set
        String word = toString(someChs);
        if (isValid.apply(word))
          words.add(word);
      }
    }
    return words;
  }  // end of subsets()


  private static Boolean goodWord(String word)
  /* every word is valid -- a Function which
     does no filtering */
  {   return true;  }


  // ------------------------ permutations ------------------------
  // 3 versions: recursive, iterative, factoradic


  public static ArrayList<String> permutes(String s)
  {  return permutes(s, WordUtils::goodWord);  }


  public static ArrayList<String> permutes(String s,
                            Function<String,Boolean> isValid)
  {
    ArrayList<String> words = new ArrayList<>();
    char[] chs = s.toCharArray();
    permutes(chs, 0, isValid, words);
    return words;
  }  // end of permutes()


  private static void permutes(char[] chs, int pos,
                           Function<String,Boolean> isValid,
                           ArrayList<String> words)
  {
    if (pos == chs.length-1) {   // last char of array so store
      String word = String.valueOf(chs);
  //    System.out.println("permutes: " + word);
      if (isValid.apply(word))
        words.add(word);
    }
    else {
      // try every later char in the pos position
      for (int i = pos; i < chs.length; i++) {
        swap(chs, pos, i);
        permutes(chs, pos+1, isValid, words);
        swap(chs, i, pos); // undo swap
      }
    }
  } // end of permutes()


  public static void swap(char[] chs, int i, int j)
  // swap ith and jth chars of the array
  { char temp = chs[i];
    chs[i] = chs[j];
    chs[j] = temp;
  } // end of swap()



  public static ArrayList<String> ipermutes(String s)
  {
    ArrayList<String> words = new ArrayList<>();
    ipermutes(s, words);
    return words;
  }  // end of ipermutes()


  private static void ipermutes(String s, ArrayList<String> words)
  // permutations of a string using iteration
  // https://www.techiedelight.com/find-permutations-string-cpp-java-iterative/
  {
    if (s == null || s.length() == 0)
      return;
    if (s.length() == 1) {
      words.add(s);
      return;
    }

    char[] chars = s.toCharArray();
    Arrays.sort(chars);
    int n = s.length();
    while (true) {
      words.add( String.valueOf(chars));

      /* Rearrange the string to the next
         lexicographically ordered permutation (if any) or return if
         we are already at the highest possible permutation
      */
      // Find largest i such that chars[i-1] < chars[i]
      int i = n - 1;
      while (chars[i-1] >= chars[i]) {
        /* if i is the first index of the string, we are
           already at the last possible permutation
           (string is sorted in reverse order) */
        if (--i == 0)
          return;
      }

      /* find the highest j to the right of i such that
         chars[j] > chars[i-1] 
         (chars[i...n-1] is sorted in reverse order) */
      int j = n - 1;
      while ((j > i) && (chars[j] <= chars[i-1]))
        j--;

      swap(chars, i-1, j);
      reverse (chars, i, n-1);
    }
  }  // end of ipermutes()


  private static void reverse(char[] arr, int i, int j)
  // reverse a char array between specified indices
  {
    while (i < j)   // stop when two endpoints intersect
      swap(arr, i++, j--);
  }



  public static String fpermute(long n, String word)
  // permutation generation using the Factoradic rep.
  // see Anagrams.java and FactPermutes.java
  {  return fpermute(n, word.toCharArray() );  }


  public static String fpermute(long n, char[] letters)
  {
    int[] fact = getFactoradic(n, letters);
    return getPermutation(fact, letters);
  }  // end of fpermute()




  public static int[] getFactoradic(long n, char[] letters)
  /* Get the Factoradic representation of n.
    Successively divide the number by 1,2,3,4 and so on until 
    the quotient becomes zero, and store the remainders in 
    right-to-left order in fact[].
  */
  {
    int[] fact = new int[letters.length];
    long idx = 1L;
    while (n != 0) {
      fact[(int)(letters.length - idx)] = (int)(n%idx);
      n = n/idx;
      idx++;
    }
    return fact;
  } /* getFactoradic */


  public static String getPermutation(int[] fact, char[] letters)
  /* return the nth permutation of letters by
     using the Factoradic representation of n
  */
  {
    ArrayList<Character> permChs = new ArrayList<>();
    boolean[] isCharUsed = new boolean[letters.length];     
                     // by default, values are initialised to false

    for (int i = 0; i < fact.length; i++) {
      int pos = fact[i];
      char ch = getUnusedCharAtPos(pos, isCharUsed, letters);
      permChs.add(ch);
    }

    StringBuilder sb = new StringBuilder();
    for (char ch : permChs)
      sb.append(ch);
    return sb.toString();
  } /* getPermutation */



  private static char getUnusedCharAtPos(int pos, 
                  boolean[] isCharUsed, char[] letters)
  /* Return the character from pos in letters. 
    Count from the left, starting at 0, and only count 
    unused letters.
  */
  {
    int unusedCnt = -1;
    for (int i = 0; i < letters.length; i++) {
      if (!isCharUsed[i]) {
        unusedCnt++;
        if (unusedCnt == pos) {
          isCharUsed[i] = true;
          return letters[i];
        }
      }
    }
    System.out.println("No unused character at " + pos);
    return '?';
  } /* getUnusedCharAtPos */



  // ----------------------- dictionary ------------------
  // a file of words, one word per line


  public static ArrayList<String> loadDict()
  { return loadDict(DICT_FNM);  }

  public static ArrayList<String> loadDict(String fnm)
  {
    ArrayList<String> words = new ArrayList<>();
    try (BufferedReader br = new BufferedReader(new FileReader(fnm))) {
      String line;
      while ((line = br.readLine()) != null)
        words.add(line);
      System.out.println("Loaded dictionary " + fnm);
    }
    catch (Exception e)
    {   System.out.println("Could not load dictionary " + fnm);  }

    return words;
  }  // end of loadDict()



  // ---------------------- grid methods -----------------------


  public static char[][] randomGrid(int numRows, int numCols)
  // Create a grid of size numRows x numCols filled with random letters
  {
    if ((numRows <= 0) || (numCols <= 0)) {
      System.out.println("Invalid dimensions");
      return null;
    }

    System.out.println("Generating a random grid of " + numRows +
                                                      " x " + numCols);
    char[][] grid = new char[numRows][numCols];
    for (int r = 0; r < numRows; r++) {
      for (int c = 0; c < numCols; c++) {
        grid[r][c] = ALPHABET.charAt(
                  (int)( Math.random() * ALPHABET.length()) );
      }
    }
    return grid;
  }  // end of randomGrid()



  public static char[][] loadGrid(String fnm)
  /* Format:
       <no. of rows> <no. of cols>
        a j ..... w
        n p ....
  */
  {
    try (BufferedReader br = new BufferedReader( new FileReader(fnm))) {
      System.out.println("Loading " + fnm);

      // get array dimensions
      String line = br.readLine();
      String[] dims = line.split("\\s+");
      if (dims.length != 2) {
        System.out.println("Dimensions not found");
        System.exit(1);
      }
      int numRows = getInt(dims[0]);
      int numCols = getInt(dims[1]);
      if ((numRows <= 0) || (numCols <= 0)) {
        System.out.println("Invalid dimensions");
        System.exit(1);
      }

      char[][] grid = new char[numRows][numCols];

      // fill the array, row-by-row
      int r = 0;
      while((line = br.readLine()) != null) {
        if (r == numRows) {
          System.out.println("Too many rows: " + (r+1));
          System.exit(1);
        }
        String[] letters = line.split("\\s+");
        if (letters.length != numCols) {
          System.out.println("Column length wrong on line " + (r+1));
          System.exit(1);
        }
        for (int c=0; c < letters.length; c++)
          grid[r][c] = letters[c].charAt(0);
        r++;
      }
      return grid;
    }
    catch (IOException e)
    {  System.out.println("Could not load " + fnm); }

    return null;
  } /* loadGrid */


  public static boolean onGrid(char[][] grid, int r, int c)
  {  return ((c >= 0) && (r >= 0) &&
              (c < grid[0].length) && (r < grid.length));
  }


  public static void printGrid(char[][] grid)
  {
    // print the header
    System.out.println("\n---------------------------------");
    System.out.print("    ");
    for (int c = 0; c < grid[0].length; c++)
       System.out.print(c + "  ");
    System.out.println();

    // print the grid
    for (int r = 0; r < grid.length; r++) {
      System.out.printf("%n%d  ", r);
      for (int c = 0; c < grid[0].length; c++)
        System.out.printf(" %c ", grid[r][c]);
    }
    System.out.println();
    System.out.println("---------------------------------\n");
  }  // end of printGrid()



  // ----------------------  string methods ------------------


  public static void printWords(Iterable<?> words)
  {  printWords(words, NUM_PRINT_COLS);  }


  public static void printWords(Iterable<?> words, int numCols)
  {
    int wCount = 0;
    for(Object w : words) {
      System.out.print("  " + w);
      wCount++;
      if (wCount%numCols == 0)
        System.out.println();
    }
    System.out.println();
    System.out.println("No. of words: " + wCount + "\n");
  }  // end of printWords()



  public static String toString(ArrayList<Character> subset)
  {
    StringBuilder sb = new StringBuilder();
    for (Character ch : subset)
      sb.append(ch);
    return sb.toString();
  }


  public static ArrayList<String> removeDups(
                              ArrayList<String> words)
  {  return new ArrayList<>(new LinkedHashSet<>(words));  }



  public static String shuffle(String s)
  {  return shuffle(s, s.length()/2);  }


  public static String shuffle(String s, int n)
  // apply n pair-wise swaps to the characters in s
  {
    String shuffleWord = s;
    int len = s.length();

    for(int t=0; t < n; t++) {
      int i = (int)(Math.random() * s.length());
      int j = (int)(Math.random() * s.length());
      shuffleWord = swapString(shuffleWord, i, j);
    }
    return shuffleWord;
  } /* shuffle */


  public static String swapString(String word, int i, int j)
  // Swaps chars at the given positions
  {
    char[] chs = word.toCharArray();
    char temp = chs[i];
    chs[i] = chs[j];
    chs[j] = temp;
    return new String(chs);
  } // end of swapString()


  // ---------------------- parsing --------------------

  public static int getInt(String s)
  {
    int num = 0;
    try {
      num = Integer.parseInt(s);
    }
    catch (NumberFormatException ex){
      System.out.println("Incorrect format for int " + s);
    }
    return num;
  }  // end of getInt()


  public static long getLong(String s)
  {
    long num = 0;
    try {
      num = Long.parseLong(s);
    }
    catch (NumberFormatException ex){
      System.out.println("Incorrect format for long " + s);
    }
    return num;
  }  // end of getLong()



  // ----------------- test rig ------------------


  public static void main(String[] args)
  {
    System.out.println("Partitions of \"abcde\":");
    List<List<String>> parts = partitions("abcde");
    for (List<String> part : parts)
       System.out.println("  " + part);
    System.out.println();

    ArrayList<String> subsets = WordUtils.subsets("atest");
    Collections.sort(subsets, new LengthFirstComparator());
    WordUtils.printWords(subsets);

    Function<String, Boolean> len3 = w -> (w.length() > 3);
    Function<String, Boolean> keylen3 = w ->
                             ((w.length() > 3) && w.contains("s"));

    subsets = WordUtils.subsets("atest", keylen3);   // len3
    Collections.sort(subsets, new LengthFirstComparator());
    WordUtils.printWords(subsets);


    ArrayList<String> perms = WordUtils.permutes("atest");
    Collections.sort(perms);
    perms = WordUtils.removeDups(perms);
    WordUtils.printWords(perms);

    Function<String, Boolean> firsta = w -> (w.charAt(0) == 'a');
    perms = WordUtils.permutes("atest", firsta);
    Collections.sort(perms);
    perms = WordUtils.removeDups(perms);
    WordUtils.printWords(perms);

    perms = WordUtils.ipermutes("atest");
    Collections.sort(perms);
    perms = WordUtils.removeDups(perms);
    WordUtils.printWords(perms);


    ArrayList<String> dict = WordUtils.loadDict();
    System.out.println("Is \"collection\" in dictionary? " +
                                 dict.contains("collection"));
    System.out.println("Is \"colection\" in dictionary? " +
                                 dict.contains("colection"));
  }  // end of main()


}  // end of WordUtils class