Monday, November 7, 2011
Sunday, November 6, 2011
Padovan String Sequence Problem
Problem Find number of occurrences of input string in nth Padovan String P(n)
where P(0) = 'X', P(1)='Y' and P(2)='Z'
Input Parameters: needle string str to search for and number n
Conditions to handle:
if number n is >= 40 return -1
if string str has any other characters then X,Y and Z return -1
Solution
Solved this problem for preliminary round of one programming contest.
PadovanString.java
[code language="java"]
public class PadovanString {
public int stringOccurrences(int n, String str){
if (n >= 40)
return -1;
if (str.replaceAll("X|Y|Z", "").length() > 0)
return -1;
String res= pad(n);
/* print nth Padovan String
System.out.println(res);*/
/*replace search string with null and caculate number of occurences*/
return (res.length() - res.replaceAll(str, "").length())/(str.length());
}
public String pad(int n){
if (n == 0) return "X";
if (n == 1) return "Y";
if (n == 2) return "Z";
else return pad(n-2) + pad(n-3);
}
}
[/code]
Test.java
[code language="java"]
public class Test {
public static void main(String []args)
{
PadovanString p = new PadovanString();
System.out.println(p.stringOccurrences(20,"YZ"));
}
}
[/code]
Also, Length of Nth padovan string = Nth Padovan number
where P(0) = 'X', P(1)='Y' and P(2)='Z'
Input Parameters: needle string str to search for and number n
Conditions to handle:
if number n is >= 40 return -1
if string str has any other characters then X,Y and Z return -1
Solution
Solved this problem for preliminary round of one programming contest.
PadovanString.java
[code language="java"]
public class PadovanString {
public int stringOccurrences(int n, String str){
if (n >= 40)
return -1;
if (str.replaceAll("X|Y|Z", "").length() > 0)
return -1;
String res= pad(n);
/* print nth Padovan String
System.out.println(res);*/
/*replace search string with null and caculate number of occurences*/
return (res.length() - res.replaceAll(str, "").length())/(str.length());
}
public String pad(int n){
if (n == 0) return "X";
if (n == 1) return "Y";
if (n == 2) return "Z";
else return pad(n-2) + pad(n-3);
}
}
[/code]
Test.java
[code language="java"]
public class Test {
public static void main(String []args)
{
PadovanString p = new PadovanString();
System.out.println(p.stringOccurrences(20,"YZ"));
}
}
[/code]
Also, Length of Nth padovan string = Nth Padovan number
Saturday, November 5, 2011
Urban dictionary and Youtube search for cool slang's and their usage using Python
Urban dictionary is a user maintained dictionary of slang's. A thesaurus search for a word gives all the related slang's, related words could be antonym also.
Youtube, not long ago, started video comment search which is still in beta. Here, comments on all videos are searched for entered search term.
Requirement : To get related slang's from urban dictionary for a particular word, and then query youtube usage of those slang's.
[sourcecode language="python" wraplines="false"]
from BeautifulSoup import BeautifulSoup,NavigableString
import nltk
import os
import re
import urllib2
import webbrowser
import time
def get_soup(url):
#get soup object for the url
try:
page = urllib2.urlopen(url)
except urllib2.URLError, e:
print 'Failed to fetch ' + url
raise e
try:
soup = BeautifulSoup(page)
except HTMLParser.HTMLParseError, e:
print 'Failed to parse ' + url
raise e
return soup
def get_related(word):
word_list=[]
print 'Fetching related words for '+word+'........'
soup=get_soup('http://www.urbandictionary.com/thesaurus.php?term='+word)
for td in soup.findAll('td', {'class':'word'}): #each row
rel_word=td.find('a').contents[0].encode()
print rel_word
word_list.append(rel_word)
return word_list
def get_comment(word,npages):
print 'Fetching comments for '+word+'........'
comments =[]
for i in range(1,npages+1):
soup= get_soup('http://www.youtube.com/comment_search?q='+str(word)+'&ld=1&comment_only=1&hl=en&so=pagerank&page='+str(i))
for span in soup.findAll('span', {'class':'comment-result-comment'}): #each row
comment =''
for text in span.findAll(text=True):
comment = comment+ ' '+ text
comment=re.sub('[ ]+|\n|\r',' ',comment.strip())
comment=re.sub('^[0-9]+[ ]+','',comment)
comments.append(comment.encode('utf-8'))
time.sleep(6)
return comments
def main():
word='spooky'
npages=2
word_list=get_related(word)
#word_list = ['spooky']
file1=open('word_list','w')
for w in word_list:
for comment in get_comment(w,npages):
file1.write(comment+'\n')
file1.close()
if __name__ == '__main__':
main()
[/sourcecode]
Youtube, not long ago, started video comment search which is still in beta. Here, comments on all videos are searched for entered search term.
Requirement : To get related slang's from urban dictionary for a particular word, and then query youtube usage of those slang's.
[sourcecode language="python" wraplines="false"]
from BeautifulSoup import BeautifulSoup,NavigableString
import nltk
import os
import re
import urllib2
import webbrowser
import time
def get_soup(url):
#get soup object for the url
try:
page = urllib2.urlopen(url)
except urllib2.URLError, e:
print 'Failed to fetch ' + url
raise e
try:
soup = BeautifulSoup(page)
except HTMLParser.HTMLParseError, e:
print 'Failed to parse ' + url
raise e
return soup
def get_related(word):
word_list=[]
print 'Fetching related words for '+word+'........'
soup=get_soup('http://www.urbandictionary.com/thesaurus.php?term='+word)
for td in soup.findAll('td', {'class':'word'}): #each row
rel_word=td.find('a').contents[0].encode()
print rel_word
word_list.append(rel_word)
return word_list
def get_comment(word,npages):
print 'Fetching comments for '+word+'........'
comments =[]
for i in range(1,npages+1):
soup= get_soup('http://www.youtube.com/comment_search?q='+str(word)+'&ld=1&comment_only=1&hl=en&so=pagerank&page='+str(i))
for span in soup.findAll('span', {'class':'comment-result-comment'}): #each row
comment =''
for text in span.findAll(text=True):
comment = comment+ ' '+ text
comment=re.sub('[ ]+|\n|\r',' ',comment.strip())
comment=re.sub('^[0-9]+[ ]+','',comment)
comments.append(comment.encode('utf-8'))
time.sleep(6)
return comments
def main():
word='spooky'
npages=2
word_list=get_related(word)
#word_list = ['spooky']
file1=open('word_list','w')
for w in word_list:
for comment in get_comment(w,npages):
file1.write(comment+'\n')
file1.close()
if __name__ == '__main__':
main()
[/sourcecode]
Thursday, October 20, 2011
Sentiment analysis using Naive Bayes Algorithm
Experimented with simple Naive Bayes for sentiment classification.
Naive Bayes code is available here chatper6/docclass.py and training data is available here
Changed the getwords() function in docclass.py
- to remove special characters like single-quote, comma, full stop from text
- to split based on white spaces instead of non word character because it ignored emots with non word character split and
- included nltk stopwords corpus check.
[sourcecode language="python"]
def getwords(doc):
doc=re.sub('\.+|,+|!+|\'','',doc)
splitter=re.compile('\\s+')
#print doc
# Split the words by non-alpha characters
words=[s.lower().strip() for s in splitter.split(doc)
if s.lower().strip() not in nltk.corpus.stopwords.words('english') ]
print words
# Return the unique set of words only
return dict([(w,1) for w in words])
[/sourcecode]
For training data, converted ';;' separated data file to '\t' separated file because csv.reader() function
was not accepting two symbol delimiters.
Changed sampletrain function to train classifier on training data file "testdata.manual.2009.05.25".
[sourcecode language="python"]
def sampletrain(cl):
read = csv.reader(open('pos 1', 'rb'), delimiter='\t')
cnt = 1
for row in read:
if row[0] == 0:
sent = 'bad'
else:
sent = 'pos'
data = row[5]
cl.train(data,sent)
cnt = cnt+1
print cnt
[/sourcecode]
Naive Bayes code is available here chatper6/docclass.py and training data is available here
Changed the getwords() function in docclass.py
- to remove special characters like single-quote, comma, full stop from text
- to split based on white spaces instead of non word character because it ignored emots with non word character split and
- included nltk stopwords corpus check.
[sourcecode language="python"]
def getwords(doc):
doc=re.sub('\.+|,+|!+|\'','',doc)
splitter=re.compile('\\s+')
#print doc
# Split the words by non-alpha characters
words=[s.lower().strip() for s in splitter.split(doc)
if s.lower().strip() not in nltk.corpus.stopwords.words('english') ]
print words
# Return the unique set of words only
return dict([(w,1) for w in words])
[/sourcecode]
For training data, converted ';;' separated data file to '\t' separated file because csv.reader() function
was not accepting two symbol delimiters.
Changed sampletrain function to train classifier on training data file "testdata.manual.2009.05.25".
[sourcecode language="python"]
def sampletrain(cl):
read = csv.reader(open('pos 1', 'rb'), delimiter='\t')
cnt = 1
for row in read:
if row[0] == 0:
sent = 'bad'
else:
sent = 'pos'
data = row[5]
cl.train(data,sent)
cnt = cnt+1
print cnt
[/sourcecode]
Wednesday, October 5, 2011
Socially adept programmers
The programmer stereotype as described in personality traits of great programmer
Programmers who value social image present themselves so to conform to a perception of society's preferred type of personality. Some ways in which they manipulate perception of society are
The stereotypical programmer is a shy young man, either scrawny or overweight, who works by himself in an 8’x8’ cubicle in a bigger room of dozens cubicles, each holding someone just like him. He intensely concentrates on writing cryptic instructions to coax a computer to do what is needed. He devotes his evenings, weekends, and summers to work. He has no social life and any hobbies he may have resemble his work. In some companies he is regarded as an indispensable genius; in others he is tolerated as an eccentric artist. (McConnell, 1999)
Programmers who value social image present themselves so to conform to a perception of society's preferred type of personality. Some ways in which they manipulate perception of society are
- When asked to stay little longer they decline by saying that they have some personal commitments, they need to spend time with family, when, in fact they will be working on some open source project or breaking into high profile gov network.
- They don't use Facebook or twitter often, so they develop a program that autonomously posts status and comment on others feed periodically(using some NLP and ML techniques) to show that they spend a lot of time on social networks and are social.
- They are aware that in social conversation what matters is not the correctness of the argument, but how much laughter it provokes and how much interesting it is.
- They don't use IT jargon in social conversations, even if they know everything about them and in fact, make fun of people who use them(making fun of others is most frequently used technique in social conversations).
- They identify themselves with hippie programmers instead of nerd programmers.
- They have a girlfriend or at least this is what they tell to others.
- They never tell programming as their hobby even if programming is at the top on the list.
Thursday, September 22, 2011
Funny Incident @Work
Today, my manager asked me to send him my profile in one-page ppt. After I sent him the document he replied back saying 'You haven't included number of years of experience in it. Update it & send again' .
But I included that in document. So, to clarify, I call him.
Me: Hi <manager> , its regarding the profile. Years of experience, I have mentioned it in the document.
Manger: Where is it? I don't see it.
Me: Its in first sentence of document itself.
Manager: You mentioned it in letters. ah.. you should have mentioned it in digits.
Me: Okay.Anything else.
Manager: No, Nothing else. Just update it, change it to digit and resend me the document.
He wanted me to replace the word with a single digit and resend him the document. Amazing!!
Such incidents really provoke laughter and provide amusement at work.
But I included that in document. So, to clarify, I call him.
Me: Hi <manager> , its regarding the profile. Years of experience, I have mentioned it in the document.
Manger: Where is it? I don't see it.
Me: Its in first sentence of document itself.
Manager: You mentioned it in letters. ah.. you should have mentioned it in digits.
Me: Okay.Anything else.
Manager: No, Nothing else. Just update it, change it to digit and resend me the document.
He wanted me to replace the word with a single digit and resend him the document. Amazing!!
Such incidents really provoke laughter and provide amusement at work.
Monday, September 5, 2011
Extracting movie title from torrent file name using Regular Expression
Movie files downloaded from torrent sites has file name which contains format types (like dvdrip, dvdscr, xvid etc), year, comments , user names and of course movie name. We want to extract movie name from this file names.
Based on the observation that
'(.*?)(dvdrip|xvid| cd[0-9]|dvdscr|brrip|divx|[\{\(\[]?[0-9]{4}).*'
This regular expression will find file names where we have dvdrip, brrip, xvid(we can specify any number of values here) or year and finds first of any one of the appearing patterns because we have used lazy parsing here using .*?. We then extract the first back referenced part \1.
Secondly, to remove the part within brackets we use
'(.*?)\(.*\)(.*)' regular expression.
Following code snippet gets the movie names(to an extent) from file name.
import re
fr = open('filenameslist.txt', 'r')
fw = open('movienames.txt', 'w')
for line in fr:
text = line.strip()
text1 = re.search('([^\\\]+)\.(avi|mkv|mpeg|mpg|mov|mp4)$', text)
if text1:
text = text1.group(1)
text = text.replace('.', ' ').lower()
text2 = re.search('(.*?)(dvdrip|xvid| cd[0-9]|dvdscr|brrip|divx|[\{\(\[]?[0-9]{4}).*', text)
if text2:
text = text2.group(1)
text3 = re.search('(.*?)\(.*\)(.*)', text)
if text3:
text = text3.group(1)
# print text
fw.write(text + '\n')
fr.close()
fw.close()
Output can be improved further observing things like we can replace characters like underscore with space, we can check for only four digits where next character is non word character ..
| Input File names | Output Achieved | |
|---|---|---|
| countdown.to.zero.2010.xvid-submerge.avi | countdown to zero | |
| DrJn.2010.BRRip_mediafiremoviez.com.mkv | drjn | |
| Nim's.Island[2008]DvDrip-aXXo.avi | nim's island | |
| Invictus.DVDSCR.xViD-xSCR.CD1.avi | invictus | |
| Invictus.DVDSCR.xViD-xSCR.CD2.avi | invictus | |
| 20000 Leagues Under The Sea.avi | ||
| Across The Universe.MoZinRaT CD1.avi | across the universe mozinrat | |
| Adoration 2008 DvdRip ExtraScene RG.avi | adoration | |
| Amelie(English Dubbed).avi | amelie | |
| America.2009.STV.DVDRip.XviD-ViSiON.avi | america | |
| VTS_02_1.avi | vts_02_1 | |
| VTS_02_2.avi | vts_02_2 | |
| Antibodies.2005.GERMAN.DVDRip.XviD.AC3.CD1-AFO.avi | antibodies | |
| arranged.xvid-reserved.avi | arranged | |
| badder.santa.dvdrip.xvid-deity.avi | badder santa | |
| Balls of Fury[2007]DvDrip[Eng]-FXG.avi | balls of fury | |
| Bruno (2009) DVDRip-MAXSPEED www.torentz.3xforum.ro.avi | bruno | |
| Defiance DvDSCR[2009] ( 10rating ).avi | defiance | |
| Down With Love (cute romantic comedy).avi | down with love | |
| Einstein.And.Eddington.2008.DVDRip.XviD.avi | einstein and eddington | |
| ENEMY_OF_THE_STATE..DVDrip(vice).avi | enemy_of_the_state |
Based on the observation that
- Most of the file name contains the format like 'dvdrip', 'xvid', 'brrip','dvdscr' or other words like 'CD1','(<year>)','[<year>]' specified in the name and everything after any of this words doesnot contains any useful data.
- Sometimes extra information is added to file name inside bracket like
Defiance DvDSCR[2009] ( 10rating ).avi
Down With Love (cute romantic comedy).avi
so we can also ignore the part including and after brackets as movie names doesn't have brackets in them and have no useful information after it.
'(.*?)(dvdrip|xvid| cd[0-9]|dvdscr|brrip|divx|[\{\(\[]?[0-9]{4}).*'
This regular expression will find file names where we have dvdrip, brrip, xvid(we can specify any number of values here) or year and finds first of any one of the appearing patterns because we have used lazy parsing here using .*?. We then extract the first back referenced part \1.
Secondly, to remove the part within brackets we use
'(.*?)\(.*\)(.*)' regular expression.
Following code snippet gets the movie names(to an extent) from file name.
import re
fr = open('filenameslist.txt', 'r')
fw = open('movienames.txt', 'w')
for line in fr:
text = line.strip()
text1 = re.search('([^\\\]+)\.(avi|mkv|mpeg|mpg|mov|mp4)$', text)
if text1:
text = text1.group(1)
text = text.replace('.', ' ').lower()
text2 = re.search('(.*?)(dvdrip|xvid| cd[0-9]|dvdscr|brrip|divx|[\{\(\[]?[0-9]{4}).*', text)
if text2:
text = text2.group(1)
text3 = re.search('(.*?)\(.*\)(.*)', text)
if text3:
text = text3.group(1)
# print text
fw.write(text + '\n')
fr.close()
fw.close()
Output can be improved further observing things like we can replace characters like underscore with space, we can check for only four digits where next character is non word character ..
Subscribe to:
Posts (Atom)