Problem 19 : Counting Sundays

Counting Sundays

Problem 19

You are given the following information, but you may prefer to do some research for yourself.

• 1 Jan 1900 was a Monday.
• Thirty days has September,
  April, June and November.
  All the rest have thirty-one,
  Saving February alone,
  Which has twenty-eight, rain or shine.
  And on leap years, twenty-nine.
• A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

                                                                                                       (https://projecteuler.net/problem=19)
Now we are on the problem with calendar counting.

I have always hoped that our current calendar becomes simpler and more uniform (without any confusing leap years and varying month lengths, ... etc), but, whatever.

At least it makes calendar counting problems more fun and exciting, so I'm ok with it now.

We are dating back to January 1st, 1901, when 20^th century began.

Here are some important events in 1901.

Ok. Let's start writing our algorithm.

First method that I want is to determine if the year is leap year or not.

Because leap years are divisible by 4, but centuries don't count, but 400-multiple centuries do count, it seems tedious, and we need several steps.

public static boolean isLeap(int y)

{...}

So first filter is whether the year is multiple of 4; if it is, then that year can be leap year possibly; if not, then no chance.

if (y%4 == 0)
{
    ...
}
return false;

Second, if the year is divisible by 4, then we check if the year is multiple of 400; if it is, then it is a leap year; if not, then we'll see.

if (y%4 == 0)
{
    if (y%400 == 0) return true;
    else ...
}

Third, if the year isn't multiple of 400, then we check if the year is multiple of 100; if it is. then it is not a leap year; if not, it is.

if (y%4 == 0)
{
    if (y%400 == 0) return true;
    else if (y%100 == 0) return false;
    return true;
}

When we combine them:

public static boolean isLeap(int y)
{
    if (y%4 == 0)
    {
        if (y%400 == 0) return true;
        else if (y%100 == 0) return false;
        return true;
    }
    return false;
}

After making that method, I worked on how to easily find out Sundays without using complicated algorithms involving arrays or Strings.

So here is the system that I designed, and it worked perfectly:

S	M	T	W	T	F	S
0	1	2	3	4	5	6

Using divisibility by 7, we can get the reminders from 0-6.

if the day count divided by 7 gives us 1, then we know that it is Monday.

For example, starting with Monday, we want to know what day it is after 24 days.

Because Monday is 1 in the chart, and 1 + 24 = 25, we divide it by 7, and we will get 4 as a reminder.

And 4 is Thursday, according to the chart I made. Ah! It is Thursday after 24 days.

My algorithm is the Modulus Representation of Days (Modulo 7).

From now on, it becomes really easy implementation.

We start with 0 Sunday count, and day 2 (which is Tuesday, according to the chart I made):

int count = 0, day = 2;

Year from 1901 to 2000 and month from 1 to 12:

for (int y = 1901; y <= 2000; y++) // years
{
    for (int m = 1; m <= 12; m++) // months
    {
        ...
    }
    ...
}

If months are April, June, September, and November, there are 30 days always:

if (m == 4 || m == 6 || m == 9 || m == 11)
    day += 30;

If February, then we check leap-year-ity of the year:

else if (m == 2)
{
    if (isLeap(y)) day += 29;
    else day += 28;
}

Rest of the months are 31 days:

else day += 31;

After that, we divide by 7 and get the reminder. If the reminder is 0 on the first day of each month, we know that it is Sunday:

day %= 7;
if (day == 0) count++; // if it is sunday

Combining all that:

int count = 0, day = 2; // modulus representation of days (modulo 7) : SMTWTFS == 0123456
  
for (int y = 1901; y <= 2000; y++) // years
{
    for (int m = 1; m <= 12; m++) // months
    {
        if (m == 4 || m == 6 || m == 9 || m == 11)
            day += 30;
        else if (m == 2)
        {
            if (isLeap(y)) day += 29;
            else day += 28;
        }
        else day += 31;
  
        day %= 7;
        if (day == 0) count++; // if it is sunday
    }
}
System.out.println(count);

Answer is 171
Execution time is .796564 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem019.java

Problem 18 : Maximum Path Sum I

Maximum path sum I

Problem 18

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

                                                                                                       (https://projecteuler.net/problem=18)

Problem 18 is awesome. It's simply amazing.

Personally, I found out dynamic programming while solving this problem, and it is one of the most powerful algorithms that I've ever learned.

As my brute force method took more than 5 minutes on the first attempt, the drastic improvement of efficiency down to 3 milli-second was astonishing advancement and was done solely by dynamic programming.

(Note that the solution will be same for Problem 67).

Anytime there is a large set of data, we are going to use read-file method to store the data.

private static int[][] triangle = read();

public static int[][] read()
{
    int[][] text = new int[15][];
    File file = new File(text018);
    try (BufferedReader br = new BufferedReader(new FileReader(file)))
    {
        String line;
        for (int i=0; (line = br.readLine()) != null; i++)
        {
            String[] temp = line.split(" ");
            text[i] = new int[i+1];
            for (int j=0; j <= i; j++)
                text[i][j] = Integer.parseInt(temp[j]);
        }
    }
    catch (IOException e)
    {
        System.err.println(e);
    }
    return text;
}

Instead of starting from the top and coming downward, I will start from the bottom and go upward.

Let's look at the bottom-left region, where a triplet of 63, 04, and 62 are located.

   63
04  62

I will call 63 the parent number and 04 and 62 the daughter numbers.

   63
04  62

We are going to modify our pyramid by adding the larger daughter number to the parent number.

   63
04  62

62 is greater than 04, so I will add the number to the top.

  125
04  62

If we do the same thing for the second pair, then:

   66
62  98

  164
62  98

We are going to do the same thing for all the pairs in the first floor, and then we will have the second floor with the greatest possible values of sums.

After finishing the second floor, then we will step up and select two pairs from the second floor and form the greatest possible values of sums in the third floor, and so on.

And because this is repetitive process, we can tell the program just once how to process the numbers, and after that computer will just follow through the logic until it reaches the last floor, or the top number, which will then become the largest possible sum of the adjacent numbers.

We call this dynamic programming.

Here is the implementation of the logic:

for (int i=triangle.length-1; i >= 1; i--)
{
    for (int j=0; j < i; j++)
    {
        triangle[i-1][j] += Math.max(triangle[i][j], triangle[i][j+1]);
    }
}

System.out.println(triangle[0][0]);

Answer is 1074
Execution time is 3.042578 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem018.java