I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: The All Knowing Calendar

06.07.2012
| 4692 views |
  • submit to reddit

By now you should be familiar with our Thursday Code Puzzler slot. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you think is suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

How Many Sundays Fell on the 1st?

Given the following information, calculate how many Sundays fell on the first of the month during the twentieth century: 

  • 1 January 1900 was a Monday 
  • A leap year occurs any year that is divisible by 4, but not on a century unless divisible by 400
  • "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."

 Try and make your answer as efficient as possible!

Comments

Vijay Nathani replied on Thu, 2012/06/07 - 12:53am

Solution in Groovy (using open source library Joda Time) prints answer 172.

import org.joda.time.*
def start = new DateMidnight(1900,1,1)
def end = start.plusYears(100)
int answer = 0
for (def d = start; d < end; d=d.plusMonths(1)) 
	if (d.dayOfWeek().get() == DateTimeConstants.SUNDAY) 
		answer++
println "${answer} Sundays occur on 1st of a month in 20th century"

 

Jarek Acyrf replied on Thu, 2012/06/07 - 2:07am in response to: Vijay Nathani

Nice solution. It is short and nice, but it has 3 little issues. 1. It doesnt use the 3 "knowledge points" presented in the puzzle. 2. It is not efficent which IMO was the most important. 3. The result is probably wrong... I don't have time now to present my solution. I'll try to get some time soon.

Vijay Nathani replied on Thu, 2012/06/07 - 3:04am in response to: Jarek Acyrf

1. The knowledge points are probably used in the date time library used. New code should be written only if no one has written code (for the same task) earlier.

2. Please give me a more efficient code. Let us see the difference in performance.

3. Prove the answer wrong, before calling it wrong.

Chirag Visavadia replied on Thu, 2012/06/07 - 4:11am

package org.test.SundayOnFirst;

import java.text.DateFormatSymbols;
import java.util.Calendar;

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

		int startYear = 1901;
		int endYear = 2000;
		int totalSundayFound = 0;

		/**
		 * Gets weekday strings. For example: "Sunday", "Monday", etc.
		 */
		String[] weekdays = new DateFormatSymbols().getWeekdays();

		for (; startYear <= endYear; startYear++) {

			for (int i = 0; i < 12; i++) {

				Calendar calendar = Calendar.getInstance();
				calendar.set(startYear, i, 1);

				if (weekdays[calendar.get(Calendar.DAY_OF_WEEK)].equalsIgnoreCase("sunday")) {
					System.out.println(calendar.getTime());
					totalSundayFound++;
				}
			}
		}

		System.out.println("Total Sundays Fell on the 1st: " + totalSundayFound);
	}
}

Vijay Nathani replied on Thu, 2012/06/07 - 5:30am in response to: Chirag Visavadia

Your code prints answer 171. My code prints answer 172.

You have not considered year 1900 (Jan 1900 to Dec 1900) to be in 20th century. I have considered these 12 months in 20th century.

You have considered year 2000 (Jan 2000 to Dec 2000) to be in 20th century. I have considered these 12 months NOT in 20th century.

 

If I change your line number 09 to "int startYear = 1900"

and your line number 18 to "for (; startYear < endYear; startYear++) {"

then your code gives the same answer as mine i.e. 172.

 

 

 

 

 

 

Jarek Acyrf replied on Thu, 2012/06/07 - 6:18am in response to: Vijay Nathani

Vijay, he has just shown you why your result was wrong. His solution has only first two issues I mentioned. At least the result is right.

Vijay Nathani replied on Thu, 2012/06/07 - 6:41am in response to: Jarek Acyrf

Is Jan 1900 in 19th or 20th century?

Is Jan 2000 in 20th or 21st century?

 

Neven Cvetkovic replied on Thu, 2012/06/07 - 8:01am in response to: Vijay Nathani

http://en.wikipedia.org/wiki/20th_century

The 20th century is defined as the time period running from January 1, 1901 to December 31, 2000.

Jonathan Dixon replied on Thu, 2012/06/07 - 8:09am

Here is a solution in Java, not using any date libraries. This results in 171 if we use the wikipedia defined 20th century. This solution could probably be optimized some more.

public class Sunday {
  public static void main(String args[]) {
    int startYear = 1901;
    int numYears = 100;
    int currentDay = 2; // Sunday = 0, Saturday = 6;

    int[] monthDays = {31,28,31,30,31,30,31,31,30,31,30,31};

    int count = 0;
    int month = 0;
    int year = startYear;
    boolean leapYear = false;
    while(year < startYear + numYears) {
      currentDay = (currentDay + monthDays[month] + ((leapYear && month==1) ? 1 : 0)) % 7;
      if (currentDay == 0)
        count++;
      if (++month >= 12) {
        month = 0;
        leapYear = ++year % 4 == 0;
      }
    }
    System.out.println(count);
  }
}

Vijay Nathani replied on Thu, 2012/06/07 - 10:47am

Here is one more solution in Groovy, to correct my previous mistake of start/end year in century and using Dixon's Java solution,  that prints 171.

def (START_YEAR, END_YEAR) = [1901, 2000]
def (LEAP_YEAR_INTERVAL, DAYS_IN_WEEK) = [4, 7]
def DAYS_IN_MONTH = [31,28,31,30,31,30,31,31,30,31,30,31]
def (currentDay, count) = [2, 0] // currentDay: Sunday=0, Saturday=6
for (int year = START_YEAR;  year <= END_YEAR; year++) 
	for (int month=0; month <= DAYS_IN_MONTH.size() - 1; month++) {
		int adjustForLeap = (month == 1 && year % LEAP_YEAR_INTERVAL == 0)? 1 : 0
		currentDay = (currentDay + DAYS_IN_MONTH[month] + adjustForLeap ) % DAYS_IN_WEEK
		count += currentDay? 0 : 1
	}
println "${count}"

 

 

Robert Stern replied on Thu, 2012/06/07 - 10:34am

Death to readibility!!!

 

int dayOfWeek = 1;
int sundays = 0;
int[] monthMax = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
for (int year = 1901; year < 2001; year++)
    for (int month = 0; month < 12; month++) {
        sundays = sundays + (dayOfWeek == 6 ? 1 : 0);
        dayOfWeek = (dayOfWeek + monthMax[month] + (year % 4 == 0 && year % 100 != 0 && month == 1 ? 1 : 0) % 7) % 7;
    }
System.out.println(sundays);

 

Earnest Dyke replied on Thu, 2012/06/07 - 10:53am

I believe this satisfies the requirements, does not use any special classes and calculates the correct result.

 

Earnie!

import org.junit.Test;

public class FirstOfTheMonthSundays {

	@Test
	public void countFirstOfTheMonthSundays() {
		boolean leap = false;
		int cnt = 0; // Number of Sundays that fall on the first of the month
		int d = 2; // Day of the week for 1/1/1900 (0-6)
		/*
		 * Number of days the first of the month changes between months
		 */
		int[] md = { 3, 0, 3, 2, 3, 2, 3, 3, 2, 3, 2, 3 }; 
		for (int y = 1901; y <= 2000; y++) { // Wikipedia definition of 20th Century
			/*
			 * Leap year if divisible by 4 or divisible by 400 if century
			 */
			leap = (y % 100 > 0 && y % 4 == 0)
					|| (y % 100 == 0 && y % 400 == 0) ? true : false;
			md[1] = leap ? 1 : 0; // account for leap year
			for (int m = 0; m < 12; m++) {
				d = d > 6 ? d - 7 : d;
				if (d == 0) {
					cnt++;
				}
				d += md[m];
			}
		}
		System.out.println(cnt);
	}

Jarek Acyrf replied on Thu, 2012/06/07 - 11:59am

Well... Precalculation that 1 Jan 1901 is Tuesday is kind of cheating. If you allow it then I can go step farther and count the Sundays much faster:

<code>

public class Calendator {
    
    static final int MONDAY=0,TUESDAY=1,WEDNESDAY=2,THURSDAY=3,FRIDAY=4,SATURDAY=5,SUNDAY=6;

    final static int YEAR_START=1901;
    final static int YEAR_END=2000;
    final static int DAY_START=TUESDAY;

    final static int yearDayIncrement=1;
    final static int yearDayIncrementLeap=2;
    final static int[] weekDaysOn1stOfMonth={2, 1, 1, 3, 1, 2, 2};
    final static int[] weekDaysOn1stOfMonthLeap={3, 1, 1, 2, 2, 1, 2};
    
    static public void main(String[] params){
        int theDOW=SUNDAY;
        int dowCount = countDayOfWeek1stInMonth(YEAR_START, DAY_START, YEAR_END, theDOW);
        System.out.println(dowCount);
    }

    private static int countDayOfWeek1stInMonth(int yearStart, int dayStart, int yearEnd, int theDOW) {
        int dowCount=0;
        int currentDOW=dayStart;
        for (int year=yearStart;year<=yearEnd;year++){
            dowCount+=day1stInMonthInYear(theDOW, year, currentDOW);
            int inc=((isLeapYear(year))?yearDayIncrementLeap:yearDayIncrement);
            currentDOW=(currentDOW+inc)%7;
        }
        return dowCount;
    }

    private static int day1stInMonthInYear(int day,int year,int dayStartingYear){
        int diff = day-dayStartingYear;
        if (diff<0)
            diff+=7;
        if (isLeapYear(year))
            return weekDaysOn1stOfMonthLeap[diff];
        else
            return weekDaysOn1stOfMonth[diff];
    }

    final static boolean isLeapYear(int year){
        if ((year&3)!=0)//faster check if dividable by 4
            return false;
        if(year%400==0)
            return true;
        if(year%100==0)
            return false;
        return true;
    }
}

</code>

The methods are static so JVM should inline them. I've got version without any cheating, but it is longer - about 100lines.

Weston Koberstein replied on Thu, 2012/06/07 - 11:56am

Here is another solution that solves the problem. 

public class Sunday {
//given the first day of the year how many Sundays start a month.
static int[] numOfSundayInNonLeapYear = { 2, 2, 2, 1, 3, 1, 1 };
static int[] numOfSundayInLeapYear = { 3, 2, 1, 2, 2, 1, 1 };

public static void main(String args[]) {

int startYear = 1901;
int numYears = 100;
int count = 0;
int currentDay = 2;
for (int year = startYear; year < startYear + numYears; year++) {

boolean isLeapYear = (year % 100 > 0 && year % 4 == 0)
|| (year % 100 == 0 && year % 400 == 0);

if( isLeapYear ){
count += numOfSundayInLeapYear[currentDay];
} else {
count += numOfSundayInNonLeapYear[currentDay];
}

//since 366%7 = 2 we can just add two days for leap year and one for non leap years
currentDay = (currentDay + (isLeapYear?2:1)) % 7;
}
System.out.println(count);
}
}

 

Weston Koberstein replied on Thu, 2012/06/07 - 12:00pm in response to: Weston Koberstein

oops beaten to the solution a previous poster

Jarek Acyrf replied on Thu, 2012/06/07 - 2:26pm

We can still be a bit faster if we realize that every 28 years any week day falls first in a month exactly 48 times while a starting weekday doesn't change. Exept for 28 years period in which there is a year that is dividable by 4 and is not a leap year (1900,2100,2200,2300,2500 etc.). So we can still optimize:

 

public class Calendator {

    static final int MONDAY=0,TUESDAY=1,WEDNESDAY=2,THURSDAY=3,FRIDAY=4,SATURDAY=5,SUNDAY=6;

    final static int YEAR_START=1901;
    final static int YEAR_END=2000;
    final static int DAY_START=TUESDAY;

    final static int yearDayIncrement=1;
    final static int yearDayIncrementLeap=2;
    final static int[] weekDaysOn1stOfMonth={2, 1, 1, 3, 1, 2, 2};
    final static int[] weekDaysOn1stOfMonthLeap={3, 1, 1, 2, 2, 1, 2};

    static public void main(String[] params){
        int theDOW=SUNDAY;
        int dowCount = countDayOfWeek1stInMonth(YEAR_START, DAY_START, YEAR_END, theDOW);
        System.out.println(dowCount);
    }

    private static int countDayOfWeek1stInMonth(int yearStart, int dayStart, int yearEnd, int theDOW) {
        int dowCount=0;
        int currentDOW=dayStart;

        int year=yearStart;
        while (year<=yearEnd){
            if (isNext28Ordinary(year)&&((yearEnd-year)>27)){
                year+=28;
                dowCount+=48;
                continue;
            }
            else
            {
                int lastYear=((year+99)/100)*100;
                if (yearEnd<lastYear)
                    lastYear=yearEnd;
                for (;year<=lastYear;year++){//goes until year XX01 or until endYear reached passed
                    dowCount+=day1stInMonthInYear(theDOW, year, currentDOW);
                    int inc=((isLeapYear(year))?yearDayIncrementLeap:yearDayIncrement);
                    currentDOW=(currentDOW+inc)%7;
                }
            }
        }
        return dowCount;
    }

    private static boolean isNext28Ordinary(int year){
        if (((year-1)%100)<72)
            return true;
        int cent=(year+28)/100;
        return ((cent&3)==0);


    }
    private static int day1stInMonthInYear(int day,int year,int dayStartingYear){
        int diff = day-dayStartingYear;
        if (diff<0)
            diff+=7;
        if (isLeapYear(year))
            return weekDaysOn1stOfMonthLeap[diff];
        else
            return weekDaysOn1stOfMonth[diff];
    }

    final static boolean isLeapYear(int year){
        if ((year&3)!=0)//faster check if dividable by 4
            return false;
        if(year%400==0)
            return true;
        if(year%100==0)
            return false;
        return true;
    }
}
 

Zheng Dan replied on Fri, 2012/06/08 - 1:50am


#!/usr/bin/python #
# -*- coding: utf-8 -*-
from datetime import *
print sum([1 if date(i,j,1).isoweekday() == 7 else 0 for i in range(1901,2001) for j in range(1,13)])

T SnowWolf Wagner replied on Fri, 2012/06/08 - 7:03am in response to: Chirag Visavadia

Not bad but a few changes that make it more effecent.

 

  • There is no need to use the DateFormatSymbols. Calander has a SUNDAY constant.  
  • Always use GregorianCalendar to get correct math. 
  • You only need to get the calendar once as it is mutable.  

 

import java.util.Calendar;
import java.util.GregorianCalendar;

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

        int startYear = 1901;
        int endYear = 2000;
        int totalSundayFound = 0;
        Calendar calendar = GregorianCalendar.getInstance();

        for (; startYear <= endYear; startYear++) {
            for (int i = 0; i <= Calendar.DECEMBER; i++) {
                calendar.set(startYear, i, 1);
                if (calendar.get(Calendar.DAY_OF_WEEK) == Calendar.SUNDAY) {
                    System.out.println(calendar.getTime());
                    totalSundayFound++;
                }
            }
        }

        System.out.println("Total Sundays Fell on the 1st: " + totalSundayFound);
    }

 

 

Kamala D'africa replied on Wed, 2012/06/20 - 12:15pm

My solution is very similar to others above

public static final int[] MONTH_DAYS = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

public static void main(String[] args) {
	int count = 0;
	int daysFrom1stJan1900 = 365;
	for (int year = 1901; year < 2001; year++) {
		for (int month = 0; month < 12; month++) {
			daysFrom1stJan1900 += MONTH_DAYS[month];
			if ((month == 1) && isLeapYear(year)) {
				daysFrom1stJan1900 += 1;
			}
			if (daysFrom1stJan1900 % 7 == 6) {
				count++;
			}
		}
	}
	System.out.println(count);
}

public static boolean isLeapYear(int y) {
	return (y % 4 == 0) && (y % 100 != 0 || y % 400 == 0);
}

 

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.