Overview

BabyGPT.java implements a simple text generator by using a graph to store words as vertices and edges to encode valid sentence structures. This uses a simplified version of Markov Chains.

We will categorize all provided words into the following 6 types: Subject, Auxiliary, Verb, Noun, Adverb, Preposition

Then, when we add all the vertices to the graph, we can group them based on their word type. (we do not group them at all in the data structure, just algorithmically).

Then, we can define possible sentence structures, which connect these groups to one another in specific orders.

You will first implement the method for reading words from an input file then storing them in a HashMap based on their type. Then, you will implement a method to build the word graph, for all possible sentence structures.

Finally, we provide a method with a modified version of Dijkstra’s algorithm, which traverses the graph in a valid sentence ordering based on the given prompt. This creates technically valid (or close to valid) sentences for different inputs.

Overview of files provided

• BabyGPT.java – This file contains the adjacency list representation of the sentence graph, where you will build the word dictionary and network. This will be submitted to Autolab. 
• Word.java – This class represents a single word, with attributes for the word text, its type, and a int frequency value.
• StdIn.java – StdIn library provided for your use when reading in words from the input file.
• Driver.java – This class can be used to simply test the output of the word graph, and interact with the text generator. 

UPDATE and SUBMIT the BabyGPT.java file to Autolab

Working With HashMaps

• The java.util package contains many premade data structures such as ArrayList, LinkedList, and HashMap.
• HashMap is a Java <key, value> data structure, functionally equivalent to a Hash Table.
  • HashMap<K,V> map = new HashMap<K, V>(); will initialize an empty map, with keys having type K and values having type V.  
  • map.put(K key, V value) will put the given value into the hash map with the given key, or update the value if it is already present.
  • map.get(K key) will return the corresponding value for the given key.
• HashMaps (and other implementations like HashSet, Hashtable) are good for solving many problems.
  • Tracking values for many different variables (keys)
  • Finding duplicates / frequency of elements
  • Tracking pairs (such as two sum)
• You can loop over a HashMap with “for (HashMap.Entry<Key, Value> entry : mapName.entrySet())”
  • Then, “entry” loops over every key-value pair in the map.
  • Use entry.getKey() and entry.getValue() to get the current key-value data.

Working With ArrayLists

An ArrayList is an ordered array-like structure with no size limit, as it automatically resizes.

• You can initialize an empty ArrayList named “name” which holds objects of type “Type” with ArrayList name = new ArrayList<>();
• For example, an ArrayList of integers named “arrList” is initialized with ArrayList arrList = new ArrayList<>();
• You can add a new element of type “Type” to the end of your ArrayList in average case O(1) time with name.add(newElement);
• You can get the element at some index of your ArrayList in O(1) time with name.get(index);
• You can set some index to some new element in O(1) time with name.set(index, newElement);
• You can check if the ArrayList contains some element (returns a boolean) in O(n) time with name.contains(element)
• You can find the index of an item in the ArrayList using name.indexOf(item) – if the item is not present in the ArrayList this will return -1  
• To get the number of elements in the ArrayList do name.size()

Working with LLNode<> objects

For assignments/labs in CS112, we will use a cs112.jar file containing useful classes. This includes the LLNode<> class, which implements a singly linked list node.  

• The LLNode class takes in a generic type, which means it can store any type of data. In this lab you will be working with nodes that have Word data – to have nodes with Word data we can use LLNode 
• Making a node: LLNode newNode = new LLNode<>(data) – replace T with a type
  • Note that the data must be passed in for the constructor, and the data of a node can not be changed later (aka it is immutable)
• Methods: 
  • getNext() – returns the next node in the linked list 
  • getData() – returns the data stored in the current node
  • setNext(LLNode nextNode) – sets the next node of the current node to nextNode

Programming

First, ensure that you are working in the correct directory. See this image:

Methods to be implemented by you: