Small Math Puzzles Make My Day

I was recently hanging out with some friends, and one of them brought out an old math problem sheet. This problem sheet was briefly passed around and then put away again. One of the problems was a cute math puzzle. This problem was…

Find the sum of the first 1234 elements in following sequence
1, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 1, …


Sidenote:
There is a difference between a sequence and a series. The difference is:
a sequence is a list of numbers (1, 2, 1, 2, 2, …)
a series is the sum of a sequence (1 + 2 + 1 + 2 + 2 + … )


Before proceeding, I encourage you to solve the problem yourself.

The first thing I recognized was that the positions of “1” in the sequence corresponded to the triangle numbers.
1,
2, 1,
2, 2, 1,
2, 2, 2, 1,
2, 2, 2, 2, 1,

After the sheet was put away, the little problem stuck in my head. When I got the opportunity, I used my phone to run my quickly written script.

x=1234
for n in range(0, x-1):
  if (n*(n+1))/2 > x: 
    tri =n-1
    print x*2-tri 
    break

This finds the number of triangle numbers less than 1234 (which corresponds to the number of 1s in the sequence), then subtracts this number from 1234*2.

Setting Up pygeoip Environment on Ubuntu

GeoIP uses a large database to find information about a given IP address or website. I went through a couple different package installations before it integrated with my programs successfully. The fairly simple process I settled upon to set up the functional package, pygeoip (python API for GeoIP), is as follows:

sudo easy_install pygeoip
cd /usr

To find the path of GeoIP.dat, embrace the power of `  (not ‘, `  on US keyboards shares a key with ~).

find `pwd` -name 'GeoIP.dat'

After downloading GeoLiteCity.dat, a simple way rename the file to GeoIPCity.dat whilst moving said file to the same path as GeoIP.dat (for convenience)…

sudo mv Downloads/GeoLiteCity.dat /usr/share/GeoIP/GeoIPCity.dat

In order to check the success of your environment’s set-up, run this as a py script or in a term window

import pygeoip
#gi = pygeoip.GeoIP('/usr/share/GeoIP/GeoIP.dat', pygeoip.MEMORY_CACHE)
gi = pygeoip.GeoIP('/usr/share/GeoIP/GeoIPCity.dat)
print gi.record_by_addr('64.233.161.99')

Python: Planning Lunches and Groceries

I bring my lunch to work to avoid food poisoning (I have food allergies, not paranoia). To be able to make these lunches for work when exhausted, I’d like a list of what to pack for a set number of days.

Today, I solved this problem by writing foodplan.py

from random import randint


protein= [‘2 hard boiled eggs’, ‘1 chicken sausage’, ‘1 serving soup’]
grains = [‘1 serving baby rice’, ‘1 serving overnight GF oatmeal’]
sides = [‘apples’, ‘coffee’, ‘plain’, ‘blueberries’, ‘bananas’]
fruit_veg = [‘cherry tomatoes’, ‘grapes’, ‘bell peppers’, ‘cucumbers’, ‘apples’]

def generate():
    print “How many days? n”
    days = int(raw_input())
    [one_meal() for day in xrange(days)]

def one_meal():
    print “%s n %s with %s n %s nn” %(protein[randint(0, len(protein)-1)], grains[randint(0, len(grains)-1)], sides[randint(0, len(sides)-1)], fruit_veg[randint(0, len(fruit_veg)-1)])

if __name__ == ‘__main__’:
    generate()

If, like me, your hatred for hard code exceeds your wariness of eval, you can rewrite one_meal() as two functions:

from random import randint

protein= [‘2 hard boiled eggs’, ‘1 chicken sausage’, ‘1 serving soup’]
grains = [‘1 serving baby rice’, ‘1 serving overnight GF oatmeal’]
sides = [‘apples’, ‘coffee’, ‘plain’, ‘blueberries’, ‘bananas’]
fruit_veg = [‘cherry tomatoes’, ‘grapes’, ‘bell peppers’, ‘cucumbers’, ‘apples’]

def generate():
    print “How many days? n”
    days = int(raw_input())
    [one_meal() for day in xrange(days)]

def one_meal():
    print ” %s n %s with %s n %s nn” % (pick(‘protein’), pick(‘grains’), pick(‘sides’), pick(‘fruit_veg’))

def pick(name):
    func = eval(name)
    return func[randint(0, len(func)-1)]

if __name__ == ‘__main__’:
    generate()

Adjust the contents of the arrays at the beginning to make this code applicable to your lunch planning desires.

Last year, I wanted to email myself grocery lists. I wrote foodemail.py to solve this problem (seems that my tastes haven’t changed much):

import smtplib
from datetime import datetime
import get


groceries = [“Hey! nnThe grocery list for this week is as follows: nn”]
food = {‘protein’: [[‘hummus’, 1.5, 780],[‘honey roasted turkey’, 0.75, 270],[‘tofu’, 0.4, 500], [‘soup’, 1.5, 250]], ‘drinks’: [[‘diet ginger ale(packs of 12)’, 0.5], [‘water bottles’, 3], [‘unsweetened almond/soy milk’, 0.75]], ‘fruit/veg’: [[‘oranges/clementines’, .2, 60],[‘bananas(bunch)’, .2, 80],[‘green apples’, 3, 80], [‘salad’, 1/3, 40], [‘frozen corn’, 0.5, 100],[‘green peppers’, 2, 15]]}

def noticeEMail(starttime, usr, psw, fromaddr, toaddr, message):
    # Calculate run time
    runtime=datetime.now() - starttime
    # Initialize SMTP server
    server=smtplib.SMTP(‘smtp.gmail.com:587’)
    server.starttls()
    server.login(usr,psw)
    # Send email
    senddate=datetime.strftime(datetime.now(), ‘%Y-%m-%d’)
    subject=”Grocery List for this week”
    m=”Date: %srnFrom: %srnTo: %srnSubject: %srnX-Mailer: My-Mailrnrn” % (senddate, fromaddr, toaddr, subject)
    msg=message
    server.sendmail(fromaddr, toaddr, m+msg)
    server.quit()

if __name__ == ‘__main__’:
    # Start time of script
    starttime=datetime.now()
    # Fill these in with the appropriate info…
    usr=’YOUREMAIL’
    psw=get.getPass(‘YOURPASSWORD’)
    fromaddr=’YOUREMAIL@SERVER.COM’
    toaddr= [‘RECIPIENT@SERVER.COM’, ‘RECIPIENT2@SERVER.COM’] #As many recipients as you like
    #creates appropriate grocery info
    index = [‘protein’, ‘drinks’, ‘fruit/veg’]
    print “Days?"
    days = int(raw_input())
    for x in range(0, len(food)):
        for y in range(0, len(food[index[x]])-1):
            if int(days*food[index[x]][y][1]) > 0:
                string = ‘t’ + food[index[x]][y][0] + ‘ x%d n’ % int(days*food[index[x]][y][1])
                groceries.append(string)
            else: pass
    print ‘ ‘.join(str(k) for k in groceries)
    print “Enter 0 if satisfactory, enter 1 to add to the list: “
    user = int(raw_input())
    if user == 0: pass
    elif user == 1:
        print “What would you like to add?”
        addition = raw_input()
        y = [x.strip() for x in addition.split(‘,’)]
        for x in xrange(0, len(y)):
            groceries.append(“t%s n” % y[x])
    groceries.append(“nCheers! nt tRin”)
    msg = ‘ ‘.join(str(k) for k in groceries)
    # Send notification email
    noticeEMail(starttime, usr, psw, fromaddr, toaddr, msg)

Looking at foodemail.py, I see that my coding has become more efficient over this past year.

I hope that these programs are useful for your food planning!

I Write Poetry in Python

I enjoy songwriting. Here are the lyrics to a silly, fun song I wrote a couple of months ago.

I Write Poetry in Python by Catherine Ray

I have no life and I can prove it mathematically.
I judge your human worth using a spectrum of rationality
I know vector calculus, but I can’t remember how to do long division.
When I compile, my waiting ritual resembles superstition.
I know how to integrate a chicken and take the derivative of water,
I had to pick just one, Asimov ‘s my favorite author.
And I… I write poetry in Python.

You put the period outside the quotes! You’re not quoting the end of the sentence
What the heck do english majors know, anyway. Correction fail, I demand repentance!
I’ve gutted and rebuilt my laptop 5 times since I last changed the oil in my crappy car.
Yet, I’ll bet you I can’t name a single television star.
‘Cause I, I write poetry in Python.

I’ve got to bring a jacket with me, in the middle of summer,
’cause there’s a wind-chill factor in the lab, my priority is comfort
The three most dangerous things in the world are a programmer with a soldering iron,
a hardware engineer with a software patch,
and a user with an idea.
So, I, I just write poetry in Python.

Pythonic Method Calling

I have an aversion to hard-coding. Hard coding is when you write out a long, elaborate code that could also be written with a dynamic loop. This usually limits the ability to easily adjust your own code in case you want to change something later (or re-use it). “Hard coding” refers to “rigidly” writing out things instead of keeping them dynamic.

This practice is frowned upon by most of the programmers I’ve met (especially the Python programmers). In Python, code is ‘pythonic’ if it is well-written and concise. This link is to an excellent article on ‘What is Pythonic?’, I highly recommend reading this for a more in-depth explanation of the term: http://blog.startifact.com/posts/older/what-is-pythonic.html

Today, while I was revising my Prime Number Algorithm program (an earlier post), I figured out how to pass functions as strings. The eval function allows me to run python code within itself. This definition of eval is vague and unhelpful.

Let me show you to make a calling method, ‘execute,’ pythonic in order to explain the purpose of the eval function.

Let’s assume that we want a program that executes methods p1(n), p2(n), …, p5(n) given some string n. I will refer to these methods collectively as ‘p’-methods.

We could hard-code this as such:

class Test():
    def execute(self, n):
        self.p1(n)
        self.p2(n)
        self.p3(n)
        self.p4(n)
        self.p5(n)

    def p1(self,n):
        print “Hello”+n
    def p2(self,n):
        print “Hello2″+n
    def p3(self, n):
        print “Hello3″+n
    def p4(self,n):
        print “Hello4″+n
    def p5(self,n):
        print “Hello5″+n

if __name__ == ‘__main__’:
    test = Test()
    test.execute(‘ World!’)

The above program will run all 5 ‘p’-methods and print the appropriate strings. However, what if there were 1000 different ‘p’-methods we needed to run? Must we type out each method in order to call these ‘p’-methods within the execute method?

At first, I created a forloop to iteratively call execute, providing a new method each time. If you run the code below, execute will treat the ‘method’ parameter as a String type (instead of a function) and throws an error.

(NON-FUNCTIONAL)

class Test():
    def execute(self, method_name):
        self.method_name(‘ World!’)   

    def send_method(self):
        for version in xrange(1,6):
            version = str(version) #run each ‘p’-method version = 1, 2, 3, 4
            method = ‘self.’+’p’+version #note that type(method == String
            self.execute(method)

    def p1(self,n):
        print “Hello”+n
    def p2(self,n):
        print “Hello2″+n
    def p3(self, n):
        print “Hello3″+n
    def p4(self,n):
        print “Hello4″+n
    def p5(self,n):
        print “Hello5″+n

if __name__ == ‘__main__’:
    test = Test()
    test.send_method()

We are so very close to having a pythonic solution. In order to fix this error, we must make the String into a method call. With one extra line, we evaluate the String input (‘method_name’) as a function and run all ‘p’-methods! The final version of the execute method is:

class Test():
    def execute(self, method_name):
        method = eval(method_name)
        methodrun = method(‘ World!’)   

    def send_method(self):
        for version in xrange(1,5):
            version = str(version) #test each version of the algorithm, version = 1, 2, 3, 4
            method = ‘self.’+’p’+version
            self.execute(method)

    def p1(self,n):
        print “Hello”+n
    def p2(self,n):
        print “Hello2″+n
    def p3(self, n):
        print “Hello3″+n
    def p4(self,n):
        print “Hello4″+n
    def p5(self,n):
        print “Hello5″+n

if __name__ == ‘__main__’:
    test = Test()
    test.send_method()

I hope this gives you an idea of: why hard-coding is bad, what ‘pythonic’ means, how ‘eval’ comes in handy and what I do in my free time.

Implementation of Prime Number Algorithms

I’m currently reading Algorithms Unplugged, lent to me by my friend and professor, Dr. Marr.

The text provided 4 versions of an algorithm and claimed that each new version had a noticeable increase in runtime efficiency.

These algorithms take some number n and return a list of all prime numbers up to and including n. For example, if n = 13, this algorithm returns [2,3,5,7,11,13].

I was skeptical of their claims \(\Rightarrow\) I took the pseudocode and converted it into functional Python, then wrote a timing function: this tests each algorithm by letting n = 2^6 to 2^20 and repeating each calculation 1000 times (in order to find the average runtime).

I had to wrestle with Python in order to stop it from rounding off the calculated runtimes (treating runtime as a float), which lead to an interesting adventure into the time module man page.

tl;dr

  • take pseudocode from a book (p.121-127 of Algorithms Unplugged by various German computer scientists*)
  • translate said pseudocode into functional code, and
  • test the run-times of each algorithm

'''
Catherine Ray
prime_runtime0.py
'Algorithms Unplugged' Demonstration
Program uses algorithms listed in pseudocode from pg.119-127. Each algorithm returns a list of all primes up to some number n.
There are 4 versions of this algorithm; this program computes the average runtimes of each version and prints to stdout.
'''
import math
import time as t
class Runtime():
 def execute(self):
  repeat = 1000 #number of times to repeat runtime calculation
  n = [2**x for x in xrange(6, 21, 7)] #produce list of large numbers to test algorithms
  #n = [2**6, 2**20]
  for v in xrange(1,5):
   method = 'self.prime_number'+str(v) #test each version of the algorithm, version = 1, 2, 3, 4
   print 'ntVersion ' + str(v), 'nHighest Prime Number Computed : Average Runtimen'  #find runtime
   [self.runtime(method, number, repeat) for number in n] 
 def runtime(self, method, n, repeat):
 #function = function to test
 #n = highest prime to compute
 #repeat = number of trials to run
  method = eval(method)
  total = 0 #reset total
  for r in xrange(0, repeat+1): 
   start = t.time() #get start time
   methodrun=method(n) 
   end = t.time() #get end time
  total = total + end-start #add to previously calculated time
  average_time = total/repeat #find average runtime
  print  '2^%d :' %(int(math.log(n)/math.log(2))), average_time
 def prime_number1(self, n): #version 1, pg. 121
  list = [i for i in xrange(2,n+1)] #write down all numbers between 2 and n in a list
  for i in xrange(2, n+1):
   for k in xrange(2, n+1):
    if i*k in list: list.remove(i*k) #if i*k is in list, remove
    else: pass #if i*k isn't in list, do nothing
  return list
 def prime_number2(self, n): #version 2, pg. 123
  list = [i for i in xrange(2,n+1)] #write down all numbers between 2 and n in a list
  for i in xrange(2, int(math.floor(math.sqrt(n)))+1):
   for k in xrange(2, int(math.floor(n/i))+1):
    if i*k in list: list.remove(i*k) #if i*k is in list, remove
    else: pass #if i*k isn't in list, do nothing
  return list
 def prime_number3(self, n): #version 3, pg. 125
  list = [i for i in xrange(2,n+1)] #write down all numbers  between 2 and n in a list
  for i in xrange(2, int(math.floor(math.sqrt(n)))+1):
   if i in list:
    for k in xrange(2, int(math.floor(n/i))+1):
     if i*k in list: list.remove(i*k) #if i*k is in list, remove
     else: pass #if i*k isn't in list, do nothing
  return list
 def prime_number4(self, n): #final version, pg.127
  list = [i for i in xrange(2,n+1)] #write down all numbers between 2 and n in a list
  for i in xrange(2, int(math.floor(math.sqrt(n)))+1):
   if i in list:
    for k in xrange(int(math.floor(n/i)), i-1, -1):
     if k in list:
      if i*k in list: list.remove(i*k)  #if i*k is in list, remove
      else: pass #if i*k isn't in list, do nothing
  return list
if __name__ == '__main__':
 runtime = Runtime()
 runtime.execute()

I left the code to run overnight.

Taking a brief glance at the output, I found confirmation of the authors’ claims. The runtime each version is less than the previous version (version4 should take less time to run than version1).


*Berthold Vöcking, Helmut Alt, Martin Dietzfelbinger, Rüdiger Reischuk, Christian Scheideler, Heribert Vollmer, Dorothea Wagner