Friday, December 08, 2006

Codegolf

Ive been working on this codegolf challenge recently which I found quite fun to do (codegolf == accomplish a challenge in code using least amt of lines )

The challenge in question:-

The game of REVERSE requires you to arrange a list of numbers in numerical order from left to right. To move, you tell the computer how many numbers (counting from the left) to reverse. For example, if the current list is 2 3 4 5 1 6 7 8 9 and you reverse 4, the result will be 5 4 3 2 1 6 7 8 9. Now if you reverse 5, you win.

What we're asking you to do is, given a list of numbers in a random order, produce the moves required to arrange them so they end up in numerical order.

(from codegolf.com)



Now Ive been working on this for a couple of hours and the best I can come up with is this ( My language of choice, python):-


[UPDATE #1]: File Size - 181kb

1) Changed the while loop condition

2)A different way of printing, by adding a comma after the last object one can suppress the new line that is automatically added by print in python

3)Removing unnecessary indentation helped on the file size

4)Didnt need the strip function

import re,sys
n = map(int,re.split(" ",sys.stdin.readline()))
l = len(n)
while l:
m = n.index(max(n[0:l])) + 1
n[:m] = n[m-1::-1]
n[:l] = n[l-1::-1]
print m,l,
l -= 1


[ORIGINAL]


import re,sys
n = map(int,re.split(" ",str(sys.stdin.readline()).strip()))
l = len(n)
while n != sorted(n):
m = n.index(max(n[0:l])) + 1
n[:m] = n[m-1::-1]
n[:l] = n[l-1::-1]
print m,"\n",l
l -= 1


the algorithm works in the following way:-

given a list, get its length

find the index of the maximum value within it, do a reverse from 0 to the index, so now the max is in front (and the move being the index + 1)

then do a reverse again on the length of the list , bringing the max to the end of the list (now the move after that being the length of the list)

decrease the length, so you iterate over a smaller list and repeat the same steps on the smaller section of the list


Anyone have anymore ideas to make this shorter ( either the program itself or the algorithm ) ?

1 comment:

ilmanzo said...

hi,

to cut on code size, you don't need any import:


n=map(int,raw_input.split())


just my 2 eurocents from a fellow pygolfer ;)