Anagrams/JumblesBrute force? SillyAnagrams.javaQuantifying brute force for anagramsJohn von NeumannToward a faster anagram finderAnother anagram methodOO and JavaUnderstandable, extensible?Find all anagrams in dictionaryAnaword objects with optionsAnagram: Using NormalizersNormalizer hierarchyCPS 1003.1Anagrams/JumblesHow do humans solve puzzles like that at www.jumble.comIs it important to get computers to solve similar puzzles? Reasons?Should computers mimic humans in puzzle-solving, game playing, etc.? Lessons from chess?nelir,nelri, neilr, neirl, nerli, neril, nleir, nleri, nlier, nlire, nlrei, nlrie, nielr, nierl, niler, nilre, nirel, … lenir, lenri, leinr, leirn, lerni, lerin, linerWhat’s the problem here?CPS 1003.2Brute force? SillyAnagrams.javapublic String[] allAnagrams(String s) { int anaCount = factorial(s.length()); Set anagrams = new TreeSet(); ArrayList list = new ArrayList(); for(int k=0; k < s.length(); k++){ list.add(s.substring(k,k+1)); } while (anagrams.size() != anaCount){ Collections.shuffle(list); anagrams.add(listToString(list)); } return (String[]) anagrams.toArray(new String[0]);}CPS 1003.3Quantifying brute force for anagramsAll anagrams of "compute" takes average of 1 second over 20 trials. How long will "computer" take? Why?What is worst case time?What is best case time?We’re willing to do some pre-processing to make the time to find anagrams quickerOften find that some initialization/up-front time or cost saves in the long runWhat properties do words share that are anagrams?CPS 1003.4John von Neumann“Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.”“There's no sense in being precise when you don't even know what you're talking about. ““There are two kinds of people in the world: Johnny von Neumann and the rest of us.”Eugene Wigner, Noble PhysicistCPS 1003.5Toward a faster anagram finderWords that are anagrams have the same letters; use a letter fingerpr int or sig nature/hi s togram to help find anagramsCount how many times each letter occurs:“teacher” 1 0 1 0 2 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0“cheater” 1 0 1 0 2 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0Store words, but use fingerprint for comparison when searching for an anagramHow to compare fingerprints using .equals()How to compare fingerprints using .compareTo()How do we make client programmers unaware of fingerprints? Should we do this?CPS 1003.6Another anagram methodInstead of fingerprint/histogram idea, use sorted form of word“gable” and “bagel” both yield “abegl”Anagrams share same sorted formSimilarities/differences to histogram/fingerprint idea?Both use canonical or normal/normalized formNormalized form used for comparison, not for printingWhen should this normal form be created?When is one method preferred over the other?Big words, little words? Different alphabets? DNA vs English?CPS 1003.7OO and JavaWe’ll use an adapter or wrapper class called Anaword instead of StringClients can treat Anaword objects like strings, but the objects are better suited for finding anagrams than stringsThe Anaword for “bear” prints as “bear” but compares to other Anaword objects as 11001000000000000100000000In Java change behavior with .toString() and .equals()No overloaded operators as in C++•Exception is +, this works for strings, but can't change itWhen string needed, automatically call toString()CPS 1003.8Understandable, extensible?The code does things simply, but isn't very OO. Why is simple sometimes better? Why is it worse?void printAll(Anaword[] list, Anaword target){ System.out.print("anagrams of "+target+": "); for(int k=0; k < list.length; k++){ if (target.equals(list[k])) { System.out.print(list[k]); } } System.out.println();}CPS 1003.9Find all anagrams in dictionaryIf we sort the dictionary what will happen to the anagrams?capitol optical topicaldanger gander garden rangedlameness maleness nameless salesmenHow can we overload .equals()?Look at "danger" or 1001101000000100010….How can we sort with Collections.sort or Arrays.sortElements sorted must be comparable/sortableMust implement the java.lang.Comparable interface•Return negative, zero, positive number depending on less than, equal to, or greater than•What is method signature?CPS 1003.10Anaword objects with optionsCan we use different canonical forms in different contexts?Could have Anaword, FingerPrintAnaword, SortAnawordWhat possible issues arise? What behavior is different in subclasses?•If there’s no difference in behavior, don’t have subclassesAlternative, make canonical/normalize method a classTurn a function/idea into a class, then let the class vary to encapsulate different methodsNormalization done at construction time or laterWhere is normalizer object created? When?CPS 1003.11Anagram: Using NormalizersHow can we normalize an Anaword object differently?Call normalize explicitly on all Anaword objectsHave Anaword objects normalize themselvesAdvantages? Disadvantages?If Anaword objects normalize themselves, how can we experiment with different normalization techniques?Gut and paste. Problems? Versions? Saved code?What about using save-as and several .java files?What about deciding at runtime on normalization?We need inheritance!CPS 1003.12Normalizer hierarchyAnaword objects normalize themselvesWhere does the normalizer come from?•Passed in at construction time•Obtained from normalizer factory•Other approaches?How is Normalizer used?Normalizer is conceptually an interfaceDifferent implementations of the interface have different behavior (guts) but same skin (sort
View Full Document
Unlocking...