Hello and welcome to my blog, which will deal with programming and other silly hobbies of mine.
This page has a feed that you can track (if you use Firefox, you may see the feed icon in the location bar)
by hrj 22 Nov 2008 08:19
Undecidability of the halting problem..
.. in verse form
I think this is worth learning by-heart and should be taught to every Computer-science student.
by hrj 04 Nov 2008 18:03
One of the best linux games I have played in recent times:
Gameplay is nice. Graphics are simple but nicely polished.
If you find graphics to be very slow, disable the "Smooth Lines" option, and you will be fine, without an appreciable loss in quality.
by hrj 26 Oct 2008 13:01
The mirror I am making for my telescope is almost done. But it is the last mile which is the most trying.
I am in the polishing stages of the mirror and two events happened today:
First the good news. Looks like the focal length of my mirror is much lesser than I had believed until now. It seems to be about 68 to 72 inches, instead of the 85 inches I thought it was.
Which means my scope's length will probably be a whole feet shorter, which is great!
The bad news is, I did a round of polishing yesterday night which has caused scratches to appear on the mirror. There are 3 of them. Not too deep; but gives me jitters. Either my workspace is too dusty, or the polishing agent is contaminated.
I can't take a risk now. So, I will stop using this polishing agent and wait for a new batch to arrive.
More good news. I just built a Focault tester, and my mirror appears to be perfectly spherical!! Woohooo!
by hrj 18 Oct 2008 11:34
While solving one of those online programming puzzles1 I needed to compute all points in a collection of rectangles. Note that these rectangles can overlap!
One quick way to solve this is to maintain a Set (as opposed to a List) of points belonging to each rectangle. This would have been nice, since I anyway needed to iterate over these set of points.
However, for large rectangles, the set quickly becomes huge and unmanageable (number of points is proportional to square of rectangle width).
To reduce the memory requirement, I thought of maintaining a set of non overlapping rectangles (instead of individual points). perhaps a diagram will make it clear:
The rectangles on the left are the input. Note how they overlap.
The rectangles on the right are the output.
The algorithm in pseudo-pseudo-code is:
- Add the input rectangles one by one to the result list
- While adding, clip the new rectangle (A) by each rectangle in the result list (B)
- Clipping is done by
- Chopping A with each line segment of B
- The resulting list of chopped rectangles is then filtered such that they don't lie within B
The Scala code for this is attached to this page Region.scala. Feel free to use it as you like.
- The co-ordinates are integer based, but can be easily extended to reals
- I haven't optimised for the number of resulting rectangles. For example, it might be possible to coalesce adjoining rectangles into a single one. (The number of resulting rectangles didn't matter for my problem)
- The result is not unique. Multiple correct solutions are possible and the chosen one depends on the order in which rectangles are added.
- If you ever happen to use this piece of code, please drop me a note/comment.
by hrj 30 Sep 2008 06:52
I am a heavy user of dot (from the graph viz package). I use it for creating graphs automatically (from scripts/programs/etc).
But when it comes to quickly creating a graph manually, there is only one free tool out there that "just works".