3

The USACO 1.1 – Friday the Thirteenth problem has been solved many times in various ways. Indeed it has generated a handful of questions on StackOverflow with various solutions:

The question is: What would a solution look like using a modern C++11/14 date library such as the one I've linked to?

Would it be significantly simpler than the other solutions? Easier to write? More efficient?

Community
  • 1
  • 1
Howard Hinnant
  • 206,506
  • 52
  • 449
  • 577

1 Answers1

6

The problem statement is to count the frequency with which the 13th of each month falls on a given weekday in the range [1900-01-01, 2300-01-01).

Using date.h this is very easily and efficiently accomplished like this:

#include "date/date.h"
#include <chrono>
#include <iostream>

int
main()
{
    using namespace date;
    using namespace std::chrono;
    unsigned freq[7] = {};
    for (auto ym = 1900_y/January; ym < 2300_y/January; ym += months{1})
        freq[weekday{ym/13}.c_encoding()]++;
    for (unsigned i = 0; i < 7; ++i)
        std::cout << weekday{i} << " : " << freq[i] << '\n';
}

ym is a date::year_month object. You can think of this as like a time_point, but it has a very coarse precision of months.

You simply loop over each year, and each month of each year, and compute the day of the week for the 13th of that month, and cast that weekday into an unsigned.

The high-level syntax is quite straight forward and readable.

The algorithms under the hood are days_from_civil and weekday_from_days. Neither one of these low-level date algorithms are iterative, and thus they are very efficient. So you get the best of both worlds: Readable high-level syntax, and high performance.

The output of this simple program is also quite readable:

Sun : 687
Mon : 685
Tue : 685
Wed : 687
Thu : 684
Fri : 688
Sat : 684

It turns out Friday the 13th is slightly more likely than the other days of the week.

In C++17, you can even create a constexpr std::array<unsigned, 7> with these results (should it be important for some reason to have such numbers at compile-time):

#include "date/date.h"
#include <array>
#include <chrono>
#include <iostream>

constexpr
std::array<unsigned, 7>
compute_freq() noexcept
{
    using namespace date;
    using namespace std::chrono;
    decltype(compute_freq()) freq = {};
    for (auto ym = 1900_y/January; ym < 2300_y/January; ym += months{1})
        freq[weekday{ym/13}.c_encoding()]++;
    return freq;
}

constexpr auto freq = compute_freq();

int
main()
{
    using namespace date;
    using namespace std::chrono;
    static_assert(freq[Sunday.c_encoding()]    == 687);
    static_assert(freq[Monday.c_encoding()]    == 685);
    static_assert(freq[Tuesday.c_encoding()]   == 685);
    static_assert(freq[Wednesday.c_encoding()] == 687);
    static_assert(freq[Thursday.c_encoding()]  == 684);
    static_assert(freq[Friday.c_encoding()]    == 688);
    static_assert(freq[Saturday.c_encoding()]  == 684);
}

which generates this assembly:

_freq:
    .long   687                     ## 0x2af
    .long   685                     ## 0x2ad
    .long   685                     ## 0x2ad
    .long   687                     ## 0x2af
    .long   684                     ## 0x2ac
    .long   688                     ## 0x2b0
    .long   684                     ## 0x2ac

And you just can't get more efficient than that.

In C++20 this all becomes available in your std::lib. To port the above programs to C++20, drop #include "date/date.h" and using namespace date;. Also change the _y suffix to y.

Howard Hinnant
  • 206,506
  • 52
  • 449
  • 577