# Embedded Calendar

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.

## Input format

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.

## Output format

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) { let mut reference: Option = 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 #include #include #include #include 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; } 
We've worked on this challenge in these gyms: padua