Browsing Tag

python

Latex, Mathematics, Python

PyTex2png Make Pretty Math PNG Files With Latex, Python and C++

October 9, 2015

A few months back I posted some code on GitHub to convert Latex markup code into PNG files using Python named it PyTex2png. I know realize that I didn’t explain one bit of the code. I did however write a very clear (to me) README.md file explaining how to use the code if you wanted to download and use it. I even included a couple of cool examples. In this post I want to dive into the code that make it work.

Lets start by explaining exactly what Latex is and what this module does. Latex is a markup language used for scientific notation and papers. I came across it in my second year in college and science then I have never looked back. It is by far my favorite word processor. I even have my resume and letters typed up in Latex. It just make pretty things. Among other things, Latex can create beautiful Mathematical typography like the one below. Latex does have a bit of learning curve, but it shouldn’t be too difficult to master. We are only looking at the math portion of it anyway. Here is some Latex code and the image that got generated from it. Note that this post will not teach you Latex. There are plenty of books and information about Latex online already.

Code:

\cos (2\theta) = \cos^2 \theta - \sin^2 \theta \\
\lim_{x \to \infty} \exp(-x) = 0 \\
a \bmod b \\
x \equiv a \pmod b

[\code]

Pretty Output:

 

wpid-operators-2015-10-9-00-48.png

 

So how does that happen? Well there are a few things to look at. The first is a C++ code that was written by Bruno Bachelet. It is available here (and here as backup). There is also and online version of the code running here. This code is the main power behind the software. Everything else is just a Python wrapper to add some fancy functions like multiple files, remove background and invert colors.

Within pytex2png.py you will see a function name covert(). This function calls the C++ module to convert images, creates the PNG, removes any background and finally converts the math to white. The last portion is not really required. I was coding this up for a larger project and in that one the background is not white, so I need white fonts.


def convert(source,output,display=False):
	if(display): print "Coverting LaTeX from " + source + " to " + output
	data = get_file(source).replace("\\","\\\\")
	make_png(data,output,display)
	make_transparent_bg(output,display)
	make_white_text(output,display)

This doesn’t tell us anything about how this program works. It is just a plain function that makes calls to other functions. We will have to look at the other functions to understand how this one ties everything together. Lets take a look at the code:


# read file content as a single variable
def get_file(filename):
	file = open(filename, "r")
	lines = file.read()
	file.close()
	return lines

# create png from latex
def make_png(data,image,display):
	if(display): print "Making image..."
	command_line = "./tex2png -r* -lq \""+data+"\" " + image
	exe_command(command_line,display)

# remove white background
def make_transparent_bg(image,display):
	if(display): print "Removing white background..."
	command_line = "convert "+image+" -channel rgba -fill \"rgba(255,255,255,0)\" -opaque \"rgb(255,255,255)\" " + image
	exe_command(command_line)

# convert output text to white
def make_white_text(image,display):
	if(display): print "Converting output image text to white..."
	command_line = "convert "+image+" -channel rgb -fill \"rgba(255,255,255)\" -opaque \"rgb(0,0,0)\" " + image
	exe_command(command_line)

After a careful inspection of these functions, you should see a pattern. The first one is a get_file function. All it does is open a file and reads it’s content. Then returns the data from the file as a single object. You can read more about reading a writing from files in the Python Documentation. The other 3 functions, make_png, make_tansparent_bg, and make_white_text follow a templet:

display output
build command line command
execute command

That’s all folks! it is pretty straight forward. The commands each one execute are based off of what we need done. The first one, make_png calls the executable made from the C++ module. The remanning 2 functions, make_transparent_bg and make_white_text use a command line tool called convert. This is a Unix utility and you can read all about it in the convert manual file or on this site.

You will notice that there is one function we haven’t mentioned yet, exe_command. Let’s look at that function:


# runs a command line command and waits for it to complete
# by default it will not display any output
def exe_command(cmd, display=False):
	args = shlex.split(cmd)
	if(display):
		p = subprocess.Popen(args)
	else:
		p = subprocess.Popen(args,stdout=subprocess.PIPE)
	p.wait() 


This one should be taken as is. It takes in a command line command and excites it using a Python module called subprocess. It can be used to execute and command in the command line and can retune the results if needed. It is a good little function to keep handy for other programs in the future...

That is all the magic that ties this thing together. There are some more files and notable mentions.

  • Examples folder holds text files with Latex markup to be converted.
  • Output folder will contain PNG’s that have been converted already.
  • Source has the C++ file need to make the PNG files in the first place.
  • Makefile is used to compile the C++ file and create and executable for your computer architecture.
  • examples.py is a simple Python module to load the example text files from the folder and run them through PyTex2png converter.
  • gpl-3.0.txt is a GPL License under which the code is distributed.

Here is a PyTex2png zip file with all the files together. It is also available via GitHub (pytex2png).

Cool Stuff, Python

Have you tried out Spyder-IDE for Python Dev?

March 12, 2015

Personally, I am not much on an IDE person. I love a good plain text editor and a command  line tool. However, Spyder is not that bad. You can download it from the Spyder bit bucket repository. Give it a try. It works right out of the box. There are 3 main sub windows, a color coded text editor, a variable table and a console output. The first time you open it you should see something like this:

spyder_ide_first_run

Let's run a sample program, something like this:

#trial run Spyder IDE

x = input("Enter a number: ")
y = raw_input("Enter another number: ")

try:
    z = x*y
except:
    print "ERROR! Incompatible types"

print z

print x*int(y)

Now when we hit the run button magic is going to happen. We are going to have to enter user input in the console area. After that magic! our variable, values and data type, show up on the variable panel. This saves a ton of time and effort when it comes to development and debugging. Here is how this all looks:

spyder_first_impressions

Personally, I love this little app. It is great! Now is it enough to make me transitions from my old ways? Maybe. I am not fully convinced. I am going to need to play around with some more. I can see great potentials in this app. New IDEs are coming out everyday now, this is one of the best. It is the only one I would consider giving a fair chance.

Programming Languages, Python

A Lesson about History, Objects, Classes, Time and Python

December 3, 2014

Object Oriented Programming (OOP) became very popular in the last couple of decades. I do find that a lot of people can tell me what an Object is, but few know what is the difference between a class and Object. In fact, many use them interchangeably. So let us clear the air a bit. Here is a short nice story about the evolution of programming. Sort of.

In the dawn of programming we had variables. For a time it was good. Char, Int, Sting, Float all run along nicely. For us programmers that was not enough. We like to make life more complex than that. So we start writing code. A lot of code. Code that uses a lot of variables. As programmers, we love looking for patterns. Slowly we found one. We are writing the same code, over and over. Now, we the coders are a lazy bunch. We like to be challenged, not to write the same lines of code again and agin. So, we came up with the notion of functions. Function are in fact awesome!. for a long time, one could do anything with a few variables and functions. Not to long after, we found ourself copying entire library of functions and files were getting really big. then we came up with the idea of modules, or libraries if you will. How awesome is it to import a whole battery of functions at your finger tips? Most programmers thought this was the best thing since slice bread. Not the we were around back then. After a while, we thought, you know what, how about we put the data (variables) and the methods (functions) together (encapsulation) and use it as one thing, lets call it an object. Yay! Objects.

This of course is a very short description of what actually happy. Hopefully you go the point. So what are objects? They are instantiation (from the word instants) of Classes with particular attributes and behaviors. Attributes refer to the object variables, behaviors to it’s functions. In most cases, but not all, the behaviors involve the attributes. Classes are the code, the recipe for an Object. 1 Class can produces as many Objects as you computer memory can hold. Having the attributes and behaviors together gives a sense of encapsulation. In OOP, the Object attributes are accessed using getters and setters (Access Modifiers). Getters retrieve a copy of the attribute. Setter overwrite the attributes. Setters and Getters are behaviors that help keep the information help by the Object correct. That means that if there is and attribute of a class that has to be a number between 0 and 10. The setter will not allow any other value to be stored. OOP gives us a sense of abstraction since we normally can’t see the code, but we don’t need to. There are a couple of more terms you should hear for now, inheritance and polymorphism. Inheritance means a class can be extended by another class to enhance functionality. Polymorphism means “of many forms”. This applies to OOP since we can have man ors of a single class.

Wow that was a lot to take in all at once. It is time for an example. What better language to use then our favorite, Python. Yay.

We are going to work on a time module that could be helpful for future programs. we are going to start from our basic class, an instant. For our purposes, an instant of time is date and time up to minute accuracy. That means that we are going to write a class, in Python, for an instant. We will have a date (year, month, day) and hour (hour, minute) as our class attributes. To set this up will have to use some special syntax. It will look like this:


class Instant:

	def __init__(self,year,month,day,hour,minute):
		self.year = year
		self.month = month
		self.day = day
		self.hour = hour
		self.minute = minute

Ok. We start with the keyword class, followed by the class name. then we define a function named __init__. This is a special function called a constructor. This function has to be in every class in order to create an object. It is only called once to set the Object up. As the function arguments we pass in self and the reminder of the variables we want to pass in to set the Object up. Some leagues allow multiple constructors. Python does not. We will pass self from this point to every function in the class, so that they can have access to the Objects attributes. Note that self.year is not the same as year. Self.year is the class variable, while year is a function variable.

To use this class, or to get an object, we can use the following code:


def main():

	i = Instant(2014,12,3,2,11)
	print i

if __name__== "__main__":
	main()

If you run it, you will get something that looks like this:

wpid-instantclasspython-2014-12-3-01-39.png

That number is a memory location where our object is stored. If we crated more Object they all will have different hex memory addresses. This is useful to know but not ver particle. If we want to debug or do anything we will need to print out the individual attributes within the class. Thankfully, there is a special function we can write called a to-string. It is noted in Python __str__ and will be called when asked to print the object. For our example the code will look like this:


def __str__(self):
	return  "Year: " + str(self.year) + " " + \
	   	   "Month: " + str(self.month) + " " + \
		   "Day: " + str(self.day) + " " + \
		   "Hour: " + str(self.hour) + " " + \
		   "Minute: " + str(self.minute)

And the output (for the same main() function from before):

wpid-instantstrpython-2014-12-3-01-39.png

You could be fancy and change the function to return something else like:

wpid-instantstrpython2-2014-12-3-01-39.png

if you really want you could play around with colors and strings in Python all that you want, but that is not the point. Now we are going to add some getters and setters. Getters are easy, the just retrieve information, so a getter for year looks like this:


def getYear(self):
	return self.year

We define getters to avoid direct access to class attributes. However, if we go back to out main we can issue a command ‘print i.year’ without an error. In order to avoid that we will add 2 underscores to the attribute name in the constructor. That will make the attribute private so only within the class using self.year we can access thee variable. So our new constructor will look like this:


def __init__(self,year,month,day,hour,minute):
	self.__year = year
	self.__month = month
	self.__day = day
	self.__hour = hour
	self.__minute = minute

And our getter will look like this:


def getYear(self):
	return self.__year

And if we wanted to print just the year, we would use it like this:


i.getYear()

Ideally, we would have a getter for every attribute in the class. That is not a must, just a friendly suggestion. Now we can move to the setters. In a setter, we will put a new value in the Object attribute. We could start with a simple method like this:


def setYear(self,year):
	self.__year = year 

This would work. However, normally it is a good idea to check what the user is putting as a year. In Python, variables do not have a declared type. That means that a user can end up passing in something like a String, Boolean or another Object for all we now. In addition, even if the user entered a number, what if it is a negative number? for our purposes, we are going to say that a year must be between 1900 and 2100. So our new setter will look like this:


def setYear(self,year):
	if not ((type(year) != type(2000)) or (year < 1900) or (year > 2100)):
		self.__year = year 

If you were following along you would notice a problem. When we first set self.year we never checked that the value of year upholds the setter standards. In order to correct this we would need to modify our constructor to do the same check. This does get tricky, but it is necessary to maintain the integrity f the Object data. We will modify our constructor set year line to look now like this:


if not ((type(year) != type(2000)) or (year < 1900) or (year > 2100)): self.__year = year
else: raise Exception('Year is not in correct format or out of range')

This means that for each variable we will need to similar work an add a getter and setter. Assuming we got all this done we could move forward. There are 3 more function we will want to added to our instant class:

  1. beforeMe
  2. afterMe
  3. addToMe

The first 2 functions are booleans that take another instant and compare the 2 to see if the other instant is before the current one. Similar idea with afterMe. The method add to me, will take a quantity and add it to instant. Lets take a look at the functions beforeMe and afterMe:

def beforeMe(self,other):
	if self.__year > other.getYear():
		return False
	elif self.__year == other.getYear():
		if self.__month > other.getMonth():
			return False
		elif self.__month == other.getMonth():
			if self.__day > other.getDay():
				return False
			elif self.__day == other.getDay():
				if self.__hour > other.getHour():
					return False
				elif self.__hour == other.getHour():
					if self.__minute > other.getMinute():
						return False
	return True

def afterMe(self,other):
	return not self.beforeMe(other)

I did get a little laze. I could have re-wrttien afterMe as a reverse to beforeMe, this seemed smoother to me. This function really should be straight forward. Lets move on to the next one. In the next one, we can add X minutes to an instant. That is cool and useful because it does require a little math. Let us first take a look at how this is done:


def add(self,min):
	if type(min) != type(1): raise Exception("Invalid minutes to add")
		self.__minute += min
		if self.__minute > 60:
			self.__hour += self.__minute / 60
			self.__minute = self.__minute % 60
			if self.__hour > 24:
				self.__day += self.__hour / 24
				self.__hour = self.__hour % 24
				if self.__day > 30:
					self.__month += self.__day / 30
					self.__day = self.__day % 30
					if self.__month > 12:
						self.__year += self.__month / 12
						self.__month = self.__month % 12

Do note that at this point I am making a lot of assumptions. I did not account for leap years and odd months. This function should be re-wrriten better, but for our sake right now it serves it’s purpose. So after all this is said and done, we should end up with a very interesting class that represents and instant, or a moment if you will in time. That class could be used to create many Objects. Even objects that interact with each other since we can compare 2 instants using the beofreMe and afterMe functions. Maybe next time we can extend this class to be used for a TimePeriod and maybe even a meeting in a schedule book.

Here is a link to the complete instant class in Python in case you want to play around with it.

Programming Languages, Python

20 Good Functions to Know in Python

March 24, 2014

To wrap up our last 2 discussions about functions, namely how to use functions in Python and the temperature convertor, let us take a look at some functions that you may find useful in the future. We are going to start off easy and stack up. As before, we are going to be using Python 2.7. Before we get started let me remind every one, yes there are other ways, perhaps even better ways to code these functions. This is How I did it. It does not mean this is how you should do it. In fact, I would lover it if you left your version in the comments bellow! If you think it is too long for the comment section, send me an email and I will make it into a post. Lastly, these function are meant as an exercise, please be patient even if some of them do not make sense.

For each function (There are 22) we are going to look at the following:

  1. Brief description of the function
  2. Input types
  3. Excepted output
  4. Notes (if any)
  5. Example execution
  6. Code
  7. Example Output for code
  8. Final Notes (if any)

This is going to be long, so hang on. Let’s get started!

1. Even numbers:
Return a boolean value representing whether x is even or not.

input: number (integer)
output: True or False (boolean)

Example execution:
is_even(5) => False
is_even(42) => True

Code:

def is_even(n):
	return (n % 2) == 0

Code Output:

wpid-python_is_even_output-2014-01-6-19-281.png

Final notes: Be aware the although the function is excepting an integer, a float might be passed in as the value of n. The result would always be False unless n is an even integer.

2. Remove evens:
Given a list of integers, remove all even values from the list and return an odd list of numbers.

input: a list of integers (list)
output: a list of odd numbers (list)

Example execution:
remove_evens([1,2,3,4,5,6]) => [1,3,5]

Code:

* Edited thanks to Eric Wilson (See comments)

def remove_evens(alist):
	res = []
	for n in alist:
		if not is_even(n): res.append(n)
	return res

Code Output:

wpid-python_remove_evens-2014-01-6-19-281.png

Final Note: You will notice that in this function we are calling another function within the module.

3. Min Value:
Accepts a list of numbers, and returns a copy of the smallest value in it.

input: a list if integers (list)
output: the minimum number (integer)

Example execution:
minval([104,22,31,4,54,61]) => 4

Code:

def minval(alist):
	return min(alist)

Code Output:

wpid-python_minval-2014-01-6-19-281.png

Final notes: Although in the input section we assumed that the function should only accept a list of integers. The function, as coded above, will also work for a mixed valued list. Python will use simple comparison to make sense and determine what the min value is.

Final notes 2: I am aware that that this function is useless since all it does is called the built in function min().

4. Index of Min Value:
Accepts a list of numbers, and returns the index (zero based) where the smallest value can be found. It must return the earliest index, in case of ties.

input: a list if integers (list)
output: the minimum number’s index in the list (integer)

Example execution:
min_index([104,22,31,4,54,61]) => 3

Code:

def min_index(alist):
	return alist.index(minval(alist))

Code Output:

wpid-python_minval_index_2-2014-01-6-19-281.png

Final Note: You will notice that in this function we are calling another function within the module.

5. Remove Value:
Finds the first instance of a value, and removes it from the list. Return a boolean, True when the value was removed, and False when the value wasn't found.

input: an integer value and a list of integer numbers
output: True or False (boolean)

Example execution:
remove_a_value(22,[104,22,31,4,54,61]) => True
remove_a_value(105,[104,22,31,4,54,61]) => False

Code:

def remove_a_value(val, alist):
	try:
		alist.remove(val)
		return True
	except:
		return False

Code Output:

wpid-python_remove_value-2014-01-6-19-281.png

6. Simple Sort:
Given a list of numbers, you will return a copy of the list with all elements in sorted (ascending) order. You must implement the following algorithm:

make a copy of the list make an empty result list
LOOP as long as the copylist isn't empty:
find the minimum value in the copylist, remove it
add that minval to the end of the resultlist return the result list

input: a list if integers (list)
output: a list of sorted integers (list)

Example execution:
simple_sort([104, 22, 31, 4, 54, 61]) => [4, 22, 31, 54, 61, 104]

Code:

def simple_sort(alist):
	copy = alist[:]
	res = []
	while len(copy) > 0:
		x = minval(copy)
		res.append(x)
		copy.remove(x)
	return res

Code Output:

wpid-demo_function_6-2014-01-6-19-281.png

Final Note: Although the function is assuming to work on integers, it may also work on other data types. Try it out.

7. Destructive Sort:
This behaves the same as Simple Sort, except that it must modify the original.

input: a list if integers (list)
output: NONE.

NOTE: In this function we will be modifying the original list, meaning it is a destructive function to the arguments passed in. Also note that the function does not have any return statements or a return value.

Example execution:
list_a = [33,94,1,92,54,12]
distraction_sort(list_a)

Code:

#The code uses simple_sot(alist) to sort the list and then rewrites the original list values
def distraction_sort(xs):
	temp = simple_sort(xs)
	for i in range(len(temp)):
		xs[i] = temp[i]

Code Output:

wpid-demo_function_7-2014-01-6-19-281.png

8. Middle Sort:
Without modifying the original list, find out what the middle element would be when all the elements are sorted. If the length is even (and thus no true 'middle' element), then out of the two elements closest to the middle, prefer the left one.

input: a list if integers (list)
output: the middle number if the list was sorted (an integer)

Example execution:
median_value([5,34,29,91,102,44,1,4]) => 29

Code:

def median_value(xs):
	temp = simple_sort(xs)
	mid = int(len(xs)/2)
	if is_even(len(xs)): mid -= 1
	return temp[mid]

Code Output:

wpid-demo_function_8-2014-01-6-19-281.png

9. Kth Sorted:
Like Middle Sort, only we seek the Kth spot, not the middle spot. K is a zero-based integer index into the sorted version of list.

input: a list if integers (list)
output: the kth number if the list was sorted (an integer)

Example execution:
kth(2,[71,43,67,10,4,3,87,103s]) => 10

Code:

def kth(k,xs):
	temp = simple_sort(xs)
	return temp[k]

Code Output:

wpid-demo_function_9-2014-01-6-19-28.png

10. Zip List:
Given two lists of values, create and return a list of tuples that "zip" up the values from the two lists together - first items in a pair, second items in a pair, and so on.

input: 2 lists of integers (lists)
output: a single list of tuples with values from both lists (a list)

Example execution:
zip([1, 2, 3, 4], ['a', 'b', 'c', 'd']) => [(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')]

Code:

def zip(xs,ys):
	res = []
	i = 0
	while i < len(xs) and i < len(ys):
		res.append((xs[i],ys[i]))
		i += 1
	return res

Code Output:

wpid-demo_function_10_b-2014-01-6-19-28.png

11. Multiply Lists:
Given two lists of numbers, create a new list of numbers by multiplying the same-indexed values. As soon as one list runs out of values, the resulting list ends.

input: 2 lists of integers (lists)
output: a single list with the values from both list multiplied, while both lists have values (a list)

Example execution:
pairwise_multiply([2, 3, 10, 11], [35, 10, 29, 3]) => [70, 30, 290, 33]

Code:

def pairwise_multiply(xs,ys):
	res = []
	i = 0
	while i < len(xs) and i < len(ys):
		res.append(xs[i]*ys[i])
		i += 1
	return res

Code Output:

wpid-demo_cundtion_11-2014-01-6-19-28.png

12. Dot Product:
Given two lists of numbers, return a single number found by multiplying each same-indexed pair of numbers, and adding the results together.

input: 2 lists of integers (lists)
output: the sum of each pair of elements multiplied (an integer)

Example execution:
dot_product([1, 2, 3], [3, 2, 1]) => 10

Code:

def dot_product(alist, blist):
	return sum(pairwise_multiply(alist,blist))

Code Output:

wpid-demo_function_12-2014-01-6-19-28.png

13. N Copies:
Return a list with n copies of val.

input: a number and a value (integer,any)
output: a list with n copies of a given value (a list)

Example execution:
n_copy(5,3) => [5, 5, 5]

Code:

def n_copy(val,n):
	res = []
	for i in range(n):
		res.append(val)
	return res

Code Output:

wpid-demo_function_13-2014-01-6-19-28.png

14. Interleave:
Given two lists of values, create (and return) the interleaved version by making a new list with the first value of list_a, then the first value of list_b, then the second value of list_a, second value of list_b, and so on. Once a list is done the rest of the values from the other list are added to the resulting list.

input: 2 lists of integers (lists)
output: A single list with the values from both lists interleaved (a list)

NOTE: Etra valuees for either list are added to the end of the result list

Example execution:
interleave(['a', 'b', 'c'], [1, 2, 3]) => ['a', 1, 'b', 2, 'c', 3]

Code:

def interleave(alist,blist):
	res = []
	i = 0
	while i<len(alist) and i<len(blist):
		res.append(alist[i])
		res.append(blist[i])
		i += 1
	for j in range(i,len(alist)):
		res.append(alist[j])
	for j in range(i,len(blist)):
		res.append(blist[j])
	return res

Code Output:

wpid-demo_function_14-2014-01-6-19-28.png

15. Riffle Shuffle:
Imagine we were shuffling cards with the standard "riffle" shuffle (just interleaving two halves of the deck together). For many card games, we need to perform multiple shuffling in order to get enough apparent randomness in the order of cards. List represents the 'deck' to be shuffled, and n represents how many "riffle" shuffling need to be performed.

input: a single list (a list)
output: a shuffled list (a list)

NOTE: Like function 7, distraction_sort, this function modifies the original values given

Example execution:
list_a = ['a','b','c','d','e','f','g']
riffle_shuffle(list_a)

Code:

def riffle_shuffle(alist):
	temp = alist
	mid = int(len(alist)/2)
	temp = interleave(temp[0:mid],temp[mid:len(alist)])
	for i in range(len(alist)):
		alist[i] = temp[i]

Code Output:

wpid-demo_function_15-2014-01-6-19-28.png

16. Pairs:
Create and return a list of all possible pairs from values in list_a and values in list_b. The order of elements is important! all of the pairs of list_a first element must appear before all pairs involving list_a second element; similarly, when pairing with a specific element from list_a, these pairs must include list_b elements in the same order as original.

input: 2 lists of integers (lists)
output: a single list with pairs of values from both lists (a list)

Example execution:
all_pairs([1, 2, 3], ['a', 'b', 'c']) => [(1, 'a'), (1, 'b'), (1, 'c'), (2, 'a'), (2, 'b'), (2, 'c'), (3, 'a'), (3, 'b'), (3, 'c')]

Code:

def all_pairs(alist,blist):
	res = []
	for x in alist:
		for y in blist:
			res.append((x,y))
	return res

Code Output:

wpid-demo_function_16-2014-01-6-19-28.png

17. Build Deck:
Create a fresh, organized deck. You must generate the result from these two strings: one representing all the pips (card values) "23456789TJQKA", and another representing the suits, "CDHS".

input: 2 strings, “23456789TJQKA” and “CDHS” (strings)
output: a list of cards (a list)

NOTE: each card will be repressed by a value and suit. For example: 4C is 4 of clubs, TS is ten of spades and QH is queen of heats.

Example execution:
new_deck()

Code:

def new_deck():
	val = "23456789TJQKA"
	shapes = "CDHS"
	return (all_pairs(val,shapes))

Code Output:

wpid-demo_function_17_b-2014-01-6-19-28.png

18. Reduce Dimension:
Given a list of more than one dimension, create and return a new list by collapsing that outermost dimension.

input: a multidimensional list (a list)
output: the list without the outmost dimension (a list)

NOTE: This function only reduces the original list dimension by 1, not a full flatten.

Example execution:
flatten([[[1, 2, 3], 4], [5]]) => [[1, 2, 3], 4, 5]

Code:

def flatten(alist):
	res = []
	for i in alist:
		for j in i:
			res.append(j)
	return res

Code Output:

wpid-demo_function_18-2014-01-6-19-28.png

19. Map:
Given a python function and a sequence of values, create and return a new list by calling the function on each value in the sequence and placing the results into the returned list.

input: a function name and a sequence of values (string,tuple/list)
output: the results from the mapped function onto the sequence of values (a list)

Example execution:
map(ord,”Hello World”) => [72, 101, 108, 108, 111, 32, 87, 111, 114, 108, 100]

Code:

def map(f,alist):
	res = []
	for x in alist:
		res.append(eval(str(f(x))))
	return res

Code Output:

wpid-demo_function_19-2014-01-6-19-28.png

20. Zip With:
Combine elements of list_a and list_b together while using the operator, generating a new list.

input: a function and 2 lists (string,lists)
output: a list with the values from applying the function on the lists values (a list)

Example execution:
zip_with(add, [1, 2, 3], [4, 5, 6]) => [5, 7, 9]

Code:

def zip_with(f,alist,blist):
	res = []
	i = 0
	while i<len(alist) and i<len(blist):
		res.append(eval(str(f(alist[i],blist[i]))))
		i += 1
	return res

Code Output:

wpid-demo_function_20-2014-01-6-19-28.png

Cool Stuff, Programming Languages, Python

The Game of Battleships in Python

February 17, 2014

A couple of weeks ago we talked about the game of Tic Tac Toe. I thought it would be fit to talk about another game, Battleships. Both games are excellent beginner games for programming and Python makes it very easy to implement them without a lot of hassle. You will notice that this article is a little different from my regular work. Normally I have the output of the function embedded. Since this is a game, like Tic Tac Toe, it is hard to capture the game in a single screen shoot. I will have some screen shoots toward the end of the article when I talk about printing out the board. Before we begin let us lay some ground rules for the game:

  1. This is a modified version of the game Battleships.
  2. The coordinates used for this game are all numeric.
  3. The game will be played against a random computer player.
  4. The computer will place random ships that are hidden from the user.
  5. The turns alternate between player regards of hit or miss.

Let us begin by laying out our main logic for the game. Here is some pseudo code that will help keep us inline:

  1. Setup the boards for both computer and user
  2. Place ships
  3. Alternate turns asking for coordinates and check win condition.

That is just a very rough outline. Of course the game itself is a lot more complex than this. So let’s get started. First we need to think about data representation. We need to have 2 boards that are 10 X 10. That is easy, it is just a list of lists with 10 lists. We will say that a cell is empty if it contains a “-1” value. So we just need to initiate this list of lists like this:


#setup blank 10x10 board
	board = []
	for i in range(10):
		board_row = []
		for j in range(10):
			board_row.append(-1)
		board.append(board_row)

	#setup user and computer boards
	user_board = copy.deepcopy(board)
	comp_board = copy.deepcopy(board)

Notice that we had to use the Python copy module to make sure we are not pointing to the same memory. There are other ways to this, like having the code duplicated. This is a topic for another day, in the mean time, here is a nice article about Deep and Shallow copies in Python. You may want to note that some of this principles are actually global and have parallels in other languages. So we have the boards, but what about this ships? Well, that is easy, what if we have a dictionaries attached to our list of list as the final element. The dictionary will look like this:


ships = {"Aircraft Carrier":5,
		     "Battleship":4,
 		     "Submarine":3,
		     "Destroyer":3,
		     "Patrol Boat":2}

Ok. So we have the easy part taken away. Now we have to look at how to place the ships. That is a little more complex. Lets first think about our logic. We need to figure out first that the coordinates entered by the user are valid. Then we have to ask orientation of the ship. After that we need to make sure that a ship can be actually placed. For example, what if we are trying to place a Patrol Boat at row: 10 col: 8, vertically? We cannot place the ship there. Horizontally we can, but that is another entry. So we will need to validate the request. If all is good, we will use the first letter of the ship name as a place holder on the board. Seeing the code might hep a little, so here it is:


def user_place_ships(board,ships):

	for ship in ships.keys():

		#get coordinates from user and vlidate the postion
		valid = False
		while(not valid):

			print_board("u",board)
			print "Placing a/an " + ship
			x,y = get_coor()
			ori = v_or_h()
			valid = validate(board,ships[ship],x,y,ori)
			if not valid:
				print "Cannot place a ship there.\nPlease take a look at the board and try again."
				raw_input("Hit ENTER to continue")

		#place the ship
		board = place_ship(board,ships[ship],ship[0],ori,x,y)
		print_board("u",board)

	raw_input("Done placing user ships. Hit ENTER to continue")
	return board

You will notice that we call 5 functions we did not talk about yet. So let us talk about them. We will talk about the printing function in a little bit. We will take a look first at the get_coor() function. Before you get cold feet I do warn you that this function is lengthy. Keep in mind that the function accounts for user errors and will make sure that the only input it will accept and return is 2 values that are between 1 - 10. Nothing more, nothing less.


def get_coor():

	while (True):
		user_input = raw_input("Please enter coordinates (row,col) ? ")
		try:
			#see that user entered 2 values seprated by comma
			coor = user_input.split(",")
			if len(coor) != 2:
				raise Exception("Invalid entry, too few/many coordinates.");

			#check that 2 values are integers
			coor[0] = int(coor[0])-1
			coor[1] = int(coor[1])-1

			#check that values of integers are between 1 and 10 for both coordinates
			if coor[0] > 9 or coor[0] < 0 or coor[1] > 9 or coor[1] < 0:
				raise Exception("Invalid entry. Please use values between 1 to 10 only.")

			#if everything is ok, return coordinates
			return coor

		except ValueError:
			print "Invalid entry. Please enter only numeric values for coordinates"
		except Exception as e:
			print e

Ok. So that was a mouth full. How about the next one, the v_or_h()? That is a little more straight forward, it only return V or H. This should be simple:


def v_or_h():

	#get ship orientation from user
	while(True):
		user_input = raw_input("vertical or horizontal (v,h) ? ")
		if user_input == "v" or user_input == "h":
			return user_input
		else:
			print "Invalid input. Please only enter v or h"

Recall that we are doing all this to place the user ships. So at this point we have a valid coordinate from the user and an orientation. Now we go back to our placement issue. We need to make sue that the type of ship can be placed where the user wants it. To do this we just need to check that it can physically be placed within the board limits and that the cells are empty (-1).


def validate(board,ship,x,y,ori):

	#validate the ship can be placed at given coordinates
	if ori == "v" and x+ship > 10:
		return False
	elif ori == "h" and y+ship > 10:
		return False
	else:
		if ori == "v":
			for i in range(ship):
				if board[x+i][y] != -1:
					return False
		elif ori == "h":
			for i in range(ship):
				if board[x][y+i] != -1:
					return False

You should note that this function returns a boolean value of True or False. This is so we can use it when we write the computer version of place ships, we can use the validate() function without writing a new one. Now all we have look at, excluding the print function is the actual placement of the ships. Recall that all we need to do at this point is put the intial character of the ships name.


def place_ship(board,ship,s,ori,x,y):

	#place ship based on orientation
	if ori == "v":
		for i in range(ship):
			board[x+i][y] = s
	elif ori == "h":
		for i in range(ship):
			board[x][y+i] = s

	return board

You will notice that this looks very much like a function that we can reuse, just like the validate() function. Perhaps now is a good time to look at the ship placement for the computer agent.


def computer_place_ships(board,ships):

	for ship in ships.keys():

		#genreate random coordinates and vlidate the postion
		valid = False
		while(not valid):

			x = random.randint(1,10)-1
			y = random.randint(1,10)-1
			o = random.randint(0,1)
			if o == 0:
				ori = "v"
			else:
				ori = "h"
			valid = validate(board,ships[ship],x,y,ori)

		#place the ship
		print "Computer placing a/an " + ship
		board = place_ship(board,ships[ship],ship[0],ori,x,y)

	return board

The main difference between the user and computer ship placement is that the computer uses randomization to place the ships while the user enters the information. At this point we have our setup complete and can play the game. The 2 functions that will handle the game are user_move and computer_move. Let us take a look at both:


def user_move(board):

	#get coordinates from the user and try to make move
	#if move is a hit, check ship sunk and win condition
	while(True):
		x,y = get_coor()
		res = make_move(board,x,y)
		if res == "hit":
			print "Hit at " + str(x+1) + "," + str(y+1)
			check_sink(board,x,y)
			board[x][y] = '$'
			if check_win(board):
				return "WIN"
		elif res == "miss":
			print "Sorry, " + str(x+1) + "," + str(y+1) + " is a miss."
			board[x][y] = "*"
		elif res == "try again":
			print "Sorry, that coordinate was already hit. Please try again"

		if res != "try again":
			return board

def computer_move(board):

	#generate user coordinates from the user and try to make move
	#if move is a hit, check ship sunk and win condition
	while(True):
		x = random.randint(1,10)-1
		y = random.randint(1,10)-1
		res = make_move(board,x,y)
		if res == "hit":
			print "Hit at " + str(x+1) + "," + str(y+1)
			check_sink(board,x,y)
			board[x][y] = '$'
			if check_win(board):
				return "WIN"
		elif res == "miss":
			print "Sorry, " + str(x+1) + "," + str(y+1) + " is a miss."
			board[x][y] = "*"

		if res != "try again":

			return board

Fist thing you will notice is the infomus function get_coor(). We have used it before and it will work for us again. Now we have 3 more function we need to look at in order to understand how this works. We will start with make_move() this function looks like this:


def make_move(board,x,y):

	#make a move on the board and return the result, hit, miss or try again for repeat hit
	if board[x][y] == -1:
		return "miss"
	elif board[x][y] == '*' or board[x][y] == '$':
		return "try again"
	else:
		return "hit"

All this function really does is looks at the board in a particular cell and returns a value at that cell. Based of the result the board will be updated if needed. Now we need to check if a ship got sunk. This is easy. If you recall we have a dictionary containing the ships and the amount of hits they can take. This is the last element in the board data representation. So this is not as bad as you might think. We just need to figure out what ship got hit and if it has more damage points.


def check_sink(board,x,y):

	#figure out what ship was hit
	if board[x][y] == "A":
		ship = "Aircraft Carrier"
	elif board[x][y] == "B":
		ship = "Battleship"
	elif board[x][y] == "S":
		ship = "Submarine"
	elif board[x][y] == "D":
		ship = "Destroyer"
	elif board[x][y] == "P":
		ship = "Patrol Boat"

	#mark cell as hit and check if sunk
	board[-1][ship] -= 1
	if board[-1][ship] == 0:
		print ship + " Sunk"

Cool. Now for the last function, check_win(). Now this can be done better, but I was tired at this point so I went for simple. If you think about it, a board is in a win condition if all the ships are gone. That means that in our representation, all the cells must conation a -1 for empty, a $ for a hit or a * for a miss. Any other character is a ship and there fore not a win. So the function can look like this:


def check_win(board):

	#simple for loop to check all cells in 2d board
	#if any cell contains a char that is not a hit or a miss return false
	for i in range(10):
		for j in range(10):
			if board[i][j] != -1 and board[i][j] != '*' and board[i][j] != '$':
				return False
	return True

So now we have our puzzle almost complete. The last pice we need is a good print function. This function is built upon the Tic Tac Toe function, but is a little more complex. Recall that there are 2 printing functions that we need. When the users sees the computer board, the ships should be hidden. However, when the user is presented with their own board, they should see all the ships. In wither case, the hits and misses should be displayed and the ‘-1’ should not be printed. This took me a while to get working properly. Mostly because I wanted it to look good, for me. Here is the printing function:


def print_board(s,board):

	# WARNING: This function was crafted with a lot of attention. Please be aware that any
	#          modifications to this function will result in a poor output of the board
	#          layout. You have been warn.

	#find out if you are printing the computer or user board
	player = "Computer"
	if s == "u":
		player = "User"

	print "The " + player + "'s board look like this: \n"

	#print the horizontal numbers
	print " ",
	for i in range(10):
		print "  " + str(i+1) + "  ",
	print "\n"

	for i in range(10):

		#print the vertical line number
		if i != 9:
			print str(i+1) + "  ",
		else:
			print str(i+1) + " ",

		#print the board values, and cell dividers
		for j in range(10):
			if board[i][j] == -1:
				print ' ',
			elif s == "u":
				print board[i][j],
			elif s == "c":
				if board[i][j] == "*" or board[i][j] == "$":
					print board[i][j],
				else:
					print " ",

			if j != 9:
				print " | ",
		print

		#print a horizontal line
		if i != 9:
			print "   ----------------------------------------------------------"
		else:
			print

So to sum it all up, here is a link to the complete code Battleships in Python Command Line. Here are some screen shoots I took from the game play:

wpid-python_battleships_placing_ships-2014-02-16-19-17.png

wpid-python_battleships_user_ships-2014-02-16-19-17.png
wpid-python_battleships_computer_placing_ships-2014-02-16-19-17.png

wpid-python_battleships_user_move-2014-02-16-19-17.png

wpid-python_battleships_computer_hitship-2014-02-16-19-17.png

wpid-python_battleships_user_move-2014-02-16-19-17.png
wpid-python_battleships_userwon-2014-02-16-19-17.png

Have Fun!

Python

The game of Tic Tac Toe in Python

January 29, 2014

The last time I wrote an article we talked about the properties of a list. Many of you have pointed out some improvements that we incorporated in a later post addressing the issues some have you had with the code. This time, I would like to take on a larger program that utilizes some techniques we talked about as well as some new ones. In this article we are going to program the game of Tic Tac Toe in Python. I trust most people, if not everyone, have heard of the game and played it as children. Like always, I will be using Python 2.7.3 to test run my code. Some modification might be required for newer versions of Python.

The game of Tic Tac Toe is a perfect assignment for any programmers. You will be surprised how many times we go back to this game from a different angle. From this game you can learn turn based gaming programming, artificial intelligence , user interaction and many others topics. For now we are going to limit the game to non computer players. Here is a brief description of our assignment:

You are to implement the two player game of Tic Tac Toe. The program should display the board and prompt each user a move. The program should validate each move and handle any incorrect input. The entire user interaction should be command line based. Upon winning or a draw of the game, an appropriate message should be displayed acknowledging such condition.

The specs for this game are intentionally vague for the purpose of this article. We are going to tackle this problem one thing at a time. Let’s start by breaking down the program into some smaller blocks. Here is some rough pseudocode for us to work with:

  1. Setup Game
  2. Ask for user input on each turn
  3. Check if win condition met or no more moves
  4. Display the appropriate message and quit the game.

Let’s get started. First, let us think about how we can represent the board. A Tic Tac Toe board is a 3 X 3 grid. We could use a 2 dimensional list, or we can use one list with 9 elements that correspond to our 3 X 3 grid. So we are going to end up representing the board in Python in 1 list. Further more, we will set a value, -1, for an unclaimed cell, 0, for ‘O’ and 1 for ‘X’. This means that at any point in the game the list, board, will contain all the information we need for the game. Let’s take a look at the initial setup for the game:


board = []
	for i in range(9):
		board.append(-1)

That is it. This alone gives us a board with 9 cells all empty. Now let us tackle the display part. Although it is nice that we can represent the whole game in 1 variable, it is not very practical for the user. We want to display the game just like we would if we were to be playing on a pice of paper. To do so we will need to to print out a 3 X 3 grid from a 1 dimensional list. Let us first look at a quick example.

Let us consider that we have the list of numbers 1 to 9, and we want to print them out like this:

tic_tac_toe_map

To do so we can use this code:


a_list = [1,2,3,4,5,6,7,8,9]

for i in range(3):
	for j in range(3):
		print a_list[i*3+j],
	print 

The output would be:

wpid-3x3matrixpython-2013-11-12-15-13.png

How did this happen? Well, let us think about the values i and j take within the inner loop:

i_and_j_map_python

Now we want the values to be 0 to 8 to correspond to the list indexes of a_list. After playing with the numbers a little bit I found out that the formula i*3 + j gives me the values 0 to 8. Like this:

formulated_i_and_j_map_python

Cool. Let us now use this information to print out our Tic Tac Toe board. We already had the code to generate our board. Now lets see if we can print it. Consider the following function:


def print_board(board):

	print "The board look like this: \n"

	for i in range(3):
		print " ",
		for j in range(3):
			if board[i*3+j] == 1:
				print 'X',
			elif board[i*3+j] == 0:
				print 'O',
			else:
				print ' ',

			if j != 2:
				print " | ",
		print

		if i != 2:
			print "-----------------"
		else:
			print 

What will the function output? This:

wpid-tic_tact_tow_empty_board_python-2013-11-12-15-13.png
It is empty because all I did is generated an empty board using the code above. What would have happened if we sent it another list? Let’s investigate the code. It has a double loop like before, only instead of just printing out a_list[i*3+j] we take a look at it and print the appropriate value. If the list at that index contains the value 1 we print ‘X’ if it is 0, we print ‘O’. Otherwise it is just an empty space. The rest of the print statements are used to generate the lines. Note that we also use the comma (‘,’) to suppress the carriage return. You can read this article to find out more about Strings in Python.

So we completed our first part. We have a method to display the board and we have a setup for the game. Now let us see what is asking a user for input. Remember that we need to validate that the move is legal, i.e. the spot is not taken, and that the move is numeric between 1-9. Recall we are using a list to store the board. That means that will little effort we can ask the user which cell he would like to place a move in. Before we take user input, we will need to let the user know about this mapping of his/her moves. To do so let’s print out some instructions regarding the cell enumeration. Since we already have a function to print the board, with a little modification to it we can add an elif and write a small function to print the instructions, like this:


def print_instruction():
	print "Please use the following cell numbers to make your move"
	print_board([2,3,4,5,6,7,8,9,10])

If called, this function will print out:

wpid-tic_tac_toe_board_map_python_w_instructions-2013-11-12-15-13.png

Now, consider the following function that takes a player’s move and validates that it is a number between 1 to 9 and of numeric type:


def get_input(turn):

	valid = False
	while not valid:
		try:
			user = raw_input("Where would you like to place " + turn + " (1-9)? ")
			user = int(user)
			if user >= 1 and user <= 9:
				return user-1
			else:
				print "That is not a valid move! Please try again.\n"
				print_instruction()
		except Exception as e:
			print user + " is not a valid move! Please try again.\n"
			print_instruction()

This function will keep asking the user for a spot to place their move. If it is not numeric, we use a try-except block to catch the exception. If not between 1-9, we use a simple if-statement. Either way we notify the user of their error with an appropriate message. This is pretty straight forward. You always want to make sure the any user input is indeed valid. You should except the user to err. In this case, we accept user input as a sting and we try to convert it to an integer. Any input that is not between the numbers 1 to 9 will be considered invalid input and an appropriate message will be displayed.

wpid-python_err_input_ttt-2013-11-12-15-13.png

Great. We are actually almost done. The next part is how to check if a someone the Tic Tac Toe game. The function is not pretty, in fact it is hard coded for all possible board situations. It simply works. If there is a winner, the winners symbol will be returned, namely ‘X’ or ‘O’. If there is no winner, the function will return -1. Let us take a look:


def check_win(board):
	win_cond = ((1,2,3),(4,5,6),(7,8,9),(1,4,7),(2,5,8),(3,6,9),(1,5,9),(3,5,7))
	for each in win_cond:
		try:
			if board[each[0]-1] == board[each[1]-1] and board[each[1]-1] == board[each[2]-1]:
				return board[each[0]-1]
		except:
			pass
	return -1

So far we have talked about all the parts we need to make the game. Now it is time to put it all together. We will use all the functions we talked about and add some more logic. For example, we will have the game login in a while-loop. The loop will keep going while we do not have a winner. We will also keep track of the number of moves made. If less than 4 move were made, there is no sense to check for a win condition. If there were 9 moves made and no winner, the game is a tie. Other than that, the code should be fairly simple by now.


def main():

	# setup game
	# alternate turns
	# check if win or end
	# quit and show the board

	print_instruction()

	board = []
	for i in range(9):
		board.append(-1)

	win = False
	move = 0
	while not win:

		# print board
		print_board(board)
		print “Turn number “ + str(move+1)
		if move % 2 == 0:
			turn = ‘X’
		else:
			turn = ‘O’

		# get user input
		user = get_input(turn)
		while board[user] != -1:
			print “Invalid move! Cell already taken. Please try again.\n”
			user = get_input(turn)
		board[user] = 1 if turn == ‘X’ else 0

		# advance move and check for end game
		move += 1
		if move > 4:
			winner = check_win(board)
			if winner != -1:
				out = “The winner is “
				out += “X” if winner == 1 else “O”
				out += “ ☺”
				quit_game(board,out)
			elif move == 9:
				quit_game(board,”No winner :(”)

Since the output of this will be a little long, I will let you have fun and download it yourself, download Command Line Tic Tac Toe for Python If I have time in the future, I will try to record my screen and add the output.

Have fun playing!

Cool Stuff, Programming Languages, Python

Sending Email From Python Using Command Line

January 10, 2014

Since many of my commenters ask for something a little more advance in Python, I wrote up this script I wrote. Notice that this script will allow you to use almost anything you would come to except from an email client. Sending Email From Python is simpler than you think. That includes cc and bcc fields, html mode and attachment files. You will have to use your own email configuration, I left the settings from gmail, but any email account could be used. Just fill in your user name and password. You can include this module and use the compose_email() function to send emails directly from you Python program. As a word of advice, try to not send too many emails all at once (like 400 emails). Gmail will not send the emails and your email address will be marked as spam. Use with caution.

NOTE: The only output of the program is a single print statement (assuming it all went well), that will indicate an email has been sent.


#account setup
username = '***';
password = '***';
server = 'smtp.gmail.com:587';

#imports
from time import sleep;
import smtplib;
from email.mime.application import MIMEApplication
from email.mime.text import MIMEText;
from email.mime.multipart import MIMEMultipart;

# create msg - MIME* object
# takes addresses to, from cc and a subject
# returns the MIME* object
def create_msg(to_address,
               from_address='',
               cc_address='',
               bcc_address='',
               subject=''):

    msg = MIMEMultipart();
    msg['Subject'] = subject;
    msg['To'] = to_address;
    msg['Cc'] = cc_address;
    msg['From'] = from_address;
    return msg;

# send an email
# takes an smtp address, user name, password and MIME* object
# if mode = 0 sends to and cc
# if mode = 1 sends to bcc
def send_email(smtp_address, usr, password, msg, mode):
    server = smtplib.SMTP(smtp_address);
    server.ehlo();
    server.starttls();
    server.ehlo();
    server.login(username,password);
    if (mode == 0 and msg['To'] != ''):
        server.sendmail(msg['From'],(msg['To']+msg['Cc']).split(","), msg.as_string());
    elif (mode == 1 and msg['Bcc'] != ''):
        server.sendmail(msg['From'],msg['Bcc'].split(","),msg.as_string());
    elif (mode != 0 and mode != 1):
        print 'error in send mail bcc'; print 'email cancled'; exit();
    server.quit();

# compose email
# takes all the details for an email and sends it
# address format: list, [0] - to
#                       [1] - cc
#                       [2] - bcc
# subject format: string
# body format: list of pairs [0] - text
#                            [1] - type:
#                                        0 - plain
#                                        1 - html
# files is list of strings
def compose_email(addresses, subject, body, files):

    # addresses
    to_address = addresses[0];
    cc_address = addresses[1];
    bcc_address = addresses[2];

    # create a message
    msg = create_msg(to_address, cc_address=cc_address , subject=subject);

    # add text
    for text in body:
        attach_text(msg, text[0], text[1]);

    # add files
    if (files != ''):
        file_list = files.split(',');
        for afile in file_list:
            attach_file(msg, afile);

    # send message
    send_email(server, username, password, msg, 0);

    # check for bcc
    if (bcc_address != ''):
        msg['Bcc'] = bcc_address;
        send_email(server, username, password, msg, 1);

    print 'email sent'

# attach text
# attaches a plain text or html text to a message
def attach_text(msg, atext, mode):
    part = MIMEText(atext, get_mode(mode));
    msg.attach(part);

# util function to get mode type
def get_mode(mode):
    if (mode == 0):
        mode = 'plain';
    elif (mode == 1):
        mode = 'html';
    else:
        print 'error in text kind'; print 'email cancled'; exit();
    return mode;

# attach file
# takes the message and a file name and attaches the file to the message
def attach_file(msg, afile):
    part = MIMEApplication(open(afile, "rb").read());
    part.add_header('Content-Disposition', 'attachment', filename=afile);
    msg.attach(part);

#to be tested...
compose_email(['cpt@thelivingpearl.com','',''],
              'test v.5.0',
              [['some text goes here...\n',0]],
              '');

#compose_email can take the following arguments:
#	1. to recipients (separated by a comma)
#	2. cc recipients (separated by a comma)
#	3. bcc recipients (separated by a comma)
#	4. subject
#	5. a list with message and mode (plain txt or html)
#	6. files to be attached

Programming Languages, Python

Temperature Conversion Application In Python

January 2, 2014

Last time we talked about using functions in Python, this time let us take it a step farther and create a module. Functions are great and you are going to use them everywhere, but what happens when you need to use a function in more than one place? What happens when a function needs to be utilized in different files within one application? In Python, we create modules, which are just your regular .py files. We can use functions (and objects) from other files by using an import statement. Every language has some form of an import statement. In C we use an include statement. The idea is that when you need, you can include code from another code file. For this post, lets assume a scenario. Imagine that you are an entry level programmer at a software company. You are assign to a team that is working on some large scale scientific application in Python. As the newbie on the team, you are giving the task to write functions that will be used for temperature conversation in multiple parts of the program. You are given the following function pseudocode and are requested to write the code for them:

  1. c2f(t) will take a float temperature in Celsius and return a float temperature in Fahrenheit
  2. c2k(t) will take a float temperature in Celsius and return a float temperature Kelvin
  3. f2c(t) will take a float temperature in Fahrenheit and return a float temperature Celsius
  4. f2k(t) will take a float temperature in Fahrenheit and return a float temperature Kelvin
  5. k2c(t) will take a float temperature in Kelvin and return a float temperature in Celsius
  6. k2f(t) will take a float temperature in Kelvin and return a float temperature in Fahrenheit

So these functions are pretty easy to write, they are all 1 line of code. Using some basic formulas from Wikipedia Conversion of units of temperature the code in Python for temperature conversion might look like this:


def c2f(t):
	return (t*9/5.0)+32

def c2k(t):
	return t+273.15

def f2c(t):
	return (t-32)*5.0/9

def f2k(t):
	return (t+459.67)*5.0/9

def k2c(t):
	return t-273.15

def k2f(t):
	return (t*9/5.0)-459.67

That was simple. Notice that we have included in every calculation an implicate conversion to float, so even if t is not a float, the result will return as a float. That might be useful if at some other part of the application some numeric calculation is required. Especially if the calculation requires higher level of accuracy. Within a couple of minutes you hand your boss (email him/her) a file named temperature.py and you think you are done. In most cases you might be done, but have you tested your code? Rushing code is never a good idea. Take the time to fully test you code and make sure it works the way you think it does. This example might be straight forward, but other examples might be more complicated. It is a good habit to always self test you code. Here is one way you can test the code:


def main():

	menu = “\nTemperature Convertor\n\n"+\
	 	"1. Celsius to Fahrenheit\n"+\
		"2. Celsius to Kelvin\n"+\
		"3. Fahrenheit to Celsius\n"+\
		"4. Fahrenheit to Kelvin\n"+\
		"5. Kelvin to Celsius\n"+\
    		"6. Kelvin to Fahrenheit\n"+\
		"7. Quit"

	user_input = 0
	while user_input != 7:
		print menu
		user_input = raw_input("Please enter a valid selection: ")

		try:
			user_input = int(user_input)
		except:
			print user_input + " is not a valid selection, please try again\n"

		if user_input == 1:
			t = get_user_input()
			print str(t) + " degree Celsius is " + str((c2f(t))) + " degree Fahrenheit"
		elif user_input == 2:
			t = get_user_input()
			print str(t) + " degree Celsius is " + str((c2k(t))) + " degree Kelvin"
		elif user_input == 3:
			t = get_user_input()
			print str(t) + " degree Fahrenheit is " + str((f2c(t))) + " degree Celsius"
		elif user_input == 4:
			t = get_user_input()
			print str(t) + " degree Fahrenheit is " + str((f2K(t))) + " degree Kelvin"
		elif user_input == 5:
			t = get_user_input()
			print str(t) + " degree Kelvin is " + str((k2c(t))) + " degree Celsius"
		elif user_input == 6:
			t = get_user_input()
			print str(t) + " degree Kelvin is " + str((k2f(t))) + " degree Fahrenheit"
		elif user_input == 7:
			quit()
		else:
			print str(user_input) + " is not a valid selection, please try again\n"

if __name__ == "__main__":
	main()

The output of the code might look like this: wpid-python_tempeature_converstion-2014-01-2-19-29.png Now this main() function is in a different file called converter.py. The file content has now functions that can convert anything. However, in the very top of the file there is one magical statement:


from temperature import *

There are different ways to include code from another .py file, but for now, we can use this one. All it is is a small indication for Python to know that if they need to open a temperature.py file as well as the converter.py file. The only requirement is that both files are in the same working directory, that is that they are in the same folder. When you examine the code you may notice that some code was added to account for invalid entries, such as if a user enters a character instead of a number. There is also a hidden function called get_user_input() that looks like this:


def get_user_input():

	user_input = 0
	while type(user_input) != type(1.0):
		user_input = raw_input("Enter degrees to convert: ")
		try:
			user_input = float(user_input)
		except:
			print user_input + " is not a valid entry"
	return user_input

This function makes sure the user enters a numeric value to convert. At this point you have all the tools necessary to tell you boss that you have tested you code and it works properly. You might also want to keep this as part of the code in case you want to use it in the future. I have uploaded the code in case you want to test it out for yourself, Temperature Conversation Application in Python.

Programming Languages, Python

Introduction to Functions in Python

December 23, 2013

As you begin to learn programming, sooner or later you will run into the issue of rewriting code. That is one of the many reasons we teach and learn to write functions. Functions are much like the mathematical equivalent, they are machines, with some input and output. Somewhere in school you might have learned that a function f takes a value x and has an output y. Much like that we have functions in programming that can take variables or arguments and have an output of some result. The inner working of a function in math is more technical, like f(x) = 2x + 3. In a similar matter, functions in programming execute statements.

500px-Function_machine2.svg

There are 4 different types of functions that we can consider:

  1. No variables and no return
  2. Variable and no return
  3. No variable and a return
  4. Variable and return

Let us look at some examples. First let us look at the syntax requirements by Python to write Functions in Python. Like before, we will consider Python 2.7 to be our standard. The same ideas will apply to other versions and even other languages. You can take a look at the Python 2.7 function definition for more reading, but the basic definition of a function in python will look something like this:

def <function_name>(<Variables>) :
    <body>

Where <function_name> is a must, <Variables> are optional and <body> can be as minimal as pass. So what is our most minimal function? The useless function:


def useless():
	pass

As you may guess, using this function is pointless, but that brings up another question, how do we use functions? That is simple, we call functions, by name. So if we were to make use of this function we can call it by the statement:


useless()

Now this is pointless, since nothing will let you know that the function even executed correctly. Computers today are so fast, in a blink of an eye your program will run through the code, and without any output, there is nothing to make the user verify that something actually happened. This brings us to the first kind of functions, functions without variables and without a return. You may think this is pointless by itself, but let’s say you need to do a menu to allow the user to select from 3 options, something that looks like this:

wpid-pyhton_basic_menu-2013-12-23-10-21.png

The beginning code can look something like this:


print "1. do something"
print "2. do something else"
print "3. quit"

user_input = raw_input("Please make a valid selection: ")

if user_input == "1":
	print "doing something..."

elif user_input == "2":
	print "doing something else"

elif user_input == "3":
	quit()

else:
	print "not a valid selection" 

Now this is nice, but what if we have to repeat this, won’t it be easier in a loop. Sure it will! To change it we will need to add a while statement and set user_input to some initial value. Our code will look now like this:


user_input = 1

while user_input != 3:

	print "1. do something"
	print "2. do something else"
	print "3. quit"

	user_input = raw_input("Please make a valid selection: ")

	if user_input == "1":
		print "doing something..."

	elif user_input == "2":
		print "doing something else"

	elif user_input == "3":
		quit()

	else:
		print "not a valid selection" 

Now that is a little more intuitive. Now our program will execute code, but keep going back to the main loop. It would be helpful if instead of the print statements, we change it to have a single function call, to out function that takes no variables and has no return. That is right, a useless function is perfect for printing out information.


def print_menu():

	print "1. do something"
	print "2. do something else"
	print "3. quit"

You may some other usage for a function of such. I normally use them for printing out user information, such as help instructions and menus. You might find other use to them, such as updating global variables, but that is beyond the scope of this post. Let us look at our code now inside the while loop:


print_menu()

user_input = raw_input("Please make a valid selection: ")

if user_input == "1":
	print "doing something..."

elif user_input == "2":
	print "doing something else"

elif user_input == "3":
	quit()

else:
	print "not a valid selection" 

The next type of functions we want to examine are those who take a variable and return now value. Let’s say we want a function that will print out “ho” a given number of times. a function like that might look like this:


def ho(n):
	for i in range(n):
		print "ho",
	print

Notice that the function is named ho, and that it has a variable name in the parentheses. The variable will receive a value when we call the function. If no value is given, we will get a trace back that looks like this:

wpid-python_functions_errors_1-2013-12-23-10-21.png

We want to try to avoid that. To do so, we can assign a defualt value, just in case we “forget” to give it a value. We do this by adding an equal sign and a value. Like this:


def ho(n=3):
	for i in range(n):
		print "ho",
	print

So now we can call this function by ethier just the name, or by giving it a number of time to print “ho”. Like this:


ho()

ho(5)

The output will be:

wpid-python_ho_function_output-2013-12-23-10-21.png

These types of functions are useful for all sort of things. usually, things that can be computed or executed without any of the results needing to come back to our main program. Let us look at another example that has more than 1 variable, the power function. Let us say that the default value of the power is always 2, but the base has to be given by the user. The result does not need to be stored, it can be printed out to the screen. This function might look like this:


def power(base,exp=2):
	print base ** exp

Notice that we have multiple variables, 1 with no default value and 1 with a default value. In theory, a function can has as many variables as you need. It may also have a dynamic number of variables. As a rule of thumb, if you have over 4-5 variables as arguments for your function, you may want to rethink your logic a little. Let us look at the output of our power function and some function calls:


power(2)

power(5)

power(5,3)

wpid-python_power_function_output-2013-12-23-10-21.png

You may think that this is it, but it is not. Until now we say functions that do something and output to the screen something. What if we actually need the value? What if we are within a bigger program and we need the value of the power function? We will get back to that in a minute. Let us first talk about function with no variables. Such function are getters of values, something like a random number generator. Lets say we need a function that will return 2 every time it is called. I know, it seems pointless, but it is for demonstration only. That function will look like this:

def rtn_2():
    return 2

Notice that we use a special reserved keyword return. The values, or variables, after that word is what the function returns. In this case we return the value 2. Now, our function call is the same, but since we return a value, that normally means we want to store it somewhere. So out function call changes from just the name of a function to a variable assignment statements that looks like this:

value = rtn_2()

The value returned from the function rtn_2 will be stored in the variable value for future usage. We can also have multiple return statements and multiple values returns, but that is another topic by itself. Now we are ready to talk about the most common and most useful function type, functions with variables and return types. Let us say that we want to modify our power function from before to return the value, we can modify it to look something like this:


def power2(base,exp=2):
	return base ** exp

That was easy. Now the value computed will be returned tot he calling function for future reference. Cool. Lets see if we can combine all 4 functions to be call from our menu program (Again, just inside the while loop):


print_menu()

user_input = raw_input("Please make a valid selection: ")
print

if user_input == "1":
	n = input("enter a number: ")
	ho(n)

elif user_input == "2":
	base = input("enter a number: ")
	print str(base) + " to the power of 2 is ",
	power(base)
	base = input("enter a number: ")
	exp = input("enter a number: ")
	print str(base) + " to the power of " + str(exp) + " is ",
	power(base,exp)

elif user_input == "3":
	value = rtn_2()
	print "The value is " + str(value)

elif user_input == "4":
	base = input("enter a number: ")
	res = power2(base)
	print str(base) + " to the power of 2 is " + str(res)
	base = input("enter a number: ")
	exp = input("enter a number: ")
	res = power2(base,exp)
	print str(base) + " to the power of " + str(exp) +" is " + str(res)

elif user_input == "5":
	quit()

else:
	print "not a valid selection" 

print

The full python function example can be viewed here. Some notes about the program and functions in general:

  • First, you will notice some print statements, those were added for ease of use.
  • Second, the function we discussed here are mostly integer ones. That is not the only case for use of functions, variable can be of any Python data type.
  • Return type of function can be of any type. The ones we showed here are not the only one.
  • There is much more to say about functions, but I might leave that out for next time, this article is getting long enough as is.

So there you have it, a nice beginner introduction into the wonderful world of functions. As I mentioned not 2 lines ago, there are many others function techniques and things you can do with them. I might try to have a following post covering these aspect coming out soon.

Happy Holidays!

Computer Programming I, Programming Languages, Python

Compute the Average, Min, Max and Mode of a List in Python

October 24, 2013

Lists are by far the most common data type you will use in Python. I wanted to take a few minutes to see how easy Python make the use os lists. I also want you to notice how much ground we can cover by just thinking about these properties of a list. In this article we will talk about lists, functions, searching, return values, data tpes, diconaaries, try-catch try-except blocks and more interesting Python techniques.

So we will be finding the average, min, max and mode of a list. I won’t go into different theories on how to efficiently find these, but rather straight forward approach. Let us start by an assumption that all the values in our list are going to be integers and the data is already stored in a variable named list. As before, we will be using Python 2.7, here is a copy of Python2.7 documentation if you need it. Coming from that we can start by saying our main function looks like this:


def main():

	list = [3,4,1,20,102,3,5,67,39,28,10,1,4,34,1,6,107,99]

	avg(list)
	min(list)
	max(list)
	mode(list)

This will simply call 4 different functions that will each find and print what we are looking for. First, lets go over some list basic properites. In all these function we will use for loops to iterate over the elements of the array. Lucky Python has a simple syntax that allows us to have a variable in the for loop that will take the values of the array.

What does this mean? You will recall that arrays have 0 indexing property that allows us to access the elements in the array directly. If we were to have the syntax list[0] is our example, the value will correspond to 3. the syntax list[1] will have the value 4. We can access each element individually and directly. We can use this to change values in the array. If we were to have list[0] = 55 in our code, the value of list[0] will change to be 55. Here is an example code:


list = [3,4,1,20,102,3,5,67,39,28,10,1,4,34,1,6,107,99]

print list

print list[0]
print list[1]

list[0] = 55

print list[0]
print list

This code will output:

wpid-list_index_exampe_python-2013-10-24-15-30.png

Notice that the values of the list have changed after the assignment. Now let us recall the for loop syntax and properties in Python. The syntax is for element in sequence. That means that we need to provide a name of a variable, in this case element and a sequence such as a String, List, Tuple, etc. So if we wanted to print the numbers 1 to 10 in Python, we will need a list sequence with the numbers in a list and then we can just print element. Like this:


for element in [1,2,3,4,5,6,7,8,9,10]:
		print element

And the output:

wpid-1_to_10_python_for_loop-2013-10-24-15-30.png

Cool. However, what if we need the numbers 1 to 1,000? Well, you can either write them all in a list, or you can use the Python range function. This function has 3 variations. You can eithier call it with 1 integer, and the function will return the numbers from 0 to the number you requested in increments of 1. You can provide the function with a start number and end number (2 integers), and you will get back the numbers from the start to end in increments of 1. Finally you can give the range function 3 integers which will server as start, stop and increment. Here is an example to demonstrate:


# range with 1 argument, return a list with the numbers 1 to 10 in increments of 5
print range(10)

# range with 2 arguments, return a list with the numbers 5 to 10 in increments of 1
print range(5,10)

# range with 3 arguments, return a list with the numbers 5 to 50 in increments of 5
print range(5,50,5)

Output:

wpid-range_function_python-2013-10-24-15-30.png

Remember that the range function in not including the last number. So range(10) gave us the numbers 0 to 9 without 10. Lets combine the range function with indexing of the list to access and print the elements in a list.


list = [3,4,1,20,102,3,5]

for i in range(len(list)):
	print list[i]

This code will output:

wpid-python_list_example-2013-10-24-15-30.png

This is one way to do it. Note that we are using the Python len function to get the length of the list. Len is a built in function in Python and will return the length of any sequence.

Another way to accomplish the same task is to use Python and remove the indexing. Like this:


for element in list:
	print element

Both code output will be the same. There are some cases (as we are going to see) were we will need to use the first one and some where we are going to use the second. It all depends on your program. Now lets take a look and see how can we calculate the Average, Min, Max and Mode of a list. First what is the Average of a list? It is just the sum of the elements divided by the number of elements. Well, we can get the number of elements using the len function, and we can iterate through the elements and add them all up. Like this:


def avg(list):

	sum = 0
	for elm in list:
		sum += elm

	print “The average element of the list is: “ + str(sum/(len(list)*1.0))

That was very simple. Let me just clarify some things. You will notice that in the calculation we are multiplying everything by 1.0. We do this to make sure the length of a list, an integer is turned into a double. That way the result of the average element will not be rounded. We also need to convert the average from double to a string in order to concatenate it with a String.

Now let us move on to the Min/Max problem. Essentially both of these are two faces of the same coin. Here is our stragedy to solver this:

  1. Assume the fist element is our Minimum/Maximum value.
  2. For the rest of the elements in the array
  3. If you find a result smaller/larger than Minimum/Maximum, they are the new Minimum/Maximum
  4. return Minimum/Maximum

Hopefully that algorithm was easy enough to follow. Let us take a look how this looks like in Python:


def min(list):

	min = list[0]

	for elm in list[1:]:
		if elm < min:  			min = elm 			 	print "The minimum value in the list is: " + str(min) 	 def max(list): 	max = list[0] 	 	for elm in list[1:]: 		if elm > max:
			max = elm

	print "The maximum value in the list is: " + str(max)

And the output: (assume that: list = [3,4,1,20,102,3,5,67,39,28,10,1,4,34,1,6,107,99])

wpid-min_max_output-2013-10-24-15-30.png

Now let us to get to the hard part, computing the mode. This will turn out to be not so hard. What is the mode of a list? It is the number (or numbers) that occur most often. Ok. Now we are going to use 2 powerful tools Python has in it’s dictionaries and try-catch try-except statements. Dictionaries in Python are essentially lists where you can define the key. You can think about them as lists, but instead of an index that starts at 0 and goes up, you can name the key anything you would like. I would love to spend some time on them, but this might have to be another post by itself. Try-Catch Try-Except blocks are another post all by themselves, but think about them as a way to avoid TraceBacks. In other words if Python were to execute a statement that will result in a TraceBack, you can specify what to execute and the program will continue instead of terminate. I would love to talk mode about these 2, but for the time being you will have to read more about them on the Python Documentation or Google it.

So what i our strategy to find the Mode of a list? Well, first we can count the number of occurrences of each element in the list. We can use a dictionary to store the count and use the element themselves as the key. Let us see what that we give us:


list = [3,4,1,20,102,3,5,67,39,10,1,4,34,1,6,107,99]

d = {}
for i in t:
	try:
		d[i] += 1
	except(KeyError):
		d[i] = 1

print d

This will output the following:

wpid-dic_mode_python-2013-10-24-15-30.png

When we print out a dictionary we get all the keys and the values separated by a colon (:). We can also get all the keys in the list by typing d.keys(). That will give us a list of keys. Now the rest of the code involves finding the max of all values in the dictionary and then printing the keys that fit these values. Here is how that part looks:


for key in keys[1:]:
		if d[key] > max:
			max = d[key]

	print "The mode of the list is: ",
	for key in keys:
		if d[key] == max:
			print key,
	print " with the mode of: " + str(max)

wpid-mode_of_list_python-2013-10-24-15-30.png

Here is a link to the full code to Compute a Mode of a list in Python.

That’s it. We figured out everything we set to do in the beginning. But wait, there is more!

BOUNS Time: Find the range of the numbers in the list. That is super easy, especially now. The range of a list of numbers is simply the Maximum of your list minus the Minimum of your list. Since we alredy have function for that, this is super easy. Let’s take a look: (note a slight modification of the min/max functions is required to return values instead of print statements).


print "The range of the list is: " + str(max(list) - min(list))

By now you should have a better understanding of how lists work in Python. You will find out that all the tools we looked at are extremely useful and you will find them in every Python application. I am including here a full copy of the .py file I used to Compute the Mean, Min, Max, Mode and Range of a list in Python. I hope you have had some fun and learned something along the way. Here is the output of the complete program for:


list = [3,4,1,20,102,3,5,67,39,10,1,4,34,1,6,107,99]

wpid-python_list_data-2013-10-24-15-30.png

Any questions?

Problems

Kth Number Generator in Python

July 16, 2013

A while back we looked at how to generate prime numbers in python. I was looking around for some similar problems that uses prime numbers and I came across an interview question. The question goes something lie this:

        Assume you have a function

f(x,y,z) = a^x * b^y * c^z

Where,

a,b,c - constants
x,y,z - larger than zero integers

The problem: find the kth number this function generates.

I do realize that this sounds very abstract. Let me simplify it. Assume a,b,c are 2,3,5 respectfully. If we start plugging in values to x,y,z starting from (0,0,0) we will get the following result:

 2^0 * 3^0 * 5^0 = 1
 2^1 * 3^0 * 5^0 = 2
 2^0 * 3^1 * 5^0 = 3
 2^1 * 3^1 * 5^0 = 6
 2^0 * 3^0 * 5^1 = 5
 2^1 * 3^0 * 5^1 = 10
 2^0 * 3^1 * 5^1 = 15
 2^1 * 3^1 * 5^1 = 30
 2^2 * 3^0 * 5^0 = 4
 ...

You will notice that the numbers generated are not in order. That means that brute force is almost for sure out of the question. Why? Because there is always a slight chance that we did not generate a number. For example, if we considered only the values 0,1 for x,y,z, we will never get the value 4. So what can we do? We need to think. Keep in mind that this is an interview question for programmers and mathematicians. You may see it in the future. When you do see it, you have about 30 minutes to figure it out. When you are in that scenario, do not worry about getting to the perfect solution (unless it is required). The interview is looking for a process, a thinking mind. So think out loud.

Let us look at a brute force approach to this problem:

import sys

def main(argv):

if len(argv) != 4:
sys.exit('Usage: kth_brute.py <a> <b> <c> <k>')

a = int(sys.argv[1])
b = int(sys.argv[2])
c = int(sys.argv[3])
k = int(sys.argv[4])
list = []

for x in range(k):
for y in range(k):
for z in range(k):
list.append((a**x * b**y * c**z))

list.sort()
print '\nThe kth number is: ' + str(list[m-1]) + '\n'

if __name__ == "__main__":
main(sys.argv[1:])

And the output:

wpid-python_kth_brute-2013-07-16-09-02.png

Now that we saw a solution, let us try to do better. After all, this solution will take a while to run for a large k. In addition, it has the chance to miss a number because we are not generating the numbers in order. If you sit for long enough and keep generating numbers on paper you may start to notice something. The numbers the function generate do have some basic factors that are easy to miss. They are products of constant (prime numbers in his case). That means that we can write the numbers we get as factors:

 1
 2
 3
 2*3
 5
 2*5
 3*5
 2*3*5
 2*2
 ...

How about that. What if instead of trying to generate the next number based on the exponent values, we looked at what would be the minimum value? That will save us from sorting in the end and we won’t have to generate a whole bunch of extra numbers. To further use this idea, let us create 3 queues for each of the constant. Every iteration we will add or remove from the queue values based on the current value. here is a general algorithm:

        let q2,q3,q5 be queues
add 1 to q2
set val to 0
for i in k (k being the kth number)
for each q
if q_m is not empty, pop q_m to v_m
else, set v_m to MAX_INT
set val to the min value of v2,v3,v5

if val is from q2
append (2*val) to q2
append (3*val) to q3
elif val is from q3
append (3*val) to q3

append (5*val) to q5 (always)

return val

Seems simple right? Here is the code in Python:

import sys
from collections import deque

def main(argv):

if len(argv) != 5:
sys.exit('Usage: kth.py <a> <b> <c> <k> <echo>')

# get bases
a = int(sys.argv[1])
b = int(sys.argv[2])
c = int(sys.argv[3])
k = int(sys.argv[4])
echo = int(sys.argv[5])

# setup queue
q1 = deque([])
q2 = deque([])
q3 = deque([])

# init variables
q1.append(1)
val = 0

for i in range(k):

# set v to the next value in queue or to MAX_INT if queue empty
if len(q1) > 0: v1 = q1[0]
else: v1 = 2**32

if len(q2) > 0: v2 = q2[0]
else: v2 = 2**32

if len(q3) > 0: v3 = q3[0]
else: v3 = 2**32

# choose the next minimum value from the 3 queues
val = min(v1,v2,v3)

# add next values to queue
if val == v1:
q1.popleft()
q1.append(a*val)
q2.append(b*val)
elif val == v2:
q2.popleft()
q2.append(b*val)
elif val == v3:
q3.popleft()

# always add the largest
q3.append(c*val)

# if echo is True print every number
if echo: print str(i+1) + ": " + str(val)

print '\nThe kth number is: ' + str(val) + '\n'

if __name__ == "__main__":
main(sys.argv[1:])

And here are some example runs:

wpid-pyhton_kth_number_short-2013-07-16-09-02.png

wpid-pyhton_kth_number_long-2013-07-16-09-02.png

Computer Programming I

A Quick Tutorial for Python Syntax

July 8, 2013

For some, Python is far from their first language. For others, it is where they had started programming. I have received several comments and emails from readers asking how to proceed after understanding the basic concepts in Python. I am hoping to put together a road-map into Python in the next few weeks. Whether you know Python already or want to learn the basic quickly, I hope you will find this post (and the rest) useful. This is a very quick paste, high overview of the language. You are expected to know the basics of programming. Think of this as fast Python syntax review. For this tutorial I will use Python2.7. I highly recommend you consult the Python2.7 documentation while coding or download Python2.7 documentation for offline use. Linux and Mac come with Python already pre-installed. If you require help setting up a Python environment, please consult the Python installation guide. I am going to assume from this point on you already have Python 2.7 at least installed on your system. So let us get to it:

Running Python

There are 3 ways to execute Python code:

  1. The Python Interpreter - an interactive terminal. Statements are evaluated as entered.
  2. Loading a file into the Python Interpreter - save any text file as a .py and execute the statements.
  3. Compiled Python - this is not for speed of execution, rather for sharing a program without sharing code.

For any of the ways, we are going to focus on command line only. There are IDEs for Python, however they are an overkill for this tutorial. To run Python, simply lunch your terminal and type ‘python’. If you want to run a .py file in the terminal type ‘python <file_name.py>’, where file_name should be replaced with your file name.

Comments

In Python, any line starting with the ‘#’ symbol is considered a comment and will be ignored by the Interpreter.

Python Basic Data Types

Similar to other languages, Python supports the idea of basic data types. Unlike most low-level languages, Python does not require the programmer to specify the type. Python interrupter takes case of the data type for you. You may also change to type throughout the program. Thankfully, Python has a built in function type() that can clarify what type of data Python ‘thinks’ the variable is. The basic data types are:

* integer
* long
* float
* complex
* string
* boolean

Here is an output from the Python interpreter:

wpid-pythonbasicdatatypes-2013-01-20-10-09.png

Python Data Structures

Python has 4 data structures that could be at your disposal. These are complex data types that are built from the basic data types we saw before. Each of the data structure types has different usage and attributes. We will discuss:

* Lists
* Tuples
* Dictionaries
* Sets

Starting from the top, Lists are the most common data structure used in Python. With Lists you can group basic datatypes or even data structures together. You can preform numbers standard library function on lists. The 2 (2things) most important things to remember about lists are:

* They are 0 and reversed numeric indexed
* They are mutable

Let us look at some list example operations:

wpid-pythonlists2-2013-01-20-10-09.png

Moving on to tuples, they are very similar to lists but with one thing apart. Tuples are immutable. You may think of tuples as immutable lists, in other words lists that can not be changed once you create them. All the operations we have done on lists apply to Tuples, however, we cannot remove or add elements. This means that when we initiate a Tuple we initiate it with values that may never change. Let us look at some simple Tuple operations:

wpid-pythontupleexamples2-2013-01-20-10-09.png

So now that we have some data types we can move on to the next vital piece of information you need to know, Python Standard Library. Python include a huge array of functions you can use without anything special. The type() and len() functions are some examples of the functions that are included in standard library. This also includes function such as input() and raw_input(), string and number manipulation and many more functions. The best advice if you are looking for a function, check if it is included in stadard library before going to far.

So now what do we do if a function is not in standard library. For example, lets say we need to comute a sin() of an angle, or require the value of pi for calculation, what do we do then? Well, in that case we can import a library. That is right, in addtion to the huge standard library there is also a "secondary library" with everything you might think about, at least in the beginning. Again, you can refer to the Python2.7 documentation for any reference to these libraries. In our case we can import the math library and directly call the math.sin() function or access the value of math.pi. Let us take a look:

 

python_math_import_example3

 

Python is truly a fun language to begin to code with. I did not begin with Python myself, but I highly recommend it to others. Why? well, first I do not think anyone should start in PASCAL any more. Although it was a good educational languages, it is pointless to learn today. Second, Python is natural. It is easy to ease in to programming with python far more than any other language. (This last point might be debatable on the person and the teacher).

Cool Stuff

Simple GUI Text Editor in Python

July 3, 2013

I wrote this simple text editor a while back and came across it while cleaning out my hard drive. I know this is a little more advance than what I normally post, but I wanted to show off what Python can do. Do not worry if you do not understand the code at this point. Just enjoy the fact that in less than 100 lines of code, you can have a working replica of notepad or any other GUI text editor.

 

What can you do in under 100 lines of code?

 


from Tkinter import *
from tkSimpleDialog import askstring
from tkFileDialog   import asksaveasfilename

from tkMessageBox import askokcancel

class Quitter(Frame):
    def __init__(self, parent=None):
        Frame.__init__(self, parent)
        self.pack()
        widget = Button(self, text='Quit', command=self.quit)
        widget.pack(expand=YES, fill=BOTH, side=LEFT)
    def quit(self):
        ans = askokcancel('Verify exit', "Really quit?")
        if ans: Frame.quit(self)

class ScrolledText(Frame):
    def __init__(self, parent=None, text='', file=None):
        Frame.__init__(self, parent)
        self.pack(expand=YES, fill=BOTH)
        self.makewidgets()
        self.settext(text, file)
    def makewidgets(self):
        sbar = Scrollbar(self)
        text = Text(self, relief=SUNKEN)
        sbar.config(command=text.yview)
        text.config(yscrollcommand=sbar.set)
        sbar.pack(side=RIGHT, fill=Y)
        text.pack(side=LEFT, expand=YES, fill=BOTH)
        self.text = text
    def settext(self, text='', file=None):
        if file:
            text = open(file, 'r').read()
        self.text.delete('1.0', END)
        self.text.insert('1.0', text)
        self.text.mark_set(INSERT, '1.0')
        self.text.focus()
    def gettext(self):
        return self.text.get('1.0', END+'-1c')

class SimpleEditor(ScrolledText):
    def __init__(self, parent=None, file=None):
        frm = Frame(parent)
        frm.pack(fill=X)
        Button(frm, text='Save',  command=self.onSave).pack(side=LEFT)
        Button(frm, text='Cut',   command=self.onCut).pack(side=LEFT)
        Button(frm, text='Paste', command=self.onPaste).pack(side=LEFT)
        Button(frm, text='Find',  command=self.onFind).pack(side=LEFT)
        Quitter(frm).pack(side=LEFT)
        ScrolledText.__init__(self, parent, file=file)
        self.text.config(font=('courier', 9, 'normal'))
    def onSave(self):
        filename = asksaveasfilename()
        if filename:
            alltext = self.gettext()
            open(filename, 'w').write(alltext)
    def onCut(self):
        text = self.text.get(SEL_FIRST, SEL_LAST)
        self.text.delete(SEL_FIRST, SEL_LAST)
        self.clipboard_clear()
        self.clipboard_append(text)
    def onPaste(self):
        try:
            text = self.selection_get(selection='CLIPBOARD')
            self.text.insert(INSERT, text)
        except TclError:
            pass
    def onFind(self):
        target = askstring('SimpleEditor', 'Search String?')
        if target:
            where = self.text.search(target, INSERT, END)
            if where:
                print where
                pastit = where + ('+%dc' % len(target))
               #self.text.tag_remove(SEL, '1.0', END)
                self.text.tag_add(SEL, where, pastit)
                self.text.mark_set(INSERT, pastit)
                self.text.see(INSERT)
                self.text.focus()

if __name__ == '__main__':
    try:
        SimpleEditor(file=sys.argv[1]).mainloop()
    except IndexError:
        SimpleEditor().mainloop()

 

Mathematics

The Speed of Multiplication

June 18, 2013

For the most part, all of us take for granted that the cpu can do multiplication in a timely matter. However, there are some systems that do not have multiplication. Furthermore, how is multiplication actually done? Multiplication is nothing more than repeated applications of additions. For example, if we want to compute 5 x 4 we can add 5 4 times or add 4 5 times and keep track of the sum. Let’s take a look how this might look like in Python 2.7.


import sys

def main(argv):

if len(argv) != 2:
sys.exit('Usage: simple_multi.py <a> <b>')

a = int(sys.argv[1])
b = int(sys.argv[2])
sum = 0

for i in range(a):
sum += b

print "The result of " + str(a) + " times " + str(b) + " is: " + str(sum)

if __name__ == "__main__":
main(sys.argv[1:])


And the output:

wpid-python_simple_multipication-2013-06-18-09-38.png

Sweet. Now for most of you this will be it. Trust me, for me the multiplication symbol is it. I never thought I will have to code multiplication. That is until it came up. I have a friend who happens to be a mathematician with a particular fascination to numbers and counting. So he came up to me claiming that he has this fast way to do multiplication that has to do with the ten’s places and basic multiplication. Basic multiplication being the 10 x 10 grid (or 12 x 12) we all had to memorize at some point. So I decided to put him up for the test, I wrote his algorithm in Python as well as the one above and Russian Multiplication. I won’t spend time trying to explain the algorithms. If you want to, you will find the link helpful enough to explain Russian Multiplication. If you want to find out more about my friend’s Ten’s Multipication, send him a message on his blog DeadEndMath. All in python, running on the same computer with the same Linux time command measuring their performance. Before we get to the data, let’s take a look at the code:

Ten’s Multiplication:


import sys

def main(argv):

if len(argv) != 2:
sys.exit('Usage: tens_multi.py <a> <b>')

a = sys.argv[1]
b = sys.argv[2]
sum = 0;
c = len(a) - 1;

for i in a:
d = len(b) - 1;
for j in b:
sum += int(i)*int(j)*(10**c)*(10**d);
d -= 1;
c -= 1;

print "The result of " + a + " times " + b + " is: " + str(sum)

if __name__ == "__main__":
main(sys.argv[1:])


And the output for verification:

wpid-python_tens_multipication-2013-06-18-09-38.png

Well, at least we got the same results. Let us look at the Russian Multiplication in Python:


import sys

def main(argv):

if len(argv) != 2:
sys.exit('Usage: russian_multi.py <a> <b>')

a = int(sys.argv[1])
b = int(sys.argv[2])

sum = 0;

if a == 0 or b == 0:
print 0;
exit();

if b%2 == 1:
sum += a;

while b != 1:
a = a*2;
b = b/2;
if b%2 == 1:
sum += a;

print "The result of " + str(a) + " times " + str(b) + " is: " + str(sum)

if __name__ == "__main__":
main(sys.argv[1:])


The output:

wpid-python_russian_multipication-2013-06-18-09-38.png

Again, good thing we got the same results. Now we know we have all three versions of multiplication and they are all computing products of 2 numbers correctly. Now let us look at their time compression. I have organized the data in a table for convince:

 

Simple Ten's Russian
4 x 5 0.013 0.013 0.014
22 x 54 0.014 0.014 0.014
5142 x 9810 0.014 0.014 0.014
716234 x 847263 0.040 0.014 0.014
817263548 x  827461930 NaN 0.014 0.014


So what can we see? Well first of all the data gathered is from the linux time command. When execute any program in a Linux shell, you can add the command time before the program. This will return you with an output similar to the one below after the command is complete. the times shown are subjective to your computer specifications and current status (i.e. running programs). Here is an example of a Linux time output:

wpid-python_time_example-2013-06-18-09-38.png

So what does all this mean? The real time is total execution time. The user time is how long it took the user to key in the input. The sys time is the time your command was running on the cpu. In the table above, the time was taken from the sys value of execution of each command. You will notice that simple multiplication gets more cpu consuming as the length of the input increases, while the time for Ten’s and Russian Multiplication remained constant. This means that either algorithm could work as a substitute to multiplication if you happen to work in an environment that does not support multiplication natively. As a final note let me add that even a basic multiplication in Python operates within the same time as Ten’s and Russian multiplication, if not a second faster.

Cool Stuff

The Game of Hangman in Python

June 6, 2013

Computer games and python are like a perfect match, it just works. Python is simple enough and powerful to provide game designer and programers a common ground for them to meet up and create awesome stuff. In fact, Python has the PyGame library that is dedicated to creating games. There are many games for Python, buy I thought it would be beneficial to start off with a simple version of Hangman. As before, we will be using Python 2.7 for our examples.

Before we take off with it, let us agree to the rules of the game:

  • The computer will randomly chose a secret word.
  • For each user guess, all occurrences of the same letter in the word will be revealed to the player.
  • The computer will draw the “hangman digram” as outlined bellow for each turn.
  • The user may guess letters at each turn until the word is completed or the “hangman digram” is complete.
  • We can assume that all user input and word letters are lowercase alpha numeric without errors.

The last one is made to simplify the code and the constrains for the problem. In reality we should always account for errors, but I am going to et this one slide. For now. Let us first look and the “hangman digram”. Some people think this is the hardest thing, but it is actually the easiest. Here are the 7 possibilities of the board in ASCII art form.

  +---+
  |   |
      |
      |
      |
      |
=========

  +---+
  |   |
  0   |
  |   |
      |
      |
=========

  +---+
  |   |
  0   |
 /|   |
      |
      |
=========

  +---+
  |   |
  0   |
 /|\  |
      |
      |
=========

  +---+
  |   |
  0   |
 /|\  |
 /    |
      |
=========

  +---+
  |   |
  0   |
 /|\  |
 / \  |
      |
=========

This was generated by this short Python code:


board = [
'  +---+   \n  |   |   \n      |   \n      |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n      |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n  |   |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|   |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|\\  |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|\\  |   \n /    |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|\\  |   \n / \\  |   \n      |   \n========= \n'
]

for i in range(len(borad)):
	print board[i]

This will take care of any of the board configurations. All we need to worry about is how many letters the user has got wrong and we can immediately print out the corresponding “hangman diagram”. Let us make it a little more nice and wrap it in a class. Classes are objects in Python, very similar to Objects in Java. We can encapsulate the board configuration, word to be guessed, missed letters and guessed letters in 1 object. Lets take a look:


board = [
'  +---+   \n  |   |   \n      |   \n      |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n      |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n  |   |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|   |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|\\  |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|\\  |   \n /    |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|\\  |   \n / \\  |   \n      |   \n========= \n'
]

class Hangman:
	def __init__(self,word):
		self.word = word
		self.missed_letters = []
		self.guessed_letters = []

Sweet. Let us move on and create a print function. Print functions are useful for debugging and will take care of our user interface. When we want to print our Hangman object, we really want to know all the information, how the board looks like (or how much of the diagram is complete), the letter we missed, the blank splits for the words and letters we already found. Let us take a look:


def print_game_status(self):
		print board[len(self.missed_letters)]
		print 'Word: ' + self.hide_word()
		print 'Letters Missed: ',
		for letter in self.missed_letters:
			print letter,
		print
		print 'Letters Guessed: ',
		for letter in self.guessed_letters:
			print letter,
		print

And the output for an empty board:

wpid-hangman_empty_board_python-2013-06-6-13-05.png

Upon close inspection, you will notice that there is another method I am calling name hide_word(). By the concatenation with the string before, you can assume the function is defined and returns a string. What we really need, is a function that can take a word and print out only the letters the user has already guessed. Let’s take a look:


def hide_word(self):
		rtn = ''
		for letter in self.word:
			if letter not in self.guessed_letters:
				rtn += '_'
			else:
				rtn += letter
		return rtn

That seems good enough. Before we can move on to the game play and logic, we need a method in the Hangman object to update a current guess. That is straight forward and looks like so:


def guess(self,letter):
		if letter in self.word and letter not in self.guessed_letters:
			self.guessed_letters.append(letter)
		elif letter not in self.word and letter not in self.missed_letters:
			self.missed_letters.append(letter)
		else:
			return False
		return True

So if the letter is in the word we are trying to guess and we haven’t tried to guess it before, we are going to mark it and return 1 for successful update or if the letter is not in our word, but has not been asked again. If either of these conditions is a failure, we have a repeat input we have already accounted for and we will return 0 to notify the game handler of a problem. The last method we are really missing is to check for win condition. Here is how we can check for hangman win condition in our case:


def hangman_won(self):
		if '_' not in self.hide_word():
			return True
		return False

Notice that we are reusing methods we already have, making things simple. Now our Hangman game object is complete. You will think that we are over, but there is one more method we are missing for the game to be complete. We have a method to check if the game has been won, but we do not have a method to check if the game is over. What happens when the “hangman digram” is complete? For this we will add just a one liner method:


def hangman_over(self):
		return self.hangman_won() or len(self.missed_letters) == 7

Sweet. Now all we need is a main driver and some helper function and we are all done. Our main method can look like this:


def main():

	game = Hangman(rand_word())
	while not game.hangman_over():
		game.print_game_status()
		user_input = raw_input('\nEnter a letter: ')
		game.guess(user_input)

	game.print_game_status()
	if game.hangman_won():
		print '\nCongratulations! You are the winner of Hangman!'
	else:
		print '\nSorry, you have lost in the game of Hangman...'
		print 'The word was ' + game.word

	print '\nGoodbye!\n'

You will be now notice that we are almost done, just 1 more function and we are clear, the rand_word() function. Now you can get very fancy with this, read from a file and randomly choose and such. However, I want to keep things simple, so I limited the word bank into a small list from which I randomly choose 1 word. Check it out:


def rand_word():

	bank = ['the','living','pearl','.com','captain','deadbones']
	return bank[random.randint(0,len(bank))]

That’s all folks. That is the simple way you can get a game started in python. Now you might think this is very complex. If you are looking for a more simple approach, there is a whole chapter about hangman in python I recommend you check out. The reason we set it up like this is so we can add some GUI events or make it more complex without a lot of hassle. You can download the Python code for Hangman or code it yourself. I hope this gave you some flavor to how games and python could work together. What game can you come up with?

Here are some output screen shots:

wpid-python_hangman_game_screen_1-2013-06-6-13-05.png

wpid-python_hangman_game_screen_2-2013-06-6-13-05.png

wpid-python_hangman_game_screen_3-2013-06-6-13-05.png
wpid-python_hangman_game_screen_4-2013-06-6-13-05.png

wpid-python_hangman_game_screen_6-2013-06-6-13-05.png

wpid-python_hangman_game_screen_5-2013-06-6-13-05.png

Security

Caesar Ciphers in Python

June 3, 2013

Today I want to talk to you about ciphers, more in particular Caesar Ciphers. Encryption and Decryption of secret messages date back a long time before computers. Countless Nations have utilized ciphers to communicate secrets across distances. For example, lets say I have soldier on the other side of the planet and I am relaying them a message that might put their life at risk. Do we want that message falling into the wrong hands? No. So what can we do? Well, the simple answer is to encrypt the message. Today almost every message is encrypted and packet into protocols several of times. For example, your computer encrypts packets it sends back and forth with your WiFi router all the time. Computers, for better or worse, require us to come up with new encryption methods on a daily basis. However, everyone has to start somewhere. Before you can plunge in and understand things like AES and RSA encryption, we need to start in something basic, like Caesar Ciphers.

wpid-Ciphrdsk-2013-06-3-12-17.gif

Caesar Cipher is pretty simple. It is a substitution cipher that people like to think was user by Julius Caesar. In this cipher we follow a formula to encrypt a message and another to decrypt. Let us take a look at what that means mathematically.

Here is our encryption formula:

wpid-bbb819c72cda43180d98e6ade5cadb04-2013-06-3-12-17.png

And here is decryption:

wpid-d7959a1a4e5af0c29600d66a7fac615b-2013-06-3-12-17.png

And thats it folks. Wait, what does this actually mean? Well, lets first start with out assumptions:

  1. The alphabet we are working with contains 26 letters (English)
  2. n is is a number less than or equal to 25.

These assumptions can be modified for any alphabet language of you choosing. If the alphabet contains m letters, than n has to be less than or equal to m-1. As long as you keep both conditions, you will be fine. Here is a general outline and picture of how the algorithm works. You should be aware that normally n is set to 3, but it will work with any number.

  1. Assign numeric values to each letter in the alphabet.
  2. Encrypt:
    • for each letter in plain_text
      • new letter is letter_numeric_value + n
  3. Decrypt:
    • for each letter in cipher
      • plain_text_letter is letter_numeric_value - n

For it to make some sense, here is a visual picture from Wikipedia:

wpid-320px-Caesar_cipher_left_shift_of_3.svg-2013-06-3-12-17.png

 

So the letter E in our message (plain text) is 5 and n=3, so our encrypted value of E is B. Now that we have some background and a simple example, let us implement it in Python. Like always, we will use Python 2.7. Here is how Caesar Cipher looks like in Python:

First lets look at a simple encryption module:


import sys

def main(argv):
	if (len(sys.argv) != 2):
		sys.exit('Usage: sub.py <k>')
		
	plaintext = list(raw_input('Enter message: '))
	alphabet = list('abcdefghijklmnopqrstuvwxyz')
	k = int(sys.argv[1])
	cipher = ''
		
	for c in plaintext:
		if c in alphabet:
			cipher += alphabet[(alphabet.index(c)+k)%(len(alphabet))]
		
	print 'Your encrypted message is: ' + cipher
	

if __name__ == "__main__":
	main(sys.argv[1:])

In this example we define the alphabet and make use of Python List and Indexing. We ask the user to pass in a key of length k and preform the substation. Here is an example run:

wpid-pythoncaesarciherexample-2013-06-3-12-17.png

Now let us up the stakes to something more complex. After all, this is an encryption that people used to do by hand all the time. Take a look at this program:


import sys 

def encrypt(k):
	plaintext = raw_input('Enter plain text message: ')
	cipher = ''
	
	for each in plaintext:
		c = (ord(each)+k) % 126
		
		if c < 32: 
			c+=31
			
		cipher += chr(c)
		
	print 'Your encrypted message is: ' + cipher

def decrypt(k):
	cipher = raw_input('Enter encrypted message: ')
	plaintext = ''
	
	for each in cipher:
		p = (ord(each)-k) % 126
	
		if p < 32:
			p+=95
						
		plaintext += chr(p)
		
	print 'Your plain text message is: ' + plaintext

def main(argv):
	if (len(sys.argv) != 3):
		sys.exit('Usage: ceaser.py <k> <mode>')
		
	if sys.argv[2] == 'e':
		encrypt(int(sys.argv[1]))
	elif sys.argv[2] == 'd':
		decrypt(int(sys.argv[1]))
	else:
		sys.exit('Error in mode type')


if __name__ == "__main__":
	main(sys.argv[1:])

The first question you might ask is why is the mod 126? Well, this version of Caesar Cipher was adapted to take full use of the ASCII Printable Character map, minus the first 32 characters that are not printable. With this program, we can chose a larger n and create a “harder” to break ciphers. You will also notice that now we can do Encryption and Decryption in the same program. Let us try to decrypt ‘khoor’ and see what we get:

wpid-pythoncaesardecryption-2013-06-3-12-17.png

Sweet. Now let’s try to encrypt something a little longer with a different key.

wpid-pythoncaesarlongencryption-2013-06-3-12-17.png

And Decryption:

wpid-pythoncaesarlongdecryption-2013-06-3-12-17.png

Caesar ciphers are nice to play around with and to learn basic concepts, but is really impractical. The number of combination you can get is really small compared to what the computer can generate. Brute force attacks can always crack the code with very little human intervention. Consider a 26 letter alphabet. There are only 25 options for selecting a unique n. That means that if I can generate all the 25 permutations, 1 of them has to be the correct plain text. Let us look brute force braking using the following script:


import sys 

def decrypt(k,cipher):
	plaintext = ''
	
	for each in cipher:
		p = (ord(each)-k) % 126
	
		if p < 32:
			p+=95
						
		plaintext += chr(p)
		
	print plaintext

def main(argv):
	if (len(sys.argv) != 1):
		sys.exit('Usage: brute_ceaser.py')
		
	cipher = raw_input('Enter message: ')
		
	for i in range(1,95,1):
		decrypt(i,cipher)

if __name__ == "__main__":
	main(sys.argv[1:])

I will spare you the entire 94 lines that got printed out, here are a few. Can you guess what the message originally was?

wpid-pythoncaesarbruteforcea-2013-06-3-12-17.png

Here is another one:

wpid-pythoncaesarbruteforceb-2013-06-3-12-17.png

I will let you come to your own conclusions as to how “hard” it is to brake Caesar Ciphers. Personally, I wouldn’t use them for anything simple. Than again, I do not know how many people would check if you used it. I hoped you gain some understanding to how cipher works, substitution ciphers in particular. Next time I might dig a little farther into security algorithms and play around with another step up in encryption-decryption algorithms.

Happy Hacking
Captain DeadBones

Cool Stuff

Coding With Your Voice Using Python and Emacs

May 5, 2013

Passwords

Authentication of Users and Passwords in Python

January 29, 2013

Before we dive in to the topic, I would like to apologies. Over the past 10 days, I have had multiple matters that require my attention. While I try to allocate some time for everything, this blog has not been on the top of my priorities. This was a mistake, I now realize. I should have anticipated some of the issues and plan ahead accordingly. The opposite is what happened. I cannot say this will not happen again, I can only apologies and try to do better in the future. So let us get started.

The last post I wrote talked about how to password protect your python program. Although this is very neat and sufficient in most cases, what you really need is a method to authenticate users and password. This post will be rather simple and straight to the point. Much of the work it relies on we have done already. Recall at this point we are storing the password as encrypted strings in a file, independent of our python program. Now we just have 2 things we have to do. We will start by recognizing a single user and allow him/her accesses. Then, we will expand the program to allow multiple allowed users accesses. As noted before, we are going to use Python2.7, I strongly encourage referring to the documentation or download the documentation for python2.7 for offline reference.

As we did previously, before we can authenticate any user we have figure out how we want to store the data we are comparing to. You may recall we used a support program to create a file and store the password. Now we will extend the “helper” script to store a user name on a single line, followed by the encrypted password in the next line. This format may be modified at your discretion. For example, you may choose to encrypt both the user name and the password. You may also choose to have all the information as a single line, separated by a vertical line, ‘|’, or a comma, ‘,’. The options are multiple, but the principle is the same. Assuming we follow the first suggested format, here is how the code to store a user name and password will look like:


import sys
import hashlib
import getpass

def main(argv):

	if len(argv) != 1:
		sys.exit('Usage: store_user_pass.py <file_name>')

	print '\nUser & Password Storage Program v.01\n'
	
	if raw_input('The file ' + sys.argv[1] + ' will be erased or overwrite if exsting.\nDo you wish to continue (Y/n): ') not in ('Y','y') :
		sys.exit('\nChanges were not recorded\n')
	
	user_name = raw_input('Please Enter a User Name: ')
	password = hashlib.sha224(getpass.getpass('Please Enter a Password: ')).hexdigest()

	try:
		file_conn = open(sys.argv[1],'w')
		file_conn.write(user_name + '\n')
		file_conn.write(password + '\n')
		file_conn.close()
	except:
		sys.exit('There was a problem writing to the file!')

	print '\nPassword safely stored in ' + sys.argv[1] + '\n'		
			
if __name__ == "__main__":
	main(sys.argv[1:])

Note that the changes from our previous version, store a single encrypted password, have not changed much. The main thing we have done is added a user_name variable that gets written to the file. As before, we warn the user from alteration of a file might already exist. Here is an example output of the program:

wpid-userandpasswordstorage-2013-01-21-16-37.png

Here are the content of the file pass_db.txt:


cptdeadbones
99fb2f48c6af4761f904fc85f95eb56190e5d40b1f44ec3a9c1fa319

Now we are ready to see how the other side of this program might look like. Since we know how to verify the password, adding the user name option is not much change. For our application purpose, we will terminate the program if the user name is not known or x password attempts have been made. Here is how the code for this will look like:


import sys
import hashlib
import getpass

def main(argv):

	if len(argv) != 1:
		sys.exit('Usage: user_pass.py <file_name>')

	print '\nUser & Password Authentication Program v.01\n'

	try:
		file_conn = open(sys.argv[1])
		user_name = file_conn.readline()[:-1]
		password = file_conn.readline()[:-1]
		file_conn.close()
	except:
		sys.exit('There was a problem reading the file!')
		
	pass_try = 0 
	x = 3
	
	if raw_input('Please Enter User Name: ') != user_name:
		sys.exit('Incorrect User Name, terminating... \n')
	
	while pass_try < x:
		user_input = hashlib.sha224(getpass.getpass('Please Enter Password: ')).hexdigest()
		if user_input != password:
			pass_try += 1
			print 'Incorrect Password, ' + str(x-pass_try) + ' more attemts left\n'
		else:
			pass_try = x+1
			
	if pass_try == x and user_input != password:
		sys.exit('Incorrect Password, terminating... \n')

	print 'User is logged in!\n'		
			
if __name__ == "__main__":
	main(sys.argv[1:])

Running the code with the file we generated before, pass_db.txt:

wpid-userpassverify-2013-01-21-16-37.png

Like previous programs, the user is prompt for a password 3 times. At each trial the user is notified the number of password attempts reaming. At this point, if you have been following along, you should be able to pice together how this might be extended to multiple users. For our final version we will have 2 python files, one to generate a password file and the other to log the user in. The modification for the storage code needed at this point are minimal, all we need to change is the mode we write to the file. In previous versions we used ‘w’ for write mode. Now we are going to use ‘a’, which is only going to append the new information to the end of the file. If the file is not yet created, the file will be created.You can look users and password storage program.

Last but not least, here is our final version of the authentication module. First the code:


import sys
import hashlib
import getpass

def process_file(file_name):
	
	user_names = []
	passwords = []
	
	try:
		file_conn = open(file_name)
		data = file_conn.readlines()

		for i in range(len(data)): 
			if i%2 == 0:
				user_names.append(data[i][:-1])
			else:
				passwords.append(data[i][:-1])
			
		file_conn.close()
	except:
		sys.exit('There was a problem reading the file!')
		
	return user_names, passwords

def main(argv):

	if len(argv) != 1:
		sys.exit('Usage: user_pass.py <file_name>')

	print '\nUser & Password Authentication Program v.01\n'

	user_names, passwords = process_file(sys.argv[1])
		
	pass_try = 0 
	x = 3
	
	user = raw_input('Please Enter User Name: ')
	
	if user not in user_names:
		sys.exit('Unkown User Name, terminating... \n')
		
	while pass_try < x:
		user_input = hashlib.sha224(getpass.getpass('Please Enter Password: ')).hexdigest()
		if user_input != passwords[user_names.index(user)]:
			pass_try += 1
			print 'Incorrect Password, ' + str(x-pass_try) + ' more attemts left\n'
		else:
			pass_try = x+1
			
	if pass_try == x:
		sys.exit('Incorrect Password, terminating... \n')

	print 'User is logged in!\n'		
			
if __name__ == "__main__":
	main(sys.argv[1:])


So what is different? Now instead of just reading one user name and password, we read more. The information is stored in 2 (2things) lists that have corresponding indexes. So the user name at index 1 has an encrypted password stored at index 1 of the password list. All other operation are the same as any previous example. I do not think there is a need to include an input, it is the same as before.

For a final remark, I realize that the method I discussed in this and the previous post and this one are not very secure or useful outside of an educational exercise. In ‘real world’ applications the information will be stored in a database. There are some software that has already been pre written for user authentication in python. The bottom line is that user authentication is not enough to protect an application. There are several more methods we may or may not cover in the future. For the near time, we will start to look into security algorithms and application.

Passwords

Password Protecting Your Python Application

January 18, 2013

Couple weeks back we talked about how to generate passwords in python. Now, I would like to explore how to password protect your application. We will be using Python again, only this time I will upgrade to Python2.7 due to popular demand. You can reference to Python2.7 the documentation or download Python2.7 documentation.

There are many situations in which you would like to password protect the application. It could be just a simple application you do not want anyone else to run, or it could be an application that stores sensitive data. The two things you need to keep in mind is that authentication is independent of the application and that we are discussing application authentication. That is, the ideas may apply to web, mobile & other applications, however, we are going to limit this discussion to python application.

Lost You Password?<a href="http://c9d568r8ox3aii95ujuky1vcxo.hop.clickbank.net/" target="_top">Click Here!</a>

Let us start by assuming there is an application we wish to secure. For demonstration purpose, the application will simply print out:

User is logged in!

Otherwise an appropriate error message will be displayed. We can agree that the print statement can be replaced with a function call to start an application. We are going to start with the simplest case. We have a string password that is stored in a variable. We prompt the user for a password. If the user input does not match the stored password, we terminate the application without letting the user log in. Here is what that would look like in code:


import sys

def main():

	print '\nPassword Request Program v.01\n'

	password = 'abcd'
	user_input = raw_input('Please Enter Password: ')

	if user_input != password:
		sys.exit('Incorrect Password, terminating... \n')

	print 'User is logged in!\n'

if __name__ == &quot;__main__&quot;:
	main()

And the output of the program in both cases:

password auth 1_1

password auth 1_2

You can see that the first time the user entered ‘password’ for the password. The program recognizes an incorrect password and is terminated. The second time the user entered the correct password ‘abcd’ and the user was successfully logged in. For a simple application, this might be enough. However, we are going to take this idea much further. To start, let us add the ability for the user to try to enter a password x amount of times before the program is terminated. For now, let us assume x is 3. You might change the value of x to any number you wish. Our modifed program might look like this:


import sys

def main():

	print '\nPassword Request Program v.02\n'

	password = 'abcd'
	pass_try = 0
	x = 3

	while pass_try &lt; x:
		user_input = raw_input('Please Enter Password: ')
		if user_input != password:
			pass_try += 1
			print 'Incorrect Password, ' + str(x-pass_try) + ' more attempts left\n'
		else:
			pass_try = x + 1

	if pass_try == x and user_input != password:
		sys.exit('Incorrect Password, terminating... \n')

	print 'User is logged in!\n'

if __name__ == &quot;__main__&quot;:
	main()

Sample output:

password auth 2_2_2

password auth 2_2_1

If you examine the code you might notice a few different things. We have a while-loop that runs for x amount of times. This might be replaced with a simple for-loop, but keep in mind that there is no guarantee that the user will need any incorrect attempts. In addition, if you do use a for loop, you might need to use a break statement, which is not a good programming habit. You might also notice that that the program notifies the user how many attempts he or she has left. This is not required, but as a user it is nice to know.

As you examine the code, you will soon realize that storing the password in the code as a string is not the best practice. Let us move the password into a file. This way we can separate the password from the program. The path for the file will be given as a command line argument. The file can by anywhere in the file system, including on a USB drive. Without it, the program will not run and terminate immediately. For this example, we will store the password in a plain txt file called pass_file1.txt. Here is the content of the text file:


abcd

Here is our new version, using the file to store the password:


import sys

def main(argv):

	if len(argv) != 1:
		sys.exit('Usage: pass_auth3.py &lt;file_name&gt;')

	print '\nPassword Request Program v.03\n'

	try:
		file_conn = open(sys.argv[1])
		password = file_conn.readline()[:-1]
		file_conn.close()
	except:
		sys.exit('There was a problem reading the file!')

	pass_try = 0
	x = 3

	while pass_try &lt; x:
		user_input = raw_input('Please Enter Password: ')
		if user_input != password:
			pass_try += 1
			print 'Incorrect Password, ' + str(x-pass_try) + ' more attempts left\n'
		else:
			pass_try = 4

	if pass_try == x and user_input != password:
		sys.exit('Incorrect Password, terminating... \n')

	print 'User is logged in!\n'

if __name__ == &quot;__main__&quot;:
	main(sys.argv[1:])

And here is some sample output. Notice that the first try is without giving the program a path to a file.

password auth 3_2_1
password auth 3_2_2
password auth 3_2_3

Take a closer look at the code. You will notice that there is more than one way the program can might terminate. If a file is not provided the program will terminate immediately. If there are any issues reading the file the program will terminate. Finally, if the password is incorrect more than x times the program will terminate. When reading from the file we use the readline() method. This will read an entire line from the file, including the newline character ‘\n’. This is why there is an added [:-1] to trim the string to not include the newline character.

So far we have seen how to ask for a simple password. However, this is far from a real-world application strength. The problem is that the password is stored as a plain text file. This means that if anyone was to open it, they will know your password immediately. As a good programmer, you do not want a client to find out their secure passwords are stored in plain text. Much less a user finding that out. Or worse. To solve this problem we will introduce 2 (2things) new ideas. First a method to avoid seeing the characters as the user types. Second, we will encrypt the password we store in the file using one way encryption.

In order to hide the password while the user is typing, we will use a python standard library named getpass. The library is quite small, but provides exactly what the name suggests and nothing else. Here is a simple example of how the library works:

wpid-getpassexample-2013-01-17-20-47.png

Basically, getpass.getpass() is equivalent to using raw_input(), but hides the typed characters. I think it is rather straight forward why you should use this library when asking a user for a password. Moving on to the second thing, we need a way to encrypt our password. Furthermore, we want our password encrypted using a one way encryption method. This means that once we encrypt the data, there is no simple function to retrieve the data. Python has a multiple ways to achieve this using standard library functions. We will use a built-in library called hashlib that provides many encryption methods. I choose to follow on of the examples and use sha224 with conversion to hex. Here is an example of using sha224:

wpid-shaexample-2013-01-17-20-47.png

You can see that the encrypted string has nothing to do with the string ‘password’. So how are we going to use one way encryption? Simple, we are going to store the original encrypted password in the file. Then when the user enters a password we will encrypt the user input exactly the same way and compare the encrypted string from the file. If we do not use the same encryption algorithm, this method will not work. You may change the encryption algorithm to what every method you like. Since we need to encrypt the passwords, we will need a helper program to store the password before we modify the authentication program. Here is an example program to store the an encrypted password:


import sys
import hashlib
import getpass

def main(argv):

	if len(argv) != 1:
		sys.exit('Usage: store_pass.py &lt;file_name&gt;')

	print '\nPassword Storage Program v.01\n'

	if raw_input('The file ' + sys.argv[1] + ' will be erased or overwrite if existing.\nDo you wish to continue (Y/n): ') != 'Y' :
		sys.exit('\nChanges were not recorded\n')

	password = hashlib.sha224(getpass.getpass('Please Enter a Password: ')).hexdigest()

	try:
		file_conn = open(sys.argv[1],'w')
		file_conn.write(password + '\n')
		file_conn.close()
	except:
		sys.exit('There was a problem writing to the file!')

	print '\nPassword safely stored in ' + sys.argv[1] + '\n'

if __name__ == &quot;__main__&quot;:
	main(sys.argv[1:])

Here is an example output for this program:

wpid-storepass1-2013-01-17-20-47.png

The program is fairly simple. First we verify that the user acknowledges that if the file exists already it will be erased. There are other ways around this, but this is one of the simple solutions. You do not want to assume the user entered the right file name the first time. If you were to use a file name that already exists, the file will be permanently altered. Since we opened the file in write mode, we will erase any information already there. This is why you should double check that the user entered the correct file name. Of course, you do not have to do it and you may erase the associated if statement.

As a last note, we do not store the plain value of the password in a variable. Instead it is transferred directly to the encryption method. This offers some extra security to you program. Finally, we write the information to the file and terminate the program. If we were to look at the content of pass_file2.txt we will see something like this:


a76654d8e3550e9a2d67a0eeb6c67b220e5885eddd3fde135806e601

Now we are ready for our final version of password authentication, using the encrypted password file. Here is the code for it:


import sys
import hashlib
import getpass

def main(argv):

	if len(argv) != 1:
		sys.exit('Usage: pass_auth3.py &lt;file_name&gt;')

	print '\nPassword Request Program v.04\n'

	try:
		file_conn = open(sys.argv[1])
		password = file_conn.readline()[:-1]
		file_conn.close()
	except:
		sys.exit('There was a problem reading the file!')

	pass_try = 0
	x = 3

	while pass_try &lt; x:
		user_input = hashlib.sha224(getpass.getpass('Please Enter Password: ')).hexdigest()
		if user_input != password:
			pass_try += 1
			print 'Incorrect Password, ' + str(x-pass_try) + ' more attempts left\n'
		else:
			pass_try = 4

	if pass_try == x and user_input != password:
		sys.exit('Incorrect Password, terminating... \n')

	print 'User is logged in!\n'

if __name__ == &quot;__main__&quot;:
	main(sys.argv[1:])

Notice that not much has changed. What we have added is applying the same encryption method we did to the file, to the user input. Here is how the program looks like when it runs:

password auth 4_1

password auth 4_2

We have explored adding a password security to your python program. If you really want to use it, you will need to conceal your code. One way to conceal your code is to compile code to a pyc file. This is just one way you might do this. There are other methods you could explore to create executable from p a py file. We will not explore them within this post. For the moment, I will leave you with a pyc file and a file containing an encrypted password. The application will have a unique output. Can you make the application run?

pyc riddle file
passwod file

Mathematics

The Easy Way to Solve Equations in Python

January 15, 2013

Over the past few days I was debating what I should write about next. I really enjoy sharing my thoughts and have been getting great responses from my readers. I thanks you for your comments. At your request I have decided to cover another math topic, solving equations using python. Equation solving is something fundamental in computing, mathematics and other scientific applications. Using computers enables users to solve a wider range of equations than we could by non-computer methods. However, there is a cost at hand, accuracy. Although computers can solve equations using a few methods, we will witness that accuracy will change between methods. In some cases you might not get to a solution at all.

Before we dive into code behind solving equations, let us step back. A good programmer should always consult other resources to see what else has been done already. The Internet (and Google) have given us great tools to research any topic our heart desires. There are many tools available to solve equations and do almost any other mathematical calculations. Matlab and Matamatica are both great mathematical softwares that can do amazing things. However, they are paid distributions. I do not have anything against paid software, but for the sake of educational useage I would like to keep everything in the realm of free (open source preferred). I like to post code that anyone can download, run, modify, distribute or do anything else they would like to do with it. Using paid languages will be counter productive to such goals and limit the readers of this blog. That being said, if there is a request I will put up Matlab code for the algorithms discussed in this post.

On another note, we will be using Python2.6 for all the examples that are to follow. We will not be using NumPy or SciPy. Both are great scientific math tools but an over kill for what we are trying to do. Our mission is simple, solving an equations. More precisely, we want to figure out where a given function intersect the x-axis without using “the big guns”, including Wolfram-Alpha. So let us get to it.

The Bisection Method:

At out first stop, the most fundamental approach to solving equations is the Bisection Method. Here is the theory in a nutshell:

“If f is a continues function on [a,b], where f(a)f(b) < 0, there must be a point r between a and b where f(r) = 0”

So what does this means? It means that if we have a function that cross the axises between point a and b, then the value of the function at f(a), multiplied by the value of the function at b, f(b), must be smaller that 0. Further more between a and b there is a point where the function f is 0. Here is a picture describing such event:

wpid-bisectiongraph-2013-01-15-18-58.png

Here is a general solution in code that does exactly that:


def bisection(a,b,tol):
	c = (a+b)/2.0
	while (b-a)/2.0 > tol:
		if f(c) == 0:
			return c
		elif f(a)*f(c) &lt; 0:
			b = c
		else :
			a = c
		c = (a+b)/2.0
		
	return c

Notice that we have a while loop that runs while we are within tolerance and that we assume function f(x). The latter part can be solved by writing a function f that outputs the desired function. Here is the function we are going to work with:

 x^3 + x - 1

And here is the python equivalent:


def f(x):
	return x**3 + x -1

Once we add the code together we can run it and get a solution within tolerance. What is the tolerance? The Bisection method literally cuts in half the solution at each iteration, assuming the mid point between a and b is the solution. So in theory we can keep asking for a more accurate solution by setting a lower tolerance. The “real” solution to the function according to Wolfram Alpha is 0.6823278... We will use this solution as a guide to compare the accuracy of solutions we compute. Here are a few outputs for our code, for a solution between 0 and 1 using various tolerances:

(The full code for the Bisection Methon in Python)

wpid-bisectionoutput2-2013-01-15-18-58.png

As you can see, the first solution is only accurate to 2 decimal places. If we tried a lower tolerance we would have got maybe one or none of the digits correct. When we increased our tolerance we arrive to a more accurate solution, within tolerance range. Bisection is a good method to use when it applies. The Bisection method will not work on all functions, but is a quick solution to many equations.

Fixed Point Iteration (FPI)

Fixed point iteration is another method of solving equations. The definition of a fixed point r is when g(r)=r. Using this definition, we start with some initial guess, x and plug it into the function. However, unlike bisection, this method does require us to do some math work before code. We have to transform our function to be in the form x=g(x). This is where the heart of FPI is. Based on your setup and initial guess, you may reach a solution really fast, or not at all. Here is how the code for FPI looks like:


def fpi(x, k):
	for i in range(k):
		x = g(x)
	return x

You will note that now we are no longer using a while loop. FPI could be setup in a smilier way to Bisection, but for simplicity is setup in a fixed i-loop. Using the same function as before, let us say we transform the function to be like this:

 x = \sqrt[3]{1-x}

And in python (using python’s math library):


def g(x):
	return math.pow(1-x,1/3.0)

You will notice that python only has a square root function. For any other roots we use python’s power function. Please remember that 1/3 in integer division is 0. Therefore, we have to use 1/3.0 to get the cubic root. Running the program for 10 iterations starting at 0.5 yields the following output:

(The full code for Fixed Point Iteration in Python)

wpid-fpiroot-2013-01-15-18-58.png

This is not very close, we only have 1 digit and we started close to the solution. If we let the program run for 100 iterations we get really close to the solution:

wpid-fpiroot100-2013-01-15-18-58.png

How many iteration do you need? It depends on your function. A variation on this function might solve it in 7 iterations (can you find the function?). Again, in FPI it depends on the setup and the initial guess. As a rule of thumb, it will either conversation very fast, or not at all. But then again, sometimes it just needs one or more steps.

Newton’s Method

Our next stop, and the basis for our next method, is Newton’s method. In this case, like FPI we start with an initial guess and keep redefining x, however, we use this function to find the next x :

 x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)}

Newton’s method adds another math task we will have to do outside of our code, taking the derivative. We will see that the last method will take care of this, but at another cost. Here is how Newton’s method will look like in code:


def newt(x,n):
	for i in range(n):
		x = x - f(x)/f_prime(x)
	return x

This means we will have to define our original function as well as a derivative (prime) function. Not a problem, we can use the same function we have been solving all along. This is what it will look like:

 f(x) = x^3 + x - 1
 f'(x) = 3x^2 + 1

And in Python:


def f(x):
	return x**3 + x - 1

def f_prime(x):
	return 3*x**2 + 1

Before we run our code, we need to take care of one special case. What if the derivative is 0 or end up computing to 0? Than we will have a division by zero error. This can be simply avoided by a couple of if statements. Like so:


def newt(x,n):
	for i in range(n):
		if f_prime(x) == 0:
			return x
		x = x - f(x)/f_prime(x)
	return x

This should take care of any division by zero errors. However, do not take my word for it, try it out for yourself!

And now running the code, using -0.7 as our initial x for 10 iterations will yield:

(The full code for Newton’s Method in Python)

wpid-newtonsmethod-2013-01-15-18-58.png

If you add some debug statements and examine the output you will note that the solutions was found after only 7 iterations. That is really fast and a lot better than 100 iterations of FPI. You might have output like this:

wpid-newt_output-2013-01-15-18-58.png

Secant Method

Although Newton’s method works really well, taking derivatives is not always an option. For that, there is another method, mathematically based on Newton’s method and the definition of derivatives. This time we start off with 2 initial guesses and move forward by using one of the guess and a new point. The new point is calculated from the formula:

 x_{i+2} = x_{i+1} - \frac{f(x_{i+1})(x_{i+1}-x_i)}{f(x_{i+1}) - f(x_i)}

In Python the Secant Method might look like this:


def secant(x0,x1,n):
	for i in range(n):
		x_temp = x1 - (f(x1)*(x1-x0)*1.0)/(f(x1)-f(x0))
		x0 = x1
		x1 = x_temp
	return x1

Note that there is a chance that we will be dividing by 0, again we must add a check to ensure that this does not happen. Also note that we use a temp variable to swap values around. This is so we do not require much memory. A new, modified version of the Secant method might look like this:


def secant_2(x0,x1,n):
	for i in range(n):
		if f(x1)-f(x0) == 0:
			return x1
		x_temp = x1 - (f(x1)*(x1-x0)*1.0)/(f(x1)-f(x0))
		x0 = x1
		x1 = x_temp
	return x1

As before, we are using for loops, which might be swapped to while loops. I recommend you try it your self, but remember, while loops must terminate at some point. Running the Secant code starting with 0 and 1 for 10 iterations, on out “famous” function yields the following output:

(The full code for Secant Method in Python)

wpid-secantoutput-2013-01-15-18-58.png

We have gone over 4 basic methods of solving equations. There are many more approaches to solve equations, this is by no means a complete survey. I trust that if you are in need for more information you can find it using a friendly search engine. Note that there is still much to say about the accuracy of the solutions computed by these methods. Also note that there are some programming “tricks” that can be done to shorten calculation. For more accurate mathematical definitions and information please seek out a mathematician.

This post was made possible by Numerical Analysis by Timothy Sauer