Last active
October 9, 2022 00:16
-
-
Save kccqzy/36d893f14f2386c733b488d46b3d03ac to your computer and use it in GitHub Desktop.
The Bus Schedule Problem (Problem B)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <assert.h> | |
#include <stdio.h> | |
#include <stdlib.h> | |
#include <time.h> | |
#include <algorithm> | |
#include <iostream> | |
#include <map> | |
#include <sstream> | |
#include <string> | |
#include <vector> | |
#ifdef NDEBUG | |
#define CHECK_EQ(a, b) ((void)0) | |
#else | |
class Assertion { | |
public: | |
template <typename A, typename B> | |
Assertion(const char* func, const char* file, int line, const char* sa, | |
const char* sb, A a, B b) | |
: eq(a == b) { | |
if (!eq) { | |
msg << "Assertion failed at " << file << ":" << line << " " << func | |
<< ".\nExpecting equality between:\n" | |
<< sa << "\n which is " << a << "\nand:\n" | |
<< sb << "\n which is " << b << "\n"; | |
} | |
} | |
template <typename T> | |
Assertion& operator<<(T const& t) { | |
if (!eq) { | |
msg << t; | |
} | |
return *this; | |
} | |
~Assertion() { | |
if (!eq) { | |
std::cerr << msg.str() << std::endl; | |
abort(); | |
} | |
} | |
private: | |
bool eq; | |
std::ostringstream msg; | |
}; | |
#define CHECK_EQ(a, b) Assertion(__func__, __FILE__, __LINE__, #a, #b, a, b) | |
#endif | |
namespace { | |
class Day { | |
public: | |
explicit Day(unsigned year, unsigned month, unsigned day); | |
unsigned y() const { return year_; } | |
unsigned m() const { return month_; } | |
unsigned d() const { return day_; } | |
unsigned weekday() const { return weekday_; } | |
unsigned daynum() const { return daynum_; } | |
void next(unsigned d = 1); | |
private: | |
explicit Day(unsigned daynum); | |
static unsigned to_day_num(unsigned year, unsigned month, unsigned day); | |
unsigned daynum_; | |
unsigned weekday_; | |
unsigned year_; | |
unsigned month_; | |
unsigned day_; | |
}; | |
unsigned Day::to_day_num(unsigned year, unsigned month, unsigned day) { | |
unsigned daynum; | |
assert(month > 0); | |
// Adjust month to be correct | |
--month; | |
if (month >= 12) { | |
year += month / 12; | |
month %= 12; | |
} | |
++month; | |
// Convert year to the right number of days of offset. | |
assert(year >= 1600); | |
bool leap = false; | |
{ | |
unsigned cycles = (year - 1600) / 400; | |
unsigned rem = (year - 1600) % 400; | |
// Each cycle has 97 leap years. | |
unsigned leaps = 97 * cycles; | |
unsigned centuries = rem / 100; | |
if (rem == 0) { | |
leap = true; // mod 400 year | |
} else { | |
// Each century has 24 leap years from xx04 to xx96 (mod 400 leap handled | |
// later). | |
leaps += 24 * centuries; | |
rem %= 100; | |
if (rem) { | |
leaps += rem / 4; | |
rem %= 4; | |
leap = !rem; | |
} | |
} | |
// Add one since the first year of each cycle is leap. | |
++leaps; | |
// Remove the current year from consideration. | |
leaps -= leap; | |
daynum = (year - 1600) * 365 + leaps; | |
} | |
// Month | |
static constexpr unsigned days_through_month[] = { | |
0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334}; | |
daynum += days_through_month[month - 1]; | |
if (leap && month >= 3) ++daynum; | |
// Day | |
daynum += day - 1; | |
return daynum; | |
} | |
Day::Day(unsigned daynum) : daynum_(daynum), weekday_((daynum + 6) % 7) { | |
static constexpr unsigned days_4y = 365 * 4 + 1; | |
static constexpr unsigned days_100y = 365 * 100 + 24; | |
static constexpr unsigned days_400y = 365 * 400 + 97; | |
// For convenience, we want leaps days to be at the end. Hence remdays == | |
// number of days since 1200-03-01. Why not 1600-03-01? We hate negative | |
// numbers. | |
unsigned remdays = daynum_ + days_400y - 31 - 29; | |
unsigned cycles = remdays / days_400y; | |
remdays %= days_400y; | |
// remdays in [0, 146096] | |
unsigned centuries = remdays / days_100y; | |
remdays %= days_100y; | |
if (centuries == 4) { | |
assert(remdays == 0); | |
centuries = 3; | |
remdays = days_100y; | |
} | |
// remdays in [0, 36524] | |
unsigned fouryears = remdays / days_4y; | |
remdays %= days_4y; | |
// remdays in [0, 1460] | |
assert(fouryears < 25); | |
assert(remdays < days_4y); | |
unsigned remyears = remdays / 365; | |
remdays %= 365; | |
if (remyears == 4) { | |
assert(remdays == 0); | |
remyears = 3; | |
remdays = 365; | |
} | |
// remdays in [0,365] | |
year_ = 1200 + 400 * cycles + 100 * centuries + 4 * fouryears + remyears; | |
static constexpr unsigned days_in_month[] = {31, 30, 31, 30, 31, 31, | |
30, 31, 30, 31, 31, 29}; | |
for (month_ = 0; days_in_month[month_] <= remdays; ++month_) { | |
remdays -= days_in_month[month_]; | |
} | |
month_ += 3; | |
if (month_ > 12) { | |
month_ -= 12; | |
year_++; | |
} | |
day_ = 1 + remdays; | |
} | |
Day::Day(unsigned year, unsigned month, unsigned day) | |
: Day(to_day_num(year, month, day)) { | |
#ifndef NDEBUG | |
if (year >= 1900) { | |
tm t{.tm_mday = static_cast<int>(day), | |
.tm_mon = static_cast<int>(month) - 1, | |
.tm_year = static_cast<int>(year) - 1900}; | |
mktime(&t); | |
CHECK_EQ(t.tm_mday, day_) | |
<< "where day_ " << day_ << " month_ " << month_ << " year_ " << year_ | |
<< " with input " << year << "-" << month << "-" << day; | |
CHECK_EQ(t.tm_mon + 1, month_) | |
<< "where day_ " << day_ << " month_ " << month_ << " year_ " << year_ | |
<< " with input " << year << "-" << month << "-" << day; | |
CHECK_EQ(t.tm_year + 1900, year_) | |
<< "where day_ " << day_ << " month_ " << month_ << " year_ " << year_ | |
<< " with input " << year << "-" << month << "-" << day; | |
CHECK_EQ(t.tm_wday, weekday_) | |
<< "where day_ " << day_ << " month_ " << month_ << " year_ " << year_ | |
<< " with input " << year << "-" << month << "-" << day; | |
} | |
#endif | |
} | |
void Day::next(unsigned d) { | |
#ifndef NDEBUG | |
unsigned old_day = day_, old_month = month_, old_year = year_; | |
#endif | |
daynum_ += d; | |
weekday_ += d; | |
weekday_ %= 7; | |
static constexpr unsigned days_in_month[] = {31, 28, 31, 30, 31, 30, | |
31, 31, 30, 31, 30, 31}; | |
for (unsigned i = 0; i < d; ++i) { | |
if (++day_ > days_in_month[month_ - 1]) { | |
if (!(month_ == 2 && day_ == 29 && | |
(year_ % 4 == 0 && (year_ % 100 != 0 || year_ % 400 == 0)))) { | |
day_ = 1; | |
if (++month_ > 12) { | |
month_ = 1; | |
year_++; | |
} | |
} | |
} | |
} | |
#ifndef NDEBUG | |
Day slow(daynum_); | |
CHECK_EQ(slow.day_, day_) | |
<< "where day_ " << day_ << " month_ " << month_ << " year_ " << year_ | |
<< " vs originally day_ " << old_day << " month_ " << old_month | |
<< " year_ " << old_year; | |
CHECK_EQ(slow.month_, month_) | |
<< "where day_ " << day_ << " month_ " << month_ << " year_ " << year_ | |
<< " vs originally day_ " << old_day << " month_ " << old_month | |
<< " year_ " << old_year; | |
CHECK_EQ(slow.year_, year_) | |
<< "where day_ " << day_ << " month_ " << month_ << " year_ " << year_ | |
<< " vs originally day_ " << old_day << " month_ " << old_month | |
<< " year_ " << old_year; | |
CHECK_EQ(slow.weekday_, weekday_); | |
#endif | |
} | |
static Day get_monday_after_easter(int y) { | |
int golden = (y % 19) + 1; | |
int solar = (y - 1600) / 100 - (y - 1600) / 400; | |
int lunar = (((y - 1400) / 100) * 8) / 25; | |
int p = (3003 - (11 * golden) + solar - lunar) % 30; | |
if ((p == 29) || ((p == 28) && (golden > 11))) p--; | |
Day t(y, 3, 21 + p); | |
// Next Sunday == easter. Adds 7 if currently Sunday. We want the Monday | |
// afterwards. | |
t.next(7 - t.weekday() + 1); | |
return t; | |
} | |
static const std::vector<Day>& get_holidays_for_year(int y) { | |
static std::map<int, std::vector<Day>> cached; | |
std::vector<Day>& rv = cached[y]; | |
if (!rv.empty()) return rv; | |
rv.reserve(65); | |
// Legal holidays | |
rv.push_back(Day(y, 1, 1)); | |
rv.push_back(get_monday_after_easter(y)); | |
rv.push_back(Day(y, 5, 1)); | |
rv.push_back(Day(y, 5, 8)); | |
rv.push_back(Day(y, 6, 5)); | |
rv.push_back(Day(y, 6, 6)); | |
rv.push_back(Day(y, 9, 28)); | |
rv.push_back(Day(y, 10, 28)); | |
rv.push_back(Day(y, 11, 17)); | |
rv.push_back(Day(y, 12, 24)); | |
rv.push_back(Day(y, 12, 25)); | |
rv.push_back(Day(y, 12, 26)); | |
// All Sundays | |
Day t = rv.front(); // New Year | |
t.next(7 - t.weekday()); | |
do { | |
rv.push_back(t); | |
t.next(7); | |
} while (t.y() == y); | |
return rv; | |
} | |
static bool is_in_vec(Day const& t, std::vector<Day> const& vec) { | |
return std::any_of(vec.begin(), vec.end(), [&t](const auto& ht) { | |
return ht.d() == t.d() && ht.m() == t.m(); | |
}); | |
} | |
static bool is_day_holiday(Day const& t) { | |
return is_in_vec(t, get_holidays_for_year(t.y())); | |
} | |
static const std::vector<Day>& get_weekday_after_holidays_for_year(int y) { | |
static std::map<int, std::vector<Day>> cached; | |
std::vector<Day>& rv = cached[y]; | |
if (!rv.empty()) return rv; | |
rv.reserve(65); | |
for (Day day : get_holidays_for_year(y)) { | |
do { | |
day.next(); | |
} while (!(day.weekday() >= 1 && day.weekday() <= 5) || | |
is_day_holiday(day)); | |
rv.push_back(day); | |
} | |
return rv; | |
} | |
static bool bus_runs(Day const& t, std::string const& spec) { | |
// Check 1-7 | |
for (int weekday = 1; weekday <= 7; weekday++) { | |
char spec_day = '0' + weekday; | |
if (spec.find(spec_day) != std::string::npos && | |
t.weekday() == weekday % 7) { | |
return true; | |
} | |
} | |
// Check t | |
if (spec.find('t') != std::string::npos && is_day_holiday(t)) { | |
return true; | |
} | |
// Check w | |
if (spec.find('w') != std::string::npos && t.weekday() >= 1 && | |
t.weekday() <= 5 && !is_day_holiday(t)) { | |
return true; | |
} | |
// Check a | |
if (spec.find('a') != std::string::npos && | |
is_in_vec(t, get_weekday_after_holidays_for_year(t.y()))) { | |
return true; | |
} | |
return false; | |
} | |
static std::pair<Day, Day> into_restrictions(int y, int d1, int m1) { | |
Day begin(y, m1, d1); | |
Day end = begin; | |
end.next(); | |
// Ignore Feb 29th if not leap year. | |
if (d1 == 29 && m1 == 2 && begin.d() == 1) { | |
end = begin; | |
} | |
return std::make_pair(begin, end); | |
} | |
static std::pair<Day, Day> into_restrictions(int y, int d1, int m1, int d2, | |
int m2) { | |
Day begin(y, m1, d1); | |
Day end(y, m2, d2 + 1 /* open interval */); | |
// Treat end as Feb 28th if not leap year. | |
if (d2 == 29 && m2 == 2 && end.d() == 2) { | |
end = Day(y, 3, 1); | |
} | |
return std::make_pair(begin, end); | |
} | |
static std::vector<std::pair<Day, Day>> parse_restrictions( | |
int y, std::string const& s) { | |
std::vector<std::pair<Day, Day>> rv; | |
const char* p = s.c_str(); | |
for (;;) { | |
char* end; | |
long d1 = strtol(p, &end, 10); | |
assert(*end == '.'); | |
p = end + 1; | |
long m1 = strtol(p, &end, 10); | |
assert(*end == '.'); | |
p = end + 1; | |
if (*p == '-') { | |
p++; | |
long d2 = strtol(p, &end, 10); | |
assert(*end == '.'); | |
p = end + 1; | |
long m2 = strtol(p, &end, 10); | |
assert(*end == '.'); | |
p = end + 1; | |
rv.push_back(into_restrictions(y, d1, m1, d2, m2)); | |
} else { | |
rv.push_back(into_restrictions(y, d1, m1)); | |
} | |
if (*p == '\0') return rv; | |
assert(*p == ','); | |
p++; | |
} | |
} | |
} // namespace | |
int main() { | |
#ifndef NDEBUG | |
for (int y = 1600; y <= 2100; ++y) { | |
Day t1(y, 12, 31); | |
CHECK_EQ(t1.y(), y); | |
CHECK_EQ(t1.m(), 12); | |
CHECK_EQ(t1.d(), 31); | |
t1.next(); | |
CHECK_EQ(t1.y(), y + 1); | |
CHECK_EQ(t1.m(), 1); | |
CHECK_EQ(t1.d(), 1); | |
Day t2(y + 1, 1, 1); | |
CHECK_EQ(t1.daynum(), t2.daynum()); | |
CHECK_EQ(t1.y(), t2.y()); | |
CHECK_EQ(t1.m(), t2.m()); | |
CHECK_EQ(t1.d(), t2.d()); | |
Day leap(y, 2, 29); | |
} | |
#endif | |
std::string spec, restrictions_str; | |
int year; | |
while (std::cin >> spec >> restrictions_str >> year) { | |
int run_days = 0; | |
std::vector<std::pair<Day, Day>> restrictions = | |
parse_restrictions(year, restrictions_str); | |
for (auto const& range : restrictions) { | |
for (Day d(range.first); d.daynum() != range.second.daynum(); d.next()) { | |
run_days += bus_runs(d, spec); | |
} | |
} | |
printf("%d\n", run_days); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment