Alice - Digital Assistant like Jarvis with Smart home automation

Demo:

If the above video has issues here is the link to the demo video

Being lazy I always wished of having something like a Jarvis (for those who don't know what I am saying from Ironman) who would do whatever I say and also because it would be so cool to have something like that. And honestly with all the IoT platforms and advances in AI (with many companies providing API's and libraries) it has become so easy to build one for yourself. And I did just that. When one of our co-founders last visited India he got a Amazon Echo for the team in India. It is such a cool gadget. I was immediately so fascinated by it and I wanted to just build one by myself. So I started exploring and researching where and how to get started. I looked at various IoT devices like Raspberry Pi, Arduino, Electric Imp (we use this one my current company in a vibration sensor we build) etc. I also looked up at some examples to get started . Initially my idea was to just build a home automation device that was voice controlled but after looking at Amazon Echo I decided I could add other functionalities to it too. So I bought a Raspberry pi, an Arduino, a microphone, speakers, a relay module, wires etc for the automation. Now not being an electronics guy I had to look into some examples for putting together the electronics to make the entire automation thing work.

Setting up raspberry pi was easy as it came with a SD card with NOOBS pre-installed. I followed this tutorial to setup the PI. Next we want to control the Arduino with your raspberry pi. There are various ways for that but I used the simple one to use the serial USB cable mode to connect the raspberry pi and arduino and used Nanpy to setup serial communication between them. Once that was done I connected the relay module to the Arduino as illustrated in the following figure.

 (The relay has 2 modes of connection Normally Open and Normally Closed. I used the normally Open one in which the switch is open ie. not connected. In this we connect the power line to common connection point ie. the middle point and the neutral line to normally open point). I connected only a fan and light in my room to it but we can connect more devices to it.

Once I had the hardware ready now its time to breakdown the problem of software. The following diagram explains my system.

As shown above the home assistant is divided in different modules. I wanted the assistant to be completely handsfree. So I needed continuous speech recognition. However using online api for continuous speech is not practically possible. So I needed some sort of trigger that will start the speech recognition. So I used a offline library that listens for a keyword (like Alice in my case). Whenever it recognizes it, it executes a callback which triggers the further process. Further then I start the speech recognition that listens for a command and sends it to the API for speech to text conversion. Once the text is received the intent parser module identifies intent and the entities from the natural language text. Once the intent is identified the corresponding intent handler handles the request. The intent parser and handler module is extendable. So we can add more features (like booking a cab, ordering food etc.) by simply creating a intent parser and intent handler for the feature.

Although there are few issues with this application. The speech recognition api doesn't work properly if the microphone is at some distance from the source. Also the speech recognition doesn't function properly if there is background noise (like when music is playing the background). So to overcome this issue to some extent, I added a feature to run the system in web server mode. In this mode, the raspberry pi runs a webserver and listens for text command, which is then parsed by the intent parser and processed by intent handler. The client sends a text command to web server. So we can use any device like computer or smart phone (although I haven't built an mobile app) to record speech and convert it to text and send the text command. For demo, I created a client for the computer which does it. 

It was fun little exercise and I got to learn a lot. Here is the link for the code for the assistant. Please feel free to check it out and use it as you like (and possibly help improve).

Interesting undocumented Facebook API to identify friends in any personal photos

So last week I was casually browsing through Facebook feed and looking at some random photo posted by a friend. So hovering over the picture the Facebook displayed a rectangle over the face of my friend and showed "Do you want to tag X". This caught my attention. OK so Facebook does image recognition to identify not only faces of people but also identifies who it is. I wondered how FB does it so I spawned up my Chrome Dev Tools, to debug into how this whole thing works.

So it seems that FB has a bunch of div blocks which are the defining the face boxes with the suggestions for identity for each face box in data-recognizeduids. It also had another block of html with the names of the identified users.

OK so now the question is how is this data coming in the first place. It seems it is loaded when one clicks on a photo. So it must be loaded using some ajax call to the server later. Now to find out what call we switch to network tab which shows all the traffic between the browser and FB servers. So now it was all about finding the needle in haystack as there were hundreds of requests. So I started looking for the once with relevant names and struck gold when I found a request "/ajax/pagelet/generic.php/PhotoViewerInitPagelet". 

Then I searched the response for relevant content and found above block of html in the response. The params to the route looked encoded so after decoding them it seemed it sends bunch of params along with the id of the photo. The request looks something like this

https://www.facebook.com/ajax/pagelet/generic.php/PhotoViewerInitPagelet?dpr=2&ajaxpipe=1&ajaxpipe_token=<changed>&no_script_path=1&data={"fbid":"<changed>","set":"<changed>","type":"3","theater":null,"firstLoad":true,"ssid":<changed>,"av":"<changed>"}&__user=1&__a=1&__dyn=<changed>&__req=jsonp_2&__be=0&__pc=PHASED:DEFAULT&__rev=11111&__adt=2

Most of the params don't make much sense except for fbid which looks like the id of the photo. So I played around removing unnecessary params to find the ones that are actually needed for api to work and I found that it needed only the fb id and 2-3 other constant params. Chrome has a pretty neat feature where it allows you to copy a request as CURL request which has all headers and params so you could run it from the command line as is. Using that I replicated the request and found the same response which had the html data containing the information about the users. So I thought if we can use this API to find friends in any photo which might not be uploaded on FB. 

But for the API to work it needs the photo to be on FB. So I thought if we can temporarily upload a photo to FB without publishing it and use the API. Now to upload photos on FB I used the FB Graph API. I needed these photos not to be published and uploaded temporarily for using the API. The Graph Photo Upload API allows to upload the images with options "temporary"=> true and "published"=> false so that the images are uploaded temporarily and not show up in the feed. I created an app on FB Photo Friend Finder which uses publish_actions and user_photos permissions to allow access to the photo API. Once the photo is uploaded the API returns with the id of the photo which is then passed to the above PhotoViewerInitPagelet API which returns HTML data containing details of face suggestions. Now all I needed to do was parse the response to extract the data which can easily be done using HTML parser. I used Nokogiri in ruby for the same.

I put together a small Ruby script to do all of these. So you just run the script with path to image as input param and the script returns the number of people in the photo and identifies the friends. I found this API has a limitation it only suggests people in the photo who are in your FB friend list. I used Koala gem to access FB Graph API and JSON and Nokogiri libraries to parse the API response.
Here is the link to the script.
Script in action.

It was a lot of fun exploring and putting together the script.

Series Torrent Downloader to Dropbox

Blog post after a lonnng time. So I like to watch movies and series a lot. I started following so many series that it became difficult to keep track of what series is aired when and what episode am I on. It was almost like monday one, tuesday another, wednesday third one. And after that search and download it from somewhere( ;) torrents). So for a long time I had this idea that there should be some application that automatically takes care of everything from keeping track of all my series (which episode is aired when and download the next aired episode from torrents to my dropbox and notify me after that). But didn't find time to build one. But finally I was able to put something together. 

So it all started when I came across the popcorn app, which is used for streaming movies and series from torrents. So I just got curious about how it works, and I came the torrent stream library, that the popcorn app used. It basically takes a torrent and generates a stream out of it, and you can write it to a file, stream it on a video player. So I thought if I could upload the stream to some cloud storage. Now dropbox provides a chunked upload feature that can take chunks of file, so essentially you could break down a very large file into chunks and upload it, or resume a partial download using this feature. So I took the chunks in stream provided by library and uploaded chunks to dropbox. It seems even google drive provides an api for it. But for now I have it only for dropbox. As I am open sourcing it, someone might be interested in extending it to other cloud storage services. So now I had the portion that uploaded a torrent to dropbox. Now as this library is in nodejs. But I am not so proficient in JS. So for the other part I used ruby. So I wrote a service that essentially monitors all series that you specify in configs and download them to dropbox using the nodejs script. It uses the tv maze api, to get the next episode for each series that it needs to download. So it essentially runs like a cron, every 2 hours it gets an episode of a series from api checks if that episode is out for download, if not it records it in a DbStore. (I used redis as my db store.) and sleeps. Next time when it runs it checks if the next episode in my db store is available. Now if it is then it downloads the file to dropbox, and then updates the next episode to download in db store. 

Once both scripts were done, I thought of deploying it to my (free) heroku instance. However the challenge with that is how do I trigger it at specific times in a day. It does provide something called a worker dyno, but I don't have much idea if heroku provides a free plugin for scheduling scripts. So I came up with this. I run a web server (I used sinatra), and have a continuous background thread that actually runs the above task, then sleeps for x hours and then comes back, so essentially behaving like a scheduled task. And using this technique I could also add a route that simple dumps the logs of the task to monitor if everything went well. Now there was one more small issue with heroku. Heroku shuts down your app if there is inactivity for some time( I think 15 minutes.) But now I cannot afford my task shutting down as I don't have any way to track if it shutdown in between a download. So to keep it up all the time, I used a service (pingdom) that sends a ping to the app every 5 minutes. It is essentially used to track the uptime of a service. Ironically, I used it to keep my app up all the time.

I have open sourced it on github. You could check it out, and help me improve it. And use it at your own risk. It can be deployed in both modes as a webserver on heroku or a cron on some other cloud instance. Although to use it you need to create a app on your dropbox, authorize it and get a access token. And add the access token to dnode.js. It is the nodejs script that is actually used for downloading the torrent to dropbox. If you want yourself to be notified you could also create a mailgun account and create a key and add it to constants.yml that is used to send emails to your specified email. Otherwise you could comment the mail sending line. You also need a redis node on cloud, which is used as a db store. I used redislabs service which provides a 25 MB node for free. And to add the series you want to monitor you could add it to the list in constants.yml.

Gmail Notifier for Mac OSX

Recently, I came across this gem called terminal-notifier, it allows you to send Mac OS X User Notifications. It also comes with a command-line tool. I was thinking of some interesting use-case for it. Then an idea struck, how about an application that notifies when I receive a mail contains specific text, or from some specific user.
Now I'll give a little background about how and why this app. In our office on any special occasion, people get chocolates or sweets and put it in cafeteria, and then mail in a common group to let people know. As it happens, I don't have the habit to check my mails very frequently, and often miss out on important mails at right time. So how about an script that checks for mails containing certain words or from a specific user.
So the task was simple check for the new emails and if they contain a match for the given criteria in my case it was if the mail subject or the body contains words sweets or chocolates then send a User Notification. To get the emails I used the gmail gem. Now this gem needs your username and password. But storing them as plaintext in the script is not smart from security point. So I was looking for a simple and reliable option to store and retrieve my username and password. So I used OSX keychain tool to store the sensitive information. To retrieve the email and password I used the commandline tool "security". Initially to store the username and password in OSX Keychain use,

security add-internet-password -a username -w password -s http://mail.google.com

And then to retrieve it use,

security 2>&1 find-internet-password -ga username | grep password | cut -d '"' -f2

Moving forward once I get the username and password, I logged into the gmail account by,

gmail = Gmail.new(username, password)

After logging in I searched through the unread mails for the search queries in both subject and body of mail. Once I find the mail containing the search term I fire a notification. Now as this gem didn't have a sound notification I used the system sounds file and played it using the afplay command as,

afplay -v 4 -q 1 /System/Library/Sounds/Glass.aiff

and then fire the user notification by calling,

TerminalNotifier.notify("Subject : #{content_to_display}", :title => 'Title')

and then marked the mail as read so that it didn't come up when next time the cron runs. Finally to continuously scan through my inbox I set up this script as a cron that will run every minute,
*/1 * * * * ruby gmail_notifier.rb

You can find the complete script on github here

A simple No-SQL key-value db using self-modifying ruby script: An interesting application of Ruby's Reflection API

I am basically a java developer and I recently started learning ruby and was amazed at the ease in which you can develop in it and elegance of the language. The easiest way to learn any programming language is to develop simple applications in it that use various features of language. So when going through the various features I came across Reflection and Metaprogramming in Ruby. A very powerful feature in ruby. It amazing how the eval function allows one to write and execute ruby code dynamically. So while thinking of an application using this feature I came up with the following application.
It is a simple No-SQL key-value db that stores data in hash in ruby. The first line declares a hash. Then the following part of script reads its own code and uses eval function to execute it declare the hash. Then depending upon the function called GET/SET it either retrieves the value associated with the key or sets a new key/value in hash. Then it simply stores the new hash in the source code.
Here is the source code for the ruby script:

hash={"1"=>"Narendra", "2"=>"Mangesh", "3"=>"Viru", "4"=>"Virendra", "5"=>"Genh"}
z=[]
err_msg="ruby #{__FILE__} <GET/SET> <key_to_search/key_to_set> <not_required/value_to_set>"
if ARGV.length<2 && (ARGV[0]!="GET" || ARGV[0]!="SET")
  puts err_msg
  exit
end
if ARGV[0]=="SET" && ARGV.length!=3
  puts err_msg
  exit
end
File.open(__FILE__,'r'){|f| f.each_line {|l| z<<l}}
c=eval(z[0])
if ARGV[0]=="GET"
  puts c[ARGV[1]] if c.include?(ARGV[1])
elsif ARGV[0]=="SET"
  c[ARGV[1]]=ARGV[2]
  z[0]="hash="+c.inspect+"\n"
  File.open(__FILE__,'w'){|f| z.each{|x| f<<x}}
end

Hacking the Little Alchemy game with only Chrome in less than an hour

Today my friend introduced me to this cute little but addictive game named Little Alchemy.
So playing around with it for few minutes and looking at the time it took to find new elements I wondered how much time it would take to find all. Not having the patience to play whole game to determine all elements I thought why not do it the hacker style. So popped open the Chrome Web Inspector and looked around in the network tab to see what all data is sent by littlealchemy web page. I noticed it stores all data in application cache and retrieves from there. Looking around the js files for something interesting I struck gold when I found the logic in alchemy.js file. It seemed to make ajax call to 2 files /base/names.json and /base/base.json. Then I looked into these files and found that the mapping of all the elements was stored in base.json in array forms and all the names of elements were stored in names.json. After finding this it was a piece of cake to hack together a javascript code to display the combinations for all elements. So then I opened the javascript console and put together this piece of code to print the combinations for all elements and dumped it to a html file. You can check the output here.

And here is the piece of javascript code

var base,names,i,j;
$.ajax({
          type: "GET",
          url: "http://littlealchemy.com/base/base.json",
          }).done(function( data ) {
          base=data;
});
$.ajax({
          type: "GET",
          url: "http://littlealchemy.com/base/names.json",
          }).done(function( data ) {
          names=data;
});
for(i=4;i<base.base.length;i++){
   for(j=0;j<base.base[i].length;j++){
      if(names.lang[Number(base.base[i][j][0])]==undefined){
         console.log(names.lang[i]+ " doesn't have any combination");
         continue;
      }
      console.log(names.lang[Number(base.base[i][j][0])]+" + "+names.lang[Number(base.base[i][j][1])]+" => "+names.lang[i]);
   }
}

So damn true: "Necessity the mother of building cool stuff"

Few days back, some hardware issue with my hard drive left it irrepairable and all my data was lost including softwares, movies, music. (Thank god I use github to host all my projects).

Now loss of movies and softwares is no big deal. But finding one's song collection is difficult as one has a particular taste for music. But good for me all that music is stored in my IPod. But as we all know Apple doesn't allow one to copy music files from IPod to computer. So what I did was look around some way to get my music from IPod to PC. I opened the IPod in USB storage mode and looked at where the files are stored. I found all the files but they were stored with random (unrecognizable) names in it. So for starters I copied all those files to my PC. Then I looked for a way to get the files some understandable names. But naming around 1000 songs listening to each one is not the way a geek would do it. So then I wrote this java app that scanned through all mp3 files and read the ID3 tags to get the song title and renamed all songs. Cool so it scanned all files and did the task in few minutes. Then I thought why not modify it a little and let it scan through your entire computer and look for mp3 files, rename them using song title and store them in a single directory where the songs are categorized in subdirectories using the album  name or artist name. In this way all the duplicates of a single mp3 would also be removed.

So this Mp3Manager is a console utility in java that takes as input the name of root directory to store all your music files and type of categorization to use to store the music files in directories(album name or artist). It is available on github

Read the readme.md to know how to use it. Let me know if you like it or if you would like any modifications to it.

Fuzzy matching autocomplete library with inbuilt standalone http server in java

Past couple of days I had this idea in mind of implementing a autocomplete that uses fuzzy matching. For fuzzy matching of a partial string with all the strings in dictionary it uses the Levenshtein distance. Now finding the Levenshtein distance of given string with each string in dictionary is very inefficient. So I used the idea described here. Converted it to java and modified it to fit the needs.

It is available in 2 modes. First is the Http server mode in which you run the standalone server and call it directly from your ajax script.It returns data in json format with decreasing scores. For this you need to configure it by providing the file name containing the words for suggestion. To use it run the server and then use this url to get the results   http://server-ip/autoc?word=word_for_autocomplete&tf=max_typos_allowed

Specify the word_for_autocomplete and the max_typos_allowed parameter.

The second is you can embed it directly in your application by first creating trie and then calling the getResult() method in CHandler class. See the source code for better understanding. A sample main method is given which uses the second method.

You can find the source code for the project here.

If you like the idea and want to improve it or port it to other languages fork me github.

Find a word in 2D matrix

I read about this problem in TC forums.

How to efficiently search for a word in a 2D matrix of letters , given the conditions that , we can start at any position and for every position we can go to only the adjacent positions (vertically,horizontally and diagonally ,i.e in all 8 directions).
Example- searching topcoder in this matrix :
t o p t
g f c q
t y o d
d f r e

My solution to this problem is a simple recursive DFS. Along with yes or no it highlights the word itself in the matrix by displaying the word and '-' at all other locations.  My implementation is as shown below.

You can also find it here

import java.util.*;
import java.io.*;
public class Main{
        public static int flag=0,m,n,dx[]={0,0,1,-1,1,-1,-1,1};
        public static int dy[]={1,-1,0,0,1,-1,1,-1};
        public static char wrd[];
        static class S{char a;int p,x,y;
                S(){}
                S(char b,int pos,int c,int d){a=b;p=pos;x=c;y=d;}
        }
        public static LinkedList<S>vis=new LinkedList<S>();
        public static LinkedList<S>init=new LinkedList<S>();
  public static Stack<S>fc=new Stack<S>();
        public static char mat[][];
        public static void main(String args[]) throws Exception{
                BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
                m=Integer.parseInt(br.readLine());
                n=Integer.parseInt(br.readLine());
                int i,j;
    long a=System.currentTimeMillis();
                mat=new char[m][n];
    wrd=br.readLine().toCharArray();
                for(i=0;i<m;i++) mat[i]=br.readLine().toCharArray();
                for(i=0;i<m;i++) for(j=0;j<n;j++) if(mat[i][j]==wrd[0]){init.add(new S(wrd[0],0,i,j));}
                for(i=0;i<init.size();i++) {solve(init.get(i));if(flag==1) break;}
    if(flag==0) {System.out.println("NO");return;}
    for(i=0;i<n;i++) for(j=0;j<n;j++) mat[i][j]='-';
    S tp=null;
    for(;!fc.isEmpty();) {tp=fc.pop();mat[tp.x][tp.y]=tp.a;}
    for(i=0;i<m;i++) {
     for(j=0;j<n;j++) System.out.print(mat[i][j]);
     System.out.println();
    }
    System.out.println((System.currentTimeMillis()-a)+"ms");
        }
        public static void solve(S s){
   int i,j;
   if(s.p==wrd.length-1){System.out.println("YES");fc.push(s);flag=1;return;}
            for(i=0;i<8;i++) 
    if((s.x+dx[i])>0&&(s.y+dy[i])>0&&(s.x+dx[i])<m&&(s.y+dy[i])<n&&mat[s.x+dx[i]][s.y+dy[i]]==wrd[s.p+1]) 
     solve(new S(wrd[s.p+1],(s.p+1),(s.x+dx[i]),(s.y+dy[i])));
            if(s.p>=0&&s.p<wrd.length&&flag==1){fc.push(s);}
        }
}

21
21
topcoder
ataabmtdvegybznbzqwtb
odiurtrdutatureiortzn
godytqoqdxjwvxbnxwaxm
jhhxicpsqzfaxcctcefck
lcjsoideqlcwevkovrfyj
padervwrtjjthnjpbtuth
qacjgkaektdewmhsnyyfg
zbxbigjdgrythhgdmudef
crufjakjerwwsdffliywd
vqzbnkmfjtgrwkdgkodas
naohuyhfgofgfjuhjrvaa
mjgfdskuifyiumyjgleaw
lrepwoiepodsobtbdjdcf
hfueydfughyuicavsfosh
iovhjuhodjitgzzcaxctg
hjgsiugfyiusfgioqzpeb
jbhsfgudfghdhfghgsoqv
fgyhdutsfyirtyiytrtac
gjihysoduftfuihfytadx
gyrwydfiuzadytiudfufs
jgiosjtisodfstotisryt
YES
---------------------
---------------------
---------------------
---------------------
---------------------
---------------------
---------------------
---------------------
---------------------
---------------------
-----------------r---
------------------e--
------------------d--
------------------o--
------------------c--
------------------p--
------------------o--
------------------t--
---------------------
---------------------
---------------------
125ms

Trie datastructure

Trie is a very useful data structure. It finds many uses in string based applications like dictionary, autocomplete, spell check etc.

This blog post is not a tutorial on trie but I am simply sharing my trie implementation in java here.

You could find many other implementations on the internet but I really struggled understanding the other implementations especially the function of getting complete words matching a prefix. So I decided to write my own. Here is my implementation.

You can also find it here

class Node{
	public char d;public boolean e;
	public LinkedList<Node>c;
	public Node(){}
	public Node(char a){d=a;e=Boolean.FALSE;c=new LinkedList<Node>();}
	public Node sub(char a){
		int i;
		if(c.isEmpty()) return null;
		for(i=0;i<c.size();i++)
			if(c.get(i).d==a) return c.get(i);
		return null;
	}
}
class Trie{
	Node root;
	public Trie(){
		root=new Node(' ');
	}
	public void add(String a){
		Node n,cur=root;int len=a.length(),i,j;
		if(len==0) cur.e=Boolean.TRUE;
		else{
			for(i=0;i<len;i++){
				if(cur.sub(a.charAt(i))==null) break;
				cur=cur.sub(a.charAt(i));
			}
			while(i<len){
				n=new Node(a.charAt(i));
				cur.c.add(n);
				cur=cur.sub(a.charAt(i));
				i++;
			}
			cur.e=Boolean.TRUE;
		}
	}
	public boolean search(String a){
		Node cur=root;int i,j,len=a.length();
		for(i=0;i<len;i++) {
			if(cur.sub(a.charAt(i))==null) return Boolean.FALSE;
			cur=cur.sub(a.charAt(i));
		}
		if(i==len) return Boolean.TRUE;
		return Boolean.FALSE;
	}
	public boolean searchw(String a){
		Node cur=root;int i,j,len=a.length();
		for(i=0;i<len;i++) {
			if(cur.sub(a.charAt(i))==null) return Boolean.FALSE;
			cur=cur.sub(a.charAt(i));
		}
		return cur.e;
	}
	public String next(String pre){
		Node cur=root;int i,len=pre.length();
		for(i=0;i<len;i++) {
			if(cur.sub(pre.charAt(i))==null) return "";
			cur=cur.sub(pre.charAt(i));
		}
		String res="";
		if(i==len) {
			for(Node a:cur.c)
				res=res+String.valueOf(a.d);
			return res;
		}
		return "";
	}
	public LinkedList<Node> getnode(String pre){
		Node cur=root;int i,j,len=pre.length();
		for(i=0;i<len;i++) {
			if(cur.sub(pre.charAt(i))==null) return null;
			cur=cur.sub(pre.charAt(i));
		}
		if(i==len) return cur.c;
		return null;
	}
	public Vector<String>all=new Vector<String>();
	String tm;
	public Vector<String> getStrings(String pre){
		rec(pre);
		return all;
		//for(String f:all) System.out.println(f);
		//System.out.println(all.size());
	}
	public void rec(String pr){
		LinkedList<Node>nod=getnode(pr);
		for(Node n:nod){
			tm=pr+String.valueOf(n.d);
			if(n.e) {all.add(tm);}
			else {
				rec(tm);
			}
		}
	}
}

Levenshtein Distance:(How big the social network for a word is?)

Last week I came across this problem on codeeval.com 

Levenshtein Distance 

Description:

Two words are friends if they have a Levenshtein distance of 1 (For details see http://en.wikipedia.org/wiki/Levenshtein_distance). That is, you can add, remove, or substitute exactly one letter in word X to create word Y. A word’s social network consists of all of its friends, plus all of their friends, and all of their friends’ friends, and so on. Write a program to tell us how big the social network for the word 'hello' is, using this word list https://raw.github.com/codeeval/Levenshtein-Distance-Challenge/master/input_levenshtein_distance.txt

Input sample:

Your program should accept as its first argument a path to a filename.The input file contains the word list. This list is also available at https://raw.github.com/codeeval/Levenshtein-Distance-Challenge/master/input_levenshtein_distance.txt.

Output sample:

Print out how big the social network for the word 'hello' is. e.g. The social network for the word 'abcde' is 4846.

Now there are many ways of solving this as you might find on the internet. Most of them depend on finding the Levenshtein distance for calculating the neighbors of a word. But the problem I found that was it takes O(n2) time to calculate Levenshtein  distance(edit distance using dp) between 2 words. After this it all gets down to doing a DFS starting with 'hello'. This approach takes a lot of time to run. 

My approach for overcoming the problem with calculating the neighbors is as follows. Now we know that in this we need only the words that are at a distance of 1. Now these words are the once that can be obtained either by deleting a character, or replacing a character. So I simply simulated it using for loops and generating all possible words formed by deleting or adding or changing a letter and look it up in dictionary. For efficient storing of dictionary and lookup I used 2 dimensions. ie. An array of HashSet where HashSet at index i stores only words of length i.

You can find the full program here

Here is the logic for getting all words at distance 1:

public static void addwords(String wrd){
	int i,len=wrd.length();
	char z;
	StringBuffer sb;
	String b="";
	for(i=0;i<len;i++){
		sb=new StringBuffer(wrd);
		sb=sb.deleteCharAt(i);b=sb.toString();
		if(h[len-1].contains(b)){
			st.add(b);h[len-1].remove(b);
		}
	}
	for(i=0;i<=len;i++){
		for(z='a';z<='z';z++){
			sb=new StringBuffer(wrd);
			sb=sb.insert(i,z);
			b=sb.toString();
			if(h[len+1].contains(b)){
				st.add(b);h[len+1].remove(b);
			}
		}
	}
	for(i=0;i<len;i++){
		for(z='a';z<='z';z++){
			sb=new StringBuffer(wrd);
			sb.setCharAt(i,z);
			b=sb.toString();
			if(h[len].contains(b)){
				st.add(b);h[len].remove(b);
			}
		}
	}
}

AddAGram: A Puzzle challenge from ITA Software

Last week I came across this page where ITA Software posted a few puzzle challenges it used in its hiring process. I found the one named AddAGram very interesting and then decided to solve it.
Here is the question:

An "add-a-gram" is a sequence of words formed by starting with a 3-letter word, adding a letter and rearranging to form a 4-letter word, and so on. For example, here are add-a-grams of the words "CREDENTIALS" and "ANACHRONISM":

ail + s = sail + n = nails + e = aliens + t = salient + r = entrails + c = clarinets + e = interlaces + d = CREDENTIALS (length 11)

mar + c = cram + h = march + s = charms + o = chromas + n = monarchs + i = harmonics + a = maraschino + n = ANACHRONISM (length 11)

Test your own credentials: given the dictionary found here, what is the longest add-a-gram?

 Initially I thought it would be solvable using a trie by inserting the words in dictionary in a trie and then simply searching the trie for the longest path down with each node after 3 node which is an end node ie. each node after third node marked as end of some word. But then I realized that it was wrong after half way coding it. Then I went back to square one and rethought the problem and then realized that it can be solvable only by searching. So then I came up with the following approach. I started with the longest word in the dictionary and then found the next word that is at a distance of 1 deletion from the previous word then pushed all those on a stack and for each word in the stack searched for next word at a distance of 1. So I basically created a graph from the words in dictionary t runtime and ran a DFS on it. The biggest hurdle or problem with this approach is searching through the whole dictionary for a word of that length and then backtracking when error occurs is very costly. So then I came up with a simple optimization technique to reduce the amount of words to be searched by storing the words in a array of  vectors where vector at index i stores words of length i so dividing the access in 2 dimensions gives access to the all words of length i directly by calling dict[i].get(). Then finally we can rebuild the original sequence in the visited list of nodes.
It is written in java and it takes ~20 secs to run wit the dictionary of words given here.


Here is only the main logic part of the code:

You can find the complete program here

public class AddAGram{
 public static Vector<String>dic[];
 public static Stack<String>s;
 public static HashSet<String>vis=new HashSet<String>();
 public static boolean check(char []l,char []s){
  int i,j,len=l.length;
  for(i=0;i<s.length;i++)
   for(j=0;j<l.length;j++)
    if(s[i]==l[j]&&l[j]!=0) {s[i]=0;l[j]=0;len--;}
  if(len==1) return true;
  return false;
 }
 static void addAll(String str){
  int l=str.length()-1,tot=dic[l].size();
  String other="";
  for(int i=0;i<tot;i++){
   other=dic[l].elementAt(i);
   if(check(str.toCharArray(),other.toCharArray())&&!vis.contains(other))
    s.push(other);
  }
 }
 static char diff(String small,String large){
  StringBuffer sb=new StringBuffer(large);
  for(int i=0;i<small.length();i++)
   sb=sb.deleteCharAt(sb.indexOf(String.valueOf(small.charAt(i))));
  return sb.charAt(0);
 }
 public static void generateOriginal(String start,String end){
  LinkedList<String>list=new LinkedList<String>();
  for(String a:vis) list.add(a);
  String next="",prev=start;
  list.remove(start);
  int k,j=end.length();
  for(int i=4;i<=j;){
   for(k=0;k<list.size();k++){
    if(list.get(k).length()==i){
     if(check(list.get(k).toCharArray(),prev.toCharArray())){
      next=list.remove(k);i++;
      System.out.println(prev+"+"+diff(prev,next)+"="+next);
      prev=next;break;
     }
    }
   }
  }
 }
 public static void main(String args[]) throws Exception{
  dic=new Vector[30];
  String str;int i,j,k;
  for(i=0;i<30;i++) dic[i]=new Vector<String>();
  InputReader sc=new InputReader(new FileInputStream("WORD.LST"));
  long init=System.currentTimeMillis();
  while(!sc.isExhausted()){
   str=sc.readLine();dic[str.length()].add(str);
  }
  int z=0;
  String word="",tmp="";Vector<String>v;
  for(i=29;i>2;i--){
   v=dic[i];
   for(z=0;z<v.size();z++){
    word=v.elementAt(z);
    s=new Stack<String>();
    vis.clear();
    s.push(word);
    while(!s.empty()){
     tmp=s.pop();
     addAll(tmp);
     vis.add(tmp);
     if(tmp.length()==3) {
      generateOriginal(tmp,word);
      System.out.println("Time taken : "+(System.currentTimeMillis()-init));
      return;
     }
    }
   }
  }
 }
}