Question 2: Finding the best Scrabble word with Recursion Scrabble is a game in
ID: 3899435 • Letter: Q
Question
Question 2: Finding the best Scrabble word with Recursion
Scrabble is a game in which players construct words from random letters, building on words already played. Each
letter has an associated point value and the aim is to collect more points than your opponent. Please see
https:
//en.wikipedia.org/wiki/Scrabble
for an overview if you are unfamiliar with the game.
You will write a program that allows a user to enter 7 letters (representing the letter tiles they hold), plus an 8th
letter (representing the letter they would like to use on the board).
Your program will output all valid words that can be made from the entered letters, as well as list the point value
for each of the words, and then print the word that has the highest point value.
Dictionary class
In order to know whether you have generated a valid word, rst create a dictionary class.
The le words
alpha.txt" (obtained from
https://github.com/dwyl/english-words
) contains 370099 words
in the English language. You will load this le into an instance of the Dictionary class.
Store your dictionary in a basic array (i.e. not ArrayList) of Strings.
Data members of the Dictionary class will be the array, and the number of words in the dictionary.
The constructor for your Dictionary class should accept an integer that speci es the size of the array. The
constructor will then create an array of appropriate size.
Write a public method
fill(String filename, int num)
that will read in
num
words from a given le and
store the words in order in the array. If the array already contains words, add the words in the given le to
the existing array (checking that you are not adding duplicates). When reading in the words, verify that the
array is large enough to hold the speci ed number of words, and enlarge the array if necessary. In order to use
the recursive binary search below, your words must be stored in alphabetical order.
Write a public
search(String word)
method that will use a
recursive binary search
to search the dictionary
for the given word. If the given word appears in the dictionary, return true. If the given word is not found,
return false.
Letters Class
Create a class that holds the value of each letter/tile in the game.
(Note the similarity to question 1. It is suggested
that you reuse your Node and Linked List classes, with slight modi cations if desired, and add the required method
below.)
The value of each letter is as follows:
Letter
Points
Letter
Points
Letter
Points
A
1
J
8
S
1
B
3
K
5
T
1
C
3
L
1
U
1
D
2
M
3
V
4
E
1
N
1
W
4
F
4
O
1
X
8
G
2
P
3
Y
4
H
4
Q
10
Z
10
I
1
R
1
Include a
getValue(char letter)
method that returns the points value (i.e. an integer) for the given lett
Explanation / Answer
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.Arrays;
import java.util.ArrayList;
import java.io.*;
import java.util.*;
public class Scrabble {
private List<Letters> letterSets;
private String[] arr_dictionary;
private String[] arr_words;
private int num_of_words_read = 0;
public Scrabble(int size) {
letterSets = Arrays.asList(
new Letters(0, "*"),
new Letters(1, "aeioulnrst"),
new Letters(2, "dg"),
new Letters(3, "bcmp"),
new Letters(4, "fhvwy"),
new Letters(5, "k"),
new Letters(8, "jx"),
new Letters(10, "qz")
);
arr_dictionary = new String[size];
arr_words = new String [370099];
}
public static void main(String[] args) throws FileNotFoundException {
Scrabble scrabble = new Scrabble(370099);
scrabble.fill("words_alpha.txt", 370099);
// take user input
char[] chars = "abcdefg".toCharArray();
int len = 7;
char start_with = 'a';
scrabble.iterate(chars, len, new char[len], 0, start_with);
for(int i=0; i<scrabble.num_of_words_read; i++) {
if(scrabble.bsearch(scrabble.arr_words[i], scrabble.arr_dictionary, 0, scrabble.arr_dictionary.length) != -1)
System.out.println("'" + scrabble.arr_words[i] + "' is worth "
+ scrabble.getWordScore(scrabble.arr_words[i]) + " points");
}
}
public int bsearch(String word, String [] words, int a, int b) {
if(b <= a)
return -1;
if(b - a == 1)
return words[a].equals(word) ? a : -1;
int pivot = (a + b)/2;
if(word.compareTo(words[pivot]) < 0) {
return bsearch(word, words, 0, pivot);
} else if(word.compareTo(words[pivot]) > 0) {
return bsearch(word, words, pivot, b);
}
return pivot;
}
public int getWordScore(String word) {
int finalScore = 0;
for (char letter : word.toCharArray()) {
finalScore += getLetterScore(letter);
}
return finalScore;
}
public int getLetterScore(char letter) {
for (Letters letterSet : letterSets) {
if (letterSet.containsLetter(letter)) {
return letterSet.getValue();
}
}
throw new IllegalArgumentException("'" + letter + "' is not a valid scrabble letter");
}
public void fill(String filename, int num) throws FileNotFoundException {
File file_o = new File(filename);
Scanner sc = new Scanner(file_o);
int i=0;
while (sc.hasNextLine()) {
String str = sc.nextLine();
if(i<num) {
arr_dictionary[i] = str;
i++;
} else
break;
}
}
public void iterate(char[] chars, int len, char[] build, int pos, char start_with) {
if (pos == len) {
String word = new String(build);
if (word.matches("^" + start_with + ".*$")) {
arr_words[num_of_words_read] = word;
num_of_words_read ++;
}
return;
}
for (int i = 0; i < chars.length; i++) {
build[pos] = chars[i];
iterate(chars, len, build, pos + 1, start_with);
}
}
public static final class Letters {
private int score;
private List<Character> letters;
public Letters(int score, String letters) {
this.score = score;
this.letters = new ArrayList<Character>(letters.length());
for (char letter : letters.toCharArray()) {
this.letters.add(letter);
}
}
public int getValue() {
return score;
}
public boolean containsLetter(Character letter) {
return letters.contains(letter);
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.