C++

Forum

 
Challenge

Pages: 12
helios (17506)
Write a constant time implementation of days_in_month(int year, int month) and days_since_january_first(int year, int month, int day). If you use a constant data array, it must fit in 16 bytes.

Note: "Constant time" means that the run time is uncorrelated with the input. No "ooh, but the input is bounded, so the run time is also bounded" shenanigans.
zapshe (1834)
Wouldn't multi-threading solve the issue of keeping constant time?
helios (17506)
"Constant time" is the run time order O(1).
zapshe (1834)
When I ran it, it ran within a .5ms variance of 1002ms that was constant no matter the input.

The variance comes from inherit facts of my machine, but it never varied in a different way or pattern simply because of changing the input.

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
#include <iostream>
#include <chrono>
#include <thread>

int days_in_month(int year, int month)
{
	if (month == 9 || month == 4 || month == 6 || month == 11)
		return 30;

	if (month == 2)
	{
		if (year % 4 == 0)
			return 29;

		else
			return 28;
	}

	else
		return 31;
}

void days_since_january_first(int year, int month, int day)
{
	int since = day;
	month--;

	for (int i = 1; i <= month; i++)
	{
		since += (days_in_month(year, i));
	}


	since--;
	std::cout << since;
}

void pause_thread(int n)
{
	std::this_thread::sleep_for(std::chrono::seconds(n));
}

int main()
{ 
	int year;
	int month;
	int day;

	std::cout << "Enter Year: ";
	std::cin >> year;
	std::cout << "Enter Month: ";
	std::cin >> month;
	std::cout << "Enter Day: ";
	std::cin >> day;

	auto t0 = std::chrono::steady_clock::now();
	std::thread tt(pause_thread, 1);
	std::thread t(days_since_january_first, year, month, day);
	tt.join();
	t.join();
	auto t1 = std::chrono::steady_clock::now();
	auto d = std::chrono::duration_cast<std::chrono::duration<double>>(t1 - t0);
	std::cout << '\n' << d.count() << " seconds" << std::endl;
}
Last edited on
zapshe (1834)
"Constant time" is the run time order O(1).

??

Did you mean that the run time of both functions should be the same or that the runtime of the program should be constant?
helios (17506)
What do they teach kids in school these days?

O(1) means that a program terminates in a bounded number of fundamental operations for all inputs. "Bounded" meaning, that if i is the input and f(i) is the number of operations, there exists a natural k such that k >= f(i), regardless of the value of i. In other words, the run time doesn't go to infinity as the input goes to infinity.

days_since_january_first() contains a loop that iterates a number of times based on one of the inputs, so the function runs in O(n) (linear time).
Last edited on
zapshe (1834)
What do they teach kids in school these days?

Basically nothing. But to be fair, it could be a concept that'll be gone over in a later course.

So the runtime of the "days_since_january_first" function needs to be constant? I think I know a way. Do you have the answer to this yourself?
ne555 (10692)
> days_since_january_first() contains a loop that iterates a number of times based on one of the inputs
1
2
3
4
 
	for (int i = 1; i <= 12; i++)
	{
		since += (days_in_month(year, i)) * (i<=month);
	}
now the number of iterations doesn't depend on the input
zapshe (1834)
Using an array like this solves that issue. Computation time is much more staggered here since it's not regulated, but that's due to inherit things rather than input.

You said an array must fit 16 bytes, but I was a bit lazy. It's possible to get it down to that if you remove some parts of the array (like the first part of the array since it can be assumed) and possibly move some parts of it into a char array that can hold a symbol which has a numeric value in the ascii table that corresponds to the number we wanted it to hold.

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
#include <iostream>
#include <chrono>
#include <thread>

unsigned short int d[11];

int days_in_month(int year, int month)
{
	if (month == 9 || month == 4 || month == 6 || month == 11)
		return 30;

	if (month == 2)
	{
		if (year % 4 == 0)
			return 29;

		else
			return 28;
	}

	else
		return 31;
}

void days_since_january_first(int year, int month, int day)
{
	int since = day;
	month--;


	if (year % 4 == 0)
		since += 1;

	since = d[month-1] + since;
	
	since--;
	std::cout << since;
}

int main()
{
	d[0] = 31; 
	d[1] = 59;
	d[2] = 90;
	d[3] = 120;
	d[4] = 151;
	d[5] = 181;
	d[6] = 212;
	d[7] = 243;
	d[8] = 273;
	d[9] = 304;
	d[10] = 334;


	int year;
	int month;
	int day;

	std::cout << "Enter Year: ";
	std::cin >> year;
	std::cout << "Enter Month: ";
	std::cin >> month;
	std::cout << "Enter Day: ";
	std::cin >> day;

	auto t0 = std::chrono::steady_clock::now();
	days_since_january_first(year, month, day);
	auto t1 = std::chrono::steady_clock::now();
	auto d = std::chrono::duration_cast<std::chrono::duration<double>>(t1 - t0);
	std::cout << '\n' << d.count() << " seconds" << std::endl;
}
Last edited on
salem c (3685)
Rough idea for days since 1jan
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
 
total = day;
switch ( month ) {
  case 11:
    total += 30;
  case 10:
    total += 31;
  case 9:
    total += 30;
  case 8:
    total += 31;
  case 7:
    total += 31;
  case 6:
    total += 30;
  case 5:
    total += 31;
  case 4:
    total += 30;
  case 3:
    total += 31;
  case 2:
    total += 28 + isleap(year);
  case 1:
    total += 31;
}
Last edited on
helios (17506)
ne555: Figures. Nobody likes a smartass (Douglas Adams).

zapshe: You're on the right track. Can you figure out how to compress d and make it constant?
Also, your leap year condition is wrong. 2000 is a leap year, but 1900 isn't.
zapshe (1834)
@salem c

A switch is a good replacement for an array since he wanted it limited to 16 bytes. The only issue with setting total to the actual amount of days the month holds is that, to calculate the amount of days, you'll need to somehow loop through this. You can use it alongside ne555's loop, but that's extra work for the computer with no benefit.

EDIT: My bad, I see there's no break statement so that actually works pretty well!
Last edited on
zapshe (1834)
I edited the code for correct leap years and made d constant. But I'm not sure how to make it smaller without making things messier. I tried turning it into a __int8 but that made the bigger numbers at the end overflow. I've never tried being memory efficient before ;-;

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
#include <iostream>
#include <chrono>
#include <thread>

const __int16 d[11] = { 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334 };

int days_in_month(int year, int month)
{
	if (month == 9 || month == 4 || month == 6 || month == 11)
		return 30;

	if (month == 2)
	{
		if ((year % 4 == 0) && (!(year % 100 == 0) || (year % 400 == 0)))
			return 29;

		else
			return 28;
	}

	else
		return 31;
}

void days_since_january_first(int year, int month, int day)
{
	int since = day;
	month--;

	if ((year % 4 == 0) && (!(year % 100 == 0) || (year % 400 == 0)))
		since += 1;

	since = d[month-1] + since;
	
	since--;
	std::cout << since;
}

int main()
{
	std::cout << sizeof(d) << '\n';

	int year;
	int month;
	int day;

	std::cout << "Enter Year: ";
	std::cin >> year;
	std::cout << "Enter Month: ";
	std::cin >> month;
	std::cout << "Enter Day: ";
	std::cin >> day;

	auto t0 = std::chrono::steady_clock::now();
	days_since_january_first(year, month, day);
	auto t1 = std::chrono::steady_clock::now();
	auto dd = std::chrono::duration_cast<std::chrono::duration<double>>(t1 - t0);
	std::cout << '\n' << dd.count() << " seconds" << std::endl;
}
zapshe (1834)
I got it down to 14 bytes but I don't like the method:

1
2
 
const __int8 dd[8] = { 31, 59, 90, 120, 151, 181, 212, 243 };
const __int16 d[3] = { 273, 304, 334 };


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
void days_since_january_first(int year, int month, int day)
{
	int since = day;
	month--;

	if ((year % 4 == 0) && (!(year % 100 == 0) || (year % 400 == 0)))
		since += 1;

	if(month <= 8)
		since = d[month-1] + since;

	if (month > 8)
		since = d[month - 9] + since;
	
	since--;
	std::cout << since;
}
helios (17506)
I tried turning it into a __int8 but that made the bigger numbers at the end overflow.
Yup. But is there a representation that will make it fit? Hint: the largest number (the last one) in the array can be made smaller than 32.
Duthomhas (13129)
Heh, LOL, easy peasy.

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

bool is_leap_year( int year )
{
  return !(year % 4) and ((year % 400) or !(year % 100));
}

int days_in_month( int year, int month )
{
  return (month == 2)
    ? (28 + is_leap_year( year ))
    : (30 + (!(month % 2) ^ (month < 8)));
}

int days_since_january_first( int year, int month, int day )
{
  const signed char days[] = { 0, 1, -1, 0, 0, 1, 1, 2, 3, 3, 4, 4, 5 };
  return ((month - 1) * 30) + days[month - 1] + ((month > 2) and is_leap_year( year )) + day - 1;
}

#include <iostream>
#include <string>

int main( int argc, char** argv ) try
{
  if (argc != 4) throw 1;
  int year  = std::stoi( argv[1] );
  int month = std::stoi( argv[2] );
  int day   = std::stoi( argv[3] );
  if (is_leap_year( year )) std::cout << year << " is a leap year\n";
  std::cout << "days in month = " << days_in_month( year, month ) << "\n";
  std::cout << "days since january first = " << days_since_january_first( year, month, day ) << "\n";
}
catch (...)
{
  std::cout << "usage:\n  " << argv[0] << " YEAR MONTH DAY\n";
  return 1;
}

:O)

[edit]
@zapshe
Constant time is a concept you should have seen by now...

[edit2]
Oops. I just re-read the challenge and realized I totally missed a function. Give me a few.

Okay, done. I decided to use the constant data array for this one... heh.
Last edited on
zapshe (1834)
https://www.youtube.com/watch?v=XLUodac2BRU

Constant time is a concept you should have seen by now...

Self-taught as you know, no concept like this has been covered in university yet. I may have some holes in my knowledge because I haven't been doing this as long as you guys :( . But if it's just small programming concepts like this, then they'll be easy to learn if the time comes for them.

Is ciso646 portable? Never seen it before, I call hacks.


But is there a representation that will make it fit? Hint: the largest number (the last one) in the array can be made smaller than 32.

No idea. I've never gone over concepts that try to save memory space, so I'm not picking up on what you're laying down. I think a bit field might work well here, but that doesn't seem to be what you're implying.
Duthomhas (13129)
Here it is using the C Standard Library:

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

#define _CRT_SECURE_NO_WARNINGS 1

int days_since_january_first( int year, int month, int day )
{
  struct tm ts{ 0, 0, 0, day, month - 1, year - 1900, 0, 0, 0 };
  auto t = std::mktime( &ts );
  return std::localtime( &t )->tm_yday;
}

int days_in_month( int year, int month )
{
  return (month == 12) ? 31
       : days_since_january_first( year, month + 1, 1 )
       - days_since_january_first( year, month,     1 );
}


#include <iostream>
#include <string>

int main( int argc, char** argv ) try
{
  if (argc != 4) throw 1;
  int year  = std::stoi( argv[1] );
  int month = std::stoi( argv[2] );
  int day   = std::stoi( argv[3] );
//  if (is_leap_year( year )) std::cout << year << " is a leap year\n";
  std::cout << "days in month = " << days_in_month( year, month ) << "\n";
  std::cout << "days since january first = " << days_since_january_first( year, month, day ) << "\n";
}
catch (...)
{
  std::cout << "usage:\n  " << argv[0] << " YEAR MONTH DAY\n";
  return 1;
}

:O)

[edit]
<ciso646>/<iso646.h> is part of the C++/C standard.
Last edited on
lastchance (6980)
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;

unsigned char zeroth[1+12+1] = { 0, 0, 31, 59, 90, 120, 151, 181, 212, 243, 17, 48, 78, 109 };


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


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


int days_since_january_first( int year, int month, int day )
{
   return zeroth[month] + ( month >= 10 ) * 256 + day - 1
          + is_leap( year ) * ( month > 2 );  // corrected
}


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';
}



Requirements from @Helios: "the run time is uncorrelated with the input". (Actually, I think that is more stringent than O(1), which simply means a constant upper bound.)

So:
- no branching (if, else, switch etc.) if number of operations depends on the input
- no use of && or ||, since "short-cutting" may reduce the number of operations (even if that's a good thing!)

I think the array is 14 bytes.
Last edited on
Duthomhas (13129)
Yeah, after you posted last night (before your thoughts on edit) I had the same thing pass through my head and I thought to myself that you have won this challenge.
Pages: 12