3. Word Puzzles and Games - UVM

1 3. Word Puzzles and GamesRobert of Computer ScienceUniversity of VermontRobert R. Snapp 20143. Word Puzzles and GamesCS 32, Fall 20141 / 271 Word GamesRiddlesLipogramsPalindromesAnagrams 2 Computational QuestionsHeuristicsTrees (and Factorial Trees)The Multiplication PrincipleEnumerating Anagrams havingnUnique SymbolsEnumerating Anagrams having Repeated Symbols3 ReferencesRobert R. Snapp 20143. Word Puzzles and GamesCS 32, Fall 20142 / 27A RiddleAs I was going to St. Ives,I met a man with seven wives,Each wife had seven sacks,Each sack had seven cats,Each cat had seven kits;Kits, cats, sacks, and wives,How many were going to St.

2 Ives?Probably only one person: the I of the R. Snapp 20143. Word Puzzles and GamesCS 32, Fall 20143 / 27A RiddleAs I was going to St. Ives,I met a man with seven wives,Each wife had seven sacks,Each sack had seven cats,Each cat had seven kits;Kits, cats, sacks, and wives,How many were going to St. Ives?Probably only one person: the I of the R. Snapp 20143. Word Puzzles and GamesCS 32, Fall 20143 / 27A LipogramGadsby was walking back from a visit down in Branton Hill smanufacturing district on a Saturday night.

3 A busy day s traffichad had its noisy run; and with not many folks in sight. HisHonor got along without having to stop to grasp a hand, or talk;for a Mayor out of City Hall is a shining mark for anypolitician. And so, coming to Broadway, a booming bass drumand sounds of singing, told of a small Salvation Army unitcarrying on amidst Broadway s night shopping , walking toward that group, saw a young girl, backtoward him, just finishing a long, soulful oration: : :(From, Ernest Vincent Wright,Gadsby, Wetzel Press, 1939; cf.)

4 Ross Eckler,Making theAlphabet Dance, St. Martin s Press, New York, 1996, pp. 2 3.)Robert R. Snapp 20143. Word Puzzles and GamesCS 32, Fall 20144 / 27 Another LipogramEnfettered, these sentences repress free speech. Thetext deletes selected letters. We see the revered exegetereject metred verse: the sestet, the tercet evenlessc nes lev es en rebels. He sets new lets cleverness exceed decent levels. He eschewsthe esteemed genres, the expected themes evenles belleslettres en prefers the perverse French esthetes:Verne, P ret, Genet, Perec hence, he pens ferventscreeds, then enters the street, where he sells these letterpressnewsletters, three cents per sheet.

5 He engendersperfect newness wherever we need fresh Christian B k, Couch House Books, Toronto, R. Snapp 20143. Word Puzzles and GamesCS 32, Fall 20145 / 27 PalindromesA man, a plan, a canal Panama!Madam, I m it a bat I saw?Rise to vote, , O Caesar, erase a , a base life defiles a bad R. Snapp 20143. Word Puzzles and GamesCS 32, Fall 20146 / 27 Anagrams: OriginsThe oldest known anagrams may have been written in 260 BC by Lycophron, aGreek poet. His poem Cassandra containstwo:The letters in the name of Ptolemy EMAIO ;are rewritten ME ITO ;which translates to made of honey.

6 The letters in the name of Arsino (Ptolemy s queen),AP INOH;are rewritten asHPA ION;which means Hera s violet. Robert R. Snapp 20143. Word Puzzles and GamesCS 32, Fall 20147 / 27 Anagrams: American PresidentsABRAHAM LINCOLN: oh, call man brain HERBERT CLARK HOOVER: the ever dark horrorHARRY S TRUMAN: rash army runtDWIGHT DAVID EISENHOWER: he did view the war doingsJAMES EARL CARTER: a rare calm jesterRONALD WILSON REAGAN: no darlings, no ERA lawGEORGE HERBERT WALKER BUSH: huge berserk rebelwarthog(cf.)

7 Ross Eckler,Making the Alphabet Dance, St. Martin s Press, New York, 1996, p. 139.)Robert R. Snapp 20143. Word Puzzles and GamesCS 32, Fall 20148 / 27 More AnagramsINCOMPREHENSIBLE:problem in ChineseSTORMY WEATHER:showery matterROCKY MOUNTAINS:o, man ski countryTHE PIANO BENCH:beneath ChopinTHE CAFETERIA:fact: I eat here.(cf. Ross Eckler,Making the Alphabet Dance, St. Martin s Press, New York, 1996,pp. 139 141.)Robert R. Snapp 20143. Word Puzzles and GamesCS 32, Fall 20149 / 27 AnagramsRobert R.

8 Snapp 20143. Word Puzzles and GamesCS 32, Fall 201410 / 27 Anagrams: Four Questions1 How doyouunscramble a jumbled word, likePUGOR?2 Can we create an algorithm (or procedure) so that anyone, even a computer canunscramble a jumbled word?3 How many anagrams ofPUGORare there? That is, in how manydifferentwayscan these five letters be rearranged as a single word?4 How many anagrams does ann-letter word have? (Do alln-letter words havethe same number of anagrams?)Robert R. Snapp 20143. Word Puzzles and GamesCS 32, Fall 201411 / 27 The Multiplication PrincipleIn general, if a construction (or process) can be represented as a sequence ofksteps, and the number of ways of performing each step is independent of anyprevious choices, and ifn1,n2,n3,: : :,nkdenote the number of ways of performingeach step, thenNDn1 n2 n3 nk;denotes the total number of different constructions (or processes).

9 This statement is calledthe multiplication number of permutations of abcd is found by settingkD4, withn1D4,n2D3,n3D2, andn1D1, henceNDn1 n2 n3 n4D4 3 2 1D4 Robert R. Snapp 20143. Word Puzzles and GamesCS 32, Fall 201412 / 27 Some Problem Solving Heuristics1If the problem is too hard, try to solve an easier problem and Conquer: Hard problems can often be broken up into pieces, whereeach piece corresponds to an easier : Sometimes it is easier to solve a more general problem a picture: Try to represent the problem as a an abstraction.

10 An abstraction is a simpler representation of theproblem we are trying to solve. Reducing the problem to an abstraction that onehas seen before often will suggest a simple R. Snapp 20143. Word Puzzles and GamesCS 32, Fall 201413 / 27 Common Abstractions1 Asetis an unordered collection of objects ( , things, symbols, concepts,labels) in which each element (or member) appears no more than left and right curly brackets,f: : :g, are used to denote a set. Thus theset of odd numbers between 0 and 10 isf1; 3; 5; 7; 9g, and the set of suits in astandard deck of playing cards isf~;|; ;}g.