Pete's Log: starting the day out right
Entry #653, (Coding, Hacking, & CS stuff)(posted when I was 22 years old.)
La la la. Three hours of sleep is awesome. It gives me a uniquely different perspective on stuff. And it makes mountain dew taste good.
So for numerical today, I grabbed a copy of the 2000 Mid-Central European Regional Programming Contest problem set. Worked out the basics of one of the problems during class. A good way to spend my time. It was kind of an interesting one. I'll quote some of it:
Ouroboros is a mythical snake from ancient Egypt. It has its tail in its mouth and continously devours itself.
The Ouroboros numbers are binary numbers of 2^n bits that have the property of "generating" the whole set of numbers from 0 to 2^n-1. The generation works as follows: given an Ouroboros number, we place its 2^n bits wrapped in a circle. Then we can take 2^n 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. There are 0011, 0110, 1100, and 1001. In this case, the smallest one is 0011. Here is the Ouroboros circle for 0011:
| k | 0011 | o(2,k) |
|---|---|---|
| 0 | 00 | 0 |
| 1 | 01 | 1 |
| 2 | 11 | 3 |
| 3 | 10 | 2 |
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.
So their input requirements state that the given n will be no greater than 15, so I figured I didn't have to be terribly efficient. Turns out I was wrong. I've got a working program, but it's pretty slow once n gets to be about 12 or so. So I'll have to think about this one some more. But later, I think. Now it's time to get real work done.