import java.util.*;
public class RandomSentences {
public static void main(String[] args) {
String [] articles = {"a","the","my","your"};
String [] adjectives = {"playful","red"};
String [] nouns = {"dog","frog","bug"};
String [] actions = {"is walking","is jumping","is flying by"};
// write code to construct random sentences out of
// the words above
}
}
You will need to use a random number generator. Make sure to write your code in such a way that if you add or delete some of the words in the arrays, your program should still work correctly.
The comparison is case-sensitive. The two given arrays must remain unchanged. Since you don't know in advance how many common strings the two arrays have, you need to create the new array the size of the shorter of the two given arrays (why do you need at least that many? and why is this enough?). At the end you need to find the number of non-null elements of the new array.
What is the efficiency of your algorithm?
Here is some code to get you started. The common strings in this
example are "I","do","not","like".
public class CommonStrings {
public static void main(String[] args) {
String [] array1 = {"I","do","not","like","green","eggs","and",
"ham"};
String [] array2 = {"I","do","not","like","it","Sam","I","am"};
}
}
About Spanish alphabet. As it turns out, Spanish alphabet is not
clearly defined. Most sources list 29 letters in the alphabet:
26 the same as in English alphabet, and the extra letters ch, ll, and
ñ (if your browser doesn't show it, it's n with the ~ on
top). Some also include rr as a separate letter. See a
page at about.com and a
page at allinfo-about.com for more details. However, according to
this
source, for the alphabetizing purpose the two-symbol letters ch
and ll would be each considered as two separate letters. In other words,
chorizo comes before comida in alphabetical
order (if ch was a letter of its own, everything that starts with ch
would be after everything that starts with just a c). Therefore, for
our purposes we will use an alphabet of 27 letters, with the only
additional letter ñ which comes right after n. For simplicity we will
write this letter as ~, for instance "Al niño" will be
written as "Al ni~o".
Our sample vocabulary comes from this Glossary of Spanish Food. We will only use words that can be translated by a single word.
Below is the file TestSpanish with the data for testing your code.
import java.util.*;
public class TestSpanish {
public static void main(String [] args) {
// the words are stored as pairs: an english word followed by
// its spanish translation.
// ~ stands for ñ (n with tilde)
String [] words = { "almonds", "almendras", "anchovy", "anchoa",
"apple", "manzana", "artichoke", "alcachofa",
"asparagus", "esparrago", "bacon", "beicon",
"banana", "platano", "basil", "albahaca",
"batter", "albardilla", "bayleaf", "laurel",
"blackberry", "mora", "brandy", "co~ac",
"bread", "pan", "butter", "mantequilla",
"cabbage", "col", "cake", "pastel",
"carrot", "zanahoria", "celery", "apio",
"cheese", "queso", "chestnut", "casta~o",
"chicken", "pollo", "chocolate", "chocolate",
"cider", "sidra", "cinnamon", "canela",
"clams", "almejas", "coconut", "coco",
"dill", "eneldo", "dogfish", "cazon",
"dough", "masa", "duck", "pato", "egg", "huevo",
"eggplant", "berenjena", "endives", "endibias",
"fennel", "hinojo", "fish", "pescado",
"flour", "harina", "garlic", "ajo",
"gelatine", "gelatina", "ginger", "jengibre",
"goose", "ganso", "grape", "uva",
"grapefruit", "pomelo", "guava", "guayaba",
"haddock", "abadejo", "ham", "jamon",
"herb", "hierba", "herring", "arenque",
"honey", "miel", "jam", "mermelada",
"kidney", "ri~on", "lamb", "cordero",
"leeks", "puerros", "lemon", "limon",
"lentils", "lentejas", "lettuce", "lechuga",
"mint", "menta", "molasses", "melazaf",
"mushrooms", "champi~ones", "mussels", "mejillones",
"mustard", "mostaza", "nectarine", "nectarina",
"noodles", "tallarines", "onion", "cebolla",
"olive", "aceituna", "pancake", "crepe",
"paprika", "pimenton", "parsley", "perejil",
"partridge", "perdiz", "pasta", "pasta",
"pepper", "pimienta", "pizza", "pizza",
"pineapple", "pi~a", "plum", "ciruela",
"potatoes", "patatas", "prawns", "gambas",
"quail", "codorniz", "rabbit", "conejo",
"radish", "rabano", "ribs", "costillas",
"rice", "arroz", "rosemary", "romero",
"saffron", "azafran", "sage", "salvia",
"salmon", "salmon", "salt", "sal", "sauce", "salsa",
"sherry", "jerez", "snail", "caracol",
"spaghetti", "espaguetis", "squid", "calamar",
"thyme", "tomillo", "tomatoes", "tomates",
"trout", "trucha", "tuna", "atun",
"vinegar", "vinagre", "watercress", "berro",
"yolks", "yemas"
};
// Randomize the data: generate two indices at random
// between 0 and length/2 and switch the pairs
// Repeat this 100 times.
// printing the words, each pair on one line
// tabs are for formatting
for (int i = 0; i < words.length/2; ++i) {
String tabs = "\t";
if (words[2*i].length() < 8) {
tabs = "\t\t";
}
System.out.println(words[2*i] + tabs + words[2*i + 1]);
}
// create a Spanish-English dictionary
// and English-Spanish dictionary
// go through the array, inserting an english word
// into the English-Spanish dictionary,
// and inserting the spanish word into the
// Spanish-English dictionary.
// Set the cross-references between the two words
// using setTranslation()
// print both dictionaries using inOrder traversal
// print the height of both dictionaries
// test the search method of both dictionaries
// Part 6 of the problem: create another two dictionaries
// setting the root to the middle of the first three elements.
// Note that the middle element will be different for
// the Spanish and the English dictionaries. Make sure to set
// the translation right for the three first elements.
// insert the rest of the elements into the dictionaries
// test the dictionaries by printing them out and
// by searching for a translation.
// print out the height of the dictionaries,
// compare them to the heights of the first two dictionaries
}
}
{"almonds", "almendras", "artichoke", "alcachofa",
"apple", "manzana", "anchovy", "anchoa",
"asparagus", "esparrago", "bacon", "beicon", //other elements unchanged
Each node class also has a comparison method. The method compares the word in the node to another string. The returned value is computed similar to the value of compareTo() method: it's negative if the word in the node comes before the parameter string, a 0 if they are equal, and a positive integer if the parameter string comes before the word in the node. The comparison method of the SpanishWordNode class compares the two strings according to the spanish alphabet. You don't need to understand the details of the method.
Each comparison method has a static counter. There is a static printCounter() method in each Node class and a reset() method for the counter. Below is the code of the two node classes:
public class EnglishWordNode {
private String word;
private SpanishWordNode translation;
private EnglishWordNode left;
private EnglishWordNode right;
private static int comparisonCounter = 0;
public int compareEnglish(String theOtherWord) {
comparisonCounter++;
return getWord().compareToIgnoreCase(theOtherWord);
}
public static void printCounter() {
System.out.println("English dictionary: " + comparisonCounter +
" comparisons");
}
public static void resetCounter() {
comparisonCounter = 0;
}
}
import java.text.*;
public class SpanishWordNode {
private String word;
private EnglishWordNode translation;
private SpanishWordNode left;
private SpanishWordNode right;
private static int comparisonCounter = 0;
public int compareSpanish(String theOtherWord) {
comparisonCounter++;
String spanishRules =
("< a,A < b,B < c,C " +
"< d,D < e,E < f,F " +
"< g,G < h,H < i,I < j,J < k,K < l,L " +
"< m,M < n,N " +
"< '~' " +
"< o,O < p,P < q,Q < r,R " +
"< s,S < t,T < u,U < v,V < w,W < x,X " +
"< y,Y < z,Z");
try {
RuleBasedCollator spanishCollator = new
RuleBasedCollator(spanishRules);
return spanishCollator.compare(getWord(),theOtherWord);
} catch (ParseException e){
System.out.println(e);
System.exit(0);
return 0;
}
}
public static void printCounter() {
System.out.println("Spanish dictionary: " + comparisonCounter +
" comparisons");
}
public static void resetCounter() {
comparisonCounter = 0;
}
}
EnglishWordNode class:
public EnglishWordNode(String theword) the
constructor, initializes the word,
public String getWord() returns the word,
public void setTranslation(SpanishWordNode trans)
sets the translation to the SpanishWordNode,
public SpanishWordNode getTranslation() returns the
translation,
public EnglishWordNode getLeft(), public EnglishWordNode
getRight() return references to the left and the right child of
the node, respectively. Returns null if there is no such node.
public void setLeft(EnglishWordNode theleft), public void
setRight(EnglishWordNode theright) set the left and the right
node references. No new nodes are created.
public EnglishDictionary() the constructor.
public EnglishWordNode getRoot() returns the root of
the tree.
public EnglishWordNode search(String englishWord)
Searches for the string in the dictionary. Returns the reference to
the node that contains the string if it's found, null if the string is
not found.
public EnglishWordNode insert(String englishWord)
Inserts the string englishWord into the tree. Returns the reference to
the node created for the string, null if the string already appears in
the tree.
Test your code by printing out the two dictionaries using InOrder() method, they should appear alphabetically. Print out the heights of both dictionaries. Test the search method by searching for a word and printing out its translation for several test examples (for english-to-spanish and spanish-to-english translation).
Print out the number of comparisons for each dictionary (before the searches).
Important: the middle spanish word among the first three can be different from the middle one among the first three english ones. Make sure to set the translation right for the first three nodes.
Print out the trees to check the ordering. Print out the height of the tree and the number of comparisons.
Compare the dictionaries created using the first element as the root to dictionaries where the root is chosen as the middle one among the first three. Compare the heights and the numbers of comparisons. Which one is more efficient?
Testing note: while you are debugging your program, it might be
helpful to use the same order of words on every run. Putting an
integer parameter in the constructor for the random number generator
allows you to fix the "random" numbers: Random r = new
Random(20);
Changing the number changes the sequence to another fixed one. Removing it makes the sequence different every time you run the program.