Comment Feed for Switching our Christmas tree bulbs (Posts on Channel 8)

Re: Switching our Christmas tree bulbs

Jose — Wed, 26 Dec 2007 23:37:02 GMT

Just for curiosity, I coded both solution on Matlab and measured the performance of both algorithms (for 365 bulbs). The first one took 0.019566 seconds to complete. The second one (aka, the optimized version ;-) ) took exactly 0.000344 seconds. Maybe not a big deal for 365 bulbs but as you said, if we think bigger the difference is huge!

Keep the puzzles coming ;-) Happy Holidays!

Re: Re: Re: Re: Re: Re: Switching our Christmas tree bulbs

Miguel — Wed, 26 Dec 2007 18:47:46 GMT

That's true, hehe... My first solution was very similar to yours, then I tried to improve it and took a paper and a pen, I was trying to extract a rule to determine the amount of divisors of a given number. In this problem, we will have ON at the end all those bulbs tagged with a number that has an odd amount of divisors (whatever they are).

In most cases, a number has an even number of divisors, because they are grouped in multiplications.

For instance, the number 50:

1x50; 2x25; and 5x10;

We have 3 multiplications, then, we have 6 divisors.

The perfect squares have an integer square root, so, we have an even number of multiplication factors but one of those multiplications is formed by only one number mutiplied by itself. Then, a perfect square will always have an odd number of divisors, and will remain ON at the end of this problem :-)

Consider 100:

1x100 (we should switch the bulb on day 1 and 100)

2x50 (two more swtchings)

4x25 (two more)

5x20 (two more)

10x10 (one more, the square root)

Number 100 has 9 divisors.

Tomorrow a new puzzle, cheers! :-)

Re: Re: Re: Re: Re: Switching our Christmas tree bulbs

sriram — Wed, 26 Dec 2007 18:25:37 GMT

I couldn't have thought of the squares the first time around... it struck me only after u asked me to list all the bulbs that glow (which is when i actually saw the numbers).

algorithms is an interesting topic indeed.

Happy holidays & happy new year :)

Re: Re: Re: Re: Switching our Christmas tree bulbs

Miguel — Wed, 26 Dec 2007 15:37:41 GMT

That is much better folk :-)

So, the basic solution could be something like this:

int i=1;

while(i*i<=limit){

bulbsOn[i]=i*i;

i++;

}

This gives you a sqrt(n) complexity. You will only have 10 steps for 100 bulbs, 1000 for 1,000,000 bulbs...

What about a more efficient solution? Tip: Dynamic programming ;-)

And, in conclusion: Which is the moral of this problem?

You, like I did the first time and most of people trying to solve this problem, have tried to code before trying to find the optimal approach for the problem.

A very wise friend of mine said one time: "When you have a hammer, everything seems a nail to hammer in"

We use to talk about high-level languages, like C#, Java... We use to add even more libraries or namespaces to these languages, very powerful libraries and languages...

But we shouldn't forget that the most powerful weapons that humans have are mathematics and logic ;-)

Next puzzle in a few days, I am glad you liked this one :-)

Re: Re: Re: Switching our Christmas tree bulbs

sriram — Wed, 26 Dec 2007 15:16:49 GMT

Yeah.....
all these numbers are perfect squares....

for a given date: n ,
all bulbs with perfect square roots between 1-n will glow...
for bulbs n+1 to 365,
all bulbs that are integral multiples of (2 to n)*(m) <365 will glow. [where m ranges from n to 183]

Re: Re: Switching our Christmas tree bulbs

Miguel — Wed, 26 Dec 2007 15:02:08 GMT

Good solution: you have found the correct bulbs... Congrat!! :-)

Regarding to the algorithm, I have a complexity of sqrt(n) for the first execution, that could also be improved for next executions changing the size of the problem (number of bulbs and days) if we use dynamic programming...

I will give you just one more clue: those numbers are special from a mathematical perspective ;-)

Re: Switching our Christmas tree bulbs

sriram — Wed, 26 Dec 2007 14:56:55 GMT

I am prolly the laziest person u would ever meet...
my method is greedy! :D
and the bulbs you asked: for day 365:
1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361

Below, was my first program .... inefficient to the core...
for (int j = 2; j <= limit; j++)
            {
                for (int i = j; i < 366; i++)
                {
                    if (i%j == 0)
                    {
                        if (light[i] == false)
                            light[i] = true;
                        else if (light[i] == true)
                            light[i] = false;
                    }

                }

Order of n^2 [baaaad] :(
of course there is lot of room for optimization .. let me leave that to the next commenter.

nice post dude! keep posting a few interesting problems.. will keep my brain from rusting :)

Re: Re: Switching our Christmas tree bulbs

Miguel — Wed, 26 Dec 2007 14:14:56 GMT

Yes, it will be 19 bulbs ON... But the most important: which is the method?

Even more important: which is the most efficient method? Which is the complexity?

And the last one (if you get the most efficient method, you will know this one): which bulbs (#1, #2 or whatever) will be ON?

Good job sriram, I think you are on the way (but I don't know your method, so... hehe)

Re: Switching our Christmas tree bulbs

sriram — Wed, 26 Dec 2007 13:11:50 GMT

Day 1: 365 glow
Day 2: 183 glow
Day 3: 182 glow
Day 4: 213 glow
....
Day 359: 23 glow
Day 365: 19 glow

is this rite?

Re: Switching our Christmas tree bulbs

sriram — Wed, 26 Dec 2007 12:37:52 GMT

okay..now i get it....answer in a while....

Re: Re: Switching our Christmas tree bulbs

Miguel — Wed, 26 Dec 2007 11:35:04 GMT

Mmm, no... Probably my explanation is not very good. This is a more complete example:

Day 1: You switch (ON) all the bulbs multiple of 1, so... 1,2,3,4...365

Day 2: You switch (OFF, because they were ON) all the multiples of 2: 2, 4, 6...

Day 3: You switch all the bulbs multiple of 3: number 3 OFF (it was ON since first day), number 6 ON (it was OFF since day 2), number 9 OFF (it was ON since first day...)

Knowing the method, I can say you that, in day, 183 there will be more than 13 bulbs ON (I can say also which ones, but it will be too much easy for you to solve it with that clue)...

Good luck ;-)

Re: Switching our Christmas tree bulbs

sriram — Wed, 26 Dec 2007 04:23:14 GMT

I am thinking that starting from 365/2 , i.e day 183 you will have only 1 bulb glowing each day..so on day 359 (Christmas) u still got only 1 bulb glowing.

maybe i read the question wrong...