Mars Rover in Python and Haskell
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!
Distantly Related posts:
Trackbacks and Pingbacks
Leave a Reply
Additional comments powered by BackType
Mars Rover in Python and Haskell http://goo.gl/fb/idD2
This comment was originally posted on Twitter
Mars Rover in Python and Haskell | Arunrocks http://bit.ly/9vDlWV
This comment was originally posted on Twitter
Arun Ravindran: Mars Rover in Python and Haskell http://bit.ly/c3PhNd
This comment was originally posted on Twitter
So is it possible to see your solution anywhere? I didn’t see any link.
Hi Martin,
I suppose you saw this post at some aggregation site. The code snippets were embedded in the original post. The Python code and Haskell code were provided
Oh, I see. With javascript deactivated the code is not visible.
May I suggest some modifications :
1) I remove your eval (because eval is evil) and replace it by a look in locals() 2) I remove your 2d vector arithmetic and replace it by complex arithmetic. Lot of people always forget about python builtin complex number support which is quite nice for 2d point operations ;)
One letter function names corresponding to each robot instruction
r = lambda x, a: (x, (a + 1) % 4) l = lambda x, a: (x, (a - 1) % 4) m = lambda x, a: (x + shifts[a], a) raw_input() # Ignore the grid size while 1: # parse initial position triplet x, y, dir = raw_input().split() pos = (int(x) + 1j * int(y),dirs.find(dir)) # parse instructions instrns = raw_input().lower() # Invoke the corresponding functions passing prev position for i in instrns: pos = locals()i print int(pos[0].real), int(pos[0].imag), dirs[pos[1]]May I also suggest replacing raw_input() / while 1 stuff by a more concise generator stuff:
One letter function names corresponding to each robot instruction
r = lambda x, a: (x, (a + 1) % 4) l = lambda x, a: (x, (a - 1) % 4) m = lambda x, a: (x + shifts[a], a) def two_by_two(lines): while True: yield next(lines).split(), next(lines).strip() next(sys.stdin) # ignore the grid size for (x, y, dir), actions in two_by_two(sys.stdin): pos = (int(x) + 1j * int(y),dirs.find(dir)) # parse instructions instrns = actions.lower() # Invoke the corresponding functions passing prev position for i in instrns: pos = locals()i print int(pos[0].real), int(pos[0].imag), dirs[pos[1]]This remove the EOFError ;)
I like that kind of little snippets of code, there is always something fun to enhance (in good or bad…)
Thank you guillaum, for those lovely suggestions. I was not happy with using eval myself as it is not really safe. Given some more time a method-lookup was something I would’ve preferred.
The complex arithmetic bit was really clever :)
If your using complex arithmetic you can recode the the l() and r() functions as rotations in complex form are equivalent to multiplications.
That and making dirs a dict gives the following:-
dirs = { 'N':1j, 'E':1, 'S':-1j, 'W':-1j } rdirs=dict(reversed(d) for d in dirs.items()) r = lambda x, a: (x, -1j * a ) l = lambda x, a: (x, 1j * a ) m = lambda x, a: (x + a, a ) raw_input() # Ignore the grid size while 1: # parse initial position triplet x, y, dir = raw_input().split() pos = (int(x) + 1j * int(y),dirs[dir] ) # parse instructions instrns = raw_input().lower() # Invoke the corresponding functions passing prev position for i in instrns: pos = locals ( ) [ i ]( * pos ) print int(pos[0].real), int(pos[0].imag), rdirs[pos[1]]Tested aginst the test vector only.Pah Thats:-
And the interpreter line of :- for i in instrns: pos = locals ( ) [ i ]( * pos )
which keeps getting eaten by the blog softtware,..
Apologies for not mentioning that comments are have markdown processing enabled. I have fixed the formatting in your original comment.
Mars Rover in Python and Haskell http://goo.gl/fb/idD2
This comment was originally posted on Twitter
I have to say, your Python code is just damn beautiful. Wonderfully idiomatic. (Err…one little quibble…using “i” to parse the character instructions gave me a little pause — I kept trying to figure out what you were doing with the integer inside the eval() expression. Woulda been better to use a more descriptive name.)