[challenge] light bulbs - Printable Version

[challenge] light bulbs - Printable Version

+- Sinisterly (https://sinister.ly)
+-- Forum: Coding (https://sinister.ly/Forum-Coding)
+--- Forum: Coding (https://sinister.ly/Forum-Coding--71)
+--- Thread: [challenge] light bulbs (/Thread-challenge-light-bulbs)

[challenge] light bulbs - phyrrus9 - 06-21-2015

Rules:
Your program may be written in any language of your choice
Your program may not take longer than 25 seconds to compute the answer

Problem:
You have a string of N light bulbs, all of which are turned off. Every second (S), light bulbs that are multiples of S toggle their state (off->on, on->off). After T seconds, what is the state of the light bulb in question (Q)?

Inputs:
N, T, Q

Outputs:
state(Q)

+1 rep and 50NSP if your program computes the correct result in under 5 seconds.

NOTE: a random number generator won't work, I will test each program a random number of times.

Limits:
10<N<4,294,967,296
100<T<1,000,000
Q is a 1-bit integer

EDIT: PLEASE include an example of how to compile and run if your language is not C/C++/Java. Sorry @Eclipse, lets see how it handles

RE: [challenge] light bulbs - phyrrus9 - 06-21-2015

(06-21-2015, 04:58 PM)Eclipse Wrote: Setting a time limit without a specific input is not really logical, since a larger input would make the program's execution time longer. Also, different CPUs will execute shit at different rates. On top of this, different languages are slower/faster than others.

Here's my solution:

Code:
#imports import time #inputs not included in elapsed calculation N = int(raw_input('N > ')) T = int(raw_input('T > ')) #start time recorded start = time.time() #main code bulbs = {} for x in xrange(1, N+1): bulbs[x] = '0' #0 = off, 1 = on for S in xrange(1, T+1): for key in bulbs: if key % S == 0: if bulbs[key] == '0': bulbs[key] = '1' else: bulbs[key] = '0' #elapsed time calculated by current time - start time elapsed = time.time() - start #output def output(): opt = str(raw_input('Would you like to see the state of all bulbs or a specific one? (ALL/ONE) > ')).upper() if opt == 'ALL': for key in bulbs: print 'Bulb ' + str(key) + ' is ' + str(bulbs[key]) elif opt == 'ONE': bn = int(input('Which Bulb? (int) > ')) print 'Bulb ' + str(bn) + ' is ' + str(bulbs[bn]) output() #print elapsed time FOR CALCULATION print 'Time taken: ' + str(elapsed) + ' seconds'

Note: Mine is pretty shite. It can't work with your upper limits because range fucks up, and upon trying different implementations, python runs out of memory. I suppose a low level language like C would've been better but meh.

Example run:

Code:
N > 100000 T > 1000 Would you like to see the state of all bulbs or a specific one? (ALL/ONE) > one Which Bulb? (int) > 1000 Bulb 1000 is 0 Time taken: 15.2100000381 seconds

Actually, the upper limit is imposed for users to make the same mistake you did at simulating it, but not calculating it. Ran into the same problem when I first did this problem.

RE: [challenge] light bulbs - Eclipse - 06-21-2015

(06-21-2015, 06:25 PM)phyrrus9 Wrote: Actually, the upper limit is imposed for users to make the same mistake you did at simulating it, but not calculating it. Ran into the same problem when I first did this problem.

Wait, what? Not quite sure what you're getting at.

EDIT: By the way, what about my comments on the time limit?

RE: [challenge] light bulbs - phyrrus9 - 06-21-2015

(06-21-2015, 07:22 PM)Eclipse Wrote: Wait, what? Not quite sure what you're getting at.

EDIT: By the way, what about my comments on the time limit?

The speed isn't really effected by the chosen language, it is but its not an entirely important factor.

my code:

Spoiler:Code:
#include <stdio.h>
int main(int argc, char ** argv)
{
        unsigned int T, N, Q, i;
        sscanf(argv[1], "%u:%u:%u", &T, &N, &Q);
        unsigned int max = T;
        register unsigned char state = 0;
        for (i = 1; i <= max; i++)
                if (i % Q == 0) state = state ? 0 : 1;
        printf("T=%d\tQ=%d\tState=%s\n", T, Q,
                state ? "On" : "Off");
}
to compile:
Code:
gcc -o lights lights.c
run:
Code:
./lights T:N:Q

Here is my results:

Code:
(precise)phyrrus9@localhost:~$ time ./a.out 543210:4294967295:31
T=543210        Q=31    State=Off

real    0m0.009s
user    0m0.007s
sys     0m0.001s

RE: [challenge] light bulbs - Eclipse - 06-21-2015

Windows:

1. https://www.python.org/downloads/
2. Download 2.7.x
3. Install
4. Open (IDLE)
5. Paste Code
6. Run (F5)

Linux:

1. You should have it installed already, if not, google it.
2:

Code:
python path/to/file.py

RE: [challenge] light bulbs - phyrrus9 - 06-21-2015

(06-21-2015, 09:31 PM)Eclipse Wrote: Windows:

1. https://www.python.org/downloads/
2. Download 2.7.x
3. Install
4. Open (IDLE)
5. Paste Code
6. Run (F5)

Linux:

1. You should have it installed already, if not, google it.
2:

Code:
python path/to/file.py

ran for 31 seconds until I had to force kill it from memory overconsumption.

RE: [challenge] light bulbs - Eclipse - 06-21-2015

(06-21-2015, 09:28 PM)phyrrus9 Wrote: Here is my results:

Code:
(precise)phyrrus9@localhost:~$ time ./a.out 543210:4294967295:31 T=543210 Q=31 State=Off real 0m0.009s user 0m0.007s sys 0m0.001s

Holy fucking shit.

(06-21-2015, 09:37 PM)phyrrus9 Wrote: ran for 31 seconds until I had to force kill it from memory overconsumption.

I'm just going to delete it and start again from scratch. Bye.