Blog

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)

The halting problem in verse form

by hrjhrj 22 Nov 2008 08:19

Undecidability of the halting problem..
.. in verse form

LoopSnoop.pdf

I think this is worth learning by-heart and should be taught to every Computer-science student.

tags:

Defcon

by hrjhrj 04 Nov 2008 18:03

One of the best linux games I have played in recent times:

Defcon

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.

tags:

Mirror making: some joy some rage

by hrjhrj 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.

Update:
More good news. I just built a Focault tester, and my mirror appears to be perfectly spherical!! Woohooo!

tags: telescope

Region Unions

by hrjhrj 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!

First attempt

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).

Second attempt

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:

regions.png

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.

Notes

  • 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.

tags:

GP Field Guide

by hrjhrj 01 Oct 2008 13:29

Note to myself:

Have a look at:
GP Field Guide

tags:

Best Interactive Graphics Editor

by hrjhrj 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".

yEd

Snapshot Below:

yEdSnap.png

tags:

page 3 of 3« previous123