July 18, 2008 – 1:09 am
Just one of the problems that I finished solving a few hours ago for google code jam. It’s the first time I tried a programming competition, and it’s a pretty interesting one. Problems are hard but solvable and you always get a few sample inputs and outputs, which is really really helpful. Programming competition often focus on speed of execution and python isn’t a good competitor then (except for a scripting language around C maybe), but I think code jam is a lot more focussed on the algorithm: you’ve got a bad algorithm ? You’ll be too slow anyway. You have a good one ? Your program will be fast enough in python or (even probably) ruby.
I see problems in three categories:
- problems complicated to understand or to translate to a program but without algorithmic complexity (if your implementation works it’s usually fast enough) and without too much math, think string manipulation for example, or parsing a grammar
- the same but with the complexity based on math, often geometry problems requiring a good knowledge of trigonometry, yeah the hit a fly with a tennis racquet problem is one of them
- problems that you can easily make into an inefficient brute force program, but that get hard when trying to solve with an efficient algorithm
I don’t like the first category: you make a program that works with the few examples you have and then if you are lucky you’re finished pretty quickly. But because there are so many cases it will probably break in some situations, and you can’t know which ones, and you can’t really test your program cause you don’t know what the output should really be. To test your program you would need to reimplement it in another way and since you have already done the easier way … well it’s hard.
The second type is … harder when you don’t have (or have forgotten) the math skill … easier if you’re a math nerd. After having solved the math problem implementing the program is usually easy enough.
The third type is fun. You can start by implementing a brute force method quickly, that will obviously be too slow for large inputs, but then you can use this method to compare the result with your optimized method, if your optimized method doesn’t always provide the good result. And I like this category of problems, I like exploring the space of solutions in a smart way. Here is a small class I made to write exploring code quickly, but which is often not efficient enough …
class Explorer(object):
"""The explorer class to explore a finite tree of possibilities.
The basic usage is
e = Explorer()
while e.next():
person = e.choose(['Linus', 'Theo'])
if person == 'Linus':
object = e.choose(['the linux guru.', 'a stupid dickhead.'])
elif person == 'Theo':
object = e.choose(['the openbsd guru.', 'a masturbating monkey.'])
print person, 'is', object
Which should display:
Linus is the linux guru.
Linus is a stupid dickhead.
Theo is the openbsd guru.
Theo is a masturbating monkey.
"""
def __init__(self):
"""Init isn't enough you need to call next after initialising.
"""
self.current_branch = None
def next(self):
"""Start a new branch. Return False if it is the end. True if it is not.
"""
if self.current_branch != None:
branch = self._next_branch(self.current_branch)
if branch == None:
return False
else:
branch = []
self.infinite_branch = self._infinite_branch(branch)
self.current_branch = []
return True
def choose(self, list):
"""Choose an element in a list.
"""
choice = self.infinite_branch.next()
self.current_branch.append((choice, len(list) - 1))
return list[choice]
def choose_or_not(self, list):
"""Choose an element in a list, or return None.
"""
choice = self.infinite_branch.next()
self.current_branch.append((choice, len(list)))
if choice == 0:
return None
return list[choice - 1]
def _next_increment(self, branch):
for i, (choice, maximum) in enumerate(reversed(branch)):
if choice != maximum:
return len(branch) - i - 1
return None
def _next_branch(self, branch):
position = self._next_increment(branch)
if position == None:
return None
result = branch[:]
result[position] = result[position][0] + 1, result[position][1]
for i in range(position+1, len(result)):
result[i] = (0, result[i][1])
return result
def _infinite_branch(self, branch):
for choice, maximum in branch:
yield choice
while True:
yield 0
Oh yeah I don’t actually answer the question in the title … I don’t really feel like explaning all the problem actually. I’ll just say that I solved it thanks to sage. It’s a great replacement for a TI-89, or matlab, or mapple or mathematica. It’s all of that and more, and in python. The language is actually a very slightly modified python. Here is an example that was helpfull in solving the tennis racquet problem:
sage: var('x')
x
sage: integral(cos(asin(x)))
arcsin(x)/2 + x*sqrt(1 - x^2)/2
Posted in Uncategorized | No Comments »
[from wikipedia but can be easily calculated as the integral of the force]
I’m using GIMP 2.4 at my job to make a website and I heard a lot of people bad-mouthing it so I expected having a bad time with it, but it’s really usable. And I had no experience of it before, my previous experience of photo editing takes me back 7 years ago in high school and with some Paint Shop Pro.
At work I have Photoshop in a windows within a VirtualBox in my Ubuntu, and … it’s awfully slow. I mean gimp isn’t fast to start up but Photoshop is something else. It takes about 20 seconds to start up.
So having the choice between the two I chose to use Gimp and I’m really happy with it. Can’t wait to try 2.6 and all its new nice features.