2.1) In this lab, you will implement a “guess your name” game where the computer

Question

2.1) In this lab, you will implement a “guess your name” game where the computer finds a name in a sorted list of names. When run, the program will look like this:

This program tries to guess your last name, but you have to give some hints.

Does your name come before "MYERSCOUGH" in the dictionary? (Y/N) Y

Does your name come before "ISENBERG" in the dictionary? (Y/N) Y

Does your name come before "DIMAGGIO" in the dictionary? (Y/N) N

Does your name come before "GALLUP" in the dictionary? (Y/N) N

. . .

Is your name "HORSTMANN"? (Y/N) Y

Start out with a program that reads all names from the "last names" file at http://www2.census.gov/topics/ genealogy/1990surnames/dist.all.last. Discard the statistical information. Sort the names, using Collections.sort.

Use this code outline (Note: you'll have to figure out exactly what to import here...):

public class NameGuesser

{

private ArrayList<String> lastNames = new ArrayList<String>();

public void readNames() throws IOException, MalformedURLException

{

URL url = new URL("http://www2.census.gov/topics/genealogy/1990surnames/ dist.all.last");

Scanner in = new Scanner(url.openStream());

. . .

}

}

Add the code for reading all names and sorting them.

2.2) Now you will implement the method that guesses the name, called guessName.

At the beginning of the search, set low to 0 and high to the maximum index of the names list. Set mid to the average of low and high, then ask the user if the name comes before the list entry at index mid. Depending on the answer, update low or high. If low == high, ask if the name matches.

What is the code for your guessName method?

2.3) How many entries does your names list have? How many guesses does your program need to make until it gives up? (Use big-Oh for your answer.)

Explanation / Answer

Comments and output attached

2.1) & 2.2)

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;

/**
*
* @author prmsh
*/
public class GuessGame {
public static ArrayList<String> readNames(){
ArrayList<String> names = new ArrayList<String>();
File file = new File("names.txt");
try {
Scanner sc = new Scanner(file);
while (sc.hasNextLine()) {
String name = sc.nextLine();
names.add(name);
}
sc.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
}
return names;
}
  
public static int guessName(ArrayList<String> names){
//setting low and high values
int low = 0, high = names.size()-1, totalGuessses = 0;
Scanner sc = new Scanner(System.in);
while(true){//checking for guess index
totalGuessses++;
System.out.println("Does your name come before "+ names.get(high)+" in the dictionary? y or n");
String choice = sc.nextLine();
if(choice.equals("y")){
high = (low+high)/2;
}
else{
low = (low+high)/2;
}
if(totalGuessses == names.size()){
break;
}
}
return totalGuessses;
}
public static void main(String args[]) {
//array list declared
ArrayList<String> names = new ArrayList<String>();
//reading names from file
names = readNames();
int guesses = guessName(names);
System.out.println("Total Guesses needed: "+guesses);
}
}

----------------------------------------------------------------------------------------------------------------------

2.3)

Names have entries === arraylist.size()

Guesses needed is O(n/2) .. since at every step.. half of the elements are get reduced.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.