Challenge

Pages: 12
Oct 17, 2019 at 2:12pm
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.
Last edited on Oct 17, 2019 at 2:13pm
Oct 17, 2019 at 3:30pm
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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.
Oct 17, 2019 at 3:53pm
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.
Oct 17, 2019 at 4:34pm
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
Oct 17, 2019 at 4:40pm
No array!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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';
}
Oct 17, 2019 at 5:07pm
I'll accept it only if you give the range of real values for k that make zeroth() correct.
1
2
3
4
5
const double k = /*...*/;

int zeroth( int month ){
    return (int)( 30 * ( month - 1 ) + k * max( month - 4.0, 0.0 ) + ( month == 2 ) - (month == 3 ) );
}
Oct 17, 2019 at 5:56pm
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*
Oct 17, 2019 at 6:00pm
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.
Oct 17, 2019 at 6:19pm
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.
Oct 17, 2019 at 6:20pm
You could have avoided floating point by doing max * 6 / 10.

Another version without arrays:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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;
}
Oct 17, 2019 at 7:30pm
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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';
}
Last edited on Oct 17, 2019 at 7:48pm
Oct 18, 2019 at 2:36am
Last one, again with polynomials:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
}
Topic archived. No new replies allowed.
Pages: 12