Last week I tried to do something which I’ve been planning for quite sometime. Porting a Python program into Haskell. In case you didn’t know, Haskell is a purely functional programming language that’s recently become a hot favourite. It has a lot of cutting edge ideas from the academic world esp laziness and strong typing. It has an interesting way to solve the ‘multi-CPU problem’.
Mars Rover is a famous programming problem used by Thoughtworks in their recruitments. I first solved the problem in Python and later attempted to solve the same in Haskell. I cannot say that I ported it from Python because the approach I’ve used is completely different.
The Problem
A squad of robotic rovers are to be landed by NASA on a plateau on Mars.
This plateau, which is curiously rectangular, must be navigated by the rovers so that their on-board cameras can get a complete view of the surrounding terrain to send back to Earth.
A rover’s position and location is represented by a combination of x and y co-ordinates and a letter representing one of the four cardinal compass points. The plateau is divided up into a grid to simplify navigation. An example position might be 0, 0, N, which means the rover is in the bottom left corner and facing North.
In order to control a rover , NASA sends a simple string of letters. The possible letters are ‘L’, ‘R’ and ‘M’. ‘L’ and ‘R’ makes the rover spin 90 degrees left or right respectively, without moving from its current spot. ‘M’ means move forward one grid point, and maintain the same heading.
Assume that the square directly North from (x, y) is (x, y+1).
INPUT:
The first line of input is the upper-right coordinates of the plateau, the lower-left coordinates are assumed to be 0,0.
The rest of the input is information pertaining to the rovers that have been deployed. Each rover has two lines of input. The first line gives the rover’s position, and the second line is a series of instructions telling the rover how to explore the plateau.
The position is made up of two integers and a letter separated by spaces, corresponding to the x and y co-ordinates and the rover’s orientation.
Each rover will be finished sequentially, which means that the second rover won’t start to move until the first one has finished moving.
OUTPUT
The output for each rover should be its final co-ordinates and heading.
INPUT AND OUTPUT
Test Input:
5 5
1 2 N
LMLMLMLMM
3 3 E
MMRMMRMRRM
Expected Output:
1 3 N
5 1 E
The Python solution
The Python solution is actually smaller than the problem itself. The readability isn’t that great, but it is quite extensible. In fact, adding a new instruction like B(ackward) would need just one additional line. You can also extend the four cardinal directions to eight with minimal changes to the code.
The Haskell solution
I am a beginner in Haskell, so apologies for any bad coding practices. You might notice that rather than using Reflection as in the Python code, I have used Type-inference to invoke the correct function for each instruction. Yet again, this scales well while adding new instructions.
Key learnings
Since some of you might be interested in Haskell, I have tried to summarize my experience in Haskell programming
- There are no loop constructs. So everything must be done using recursion!
- Haskell I/O is very hard. This is because of my little knowledge of Monads. In fact, I solved the logic pretty quickly. It took me a while to figure out the input parsing.
- Type inference catches a lot of errors. This is quite handy but error messages are sometimes confusing
- I could have used Abstract Data Types for directions but it would have made the code lengthier
In short, programming in Haskell is a mind-bending exercise. Highly recommended!
Epic
‘Tis their chase littered with unending corpses
‘Tis a dogged race with the savages of Norse’s
I’ve slain them again and again
Still their shadows circle us from bloody skies
Fire breathing dragons like Satan’s kites
Fragrance of jasmine from her lovely tresses
Mixes odours with the rotting carcasses
Her warm breath behind my neck
Holding me tight, her lips part ways
Fear not, I comfort with resolute gaze
A deranged one dives with burning eyes
Unsheathing the sword over the precipice
Life plays a ghastly roll of the dice
A swift evasion and a mighty sweep
A dismembered head shrieks over the heap
On the handle of my sword my fingers tightened
She held me tight, lithe arms wrapped from behind
Her lovely countenance rests lightly on me
My palm placed on hers, my mind easen
My steed gallops gently towards the horizon
Why is the human body such a perfectly designed machine? I mean, it is such an incredibly complicated system consisting of million of cells, designed by a genetic code, each with a specific purpose. It is an incredibly complex feat of engineering if one were to design it from scratch.
The answer is Evolution. Evolution is a continuous process of attaining perfection through small steps. The steps are some what like this
- Lets start with a fairly evolved species
- On a global scale creating life is cheap
- Every generation is an minor experiment involving producing a unique combination of genetic attributes
- The attributes might or might not help the offspring that only time will tell
- The ones with beneficial attributes like intelligence, attractiveness thrives
- One in a long period of time, a mutation i.e. significant change in attributes happen.
- This mutant might or might not survive.
- If it survives and multiplies, it might or might not supplant the earlier species.
This cycle continues over millions of years. This cycle has resulted in millions of diverse and interesting flora and fauna. The key to all this is, in fact, step 2. It is cheap to create something. Something different. The difference might be minor at first, but the cumulative effect of several minor changes is very significant.
This is how creativity works. This is how innovations work. There must be an environment to experiment and create without too much overhead. The time from conception (of an idea) to birth (i.e. implementation) must be short. This is the basic idea behind prototyping.
Taking this analogy to computer languages, most of the innovative applications are now first implemented in a dynamic language than a statically compiled language. The traditional statically typed languages require more overhead due to increased line count and lack of ready to use libraries. The time from concept to implement is longer. Dynamic languages permit the prototyping of more ideas at the cost of less optimal implementations.
This is why copying ideas and applying it to areas different from where it was intended often works. It is cheap to reproduce an idea. It might have been a result of thousand iterations. But the idea is already born now. The genetic code has been designed and it has been proven. The next step is to clone the idea and start tinkering with it in small ways. You might very well be innovating.
The real secret of innovation is in making prototyping, experimenting, iterating or whatever you call it, cheap.
Managing Creative Assets is a multi-part series on how you can manage your creative works such as a novel or even blog post without impairing your creativity. It highlights the importance of using a version control system as an integral part of one’s creative workflow. Part 1 gives a good introduction to the series which is aimed at technology novices
Getting started with Mercurial: A tutorial
The concluding part of this series will be the installation and typical usage of Tortoise Mercurial, a user friendly GUI front-end for Mercurial. It is commonly referred to as TortoiseHg (the chemical symbol for mercury).
This will be a fairly simple tutorial to follow as each description is followed by a screenshot. These screenshots were taken on Windows XP, but they will be pretty similar in other OSes
Download Tortoise mercurial from the Bitbucket site. There are installables for Windows as well as for Linux. Installation on Windows is fairly straightforward as it is wizard-based.
Managing Creative Assets is a multi-part series on how you can manage your creative works such as a novel or even blog post without impairing your creativity. It highlights the importance of using a version control system as an integral part of one’s creative workflow. Part 1 gives a good introduction to the series which is aimed at technology novices
Who started the Fire?
In April 7, 2005, Linus Torvalds wanted to use a version control system to replace the proprietary BitKeeper system for developing Linux Kernel. He absolutely hated CVS (the version control system in vogue then) with a passion. So, he did what he did best, he wrote his own. This resulted in the release of a version control system called git.
The development of git led to a sudden interest in distributed version control systems (DVCS). Though it was not the first of its kind (earlier open-source DVCS existed like Arch and Monotone), it was the first mainstream DVCS.
Today, one of the first choices you need to make while selecting a version control system is whether it is centralised or distributed. Let’s understand this from own unique stand-point i.e. for managing creative assets.
Why I do not advice VSS, Subversion or a Central Version Control
What is a Centralised Version Control (CVC)? The odds are that most of the version control systems that you might have heard of are Centralised for e.g. VSS (Microsoft Visual Sourcesafe), CVS, RCS, Clearcase or Subversion.
If you are planning to use a version control for personal use involving no or minimal collaboration with others, I would strongly recommend not to use a centralised version control system. You can skip to the next section, if you don’t want a detailed set of reasons on why I recommend non-centralised version control.
The reasons I would cite here are a mix of usability issues and technical limitations. The usability issues are subjective but I am sure many find them genuinely annoying. I am making an assumption that since this is for personal version control management, so your CVC server would probably be installed locally. The problems are:
Everything is stored inside repositories: Adding your project to a CVC effectively creates a duplicate layout of your project inside the CVC server. For e.g. if you created your subversion repository within
C:\svn, all your projects will be kept inside this folder. You will have to maintain another filesystem inside this server using arcane commands.In a distributed version control system, you simply manage the project directory inside your normal filesystem. All the version controlled files will still be inside the project directory. This is quite useful since your project directory can be moved to a different location easily and the version history will be completely intact.
Server must be always running: If you have installed VSS or SVN locally, you must always remember to start the server. This can be configured to run as a service, but you will need admin privileges for this. This is not required in a distributed version control.
Offline activity cannot be checked-in: This is an oft-quoted technical limitation. You need your svn server running to make any check-ins or check-outs, making it considerably less useful whenever you are offline. But this is less of an issue in our case, since I assume the svn server is installed locally.
Remembering to checkout immediately after you import or check-in: Ever had the feeling that your files magically disappeared only to realise that you haven’t checked out? This is an irritating ‘feature’ of CVS. The files appear and disappear as you check in and out. Even worse is that they are sometimes read-only and sometimes writeable. This is confusing and irritating from a usability standpoint.
Apparently, most people leave their relevant files checked out at all times to avoid this confusion. But that would defeat the purpose. In a distributed version control, the files are always present where you expect them to be. This leads to less confusion and a world of improvement in terms of usability.
Weird layout: Ever seen a funny looking directory structure with
truck,branchesandtagsdirectories? Then you might be looking at a project under SVN. Ever wondered which directory actually contains your code? The right answer istrunk. I am not sure, if this is the most intuitive structure possible.Distributed Version Control is a superset: This should have been my first point, almost every centralised workflow can be now supported by Distributed Version Control. You can still upload (or “push”) stuff from your branches to the project’s central server.
If you are still not convinced and still prefer centralised version control, check out the easiest way to setup subversion in Windows written by Jeff Croft.
Distributed Sounds Complex
It is a common misconception that Distributed Version Control systems are difficult to use and hard to understand. In many ways, the concepts are simpler than traditional version control systems from a beginner’s perspective.
Assume that the files (say documents or images) related to your project are kept under a particular directory. This is called the Project folder. Traditionally, your project folder will be stored in a central server. Hence the name centralised version control.
Whenever you would need to use a particular file within this folder, you will need to check-out and once you have reached some logical point (say after adding a few paragraphs in your essay or sketching the torso of a toon) you would check-in.
These check-ins are like check-points. More check-points you add, the more finer undo history you will get. Fewer check-points will mean that there will be a lot of differences from one check-in to another making it less useful.
As you might have guessed, every time you need to check-in or check-out you will need to connect to the server. Hence, practically, you will need the server (installed on your machine or elsewhere) up and running at all times.
If someone else would like to work with you on the same project, they will need to connect to your server. If they would like to work on the same files that you are working on (a rare case), they would need to create a branch and work on the branch.
This collaborative scenario is slightly different when you are working with a DVCS.
What About Distributed?
In a distributed version control system, your friend would rather clone your entire project than branch it. After creating a clone, his copy will be identical to your repository in every way. It will have the entire version history intact.
He no longer needs to be connect to your repository, he can work independently. In fact, there is really no need for a server in DVCS. The repository is actually created within the project folder.
For instance, let’s take the initial scenario. You would like to add your project folder to version control. In a DVCS, the project folder is slightly modified to add some additional information (meta-data) which is typically hidden from the user. Hence, your project folder remains mostly intact and it doesn’t have to move into a server.
In short, the defining feature of DVCS is that there can be more than one “central” repository for the same project. In case, your repository gets nuked, the cloned repository with your friend is always available as a perfect clone. To quote:
“Only wimps use tape backup: real men just upload their important stuff on ftp, and let the rest of the world mirror it ;)” — Linus Torvalds (1996-07-20)
Types of DVCS
These are the popular open-source DVCS available:
- Git – Very fast DVCS by Linus which runs on UNIX but has a weak port to Windows.
- Mercurial – Fast cross-platform DVCS by Matt Mackall of Selenic. Partly written in Python
- Bazaar – User friendly cross-platform DVCS by Canonical (of Ubuntu fame). Written in pure Python
Selecting a DVCS, like most things, is a personal choice. So, you might want to read a more detailed comparison before making a choice. I would be explaining Mercurial in my next article because it has a nice selection of all the desired features.
Do comment if you found DVCS more interesting or otherwise…
Managing Creative Assets is a multi-part series on how you can manage your creative works such as a novel or even blog post without impairing your creativity. It highlights the importance of using a version control system as an integral part of one’s creative workflow
Why Do We Need A Version Control system?
Let me start off by saying that this is article is not for the techies. Despite what the title might tell you, this is an article about how to make computers help your creative process. How does a creative process work?
Most creative people follow the following simplified process attributed to Graham Wallas while thinking creatively:
- Preparation (preparatory work on a problem that focuses the individual’s mind on the problem and explores the problem’s dimensions),
- Incubation (where the problem is internalized into the unconscious mind and nothing appears externally to be happening),
- Intimation (the creative person gets a ‘feeling’ that a solution is on its way),
- Illumination or insight (where the creative idea bursts forth from its preconscious processing into conscious awareness); and
- Verification (where the idea is consciously verified, elaborated, and then applied).
Obviously, this is an iterative process. Most writers would have a pile of crumpled paper sheets overflowing their waste baskets. Be prepared to reject a lot of ideas (even good ones) when you are involved in some creative process. Sometimes, against your earlier good judgement you would like to go back and retrieve an idea that you had discarded. You may have to rummage your waste basket for that page and if you are lucky, you might find it among the pile.
These days most of the creative works; be it a novel, a movie or even a comic is prepared on a computer. However, the process of throwing away drafts into the waste basket and later digging them out, is still the way we humans work. The various ways people achieve this in practise is:
Saving multiple version: This results in a whole mess of files grouped by their prefixes. Some prefer to suffix them with version numbers like file-v0.5.doc, file-v1.0.doc etc, while others prefer to use descriptive suffixes like file-draft.doc, file-sentforreview.doc etc. As anyone who might have used this system would have experienced, this quickly becomes unwieldy. For example what is the difference between file-v0.5.doc and file-v1.0.doc? How can I revert to the earliest version while correcting many of the typos I found in the latest version?
Using Undo and Redo: This is a very simple system to understand and hence quite popular among artists. If something doesn’t feel right, keep pressing the Undo button till you are satisfied and then start over. There are many problems with this approach. Firstly, the timeline is linear. You cannot try two different approaches at the same time. Secondly, the Undo history is available only for a single session. Close the application and the undo history is forgotten.
Use a version control system: This approach relies on an version control system that remembers every version you had ever saved (rather checked-in). This system is the focus of this article.
To extend the analogy further, a version control system can give you a bottomless waste basket with the ability to show you what changes you made from one version to another. Version control systems are powerful enough to allow you to branch out into various versions simultaneously, which is often useful when you are collaborating with others.
In fact, the addition of a version control system makes a profound change to your creative process. You are no longer afraid to make mistakes. You can play around with your creations without the fear of what you had created so far. Most people are afraid to start from scratch, even though, it is often documented that subsequent creations become more refined and hence elegant due to the better understanding of the ‘problem’ mentioned in the Preparation phase above. But be mindful of drifting in the opposite direction too, as in the case of the Second System effect.
In the next part, we will be introduced to two kinds of version control systems – Centralized and Distributed; and which one is suited for certain scenarios.
This is for the users of the Emacs editor
Dired mode is the default way of visiting directories on Emacs. Whenever you open a file using C-x C-f, you would see the current directory. If you chose to press Enter without entering a file name, you would visit the current directory in Dired mode.
I don’t use the Dired mode very much to browse directories. I would rather use Windows explorer or Nautilus. Don’t get me wrong, I do find Dired extremely useful to locate a file. But for every directory you visit it adds a new buffer. This quickly becomes very unmanageable.
However, I recently found out that you can make Dired re-use the same buffer if you press a (dired-find-alternate-file) rather than ‘Enter’ for visiting a directory in Dired mode. This is can be even used to open a file which results in the last Dired buffer being completely removed (alternatively you can use v or dired-view-file to view a read-only version of the file).
With this tip, I am finding myself using Emacs more for browsing around my file system.
I was shifting to a new house in Mangalore recently. I realised that some of the things that I value the most were not the typical big screen home theatre system or a luxurious jacuzzi.
Without sounding too cliched, let me say that some of the best things in life are not expensive. Here are some of the best things you can buy for less than Rs. 8K (around $160):
Wifi Router
This is a blessing for those with frequently off working hours calls or if you have multiple laptops. The convenience of being able to work near the balcony enjoying the quiet scenery and sipping tea is divine.
Small Water Heater
This is a pet peeve of mine. Hot water is absolutely essential for a bath. Even in summer. Yep. Nothing gives you a better satisfaction that a hot bath after a warm day. And in Mangalore it’s either raining in buckets or it’s hot and humid. I would recommend that you go for a 8l one if you want a good tradeoff between heating time and power consumption.
Portable Harddisk
I am sure most of us have tried using CDs for backing up all those wonderful photos and songs we have. The problem is – CD are not really great for organising data. It is readonly and once you burn it, there is no way to go back and change it. There are, of course, other problems like limited space and suceptibility to scratches.
Harddisk prices have gone down… a lot. So there is really no excuse for not getting one. There are sub-terrabyte ones at throwaway prices. I recommend the Western Digital’s handy Passport 500 GB.
Ebooks
Can anyone guess what’s the most heaviest thing to transport? Yep, it is undoubtedly books. The weight of a carton of books can exceed that of a TV, Microwave or even a carton full of iron boxes. I think everyone who love books would have had to part with them if they have had to travel a lot. They would have given away most of it to friends or relatives, never to see them back again.
This is sad. I don’t like giving away books. Neither do I want to kill my desire to create a personal library. I suggest an eco-friendly compromise – make a digital library. Do invest in Ebooks and Audio books. I have invested heavily in a collection that I am sure I can use anywhere once ebook readers become more cheaper. For now, I don’t mind reading them on my laptop. And yes, my library weighs less than a kilo ;)
Gamepad
I am a guy who is always tempted to buy game consoles. I have made up my mind a hundred times to buy a playstation or a nintendo, only to find that the latest PC is much better at it. And you know what PCs are always ahead in terms of sheer processing power. Except that they have clumsy input devices. Ever tried to play a racing game with a keyboard? Then you will know what I am talking about.
This is easily fixable. A USB gamepad (which looks like a PS2 Gamepad) comes in for less than Rs. 500. It is a great value for money. It has all the 4 way controls, shoulder buttons and 2 joysticks. Plus it has a built-in vibrator (no batteries needed)! I am planning to go for a second one. Now you can safely give your PC to your 5-year old cousin to play Mario Kart without fearing that he with smash your keyboard to bits shouting ‘Maaario’:)
Decent Mattress
Some one rightly said that we spend one-thirds of our life on a mattress. So why not in a really good one? There are cots in the market all the way from Rs 200 to branded mattresses worth several tens of thousands. Go for a really good branded mattress. It might cost a couple of grand, but you will not lose sleep over it ;)
Portable Home-kit
A briefcase sized kit that contains a small drill, spanners, measuring tape, pipe wrench, screwdriver set etc costs less that Rs. 2000 these days. I think it is well worth the price.
Those were, in my opinion, the best little things that don’t cost you a fortune. What are the ones you feel give you great value for money? Do add in your comments.
Little by little
Soft pink tiny hands
Thump, thump… thump, thump
Travel to unexplored lands
Thump, thump… thump, thump
A gingerly turn
A confident roll
Ebbing everywhere
Her ropey drool
Bangled hands on plastic chairs
Tap, tap…. tap, tap
Music to her little ears
Tap, tap…. tap, tap
Kitten eyes
On a sorry face
When I sigh
upon a broken vase
Grandfather clock smiling above
Tick, tock… tick, tock
She smiles back beaming with love
Tick, tock…. tick, tock
