Calculate number of Fridays 13th between given dates - effective algorithm

calc.py

'''
Created on Nov 28, 2015

@author: ivan
'''


from datetime import date, timedelta
from copy import copy
import pprint

normal_year=[31,28,31,30,31,30,31,31,30,31,30,31]
leap_year=copy(normal_year)
leap_year[1]=29


# In Georgian calendar leap is is every 4th year,  but not every 100th and again yes every 400th
def is_leap(year):
    return ((year %4 == 0) and ( not year % 100 == 0)) or (year % 400 ==0)

# there can be 14 different variants of a year
# reqular year where 1 Jan is Monday or Tuesday ... or Sunday (7)
# leap year where 1 Jan is Monday or Tuesday ... or Sunday (7)
# So we can just create array 7 x 13 x 2 and then based first weekday of the year we can 
# directly get first week day of each month and first week day of next year
monthstart=[]
for d in range(7):
    monthstart.append([[d,d]])
    for m in range(0,12):
        nn=(monthstart[d][m][0]+normal_year[m]) % 7
        nl=(monthstart[d][m][1]+leap_year[m]) % 7
        monthstart[d].append([nn,nl])
        
#pprint.pprint( monthstart)
SUNDAY=6 # if month start with Sunday, then  13th is friday 
def fri13(start, end, optimize_by_cycles=True):
    
    # this just counts months starting  by sunday within a year - from start month to end month (excluded), 
    # months are zero based
    def count_year(ys, leap, start=0, end=12):
        y=monthstart[ys]
        return reduce(lambda x,y: x + (y[leap] == SUNDAY), y[start:end],0)
    
    #basic sanity check
    if start>end:
        raise ValueError('start must be smaller then end')
    res=0
    #In Gregorian calendar we have 400 years cycles -  after 400 years it's should be same date,same week day for sure
    cycles=(end.year - start.year) // 400
    if cycles and optimize_by_cycles:
        res+=cycles*688
        start=date(start.year+cycles*400, start.month, start.day)+timedelta(days=1)
        
    # weekday of 1-Jan of start year
    year_start=date(start.year,1,1).weekday()
    # just sum found days for each year between start and end
    for y in range(start.year, end.year+1):
        this_year = y
        this_year_start=year_start
        # need special conditions for start month of first year and end month of last year
        start_month= 0 if y> start.year else start.month-1 if start.day <=13 else start.month
        end_month=12 if this_year < end.year else end.month if end.day>=13 else end.month-1 
        leap=is_leap(this_year)
        res+=count_year(this_year_start,leap, start_month , end_month)
        year_start=monthstart[year_start][-1][leap] # next year start week day we can get easily form prev. year 
        
         
    return res

test.py

'''
Created on Nov 28, 2015

@author: ivan
'''
import unittest
from calc import fri13
from datetime import date, timedelta


def naive(start,end):
    count=0
    while start<=end:
        if start.day==13 and start.weekday()==4:
            count+=1
        start+= timedelta(days=1)
    return count
class Test(unittest.TestCase):

    def test_cycle(self):
        self.assertEqual(date(1999, 5,8).weekday(), date(2399, 5,8).weekday())
        self.assertEqual(date(1800, 1,2).weekday(), date(2200, 1,2).weekday())
    def test(self):
        start=date(2015,1,1)
        end=date(2016,1,1)
        self.assertEqual(naive(start, end),3)
        self.assertEqual(fri13(start,end), naive(start, end))
        
        start=date(2015,1,1)
        end=date(2020,1,1)
        self.assertEqual(fri13(start,end), naive(start, end))
    
    def test2(self):    
        start=date(2015,3,14)
        end=date(2020,12,13)
        self.assertEqual(fri13(start,end), naive(start, end))
        
    def test3(self):    
        start=date(2015,11,12)
        end=date(2015,11,14)
        self.assertEqual(fri13(start,end), naive(start, end))
        
        start=date(2015,11,13)
        end=date(2015,11,13)
        self.assertEqual(fri13(start,end), naive(start, end))
        self.assertEqual(fri13(start,end),1)
    
        start=date(2015,3,13)
        end=date(2015,11,13)
        self.assertEqual(fri13(start,end), naive(start, end))
        self.assertEqual(fri13(start,end),2)
        
        start=date(2015,3,14)
        end=date(2015,11,13)
        self.assertEqual(fri13(start,end), naive(start, end))
        self.assertEqual(fri13(start,end),1)
        
        start=date(2015,3,13)
        end=date(2015,11,12)
        self.assertEqual(fri13(start,end), naive(start, end))
        self.assertEqual(fri13(start,end),1)
        
    def test4(self):
        start=date(1615,11,12)
        end=date(9015,11,14)
        self.assertEqual(fri13(start,end), naive(start, end))
        
    def test5(self):
        start=date(1615,11,12)
        end=date(9015,11,14)
        self.assertEqual(fri13(start,end),12729)
        
    def test6(self):
        
        start=date(1820,4,8)
        end= date(2220, 4,8)
        x=fri13(start,end, optimize_by_cycles=False)
        
        start=date(2015,11,13)
        end= date(2415,11,13)
        z=fri13(start,end, optimize_by_cycles=False)
        
        start=date(2015,11,13)
        end= date(2815,11,13)
        z=fri13(start,end, optimize_by_cycles=False)
        self.assertEqual(x,z/2)
        
        start=date(2015,11,12)
        end= date(2415,11,12)
        z=fri13(start,end, optimize_by_cycles=True)
        
        self.assertEqual(x,z)
        
        start=date(1920,7,30)
        end= date(2320, 7,30)
        y=fri13(start,end)
        print y
        self.assertEqual(x,y)

if __name__ == "__main__":
    #import sys;sys.argv = ['', 'Test.test']
    unittest.main()