Sunday, November 13th, 2011
Monte Carlo is a simulation method that can be useful in solving problems that are difficult to solve analytically.
Here's an interesting application of the technique to estimate the value of pi.
Consider a circular dartboard placed against a square backing, with the sides of the square perfectly touching the circle tangentially ...
Posted in programming | 3 Comments »
Friday, August 27th, 2010
I've been looking at the element-wise operations in Numpy arrays. The code below generates 100K primes in about 1.3 secs on my laptop.
[sourcecode language="python"]
import numpy
import math
def prime(upto=100):
return filter(lambda num: (num % numpy.arange(2,1+int(math.sqrt(num)))).all(), range(2,upto+1))
[/sourcecode]
>>> prime()
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...
Posted in programming | 7 Comments »
Thursday, August 26th, 2010
I've wanted for a while to write simple python simulations of the birthday puzzles I'd written about previously. Then, recently, I was wondering what the most efficient way to tell if a list has duplicate elements. It suddenly dawned on me that these two topics were related:
The ...
Posted in programming | No Comments »
Tuesday, August 24th, 2010
Problem: Write a python function to calculate the shortest path given a start node (or vertex), an end node and a graph. Use Dijkstra's algorithm. Return the distance from the start node to the end node, as well as the path taken to get there.
The implementation ...
Posted in programming | 7 Comments »
Sunday, July 18th, 2010
I'd blogged previously about writing a python function to find out whether a linked list is acyclic or not - it's worth a read before tackling this one.
Problem: Given the head node of a cyclic (or circular) linked list, write a function to return the node that is at ...
Posted in programming | No Comments »
Friday, June 4th, 2010
Write a Python function to find all the anagrams for each of a supplied list of words. For the word dictionary to find the anagrams you could use the one found on Unix or OS X boxes at /usr/share/dict/words. So for example:
>>> for group in anagrams(['dog','cat','horse']):
... ...
Posted in programming | 2 Comments »
Thursday, June 12th, 2008
A collegue of mine was pondering the mthToLast problem for a LinkedList I'd blogged about previously and sent me the following IM message:
just a guess - but can you use recursion to solve your link list m problem?
a method to track through the list which calls itself,
then ...
Posted in programming | No Comments »
Thursday, June 12th, 2008
Very basic - take a string and reverse it using simple recursion. I'm sure there's a bunch of ways to do it, but like the fibonacci you should aim to be able to code something like the below in about 20 seconds...
>>> def reverse(str):
if len(str)==1:
...
Posted in programming | No Comments »
Tuesday, June 10th, 2008
Quick one about coding a deep copy and avoiding recursive references...
Let's say we have an instance a which has a reference to an instance b and we have to do a deep copy of a. To do this, we need a deep copy of b as well.
But let's say ...
Posted in programming | 3 Comments »
Sunday, June 1st, 2008
The last problem in the Trees chapter of Programming Interviews Exposed was about finding the lowest common ancestor between two nodes of a binary tree. Starting from the head, if you find that the nodes that you're looking for straddle the node you're on, then you've found your lowest common ...
Posted in programming | 1 Comment »