Comments on Twisters - The new age Java Quiz: Puzzle 40 - Divide and optimize (Optimization Seri...

do { va = true; //Assume that i is a ...

2009-07-12T02:23:52.693+05:30

do {

va = true; //Assume that i is a valid answer to the puzzle

for (int d=20;d>=11&&va;d--) {
if (!isDivisble(i, d)) { //Yikes my assumption was wrong!

va = false;

}

}

i++;

} while (!va);

You should understand that this number must be div...

2009-07-10T02:11:28.062+05:30

You should understand that this number must be divided without reminder to all prime numbers at range [1..20] and it is worthless to make step smaller than 1*2*3*5*7*11*13*17*19 = 9699690

So you shold replace:

"i=1" to "i=9699690" : 8 actions
"i++" to "i+=9699690": 8 actions

Sum: 8+8 = 16 actions. Fits!

Just for bonus, not to be puzzled with incorrect output as answer, you shold replace
"System.out.println(i)" to "System.out.println(i-9699690");

My optimization:

232792560
Not optimized: 110.33363
Optimized: 0.008186197
Saved: 0.99992585% of time

The best I could come up with is this: int...

2009-07-09T21:11:51.968+05:30

The best I could come up with is this:
int d,i = 1;
d=1;
do{
for (int s=d;!isDivisble(d, i);d+=s){
}
} while (++i != 21);

System.out.println(d);

I don't know if 18 changes is enough to get to this snippet, even if the cut/paste rule is used extensively, but I fear not. However if it does, this tiny snippet runs in less than 1.25 microseconds (thats like 0.000001s) and is quite an optimization, I would say. To be fair it uses a different algorithm, although at first glance it seems structurally similar.

Here is my approach, it takes about 0.3 seconds We...

2009-07-09T20:30:44.140+05:30

Here is my approach, it takes about 0.3 seconds
We add a step variable (s) that increments i in steps of 20 and we start at 20 (because the number should be divisible by 20, this makes total sense)
Also we break the check early if it fails and we invert the check to start with the greatest number (going 20,19,18....) it is less likely that a number is not divisible by a greater number.
Note that my program outputs the correct solution (the original code outputs i+1) so the output differs (but is more correct).
If I count correctly this makes exactly 18 changes, but using the copy paste rule it could be a lot less and perform even slightly better (cuttung the '=' sign and using it as the assignment for s, e.g. or moving the'20' to get the initial assignment and then compare against s, etc.etc.).

int s,i = 20;
s=i;
boolean va = true;

/* Start looping though all the numbers and see if we can find one divisible by all numbers from 1 to 20.
*/
do {
va = true; //Assume that i is a valid answer to the puzzle
for (int d = 1; d <= 20; d++) {
if (!isDivisble(i,21-d)) { //Yikes my assumption was wrong!
va = false;
d=s;
}
}
i+=s;
} while (!va);
System.out.println(i-s);

removing the '21-' change (and saving 3 changes) will increase the runtime to almost 1 second, so if you want less changes, use this variant ;-)

Line 28, 11 changes for(int d=20;d>0;d--){ Line 3...

2009-07-09T17:40:27.523+05:30

Line 28, 11 changes
for(int d=20;d>0;d--){

Line 30, 4 changes
va = false;d=0;

After this we'll got 15 changes and ~7 seconds. Looks like solved.

But, If we'll forget about 18 changes and will move ahead :) than following can be introduces (only even numbers should be checked):
Line 25 (2 changes)
int i = 2;

Line 33 (3 changes)
i=i+2;

This will bring us to ~3.5 seconds

Here's my offering: http://www.blogtrog.com/code.a...

2009-07-09T14:02:05.284+05:30

Here's my offering:
http://www.blogtrog.com/code.aspx?id=8674f155-ca52-4803-9329-99d2085fad53

I should have only made 10 character changes and on running through 5x had an average running time of 5.4 seconds.

You can also eek a bit more out by doing things like replacing the isDivisible call but this does takes you over the 18 characters

1. Add break; statement on line 30 (+6 characters)...

2009-07-09T13:32:49.729+05:30

1. Add break; statement on line 30 (+6 characters)

2. Cut-paste line 33 (i++;) right after line 26.

3. Change it to i+=20; (+8 characters)

4. Change line 25 to int i = 20; (+3 characters)

5. Total changed: 17 characters, profit!!!

In 18 moves: int i = 2; do{ va = true; //Assu...

2009-07-09T02:56:21.951+05:30

In 18 moves:

int i = 2;
do{
va = true; //Assume that i is a valid answer to the puzzle
for(int d=20;d>=1&&va;d--){
if (!isDivisble(i, d)){ //Yikes my assumption was wrong!
va = false;
}
}
i+=2;
}while(!va);

Diagonalization FTW!! do{ va = true; //Assume ...

2009-07-09T01:16:09.136+05:30

Diagonalization FTW!!

do{
va = true; //Assume that i is a valid answer to the puzzle
for(int d=1;d<=20;d++){
if (!isDivisble(i, d)){ //Yikes my assumption was wrong!
va = false;
i++;
continue;
}
}
}while(!va);