Hi,
I read a couple of articles at linux journal. Two programming environment, especially meant to teach programming in a very interesting way. Namely, Alice and Scratch. The reviews at Linux Journal are here and here.
Showing posts with label programming. Show all posts
Showing posts with label programming. Show all posts
Monday, November 08, 2010
Wednesday, April 09, 2008
Duplex printing script
Well,
Our department printer by default runs in single side printing mode. This causes a lot of paper wastage. I finally sat down and wrote a shell script which will takes one PDF file as an input and outputs two PDF files. One with all odd-pages. Another with all even pages in reverse order so that output papers from odd-page printing can be directly fed to input tray. Of course, this requires a bit of manual intervention, but it is not a big price to pay for saving paper ( and saving trees ).
Here is a link to the script :
http://sbjoshi.googlepages.com/duplexprinting.sh
Please let me know if any bug is found in the script or if you want to suggest some improvements.
--Saurabh Joshi
Our department printer by default runs in single side printing mode. This causes a lot of paper wastage. I finally sat down and wrote a shell script which will takes one PDF file as an input and outputs two PDF files. One with all odd-pages. Another with all even pages in reverse order so that output papers from odd-page printing can be directly fed to input tray. Of course, this requires a bit of manual intervention, but it is not a big price to pay for saving paper ( and saving trees ).
Here is a link to the script :
http://sbjoshi.googlepages.com/duplexprinting.sh
Please let me know if any bug is found in the script or if you want to suggest some improvements.
--Saurabh Joshi
Saturday, February 09, 2008
Programming Challenges
Today, I had a chat with ali on different online programming challenges as IOPC is going on write now and ali has taken part in it. I was remembering my glorious days when I won a jacket in bitwise.
I am just going to enlist a few programming challenges. Obviously, the list is not exhaustive.
1) ACM ICPC : I believe it is one of the most prestigious programming challenges. It is an IBM sponsored annual event.
2) Top Coder : This too is one of the most prestigious programming challenges. General belief is that the emphasis is more on programming rather than algorithms.
3) IOCCC : Well, here one can find the weirdest C programs. Most of the time it will seem that the winning entry programs won't even compile. However, they do but it is difficult ( rather next to impossible ) to find out what they would do by merely reading the code. My favorite program is here. And yeah, it DOES compile and run.
4) Bitwise : One of the most prestigious INDIAN programming challenges. I used the word "Indian" because it is held by Indian Institute of Technology, Kharagpur. The challenge however is open internationally. It is really a pity to see that since the inception of the event, only once an Indian team could grab the first prize. Ameya Karkare ( aka crack-kare ) and Navneet Lohiwal ( aka lollu ) from Indian Institute of technology Bombay (my alma-matter :-) ) played with handle "AK47", undoubtedly shooting down all competing teams.
5) OPC : Held annually by Chennai Mathematical Institute. One of the toughest programming challenge I have ever faced.
6) CodeCraft : Held annually by International Institute of Information Technology, Hyderabad as part of their technology festival Felicity.
7) IOPC : Hosted by IIT Kanpur as part of its technology festival techkriti.
I am just going to enlist a few programming challenges. Obviously, the list is not exhaustive.
1) ACM ICPC : I believe it is one of the most prestigious programming challenges. It is an IBM sponsored annual event.
2) Top Coder : This too is one of the most prestigious programming challenges. General belief is that the emphasis is more on programming rather than algorithms.
3) IOCCC : Well, here one can find the weirdest C programs. Most of the time it will seem that the winning entry programs won't even compile. However, they do but it is difficult ( rather next to impossible ) to find out what they would do by merely reading the code. My favorite program is here. And yeah, it DOES compile and run.
4) Bitwise : One of the most prestigious INDIAN programming challenges. I used the word "Indian" because it is held by Indian Institute of Technology, Kharagpur. The challenge however is open internationally. It is really a pity to see that since the inception of the event, only once an Indian team could grab the first prize. Ameya Karkare ( aka crack-kare ) and Navneet Lohiwal ( aka lollu ) from Indian Institute of technology Bombay (my alma-matter :-) ) played with handle "AK47", undoubtedly shooting down all competing teams.
5) OPC : Held annually by Chennai Mathematical Institute. One of the toughest programming challenge I have ever faced.
6) CodeCraft : Held annually by International Institute of Information Technology, Hyderabad as part of their technology festival Felicity.
7) IOPC : Hosted by IIT Kanpur as part of its technology festival techkriti.
Thursday, March 08, 2007
Sudoku Solver
It is very unlikely for me to post twice in a day, yet I am back again. I had a little idle time at my disposal so I thought to put it to some use.
A couple of months back I read in Times of India about world Sudoku championship which was to happen in March 2007. In addition to the day to day sudoku puzzles they included certain variation of the puzzle too, to encourage readers to take part as well as to stimulate their brain :D.
Sudoku took over my mind during those days and I was completely engrossed in reading about Sudoku as well as solving them at websudoku . It occurred to me why not write a program to solving the puzzle? So I took up the task and was ready with a small Sudoku Solver .
Of course, for certain inputs it does not give the solution. I pondered over the completeness and soundness issues of the initial sudoku board. I don't know whether it is appropriate to use these terms which are often used and associated with algorithms. Let me define it this way. Completeness means that the initial information given in the board should be sufficient to solve the puzzle by using only inferences ( No guessing game/No coin tossing/ No breaking tie). In other words, there must exist at most one solution that can be derived from the initial configuration of the board. Soundness means that the information should not be conflicting, or say, at least one solution exist that can be derived from the initial information. I discussed the matter with my mathematics teacher Mr Motilal Panigrahi at GCET .
We could not arrive at any definitive proofs or conditions to ensure the soundness and completeness, but it was nice to chat with him over these things years after I left the college.
A couple of months back I read in Times of India about world Sudoku championship which was to happen in March 2007. In addition to the day to day sudoku puzzles they included certain variation of the puzzle too, to encourage readers to take part as well as to stimulate their brain :D.
Sudoku took over my mind during those days and I was completely engrossed in reading about Sudoku as well as solving them at websudoku . It occurred to me why not write a program to solving the puzzle? So I took up the task and was ready with a small Sudoku Solver .
Of course, for certain inputs it does not give the solution. I pondered over the completeness and soundness issues of the initial sudoku board. I don't know whether it is appropriate to use these terms which are often used and associated with algorithms. Let me define it this way. Completeness means that the initial information given in the board should be sufficient to solve the puzzle by using only inferences ( No guessing game/No coin tossing/ No breaking tie). In other words, there must exist at most one solution that can be derived from the initial configuration of the board. Soundness means that the information should not be conflicting, or say, at least one solution exist that can be derived from the initial information. I discussed the matter with my mathematics teacher Mr Motilal Panigrahi at GCET .
We could not arrive at any definitive proofs or conditions to ensure the soundness and completeness, but it was nice to chat with him over these things years after I left the college.
Monday, February 12, 2007
Bitwise fiasco
Yesterday was one of the worst day. It was the day of Bitwise 2007 . I participated in this contest with Pranjal as my team mate. I had really high hopes and a bit of arrogance as I could claim 26th rank in this prestigious contest last time amongst 2700 participating teams. Bitwise 2006 was my first official participation in a programming contest. Having done so well in my debut, I was dreaming to climb further up the ladder with Pranjal ( who secured 8th rank in Bitwise 2006 ) along the side.
The arrogance had fogged the part of the brain which does rational thinking, and I ended up starting my day without any kind of warm up practice for the contest. I had not even revised any relevant material.
Bitwise 2k7 started a little late than the announced time of 1300hrs. And as usual, I thought to attempt the "easier" problems ( 100 points ) first. It was based on graph theory where one was required to find out the vertice(s) having the minimum distance to all other vertices in a given tree. Initially, I started with an O(n^3) implementation and when I found the response of the system to be "Time Limit Exceeded" ( which was kind of obvious with such a naive approach to the problem ), I improved it to O(n^2). Even though, I tried harder I could neither change the complexity nor the response of the system. After 2-3 failed attempts I decided to concentrate on some other problem and come back to this one at a later time.
Problem 4, had two parts, the initial part was to decide whether a certain door k out of n will be open or closed having gone through a certain toggling scheme. It was kind of easy. The next part was a variation of the classical Tower of Hanoi problem. No matter how hard I tried, my algorithm was not matching the given sample input/output. I asked the admins to look at the problem again for any possible mistake in the statement or sample input/output. But this time they were not as quick in response as they were for the last event. After around 10-15 questions fired by different teams, they answered only one. The overall contest also had attained height of mismanagement with problem statements being updated several times after the contest timer was started. Having tried for 2-3 hours on Problem 4, to my utter surprise, I found out that many other teams were cribbing about the correctness of its problem statement. I checked the rankings and was shocked to see that none of the teams ( not even those who were sitting at Top 10 ) could solve that problem. So I gave up on this problem too.
Then, I started yet another problem having to do with dynamic programming, coins and denominations. It was a variation of the classic denomination problem. Not that it was too hard to do it, I was kind of getting low because of failures and hunger. We went out to have a dinner at a small restaurant just opposite to IIT where we discussed yet another problem involving prime number and modular arithmetic. I thought to give it a shot after coming back, but that damn "Time Limit Exceeded" was not getting out of my sight.
Finally, we decided to give up as we were still sitting at zero where other Top 50 teams begged more than 800 points. I had never been so dejected in a long time. I was literally ashamed of myself.
Today morning I read a couple of articles on Modular Arithmetic and
Fermat's little theorem and realized why my implementation was not fast enough to defeat that "Time Limit Exceeded" demon. For Problem 1 ( The one with the vertices ) I learned that the middle vertice(s) of the longest path in the tree always have minimum sum of distance to all other vertices. How to find the longest path in a tree? Well, start from any vertex A and find out the furthest vertex B from it. Now start with B and find out the furthest vertex C from B. Path B to C is the longest path and its middle vertice(s) are the ones that we needed to find out. Running time?? O(n)
The bottom line is that I have got rusty. My programming skills and algorithm designing skills have fallen down. It seems I have not been doing much brain stimulating work for a long time. May be this failure is an indication for me to start honing my skills and in addition to giving exercise to my body I should give enough exercise to my brain as well.
The arrogance had fogged the part of the brain which does rational thinking, and I ended up starting my day without any kind of warm up practice for the contest. I had not even revised any relevant material.
Bitwise 2k7 started a little late than the announced time of 1300hrs. And as usual, I thought to attempt the "easier" problems ( 100 points ) first. It was based on graph theory where one was required to find out the vertice(s) having the minimum distance to all other vertices in a given tree. Initially, I started with an O(n^3) implementation and when I found the response of the system to be "Time Limit Exceeded" ( which was kind of obvious with such a naive approach to the problem ), I improved it to O(n^2). Even though, I tried harder I could neither change the complexity nor the response of the system. After 2-3 failed attempts I decided to concentrate on some other problem and come back to this one at a later time.
Problem 4, had two parts, the initial part was to decide whether a certain door k out of n will be open or closed having gone through a certain toggling scheme. It was kind of easy. The next part was a variation of the classical Tower of Hanoi problem. No matter how hard I tried, my algorithm was not matching the given sample input/output. I asked the admins to look at the problem again for any possible mistake in the statement or sample input/output. But this time they were not as quick in response as they were for the last event. After around 10-15 questions fired by different teams, they answered only one. The overall contest also had attained height of mismanagement with problem statements being updated several times after the contest timer was started. Having tried for 2-3 hours on Problem 4, to my utter surprise, I found out that many other teams were cribbing about the correctness of its problem statement. I checked the rankings and was shocked to see that none of the teams ( not even those who were sitting at Top 10 ) could solve that problem. So I gave up on this problem too.
Then, I started yet another problem having to do with dynamic programming, coins and denominations. It was a variation of the classic denomination problem. Not that it was too hard to do it, I was kind of getting low because of failures and hunger. We went out to have a dinner at a small restaurant just opposite to IIT where we discussed yet another problem involving prime number and modular arithmetic. I thought to give it a shot after coming back, but that damn "Time Limit Exceeded" was not getting out of my sight.
Finally, we decided to give up as we were still sitting at zero where other Top 50 teams begged more than 800 points. I had never been so dejected in a long time. I was literally ashamed of myself.
Today morning I read a couple of articles on Modular Arithmetic and
Fermat's little theorem and realized why my implementation was not fast enough to defeat that "Time Limit Exceeded" demon. For Problem 1 ( The one with the vertices ) I learned that the middle vertice(s) of the longest path in the tree always have minimum sum of distance to all other vertices. How to find the longest path in a tree? Well, start from any vertex A and find out the furthest vertex B from it. Now start with B and find out the furthest vertex C from B. Path B to C is the longest path and its middle vertice(s) are the ones that we needed to find out. Running time?? O(n)
The bottom line is that I have got rusty. My programming skills and algorithm designing skills have fallen down. It seems I have not been doing much brain stimulating work for a long time. May be this failure is an indication for me to start honing my skills and in addition to giving exercise to my body I should give enough exercise to my brain as well.
Subscribe to:
Posts (Atom)