5

I am new to Programming, and to Java, and I'm trying to teach myself by working through the Project Euler website. I am trying to complete this problem: http://projecteuler.net/problem=19, which is:

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

The way I thought to solve it, was to make a 2D array that represents a calander, and to loop through the array by counting to 7, and then each time I count to 7, add 1 to that point in the array. At the end, I will sum the first row of the array, and that should be how many sundays were on the first of the month.

But I am having trouble with my loops, my counting to 7 resets when it gets to the end of a month, and I can't figure out how to stop it from doing that?

Here is my code:

public class Problem019 {
    public static void main (String[] args){

        //System.out.println(LeapYearTest(1996));
        int ThirtyOne = 31;
        int Thirty = 30;
        int FebNorm = 28;
        int FebLeap = 29;
        int a, b, c, Day, e = 0, f = 0;
        int Calander[] []= new int [12] [] ;

        Calander[0] = new int [ThirtyOne];
        Calander[1] = new int [FebNorm];
        Calander[2] = new int [ThirtyOne];
        Calander[3] = new int [Thirty];
        Calander[4] = new int [ThirtyOne];
        Calander[5] = new int [Thirty];
        Calander[6] = new int [ThirtyOne];
        Calander[7] = new int [ThirtyOne];
        Calander[8] = new int [Thirty];
        Calander[9] = new int [ThirtyOne];
        Calander[10] = new int [Thirty];
        Calander[11] = new int [ThirtyOne];

        for (a=1901;a<2001;a++){
            //System.out.println(a);
            if (LeapYearTest(a))
            {
                Calander[1] = new int [FebLeap];
            }
            else
            {
                Calander[1] = new int [FebNorm];
            }

            for (e=0;e<Calander.length;e++)
            {   
                System.out.println("e: " + e);
                f=0;

                while (f<Calander[e].length)
                {   

                    //System.out.println(Calander[e].length);
                    Day=1;
                    while (Day<8 && f<Calander[e].length)
                    {   
                        System.out.println("f: " + f + "\tDay: " + Day + "\tCalander[e][f]: " + Calander[e][f]);
                        Day++;
                        f++;

                        if (f<Calander[e].length && f!=0 && Day==7)
                        {
                        Calander[e][f]+= 1;
                        }

                    }

                }
            }
            //System.out.println(a);
        }
        for (b=0;b<Calander.length;b++)
        {   
            System.out.print(Calander[0][b]);
        }
    }   


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

}

This is what it prints, e is the month, f is the days in the month, and Day is counting to 7:

f: 25   Day: 5  Calander[e][f]: 0
f: 26   Day: 6  Calander[e][f]: 0
f: 27   Day: 7  Calander[e][f]: 100
f: 28   Day: 1  Calander[e][f]: 0
f: 29   Day: 2  Calander[e][f]: 0
**f: 30 Day: 3  Calander[e][f]: 0**
e: 10
**f: 0  Day: 1  Calander[e][f]: 0**
f: 1    Day: 2  Calander[e][f]: 0
f: 2    Day: 3  Calander[e][f]: 0

How can I set up the loops so that Day doesn't reset at the end of the month? Or is there another way to solve this problem that doesn't involve so many nested loops?

Thankyou!

4
  • 3
    All those arrays are overkill. You just need to iterate and increment the total number of Sun 1st. You iterate in parallel with a counter 0-6 and another that goes to the current month's number of days. Apr 29, 2012 at 7:50
  • 1
    Plus, there are more clever ways to compute the Sundays that fall on the first of the month besides looping over every day. Also--not that it matters if nobody else will see your code, but you misspelled Calendar, and Java coding conventions recommend using camelCase variable names (with the first letter lowercase).
    – rob
    Apr 29, 2012 at 8:14
  • @Marko: Sorry I don't understand, can you elaborate?
    – Keith
    Apr 29, 2012 at 8:22
  • Thank you to everyone that helped me, I really appreciate it!
    – Keith
    Apr 30, 2012 at 7:35

8 Answers 8

4

WOuldnt it be much quicker to have an outer loop that increments the year from 1901 to 2001, and an inner loop that checks Jan -> Dec, and then just see if the first of that month was a Sunday?

100 * 12 iterations in total,10 lines of code, tops.

Edit: To expand on this.

You can go about the problem in two ways - look at all the sundays and see if they're on the first of a month, or look at the first day of all the months and see if its a sunday.

Untested code:

Calendar calendar = Calendar.getInstance();
int count = 0;
for(int i=1901;i<2000;i++){
    for(int j=1;i<12;j++){
        calendar.set(Calendar.YEAR, i);
        calendar.set(Calendar.MONTH,j);
        calendar.set(Calendar.DAY,1);
        if(calendar.get(Calendar.DAY_OF_WEEK).equals(Calendar.SUNDAY)){
            count++;
        }
    }
}

System.out.println(count);

5
  • Sorry but I don't understand what you mean. What does the inner loop do exactly? How can I "just see if the first of that month was a Sunday"? Can you please explain in more detail? Cheers.
    – Keith
    Apr 29, 2012 at 8:17
  • @Keith: you can use Java's built-in Calendar API to compute the DayOfWeek...assuming that isn't considered cheating on Project Euler.
    – rob
    Apr 29, 2012 at 8:19
  • 1
    @rob: I would like to solve the question as a maths problem, so without using the Calender API. But I might try to solve it again with the Calender API just to learn how to use it. And I will google "camelCase" and correct Calander to Calender, thank you.
    – Keith
    Apr 29, 2012 at 8:27
  • @Keith: no problem; you can easily replace the Calendar API's functionality with your own implementation of the Doomsday Algorithm. See my answer for details.
    – rob
    Apr 29, 2012 at 9:23
  • 1
    This code will fail to go up to 31 Dec 2000 cause first for loop stop at 1999 with condition i < 2000
    – Nicocube
    Apr 29, 2012 at 12:07
3

I think you need to toss out your existing code and start fresh. Since you're trying to learn how to code by solving Project Euler problems, I won't ruin the fun for you by giving you the code. It seems you do want the full working code, so I've fixed your code, including a few bugs that were present due to some subtle details in the problem statement that you may have misunderstood or overlooked.

Just for fun, let's take a look at the immediate problem with your code that you want fixed...

When you initially declare Day, initialize it to 1. Then replace this line:

Day=1;

with this:

if (Day > 7) {
    Day = 1;
}

and move it inside of the loop that goes over the days of the month.

But there's still a serious problem. You keep overwriting your Feb array every year. You should only initialize it once, and set its length to 29. But this also has the unfortunate side effect of breaking any loops that depend on calendar[month].length, so you'll have to account for that, too.

All you really need to track are the number of Sundays that fell on the first of the month, so you just need to store and increment one variable. This solves the aforementioned problem with overwriting the Feb array, because you won't use it (or any other month's array) any more. On the other hand, if you really just want to practice using arrays, you could use a 3-dimensional array (in which the additional dimension is the year). But I'd venture to guess that most Java programmers use Lists instead of arrays most of the time, and when they do use arrays, they hardly ever use arrays with more than one dimension.

A few more notes

Your outer while loop is redundant.

Your LeapYearTest method will incorrectly return true for all leap years divisible by 100 (all years divisible by 100 are also divisible by 4, so you'll never enter the if block that tests years divisible by 100).

At the end, you're looping over every day of January (instead of looping over the first day of every month).

Also note that the problem states,

1 Jan 1900 was a Monday.

But you're supposed to find Sundays starting from 1 Jan 1901.

After fixing these and other bugs (such as the conditions in your loops), I've included a fully working version of your code below. Note that you could easily optimize this to run in a fraction of the time by making more use of the modulus (%) operator and by not computing the number of Sundays on other days of the month (since you throw them away anyway in the end).

public class Problem019 {
    public static void main (String[] args){

        final int ThirtyOne = 31;
        final int Thirty = 30;
        final int FebNorm = 28;
        final int FebLeap = 29;
        int numOfSundays = 0;

        int calendar[][]= new int [12][];

        calendar[0] = new int [ThirtyOne];
        calendar[1] = new int [FebLeap];
        calendar[2] = new int [ThirtyOne];
        calendar[3] = new int [Thirty];
        calendar[4] = new int [ThirtyOne];
        calendar[5] = new int [Thirty];
        calendar[6] = new int [ThirtyOne];
        calendar[7] = new int [ThirtyOne];
        calendar[8] = new int [Thirty];
        calendar[9] = new int [ThirtyOne];
        calendar[10] = new int [Thirty];
        calendar[11] = new int [ThirtyOne];

        int dayOfWeek = 1;
        for (int year = 1900; year < 2001; year++) {
            for (int month = 0; month < calendar.length; month++) {   
                int dayOfMonth=0;

                int daysInMonth;
                if (month == 1) {
                    daysInMonth = isLeapYear(year) ? FebLeap : FebNorm;
                }
                else {
                    daysInMonth = calendar[month].length;
                }

                while (dayOfWeek < 8 && dayOfMonth < daysInMonth) {   
                    System.out.println("year: " + year + "\tday: " + dayOfWeek
                            + "\tcalendar["+month+"]["+dayOfMonth+"]: " + calendar[month][dayOfMonth]);

                    if (dayOfWeek == 7 && year > 1900) {
                        calendar[month][dayOfMonth]++;

                        if (dayOfMonth == 0) {
                            numOfSundays++;
                        }
                    }

                    dayOfMonth++;

                    dayOfWeek++;
                    if (dayOfWeek > 7) {
                        dayOfWeek=1;
                    }
                }
            }
        }

        for (int month = 0; month < calendar.length; month++) {   
            System.out.println(calendar[month][0]);
        }

        System.out.println(numOfSundays);
    }   

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

Again, this could be improved upon quite a lot. For example, you could simply loop over the years and months, and use Java's built-in Calendar API or a third-party API, to check whether the first day of the month is a Sunday, but perhaps the coolest way to solve the problem is to implement the Doomsday Algorithm yourself. This will allow you to easily compute the day of the week for any given date, without using java.util.Calendar.

Once you have implemented the Doomsday Algorithm, you don't necessarily have to loop over all the months every time, so you could do even more optimizations. For instance, isSunday(MAR,1,year) == (! isLeapYear(year)) && isSunday(FEB,1,year).

4
  • Thanks, but I would still like to know how to loop through a staggered 2d array, by counting to 7, without resetting the count for each column?
    – Keith
    Apr 29, 2012 at 9:23
  • There are actually several problems in your code. I've updated my answer to point out some of the issues.
    – rob
    Apr 29, 2012 at 11:01
  • Thanks, I -sort of- understand. But when I use your code, it doesn't add 1 to the array if dayoftheMonth = 0. I changed the if statement to: if (dayOfMonth<calendar[month].length && day==7 && year>1900) { calendar[month][dayOfMonth]+= 1; }
    – Keith
    Apr 29, 2012 at 12:03
  • I've updated my answer with a working version. I added a numOfSundays variable to show that the arrays are not necessary.
    – rob
    Apr 30, 2012 at 0:09
1

Try this:

import java.util.Calendar;
public class Problem019 {   

    public static void main (String[] args){

        Calendar calendar = Calendar.getInstance();
        int countFirstSunday = 0;
        for(int year = 1901; year <= 2000 ; year++) {
            for(int month = 0; month <= 11; month++) {
                calendar.set(year, month, 1);
                if(calendar.get(Calendar.DAY_OF_WEEK) == Calendar.SUNDAY) {
                    countFirstSunday++;
                }
            }
        }
        System.out.println("Sundays as the first of month: " + countFirstSunday);
    }

}
1

Here is my proposition. It use Gregorian calendar to identify the date, and then if it's a Sunday.

import java.util.Date;
import java.util.GregorianCalendar;

public class SundayOfXX {

    public static void main(String [] argv) {
        int counter = 0;
        for (int year = 1901, last_year = 2000; year <= last_year ; year++) {
            for (int month = 1, last_month = 12; month <= last_month ; month++) {
                Date d = new GregorianCalendar(year,month-1,1).getTime(); // GregorianCalendar use 0 for January
                if (d.getDay() == 0) { // sunday is day number 0
                    counter++;
                    System.out.println(String.valueOf(counter) + " " + d);
                }
            }
        }
        System.out.println("Total sunday in XX century: "+counter);
    }
}

This solution is fully tested. It finds 171 sundays that are 1st day of a month in 20th century.

2
  • 171*7 = 1197 and 1197 is less than 4 years, so was 20th century only 4 years? Jul 18, 2013 at 13:23
  • Visibly you have not read the problem definition. It 171 sundays that are 1st of a month from 1901 to 2000. But I take your point, and I edited my post to be more explicit...
    – Nicocube
    Jul 18, 2013 at 14:20
0

This is your code cleaned up and simplified:

public static void main(String[] args) {
  final int thirtyOne = 31, thirty = 30;
  final int calendar[][] = new int[12][];
  final int[] febLeap = new int[29];
  final int[] febNorm = new int[28];
  calendar[0] = new int[thirtyOne];
  calendar[2] = new int[thirtyOne];
  calendar[3] = new int[thirty];
  calendar[4] = new int[thirtyOne];
  calendar[5] = new int[thirty];
  calendar[6] = new int[thirtyOne];
  calendar[7] = new int[thirtyOne];
  calendar[8] = new int[thirty];
  calendar[9] = new int[thirtyOne];
  calendar[10] = new int[thirty];
  calendar[11] = new int[thirtyOne];
  int dow = 0; // set to day of week for Jan 1 1901
  for (int y = 1901; y < 2001; y++) {
    calendar[1] = leapYearTest(y)? febLeap : febNorm;
    for (int m = 0; m < calendar.length; m++)
      for (int d = 0; d < calendar[m].length; d++)
        if (dow++ % 7 == 0) calendar[m][d]++;
  }
  int sumSundays = calendar[0][0] + febLeap[0] + febNorm[0];
  for (int i = 2; i < calendar.length; i++) sumSundays += calendar[i][0];
  System.out.println("Number of Sundays is " + sumSundays);
}

public static boolean leapYearTest(int x) {
  if (x % 4 == 0 || x % 400 == 0)
    return true;
  return x % 100 != 0;
}

Here's what I meant when I said you don't need arrays:

public static void main(String[] args) {
  final int[] mLens = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  int dow = 0; // initialize to day of week on Jan 1, 1901
  int suns = 0;
  for (int y = 1901; y < 2001; y++)
    for (int m = 0; m < mLens.length; m++) {
      if (dow++ % 7 == 0) suns++;
      final int mLen = mLens[m] + leapAdd(y, m);
      for (int d = 1; d < mLen; d++) dow++;
    }
  System.out.println(suns);
}

static int leapAdd(int y, int m) {
  if (m != 1) return 0;
  if (y % 4 == 0 || y % 400 == 0) return 1;
  return y % 100 == 0 ? 0 : 1;
}

But immediately you realize there's no sense in that inner loop running through days of month, when it's all just modulo 7. So the inner loop should say

    for (int m = 0; m < mLens.length; m++) {
      if (dow == 0) suns++;
      final int mLen = mLens[m] + leapAdd(y, m);
      dow = (dow + mLen) % 7;
    }
0

I'd do it like so (pseudocode):

class MyDate { ... } // support adding a number of days and comparing with another MyDate
MyDate end = new MyDate(31. Dec 2000)
MyDate start = new MyDate(first sunday in 20th century)
int count = start.mday == 1 ? 1 : 0;
start.add(7);
while (start < end) (
    if (start.mday == 1) count++;
    start.add(7);
}

Note that one doesn't need any arrays, much less 2d arrays. (To get the month length, however, in the add method of MyDate, using a simple constant array is ok.)

0

Here are 2 solutions:

1) Using Calendar - it is more simple, but it is not so efficient - 135 ms

import java.util.Calendar;

public class P19 {

    public static void main(String[] args) {
        int result = 0;
        for ( int year = 1901 ; year <= 2000 ; year++ ) {
            for ( int month = Calendar.JANUARY ; month <= Calendar.DECEMBER ; month++ ) {
                Calendar c = getCalendar(year, month, 1);
                if ( c.get(Calendar.DAY_OF_WEEK) == Calendar.SUNDAY ) {
                    result++;
                }
            }
        }
        System.out.println(result);
    }

    private static Calendar getCalendar(int year, int month, int day) {
        Calendar c = Calendar.getInstance();
        c.set(Calendar.YEAR, year);
        c.set(Calendar.MONTH, month);
        c.set(Calendar.DAY_OF_MONTH, day);      // or Calendar.DATE
        return c;
    }

}

Notice that:

  • DAY_OF_MONTH and DATE are equivalent.
  • I used Calendar.JANUARY because the first month is 0, not 1, even if the first day/date is 1.

2) Using my own Date class - it takes only 1.65 ms:

public class P19 {

    public static void main(String[] args) {
        // 1 Jan 1900 - Monday
        // 1900 is not leap => it has 365 days
        // 365 % 7 = 1 => 1 Jan 1901 - Tuesday => 6 Jan 1901 - Sunday

        int yearStart = 1901, yearEnd = 2000;
        int monthStart = 1, monthEnd = 12;
        int dayStart = 6, dayEnd = 31;
        Date dateStart = new Date(yearStart, monthStart, dayStart);
        Date dateStop = new Date(yearEnd, monthEnd, dayEnd);

        int result = 0;
        while (Date.compareDates(dateStart, dateStop) < 0) {
            if (dateStart.day == 1) {
                result++;
            }
            dateStart.addDays(7);
        }
        System.out.println(result);
    }

}

class Date {
    int year;
    int month;
    int day;

    Date(int year, int month, int day) {
        this.year = year;
        this.month = month;
        this.day = day;
    }

    public void addDays(int days) {
        int numberOfDaysForMonth = getTotalMonthDays(month, year);
        day += days;
        if (day >= numberOfDaysForMonth) {
            day -= numberOfDaysForMonth;
            month++;
            if (month > 12) {
                month = 1;
                year++;
            }
        }

    }

    public static int compareDates(Date d1, Date d2) {
        if (d1.year == d2.year && d1.month == d2.month && d1.day == d2.day) {
            return 0;
        }
        if (d1.year < d2.year) {
            return -1;
        }
        if (d1.year == d2.year && d1.month < d2.month) {
            return -1;
        }
        if (d1.year == d2.year && d1.month == d2.month && d1.day < d2.day) {
            return -1;
        }
        return 1;
    }

    private int getTotalMonthDays(int m, int y) {
        if (m == 2 && isLeapYear(y)) {
            return 29;
        }
        if (m == 2) {
            return 28;
        }
        if (m == 4 || m == 6 || m == 9 || m == 11) {
            return 30;
        }
        return 31;
    }

    private boolean isLeapYear(int y) {
        if (y % 4 == 0 && (y % 100 != 0 || y % 400 == 0)) {
            return true;
        }
        return false;
    }

}

This implementation iterates only through Sundays ( addDays(7) ).

Some possible improvements:

  • increase the step (E.g.: for 1, we can add 28 instead of 7 without skipping any day)
  • change the compare method to return a boolean and to simplify its body
0
public class CountingSundays {

    public static void main(String[] args) {

        int lastDayOfPreviousMonth = 6; //31 Dec 1899 is Sunday as 1 Jan 1900 is Monday

        int countOfSundayOnFirstOfMonth = 0;

        for (int year = 1900; year <= 2000; year++) {
            for (int month = 1; month <= 12; month++) {
                int dayOnFirstOfThisMonth = (lastDayOfPreviousMonth + 1) % 7;
                if (year > 1900 && dayOnFirstOfThisMonth == 6)
                    countOfSundayOnFirstOfMonth++;
                switch (month) {
                case 1: // Jan
                case 3: // Mar
                case 5: // May
                case 7: // Jul
                case 8: // Aug
                case 10: // Oct
                case 12: // Dec
                    lastDayOfPreviousMonth = (lastDayOfPreviousMonth + 3) % 7;
                    break;
                case 4: // Apr
                case 6: // Jun
                case 9: // Sep
                case 11: // Nov
                    lastDayOfPreviousMonth = (lastDayOfPreviousMonth + 2) % 7;
                    break;
                case 2: // Feb
                    if (year % 4 == 0 && (year % 100 != 0 || year % 400 == 0))
                        lastDayOfPreviousMonth = (lastDayOfPreviousMonth + 1) % 7;
                }
            }
        }


        System.out.println(countOfSundayOnFirstOfMonth);
    }

}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.