Word Ladder

okay so in yet another random query on Google to unearth some good Stanford stuff that's freely available on their website, I found a very interesting problem called "Word Ladders" here. The problem asks you to try and build a chain of words given a start word and an end word such that every pair of consecutive words in your chain differs only by 1 character. Sure was a good find but i was a little upset that while they teach this stuff to undergrads at Stanford, I had not heard about it until after 2years of completing a Masters program in CS at "not Stanford". Nevertheless i set out to try and solve it on my own in JAVA. The classic problem asks you to build the word ladder from an english lexicon but i scaled it down to an Arraylist of words and a start and end word supplied by the user.

Spent some time trying to implement this "suggested algorithm" but since i had a solution ready in my mind i couldn't get myself to complete that implementation. Here's what i came up with. Uses recursion and backtracking. The intention of sharing this source code is to help the curious and the enthusiastic few who want to solve it but might not quite have an idea on where to start.

Also this is somewhat shabby code so if you are reading this and have already solved this problem or are going to, let me know if you come up with something better. Also if you happen to be in the elite group of coders who refuse to solve seemingly trivial problems i suggest you leave a comment at the very least to help me improve it. And if you were looking for a quick solution to an "commonly asked interview question" or a school homework then the good news is i haven't given you the helper functions.. so you cant copy paste and get it to work. You are atleast 30minutes of coding time away from seeing the output :D

The source code:

public static boolean findLadder(String start, String end, List words, List ladder, int position)

{

//1. To be able to use list.set method when backtracking.

ladder.add("");

if(start.equals(end))

{

for(int i=ladder.size()-1;i>position;i--)

ladder.set(i, "");

return true;

}

//2. Find closest words to the "current" start word. (Write your own)

//@param:start: the start word, words: a list of words that you want to scan through.

List closestWordList = findClosest(start, words);

if(closestWordList.size()==0) return false;

for(String eachClosest:closestWordList)

{

List remainingWords = new ArrayList();

remainingWords.addAll(words);

remainingWords.remove(start);

remainingWords.remove(eachClosest);

if(findLadder(eachClosest,end,remainingWords,ladder, position+1))

{

ladder.set(position+1, eachClosest);

ladder.set(0, start); //to set the start word in the final output.

if(position+1==1)

printLadder(ladder);

}

else

{

for(int i=position;i

ladder.set(i, "");

}

}

ladder.set(0, start);

return true;

}

So why did i get back to blogger after a year.. well just happened to read Steve Yegge's blogs and thought of giving my 2cents to the world. I am going to post a few more dry blogs with solutions to a few good problems and hope my fellow developers join the fun.

mom i have cancer...

I have been thinking over this issue for quite a few days and wanted to write about it, but didnt know where to start. not that i am any clearer about the concept now, but i have to blog it if i want the world to think about it.. so here goes.

i guess i got the motivation from one of the spam mails forwarded by my college friend that showed disturbing images of a burnt baby, with an appeal to forward the mail so that the child would earn 10cents for every forward etc etc.  What made me think was not the graphic images but the power these images had, to touch peoples hearts, and contribute to the success of the spam mail. It must have touched my friends heart that he generously forwarded it to the whole of my saboocomps yahoo group, believing he had earned the child a few dollars..sigh!   

If you guys remember, it wasnt so long ago that make-a-wish foundation became popular for fulfilling the last wishes of children suffering from cancer and whose days were numbered.  I thought to myself, is this child luckier than me.  There goes one who gets to meet sharukh, and wow look aish is kissing another kid on his cheek. sweet! But the star meetings soon end and the child is back to reality, the harsh reality, and the impending call of death.  

If i were to revisit my childhood, i can remember several instances when i have cried bitterly for some silly toy, a video game or something that my mom didnt want to buy me.  Not that we were poor or anything, but it was considered to be a "wastage of money".  "we dont need it" came a prompt reply anytime i asked for stuff that i normally never asked for, but was just tempted into buying only because one of my duffer classmate had it.  It isnt a very uncommon scene in middle class families.  Many a times parents go to the extent of explaining to their kids that they have a limited budget and they cant afford to buy that toy or the new game this month with a false assurance that "we'll buy it some other time".   

Now consider this scenario where a child walks up to his parents and tells them, mom dad i have cancer and i dont have many days to live, can i have that new video game.  His parents would have tears in their eyes.  They would now go to any extent to get the kid the game that he so badly wants.  They'll beg, borrow, steal(my english prof used to tell us in school.. if u dont have a pen to write with go arnd and beg, borrow, steal one from ur friends.. i learnt this phrase then), take a loan, sell their jewellery and just about anything it takes to fulfil the childs dream. Why just the parents, think of your arch enemy.  What if he were to walk up to you and tell  you, dude i have been diagnosed with cancer, i prolly have another 6months.  would you forget our age old animosity and be friends with me?  trust me, you would hug him like you hugged your cousin when he stood 20th in the SSC merit list and cry if you happen to be that senti person.  

Why is it that we value people when we know they will no longer be around us for long, than when they are hale and hearty and can possibly live a long life, prolly longer than us.  Why does the call of death suddenly ring a bell somewhere in our brain, or mind, probably heart and makes us think.  Why do people gather around someones dead body and cry their hearts out when they couldnt even find time to call the deceased when he was alive, and lonely and really needed someone to talk to.  Why are people showered with praises and made to look like angels born on earth only after their death.   Why do we stand quietly in a corner and whisper to the person standing next to us and say "he was a nice man".  When will these words of praise come out of our mouths for deserving people while they are alive. 

I have probably discussed more than one issue in this blog but please do think over all the questions that i have raised.  

And as a closing note, i would like to mention, i have had differences with my mother over some issues that are too personal to be mentioned here, and no matter how much i tried to convince her she didnt budge... what makes me think is... instead of saying mom i want XYZ,  would she have agreed had i said, mom i have cancer and i dont have much time left can i have XYZ... 

you bet!

Raj Thackeray, Maharashtra and more..

Hello friends! This is my first blog and look what we have here! a blog on one of the popular marathi politicians Shri Raj Thackeray! not the best topic for a first blog isnt it? Well never mind.  I had a couple of tech topics on my mind but it will take me a lot of time, and research before i can start writing on one of those interesting topics.  Alrite here goes.. 

I have been fascinated by Raj Thackerays personality over the years and couldnt help but notice a close resemblance to the way Thackeray Sr would stand on the podium, talk, make gestures with his hand and offcorse his affirmative tone.  Both of them also share the trait of being good "vyangachitrakaar" or cartoonists.  

Well, i've been watching his videos of late, and noticed that he did infact have a few good points to start a new political party.  One that would fascinate the marathi youth, and in general entertain our masses with all that opponent bashing with marathi bad words. I wont shy away from saying i myself have chuckled when Balasaheb once said "Toh paaswaan yedzava majha maharashtrat yeun mala shahanpana shikavtoy" leave it if you couldnt read it, a translation would make it sound lame.   I would say he definitely lives upto our expectations than what abhishek bachhan did when people expected him to be just as graceful as Bachhan Sr.

Then the other day i saw one of Raj's interview organised by a certain Disha Foundation.  The interviewer seemed to be a sena loyalist yet remained impartial in his choice of questions which included everything from Raj Thackerays views on the Chatt puja to his vision for Maharashtra.  And while Raj entertained the audience by his humorous responses, he maintained his composure, posture and the serious tone that set the mood of the evening.   What was shocking however was the way he responded to 2 of the most serious question of the evening, What are the 3 biggest challenges faced by Maharashtra in the present day world, and What is your vision for Maharashtra of the future.  And Raj could manage nothing but a meek reply which didnt have that usual punch that he has when he addresses a public rally. It was evident that he didnt have much of a vision.  May i say, if we were to by some means get all the public and private schools in Maharashtra to make Marathi a compulsary language, and if we could build a great wall of Maharashtra to prevent the inflow of migrants from UP who come to Mumbai.. Raj Thackeray would be left jobless!

I am no politician, no statistician, just another humble Indian citizen, but if you were to ask me what could i do to take my city,state, country in the progressive direction, i would at the drop of a hat say, make everyone pay taxes.  For once i have realised after coming to US why US is US and why they have so much money available to them for town planning and development and beautification activities.  Goddammit! if you were to buy a laptop worth 800$ you end up shelling out a cool 100$ in taxes! Why the fuck do we go for "open box" and "no receipt" goods in our own country, when we would not even dare to ask for such things here in the US.  Think about it.  One small thing, make everyone pay taxes, right from the hawkers to store keepers, make them issue receipts for anything and everything from a cellotape to a television.  That would leave enough money for our countrys development even after our politicians have eaten up enough money to their hearts content.  

I have never been too interested in politics, never in my life, however it now seems like our country could infact do with a few well educated politicians and statesmen.  Not that i have any intentions of becoming one, but nevertheless this is definitely a good avenue that youngsters should consider, explore and jump into.  And well, on a parting note i would say, go on Raj, you have atleast a few good issues on hand that would make me want to cheer for you!