CodeVita challenge: forming the latest valid datetime in a year using some given digits

Question

After answering someone's Code Review question, I decided to tackle a sequel:

Given an input consisting of 12 non-decreasing single digits separated by commas, form the latest valid date time in a non-leap year, in MM/DD hh:mm format. Use each digit at most once. If no date time can be constructed, the output should be 0.

Example input: 0,0,1,2,2,2,3,5,9,9,9,9
Example output: 12/30 22:59

I was a bit dismayed to find that my previous answer, in Python, did not generalize very well to handle months of non-uniform lengths. I also considered @maxb's brute-force approach to be too inefficient. (This challenge involves permutations of 8 digits chosen out of 12, or 19958400 tries. Choosing 6 digits out of 9 for hh:mm:ss would only take 60480 tries.)

For an additional challenge, I decided to try using C++ instead of Python. I used C++11, but advice based on any recent version would also be welcome.

Concerns:

• Is the solution readable enough?
• Is the design of the iterator idiomatic for C++?
• Any memory-management faux pas? (The this->pool.substr() in desc2iter::unused() seems a bit wasteful. I feel like doing this->pool.c_str() + 2.)

---

#include <algorithm>
#include <cassert>
#include <cctype>
#include <iostream>
#include <string>
/**
 * An iterator to form all possible two-digit numbers in a range from a pool of
 * digits, producing results in descending order.
 */
class desc2iter {
 public:
 /**
 * Constructor.
 * max: The maximum allowable number to produce
 * min: The minimum allowable number to produce
 * pool: A pool of digits to use to form the numbers; each digit may be
 * used at most once.
 */
 desc2iter(int max, int min, const std::string& pool);
 /**
 * If there is a next (smaller) number in the sequence, return true, and
 * set the result to the number.
 */
 bool next(std::string &result);
 /**
 * Return the characters in the pool that have not been used to produce
 * the most recent result.
 */
 std::string unused() const;
 private:
 int n;
 const int min;
 std::string pool;
};
desc2iter::desc2iter(int max, int min, const std::string& pool) :
 n(max),
 min(min),
 pool(pool) {
 assert(0 <= max && max <= 99);
 assert(0 <= min && min <= max);
}
bool desc2iter::next(std::string &result) {
 if (this->pool.length() < 2) return false;
 for (; this->n >= this->min; this->n--) {
 // Take the tens digit from the pool, if it exists in the pool
 std::string::size_type t = this->pool.find('0' + (this->n / 10));
 if (t == std::string::npos) {
 this->n -= this->n % 10;
 continue;
 }
 std::swap(this->pool[0], this->pool[t]);
 // Take the ones digit from the pool, if it exists and is unused
 std::string::size_type o = this->pool.find('0' + (this->n % 10), 1);
 if (o != std::string::npos) {
 std::swap(this->pool[1], this->pool[o]);
 this->n--;
 result = this->pool.substr(0, 2);
 return true;
 }
 }
 return false;
}
std::string desc2iter::unused() const {
 return this->pool.length() >= 2 ? this->pool.substr(2) : "";
}
//////////////////////////////////////////////////////////////////////
/**
 * Form the latest possible datetime, in a non-leap year, using the given digit
 * characters, in "MM/DD hh:mm" format. Return an empty string if no valid
 * datetime can be formed.
 */
std::string max_datetime(const std::string& digits) {
 static const int month_lengths[] = {
 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
 };
 std::string MM, DD, hh, mm;
 for (desc2iter MM_it(12, 1, digits); MM_it.next(MM); ) {
 int month_len = month_lengths[std::stoi(MM)];
 for (desc2iter DD_it(month_len, 1, MM_it.unused()); DD_it.next(DD); ) {
 for (desc2iter hh_it(23, 0, DD_it.unused()); hh_it.next(hh); ) {
 for (desc2iter mm_it(59, 0, hh_it.unused()); mm_it.next(mm); ) {
 return MM + '/' + DD + ' ' + hh + ':' + mm;
 }
 }
 }
 }
 return "";
}
int main() {
 std::string input, answer;
 // Read input, keeping only digits
 std::getline(std::cin, input);
 input.erase(
 std::remove_if(input.begin(), input.end(), [](char c) {
 return !std::isdigit(c);
 }),
 input.end()
 );
 answer = max_datetime(input);
 std::cout << (answer.empty() ? "0" : answer) << '\n';
}

• Toby Speight: Do you know which year? (it matters if it has a leap second)
• 200_success: The linked challenge says 2018. But leap seconds shouldn't matter, since the output omits seconds.

Answer 1

Your code is quite good, but I believe it can be made more readable and idiomatic.

Iterator-based design

I find the question:

Is the design of the iterator idiomatic for C++?

a bit ambiguous because, whereas iterators are a building block of C++ programming, I would say that your program doesn't use them. You write a class named after them, but that doesn't offer an iterator's interface. It's a pity, because your intuition is very correct, and your algorithm can be implemented very elegantly with iterators (and without any memory allocation). The basic block would have this signature:

Iterator parse_digit(int digit, Iterator first, Iterator last);

If successful, parse_digit find the character corresponding to digit, swap it with the last character of the [first, last) range and return --last. If not, it returns last.

You can then compose parse_two_digits_number over it, and then your date parser.

Without further ado, here's what it would look like:

#include <string>
#include <algorithm>
#include <array>
#include <sstream>
#include <iomanip>
template <typename Iterator>
auto remove_digit(int digit, Iterator first, Iterator last) {
 auto it = std::find(first, last, '0'+digit);
 if (it != last) {
 std::iter_swap(it, std::prev(last));
 return std::prev(last);
 }
 else return last;
}
template <typename Iterator>
auto consume_two_digits_number(int n, Iterator first, Iterator last) {
 auto first_digit = remove_digit(n/10, first, last);
 if (first_digit != last) {
 auto second_digit = remove_digit(n%10, first, first_digit);
 if (second_digit != first_digit) return second_digit;
 }
 return last;
}
template <typename Iterator> 
std::string max_datetime(Iterator first, Iterator last) {
 static constexpr std::array month_lengths = 
 {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; 
 for (int month = 12; month >= 1; --month) {
 auto month_it = consume_two_digits_number(month, first, last);
 if (month_it == last) continue;
 for (int day = month_lengths[month]; day >= 1; --day) {
 auto day_it = consume_two_digits_number(day, first, month_it);
 if (day_it == month_it) continue;
 for (int hour = 23; hour >= 0; --hour) {
 auto hour_it = consume_two_digits_number(hour, first, day_it);
 if (hour_it == day_it) continue;
 for (int min = 59; min >= 0; --min) {
 auto min_it = consume_two_digits_number(min, first, hour_it);
 if (hour_it == min_it) continue;
 else {
 std::stringstream ss;
 ss << std::setfill('0') << std::setw(2) << month << '/' << day << ' ' << hour << ':' << min;
 return ss.str();
 }
 }
 }
 }
 }
 return ""; 
}

Miscellaneous

You'll also notice I replaced your month_lengths array by a std::array (more idiomatic -that said, I should have specified the type and the size, since deduction guides are a C++17 feature), and used a std::stringstream to compose the return string: it has abysmal performance, but it doesn't matter here and it's more readable.

• 200_success: I think it's awesome that you can just manipulate a single pool of characters.
• 200_success: In my opinion, each field of the output should be zero-padded to two digits. But that's easy to fix.
• papagaga: @200_success: fixed