ISourceCode

Make the frequent cases fast and the rare case correct

The Cuckoo’s Egg or The Morris Number Sequence

The look-and-say sequence is the sequence of integers beginning as follows:

1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, …

It is also popularly known as the Morris Number Sequence, after cryptographer Robert Morris and the puzzle is sometimes referred to as the Cuckoo’s Egg from a description of Morris in Clifford Stoll’s book The Cuckoo’s Egg – Wikipedia

The Cuckoo’s Egg: Tracking a Spy Through the Maze of Computer Espionage is a 1989 book written by Clifford Stoll. It is his first-person account of the hunt for a computer cracker who broke into a computer at the Lawrence Berkeley National Laboratory (LBL) – Wikipedia entry about the book.

Excerpt from goodreads.com
Cliff Stoll was an astronomer turned systems manager at Lawrence Berkeley Lab when a 75-cent accounting error alerted him to the presence of an unauthorized users on his system. The hacker’s code name was “Hunter”– a mystery invader hiding inside a twisting electronic labyrinth, breaking into U.S. computer systems and stealing sensitive military and security information. Stoll began a one-man hunt of his own, spying on the spy– and plunging into an incredible international probe that finally gained the attention of top U.S. counter-intelligence agents. “The Cuckoo’s Egg” is his wild and suspenseful true story– a year of deception, broken codes, satellites, missile bases and the ultimate sting operation– and how one ingenious American trapped a spy ring paid in cash and cocaine, and reporting to the KGB

The sequence is mentioned in chapter 48 of the book, The problem was given by Morris to Stoll and Stoll later in his book wrote about it. It took him 6 months to solve the problem.

The look and say sequence is defined as follows. Start with any string of digits as the first element in the sequence. Each subsequent element is defined from the previous one by “verbally” describing the previous element. For example,
* 1 is read off as “one 1” or 11.
* 11 is read off as “two 1s” or 21.
* 21 is read off as “one 2, then one 1” or 1211.
* 1211 is read off as “one 1, then one 2, then two 1s” or 111221.
* 111221 is read off as “three 1s, then two 2s, then one 1” or 312211.

You can check more on this in Stoll’s official page .

One of the property is no digits other than 1, 2, and 3 appear in the sequence, unless the seed number contains such a digit or a run of more than three of the same digit

Conway’s Constant::

If Ln denotes the number of digits of the n-th member of the sequence, then

is known as the Conway’s constant.

Below is a java program that generates the next morris number for a input string sequence.

import java.util.*;   
  
public class CuckooEgg 
{   
	public static void main(String[] args) 
	{   
	        Scanner input = new Scanner(System.in);   
          
        	char newline = '\n';   
        	int count = 0;   
        	char temp = '\n';   
        	int newLineFlag = 0;   
               		 
        	StringBuffer sb = new StringBuffer();   
        	int singleLetter = 0;
		System.out.println("Enter the string of numbers");   
		String str = input.nextLine();   
               
		for(int i = 0; i < str.length(); i++)   
        	{   
            		temp = str.charAt(i);   
                	if(newLineFlag == 0)   
                	{   
                    		newline = temp;   
                    		count = 1;   
                    		newLineFlag = 1;   
                    		if(i == str.length()-1)   
                        		singleLetter = 1;   
                    		continue;   
                	}	   
                   
                	if(temp == newline)   
                	{   
                    		count++;   
                	}
			else  
                	{   
                    		sb.append(count);   
                    		sb.append(newline);   
                    		newline = temp;   
                    		count = 1;   
                	}      
                   
                	if(i == str.length()-1)   
                	{   
                    		sb.append(count);   
                    		sb.append(newline);   
                	}   
            	}   
               
            	if(singleLetter == 1)   
            	{   
			System.out.println("The Next string in Morris sequence is");
                	System.out.println("1" + temp);   
            	}
	    	else  
            	{   
			System.out.println("The Next string in Morris sequence is");
                	System.out.println(sb.toString());     
            	}   
	}   
  
}  

OUTPUT:
labuser@ubuntu:~$ java CuckooEgg
Enter the string of numbers
1
The Next string in Morris sequence is
11

labuser@ubuntu:~$ java CuckooEgg
Enter the string of numbers
9999
The Next string in Morris sequence is
49

labuser@ubuntu:~$ java CuckooEgg
Enter the string of numbers
11111
The Next string in Morris sequence is
51

labuser@ubuntu:~$ java CuckooEgg
Enter the string of numbers
12345
The Next string in Morris sequence is
1112131415

This is a link to a look-and-say generator

Thanks for Reading !

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: