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

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.)

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() {

// 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()
);

}

• Do you know which year? (it matters if it has a leap second) Aug 20, 2018 at 7:48
• The linked challenge says 2018. But leap seconds shouldn't matter, since the output omits seconds. Aug 20, 2018 at 7:53

## 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.

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