Whatever code you write, you always write it better if you write it again. This has never failed to be true in my case. Very often I have been happy to have deleted programs (by mistake) because they have been so much better on the second run.

Coming to the point, Swaroop took part in the Google Code Jam ( don't ask me why I didn't, I honestly don't know) and gave me what he thought was the toughest question of the second round.

Now I have Gopal for company to hack around ( boy! am I happy ) and we decided to try some XP on it. No marks for guessing which language we chose - python of course. Ya now I know, GCJ had only C++ and Java :P

The concept of pair programming, at least the way we tried it, is very simple. Two people take up a problem simultaneously and try their own approaches in parallel. In sometime, it becomes evident that one approach has a better chance of succeeding than the other, and then you sit together and write code further. It does work really well, in most cases.

Being not at all new to programming contests ( that's how I got my job @ Y! - through a programming contest ) I know a damn and dirty way of solving any problem you give me - game trees and recursion. The philosophy is very simple - "When in doubt, use brute force". Put more technically, at any point in a problem, you have a finite number of paths you can follow. If you follow all of them at every point ( use recursion ), you will cover all possible solution paths. This is hopelessly inefficient as it is O(n^n) and uses recursion, but there has hardly been a problem it cant solve. There are some problems you can only solve that way, the 8 queens problem for instance. Then you do what is called alpha pruning and reduce the number of trees. Will post on it sometime.

So this problem got solved too, and Gopal and I got together and optimised and reduced the execution time from 65 seconds to 3.5 seconds as it often happens with alpha pruning - some branches of the tree just need not be there.

Coming back to my original point, the solution I had was way better the second time around: I solved the same problem today evening in 20 minutes writing 25 lines of python code using good old for-loops and it has sub second execution times even in python!

It makes me feel silly now that I ever tried to use recursion for this.

As they say, hindsight is always 20-20!


The problem:
You are given a sequence. You need to compute the minimum number of moves ( numbers in the sequence you need to change) you need to turn the sequence to an AP( Arithmetic Progression )

Disclaimer: The original problem statement is different and is an IP of TopCoder.

The solution:

def computeMinMoves(sequence):
	length = len(sequence)
	minmoves = length - 2#any sequence can be converted to an AP in n-2 moves
	for i in range(length):
		for j in range(i+2,length):
			if ( sequence[j] - sequence[i] ) % (j -i) == 0:
				moves = 0
				useless = False
				d = (sequence[j] - sequence[i])/(j-i)
				newsequence = sequence[:]
				for k in range(length):
					if k < i:
						newsequence[k] = sequence[i] - (i-k)*d
					elif k > j:
						newsequence[k] = sequence[j] + (k-j)*d
					elif k > i and k < j:
						newsequence[k] = sequence[i] + (k-i)*d
					if newsequence[k] != sequence[k]:
							moves = moves + 1
					if moves > minmoves:
						useless = True
						break
				if useless == True:
					continue
				if moves < minmoves:
					minmoves = moves
					#print "sequence: ",newsequence,"Moves: ",moves
	return minmoves

[Update] Changed the loop for j to range(i+2.length). For j = i+1, if we are producing an AP using only 2 numbers, we are getting minmoves = length -2, which is what it will return anyway, if it doesn't find a better solution. If there is another number apart from these 2 that falls in the same AP, that would be taken care of by the loop :). The code keeps getting better ;)

Tags: programming, python, tech
Current Mood: geeky
Current Music: pal