This code ended up being significantly simpler than I had expected. This solution looks at each empty cell, finds all the numbers that cell could be (aren’t in the same column, row or square) and makes a guess. It then moves on to the next cell and makes another guess. It keeps doing this until it comes to a square with no possibilities, in which case it made a mistake somewhere, or it solves the puzzle. If it made a mistake it backs up to it’s last guess and tries the next possibility. If there’s no possible numbers left, it backs up the guess before that and so on.

The code is an excellent example of the power of recursion.

puzzle = [
0,0,0, 0,0,0, 0,0,0,
0,0,0, 0,0,3, 0,8,5,
0,0,1, 0,2,0, 0,0,0,
 
0,0,0, 5,0,7, 0,0,0,
0,0,4, 0,0,0, 1,0,0,
0,9,0, 0,0,0, 0,0,0,
 
5,0,0, 0,0,0, 0,7,3,
0,0,2, 0,1,0, 0,0,0,
0,0,0, 0,4,0, 0,0,9
]
 
def listPossible(x,y,puzzle):
    """ Given a cell coordinate and a puzzle, return all values that do not occur in the square, row or column as that cell """
    indexesOfCol = range(y*9,(y+1)*9)
    indexesOfRow = range(0+x,81+x,9)
    upperLeftOfSquare = (y - y % 3)*9 + x - x % 3
    indexesOfSquare = [upperLeftOfSquare + sqX + sqY for sqX in range(0, 3) for sqY in range(0, 9*3,9)]
    notPossible = [ puzzle[index] for index in indexesOfRow + indexesOfCol + indexesOfSquare if puzzle[index] != 0 ]
    return [i for i in range(1,10) if i not in notPossible]
 
def display(puzzle):
    for y in xrange(9):
        print " ".join( str(puzzle[x + y*9]) for x in xrange(9)  )
    print #add a line after the puzzle
 
def treeMethod(puzzle):
    """ The treeMethod braches out filling in each possibility for a square until it runs into contridiction,
    then it backs up and tries another brach. """
    if 0 not in puzzle: return puzzle
    #emptyCells will hold information about each empty cell
    #it will gather the number of possibilities, the index and a list of the possibilities
    emptyCells = []
    for i in xrange(81):
        if puzzle[i] == 0:
            possibilities = listPossible( i%9, i/9, puzzle)
            emptyCells.append( (len(possibilities), i, possibilities) )
    # Now emptyCells gets sorted on the number of possibilities
    # therefore, it will grab the index with the fewest possibilities
    l, i, possibilities = sorted(emptyCells)[0]
    for guess in possibilities:
        puzzle[i] = guess
        guessResult = treeMethod(puzzle)
        if guessResult: return guessResult
    # We've exhaused possibilites, this branch does not contain a valid solution
    # Set the index i back to 0 and the function will exit (returning None)
    puzzle[i] = 0
 
solution = treeMethod(puzzle)
display(solution)

A few points of interest. Initially I had a puzzleSolved function that checked if the puzzle was solved correctly. But this method will not solve a puzzle incorrectly if a solution is possible, so I only need to check that if there are any blanks left and if there are none, the puzzle is solved. One thing that surprised me about this solution was how efficient it is. The treeMethod function generally gets called around 200 times to solve a puzzle. This is very good considering that a puzzle generally has about 50 empty cells and that this the minimal number of calls any solver could make. My friend gave me the puzzle that is in there now which is designed to specifically break this sort of brute force solution. My original solution would have taken over 600 million loops to solve. To mitigate this, I find all empty squares and always try the cell with the fewest possibilities which brings it down to around 45 thousand loops.

The following is a program that demonstrates a use of the Python decorator. The following stores all function calls in a dictionary so that if the same call is repeated, the answer can be retrieved instead of calculated. The most outstanding piece of demo code here the Fibonacci function. To calculate the one hundredth number in Fibonacci sequence using a recursive function would normally require 2^N calls (for fibb(100) that would be 1.27E30 calls), but with the functional decorator it requires N. The function at the bottom ‘Goofy’ is a non-sense equation I came up with to demonstrate that multi-argument functions work as well. I couldn’t find a good recursive function for this purpose.

from math import sqrt
 
def functional(func):
  def build(*x):
    try:
      if x not in func.D:        #check if value exists in the functions dictionary
        func.D[x] = func(*x)     #if its not there, calculate
    except:                      #if the function doesn't have a dictionary defined yet
      func.D = {}                #create dictionary
      func.D[x] = func(*x)       #calculate value for x
    return func.D[x]             #return value
  return build
 
@functional
def fac(x):
  if (x < 2):
    return 1
  return fac(x-1) * x
 
@functional
def fibb(x):
  if ( x < 2 ):
    return 1
  return fibb(x-1) + fibb(x-2)
 
@functional
def is_prime(x):
  for i in xrange(2,int(sqrt(x))):
    if is_prime(i) and ( x % i == 0 ):
      return False
  return True
 
@functional
def goofy(x,y):
  if x == 0:
    return y
  if y == 0:
    return x
  return goofy(x%y,x) + goofy(y%x, y)
 
print "goofy(6,5) = ", goofy(6,5)
print "fac(100) = ", fac(100)
print "fibb(100) = ", fibb(100)
print "is_prime(10123468391) = ", is_prime(10123468391)
print "is_prime(10123468392) = ", is_prime(10123468392)

I was given the challenge to write a Python program to parse a file and count how many times each word occurs, then print them in order of appearance. To accomplish this, I open the file and use regex (“\W+”) to split the file into a list of words. I use the words as keys in a dictionary so we can count how many times we see each word. I use the ‘get’ method to automatically initialize the count to zero if it’s the first occurrence of the word. I then use a list comprehension to reduce the dictionary down to a list of tuples which are then sorted. Finally, I convert each tuple into a string and join them all together with newlines.

import re
import sys
 
# Read File Contents
fileString = open(sys.argv[1],'r').read().lower()
 
# Build a word count
finalCount={}
for word in re.split('\W+', fileString):
    finalCount[word] = finalCount.get(word,0)+1
 
# Sort the word count and print out to a file
sortedWordList = sorted([(count,word) for (word,count) in finalCount.items()])
open(sys.argv[2],'w').write("\n".join(map(str,sortedWordList)))

I managed to condense lines 8 through 10 into a single line, but it’s ugly. I’ll leave it up to you to figure out how it works (and please, never use anything like this in production code).

finalCount=reduce(lambda d,k : (d.update({k:1+d.get(k,0)}), d)[1], re.split('\W+', fileString), {})

Or, if we want to write really bad, but concise code, here’s the whole program (two lines, but I had to split the second line)

import re, sys
open(sys.argv[2],'w').write("\n".join(map(str,sorted([(c,w) for (w,c) in reduce(lambda d,k : (...
                 d.update({k:1+d.get(k,0)}), d)[1], re.split('\W+', open(sys.argv[1],'r').read().lower()), {}).items()]))))

My friend, Stephen, wrote a version of this program a long time ago in QBasic. When I was looking to experiment with generating images in python, it seemed like the perfect test program. The idea is to start with a bunch of squares. Pick, a random point, then pick one of the 8 points that touches it and average the two colors. Over time it develops a cloudy look. The program I wrote changes 9,000 points, then renders a frame. I’ve included a movie that is 1500 frames (1 minute) so you can see the image go from squares to almost flat gray. I used the image sequencer in Blender to generate the movie from the raw PNGs that the program makes.

Movie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

import Image
import ImageDraw
import random
 
def GetRandomColor(mode):
    """Chooses a random color based on the cloud mode"""
    if (mode=="AllColors" or mode==0):
      return dict(((c, random.randint(0,255)) for c in cloud.colors))
    elif (mode=="Gray" or mode==1):
      c = random.randint(0,255)
      color = { 'r':c, 'g': c, 'b': c }
      return color
    elif (mode=="BlackAndWhite" or mode==2):
      c = random.randint(0,1)*255
      color = { 'r':c, 'g': c, 'b': c }
      return color
 
class Pixel(object):
  """Manages pixesl for the cloud. Holds color and position information"""
  def __init__(self, x, y):
    self.r = self.g = self.b = 0
    self.coords = (x,y)
  def SetColor(self, color, draw):
    """Sets the color of this pixel and draws itself using the image draw object passed in"""
    self.r = color['r']
    self.g = color['g']
    self.b = color['b']
    draw.point(self.coords, fill = "rgb(" + str(self.r) + "," + str(self.g) + "," + str(self.b) + ")")
 
class Cloud(object):
  """Draws a cloud object by repeatedly blending adjecent pixels in a grid of colors"""
  dirs = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))
  colors = ('r', 'g', 'b')
  def __init__(self, imgSizeX = 100, imgSizeY = 100, mutationsPerFrame = 0):
    """Build list of pixels"""
    self.pixels = [ Pixel(x,y) for x in range(imgSizeX) for y in range(imgSizeY)]
    if mutationsPerFrame == 0:
      mutationsPerFrame = (imgSizeX * imgSizeY) / 10
    self.mutationsPerFrame = mutationsPerFrame
    self.imgSize = (imgSizeX, imgSizeY)
    self.img = Image.new("RGB",self.imgSize)
    self.draw = ImageDraw.Draw(self.img)
  def Save(self, name):
    """Save image"""
    self.img.save(name+".png","PNG")
  def ColorSquare(self, at, squareSize=(10,10), mode=0, color=None):
    """Add a square of color defined by at and squareSize"""
    if color == None:
      color = GetRandomColor(mode)
    edgeRanges = [range(start,start+d) for start, d in zip(at,squareSize) ]
    for pixel in (self.__Pixel(x,y) for x in edgeRanges[0] ...
             for y in edgeRanges[1] if x < self.imgSize[0] and y < self.imgSize[1]):
      pixel.SetColor(color,self.draw)
  def ColorRandomGrid(self,mode=0, stepSize=(10,10)):
    """Fills the image in with a grid based on the cloud mode"""
    for coord in ( (x,y) for x in range(0, self.imgSize[0],...
             stepSize[0]) for y in range(0, self.imgSize[1], stepSize[1])):
        self.ColorSquare(coord, stepSize, mode)
  def __SetPixelColor(self, coord, color):
    """Set color of one pixel"""
    pixel = self.__Pixel(*coord)
    pixel.SetColor(color, self.draw)
  def Run(self, frames):
    map(self.__RunOneFrame, range(frames))
  def __RunOneFrame(self,frame):
    for i in range(self.mutationsPerFrame):
      self.__DoOneMutation()
    self.Save("frame_"+str(frame))
  def __DoOneMutation(self):
    """Picks a random pixel, then one of its neighbors,
    finds the average color between them and sets them both to that color"""
    randomCoord = [random.randint(0,i-1) for i in self.imgSize]
    randomPixel = self.__Pixel(randomCoord[0],randomCoord[1])
    pixels = ( randomPixel, self.__GetNeighbor(randomPixel))
    newColor = {'r': 0, 'g': 0, 'b': 0}
    for pixel in pixels:
      for c in Cloud.colors:
        newColor[c] += pixel.__dict__[c] / 2
    for pixel in pixels:
      pixel.SetColor(newColor, self.draw)
  def __GetNeighbor(self, pixel):
    randomDir = random.choice(Cloud.dirs)
    neighborCoord = [ (x+y) % m for x,y,m in zip(pixel.coords, randomDir, self.imgSize) ]
    return self.__Pixel(neighborCoord[0], neighborCoord[1])
  def __Pixel(self,x,y):
    """Gets a pixel from the the pixels list by coordinate"""
    return self.pixels[x*self.imgSize[1] + y]
 
if __name__ == "__main__":
  cloud = Cloud(300,300)
  cloud.ColorRandomGrid("BlackAndWhite")
  cloud.Run(1500)

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

As 1 = 1⁴ is not a sum it is not included.
The sum of these numbers is 1634 + 8208 + 9474 = 19316.
Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.
Link to Problem 30

# 354294 this is the largest possible number
# 354294 =9^5+9^5+9^5+9^5+9^5+9^5 for 999999
answer=0
for i in range(10,354294):
    sum=0
    temp_string=str(i)
    for j in range(0,len(temp_string)):
        sum+=int(temp_string[j])**5
    if (sum==i):
        print i
        answer+=i
print "Answer: "+str(answer)

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1£1 + 150p + 220p + 15p + 12p + 31p

How many different ways can £2 be made using any number of coins?

Link to Problem 31

def waysToMakeChange(amount, coins, waysFound = 0):
  if (amount==0 or len(coins)

Lines 5 through 7 can be summarized to a single line, but it is very difficult to read

return sum( (waysToMakeChange(amount-i*coins[0],coins[1:]) for i in range(0,1+amount/coins[0])) )

Before I get to the last version, let me say, this is for academic exercise only and nothing like this should ever be used in a production system. It is a single line, but I had to break it to fit on the page.

print (lambda a,c,f:f(a,c,f))(200,[200,100,50,20,10,5,2,1],lambda a,c,f:((a==0 or len(c)

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?
Link to Problem 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

import math
 
#find the smallest number that is evenly divisible by all of the numbers from 1 to N
 
#use a sieve to find all primes. Start with a boolean array, initially all set to true
#mark multiples of primes as false as they are found. When a prime is found, start marking
#false at prime squared.
def primes(x):
    # get all primes upto x
    x=int(x)
    if x<2: return []
    L=[True]*(x-1)
    p=[]
    for i in range(2,int(math.ceil(math.sqrt(x))+1)):
        if L[i-2]:
            p.append(i)
            for j in range(i*i,x+1,i):
                L[j-2]=False    
    for i in range(int(math.ceil(math.sqrt(x)))+1,x+1):        
        if L[i-2]:
            p.append(i)
    return p
 
 
#find the smallest number that is evenly divisible by all of the numbers from 1 to N
N=20
P=primes(N)
ans=1
for i in P:
    ans*=i**math.floor(math.log(N,i))
    # the answer is the i (a prime) raised to the highest integer such that the result is lower than N
    # to find that number we round down from the log of N base i. So in the case of log 20 base 2
    # we round down to 4 because 2**4 is 16, less than 20, but 2**5 would be 32.
print ans

A Pythagorean triplet is a set of three natural numbers, a b c, for which,
a² + b² = c²
For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.
Link to Problem 9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def f(x):
    # Given: a²+b²=c² and a+b+c=1000
    # then: c=1000-a-b :.
    # a²+b²=(1000-a-b)² :.
    # a²+b²=1000000-1000a-1000b-1000a-a²+ab-1000b+ab+b² :.
    # 0=1000000-2000a-2000b+2ab :.
    # a=(1000000-2000b)/(2000-2b)
    return (1000000.0-2000.0*x)/(2000.0-2.0*x)
 
a=0
b=1.1
while b != int(b):
    a+=1
    b=f(a)
 
c=(a**2+b**2)**.5
 
print a*b*c

The following iterative sequence is defined for the set of positive integers:

n n/2 (n is even)
n 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 40 20 10 5 16 8 4 2 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
Link to Problem 14

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# To do this efficiently we use a dictionary to remember how many steps it takes to get to
# 1 from any other number. This allows us to use a recursive function, but never perform
# the same calculation twice
 
def sequence(x):
    def f(x):
        if x==1: return 0
        if x%2==0:
            return sequence(x/2)+1
        else:
            return sequence(3*x+1)+1
    try:
        if x in sequence.d:
            return sequence.d[x]
    except:
        sequence.d = {}
    sequence.d[x] = f(x)
    return sequence.d[x]
 
large=0 # track the largest value
ans=0 # track the answer corresponding to the largest value
for i in range(1,1000000):
    temp=sequence(i)
    if temp>large:
        large,ans = temp, i
 
print ans

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.
Link to Problem 21

def sum_of_div(x): # sum of all divisors of x
  def f(x):
    sum=1
    for i in range(2,int(x**.5)):
      if (x%i == 0):
        sum += i + x/i
    if int(x**.5) == x**.5:
      sum += x**.5
    return sum
  try:
    if x in sum_of_div.d:
      return sum_of_div.d[x]
  except:
    sum_of_div.d = {}
  sum_of_div.d[x] = f(x)
  return sum_of_div.d[x]

def is_amicable(x): # return true if x is amicable
    a=sum_of_div(x)
    b=sum_of_div(a)
    return b==x and a!=x

def sumOfAmicablePairs(x):
  sum=0
  for i in range(1,x):
    if is_amicable(i):
      sum+=i
  return sum

print sumOfAmicablePairs(10000)