Project Euler #19: Counting Sundays

Sort by

recency

|

71 Discussions

|

  • + 1 comment

    There is are a couple of very convenient features of calendars that many solutions here apear unaware of. Here's my solution.

    """
    Python
    ProjectEuler+ Problem #19: Counting Sundays
    by Seven
    
    concept: Every 400 years, the calendar cycle repeats. Therefore, by finding
    all sunday-the-firsts (STFs) in any range of 400 years, one can deduce the
    number of STFs in any other range.
    
    For convenience, we can calculate the range 2000-1-1 to 2399-12-31 since it
    will allow us to find any year's place in the cycle by simply taking the year
    mod 400. Herafter "relative year" refers to the year mod 400 for starting years
    and start year mod 400 + (end year - start year) for ending years.
    
    The day of the week for any given gregorian calander date can be calculated
    using a simple formula (see the weekday(y, m, d) function below). Since we only
    care about STFs, we only need to check the first of the month of each month.
    
    The results are stored in "lookup" as a boolean list, where each value represents
    a month from relative year 0 (e.g. 2000 or 11804211600) through relative year 399
    (e.g. 2799 or 2810399). True indicates the first of the month was
    a Sunday.
    
    Since the end date is never more than 1000 years, 12 months and 31 days from the
    start year, we can repeat this range by 4 for convenience. Thus, the relative
    start and end dates always fall within the range of the lookup list.
    
    The convenience function ym(y, m) takes a relative year and month and returns the
    associated index in the lookup list.
    
    Finally, given a start and end date, we simply find the relative years for those
    dates, and sum the values of the lookup list between the dates (inclusive).
    
    """
    
    from math import floor
    
    def weekday(y, m, d):
        """
        y: year
        m: month (1=March - 12=February of following year)
        d: day
        
        return: day of week (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.
        by Alex Lopez-Ortiz
        """
        
        ## adjest the month number, shifting Jan and Feb back one year
        m -= 2
        if m < 1:
            m += 12
            y -= 1
        ## Split the year into the c=Century and y=two digit year
        c, y = divmod(y, 100)
        return (d + floor(2.6*(m) - .2) - 2 * c + y +y//4 +c//4) % 7
    
    def ym(y, m):
        """
        y: year
        m: month
        
        return: index of the year, month in the lookup list
        """
        return 12*y + (m-1)
    
     
    def span_count(y0, m0, y1, m1):
        """
        y0: start year
        m0: start month
        y1: end year
        y2: end month
        
        return: total STFs in the given range
        """
        ## find the distance from y0 to y1
        y1 -= y0
        ## find the relative starting year
        y0 %= 400
        ## find the relative ending year
        y1 += y0
        ## sum the values between the two dates (inclusive)
        return sum(lookup[ym(y0, m0):ym(y1, m1) + 1])
    
    
    
    ## defining the lookup
    global lookup
    lookup = []
    for y in range(400):
        for m in range(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 list
    lookup = lookup*4
    
    ## parse inputs
    for i in range(int(input())):
        y0, m0, d0 = [int(n) for n in input().split(' ')]
        y1, m1, d1 = [int(n) for n in input().split(' ')]
        ## if the start date is after the first of the month, we can just start on
        ## the first of the following month
        if d0 > 1:
            m0 += 1
            if m0 == 13:
                m0 = 1
                y0 += 1
        ## find the result
        print(span_count(y0, m0, y1, m1))
    
  • + 0 comments

    //c#

    using System;

    public class Solution { private static int SUNDAY = 0;

    public static void Main(string[] args) { int t = Convert.ToInt32(Console.ReadLine()); while (t-- > 0) { // input long[,] dateArray = new long[2, 3]; for (int i = 0; i < 2; i++) { string[] input = Console.ReadLine().Split(' '); for (int j = 0; j < 3; j++) { dateArray[i, j] = Convert.ToInt64(input[j]); } } // begin Adjust(ref dateArray); // long ak = 0; while (true) { if (dateArray[0, 2] == 1) { if (Verify(dateArray[0, 0], dateArray[0, 1], dateArray[0, 2])) { ak++; } } // set date dateArray[0, 2] = 1; // month plus 1 dateArray[0, 1]++; if (dateArray[0, 1] > 12) { dateArray[0, 1] = 1; dateArray[0, 0]++; } if (OverDate(dateArray)) { break; } } Console.WriteLine(ak); } }

    /** * check if dateArray[0] is later than dateArray[1] * @param dateArray * @return */ private static bool OverDate(long[,] dateArray) { if (dateArray[0, 0] > dateArray[1, 0]) { return true; } else if (dateArray[0, 0] == dateArray[1, 0]) { if (dateArray[0, 1] > dateArray[1, 1]) { return true; } else if (dateArray[0, 1] == dateArray[1, 1]) { if (dateArray[0, 2] > dateArray[1, 2]) return true; } } return false; }

    /** * let a[0] be earlier than a[1] * @param dateArray */ private static void Adjust(ref long[,] dateArray) { if (OverDate(dateArray)) { Exchange(ref dateArray); } }

    /** * exchange two input date * @param dateArray */ private static void Exchange(ref long[,] dateArray) { long[] tmp = new long[3]; tmp = new long[3] { dateArray[1, 0], dateArray[1, 1], dateArray[1, 2] }; dateArray[1, 0] = dateArray[0, 0]; dateArray[1, 1] = dateArray[0, 1]; dateArray[1, 2] = dateArray[0, 2]; dateArray[0, 0] = tmp[0]; dateArray[0, 1] = tmp[1]; dateArray[0, 2] = tmp[2]; }

    private static bool Verify(long year, long month, long day) { // w=(y + (y / 4) + (c / 4) - (2 * c) + ((26 * (month + 1)) / 10) + day - 1) % 7 // long sourceY = year; // long sourceM = month; if (month < 3) { month += 12; year -= 1; } long c = year / 100; long y = year % 100; int w = (int)((y + (y / 4) + (c / 4) - (2 * c) + ((26 * (month + 1)) / 10) + day - 1) % 7); bool t = w == SUNDAY; // if (t) { // Console.WriteLine(sourceY + "-" + sourceM + "-" + day); // } return t; } }

  • + 0 comments

    In c#:

    using System;

    public class Solution { private static int SUNDAY = 0;

    public static void Main(string[] args)
    {
        int t = Convert.ToInt32(Console.ReadLine());
        while (t-- > 0)
        {
            // input
            long[,] dateArray = new long[2, 3];
            for (int i = 0; i < 2; i++)
            {
                string[] input = Console.ReadLine().Split(' ');
                for (int j = 0; j < 3; j++)
                {
                    dateArray[i, j] = Convert.ToInt64(input[j]);
                }
            }
            // begin
            Adjust(ref dateArray);
            //
            long ak = 0;
            while (true)
            {
                if (dateArray[0, 2] == 1)
                {
                    if (Verify(dateArray[0, 0], dateArray[0, 1], dateArray[0, 2]))
                    {
                        ak++;
                    }
                }
                // set date
                dateArray[0, 2] = 1;
                // month plus 1
                dateArray[0, 1]++;
                if (dateArray[0, 1] > 12)
                {
                    dateArray[0, 1] = 1;
                    dateArray[0, 0]++;
                }
                if (OverDate(dateArray))
                {
                    break;
                }
            }
            Console.WriteLine(ak);
        }
    }
    
    /**
     * check if dateArray[0] is later than dateArray[1]
     * @param dateArray
     * @return
     */
    private static bool OverDate(long[,] dateArray)
    {
        if (dateArray[0, 0] > dateArray[1, 0])
        {
            return true;
        }
        else if (dateArray[0, 0] == dateArray[1, 0])
        {
            if (dateArray[0, 1] > dateArray[1, 1])
            {
                return true;
            }
            else if (dateArray[0, 1] == dateArray[1, 1])
            {
                if (dateArray[0, 2] > dateArray[1, 2])
                    return true;
            }
        }
        return false;
    }
    
    /**
     * let a[0] be earlier than a[1]
     * @param dateArray
     */
    private static void Adjust(ref long[,] dateArray)
    {
        if (OverDate(dateArray))
        {
            Exchange(ref dateArray);
        }
    }
    
    /**
     * exchange two input date
     * @param dateArray
     */
    private static void Exchange(ref long[,] dateArray)
    {
        long[] tmp = new long[3];
        tmp = new long[3] { dateArray[1, 0], dateArray[1, 1], dateArray[1, 2] };
        dateArray[1, 0] = dateArray[0, 0];
        dateArray[1, 1] = dateArray[0, 1];
        dateArray[1, 2] = dateArray[0, 2];
        dateArray[0, 0] = tmp[0];
        dateArray[0, 1] = tmp[1];
        dateArray[0, 2] = tmp[2];
    }
    
    private static bool Verify(long year, long month, long day)
    {
        // w=(y + (y / 4) + (c / 4) - (2 * c) + ((26 * (month + 1)) / 10) + day - 1) % 7
        // long sourceY = year;
        // long sourceM = month;
        if (month < 3)
        {
            month += 12;
            year -= 1;
        }
        long c = year / 100;
        long y = year % 100;
        int w = (int)((y + (y / 4) + (c / 4) - (2 * c) + ((26 * (month + 1)) / 10) + day - 1) % 7);
        bool t = w == SUNDAY;
        // if (t) {
        // Console.WriteLine(sourceY + "-" + sourceM + "-" + day);
        // }
        return t;
    }
    

    }

  • + 0 comments

    100%

    # Enter your code here. Read input from STDIN. Print output to STDOUT
    
    m_days = [0,31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    
    def is_leap(y):
        if y % 100 == 0:
            return(True if y % 400 == 0 else False)
        if y % 4 == 0:
            return(True)
        else:
            return(False)
        
    def no_of_leapyear(y):
        if y[0] > 2000:
            return(100//4 + (y[0]-2000)//4 - (y[0]-2000)//100 + (y[0]-2000)//400 - 
            ( 1 if is_leap(y[0]) and (y[1] == 1 or (y[1] == 2 and y[2] <= 28) ) else 0 ) ) 
        else:
            return((y[0]-1900)//4 -
            ( 1 if is_leap(y[0]) and (y[1] == 1 or (y[1] == 2 and y[2] <= 28) ) else 0 ) ) 
        
    
    for a0 in range(int(input())):
        
        y1 , y2 = list(map(int,input().split())), list(map(int,input().split()))
        
        if not y1[2] == 1:
            if y1[1] == 12:
                y1 = [y1[0]+1, 1, 1]
            else:
                y1 = [y1[0], y1[1]+1, 1]
        
        diffy1 = 365 * (y1[0] - 1900) + sum(m_days[:y1[1]]) + (y1[2] - 1) + no_of_leapyear(y1)
        
        sundays = 1 if diffy1 % 7 == 6 else 0
        
        #print(diffy1 % 7)
        
        diffy1 = 6 - diffy1 % 7 # diffs to sunday
        
        if y1[0] == y2[0]:
            if y1[1] > y2[1]:
                print(0)
                continue
            elif y1[1] == y2[1]:
                print(sundays)
                continue
        elif y1[0] > y2[0]:
            print(sundays)
            continue
         
        #print(diffy1)
        while not y1[0] > y2[0] and not (y1[0] == y2[0] and y1[1] >= y2[1]):
            
            #print(y1)
            
            d =(m_days[y1[1]] + 1) if y1[1] == 2 and is_leap(y1[0]) else m_days[y1[1]]
                
            if d % 7 == diffy1:
                sundays = sundays + 1
            
            diffy1 = (diffy1 - d % 7) if d % 7 <= diffy1 else (7-(d % 7)+diffy1) 
            
            #print(y1, diffy1)
            
            if y1[1] == 12:
                y1 = [y1[0]+1, 1, 1]
            else:
                y1 = [y1[0], y1[1]+1, 1]
                
        print(sundays)
                
    
  • + 0 comments

    My code failed for test cases 2 3 4 5 but i didnt really what's wrong with my code Can someone help me, my code is written in C++

    #include <bits/stdc++.h>
    
    using namespace std;
    
    int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    
    int isLeapYear(long long y){
        if(y%4==0 && y%100!=0) return 1;
        if(y%400 == 0) return 1;
        else return 0;
    }
    
    int first(long long y, int m){
        long long LeapYears = (y - 1901)/4 - (y - 1901)/100 + (y - 1601)/400;
        long long NumOfDays = (y - 1900)*365 + LeapYears;
        for(int i = 1; i < m; i++){
            if(i == 2) NumOfDays += days[2] + isLeapYear(y);
            else NumOfDays += days[i];
        }
        return NumOfDays%7;
    }
    
    long long CountingSundays(long long y1, long long y2, int m1, int m2){
        long long cnt = 0;
        int isSunday = first(y1, m1);
        for(int m = m1; m <= 12; m++){
            if(isSunday == 6) cnt++;
            isSunday += days[m];
            if(m==2) isSunday += isLeapYear(y1);
            isSunday %= 7;
        }
    
        for(long long y = y1+1; y < y2; y++){
            for(int m = 1; m <= 12; m++){
                if(isSunday == 6) cnt++;
                isSunday += days[m];
                if(m==2) isSunday += isLeapYear(y);
                isSunday %= 7;
            }
        }
    
        for(int m = 1; m < m2; m++){
            if(isSunday == 6) cnt++;
            isSunday += days[m];
            if(m==2) isSunday += isLeapYear(y2);
            isSunday %= 7;
        }
        return cnt;
    }
    
    int main(){
        int t; cin >> t;
        while(t--){
            long long y1, y2; int m1, m2, d1, d2;
            cin >> y1 >> m1 >> d1 >> y2 >> m2 >> d2;
            if(d1 > 1) m1++;
            cout << CountingSundays(y1,y2,m1,m2) << endl;
        }
    }