Ouroborous Snake !

Once I made a programming problem set for In-House programming contest and gave this problem , at my University taken from ACM. The problem statement is:

Ouroboros is a mythical snake from ancient Egypt. It has its tail in its mouth and continously devoursitself. The Ouroboros numbers are binary numbers of 2n bits that have the property of “generating” the whole set of numbers from 0 to 2n-1. The generation works as follows: given an Ouroboros number, we place its 2n bits wrapped in a circle. Then, we can take 2n groups of n bits starting each time with the next bit in the circle. Such circles are called Ouroboros circles for the number n. We will work only with the smallest Ouroboros number for each n.

Example: for n = 2, there are only four Ouroboros numbers. These are 0011, 0110, 1100 and 1001. In this case, the smallest one is 0011. Here is the Ouroboros circle for 0011:

1.jpeg                            2.jpeg

The table describes the function o(n,k) which calculates the k-th number in the Ouroboros circle of the smallest Ouroboros number of size n. This function is what your program should compute.

Input

The input consists of several test cases. For each test case, there will be a line containing two integers n and k (1 <= n <= 8; 0 < k < 2n). The end of the input file is indicated by a line containing two zeros. Do not process that line.

Output

For each test case, output o(n ,k) on a line by itself. 

Sample Input
2 0
2 1
3 7
4 14
0 0 

Sample Output
0
1
4
12

I recently solved this problem in my office. This costed me an exciting half an hour to solve it and code it perfectly. The real problem I faced is as soon as the size of n grows ( in terms of powers of 2), the computaion becomes too much and hence slow and solution comes too late. But the interesting part is the algorithm. Any ways interested people can solve this and I am sure this will interest them.

I, Haroon

Advertisements
  1. farid
    November 7, 2006 at 5:05 am

    i need the code please

  2. lucky
    February 12, 2008 at 6:13 am

    Please post the code sir.

  3. lucky
    February 12, 2008 at 6:14 am

    Please post the code.

  4. Man
    May 21, 2008 at 7:25 am

    Please post the code

  5. good
    May 24, 2008 at 5:29 pm

    Please mail to me the code~

  6. jaehunha
    May 27, 2008 at 11:04 am

    please mail to me the code

  7. bleemzard
    May 27, 2008 at 11:04 am

    plz mail to me this code sir!

  8. hyo gook
    May 27, 2008 at 11:38 am

    plz mail to me this code sir!

  9. cotolengo_RS
    May 26, 2009 at 8:32 pm

    please mail me the code sir!

  10. July 17, 2009 at 3:59 pm

    Please mail me the code sir

  1. No trackbacks yet.

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: