Sunday, June 28, 2009

Puzzle 37 – Fun with Strings (BirthDay Blues)

Language – Java | Type – Concept | Last date 1-Jul-2009 9:00 p.m. IST | Points 3

It’s my birthday today (June 28th) – so I got one of those Happy Birthday puzzles I have been saving up for so long!
Strings are one of the most used Java classes – so how well do we know Strings? Here another puzzle on Strings.

package com.twisters;
class Stingify{
public static void main(String args[]){
String firstOne
= new String("Happy Birthday");
String secondOne
= new String("Happy Birthday");
/* No change to the line below! */
System.out.println(
"First String is equal to second : " + (firstOne == secondOne));
}
}

The first string is pretty much equal to the second. I think it’s fair that the output should be First String is equal to second: true.

Just a few simple conditions:
1. Don’t make any changes to the line which has the print statement
2. Three semicolons are more than enough in this program. No additional semicolons.
3. The usual rule – add as many characters that you like but no deleting characters. Commenting any of the existing lines of code is equivalent to deleting it.

P.S. - I think there might be couple of hints and rambling coming across on Twitter.
P.S.2 - I still looking for folks who want to test drive the Java Treasure Hunt. Any takers?

Got an answer? Do leave it here.

Puzzle 36 – Solution

This puzzle has loads of possible optimization – here are my action packed 18 characters!
The comments for each optimization should be self explanatory.
package com.sam.twisters.euler;
/*
* A Pythagorean triplet is a set of three natural numbers,
* a < b < c, for which,
* a^(2) + b^(2) = c^(2)
* For example, 3^(2) + 4^(2) = 9 + 16 = 25 = 5^(2).

* There exists exactly one Pythagorean triplet for which a + b + c = 1000.
* Find the product abc.
*/
public class Prog9 {

public static void main(String[] args) {
long startTime = System.nanoTime();

for(int a=1;a<1000;a++){
/*
* Optimization -->for(int b=1;b<1000;b++){ (5 char deleted 1000 added 'a')
* In a Pythagorean triplet a > b & c
*/
for(int b=1;b<a;b++){
/*
* Optimization -->for(int c=1;c<1000;c++){(6 char deleted 1000 added '=b')
*/
for(int c=1;c<=b;c++){
if(a*a == b*b+c*c && a+b+c == 1000){
System.out.println(a
*b*c);
/*
* Optimization -->a=1000; (7 char)
* At this point we have found our solution and we need to break out
* of the Loop. Breaking out of the outer for loop makes most sense
*/
a
=1000;
}
}
}
}

long estimatedTime = System.nanoTime() - startTime;
System.out.println((
float)estimatedTime/1000000000);
}
}

http://www.blogtrog.com/code.aspx?id=d83d3910-5e47-4c86-ae5e-b36ec47f7b57

There were a couple of solutions like,
for(int b=1;b<1000-a;b++){
for(int c=1000-a-b;c<1000;c++){
while this solution works when the sum is 1000 it fails when you go for higher numbers say 10,000 - truth is I think the algorithm at worst is incorrect or at least arbitrary - whats the reasoning behind 1000-b? However since it works for 1,000 I considered these solutions to be correct!

I usually don't reply to all the comments (too time consuming) - but there were plenty of good suggestions/solutions so here my 2 cent.

@Arshia - Nice use of the cut-paste rule. Pretty neat of you to align the code with the comments.

@Sebastian - I think my code is fine. I just renamed the variable - the 'c' in the comments correspond to the 'a' in my code -:). Hence I find a triplet where a*a = b*b + c*c instead of c*c = a*a+b*b - Same thing isn't it?
Reminds me, Trust only the code not the comments!!

@George PĆ³lya - Your solution gets the award for the best abuse of rules -:)! Pretty neat!!

@TheMalkolm - Interesting Idea about posting the fastest code - but it would require analyzing the code - not just running all codes - after all the algorithm might be good for 1000 but what about 10,000 or 100,000?
Plus even if I just decided to run each solution - it's a lot of work - to run each solution to check the amount of time it takes!

@Makkhdn - How did you count 18. I made the exact same changes and counted 12.

I would also like to thank you folks for pointing out the problem you faced while
pasting the solution - with the '<' and '>'. I do have a suggestion folks - instead of posting the long code directly in the comments you could use the excellent service provided by Dave at www.blogtrog.com
You could just paste the link provided by at Blogtrog as the solution - could save a lot of trouble with illegal characters while adding them in comments here.

Wednesday, June 24, 2009

Puzzle 36 – Triple the fun (Optimization Series puzzle - 2)

Language – Java | Type – Concept | Last date 28-Jun-2009 9:00 p.m. IST | Points 3

If you have not looked at code optimization puzzle before – I would suggest having a look at the
first one!

Unlike the previous puzzle where the un-optimized code took over 30 minutes to run, I have already done a pretty good job on this one. It executes in about 5 seconds. Well 5 seconds is still a lot of time. Can you get it to execute in less than half a second?


package com.sam.twisters.euler;
/*
* A Pythagorean triplet is a set of three natural numbers,
* a < b < c, for which,
* a^(2) + b^(2) = c^(2)
* For example, 3^(2) + 4^(2) = 9 + 16 = 25 = 5^(2).

* There exists exactly one Pythagorean triplet for which a + b + c = 1000.
* Find the product abc.
*/
public class Prog9 {

public static void main(String[] args) {
long startTime = System.nanoTime();
/*
* For each possible pair of numbers below 1000
* check if there is a Pythagorean triplet for which a + b + c = 1000.
*/
for(int a=1;a<1000;a++){
for(int b=1;b<1000;b++){
for(int c=1;c<1000;c++){
if(a*a == b*b+c*c && a+b+c == 1000){
System.out.println(a
*b*c);
}
}
}
}

long estimatedTime = System.nanoTime() - startTime;
System.out.println((
float)estimatedTime/1000000000);
}
}

http://www.blogtrog.com/code.aspx?id=bd1246e9-25f6-4f9a-b983-486745ae457c

Rules? Same as before –

1. This code takes about 5 seconds to run. Get it to run in under half a second.
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.

Hint – There are a few comments in the code, I sure there is something there that might help!

If optimizing a code that runs in 4 seconds does not sound like a challenge – try the same code expect that instead of the sum equaling 1000 (a+b+c=1000), try for 10,000 or 100,000.

Got an answer? Do leave it here.

Puzzle 35 – Solution

A MB and KB are special numbers simple because they can be expressed as powers of 2.
1 KB = 2(10) and 1 MB = 2(20). Java provides a simple operator to multiply by two better know as the left shift operator.

So the code snippet that does the trick is,

int oneMB = oneKB<<10;

The other answer that I got is,
int oneMB = oneKB+1047552; which look like a neat enough way to solve the puzzle!

Leaders board to be updated with the next post.

Sunday, June 21, 2009

Puzzle 35 – Memory Management

Language – Java | Type – Concept | Last date 24-Jun-2009 09:00 p.m. IST | Points 3

The other day I was trying out some memory conversions. I vaguely recalled a piece of code that I wrote in my college days.

package com.twisters;
public class MemoryManager {
public static void main(String[] args) {
int oneKB = 1024; /* No change to this line! */
int oneMB = oneKB;
System.out.println(
"1 MB of memory is :"+oneMB+" bytes.");/* No change to this line! */
}
}

Obviously I think I have missed something. And I am sure I have missed it in line 5. Help me complete this code!!

Rules – pretty simple ones really!
No additional semicolons.
No changes to the lines marked with the comment /* No change to this line! */
No multiplication or division sign to be used in the program.
No additional packages except java.lang – import(ing) is a costly affair!
Make minimum changes to the code – a maximum of 8 characters change would suffice.

Link for the day – http://mindcipher.com/ - A must view site for any puzzle lover.

Got an answer? Do leave it here.

Puzzle 34 - Solution.

This is one of the most restrictive puzzles till now. With no new semi-colons being allowed it's pretty difficult add any additional code. The other restriction on line 10 & 12 leave no choice but to target line 11 which is the only line left!

In Java we can initialize variables even if they are part of an expression. This mean we can assign a value of 42 to the question at line 11 and our problem would be solved.

So here is the one line solution to this puzzle!

int theAnswer = (theQuestion=42)*9;

For all you Douglas Adams fans out here there is another puzzle based on Hitchhiker's Guide to the Galaxy coming up soon! Keep watching this space for more ...

@Sebastian - Still trying to figure out your answer :)!

Twister - Updates

I have done a few changes to this blog - just wanted to post an update on what’s new.

1. The Twitter Connection - Sometimes I feel the puzzle could be made more interesting and more thought provoking if I put in a couple of additional clauses to the original question. Twitter seems to be an ideal way to add a couple of points or throw in a hint or two for a question. It could also be a great way to get feedback!

2. Rating Widget - Each question has a rating widget with it. Rating question help me judge the good question from the junk - while I don't think there can be any immediate action I'm sure in the long run I could try and improve based on your feedback.

3. Optimization Series - In the coming days you should see a couple of more questions on optimizing code. The questions do get specific and might be harder to solve without a know algorithm. I'm willing to give it a try though and see how it goes.

4. Social Networking buttons - I think I have finally fixed all the social networking buttons - hopefully they should all work fine now!

5. Score Update tool - Have a small tool in Java that updates the score for me - makes my life a lot easier now!!

Finally the big news - The Java Treasure Hunt is ready for Beta Test - and I'm looking out for about 5 Beta Testers. Beta Testers get a first preview of the Treasure Hunt - which I hope would be fun. Anyone interested?
Leave a comment here or mail me at java.twisters@gmail.com

I would also like to thank everyone who's provided encouragement and feedback to carry on with Java Twisters. It’s always great to hear what you think about Twisters - so do let the feedback coming.

Cheers - Sam!

Wednesday, June 17, 2009

Puzzle 34 – The Answer to Life, the Universe and Everything

Language – Java | Type – Concept | Last date 21-Jun-2009 12:00 p.m. IST | Points 3

We all know the Answer to Life, the Universe and Everything (Goolge it). So it was a little surprise when I came across this piece of code that prints out 6 as the ultimate answer.

On close inspection I found that the author seems to have confused theQuestion with theAnswer. Let’s correct this, shall we?

/*
"Six by nine. Forty two."
"That's it. That's all there is."
"I always thought something was fundamentally wrong with the universe"
http://en.wikipedia.org/wiki/Notable_phrases_from_The_Hitchhiker%27s_Guide_to_the_Galaxy
*/

class Life{ /* No additional Semi-colons may be added to this class. */
public static void main(String[] args) {
int theQuestion = 6; /* No Changes to This line! */
int theAnswer = theQuestion*9;
System.out.println(
"The ultimate answer is " + theQuestion);/* No Changes to This line! */
}
}

http://en.wikipedia.org/wiki/Notable_phrases_from_The_Hitchhiker%27s_Guide_to_the_Galaxy

Get the code to print the correct answer which is 42. Please respect all the wishes of the code author, which he has given as comments.
Its also pretty impolite to delete any code that the author has already written - so no deletes please.

Got an answer? Do leave it here.

Puzzle 33 – Solution

A number is Prime if it there is no number that can divide it completely except 1 and itself. However to check if a number is prime it is not necessary to check all the way up to (number-1). It is sufficient that there it has no factor less than or equal to its square root. (Pretty easy to prove - try it!).

My optimization – Just add a Math.sqrt() at line 10 and the code runs in less than 5 seconds compared to the 30 minutes or so it takes without the optimization! Woo thats what I call an optimization!!!

package com.sam.twisters.euler;
/*
* The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
* Find the sum of all the primes below two million.
*/
public class Proj10 {

public static boolean isPrime(long n){
boolean isPrime = true && (n==2 || n%2!=0);
//Optimized-->for(long i=3; i<n&&isPrime;i+=2){ 14 chars added
for(long i=3; i<Math.sqrt(n)+1&&isPrime;i+=2){
if(n%i ==0){
isPrime
= false;
}
}
return isPrime;
}

public static void main(String[] args) {
long startTime = System.nanoTime();

long sum = 0;
int n=2;
do{
if(isPrime(n)){sum+=n;}
n
++;
}
while(n < 2000000);
System.out.println(sum);

long estimatedTime = System.nanoTime() - startTime;
System.out.println((
float)estimatedTime/1000000000);
}
}

http://www.blogtrog.com/code.aspx?id=dc704a56-8ea9-4726-85e4-b2e94e44e18e

A lot of folks came up with a similar conceptual answer and a few more suggestions. You can have a look at all the solution in the previous post.

Leaders board to be updated during the weekend!!

Sunday, June 14, 2009

Puzzle 33 – Prime Number (Optimization Series puzzle -1)

Language – Java | Type – Concept | Last date 17-Jun-2009 9:00 p.m. IST | Points 3

Lately I have been pretty interested in project Euler. Project Euler is a series of challenging mathematical/computer programming problems that require the use of a computer and programming skills to solve problems.

If you haven't been there yet I suggest do have a look.

I sure people love the idea of writing optimized code – something I usually don’t quite agree with. I would trade cheeky (and hard to understand) optimized code for easy and maintainable code. But that’s just me!!

Project Euler has thumb rule – No problem should take more than a min to solve. Since the code I write can usually take a long time to run it would be great if you folks could help me out a bit!

package com.sam.twisters.euler;
/*
* The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
* Find the sum of all the primes below two million.
*/
public class Proj10 {

/* Method that returns true if n is prime otherwise returns false*/
/* Use the brute force method! */
/* I have optimized it so that it skips even numbers.*/
public static boolean isPrime(long n){
boolean isPrime = true && (n==2 || n%2!=0);
for(long i=3; i<n&&isPrime;i+=2){
if(n%i ==0){
isPrime
= false;
}
}
return isPrime;
}

public static void main(String[] args) {
long startTime = System.nanoTime();

long sum = 0;
int n=2;
do{
if(isPrime(n)){sum+=n;}
n
++;
}
while(n < 2000000);
System.out.println(sum);

long estimatedTime = System.nanoTime() - startTime;
System.out.println((
float)estimatedTime/1000000000);
}
}


You can view the code @ http://www.blogtrog.com/code.aspx?id=1ce259ec-11f6-42bc-b03a-6aa9bf100a90

I got a few rules though.
1. This code takes about 30 minutes to run. Get it to run in under 1 min.
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 single char.
To illustrate you could cut n%2==0|| from if(n%2==0||n%i ==0){ (line 12)
And paste it at if(n%2==0||isPrime(n)){sum+=n;} (line 27) without using up a single char. Just remember its cut-paste and not copy-paste.

If all the rules seem a bit complicated - well just remember the main rule - 18 characters - either addition or deletion counts!

Hint – I would look carefully at the prime number algorithm for possible optimizations! Its a mathematical questions - so the answer could be with Math.

Link of the day -- http://projecteuler.net

(P.S – Feel free to add as many comments as needed to explain your optimization!
If the rules are not 100% clear – don't worry they will be once you see the answer(s). Please do let me know what you think of this type of question – would you like to see more? This one is purposefully simple -;)

Also if you want to re-write the entire code ,feel free to do so and leave a comment – Just that I won’t count that solution towards the score - that's all, still would be great to hear from you!)

Got an answer? Do leave it here.

Puzzle 32 – Solution

The solution to this puzzle lies in the way packages work in Java. The key concept behind packages is that more than one class can share the same name as long as they belong to different packages.

The code snippet that does the trick is,

package com.twister;

class String{}

public class DoubleTrouble{
public static void main(String args[])
{System.out.println(
"This is the wrong one!");}
public static void main(java.lang.String args[])
{System.out.println(
"This is the right one!");}
}


The class String in the same package takes precedence over the class java.lang.String. Fully qualifying the method which prints "This is the right one" with java.lang.String does the trick!

The were a couple of other really good solutions -
1.Putting the invalid main in a inner class or altogether different class.
2. Having a static initialization block. No one said that "This is the wrong one" should not print when the code is run - just that "This is the right one!" should.
Having a static block does that - innovative!

Puzzle 15 is based on the same concept but is worded differently!!

Wednesday, June 10, 2009

Puzzle 32 – Double Trouble

Language – Java | Type – Concept | Last date 14-June-2009 12:00 p.m. IST | Points 3

This brings me to the last puzzle in this series. If you are wondering what I mean – it's just the way I write twisters - A series of 16 puzzles – next week we start with a new set of questions! I like to keep the best for the last and I believe this is the toughest puzzle on twister. Maybe, you don’t – lets get cracking shall we.

package com.twisters;
class DoubleTrouble{
public static void main(String args[])
{System.out.println(
"This is the wrong one!");}

public static void main(String args[])
{System.out.println(
"This is the right one!");}
}

Get this to print 'This is the right one!' when the program is run. Oh yes you need to get the code to compile first.

Let’s get to the challenging part shall we.

You cannot change anything about the main() which has the 'This is the wrong one!' print statement. The means no changes allowed to public static void main(String args[]){System.out.println("This is the wrong one!");}
It remains as it is - no changes, no additions, no deletions, no commenting it out - nothing!

Need a hint? One of the puzzles in April holds the solution to this puzzle (Be warned, it’s a complete spoiler). However if you are really stuck, you might want to have a look at the puzzles asked in April!!

Site of the day - http://www.facebook.com/careers/puzzles.php – puzzles on Facebook – isn’t that something we have been waiting for ;)!

Got an answer? Do leave it here.

Puzzle 31 – Solution

You folks came up with a myriad of solutions for this puzzle – here is the one I had in mind.

Try-catch and finally has a peculiar behavior when it comes to returning values. In case a return statement exists in the finally block – the value in the finally block is returned even if the return in the try/catch has executed smoothly.
Finally code is always executed – even if there is a return statement in the try!!

For those who did look hard there was a hint in the last line of the puzzle – "Finally if you still haven’t figured this out – my suggestion is try again!!" It was no coincidence that two java keywords Finally and Try were present in a single sentence!

Here is the code snippet that does the trick.

package com.twisters
class TheTest{
public boolean win(){
try{
return false; //Get this code to always return true.
}
finally{
return true;
}
}
}

There were loads of other solutions that were correct – some where real gems. (Unfortunately, I still haven’t gone through all the solutions/comments!!!)

1. Use a switch statement – Oh yes I forgot to ban that one. Righhhhht.
2. return false == false?true:false – which one is the original false please?
3. Rename false to false1 and declare flase1 as a boolean variable.

There are lots more - have a look at the comments if you want to see them all.
Leaders board to be updated next week.

@Abhi – I did goof up a bit with the scores. They now stand corrected. Thanks for pointing out!

Sunday, June 7, 2009

Puzzle 31 - Falsify

Language – Java | Type – Concept | Last date 10-June-2009 9:00 p.m. IST | Points 3

The next puzzle is a pretty short one but as usual has a Java principle involved. I think this one is a little tough though I sure you folks will come up with solutions I did not think off.

package com.twisters
class TheTest{
public boolean win(){
return false; //Get this code to always return true.
}
}

We all know that truth always wins. So the method win() should always return true.

Add any amount of code you like but no deletes. Can you tell me the main principle involved in your solution?
Don’t use if, while, do-while and for keywordsYou are not allowed to use any of them for this puzzle!

Added : And before I completely forget no boolean or logical operators either - so no !, &, &&, |, || or any other such operator that works on boolean values! For those have already answered - this clause won't apply!!

Finally if you still haven’t figured this out – my suggestion is try again!!

Got an answer? Do leave it here.

Puzzle 30 – Solution

The main principle involved in this question was the fact that Java methods can have the same name as the constructor. The main solution to this problem was simple adding a method Namesake() to the class.

package com.twister;
public class Namesake {
public void Namesake(){}
public static void main(String[] args) {
new Namesake().Namesake();
}
}

Other solutions – which I could think of, were just ways in which one could get rid of the ‘.’ Between the nameskae(). So there can be solutions like,

1. new Namesake.equals(new Namesake())
2. new Namesake(); float f = 0.0; new Namesake()

Congrats to everyone who got the right answer!!!

Wednesday, June 3, 2009

Puzzle 30 - The Namesake

Language – Java | Type – Concept | Last date 7-June-2009 12:00 p.m. IST | Points 3

It's time to get back to some real basics. The next question is pretty easy – have fun folks solving this quickee.

package com.twisters;
public class Namesake {
public static void main(String[] args) {
new Namesake().Namesake();
}
}

Get this code to compile and run. Add any amount of code you like but no deletes. Can you tell me the main principle involved in your solution?

Wanna challenge yourself on this one - come up with conceptually two different solutions for this problem?

Site of the day - http://www.xploremagic.com – Magic is always fun!

Edit - Updated this post - Looks like I has some problem with BlogTrog - the service I use to display formatted code. If you have left a solution already the principle remains the same - so old solution are still good!

Puzzle 29 – Solution.

The trick here is to control a for loop using multiple variables. Thus a single for loop can be used as multiple for loop.
The code expalins this principle –

package com.twister;
import java.util.Scanner;
class Matrix{

public static void main(String a[])
{
int r,c;
int i,j,k=0;
int matrix[][] = new int[10][10];
r
= 2; c= 2;

/*Variable k is used to determine whether the for Loop
is currently scanning elements or printing them
k = 0 Loop is in scan mode
k = 1 Loop is in print mode
*/
for(j=0,i=0;i<r && j<c && k!=2;j++){
if(k==0) //Scan mode
matrix[i][j] = new Scanner(System.in).nextInt();

if(k==1) //Print Mode
System.out.print(matrix[i][j]+ " ");

if(i==r-1 && j==c-1){ //Swap from scan mode to print mode
k++;
i
=0;j=-1;
}

if(j==(c-1)){
j
=-1;i++;
if(k==1)
System.out.println(
""); //Prints a Blank line
}
}
}
}

My personal favorite solution for this puzzle is the one by Kannan - Short, concise and gets the Job done!

Leaders board to be update with the next post!