Challenge

[jonnin]

for absolutely constant time I think you need to have a sum of 0 or value for each term you use; you can't skip an addition anywhere, eg the switch idea is slick but it can skip some terms which will vary the work done. This isnt the same as big-O constant time. True constant time is an unusual requirement, some (probably ancient) embedded systems use this to ensure code takes exactly the same time every iteration.

[helios]

Interesting take from lastchance, although somewhat inelegant for my taste. Duthomhas found the same solution I did for days_in_month(), although we chose to subtract different values from the array, and he didn't realize he could use the array for both functions.

const char month_days[] = { 0, 3, 3, 6, 8, 11, 13, 16, 19, 21, 24, 26, 29, };

int is_leap_year(int y){
    return y % 4 == 0 && (y % 100 != 0 || y % 400 == 0);
}

int days_in_month(int year, int month){
    if (month == 2)
        return 28 + is_leap_year(year);
    return 28 + month_days[month] - month_days[month - 1];
}

int days_since_january_first(int year, int month, int day){
    month--;
    return month * 28 + month_days[month] +
        is_leap_year(year) * (month > 1) +
        day - 1;
    return ret;
}

True constant time is an unusual requirement

Of course, the point was to avoid trivial looping solutions that anyone can come up with in five minutes.

[jonnin]

no, your didn't ask for what I was saying (same # of cpu clocks no matter what). You were asking for O(1) (not the same thing). I got the point, its a good exercise. I was adding an additional criteria, or at least mentioning it as something to think about.

[helios]

Well, I've never seen exact clock count as a requirement, but I do know that constant time in the sense I used here (how long the function took tells you preferably nothing about the input) is a desirable feature in secure communication protocols. If a system uses algorithms that take shorter branches when given certain inputs, an attacker can gain information about the internal state of the system by measuring it how long the system takes to respond to specific requests.

https://en.wikipedia.org/wiki/Timing_attack

[lastchance]

No array!

#include <iostream>
#include <algorithm>
using namespace std;

int zeroth( int month )
{
    return (int)( 30 * ( month - 1 ) + 0.601 * max( month - 4.0, 0.0 ) + ( month == 2 ) - (month == 3 ) );
}

bool is_leap( int year )
{
   return (bool)( !(year % 4) - !( year % 100) + !( year % 400 ) );
}


int days_in_month( int year, int month )
{
   return zeroth(month+1) - zeroth(month) + is_leap( year ) * ( month == 2 );
}


int days_since_january_first( int year, int month, int day )
{
   return zeroth( month ) + day - 1 + is_leap( year ) * ( month > 2 );
}


int main()
{
   for ( int month = 1; month <= 12; month++ ) cout << month << "  " << days_in_month( 2019, month ) << '\n';
   for ( int month = 1; month <= 12; month++ ) cout << month << "  " << days_in_month( 2020, month ) << '\n';
   for ( int month = 1; month <= 12; month++ ) cout << month << "  " << days_in_month( 1900, month ) << '\n';
   for ( int month = 1; month <= 12; month++ ) cout << month << "  " << days_in_month( 2000, month ) << '\n';
// for ( int year = 1859; year <= 2019; year++ ) cout << year << " " << is_leap( year ) << '\n';
// for ( int month = 1; month <= 12; month++ ) cout << month << "  " << days_since_january_first( 2019, month, 1 ) << '\n';
// for ( int month = 1; month <= 12; month++ ) cout << month << "  " << days_since_january_first( 2020, month, 1 ) << '\n';
   for ( int month = 1; month <= 12; month++ ) cout << month << "  " << days_since_january_first( 2020, month, 29 ) << '\n';
}

[helios]

I'll accept it only if you give the range of real values for k that make zeroth() correct.

const double k = /*...*/;

int zeroth( int month ){
    return (int)( 30 * ( month - 1 ) + k * max( month - 4.0, 0.0 ) + ( month == 2 ) - (month == 3 ) );
}

[zapshe]

Of course, the point was to avoid trivial looping solutions that anyone can come up with in five minutes.

It was fun, I had time to kill since I had a client in London that was going to give me Voice Over direction for their script. It was morning for them, and 1AM for me *cries*

[lastchance]

0.6 <= k < 0.625 (limiting months would be 9 and 12)

I used 0.601 instead of 0.6 to avoid possible round-off problems.

Drat February, though! Not only do I get 10% less days on my monthly rail ticket that month, but it really screws up this formulation.

[Duthomhas]

helios wrote:

and he [Duthomhas] didn't realize he could use the array for both functions.

I did, actually, but just didn’t bother. Rule of diminishing returns and all.

I enjoyed the challenge, though.

[helios]

You could have avoided floating point by doing max * 6 / 10.

Another version without arrays:

int month_days(int month){
    double ret = 0;
    double x0 = month;
    double x = x0;
    ret +=      264155.0 /     1848.0 * x;
    x *= x0;
    ret +=   -58644857.0 /   151200.0 * x;
    x *= x0;
    ret +=    66438887.0 /   151200.0 * x;
    x *= x0;
    ret += -1502435233.0 /  5443200.0 * x;
    x *= x0;
    ret +=     6542063.0 /    60480.0 * x;
    x *= x0;
    ret +=  -305049097.0 / 10886400.0 * x;
    x *= x0;
    ret +=      331381.0 /    67200.0 * x;
    x *= x0;
    ret +=    -2151841.0 /  3628800.0 * x;
    x *= x0;
    ret +=        1451.0 /    30240.0 * x;
    x *= x0;
    ret +=      -27199.0 / 10886400.0 * x;
    x *= x0;
    ret +=         503.0 /  6652800.0 * x;
    x *= x0;
    ret +=         -11.0 / 10886400.0 * x;
    return (int)(ret + 0.5);
}

int days_in_month(int year, int month){
    if (month == 2)
        return 28 + is_leap_year(year);
    return 28 + month_days(month) - month_days(month - 1);
}

int days_since_january_first(int year, int month, int day){
    month--;
    return month * 28 + month_days(month) +
        is_leap_year(year) * (month > 1) +
        day - 1;
    return ret;
}

[lastchance]

Graph paper and a ruler out for this one ... no floats now.

Before you ask, @Helios, the slope has to lie in 4/7 <= k < 3/5 in order to truncate to the correct integer.

#include <iostream>
using namespace std;

int zeroth( int m )
{
   return 30 * ( m - 1 ) + ( m == 2 ) + ( m > 2 ) * ( -1 + ( m - 2 ) * 4 / 7 );
}

bool is_leap( int year )
{
   return (bool)( !(year % 4) - !( year % 100) + !( year % 400 ) );
}

int days_in_month( int year, int month )
{
   return zeroth(month+1) - zeroth(month) + is_leap( year ) * ( month == 2 );
}

int days_since_january_first( int year, int month, int day )
{
   return zeroth( month ) + day - 1 + is_leap( year ) * ( month > 2 );
}

//==========================================================

int main()
{
   for ( int month = 1; month <= 12; month++ ) cout << month << "  " << days_in_month( 2019, month ) << '\n';
   for ( int month = 1; month <= 12; month++ ) cout << month << "  " << days_in_month( 2020, month ) << '\n';
   for ( int month = 1; month <= 12; month++ ) cout << month << "  " << days_in_month( 1900, month ) << '\n';
   for ( int month = 1; month <= 12; month++ ) cout << month << "  " << days_in_month( 2000, month ) << '\n';
// for ( int year = 1859; year <= 2019; year++ ) cout << year << " " << is_leap( year ) << '\n';
// for ( int month = 1; month <= 12; month++ ) cout << month << "  " << days_since_january_first( 2019, month, 1 ) << '\n';
// for ( int month = 1; month <= 12; month++ ) cout << month << "  " << days_since_january_first( 2020, month, 1 ) << '\n';
// for ( int month = 1; month <= 12; month++ ) cout << month << "  " << days_since_january_first( 2019, month, 29 ) << '\n';
   for ( int month = 1; month <= 12; month++ ) cout << month << "  " << days_since_january_first( 2020, month, 29 ) << '\n';
}

[helios]

Last one, again with polynomials:

int month_days(int m){
    int x = m;
    int ret = 10 * x;
    x = x * m % 31;
    ret += x;
    x = x * m % 31;
    ret += 26 * x;
    x = x * m % 31;
    ret += 24 * x;
    x = x * m % 31;
    ret += 22 * x;
    x = x * m % 31;
    ret += 8 * x;
    x = x * m % 31;
    ret += 5 * x;
    x = x * m % 31;
    ret += 12 * x;
    x = x * m % 31;
    ret += 12 * x;
    x = x * m % 31;
    ret += 29 * x;
    x = x * m % 31;
    ret += 16 * x;
    x = x * m % 31;
    ret += 24 * x;
    return ret % 31;
}