Hi pa!
This weekend, my dear friend & mentor Manju Hanasi, who's another constant source of inspiration & ideas, shared an interesting problem with me.
This weekend, my dear friend & mentor Manju Hanasi, who's another constant source of inspiration & ideas, shared an interesting problem with me.
We thought we should share it with YOU too, so that we can get more & more interesting solutions for it.
The problem, he said, is to come up with a very efficient & fast piece of code to determine if a given DATE is in BST(British Summer Time).
Definition: For simplicity, we can assume that BST is a period between the LAST Sunday of March and the LAST Sunday of October.
One very helpful thing: It's ok if the year is in the range say, 1900 till say, 2100.
And the catch, is to do it without relying on any language-dependent API's or libraries
(
E.g., we have utility classes/packages called TimeZone which takes care of handling such stuff in
and so on...
)
But what we need is to know if it is possible to write a simple function with the following kind of signature:
boolean isInBST(Date date) ;
or simpler...
boolean isInBST(int day, int month, int year);
The function has to be as fast & efficient as possible.
So, WHAT are YOU Waiting for....??
Please try n send in your versions of this function in ANY programming language of your choice...!!!
Believe me...it'll be FUN..!! :)
Do NOT be biased or daunted by ANYthing..ANY doubts...JUST Let GO...& Let me know..! :)
It's ok even if you share your idea...pseudo-code...comments, suggestions, anything...! :)
So...me WAITING...fer your answer(s)...k ??? :)
Come ON..!!
Jusst give it a try...!! :)
It's truly a beautiful( & such a Different!) experience to ASK ( & be ASKED) Questions to WHICH the ASKER too does NOT know "the" ANSWER(s)..!! :)
That, makes it into an exchange of IDEAs...rather than of Ignorance masking as Knowledge..! :)
Hmmmmmm..! :)
Take care then, & Keep L(i/o)ving...! :)
Love & Cheers..!
The boy in rags
Planet E-art-h
--------------------
Computers are useless; they can only give you answers.
Pablo Picasso
--------------------
import java.util.Calendar;
ReplyDeleteimport java.util.Date;
public class AllTheBest {
public boolean isInBST(Date date) {
System.out.println("Input Date -> "+date);
boolean isInBST = false;
Calendar cal = Calendar.getInstance();
cal.clear();
cal.setTime(date);
Calendar lsmCal = Calendar.getInstance();
lsmCal.clear();
lsmCal.set(cal.get(Calendar.YEAR), Calendar.MARCH, 1);
lsmCal.set(Calendar.DAY_OF_WEEK_IN_MONTH, -1);
lsmCal.set(Calendar.DAY_OF_WEEK, Calendar.SUNDAY);
final Date L_S_M = lsmCal.getTime();
System.out.println("Last Sunday of March -> "+L_S_M);
Calendar lsoCal = Calendar.getInstance();
lsoCal.clear();
lsoCal.set(cal.get(Calendar.YEAR), Calendar.OCTOBER, 1, cal.getMaximum(Calendar.HOUR_OF_DAY), cal.getMaximum(Calendar.MINUTE), cal.getMaximum(Calendar.SECOND));
lsoCal.set(Calendar.DAY_OF_WEEK_IN_MONTH, -1);
lsoCal.set(Calendar.DAY_OF_WEEK, Calendar.SUNDAY);
final Date L_S_O = lsoCal.getTime();
System.out.println("Last Sunday of October -> "+L_S_O);
isInBST = date.after(L_S_M) && date.before(L_S_O);
return isInBST;
}
}
The below lines are the trick to find the last Sunday of a Month
lsoCal.set(Calendar.DAY_OF_WEEK_IN_MONTH, -1);
lsoCal.set(Calendar.DAY_OF_WEEK, Calendar.SUNDAY);
On a server running code we can cache the calculated last sunday dates in a Map for successive look up to increase performance.
ReplyDeleteimport java.sql.Date;
ReplyDeleteimport java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Calendar;
import java.util.Locale;
import java.util.TimeZone;
public class CheckDateInBST {
/**
* @param args
*/
public static void main(String[] args) {
String date = args[0];
Date testDate = null;
try {
testDate = parseDate(date);
} catch (ParseException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Date lastSundayOfMarch = getLastSundayInMonth("MAR",
getYear(testDate));
Date lastSundayOfOctober =
getLastSundayInMonth("OCT",
getYear(testDate));
System.out.println(lastSundayOfMarch);
System.out.println(lastSundayOfOctober);
boolean dateInBST =
lastSundayOfMarch.compareTo(testDate) <= 0 &&
lastSundayOfOctober.compareTo(testDate) > 0;
System.out.println(dateInBST);
}
private static Date getLastSundayInMonth(String
month,int year)
{
int no_of_days_in_week = 7;
String yearStr = String.valueOf(year);
String dateStr = "01/" + month + "/" + yearStr;
Date firstDateInMonth= null;
try {
firstDateInMonth = parseDate(dateStr);
} catch (ParseException e) {
e.printStackTrace();
}
int dayOfWeek = getDayOfWeek(firstDateInMonth);
int daysToAddToAdjustToFirstSunday =
(no_of_days_in_week - dayOfWeek + 1) %
no_of_days_in_week;
int noOfWeeksToAdd = 0;
if(daysToAddToAdjustToFirstSunday > 1)
noOfWeeksToAdd = 3;
else
noOfWeeksToAdd = 4;
int daysToAddToLastSundayOfMonth =
daysToAddToAdjustToFirstSunday +
(no_of_days_in_week * noOfWeeksToAdd);
Date lastSundayOfMonth = addDays(firstDateInMonth,
daysToAddToLastSundayOfMonth );
return lastSundayOfMonth;
}
public static Date parseDate(String date) throws ParseException {
return new Date(new SimpleDateFormat("dd/MMM/yyyy").parse(date).getTime());
}
public static int getYear(Date date)
{
Calendar calendar = getCalendar(date.getTime());
return calendar.get(Calendar.YEAR);
}
public static int getDayOfWeek(Date date) {
Calendar calendar = getCalendar(date.getTime());
return calendar.get(Calendar.DAY_OF_WEEK);
}
public static Date addDays(Date date, int numberOfDays) {
if (date != null) {
Calendar calendar = getCalendar(date.getTime());
calendar.add(Calendar.DATE, numberOfDays);
return new Date(calendar.getTimeInMillis());
}
return null;
}
private static Calendar getCalendar(long timeInMillis) {
Calendar calendar = Calendar.getInstance(TimeZone.getDefault(), Locale.getDefault());
calendar.setTimeInMillis(timeInMillis);
return calendar;
}
}
Cheers Amod..! :)
ReplyDeleteGreat to see you respond so quickly...! :)
But, as I had mentioned, we should not assume that we have any classes like TimeZone (or for example JODA library of Java for Date-time calculations! ).
It should be a raw algorithm, where we do ALL the work ourselves...!!
[ :(....but if it can be done well... :) ]
Don't worry...I'm NOT trying to hide some secret discovery & asking you friends to come up with the SAME answer---I too don't know the answer..!! And I too will publish my version soon..!
Also, if you want to share your code with syntax-highlighting, etc., I recommend a Ruby-on-Rails-based site...
http://pastie.org
Please go thru my version of the logic.
ReplyDeleteI sent it yesterday but don know if it reached u .Hence sending it again.
Please feel free to comment here on ur feedback...
import java.sql.Date;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Calendar;
import java.util.Locale;
import java.util.TimeZone;
public class CheckDateInBST {
/**
* @param args
*/
public static void main(String[] args) {
String date = args[0];
Date testDate = null;
try {
testDate = parseDate(date);
} catch (ParseException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Date lastSundayOfMarch = getLastSundayInMonth("MAR", getYear(testDate));
Date lastSundayOfOctober = getLastSundayInMonth("OCT", getYear(testDate));
System.out.println(lastSundayOfMarch);
System.out.println(lastSundayOfOctober);
boolean dateInBST = lastSundayOfMarch.compareTo(testDate) <= 0
&& lastSundayOfOctober.compareTo(testDate) > 0;
System.out.println(dateInBST);
}
private static Date getLastSundayInMonth(String month, int year) {
int no_of_days_in_week = 7;
String yearStr = String.valueOf(year);
String dateStr = "01/" + month + "/" + yearStr;
Date firstDateInMonth = null;
try {
firstDateInMonth = parseDate(dateStr);
} catch (ParseException e) {
e.printStackTrace();
}
int dayOfWeek = getDayOfWeek(firstDateInMonth);
int daysToAddToAdjustToFirstSunday = (no_of_days_in_week - dayOfWeek + 1) % no_of_days_in_week;
int noOfWeeksToAdd = 0;
if (daysToAddToAdjustToFirstSunday > 1)
noOfWeeksToAdd = 3;
else
noOfWeeksToAdd = 4;
int daysToAddToLastSundayOfMonth = daysToAddToAdjustToFirstSunday
+ (no_of_days_in_week * noOfWeeksToAdd);
Date lastSundayOfMonth = addDays(firstDateInMonth, daysToAddToLastSundayOfMonth);
return lastSundayOfMonth;
}
public static Date parseDate(String date) throws ParseException {
return new Date(new SimpleDateFormat("dd/MMM/yyyy").parse(date).getTime());
}
public static int getYear(Date date) {
Calendar calendar = getCalendar(date.getTime());
return calendar.get(Calendar.YEAR);
}
public static int getDayOfWeek(Date date) {
Calendar calendar = getCalendar(date.getTime());
return calendar.get(Calendar.DAY_OF_WEEK);
}
public static Date addDays(Date date, int numberOfDays) {
if (date != null) {
Calendar calendar = getCalendar(date.getTime());
calendar.add(Calendar.DATE, numberOfDays);
return new Date(calendar.getTimeInMillis());
}
return null;
}
private static Calendar getCalendar(long timeInMillis) {
Calendar calendar = Calendar.getInstance(TimeZone.getDefault(), Locale.getDefault());
calendar.setTimeInMillis(timeInMillis);
return calendar;
}
}
Thanks Raghu!! (Calvin)
ReplyDeleteI am not sure which part of my code is Timezone specific. Did you mean that we should not even use java.util.Calendar?
In that case I need to assume a reference to calculate Day for a Date. I can assume epoch (Thrusday, 1st Jan 1970). But it will be like writing the Calendar class functionality (may be I will copy some code :))
This comment has been removed by the author.
ReplyDeleteOk...let me share what I thought & wrote...
ReplyDeleteI felt that if it is ALREADY known that we have to do it ONLY for say [1900,2100], then, why NOT convert the problem into one involving a super-fast LOOK-up..? :P
Check it out for yourself & let me know your opinions...
Don't you think this will be FAST & efficient as well..?? I don't know...I just felt so..! And I Loved the Simplicity of the code more than anything else... :)
Here's my baby :-
http://pastie.org/926371
But there may be FAR more better & innovative ways of doing the SAME...So PLEASE do give it a try...! :)
My baby-program in case, u did NOT notice it in the above comment...! :)
ReplyDeletei could not access the link of ur program. and also the second program is not by Amod .
ReplyDeleteSorry...!
ReplyDeleteI had thought the second program was also by Amod...
(Will Try & put ALL of them in one place & share...PLEASE do give me Your NAME & any other details (website, blog-link, etc..
Will be glad to publish it..! :))
You'll know later why that strange requirement..
But as of now, we require ourselves to come up with an efficient, stand-alone algorithm/code that can be implemented in ANY language easily...(that can't be done if say we use say the JODA Date-time Java library & someone else uses PHP's facilities..! :))
Perhaps, there could be a pattern lurking somewhere too..!
Also, please know that we need to make it work for only the years in the (closed) interval [1900,2100]---that will surely help us optimize further, & come up with clever ways..! :)
But KudoS to YOU people fer churning out 2 programs in quick succession..! :)
Also, pls give http://pastie.org a try for your code..i'm sure you'll love it...! :)
Cheers..!
Hi Raghu -
ReplyDeleteMy version at http://teckticks.blogspot.com/2010/04/fast-algorithm-to-find-whether-date-is.html
Unfortunately, I couldn't format it properly; was in a hurry to post the blog.
Btw, pastie.org doesn't seem to work. I tried several times, it doesn't seem to respond.
MMH
Calvin (Raghu)
ReplyDeleteThat is a good approach. I guess it has some issues though. Try int dd = 23, mm = 3, yy = 2010;
MMH (Manju)
Your approach is also good. But your code does not seem to be complete (should be a paste mistake). Please check.
Thanks for sharing. To me, if we can formulate a lookup table and do the calculation , with no errors, it will be the quicker solution.
Anonymous - http://pastie.org is very good and Raghu code is accessible there. Raghu thanks for sharing this info.
@Amod...
ReplyDeleteOf-course my code WOULD have issues for yy=2010..
WHY?
Simply because, my code, as-it-is is meant to work ONLY fer {1900, 1901, 1902} ---just the set of these 3 years! :)
ALL we need to is, populate the look-up table with "Enough" elements...esp fer the year 2010 ( which would be the 111'th element..! ) with the date of the last Sunday of March & that for October as well.
Theoretically, if we have a Big-enough look-up table, it will work smoothly without Any hassles...right from 0 A.D.... irrespective of the HUGE gaping holes in say, 1752 ..!! :)
[OFFSET would be 0 in that case...]
[In Linux/Unix, try "cal 1752" & observe September...! :)]
@Manju--Beautiful gem...doesn't require any look-up ( except the 1st one...reference...from there, you have so beautifully deduced a pattern...! )...CHEERS fer that..! :)
@Friends---pls give it a try...& enjoy..! :)
Thanks for pointing Amod.
ReplyDeleteHere is probably the correct version.
http://pastie.org/927492
MMH
@Amod..!
ReplyDeleteI tried looking at my code...& at line-66...the operator should be && rather than || :)))
For quick checking, we can just change the OFFSET to 2010 & have 1 element arrays for startDay & endDay...! :)
THANK you soo much..! :)
LINK to my updated code! :)
I meant...
ReplyDeletehttp://pastie.org/927499