11
\$\begingroup\$

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';
}
\$\endgroup\$
  • \$\begingroup\$ Do you know which year? (it matters if it has a leap second) \$\endgroup\$ – Toby Speight Aug 20 '18 at 7:48
  • \$\begingroup\$ The linked challenge says 2018. But leap seconds shouldn't matter, since the output omits seconds. \$\endgroup\$ – 200_success Aug 20 '18 at 7:53
8
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.