If you have not looked at code optimization puzzle before - I would suggest having a look at the first one!
It's surprising how badly a program can start performing if you carelessly use nested loops. Well the code takes around 100 seconds to run and that's just too much. I think about 10 seconds is the maximum the code for this question should run. Any takers?
package com.sam.twisters.euler;
/* Problem 5 : Euler
* 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
* What is the smallest number that is evenly divisible (divisible without reminder) by all of the numbers from 1 to 20?
*/
public class Prog5 {
/*Simple function to check if the divisor completely divides the divident*/
public static boolean isDivisble(int divident, int divisor) {
if(divident%divisor == 0){
return true;
}
else{
return false;
}
}
public static void main(String[] args)
{
long startTime = System.nanoTime();
boolean va = true;
/* Start looping though all the numbers and see if we can find one divisible by all numbers from 1 to 20.
*/
int i = 1;
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++;
}while(!va);
System.out.println(i);
long estimatedTime = System.nanoTime() - startTime;
System.out.println((float)estimatedTime/1000000000);
}
}
http://www.blogtrog.com/code.aspx?id=fdc2fad6-f541-4c8d-934d-3b838323a66b
Rules? Same as before -
1. This code takes about 100 seconds to run. Get it to run in under 10 seconds.
2. You see while it's really great that you have decided to help me - I really don't want you to mess up my entire code. So here is the deal - you can change a maximum of 18 characters (yes that's all).
3. What constitutes a character change?
a. Inserting a character - each character (including space) that you add to the existing code.
b. Deleting a character - each character (including space) that you delete from the existing code.
c. Over writing a character - well you cannot do that. You could delete and insert but you cannot over write.
d. Cut Paste - Special Rule for cut paste is you can cut code from the existing code and paste it somewhere (except inside a comment) else in the code without using up a single char.
Just remember its cut-paste and not copy-paste.
Got an answer? Do leave it here.
(Do use BlogTrog and post the link to your code here, in case you have a problem posting the code in the comments!!)
Diagonalization FTW!!
ReplyDeletedo{
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);
In 18 moves:
ReplyDeleteint 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);
1. Add break; statement on line 30 (+6 characters)
ReplyDelete2. 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!!!
Here's my offering:
ReplyDeletehttp://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
Line 28, 11 changes
ReplyDeletefor(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 is my approach, it takes about 0.3 seconds
ReplyDeleteWe 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 ;-)
The best I could come up with is this:
ReplyDeleteint 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.
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
ReplyDeleteSo 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
do {
ReplyDeleteva = 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);