[C/C++] Project Euler #19 Counting Sundays

I believe this problem is designed to test whether you can correctly identify leap years.

In C/C++, you can easily solve this problem using the `mktime()` function in the `time.h` header file. However, I tried to find a slightly different approach. (When using the `mktime()` function, I wonder if leap seconds are also calculated. The day of the week for 0:00:00 on the 1st day of the month in year y is different. When I change it to 1:00, it comes out correctly.)

If you ask people what the basis for a one-year cycle is, few people know the correct answer.

Many people will probably think it's the time it takes for the Earth to revolve around the Sun.

Oh, was I wrong? Some of you may be wondering.

To be precise, one year is the time it takes from one vernal equinox to the next. It takes slightly longer for the Earth to revolve around the Sun than the standard mentioned earlier.

The Earth rotates and revolves around the Sun, but it also undergoes precession in addition to rotation. Currently, the North Star is located above the Earth's axis, but this can change. The precession cycle is about 26,000 years, so it is almost impossible for us to experience precession in our lifetime. The constellation corresponding to the date of birth also changes by one sign every 2,000 years. In other words, if Jesus was born in December, it would have been a different sign than Sagittarius, which it is now.

 

The way ancient people calculated the length of a year is also a bit different. It's a bit amusing when people talk about Cheomseongdae, a  magnificent cultural heritage of Silla, and claim that they knew a year was 365 and 1/4 days long.

First of all, the number of stones used in Cheomseongdae is not 365, and even if it were, it was already a well-known calendar system in China and other regions. The Julian calendar, established in 45 BC (700 years before Queen Seondeok), defines a year as 365 and 1/4 days. It also sets months with 30 and 31 days, with the remaining month being February. (You might wonder why February, but in the ancient Roman calendar, March was likely the first month. This is evident in the names of the months that have come down to us: September, meaning 7, is the ninth month; October, meaning 8, is the tenth; November, meaning 9, is the eleventh; and December, meaning 10, is the twelfth.)

The length of a solar year is approximately 365.2422 days. A solar year means the time between vernal equinoxes. In this case, by adding one day every four years as a leap year, it becomes 365.25 days. By removing a leap year every 100 years, it becomes 365.24 days. By adding a leap year every 400 years, it becomes 365.2425 days. The Gregorian calendar was created in 1582, named after Pope Gregory, and is the calendar we still use today. Since the number of incorrect days over 1600 years is about 12, it seems likely that the vernal equinox fell on January 1st in Roman times.

When I was writing the program, I initially thought I could calculate the number of days from January 1, 1 AD using a general formula. But that wasn't easy. So, I tried to create a formula that would result in 31 days, 30 days, ..., 28 days (or 29 days) starting from March.

Here, I simply extracted the parameters using a program.

 

void GetParameters()
{
    int m[] = { 31, 30, 31, 30, 31, 31, 30, 31, 30, 31, 31 };
    for( int a = 1 ; a <= 11 ; a++ )
    {
        for( int b = 30*a-1 ; b <= 31*a+1 ; b++ )
        {
            for( int c = 0 ; c < 5 ; c++ )
            {
                int t = 0, i;
                for( i = 1 ; i < 12 ; i++ )
                {
                    int s = (b*i + c)/a;
                    if( s-t != m[i-1] ) break;
                    t = s;
                }
                if( i == 12 ) printf("(%d, %d, %d)\n", a, b, c);
            }
        }
    }
}

 

As a result of running the function, I was able to obtain the parameters 5, 153, and 2. In other words, when counting from March, the number of days until January of the following year can be found using the following formula:

\[ \text{days} = \left\lfloor \frac{153m + 2}{5} \right\rfloor \]

And the formula for calculating leap years is:

\[ \text{days} = 365y + \left\lfloor \frac{y}{4} \right\rfloor - \left\lfloor \frac{y}{100} \right\rfloor + \left\lfloor \frac{y}{400} \right\rfloor \]

In C/C++, you don't have to worry about this because integer operations automatically truncate the decimal point.

Honestly, in a program, it would be faster to put the accumulated number of days in an array rather than using the formula above. I just thought it would be boring to code it simply...

 

calendar

So, here is the C/C++ source code for solving problem #19:

//------------------------------------------------
//    Project Euler #19 - Counting Sundays
//        - by Aubrey Choi
//        - created at 2015-01-16
//------------------------------------------------
#include <stdio.h>
#include <time.h>

int GetWeekDay(int y, int m, int d);
void GetParameters();

int main()
{
    int count = 0;

    GetParameters();
    for( int y = 1901 ; y <= 2000 ; y++ )
    {
        for( int m = 1 ; m <= 12 ; m++ )
        {
            if( GetWeekDay(y, m, 1) == 0 ) count++;
        }
    }
    printf("Ans = %d\n", count);
}

int GetWeekDay(int y, int m, int d)
{
    if( m <= 2 ) { m += 9; y += 4799; } else { m -= 3; y += 4800; }
    int days = 365*y + y/4 - y/100 + y/400 + (153*m+2)/5 + d - 32045;
    return (days+1)%7;
}

void GetParameters()
{
    int m[] = { 31, 30, 31, 30, 31, 31, 30, 31, 30, 31, 31 };
    for( int a = 1 ; a <= 11 ; a++ )
    {
        for( int b = 30*a-1 ; b <= 31*a+1 ; b++ )
        {
            for( int c = 0 ; c < 5 ; c++ )
            {
                int t = 0, i;
                for( i = 1 ; i < 12 ; i++ )
                {
                    int s = (b*i + c)/a;
                    if( s-t != m[i-1] ) break;
                    t = s;
                }
                if( i == 12 ) printf("(%d, %d, %d)\n", a, b, c);
            }
        }
    }
}