Solving Problems: Anagrams/JumblesBrute force? SillyAnagrams.javaQuantifying brute force for anagramsToward a faster anagram finderAnother anagram methodOO and JavaUnderstandable, extensible?Find all anagrams in dictionaryAnaword objects with optionsAnagram: Using NormalizersNormalizer hierarchyCompSci 100E7.1Solving Problems: Anagrams/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?CompSci 100E7.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]);}CompSci 100E7.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 (investment?) saves in the long runWhat properties do words share that are anagrams?CompSci 100E7.4Toward a faster anagram finderWords that are anagrams have the same letters; use a letter fingerprint or signature/histogram 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?CompSci 100E7.5Another 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, but 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?CompSci 100E7.6OO 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++oException is +, this works for strings, but can't change itWhen string needed, automatically call toString()CompSci 100E7.7Understandable, 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();}CompSci 100E7.8Find 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 co mpar able/sortableMust implement the java.lang.Comparable inte rfaceoReturn negative, zero, positive number depending on less than, equal to, or greater thanoWhat is method signature?CompSci 100E7.9Anaword 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?oIf 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?CompSci 100E7.10Anagram: 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?Cut 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!CompSci 100E7.11Normalizer hierarchyAnaword objects normalize themselvesWhere does the normalizer come from?oPassed in at construction timeoObtained from normalizer factoryoOther 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...