Statusreport in his new blog Ingeration has compiled a list of top challenge sites. I must admit, I already knew some of them in the past and he also told me about some of them earlier. Still, this time around I tried Electrica. Well, it’s really fun solving those puzzles with Python. I’m afraid to start Python Challenge again, after stopping a long time ago; I still have my homework to do!
Caching is easy. Consider the cache I used to optimize the recursive spring:
This kind of cache is simple and effective (especially for recursions), and may be used in all sorts of situations. However, sometimes you want a size limited cache. In that case you have to decide on the criterion used to decide which items to throw away. There are many kinds of criteria used, for further reading check out wikipedia.
For now I'd like to discuss the LRU cache though. LRU stands for Least Recently Used, which means that you throw away the items you didn't use for a long time. Time in this case is measured by actions. I thought of this type of cache when I worked on the recursive spring. Since each step in the 'recursivation' used two samples of the previous step, caching was an obvious choice, and if I had to size limit my cache, LRU whould be the type of cache to use, as you could be certain that the older samples would not have to be used until the next drawing.
The challenge for the weekend is to write an LRU cache in Python. The cache has to be general - support hash-able keys and any cache size required. It has to be efficient - in the size of the cache and the time it takes for a lookup and an update. Once the standard requirements have been met, the big competition should be on elegance. I wrote a benchmark implementation, which is efficient, but not fast. Once I see some solutions, I'll talk a bit about mine, which is an interesting case-study.
It has become a tradition for computer scientists to create various self referential 'strange loops'. Traditions such as writing a compiler in the language it compiles are actually quite useful - and also very interesting. This tradition also branched to another one (also mentioned in the linked article) of writing programs that output their own source (without disk access and other dirty tricks).
The challenge is obviously to write such a program in Python, in as few lines as possible. Here is my solution, which is at two lines. I urge you to try it for yourself before looking, it is a very educating challenge. I'll be very much interested in seeing a one-liner for this problem, or a proof that such a one-liner does not exist.
If you are interested in the bigger challenge, of writing an interpreter for Python in Python itself, go check out PyPy first.
For those interested in other 'strange loops', find a copy of 'Godel Escher Bach'. If you happen to live in Israel, and can come to Haifa, I might even lend you my copy (once I get it back :)
I bet I already wrote that sometime earlier, but I found myself today writing the following function:
def blocks(seq, block_len):
"""blocks(range(5),2) -> [[0, 1], [2, 3], [4]]"""
seq_len = len(seq)
if seq_len%block_len == 0:
num_blocks = seq_len/block_len
else:
num_blocks = 1 + (seq_len/block_len)
result = [[] for i in xrange(num_blocks)]
for idx, obj in enumerate(seq):
result[idx/block_len].append(obj)
return result
I am not satisfied with this implementation.
The challenge is to write it in a more elegant and short manner. Functions from Python's standard modules are considered valid solutions.
Ready? GO!
My Twitter