markov chain

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

public class Driver {
    //finds out if an arraylist of strings contains a specific string
    public static boolean contains (ArrayList<String> a, String x) {
        for (int i = 0; i < a.size(); i++) {
            if (a.get(i).equals(x))
                return true;
        }
        return false;
    }

    //finds the index of a string in the top row of a 2d arraylist of strings
    public static int indexinhoriz (ArrayList<ArrayList<String>> m, String s) {
        for (int i = 0; i < m.get(0).size(); i++) {
            if (m.get(0).get(i).equals(s))
                return i;
        }
        return -1;
    }

    //finds the index of a string in the left column of a 2d arraylist of strings
    public static int indexinvert (ArrayList<ArrayList<String>> m, String s) {
        for (int i = 0; i < m.size(); i++) {
            if (m.get(i).get(0).equals(s))
                return i;
          }
        return -1;
     }

    public static void main (String []args) throws IOException {
        //example input:
        String text = "According to all known laws of aviation there is no way a bee should be able to fly.Its wings are too small to get its fat little body off the ground.The bee of course flies anyway because bees don't care what humans think is impossible";
        //the only punctuation you can have in the input string are periods (and apostrophes within words). don't put spaces after periods.
         text = text.toLowerCase();

         String[] temp = text.split("\\."); //creates an array where each index holds 1 sentence
         ArrayList<String> swords = new ArrayList<String>(); //words that start sentences
         ArrayList<String> ewords = new ArrayList<String>(); //words that end sentences
         ArrayList<String[]> words = new ArrayList<String[]>(); //array that will hold each individual word
         for (int i = 0; i < temp.length; i++) {
             words.add(temp[i].split(" ")); //each string array in words will represent one sentence, with one index per word
             String[] temptemp = words.get(i); //gets the current string array (sentence)
             swords.add(temptemp[0]); //adds beginning word to swords
             ewords.add(temptemp[temptemp.length-1]); //adds ending word to ewords
         }

         ArrayList<String> wordsnorepeats = new ArrayList<String>(); //a list of all the words with no duplicates
         int iofal = 0; //stands for index of arraylist
         while (iofal < words.size()) { //while loop fills in wordsnorepeats
             String[] temptemp = words.get(iofal);
             for (int i = 0; i < temptemp.length; i++) {
                 if (!contains(wordsnorepeats, temptemp[i])) {
                    wordsnorepeats.add(temptemp[i]);
                 }
             }
             iofal++;
         }

         /*markov is a 2d arraylist where the top row & left column contain all the words. when looping through a sentence, the left column represents the current word and the top row represents the next word. the other spaces represent the frequencies that two words are next to each other. */
         ArrayList<ArrayList<String>> markov = new ArrayList<ArrayList<String>>(); //where the magic happens!
         wordsnorepeats.add(0, " "); //so that the top left corner of markov is blank
         markov.add(wordsnorepeats); //set top row
         for (int i = 1; i < wordsnorepeats.size(); i++) { //for loop sets the left column and the frequencies
             ArrayList<String> temptemptemp = new ArrayList<String>();
             temptemptemp.add("change"); //will later change to an actual word
             for (int j = 0; j < wordsnorepeats.size()-1; j++) {
                 temptemptemp.add("0"); //frequencies start out at 0
             }
             temptemptemp.set(0, wordsnorepeats.get(i)); //replaces the "change" from before
             markov.add(temptemptemp); //adds the column + frequencies to markov
         }

         /*this section fills in the frequencies by looping through the list of words*/
         for (int r = 0; r < words.size(); r++) { //r is row
             String[] t = words.get(r);
             for (int c = 0; c < t.length-1; c++) { //c is column & the for loop goes to t.length-1 because the ending words don't count
                 int data = Integer.parseInt(markov.get(indexinhoriz(markov,t[c+1])).get(indexinvert(markov, t[c])))+1; //gets the current frequency and adds one
                 markov.get(indexinvert(markov, t[c])).set(indexinhoriz(markov,t[c+1]), Integer.toString(data)); //actually sets the frequency value (yay i actually split this line up!!)
             }
         }

         /*this section creates the sentence by picking a starting word, going to its row, adding up all the frequencies in it, picking a random value from 1 to the sum of the frequencies, and then going back through and adding the frequencies up again until it reaches the number it picked. the index it ends up on is the index of the word that comes next. */
         String sentence = "";
         String word = swords.get((int)(Math.random()*swords.size())); //picks starting word
         boolean endofsentence = false;
         while (!endofsentence) {
             if (contains(ewords, word)) {
                 int x = (int)(Math.random()*10); //change 10 to change the average length of the sentences
                 if (x == 1 || x == 0 || x == 2)
                    endofsentence = true;
             }
             sentence += word;
             sentence += " ";
             int linesum = 0;
             ArrayList<String> t2 = markov.get(indexinvert(markov, word)); //gets current column
             //System.out.println(t2);
             for (int i = 1; i < t2.size(); i++) {
                 linesum += Integer.parseInt(t2.get(i)); //adds up all frequencies
             }
             int wordindex = (int)(Math.random() * linesum)+1;
             int currentindex = 0;
             int currentcount = 0;
             if (linesum == 0) { //to prevent index out of bounds errors
                 endofsentence = true;
             } else {
                 while (currentcount < wordindex && currentindex < t2.size()) {
                     currentindex++; //actual index of the word
                     currentcount += Integer.parseInt(t2.get(currentindex)); //sum of frequencies so far
                 }
                 word = markov.get(0).get(currentindex); //sets the new word
             }
         }
         sentence = sentence.substring(0, sentence.length()-1) + "."; //deletes space from the end and adds a period
         System.out.println(sentence);

       }
}