SelfDescriptive Arrays 
Written by Joe Celko 
Put on your thinking cap for another set of conundrums that will exercise your coding skills. This time Melvin Frammis introduces his junior partner Bugsy Cottman to some classic number puzzles that can be solved with arrays. Joe Celko is best known as the database expert who writes books on SQL, data and databases. But before that, he was an honest developer obsessed with finding good algorithms and clean code. This puzzle is one of the Sharpen Your Coding Skills series which introduces Melvin and Bugsy and the rest of the programming staff at International Storm Door and Software write beautiful code in whatever programming language they have to hand. Another encounter with Melvin and Bugsy, characters created by Joe Celko to challenge you to sharpen your coding skills. "Hey, Mel! Look what I found!" said Bugsy Cottman. "It is an old Google job application they handed out a few years ago" Bugsy dropped what looked like a standardized test booklet. It was entitled Google Labs Aptitude Test. "Yeah, I remember this!" laughed Melvin Frammis. "You could get fired for having a copy on your desk where was working in 2004. My boss was thought that anyone who passed the test automatically had a job at Google." Melvin picked up the booklet and began turning pages. "Hey, I missed #3 and could kick myself. Here look at it!: 1 What's the next line?
"I do not see it." said Bugsy. Then Jane Smith from Marketing walked by. "Don't see it; say it! You guys do math and I do words." She then put her finger on each line: "You start with one 1 in the first line, so that gives you the second line. The third line is two 1's ; the fourth line is one 2 and one 1; the fifth line is three 1's and two 2's; so the next line has to be 312211! Just look at it." "It is a selfreferencing kind of thing." said Melvin turning to his key board and typing. "Try this sentence that describes itself" This sentences contains 1 '0', 11 '1's, 2 '2's, 1 '3', 1 '4', 1 '5', 1 '6', 1 '7', 1 '8' and 1 '9'. Bugsy laughed and said, " I need to try to write one of those selfreferencing sentence". Melvin, said, "Do that; it is a good warm up. I got into this and looked up a selfdescriptive strings. There was a good article by McKay and Waterman in The Mathematical Gazette. It is a good programming exercise, because you can write it with arrays."
"What is an array?" asked Jane. Melvin and Bugsy looked at her with blank faces. "Oh. Nerd Stuff. I am going back to my office now." said Jane as she left. Melvin continues, "A selfdescriptive array (string) has the correct tally of i's in array element i. For example, in Pascal you can write:
This is selfdescriptive because there are six zeros, two ones, one two, one six and none (zero) of any other digit. The nice part about selfdescriptive arrays is that they are language and representationindependent. This gets us out of the realm of language and back to Nerd Stuff !" Jane turned around a stuck out her tongue, laughed and left the room. Melvin laughed and added " Here is an example of a longer selfdescriptive array, which does not depend on digits:
"I am going to play with this.:" said Bugsy. Now Readers, you can do the same with these problems.
Problem One Write a Boolean function, which will return TRUE if the array is selfdescriptive. Hint: You can get a much faster program if you do your research. The authors of the original paper give a unique general formula for such arrays, where the array has n:(n > 6) elements. Not to be out done, Sallows and Eijkhout came up with codescriptive arrays in a later issue of The Mathematical Gazette. This is a pair of arrays, each of which describes the other, in the same manner as a selfdescriptive string. For example, the pair of arrays, A and B are codescriptive:
Illustrations from xkcd a webcomic of romance,sarcasm, math, and language
Problem Two Write a Boolean function, which will return TRUE if the two arrays given as parameters are codescriptive. Hint: You can get a much faster program if you do your research again. Sallows and Eijkhout also give a unique general formula for such array pairs. But it is more fun to try a brute force approach at first. Before you ask about triplets, quadruplets, etc. of descriptive arrays, these authors proved that for n:(n > 8) there are only codescriptive pairs. Gee, just when we were starting to have fun, too. However, there are Fibonacci loops. The name comes from the famous Fibonacci series, and this structure is best described by an example.
Array F1 describes the union of the elements of arrays F2 and F3; in F2 and F3 there are six zeros, seven ones, and so forth. Likewise, array F2 describes both F1 and F3 and array F3 describes both F1 and F2. We have an advantage in most computer languages in that we can represent the set of multiple one dimensional arrays as a single two dimensional array. This will make addressing elements much easier, and let you generalize your program later. Problem Three Extra Credit There is one array which has two identical rows which meets the Fibonacci loop condition. This array is:
Is there an array with all three rows identical, which meets the Fibonacci loop condition. If so, what is it? Where are the answers? Melvin has given you some hints that you can follow up with the references below but this time we've not supplied the answers. If you would like to send in solutions to some or all of the puzzles in any language (email editor@iprogrammer.info), we'll publish the best. Joe Celko is best known as the database expert who writes books on SQL, data and databases. But before that, he was an honest developer obsessed with finding good algorithms and clean code.
Resources and References Hofstadter, Douglas METAMAGICAL THEMAS (1985), ISBN: 9780465045662. Section 1, Chapters 13. McKay, Michael and Waterman, Michael, "SelfDescriptive Strings", THE MATHEMATICAL GAZETTE, Vol. 66, pages 12 (1982). (download pdf) Look and Say Sequence (Wikipedia) Sallows, Lee and Eijkhout, Victor L., "CoDescriptive Strings", THE MATHEMATICAL GAZETTE, Vol. 70, pages 110 (1986).
Look And Say Numbers And Conway's Constant
Other Articles In Sharpen Your Coding Skills If you've not already met experienced developer Melvin Frammis and his junior programmer sidekick, Bugsy Cottman you'll find they were initially introduced in the Elevator Puzzle, the first in Joe Celko's series of Sharpen Your Coding Skills and they have posed us further challenges ever since: Programmer Puzzle  Hermit Boxes Jigsaw Puzzles and The MacMahon Squares Vertex Coverings And The Cool Kids Problem Merkles and Social Engineering To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.
Comments
or email your comment to: comments@iprogrammer.info
<ASIN:0465045669> <ASIN:0691143420>
