=-------------------------------------------------------------------- appendix to "GEB" FAQ: self-doc pangrams or "Sallowsgrams" Newsgroups: alt.fan.hofstadter, alt.tanaka-tomoyuki, rec.puzzles ;;; TANAKA Tomoyuki ("Mr. Tanaka" or "Tomoyuki") ;;; ;;; e-mail: tanaka@cs.indiana.edu =-------------------------------------------------------------------- contents: -- preface: pangrams, Sallows, self-doc -- from archive -- Sallowsgrams in many tongues ---- English ---- Dutch ---- French ---- Japanese -- a Japanese version by TT -- the English version by TT -- two French versions by Frederic Marchal -- other variations -- pangram program in Perl -- pangram program in C =-------------------------------------------------------------------- -- preface: pangrams, Sallows, self-doc a "pangrams" usually refers to sentences such as "A quick brown fox jumps over the lazy dog." i'm not talking about those. this file is about self-doc pangrams, or "Sallowsgrams". =-------------------------------------------------------------------- -- from archive http://www.cs.uu.nl/wais/html/na-faq/puzzles-archive-language-part2.html http://einstein.et.tudelft.nl/~arlet/puzzles/sol.cgi/language/english/ self.ref/self.ref.letters |-------------------------------------------------------------------- | ==> language/english/self.ref/self.ref.letters.p <== | Construct a true sentence of the form: "This sentence contains _ | a's, _ b's, _ c's, ...," where the numbers filling in the blanks | are spelled out. | | ==> language/english/self.ref/self.ref.letters.s <== | A little history of the problem, culled from the pages of | _Metamagical Themas_, Hofstadter's collection of his _Scientific | American_ columns. First mention of it is in the Jan. '82 | column. Lee Sallows opened the field with a sentence that began | "Only the fool would take trouble to verify that his sentence | was composed of ten a's ...." etc. | | Then in the addendum to the Jan.'83 column on viral sentences, | Hofstadter quotes Sallows describing his Pangram Machine, "a | clock-driven cascade of sixteen Johnson-counters," to tackle the | problem. An early success was: | | "This pangram tallies five a's, one b, one c, two d's, | twenty- eight e's, eight f's, six g's, eight h's, | thirteen i's, one j, one k, three l's, two m's, eighteen | n's, fifteen o's, two p's, one q, seven r's, twenty-five | s's, twenty-two t's, four u's, four v's, nine w's, two | x's, four y's, and one z." | | Sallows wagered ten guilders that no-one could create a perfect | self- documenting sentence beginning, "This computer-generated | pangram contains ...." within ten years. | | It was solved very quickly, after Sallows' challenge appeared in | Dewdney's Oct. '84 SA column. Larry Tesler solved it by a | method Hofstadter calls "Robinsonizing," which involves starting | with an arbitrary set of values for each letter, getting the | true values when the sentence is made, and plugging the new | values back in, making a feedback loop. Eventually, you can zero | in on a set of values that work. Tesler's sentence: | | This computer-generated pangram contains six a's, one b, | three c's, three d's, thirty-seven e's, six f's, three | g's, nine h's, twelve i's, one j, one k, two l's, three | m's, twenty-two n's, thirteen o's, three p's, one q, | fourteen r's, twenty-nine s's, twenty-four t's, five | u's, six v's, seven w's, four x's, five y's, and one z. | | The method of solution (called "Robinsonizing," after the | logician Raphael Robinson) is as follows: | | 1) Fix the count of a's. | 2) Fix the count of b's. | 3) Fix the count of c's. | ... | 26) Fix the count of z's. | Then, if the sentence is still wrong, go back to step 1. | | Most attempts will fall into long loops (what Hofstadter calls | attractive orbits), but with a good computer program, it's not | too hard to find a Robinsonizing sequence that zeros in on a | fixed set of values. | | The February and May 1992 _Word Ways_ have articles on this | subject, titled "In Quest of a Pangram, (Part 1)" by Lee | Sallows. It tells of his search for a self-referential pangram | of the form, "This pangram contains _ a's, ..., and one z." (He | built special hardware to search for them.) Two such pangrams | given in the article are: | | This pangram lists four a's, one b, one c, two d's, | twenty-nine e's, eight f's, three g's, five h's, eleven i's, | one j, one k, three l's, two m's twenty-two n's, fifteen o's, | two p's, one q, seven r's, twenty-six s's, nineteen t's, four | u's, five v's, nine w's, two x's, four y's, and one z. | | This pangram contains four a's, one b, two c's, one d, thirty | e's, six f's, five g's, seven h's, eleven i's, one j, one k, | two l's, two m's eighteen n's, fifteen o's, two p's, one q, | five r's, twenty-seven s's, eighteen t's, two u's, seven v's, | eight w's, two x's, three y's, & one z. | | It also contains one in Dutch by Rudy Kousbroek: | | Dit pangram bevat vijf a's, twee b's, twee c's, drie d's, | zesenveertig e's, vijf f's, vier g's, twee h's, vijftien i's, | vier j's, een k, twee l's, twee m's, zeventien n's, een o, | twee p's, een q, zeven r's, vierentwintig s's, zestien t's, | een u, elf v's, acht w's, een x, een y, and zes z's. | | References: | Dewdney, A.K. Scientific American, Oct. 1984, pp 18-22. | Sallows, L.C.F. Abacus, Vol.2, No.3, Spring 1985, pp 22-40. | Sallows, L.C.F. Word Ways, Feb. & May 1992 | Hofstadter, D. Scientific American, Jan. 1982, pp 12-17. | |-------------------------------------------------------------------- | ==> language/english/self.ref/self.ref.numbers.p <== | What true sentence has the form: "There are _ 0's, _ 1's, _ 2's, | ..., in this sentence"? The "'s" can be dropped if there is | only one of any number. | | ==> language/english/self.ref/self.ref.numbers.s <== | There are 1 0, 7 1's, 3 2's, 2 3's, 1 4, 1 5, 1 6, 2 7's, 1 8, | and 1 9 in this sentence. | | There are 1 0, 11 1's, 2 2's, 1 3, 1 4, 1 5, 1 6, 1 7, 1 8, | and 1 9 in this sentence. | |-------------------------------------------------------------------- | ==> language/english/self.ref/self.ref.words.p <== | What sentence describes its own word, syllable and letter count? | | ==> language/english/self.ref/self.ref.words.s <== | This sentence contains ten words, eighteen syllables, and | sixty-four letters. =-------------------------------------------------------------------- -- Sallowsgrams in many tongues (i haven't seen all the relevant articles yet.) ---- English i've seen many in English. ---- Dutch a Dutch one is in this file. MT (Metamag Themas) contains a Dutch one by Sallows. (?) ---- French MT contains a near-miss in French by (Bob) French. (?) two French variations in this file. ---- Japanese a Jp version is described below. (i have not seen a German version yet.) =-------------------------------------------------------------------- -- a Japanese version by TT a Japanese version of such a pangram ("Tomoyuki's self-documenting sentence") is in the Jp translation of "Metamagical Themas". it's in the Lisper-translator Takeuchi's afterword. this Jp version is simpler than the one above. it took me 3 hours or so, and i did it by solving linear equations --- stuff i could do when i was in junior high school. my sentence looks like this: ko no BUN SHOU ni ha "ko" ga 2 KAI, "no" ga ... where uppercase BUN SHOU KAI are in Kanji. if it were solely in KANA, the sentence would be a bit more complex than an English one. it's possible to spell out the numbers in Japanese, as ... "ha" ha ni-juu-hati KAI, ... but it looks so weird that it's not worth the trouble. =-------------------------------------------------------------------- -- the English version by TT Tanaka Tomoyuki found this sentence which consists of exactly three `T's, ten `a's, one `b', six `c's, four `d's, forty-one `e's, fourteen `f's, three `g's, thirteen `h's, twenty-one `i's, one `j', three `k's, five `l's, four `m's, twenty-nine `n's, twenty-four `o's, four `p's, two `q's, sixteen `r's, forty `s's, thirty-one `t's, nine `u's, five `v's, eight `w's, six `x's, twelve `y's, one `z', six hyphens, thirty commas, twenty-seven pairs of single quotes, and a final period. the idea behind of this sentence is: why stop at 26 chars a-z? let's count all the commas and hyphens too. (this idea naturally led to distinguishing between the uppercase `T' and the lowercase `t'.) the English version above was a nice programming project. i first tried Robisonizing (see "Metamagical Themas") and found that searches go into loops. then i tried some kind of an exhaustive search, waited for a day or something and then realized that the search takes a few thousand years to complete. then i tried using a Genetic Algorithm which didn't work. and finally i found an article (in Mathmatical Intelligencer?) by Letaw that described what i call "randomized Robisonizing", and that worked and gave me two pangrams. (it's too bad i didn't discover randomized Robisonizing. i didn't even re-discover it.) randomized Robisonizing: let's say in candidate(N) which includes the phrase "... eight `a's ..." actually contains 13 `a's. then in candidate(N+1) you pick a random number R between 8 and 13 (inclusive) and put the phrase "... [R] `a's ...". you do this for each letter. in randomized Robisonizing you don't have to check for loops. =-------------------------------------------------------------------- -- two French versions by Frederic Marchal In article <35a47e1c.5986202@news.worldnet.fr>, Frederic Marchal wrote: > >>>-- >>>Cette signature contient trois a, six c, huit d, dix-sept e, deux f, >>>deux g, deux h, treize i, dix n, cinq o, deux p, cinq q, cinq r, six >>>s, douze t, onze u, un v, neuf x et quatre z. >> >> nice. but this isn't a pangram! > >It's not a bug, it's a feature! :-) It tries instead to be the >shortest self-documenting (French) signature. > >In the same vein, here is the shortest self-documenting French >sentence (enumeration, actually) I could find : > >Trois a, trois c, trois d, neuf e, quatre f, deux h, neuf i, six n, >quatre o, deux p, cinq q, six r, sept s, huit t, neuf u, cinq x. =-------------------------------------------------------------------- -- other variations [i'll write this later.] =-------------------------------------------------------------------- -- pangram program in Perl TT's Perl Pangram Program found this sentence which contains exactly seven`a's, one`b', five`c's, three`d's, thirty-eight`e's, thirteen`f's, four`g's, eleven`h's, fifteen`i's, one`j', one`k', four`l's, three`m's, twenty-three`n's, fifteen`o's, four`p's, one`q', sixteen`r's, thirty-one`s's, twenty-four`t's, seven`u's, six`v's, four`w's, five`x's, six`y's, and one`z'. (i ran 6 processes and one of them found this in about 10 minutes. it's all luck.) this below was the 1st Perl program i've written. thanks to Keith Lim for posting these 3 lines, which inspired me to write this program. $sentence="[PUT YOUR SENTENCE HERE]"; for(split(//,$sentence)) { $count{$_}++; } for(sort keys %count) { print"$_"."=".$count{$_}."\n"; } please tell me how to clean it up (e.g. get rid of goto). and how to make it faster (without sacrificing readability). i reliaze that all this runtime throway CONSing (heap allocation + gc) is unnecessary. i wrote this mainly in the hope that others will modify it to find self-doc pangrams (Sallowsgrams) in other languages thanks to Alejandros Diamandidis for comments. i'll prob. include his suggestions later. #-------------------------------------------------------------------- # TTPPP: TT's Perl Pangram Program # # rrob.pl --- randomized Robisonizing (by Letaw) # --- just counts the 26 chars A-Z #-------------------------------------------------------------------- $debug = 0; # $tenKblip = 1; $test_with_Sallows = 0; # from "Metamagical Themas", p.69 # snum --- spelled number $snum[1] = "one" ; $snum[2] = "two" ; $snum[3] = "three" ; $snum[4] = "four" ; $snum[5] = "five" ; $snum[6] = "six" ; $snum[7] = "seven" ; $snum[8] = "eight" ; $snum[9] = "nine" ; $snum[10] = "ten" ; $snum[11] = "eleven" ; $snum[12] = "twelve" ; $snum[13] = "thirteen" ; $snum[14] = "fourteen" ; $snum[15] = "fifteen" ; $snum[16] = "sixteen" ; $snum[17] = "seventeen" ; $snum[18] = "eighteen" ; $snum[19] = "nineteen" ; $snum[20] = "twenty" ; $snum[30] = "thirty" ; $snum[40] = "forty" ; $snum[50] = "fifty" ; $snum[60] = "sixty" ; $snum[70] = "seventy" ; $snum[80] = "eighty" ; $snum[90] = "ninety" ; $AtoZ = "abcdefghijklmnopqrstuvwxyz" ; @AtoZsplit = split(//,$AtoZ) ; #-------------------------------------------------------------------- # the seed must be in all lower case. for( @AtoZsplit ) { $c{$_} = 0 } if ( $test_with_Sallows ) { $seed="this pangram tallies and "; @c1{ @AtoZsplit } = (5, 1, 1, 2, 28, 8, 6, 8, 13, 1, 1, 3, 2, 18, 15, 2, 1, 7, 25, 22, 4, 4, 9, 2, 4, 1) ; } else { $seed="this pangram tallies and "; $seed="this sentence contains exactly and "; $seed="tt's perl pangram program found this sentence which contains exactly and "; for( @AtoZsplit ) { $c1{$_} = 1 } } print "seed = `" . $seed . "'\n" ; for( @AtoZsplit ) { print"$_"."=".$c1{$_}." "; } print "\n"; while (1) { for (1 .. 10000) { # given: C1 (which will yield S), C is cleared $s = $seed; for( @AtoZsplit ) { $s = $s . sn( $c1{$_} ) . "`" . $_ . "'" . s_if_plural( $c1{$_} ) } for(split(//,$s)) { $c{$_}++; } for( @AtoZsplit ) { if ( $c{$_} != $c1{$_} ) {goto keeplooping ; } } print "-----------------------------------------\n"; print " the pangram found \n"; for( @AtoZsplit ) { print"$_"."=".$c{$_}." "; } print "\n".$s."\n" ; exit 0; keeplooping: if ( $debug ) { print "-----------------------------------------\n"; print $s."\n" ; print "-----------------------------------------"; print " TALLY OF THE ABOVE IS \n"; for( @AtoZsplit ) { print"$_"."=".$c{$_}." "; } print "\n"; } for( @AtoZsplit ) { $c1{$_} = rpick( $c1{$_} , $c{$_} ) ; $c{$_} = 0 ; } if ( $debug ) { print "-----------------------------------------"; print " NEW TALLY IS \n"; for( @AtoZsplit ) { print"$_"."=".$c1{$_}." "; } print "\n"; } } # if ( $tenKblip == 1 ) { print "10K blip \n" } print "10K blip \n" ; srand(); # unnecessary? } sub s_if_plural { if ( $_[0] >= 2 ) { "s, " } else { ", " } } sub sn { $x = $_[0] ; if ($x >= 100) { print "must be 99 or less" ; exit 1; } if ($x <= 20) { $snum[ $x ] } else { $tens = int($x / 10) * 10 ; $snum[ $tens ] ."-". $snum[ $x - $tens ] } } sub rpick { $x = $_[0] ; $y = $_[1] ; if ( $x > $y ) { $old_x = $x ; $x = $y ; $y = $old_x ; } # rand(0) is screwed if ( $x == $y ) { $x } else { int( $x + rand( $y - $x ) + 0.5) } } =-------------------------------------------------------------------- -- pangram program in C i'm translating the Perl program into C. (sorry, no plans of a Fortran version.) the current snapshot is attached below (about 80% done). what's this "floating point exception" i'm getting now? (i see --- "devide by zero") i may not work on this program for a few weeks. if someone finishes writing it, that'd be cool. /* #-------------------------------------------------------------------- # rrob.c by TT --- randomized Robisonizing (by Letaw) # --- just counts the 26 chars A-Z #-------------------------------------------------------------------- */ int test_with_Sallows = 0; /* from "Metamagical Themas", p.69 */ /* sn --- spelled number */ char* sn1s[] = { "", "one" , "two" , "three" , "four" , "five" , "six" , "seven" , "eight" , "nine" , "ten" , "eleven" , "twelve" , "thirteen" , "fourteen" , "fifteen" , "sixteen" , "seventeen" , "eighteen" , "nineteen" , "twenty" }; char* sn10s[] = { "", "", "", "thirty" , "forty" , "fifty" , "sixty" , "seventy" , "eighty" , "ninety" } ; int c[26], c1[26], seedc[26]; char* seed; main() { int i, loopvar; /* the seed must be in all lower case. */ seed="tt's c pangram program found this sentence \ which contains exactly and "; for (i=0; i<26; i++) c1[i] = 1 ; printf("seed = `%s'\n", seed); print_c1(); init_seedc(); printf("seed count:\n"); print_seedc(); while(1) { for (loopvar=0; i<10000; loopvar++) { for (i=0; i<26; i++) c[i] = seedc[i] ; /* given: C1 (which will yield S), C == SeedC */ for (i=0; i<26; i++) { add_num_to_c(c1[i]); c[i]++; add1s_to_c_if_plural(c1[i]); } for (i=0; i<26; i++) if (c[i] != c1[i]) goto keeplooping; println(); printf( "the pangram found \n"); print_c1(); print_s_from_c1(); exit(); keeplooping: println(); print_s_from_c1(); printf( "TALLY OF THE ABOVE IS \n"); print_c(); printf( "before rpick \n"); for (i=0; i<26; i++) c1[i] = rpick( c[i], c1[i] ); printf( "after rpick \n"); } printf("10K blip \n"); srand(); } } int rpick(x, y) { int old_x; if (x > y) { old_x = x; x = y; y = old_x; } return ((int) (x + rand() % (y-x) + 0.5)); } print_s_from_c1() { int i, x, tens, ones; printf("%s\n", seed); for (i=0; i<26; i++) { x = c1[i]; if (x <= 20) { printf("%s", sn1s[x]); } else { tens = x / 10 ; ones = x % 10 ; printf("%s-%s", sn10s[tens], sn1s[ones]); } printf("`%c'", 'a'+i); if (x>=2) printf("s"); printf(", "); } printf("\n"); } println() { printf("--------------------------------------------------------\n"); } add_num_to_c(x) { int i, ones, tens; char* cp; if (x <= 20) { for (cp = sn1s[x]; (*cp) > 0; cp++) c[ (*cp) - 'a']++ ; } else { tens = x / 10 ; ones = x % 10 ; for (cp = sn10s[tens]; (*cp) > 0; cp++) c[ (*cp) - 'a']++ ; for (cp = sn1s[ones]; (*cp) > 0; cp++) c[ (*cp) - 'a']++ ; } } add1s_to_c_if_plural(x) { #ifdef DEBUG if (x <= 0) { printf("bug\n"); exit(1); } #endif if (x >= 2) c[ 's' - 'a']++ ; } print_c() { int i; for (i=0; i<26; i++) printf("%c=%d ", 'a'+i, c[i] ); printf("\n"); } print_c1() { int i; for (i=0; i<26; i++) printf("%c=%d ", 'a'+i, c1[i] ); printf("\n"); } print_seedc() { int i; for (i=0; i<26; i++) printf("%c=%d ", 'a'+i, seedc[i] ); printf("\n"); } init_seedc() { int i; char* cp; for (i=0; i<26; i++) seedc[i] = 0 ; for (cp = seed; (*cp) > 0; cp++) if ( 'a'<=(*cp) && (*cp) <= 'z') { seedc[ (*cp) - 'a']++ ; #ifdef DEBUG printf("`%c' cur count: %d \n", *cp, seedc[ (*cp) - 'a'] ); #endif } } =-------------------------------------------------------------------- END