There's a guy named Tomek (I'd be surprised if there isn't something puzzley about that) who has 1337 (and this one too) friends on Facebook. Now he wants them to join in a big circle of hand-holding togetherness to celebrate the launch of Karmic Koala. (You Windows people throw house parties, we hold hands and look up at the sky. It's just the way we do it. (And yes, we are cooler!)
So, while on one of these weird hand-holding orgies, Tomek decides that they should bring an element of fun into the ritual (about time somebody did that!) and he starts playing a game of 7UP (no, this event is not sponsored or endorsed in any way by the popular brand of carbonated beverage!) where people count up from 1 up to infinity.
Now there's a twist to Tomek's game of 7UP. Counting goes upward continuously clockwise from whoever calls out 1 to begin the game. So, if person 1 calls out 1:
person 2 calls out 2
person 3 calls out 3
and so on...
till person 7 calls out 7
and person 6 calls out 8
person 5 calls out 9
and so on...
till person 1337 at the end of the circle (does that make any sense?) calls out 14
person 1 calls out 15
person 2 calls out 16
So, to end the counting and summarize the rules of the game:
- Each person calls out a number. The next person calls out the next number. The number to be called out is always incremented by one.
- The direction of counting starts clockwise from 1 to 1337.
- Direction reverses when a number that is:
- divisible by 7 (eg 7, 14...)
- contains the digit 7 (17, 27, 455677221, 7000)
So, those are the rules of the game.
Now, Tomek's a weirdo, (or we wouldn't be having this problem), so he wants us to write a program that can tell him where he has to stand if he wants to call out his favourite number.
So, if you were Tomek, what would your favourite number be? That's what we're writing this program for.
I came across this problem on the CodeChef website initially. And at the time I attempted to solve it, nobody had been able to submit a successful solution owing to length of time allotted for calculation a very generous ONE SECOND.
It does help if you look at that as ONE THOUSAND MILLISECONDS. A little.
So, I went to work on it. It sounded simple enough to write, but little did I realise that the number of elements to be processed would be HUGE if I merely brute forced this.
Imagine processing 100,000,000 elements checking each for divisibility and presence of 7! That's not good enough. And the running times proved it. When Tomek's favourite number is 100,000,000,000 we have around 3.5 minutes processing time. And to think that the size of the input can go up to 10100! We have something serious on our hands.
So, the question now is, could we optimize the algorithms used to determine divisibility and presence of 7 further or should we simply observe the state of the program over a period and see if there are any patterns that we can exploit? Which is simpler? Or more effective?
The answers to those questions are:
the first approach one is simpler, since there are plenty of well documented algorithms for that. Wikipedia has plenty of them. I used that one instead of using the standard % 7 == 0 test, since it increases the time required to process as the count goes up. But the first approach can only help so much.
The second approach brings maximum effectiveness since skipping over a bunch of elements which you know will anyway not contribute to the final answer eliminates the divisibility/presence tests associated with them.
So, your problem input size is probably reduced in size by half. And after much thought I decided to take a raw dump of the program as it worked. And ended up with a HUGE file after 3 test cases.
Will have to figure out the quirks and optimize.
The source for the program is attached. Documentation is something I'd love to do some more work on, but a work in progress is just that, it's a work in progress. This is the part where most programmer's like to spend time trying to play with code rather than document, so, I've tried explaining wherever I can. Links are also there to the pages where I got the algorithms from.
Will be posting a set of links here when I find the time.
How To Hurry Tomek's Ass Up (aka possible optimizations):
1. Who cares about the 70s, or the 700s, or the 70000000000000000000000000000000000000000s!
aka the remove the 7s way
Last night, as I was thinking about ways to optimize this, I realised that the processing required for complete blocks of the input could simply be eliminated.
Inputs of the form:
viz. any range of concurrent numbers known to contain 7 in the same place. For example:
70 - 79
Here 10 numbers can be eliminated by simply adding 10 the count and keeping the direction of count the same. The counter does not change since the number of reversals is even as in:
caller 1 at 70
caller 1337 at 71
caller 1 at 72
caller 1337 at 73
and so on...
caller 1337 at 79
caller 1 at 80
caller 2 at 81
caller 1 at 82
and so on...
So, in effect, the person to call out the first number in the series is the person who counts the last number of the series. The direction of counting remains the same.
For larger inputs 7000-7999
caller 1 at 7000
caller 1337 at 7001
caller 1337 at 7999
caller 1 at 8000
1000 inputs skipped.
So, skip formula:
((10place of 7)) elements skipped and added to count. So the larger the input, the larger the skip.
After running some timing tests, this is what I found:
Test run without the remove 7s optimizations with an input of about 10,000,000,000 ran for 1 minute and 49 seconds.
And this is with the optimization:
1 minute and 12 seconds.
There is an improvement, definitely.
So, for such large inputs, we have a 1/3rd cut in running time.
While not as large an improvement as I expected, I am pleased to say that something worked.