Category Archive: Code

Mancala

The board has two rows of six holes with a single large hole (Mancala) at each end. To start, each of the holes (except the Manacalas) have 4 stones.

Players take turns picking up all of the pieces in one of the holes on their side. The player deposits one of the stones in each hole, moving counter-clockwise until the stones run out. The player deposits stones into their own Manacala but not their opponenets. If the last stone falls in the players Manacala, they go again. If the last stone falls in an empty hole on the players side and there are pieces across from it (on the opponenets side), they capture that piece and the opposing pieces.

The game is over when one players side in empty. If the other player still has pieces on their side, those pieces are theirs. The winner is the player with the most stones

Read the rest of this entry »

Sudoku Solver

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.

Functional Decorator

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 2N 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)

CodeIgniter Unit Testing

I’ve been doing a lot of development using the CodeIgniter framework for the last few months. I’ve been looking to get into TDD, but upon inspection, I found the CodeIgniter unit tests to be a little lacking. One of the things I feel is a must for decent testing of a web app is a database mock. 90% of what I’m doing is moving data back and forth to the database, it’s also the most error prone code. I put my test class in a controller so that it was completely self contained, you could move it to a model if that would fit better. It should be easily extendible. It has a number of type check unit tests built in. It also has a setup_mock_db function that expects to find a ‘test’ database. WARNING: this function completely drops all tables it find in the test database, so use it carefully. The idea here is that you can make schema changes to your development database and they will be automatically reflected to your unit testing. Also, I know, if I’m talking to a database it’s not technically a unit test  – but if I’m not talking to a database it’s not technically helpful, at least I’m not talking to the main database, but a dedicated testing database.

When the unit test are called, most take two argument, some take three. The first argument is the result of a function. This result is going to be type checked. In the cases that take three arguments, the second argument is used for comparison (is_equal, is_not_equal). The third argument is the name of the test, this gets printed in the results report so you can identify what you were testing. I normally use a chunk of code here. Here’s what some of my unit tests look like

$this->is_false($this->user_model->is_valid_email("not an email"), 'is_valid_email("not an email")');
$this->is_null($this->user_model->log_out(), 'log_out()');

Here’s the actual controller class, I’ve removed my tests. I generally break up the tests into chunks so that I can test portions of my site. I then use the index method to call all of the chunks so I can test the whole site at once. I print a lot of HTML raw because I didn’t want to have to build views to go with this. Just drop in the controller and the unit testing is all set to go.

 

Function Invocation

The keyword ‘this’ can cause a lot of confusion in JavaScript (along with many other languages). It can change depend upon how a method is invoked. Below is an example that invokes the same method three different ways, and produces three different results.

unction sayName(){
  name = "sayName";
  alert(this.name);
}
var obj = {
  name: "obj",
  sayObjectName: sayName
};
var x = {};
x.name = "x";
 
function run(){
  sayName(); // sayName
  obj.sayObjectName(); // obj
  sayName.apply(x,null); // x
}

Words in a File

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()]))))

Image Cloud

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)

Euler 30

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

1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44

As 1 = 14 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)

Euler 31

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 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

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)

Euler 5

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

Older posts «