CS310 Goblin

Overview

Goblins are notorious for both their thieving skills and their riddle games. For example, some days when you came home there's a goblin stealing your ramen noodles. If you catch him at it, he always challenges you to a riddle game for your dinner. Unfortunately, goblins like to cheat! Heres a typical evening discussion:

Goblin: I'm thinking of a six letter word from this list: peanut, slower, packet, faster, parcel. You can guess one letter at a time and Ill tell you if its in the word and where. You can only guess wrong twice.

< The goblin isn't really thinking of a word, hes going to change his answer to win the game. >

You: "l"
Goblin: Nope! One wrong guess left!

< The goblin looked at his list and decided there were more words without an "l". So he's going to use one of the following: peanut, packet, faster >

You: "p"
Goblin: Yeah, there's a "p" here: p - - - - -

< The goblin looked at his list of words and decided that there were more words with p in the first position. So he's going to use one of the following: peanut, packet >

You: "n"
Goblin: Nope! I win! Ramen is mine now.

< The goblin disappears in a puff of smoke with your dinner. >

You have so much fun playing this game that you decide to recreate the experience for others. This is the game we're going to be creating.

Differences between the scenario above and the game you are writing:

1. The virtual goblin will be using a much larger list (he'll be reading words in from a provided dictionary).
2. The virtual goblin will say very specific things during the game which you must make match the sample runs for full credit.
3. In "debug mode" youll be able to see the goblins current list of words, but usually you wont have that.
4. The number of letters in the word and the number of guesses will be set by a command line argument.
5. For simplicity, the goblin will not use words which contain duplicate letters.

Note: In the below examples, user input is shown in green highlight and underlined.

Sample Run

> java GoblinGame ..\dictionary-mini.txt 6 2
Goblin says "Guess a letter": l
Goblin says "No dice! 1 wrong guesses left..."
Goblin says "Guess a letter": p
Goblin says "Yeah, yeah, it's like this: p-----"
Goblin says "Guess a letter": n
Goblin says "No dice! 0 wrong guesses left..."
Goblin says "I win! I was thinking of the word 'packet'
Your stuff is all mine... I'll come back for more soon!"

Sample Run Debug Mode

> java GoblinGame ..\dictionary-mini.txt 6 2 debug
--------------------------------------------------
peanut, slower, packet, faster, parcel
--------------------------------------------------
Goblin says "Guess a letter": l
Goblin says "No dice! 1 wrong guesses left..."
--------------------------------------------------
peanut, packet, faster
--------------------------------------------------
Goblin says "Guess a letter": p
Goblin says "Yeah, yeah, it's like this: p-----"
--------------------------------------------------
peanut, packet
--------------------------------------------------
Goblin says "Guess a letter": n
Goblin says "No dice! 0 wrong guesses left..."
--------------------------------------------------
packet
--------------------------------------------------
Goblin says "I win! I was thinking of the word 'packet'
Your stuff is all mine... I'll come back for more soon!"

The Goblin Algorithm

Let's say the goblin has the following words in his dictionary ( dictionary-mini.txt ):

one | three | peanut | pepper | slower | packet | pagoda | faster | papers | parcel

And he plays a game where there are 6 letters and 2 guesses. He will choose the following highlighted words:

one | three | peanute | pepper | slower | packet | pagoda | faster | papers | parcel

He will not choose "one" or three because they are not of length 6. He will not choose pepper, pagoda, or papers because they each have duplicate letters.

This is why you see the following in Sample Run Debug Mode:

> java GoblinGame ..\dictionary-mini.txt 6 2 debug
--------------------------------------------------
peanut, slower, packet, faster, parcel
--------------------------------------------------

Let's say the user guesses "l":

Goblin says "Guess a letter": l

Now the Goblin wants to cheat. He's not really thinking of a word, hes thinking of winning the game! The goblin will partition his current list of words (peanut, slower, packet, faster, parcel) into seven categories (number of letters + 1).

Now he will choose the biggest "partition", in this case 'Words without the letter l'. So hell respond:

Goblin says "No dice! 1 wrong guesses left..."

But he can't be caught cheating, so he can only use words from that partition later (peanut, packet, faster). So when the user guesses "p":

Goblin says "Guess a letter": p

The goblin does this partition:

And now he picks partition 'Words with the letter "l" in position 1' and says:

Goblin says "Yeah, yeah, it's like this: p-----"

Now that you understand more about the game, let's look at another sample run:

> java GoblinGame ..\dictionary-mini.txt 6 10
Goblin says "Guess a letter": p
Goblin says "Yeah, yeah, it's like this: p-----"
Goblin says "Guess a letter": a
Goblin says "Yeah, yeah, it's like this: pa----"
Goblin says "Guess a letter": e
Goblin says "Yeah, yeah, it's like this: pa--e-"
Goblin says "Guess a letter": e
Goblin says "You already guessed: p, a, e
Guess a new letter": t
Goblin says "No dice! 9 wrong guesses left..."
Goblin says "Guess a letter": c
Goblin says "Yeah, yeah, it's like this: pa-ce-"
Goblin says "Guess a letter": t
Goblin says "You already guessed: p, a, e, t, c
Guess a new letter": banana
Goblin says "One letter! Guess a single letter":
Goblin says "One letter! Guess a single letter": l
Goblin says "Yeah, yeah, it's like this: pa-cel"
Goblin says "Guess a letter": m
Goblin says "No dice! 8 wrong guesses left..."
Goblin says "Guess a letter": 8
Goblin says "No dice! 7 wrong guesses left..."
Goblin says "Guess a letter": r
Goblin says "Yeah, yeah, it's like this: parcel"
Goblin says "You win... here's your stuff. But I'll get you next time!"

Notes:

• The goblin says different things for wrong, duplicate, and invalid guesses.
• Only wrong guesses (not duplicate or invalid guesses) will count down the number of remaining guesses.
• When the user picked "t" there were two even partitions (no words and t at the end), the goblin prefers to tell the user he's wrong (and count down), or if there is a tie for letter position, he chooses the earliest letter position.
• If the Goblin wins, he always claims he was thinking of the first word in his remaining list.
• Words should always remain sorted in the order they appear in the dictionary file (not necessarily in alphabetical order). You should not need to really do anything to have this happen, but it will affect your debug output and the goblin's final words if you mix them up somehow and youll lose points

Requirements

An overview of the requirements are listed below, please see the grading rubric for more details.

• Implementing the classes - You will need to implement required classes and provided template files.
• Big-O - The template files provided to you contains instructions on the REQUIRED Big-O runtime for many methods. Your implementation of those methods should NOT have a higher Big-O.
• Style - You must follow the coding and conventions specified by the style checker.
• JavaDocs - You are required to write JavaDoc comments for all the required classes and methods.

Input Format(s)

Dictionary files will contain one word per line and only words with alphabetical characters (a-z) and only lower case letters. Two dictionaries have been provided ( dictionary.txt is a Scrabble dictionary, dictionary- mini.txt is for use in debugging and for showing sample runs). You may assume the given dictionary is correctly formatted for this assignment.

Implementation/Classes

This project will be built using a number of classes representing the component pieces of the project. Here we provide a description of these classes. Template files are provided for each class in the project folder and these contain further comments and additional details.

BetterArray< T > (BetterArray.java): This class represents a generic collection of objects in an array whose capacity can grow and shrink as needed. It supports the usual operations of adding and removing objects including add() and delete() . Check the included template file for all required methods and their corresponding big-O requirements. The capacity of a BetterArray may change as items are added or removed and the following rules must be followed in your implementation:

• The default initial capacity is fixed to be 2 if not specified.
• When you need to add an item and there is not enough space, grow the array to double its capacity.
• When you delete an item and the size falls below 1/4 of the capacity, shrink the array to half of its capacity.

Goblin (Goblin.java): This class implements the goblin game. It must use BetterArray objects for storage and you are not permitted to use any arrays anywhere in this file (the main method which interacts with args[] has already been implemented). You will be implementing a typical "game loop" structure:

• init() - this sets everything up for the game
• step() - this plays one round of the game (one guess by the user and goblin response)
  • bestPartition() - this is a helper method for step() which chooses subset of the goblin's current list based on the users guess
• finish() - this presents the goblin's final choice

The class define multiple methods corresponding to those steps. Some methods include partial implementations to provide a starting point for you. Check the included template file for all required methods and their big-O requirements.

GoblinGame (GoblinGame.java): This class runs the actual game loop and is fully provided (do not edit).