tag:blogger.com,1999:blog-9193160645817040317.post7128496611114494841..comments2015-12-22T12:31:53.234+05:30Comments on Twisters - The New Age Java Quiz: Puzzle 36 – Triple the fun (Optimization Series puzzle - 2)Saifuddin Merchanthttp://www.blogger.com/profile/09008041357659535766noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-9193160645817040317.post-71212638936987320892009-06-27T15:26:26.810+05:302009-06-27T15:26:26.810+05:30Also we could calculate that A is less than 500 ac...Also we could calculate that A is less than 500 actually. It comes from:<br /><br />a + b + c = 1000;<br />a**2 = b**2 + c**2;<br /><br />a = 500 - b*c/1000;<br /><br />So my previosly solution could be optimized even more :)<br /><br />for (int a = 1; a < 500; a++){<br />for (int b = 1; b < 1000-a; b++){<br />for (int c = 1000-a-b; c <= 1000 -a-b; c++){<br />if ((a * a == b * b + c * c) && (a + b + c == 1000)){<br />System.out.println(a * b * c);<br />}<br />}<br />}<br />}TheMalkolmhttps://www.blogger.com/profile/11358745568436186926noreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-6502121779605095382009-06-26T02:13:55.158+05:302009-06-26T02:13:55.158+05:30b and a aren't good variable names for blogspo...b and a aren't good variable names for blogspot, because you'll get such messages:<br /><br />Your HTML cannot be accepted: Tag is brokenstfnhttps://www.blogger.com/profile/13802280639197311708noreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-85081332322922448922009-06-26T02:11:12.036+05:302009-06-26T02:11:12.036+05:30for(int a=1;a<1000;a++){
for(int b=1;...for(int a=1;a<1000;a++){<br /> for(int b=1;b< a;b++){<br /> for(int c=1;c< b;c++){<br /> if(a*a == b*b+c*c && a+b+c == 1000){<br /> System.out.println(a*b*c);<br /> }<br /> }<br /> }<br /> }stfnhttps://www.blogger.com/profile/13802280639197311708noreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-80284443359259924962009-06-25T17:09:34.074+05:302009-06-25T17:09:34.074+05:30I found two ways
17 moves and keep the original r...I found two ways<br /><br />17 moves and keep the original result:<br />for (int a = 1; a < 1000; a++) {<br /> for (int b = 1; b < 1000-a; b++) {<br /> for (int c = 1; c <= 1000-a-b; c++) {<br /> if (a + b + c == 1000 && a * a == b * b + c * c) {<br /> System.out.println(a * b * c);<br /> }<br /> }<br /> }<br />}<br /><br />18 moves and go slightly faster :<br />for (int a = 1; a < 1000; a++) {<br /> for (int b = 1; b < a; b++) {<br /> for (int c = 1; c < b; c++) {<br /> if (a + b + c == 1000 && a * a == b * b + c * c ) {<br /> System.out.println(a * b * c);<br /> }<br /> }<br /> }<br />}Makkhdynhttps://www.blogger.com/profile/16225036210991551541noreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-50696176457504911572009-06-25T15:30:54.376+05:302009-06-25T15:30:54.376+05:30for (int a = 1; a < 1000; a++) {
for (int b = 1...for (int a = 1; a < 1000; a++) {<br />for (int b = 1; b < 1000-a; b++) {<br />for (int c = 1000-a-b; c <= 1000 -a-b; c++) {<br />if ((a * a == b * b + c * c) && (a + b + c == 1000)) {<br />System.out.println(a * b * c);<br />}<br />}<br />}<br />}<br /><br />This code runtime is about 0.2% of original at my comp. A lot better than u asked (10%)<br /><br />Would u write the fastest one in the solution post?TheMalkolmhttps://www.blogger.com/profile/11358745568436186926noreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-79098938503442407222009-06-25T14:37:50.742+05:302009-06-25T14:37:50.742+05:3020 for(int b=1;b<1000-a;b++){
21 ...20 for(int b=1;b<1000-a;b++){<br />21 for(int c=1000-a-b;c<1000;c++){<br />...<br />24 }break;<br /><br />Changes: 2 (line 20) + 7 (line 21) + 6 (line 24) = 15 <br /><br />Time: 0.0086187925Yauheninoreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-59442989889795373552009-06-25T13:21:18.683+05:302009-06-25T13:21:18.683+05:30From 2.70s to 0.05s with a total of 17 changes:
t...From 2.70s to 0.05s with a total of 17 changes:<br /><br />triplet: // added colon: 1 change, cut&pasted "triplet" from comments<br />for(int a=1;a<1000;a++){<br /> for(int b=1;b<a;b++){ // delete "1000", add "a": 5 changes<br /> for(int c=1;c<b;c++){ // delete "1000", add "b": 5 changes<br /> if(a*a == b*b+c*c && a+b+c == 1000){<br /> System.out.println(a*b*c);<br /> break triplet; // add "break;": 6 changes, cut&pasted " triplet" from comments<br /> }<br /> }<br /> }<br />}George Pólyanoreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-21655518514175430322009-06-25T13:13:14.516+05:302009-06-25T13:13:14.516+05:30This is a solution that uses about 17 changes and ...This is a solution that uses about 17 changes and runs in less than 5 milliseconds:<br /><br /> for(int a=1;a<;1000;a++){<br /> for(int b=a;b<;1000;b++){<br /> /*for(*/int c=1000-a-b;//c<;1000;c++){<br /> if(a*a + b*b == c*c && a+b+c == 1000){<br /> System.out.println(a*b*c);<br /> //}<br /> }<br /> }<br /> }<br /><br />(That same code still runs in just two tenths of a second for 10.000)<br /><br />The problem is that there is a bug in the original code which needed to be fixed. The theoreme states that a < b < c and the code checks for a^(2) = b^(2) + c^(2) instead of<br />a^(2) + b^(2) = c^(2) (as shown in the comments).<br />Note there is no triplet that fulfills this because the sum of the squares of two values that are greater than another value will always be greater and thus it will never work. So the initial code is wrong (although it generates the right product).<br />I had to do more than the allowed number of changes but that was just to correct the code check!<br /><br />The probably anticipated solution that runs in about half a second and requires 10 character changes would have been:<br /><br /> for(int a=1;a<;1000;a++){<br /> for(int b=1;b<;a;b++){<br /> for(int c=1;c<;b;c++){<br /> if(a*a == b*b+c*c && a+b+c == 1000){<br /> System.out.println(a*b*c);<br /> }<br /> }<br /> }<br /> }<br /><br />But the triplet that is found is not ordered correctly either. However all of this is just a matter of reinterpreting (renaming) the variables.<br /><br />So using the the cut-paste special rule (for switching variables in the loops) I get this solution:<br /><br /> for(int c=1;c<;1000;c++){<br /> for(int b=c;b<;1000;b++){<br /> //for(<br /> int a=1000-c-b;//a<;1000;a++){<br /> if(a*a == b*b+c*c && a+b+c == 1000){<br /> System.out.println(a*b*c);<br /> }<br /> <br /> }<br /> }<br /><br />Which makes 15 changes if my count is correct and runs in 1.5 milliseconds (I had to run the code a hundred times because nanotime is not accurately enough for just one run)<br /><br />BTW: the comment field does not accept the < sign - escaping them by hand is pretty annoyingSebastianhttp://www.yworks.comnoreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-58423733542880080682009-06-25T04:48:20.178+05:302009-06-25T04:48:20.178+05:30line 20: b(smallerThan)1000 && b(smallerTh...line 20: b(smallerThan)1000 && b(smallerThan)a<br />line 21: c(smallerThan)1000 && c(smallerThan)b<br /><br />That should do it =)<br />(replace smallerThans by correspondant Java operator)Anonymoushttps://www.blogger.com/profile/06187177872270364018noreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-89219268165432851732009-06-25T04:31:53.033+05:302009-06-25T04:31:53.033+05:30Cut and paste c*c to where a*a is followed by anot...Cut and paste c*c to where a*a is followed by another cut and paste of a*a to where c*c originally was. Add 2 characters so b=a+1 and another 2 characters to set c=b+1. Add a conditional on the second for loop as " && a+b<1000" which is another 12 characters with spaces for a total of 16 characters to get:<br /><br />for(int a=1;a<1000;a++){<br /> for(int b=a+1;b<1000 && a+b<1000;b++){<br /> for(int c=b+1;c<1000;c++){<br /> if(c*c == b*b+a*a && a+b+c == 1000){<br /> System.out.println(a*b*c);<br /> }<br /> }<br /> }<br />}<br /><br />With the resultant output as follows:<br /><br />31875000<br />0.479309Arshia Khanhttps://www.blogger.com/profile/04023130805491879540noreply@blogger.com