I took several tests ranging from 1 to 2 min from http://www.typingtest.com/. My speed is close to 48 wpm. How to improve this? Interesting.
I also used backspace quite a few times. I remember my colleague Rajesh Seenivasan typing without pressing a backspace. Now, that is something I took up as a personal challenge and was able to get past many backspaces, but there are a few more to trim :-)
Monday, December 24, 2012
TopCoder:SRM233:SmartWordToy
This entry is about SmartWordToy problem from the Single Round Match 233 of TopCoder Division 1 and it is a 500 point problem:
Have you visited the TopCoder Algorithm tutorials page? You must have seen the mention of BFS (Breadth First Search) there and probably started to try the first problem listed there: SmartWordToy. I started too.
It seemed an interesting problem: there are 4 letter blocks; each block contains 2 buttons; left makes the letter go the previous letter in the sequence; right button takes the letter one step forward; given a start, end and a set of disallowed combinations, what is the minimum number of button presses required to reach the end?
The sequence of letters are cyclic which means that if you are seeing 'a' and press the left button, you will see 'z'. Also, if you are at 'z' and press the right button, you will see 'a'. Every time a button is pressed, the total score adds up until the end is reached.
The first test case in the problem being:
start = "aaaa"
end = "zzzz"
forbidden = { "aaaz", "aaza", "azaa", "zaaa", "azzz", "zazz", "zzaz", "zzza"}
v0.1:
I created a graph that would generate 8 new strings (or state) from a given string (state). For instance:
aaaa = zaaa baaa azaa abaa aaza aaba aaaz aaab
This is the set that results from pressing 1 button (left or right) on each block.
The graph generation took about 9 seconds to finish and if i had submitted this version, it would say 'Time Limit Exceeded'. We will come to this problem later.
After this, I added the start state to the queue and started the BFS. Pick the first state from the queue, check if it the goal state, if not, add it to the visited states, get the 8 possible states from this state, add it to the queue. If it is the goal state, end.
Problems with this approach:
1. Graph has been generated taking really long time.
2. How do we count the button presses?
3. On looking at the program trace, you see that the path taken does not go towards the goal. Even if the goal state was reached, it is certainly not the optimal path. This raises the question: how do we really use BFS?
v1.0
1. Addressed the early graph creation by adding the start state to the queue. Picking the item off the queue, checking if it is present in the graph, if not, add it to the graph along with the set of states that it generates.
2. Added a cost to each state by computing the distance from a given state to the goal state. This was interesting because there are 2 possible costs: forward cost (distance from a to z is 25) and reverse cost (distance from a to z is 1)
3. Now, I used Dijkstra's min path algorithm to pick the state with the least cost and then go towards the goal.
This solution passed all the sample test cases for the problem and some of my own. With confidence, I submitted the solution and got 469 out of 500. I then ran the system tests and saw that one test case fails:
String start = "aaaa";
String finish = "xxxx";
String[] forbidden = { "xz xz xz z", "xa xa xa b" };
Expected = 12, my output is 14. Need to find the root cause and fix it.
Learnings:
1. Just in time execution
2. Go towards the goal :-)
Have you visited the TopCoder Algorithm tutorials page? You must have seen the mention of BFS (Breadth First Search) there and probably started to try the first problem listed there: SmartWordToy. I started too.
It seemed an interesting problem: there are 4 letter blocks; each block contains 2 buttons; left makes the letter go the previous letter in the sequence; right button takes the letter one step forward; given a start, end and a set of disallowed combinations, what is the minimum number of button presses required to reach the end?
The sequence of letters are cyclic which means that if you are seeing 'a' and press the left button, you will see 'z'. Also, if you are at 'z' and press the right button, you will see 'a'. Every time a button is pressed, the total score adds up until the end is reached.
The first test case in the problem being:
start = "aaaa"
end = "zzzz"
forbidden = { "aaaz", "aaza", "azaa", "zaaa", "azzz", "zazz", "zzaz", "zzza"}
v0.1:
I created a graph that would generate 8 new strings (or state) from a given string (state). For instance:
aaaa = zaaa baaa azaa abaa aaza aaba aaaz aaab
This is the set that results from pressing 1 button (left or right) on each block.
The graph generation took about 9 seconds to finish and if i had submitted this version, it would say 'Time Limit Exceeded'. We will come to this problem later.
After this, I added the start state to the queue and started the BFS. Pick the first state from the queue, check if it the goal state, if not, add it to the visited states, get the 8 possible states from this state, add it to the queue. If it is the goal state, end.
Problems with this approach:
1. Graph has been generated taking really long time.
2. How do we count the button presses?
3. On looking at the program trace, you see that the path taken does not go towards the goal. Even if the goal state was reached, it is certainly not the optimal path. This raises the question: how do we really use BFS?
v1.0
1. Addressed the early graph creation by adding the start state to the queue. Picking the item off the queue, checking if it is present in the graph, if not, add it to the graph along with the set of states that it generates.
2. Added a cost to each state by computing the distance from a given state to the goal state. This was interesting because there are 2 possible costs: forward cost (distance from a to z is 25) and reverse cost (distance from a to z is 1)
3. Now, I used Dijkstra's min path algorithm to pick the state with the least cost and then go towards the goal.
This solution passed all the sample test cases for the problem and some of my own. With confidence, I submitted the solution and got 469 out of 500. I then ran the system tests and saw that one test case fails:
String start = "aaaa";
String finish = "xxxx";
String[] forbidden = { "xz xz xz z", "xa xa xa b" };
Expected = 12, my output is 14. Need to find the root cause and fix it.
Learnings:
1. Just in time execution
2. Go towards the goal :-)
Saturday, December 8, 2012
foss.in 2012 videos online: http://hasgeek.tv/fossdotin/
Need I say more.
The inaugural talk by Atul Chitnis starts after a set of photos are flashed and Subbu is featured in the photos :-)
The inaugural talk by Atul Chitnis starts after a set of photos are flashed and Subbu is featured in the photos :-)
ArsDigita: Discrete Math: Prof.Shai Simonson
I have been fortunate to have come to know of the videos from the courses taught by Prof.Shai Simonson at ArsDigita University (http://aduni.org/) Here are the links:
1. Discrete Mathematics: http://aduni.org/courses/discrete/index.php?view=cw
2. Algorithms: http://aduni.org/courses/algorithms/index.php?view=cw
My friends (Radha, Prasad, Subbu) and I ordered the DVDs and we have the complete collection of the courses.
I particularly like the courses taught by Prof.Shai and interestingly enough, some of the material that he goes over have appeared in the interviews I have been to. Also, I got to see the video of Proj.Jerry Sussman of the 'Structure and Interpretations of Computer Programs' fame talking about his experiences. Wonderful.
I came across these videos because another friend Malatesh shared them with me many years ago. Thank you Malto.
I am enjoying these videos and the learning that comes from them.
1. Discrete Mathematics: http://aduni.org/courses/discrete/index.php?view=cw
2. Algorithms: http://aduni.org/courses/algorithms/index.php?view=cw
My friends (Radha, Prasad, Subbu) and I ordered the DVDs and we have the complete collection of the courses.
I particularly like the courses taught by Prof.Shai and interestingly enough, some of the material that he goes over have appeared in the interviews I have been to. Also, I got to see the video of Proj.Jerry Sussman of the 'Structure and Interpretations of Computer Programs' fame talking about his experiences. Wonderful.
I came across these videos because another friend Malatesh shared them with me many years ago. Thank you Malto.
I am enjoying these videos and the learning that comes from them.
Sunday, December 2, 2012
Topcoder SRM 562 Div2 250 point problem: Cucumber Market
Problem in short: Kid goes to cucumber market with a budget and chooses k items out of available n items. He can choose any of all possible k combinations and the return is 'YES' if he can successfully buy any such combination, otherwise 'NO'. The inputs being the array of prices and the number k.
My approach: Initially, I sorted the price array and got totals of k items (0..k, 1..k+1, 2..k+2, so on until n) and found test cases to pass except the 2nd one. I seemed to have gotten lost when I needed to sum up items 0, 2, 3,.. which is basically taking any of the k elements from the n elements.
Now, the problem seemed to need all possible k combination from n items. I thought of looking up how to get all the k combinations and then coding phase time ran out.
Challenge phase: In this phase, I looked up one solution which had picked up the worst possible set of k items and if that did not satisfy the criterion, it returned 'NO'. This felt rather intimidating. How could I possibly miss this?
Anyway, one thing I need to learn is to figure out how to find all k items from n items.
Found an interesting link in StackOverflow:
http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n
Sunday, April 18, 2010
Leopardboard bricked.
Looks like the Leopardboard got bricked while I was trying to install the UBL and U-Boot from the RidgeRun SDK. Have to unbrick it now!
Back to http://firstpenguin.org/Leopardboard#Recovering_a_bricked_LeopardBoard
Back to http://firstpenguin.org/Leopardboard#Recovering_a_bricked_LeopardBoard
Sunday, March 21, 2010
Regular expressions in Python
Pretty interesting article - http://www.informit.com/articles/article.aspx?p=1412026
Saturday, September 5, 2009
Android app Hunting Lines has been submitted as an entry into ADC2
Hunting Lines is an app that lets a user select a set of contacts and starts dialing them one after the other until one of them picks up the call. This was inspired by the problem of contacting LPG gas agencies and the like that have many phone lines that are always busy!
This app has been submitted as an entry into ADC2, which is the Android Developer Challenge 2 by Google.
Some problems/challenges we saw while making the app:
* There are internal APIs in the SDK that are invisible to developers like us unless there is a certificate that is the same as the one used by the Android core platform.
* What APIs did this app need: a way to reliably know the different phone states like call started, ringing, connected, disconnected, idle, missed etc. The only ones available are: off hook, idle and ringing. So, that was the first problem. So, how did we figure out if a call we initiated went through or not - a post by someone in Google (Megha Joshi) hinted at using call log for some question came as help. So, the app changed to look at the call log whenver the call state idle event is received. That worked!
* 2 phones had Android on them for testing - one was the openmoko phone and the other being the Android Dev Phone. One the openmoko, we used the alpha release of the cupcake version by Koolu. On this version, the app started to go from one number to the other perfectly until one of them connects.
The same thing did not work on the Android Dev Phone, why - after every call, we would end up seeing the call log screen that prevented the phone state idle event to be posted. So, you have to exit the call log screen to start dialing the next number!!! How dumb can that be specially when you want the app to be completely automatic. Any workarounds here - None!!! Just while searching for a workaround, I saw an email from someone (flohier) to the android developers forum stating the same problem and the failed attempts at getting it to work.
* At times during debugging, I would end up not seeing the app and we figured out that when Android loads, it would kill an app that does not have a certificate. I learnt this only while trying to submit the app and it threw an error saying it needs a self certified certificate.
Anyway, it is now in the contest. We plan to release the source and the apk into opensource in a day or two. We will post an update here. If you plan to use the source or the apk, please send an email to openologyATgooglegroups.com. Oh, and please send us some feedback if you use the app!
Update - here's the source - http://gitorious.org/hunting-lines
New home - http://firstpenguin.org/tiki-read_article.php?articleId=4
p.s: the name was coined by Praveen and the idea comes from Radha.
This app has been submitted as an entry into ADC2, which is the Android Developer Challenge 2 by Google.
Some problems/challenges we saw while making the app:
* There are internal APIs in the SDK that are invisible to developers like us unless there is a certificate that is the same as the one used by the Android core platform.
* What APIs did this app need: a way to reliably know the different phone states like call started, ringing, connected, disconnected, idle, missed etc. The only ones available are: off hook, idle and ringing. So, that was the first problem. So, how did we figure out if a call we initiated went through or not - a post by someone in Google (Megha Joshi) hinted at using call log for some question came as help. So, the app changed to look at the call log whenver the call state idle event is received. That worked!
* 2 phones had Android on them for testing - one was the openmoko phone and the other being the Android Dev Phone. One the openmoko, we used the alpha release of the cupcake version by Koolu. On this version, the app started to go from one number to the other perfectly until one of them connects.
The same thing did not work on the Android Dev Phone, why - after every call, we would end up seeing the call log screen that prevented the phone state idle event to be posted. So, you have to exit the call log screen to start dialing the next number!!! How dumb can that be specially when you want the app to be completely automatic. Any workarounds here - None!!! Just while searching for a workaround, I saw an email from someone (flohier) to the android developers forum stating the same problem and the failed attempts at getting it to work.
* At times during debugging, I would end up not seeing the app and we figured out that when Android loads, it would kill an app that does not have a certificate. I learnt this only while trying to submit the app and it threw an error saying it needs a self certified certificate.
Anyway, it is now in the contest. We plan to release the source and the apk into opensource in a day or two. We will post an update here. If you plan to use the source or the apk, please send an email to openologyATgooglegroups.com. Oh, and please send us some feedback if you use the app!
Update - here's the source - http://gitorious.org/hunting-lines
New home - http://firstpenguin.org/tiki-read_article.php?articleId=4
p.s: the name was coined by Praveen and the idea comes from Radha.
Thursday, July 9, 2009
InstallShield error 6199 and other errors...
I am posting this here because the forums I have been visiting don't let me post unless I am registered. I don't want to register because this will be the only time I will post. So, I thought why not let Google search land up at this blog entry? That will keep things simple.
I got this unusual error and with the help of a friend, figured out that a "special" character had landed into the Installshield ISM file. Instead of "Author's" it had become "AuthorÉs" (I have used Alt+keypad 400 to generate this character in place the actual one I saw!).
This was figured out by opening the ISM file in the InstallShield editor while all the time, the internal error was showing up in the command line. It turns out that I have seen a lot of people using the ISsaBld.exe to generate the installers. So, the editor said - Line 1549 Col 100 has a special char, while the command line just generated "ISDEV: internal error -6199". Interesting isn't it?
There were other errors like the directory where the output was being generated was open by some process. So, I used SysInternals' ProcessExplorer to figure it out!
I got this unusual error and with the help of a friend, figured out that a "special" character had landed into the Installshield ISM file. Instead of "Author's" it had become "AuthorÉs" (I have used Alt+keypad 400 to generate this character in place the actual one I saw!).
This was figured out by opening the ISM file in the InstallShield editor while all the time, the internal error was showing up in the command line. It turns out that I have seen a lot of people using the ISsaBld.exe to generate the installers. So, the editor said - Line 1549 Col 100 has a special char, while the command line just generated "ISDEV: internal error -6199". Interesting isn't it?
There were other errors like the directory where the output was being generated was open by some process. So, I used SysInternals' ProcessExplorer to figure it out!
-raghav
Thursday, May 21, 2009
Inspired by Dr.Randy Pausch
Landed up at the transcript of Dr.Randy Pausch's 'Last Lecture' and was instantly inspired by him. Ended up reading his book and have had many discussions with Prasad, Radha and Subbu.
Did something interesting with the 'First Penguin' chapter! More information will follow soon. BTW, 'First Penguin' just bowled us out!!!
Thank you Dr.Randy Pausch for everything! And for 'Alice' the 3D programming language!
Someday, we wish to visit CMU, walk on the Randy Pausch bridge and scale the brick walls!!!
Did something interesting with the 'First Penguin' chapter! More information will follow soon. BTW, 'First Penguin' just bowled us out!!!
Thank you Dr.Randy Pausch for everything! And for 'Alice' the 3D programming language!
Someday, we wish to visit CMU, walk on the Randy Pausch bridge and scale the brick walls!!!
More about Dr.Randy Pausch: http://en.wikipedia.org/wiki/Randy_Pausch
The Last Lecture: http://www.youtube.com/watch?v=ji5_MqicxSo
Lecture on Time Management: http://video.google.com/videoplay?docid=-5784740380335567758
The Last Lecture: http://www.youtube.com/watch?v=ji5_MqicxSo
Lecture on Time Management: http://video.google.com/videoplay?docid=-5784740380335567758
Subscribe to:
Posts (Atom)