The Bus Schedule Problem (Problem B)

bus_schedule.cc

#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);
  }
}