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
1 1
2 1
1 2 1 1
1 1 1 2 2 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 self-referencing 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 self-referencing sentence". Melvin, said, "Do that; it is a good warm up. I got into this and looked up a self-descriptive 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 self-descriptive array (string) has the correct tally of i's in array element i. For example, in Pascal you can write:

A: ARRAY [0..9] OF
 INTEGER = (6, 2, 1, 0, 0, 0, 1, 0, 0, 0);

This is self-descriptive because there are six zeros, two ones, one two, one six and none (zero) of any other digit. The nice part about self-descriptive arrays is that they are language- and representation-independent. 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 self-descriptive array, which does not depend on digits:

X: ARRAY [0..16] OF
 INTEGER= (13, 2, 1, 0, 0, 0, 0, 0,
              0, 0, 0, 0, 0, 1, 0, 0, 0);

"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 self-descriptive.

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 co-descriptive 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 self-descriptive string. For example, the pair of arrays, A and B are co-descriptive:

A: ARRAY [0..9] OF INTEGER =
 (6, 3, 0, 0, 0, 0, 0, 1, 0, 0);
B: ARRAY [0..9] OF INTEGER =
 (7, 1, 0, 1, 0, 0, 1, 0, 0, 0);

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 co-descriptive.

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 co-descriptive 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.

F1:ARRAY [0..9] OF INTEGER =
    (6, 7, 3, 0, 0, 1, 1, 1, 0, 1);
F2:ARRAY [0..9] OF INTEGER =
    (7, 6, 2, 1, 0, 1, 1, 1, 0, 1);
F3:ARRAY [0..9] OF INTEGER =
    (5, 9, 1, 1, 0, 0, 2, 2, 0, 0);

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
Write a Boolean function, which will return TRUE if the two dimensional array given as a parameter has rows which meet the Fibonacci loop condition. To make life easier, let us assume that the array parameter is always made up of exactly three rows.

Extra Credit

There is one array which has two identical rows which meets the Fibonacci loop condition. This array is:

F:ARRAY [1..3, 0..9] OF INTEGER= (
   (6, 6, 2, 2, 0, 2, 0, 2, 0, 0),
   (7, 3, 5, 1, 0, 1, 2, 1, 0, 0),
   (7, 3, 5, 1, 0, 1, 2, 1, 0, 0)
);

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@i-programmer.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

Mathematica's Google Aptitude

Hofstadter, Douglas METAMAGICAL THEMAS (1985), ISBN: 978-0465045662. Section 1, Chapters 1-3.

McKay, Michael and Waterman, Michael, "Self-Descriptive Strings", THE MATHEMATICAL GAZETTE, Vol. 66, pages 1-2 (1982). (download pdf)

Look and Say Sequence (Wikipedia)

Sallows, Lee and Eijkhout, Victor L., "Co-Descriptive Strings", THE MATHEMATICAL GAZETTE, Vol. 70, pages 1-10 (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:

Towers Of Hanoi Mutants

Programmer Puzzle - Hermit Boxes

Jigsaw Puzzles and The MacMahon Squares

Vertex Coverings And The Cool Kids Problem

The Best Sub-Array Problem

Self-Descriptive Arrays

Taxicab Geometry Puzzle

Merkles and Social Engineering

Three Warehouses Puzzle

The Post Production Problem

Elevator Puzzle

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

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

<ASIN:0465045669>

<ASIN:0691143420>