Monday, April 19, 2010

ALL the B(e)ST...!!! ;-)

Hi pa!

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
--------------------

17 comments:

  1. import java.util.Calendar;
    import 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);

    ReplyDelete
  2. On a server running code we can cache the calculated last sunday dates in a Map for successive look up to increase performance.

    ReplyDelete
  3. 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;
    }

    }

    ReplyDelete
  4. Cheers Amod..! :)
    Great 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

    ReplyDelete
  5. Please go thru my version of the logic.
    I 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;
    }

    }

    ReplyDelete
  6. Thanks Raghu!! (Calvin)

    I 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 :))

    ReplyDelete
  7. This comment has been removed by the author.

    ReplyDelete
  8. Ok...let me share what I thought & wrote...

    I 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...! :)

    ReplyDelete
  9. My baby-program in case, u did NOT notice it in the above comment...! :)

    ReplyDelete
  10. i could not access the link of ur program. and also the second program is not by Amod .

    ReplyDelete
  11. Sorry...!

    I 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..!

    ReplyDelete
  12. Hi Raghu -

    My 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

    ReplyDelete
  13. Calvin (Raghu)

    That 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.

    ReplyDelete
  14. @Amod...

    Of-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..! :)

    ReplyDelete
  15. Thanks for pointing Amod.

    Here is probably the correct version.

    http://pastie.org/927492

    MMH

    ReplyDelete
  16. @Amod..!

    I 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! :)

    ReplyDelete
  17. I meant...

    http://pastie.org/927499

    ReplyDelete

Pleeze do give me YOUr (in)valuable feedback...!
Thanks a lot in deed.. :)