HW09

If at first you don't succeed...

README (Before Lab)

Overview

A trie (prefix tree) is a special kind of tree that can store bunch of words (a vocabulary, a lexicon) in a super cool way.
- Each node has a single letter (except for the root node, which is blank).
- Each node also has a boolean that says whether the node has the last letter in a word ("terminates" the word).
  - If this boolean is true, then we say the node is a terminal node.
  - We can read a word out of a trie by following a path down from the root to a terminal node.
Example:
- Terminal nodes are colored cyan (greenish-blue).
- The trie stores these words: [a, app, apple, awe, ban, banana, id]

API

Node

Each instance of the Node class has an array of references to its children.
- Node[] children is constructed to have 26 elements (corresponding to 'a', 'b', ..., 'z' in order)
- It might seem weird at first, but a Node object does NOT actually store its own letter!
  - Instead, a node's letter is implicit in its index in its parent's array of children.
    - children[0] has letter 'a', children[1] has letter 'b', and so on.
We can convert between a letter index (0, 1, ..., 25) and its corresponding letter ('a', 'b', ..., 'z').
- int letterIndex = letter - 'a';
  - 0 <--letterIndex from letter-- 'a'
  - 1 <--letterIndex from letter-- 'b'
  - ...
- char letter = (char)('a' + letterIndex);
  - Note: (char)(...) is a cast. In order to assign the result of 'a' + letterIndex to letter, we have to cast it from an int to a char. Otherwise, we get acompiler error. (Error: incompatible types: possible lossy conversion from int to char)
  - 'a' <--letter from letterIndex-- 0
  - 'b' <--letter from letterIndex-- 1
  - ...

API Example

👀 Example: Hard-coding the word cat into the trie.

root = new Node();
root.children[2] = new Node();
root.children[2].children[0] = new Node();
root.children[2].children[0].children['t' - 'a'] = new Node();
root.children[2].children[0].children['t' - 'a'].isTerminal = true;

Complete Example

👀 Complete Example: What should happen when the autograder runs?

NOTE: This does NOT include the A+ problem for pruning the tree.

 *

> addWord("app"); // returns true

 *
 |
 a
 |
 p
 |
[p]

> addWord("a"); // returns true

 *
 |
[a]
 |
 p
 |
[p]

> addWord("a"); // returns false ("a" already in trie)

> containsWord("a"); // returns true

> containsWord("app"); // returns true

> containsWord("apple"); // returns false

> removeWord("app"); // returns true

 *
 |
[a]
 |
 p
 |
 p

> removeWord("app"); // returns false ("app" was not in trie)

> containsWord("a"); // returns true

> containsWord("app"); // returns false

> containsWord("apple"); // returns false

> addWord("at");

   *
   |
  [a]
  / \
 p  [t]
 |
 p

> addWord("cow");

      *
    /   \ 
  [a]    c
  / \    |
 p  [t]  o
 |       |
 p      [w]

> addWord("atom");

      *
    /   \ 
  [a]    c
  / \    |
 p  [t]  o
 |   |   |
 p   o  [w]
     |
    [m]

> getAllWords(); // returns [a, at, atom, cow]

> removeWord("atom"); // returns true

      *
    /   \ 
  [a]    c
  / \    |
 p  [t]  o
 |   |   |
 p   o  [w]
     |
     m

> removeWord("atom"); // returns false

> getAllWords(); // returns [a, at, cow]

TODO's

A-
- Update Cow
- Implement all functions marked with TODO's except getAllWords()
  - HINT: You do NOT need to do a full tree traversal to solve either of these questions. (My solution does NOT use recursion or a stack or a queue or anything fancy like that; I just use a for loop 🙂👍)
  - ✨ Implement them one at a time, in order, testing as you go.
  - ✨ Try out the interactive app to test your code!
    - ✨ The app prints out instructions when it starts; Please ask questions if you are unsure about how to use it. 🙂👍
- IMPORTANT: Copy and paste the autograder output into a comment at the top of your code file once you're done with everything.
- NOTE: Make sure to follow all NOTE's in the Starter Code comments.
- HINT: You can add your own little test cases in the Trie constructor.
A
- Implement all functions marked with TODO's.
A+
- Do >= 1 of the following...
  - Improve removeWord(String word) to prune away any parts of the trie that are no longer needed following the removal of word. (Maybe recursion is helpful? Maybe not?) The final state of the Complete Example should now be:
```
   *
 /   \ 
[a]   c
 |    |
[t]   o
      |
     [w]
```
  - Implement Spelling Corrections from the old version of the homework.
    - Feel free to temporarily comment out the Cow and draw stuff in main.
  - Implement Matching Regular Expressions from the old version of the homework.
A++
- Extend the starter code's wonderful draw function to make the addition and removal of nodes animated (the trie should grow and branch like it's alive)
  - Explain your approach, in detail, in a comment at the top of your code
  - NOTE: The smoother the animation, the better

Starter Code

import java.util.*;
class HW09 extends Cow {

	static class Node {
		// The node's children
		// children[0] corresponds to 'a', children[1] corresponds to 'b', ...
		// Initially, all children are null (empty slots)
		Node[] children;

		// Whether the node corresponds to the last letter in a word
		boolean isTerminal;

		Node() {
			this.children = new Node[26]; // [ null, null, ..., null ]
			this.isTerminal = false; // NOTE: This line is optional
		}
	}

	static class Trie {
		// The root node of the trie.
		Node root;

		// Construct a new trie.
		// NOTE: Feel free to write your own tests in this constructor.
		// NOTE: Uncomment the autograder line to run a simple auto-grading function.
		//       The autograder builds a trie by calling the functions you will implement.
		//       +'s are passing tests; -'s are failing tests.
		//       (A crash means one of more of your functions is broken.)
		Trie() {
			this.root = new Node();

			// this.addWord("apple");

			// AutoGrader.grade(this);
		}

		// If the word is NOT in the trie, adds the word to the trie and returns true.
		// Otherwise, does nothing and returns false.
		// NOTE: Do NOT call containsWord(...) inside this function.
		//       Doing so would be inefficient (slow).
		boolean addWord(String word) {
			Node curr = root;
			// TODO

			return false;
		}

		// Returns whether the word is in the trie.
		// NOTE: Do NOT call getAllWords() inside this function.
		// NOTE: Do NOT call addWord(...) inside this function.
		// NOTE: Do NOT call removeWord(...) inside this function.
		boolean containsWord(String word) {
			// TODO

			return false;
		}

		// If the word is in the trie, removes the word from the trie and returns true.
		// Otherwise, does nothing and returns false.
		// NOTE: You can "remove" a word by setting the last node in the word's isTerminal to false.
		//       This looks odd in the visualizer, but is A OK.
		//       You do NOT have to actually remove nodes / "prune the tree."
		//       (You certainly can if you want!--It's kinda tricky!)
		// NOTE: Do NOT call containsWord(...) inside this function.
		boolean removeWord(String word) {
			// TODO 

			return false;
		}


		// Get all the words in the trie in alphabetical order.
		// 
		// NOTE: Don't worry about the list being alphabetical.
		//       Our trie gives us this "for free."
		// 
		// NOTE: This problem has a cute recursive solution in Java.
		//       I've set things up assuming you will use recursion.
		// NOTE: Using recursion is optional.
		ArrayList<String> getAllWords() {
			ArrayList<String> result = new ArrayList<>();
			_getAllWordsHelper(root, "", result);
			return result;
		}

		// Recursive helper function (calls itself).
		void _getAllWordsHelper(Node node, String prefix, ArrayList<String> result) {
			// TODO

		}

	}


	/////////////////////////
	// YOUR CODE ENDS HERE //
	/////////////////////////


	////////////////
	// AUTOGRADER //
	////////////////

	static class AutoGrader {
		static void grade(Trie trie) {
			trie.root = new Node();
			System.out.print("[AutoGrader] ");
			_grade(trie.addWord("app"), true);
			_grade(trie.addWord("a"), true);
			_grade(trie.addWord("a"), false); //
			_grade(trie.containsWord("a"), true);
			_grade(trie.containsWord("app"), true);
			_grade(trie.containsWord("apple"), false); 
			_grade(trie.removeWord("app"), true);
			_grade(trie.removeWord("app"), false);
			_grade(trie.containsWord("a"), true);
			_grade(trie.containsWord("app"), false);
			_grade(trie.containsWord("apple"), false);
			_grade(trie.addWord("at"), true);
			_grade(trie.addWord("cow"), true);
			_grade(trie.addWord("atom"), true);
			_gradeGetAllWords(trie, new String[]{ "a", "at", "atom", "cow" }); //
			_grade(trie.removeWord("atom"), true);
			_grade(trie.removeWord("atom"), false);
			_gradeGetAllWords(trie, new String[]{ "a", "at", "cow" }); //
			PRINT(" // +'s are passing tests; -'s are failing tests\n");
		}

		static void _grade(boolean studentAnswer, boolean correctAnswer) {
			boolean isCorrect = (studentAnswer == correctAnswer);
			System.out.print(isCorrect ? "+" : "-");
		}

		static void _gradeGetAllWords(Trie trie, String[] correctAllWords) {
			ArrayList<String> studentAllWords = trie.getAllWords();
			boolean match = (studentAllWords.size() == correctAllWords.length);
			if (match) {
				for (int i = 0; i < correctAllWords.length; ++i) {
					if (!studentAllWords.get(i).equals(correctAllWords[i])) {
						match = false;
						break;
					}
				}
			}
			_grade(true, match);
		}
	}


	//////////
	// MAIN //
	//////////

	public static void main(String[] arguments) {        
		_trie = new Trie();
		_consoleBuffer = "";
		_consoleState = CONSOLE_STATE_ADDING;

		PRINT("Press + start adding words.");
		PRINT("Press - start removing words.");
		PRINT("Press ? start querying (asking) whether words are in the _trie.");
		PRINT("Type a word like you normally do.");
		PRINT("Press Enter to add/remove/query a word.");
		PRINT("Press Space to print all the words in the trie.");
		PRINT("Press Escape to quit.");
		PRINT();

		canvasConfig(0, 0, 8, 8);

		double canvasWidth = _canvas_get_width_World();
		double canvasHeight = _canvas_get_height_World();
    
		while (beginFrame()) {
			_HW09_drawTrie(_trie.root, canvasWidth, canvasHeight);
			_HW09_updateConsole();
			_HW09_drawConsole();

		}
	}


	/////////////
	// CONSOLE //
	/////////////

	static final int CONSOLE_STATE_ADDING   = 0;
	static final int CONSOLE_STATE_REMOVING = 1;
	static final int CONSOLE_STATE_QUERYING = 2;

	static String _consoleBuffer;
	static int _consoleState;

	static void _HW09_updateConsole() {
		if (keyPressed(27)) { // FORNOW
			System.exit(0);
		} else if (keyPressed('=')) {
			_consoleState = CONSOLE_STATE_ADDING;
		} else if (keyPressed('-')) {
			_consoleState = CONSOLE_STATE_REMOVING;
		} else if (keyPressed('/')) {
			_consoleState = CONSOLE_STATE_QUERYING;
		} else if (keyPressed(' ')) {
			System.out.println("[getAllWords] " + _trie.getAllWords());
		} else if (keyPressed('\b')) {
			if (_consoleBuffer.length() > 0) {
				_consoleBuffer = _consoleBuffer.substring(0, _consoleBuffer.length() - 1);
			}
		} else if (keyPressed('\n') || keyPressed('\r')) {
			String word = _consoleBuffer.trim();
			boolean valid = true;
			if (word.length() > 0) {
				if (_consoleState == CONSOLE_STATE_ADDING) {
					boolean added = _trie.addWord(word);
					if (added) {
						System.out.println("[addWord] added \"" + word + "\" to the trie");
					} else {
						System.err.println("[addWord] did NOT add \"" + word + "\"; trie already contained it");
					}
				} else if (_consoleState == CONSOLE_STATE_REMOVING) {
					boolean removed = _trie.removeWord(word);
					if (removed) {
						System.out.println("[removeWord] removed \"" + word + "\" from the trie");
					} else {
						System.err.println("[removeWord] did NOT remove \"" + word + "\"; trie did NOT contain it");
					}
				} else if (_consoleState == CONSOLE_STATE_QUERYING) {
					boolean containsWord = _trie.containsWord(word);
					if (containsWord) {
						System.out.println("[containsWord] trie does contain \"" + word + "\"");
					} else {
						System.err.println("[containsWord] trie does NOT contain \"" + word + "\"");
					}
				} else {
					ASSERT(false);
				}
				_consoleBuffer = "";
			}
		} else if (keyAnyPressed) {
			if ('A' <= keyLastPressed && keyLastPressed <= 'Z') {
				_consoleBuffer += (char) ('a' + (keyLastPressed - 'A'));
			}
		}
	}

	static void _HW09_drawConsole() {
		double canvasHeight = _canvas_get_height_World();

		String prefix = null;
		Color color = null;
		if (_consoleState == CONSOLE_STATE_ADDING) {
			prefix = "+";
			color = new Color(0.0, 0.6, 0.0);
		} else if (_consoleState == CONSOLE_STATE_REMOVING) {
			prefix = "-";
			color = new Color(0.8, 0.0, 0.0);
		} else if (_consoleState == CONSOLE_STATE_QUERYING) {
			prefix = "?";
			color = new Color(0.0, 0.0, 0.8);
		} else {
			ASSERT(false);
		}
		drawString(prefix + ' ' + _consoleBuffer, 0.5, canvasHeight - 0.5, color, 24);
	}


	//////////
	// TRIE///
	//////////

	static Trie _trie;


}

Home Docs Glow HelpHours LectureRecordings

Provide feedback

Saved searches

Use saved searches to filter your results more quickly