We are working on an embedded device with a small amount of memory. In this
device there is no space for time libraries. The device should provide the
current time in UTC with this format: 2020-02-11 14:12:18.123 (year-month-day
hour:minute:second, where second has 3 decimals).
Sometimes the device receives the current UTC time from an external source.
The device is only aware of its uptime (milliseconds from the boot).
We are writing a serial protocol to update the reference time and get current time.
Any line beginning with R (reference) contains the reference time in UTC and associated uptime in milliseconds.
Any line beginning with G (get) contains the uptime in milliseconds.
1
2
3
|
R 2020-02-11 13:12:18.123 1000000
G 4600000
G 8200000
|
Constraints
Uptime is in milliseconds and can only increment.
Reference may not be provided or may be provided multiple times. Reference are
always valid timestamps.
Print out the current time in UTC for each input line beginning with G. If a
reference time is not available, print -.
Solutions
Handling (human) time is difficult… time zones, leap years, leap seconds. Most
languages have libraries to handle calculation on dates.
But… you should not have used any time library available in your language of
choice!
Naive solution
We have a reference time, where human time and computer time are associated.
When we want to translate computer time to human time, we can add second by
second to the human time, handling remainders correctly (remember months have a
variable amount of days and leap years exist).
Improved solution
While at the date level there are special cases (days per month and leap years),
time of the day is regular (e.g.: the second 3600 is always 01:00:00.000).
So we can first calculate how many days is the difference between the reference
time and the computer time and add them to the date.
Then we use the remaining milliseconds to add to the found day. It may be
possible to step to next day (e.g.: it’s 23:00 and remaining time to add is 4000
seconds).
Update reference
To speed up things, knowing that computer time always increment, we can update
the reference time everytime we calculate a new human time.
Solution in Rust
A working example in Rust (some code, like input parsing, is missing).
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
|
use std::convert::TryFrom;
type Timestamp = i64;
#[derive(Clone, Copy)]
struct Time {
hour: i64,
minute: i64,
millisecond: i64,
}
const MS_IN_DAY: i64 = 24 * MS_IN_HOUR;
const MS_IN_HOUR: i64 = 60 * MS_IN_MINUTE;
const MS_IN_MINUTE: i64 = 60 * MS_IN_SECOND;
const MS_IN_SECOND: i64 = 1000;
impl Time {
fn from_milliseconds(millisecond: i64) -> Self {
let hour = millisecond / MS_IN_HOUR;
let millisecond = millisecond % MS_IN_HOUR;
let minute = millisecond / MS_IN_MINUTE;
let millisecond = millisecond % MS_IN_MINUTE;
Self {
hour,
minute,
millisecond,
}
}
fn to_milliseconds(&self) -> i64 {
self.hour * MS_IN_HOUR
+ self.minute * MS_IN_MINUTE
+ self.millisecond
}
}
#[derive(Clone, Copy)]
struct DateTime {
year: i64,
month: i64,
day: i64,
hour: i64,
minute: i64,
millisecond: i64,
}
impl DateTime {
fn add_milliseconds(&self, ms: i64) -> Self {
let mut day_offset = ms / MS_IN_DAY;
let time_offset = ms % MS_IN_DAY;
let &DateTime {
mut year,
mut month,
mut day,
..
} = self;
let mut new_time_of_day =
self.time_of_day_milliseconds() + time_offset;
if new_time_of_day >= MS_IN_DAY {
new_time_of_day -= MS_IN_DAY;
day_offset += 1;
}
if day_offset > 0 {
let (y, m, d) = carry_over_day(
year,
month,
day + day_offset,
);
year = y;
month = m;
day = d;
}
let Time {
hour,
minute,
millisecond,
} = Time::from_milliseconds(new_time_of_day);
Self {
year,
month,
day,
hour,
minute,
millisecond,
}
}
fn time_of_day_milliseconds(&self) -> i64 {
let tod = Time {
hour: self.hour,
minute: self.minute,
millisecond: self.millisecond,
};
tod.to_milliseconds()
}
}
struct Reference {
dt: DateTime,
t: Timestamp,
}
enum Entry {
Reference(Reference),
Get(Timestamp),
}
fn days_in_month(y: i64, m: i64) -> i64 {
match m {
1 | 3 | 5 | 7 | 8 | 10 | 12 => 31,
2 => 28 + (((y & 3) == 0) as i64),
_ => 30,
}
}
fn carry_over_day(
mut y: i64,
mut m: i64,
mut d: i64,
) -> (i64, i64, i64) {
loop {
let d_max = days_in_month(y, m);
if d > d_max {
d -= d_max;
m += 1;
} else {
break;
}
if m > 12 {
m -= 12;
y += 1;
}
}
(y, m, d)
}
fn run(entries: Vec<Entry>) {
let mut reference: Option<Reference> = None;
for entry in entries {
match entry {
Entry::Reference(r) => {
reference = Some(r);
}
Entry::Get(t) => {
if let Some(r) = &reference {
let diff = t - r.t;
let dt = r.dt.add_milliseconds(diff);
println!("{}", dt);
reference = Some(Reference { dt, t });
} else {
println!("-");
}
}
}
}
}
|
A solution in C by Michele Liberi:
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
|
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <sys/time.h>
int Mdays(int y, int m){
switch(m){
case 4: case 6: case 9: case 11:
return 30;
case 1: case 3: case 5: case 7: case 8: case 10: case 12:
return 31;
case 2:
if (y%4)
return 28;
}
return 29;
}
int Ydays(int y){
if (y%4)
return 365;
return 366;
}
int main() {
char c, r=0;
unsigned long yyyy, mm, dd, hh, min, ss, mmm, offset, newoffset, delta, x;
while ((c=getchar())!=EOF)
switch(c){
case 'G':
scanf(" %lu\n", &newoffset);
if (r){
delta=newoffset-offset;
offset=newoffset;
mmm+=delta; delta=mmm/1000; mmm%=1000;
ss+=delta; delta=ss/60; ss%=60;
min+=delta; delta=min/60; min%=60;
hh+=delta; delta=hh/24; hh%=24;
dd+=delta;
while (dd>(x=Ydays(yyyy)))
dd-=x, ++yyyy;
while (dd>(x=Mdays(yyyy,mm))){
dd-=x;
if (mm<12)
++mm;
else
mm=1, ++yyyy;
}
printf("%04lu-%02lu-%02lu %02lu:%02lu:%02lu.%03lu\n", yyyy, mm, dd, hh, min, ss, mmm);
}
else
printf("-\n");
break;
case 'R':
r=1;
scanf(" %lu-%lu-%lu %lu:%lu:%lu.%lu %lu\n", &yyyy, &mm, &dd, &hh, &min, &ss, &mmm, &offset);
}
return 0;
}
|