We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
There is are a couple of very convenient features of calendars that many solutions here apear unaware of. Here's my solution.
"""PythonProjectEuler+Problem#19:CountingSundaysbySevenconcept:Every400years,thecalendarcyclerepeats.Therefore,byfindingallsunday-the-firsts(STFs)inanyrangeof400years,onecandeducethenumberofSTFsinanyotherrange.Forconvenience,wecancalculatetherange2000-1-1to2399-12-31sinceitwillallowustofindanyyear'splaceinthecyclebysimplytakingtheyearmod400.Herafter"relative year"referstotheyearmod400forstartingyearsandstartyearmod400+(endyear-startyear)forendingyears.Thedayoftheweekforanygivengregoriancalanderdatecanbecalculatedusingasimpleformula(seetheweekday(y,m,d)functionbelow).SinceweonlycareaboutSTFs,weonlyneedtocheckthefirstofthemonthofeachmonth.Theresultsarestoredin"lookup"asabooleanlist,whereeachvaluerepresentsamonthfromrelativeyear0(e.g.2000or11804211600)throughrelativeyear399(e.g.2799or2810399).TrueindicatesthefirstofthemonthwasaSunday.Sincetheenddateisnevermorethan1000years,12monthsand31daysfromthestartyear,wecanrepeatthisrangeby4forconvenience.Thus,therelativestartandenddatesalwaysfallwithintherangeofthelookuplist.Theconveniencefunctionym(y,m)takesarelativeyearandmonthandreturnstheassociatedindexinthelookuplist.Finally,givenastartandenddate,wesimplyfindtherelativeyearsforthosedates,andsumthevaluesofthelookuplistbetweenthedates(inclusive)."""frommathimportfloordefweekday(y,m,d):"""y:yearm:month(1=March-12=Februaryoffollowingyear)d:dayreturn:dayofweek(0=Sunday-6=Saturday)reference:https://cs.uwaterloo.ca/~alopez-o/math-faq/node73.html#:~:text=Here%20is%20a%20standard%20method,the%20day%20of%20the%20month.byAlexLopez-Ortiz"""## adjest the month number, shifting Jan and Feb back one yearm-=2ifm<1:m+=12y-=1## Split the year into the c=Century and y=two digit yearc,y=divmod(y,100)return(d+floor(2.6*(m)-.2)-2*c+y+y//4 +c//4) % 7defym(y,m):"""y:yearm:monthreturn:indexoftheyear,monthinthelookuplist"""return12*y+(m-1)defspan_count(y0,m0,y1,m1):"""y0:startyearm0:startmonthy1:endyeary2:endmonthreturn:totalSTFsinthegivenrange"""## find the distance from y0 to y1y1-=y0## find the relative starting yeary0%=400## find the relative ending yeary1+=y0## sum the values between the two dates (inclusive)returnsum(lookup[ym(y0,m0):ym(y1,m1)+1])## defining the lookupgloballookuplookup=[]foryinrange(400):forminrange(1,13):lookup.append(weekday(y,m,1)==0)## repeat the lookup so that relative start/end years always fall within## the range of the lookup listlookup=lookup*4## parse inputsforiinrange(int(input())):y0,m0,d0=[int(n)fornininput().split(' ')]y1,m1,d1=[int(n)fornininput().split(' ')]## if the start date is after the first of the month, we can just start on## the first of the following monthifd0>1:m0+=1ifm0==13:m0=1y0+=1## find the resultprint(span_count(y0,m0,y1,m1))
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #19: Counting Sundays
You are viewing a single comment's thread. Return to all comments →
There is are a couple of very convenient features of calendars that many solutions here apear unaware of. Here's my solution.