C++ Implementation of Crazy Bob Lee's clever solution to a coding challenge

crazyboblee.cpp

// In honor of Crazy Bob Lee who was tragically murdered today
// https://www.beust.com/weblog/coding-challenge/
// I've ported his genius code to C++ and also created a non-recursive version, which is slightly faster on my system

// write a counter function that counts from 1 to max but only returns numbers whose digits don’t repeat.
// For example, part of the output would be:
// 8, 9, 10, 12 (11 is not valid)
// 98, 102, 103 (99, 100 and 101 are not valid)
// 5432, 5436, 5437 (5433, 5434 and 5435 are not valid)
// Also:
// Display the biggest jump (in the sequences above, it’s 4: 98 -> 102)
// Display the total count of numbers
// Give these two values for max=10000

#include <iostream>
#include <functional>
#include <iostream>
#include <functional>
#include <vector>
#include <execution>
#include <mutex>
#include <algorithm>
#include <iostream>
#include <chrono>
#include <stack>
#include <tuple>

using namespace std::chrono;

class ExecutionTimer
{
public:
    // Use the best steady clock available
    using Clock = std::conditional_t<high_resolution_clock::is_steady,
        high_resolution_clock,
        steady_clock>;

    ExecutionTimer() = default;
    inline ~ExecutionTimer()
    {
        std::string units = " microSeconds";
        // Determine whether to print uSecs or mSecs or Secs
        double count = duration_cast<microseconds>(Clock::now() - mStart).count();
        if (count > 1000)
        {
            // Convert to milliseconds
            units = " milliSeconds";
            count /= 1000.0f;
            if (count > 1000)
            {
                // Convert to seconds
                units = " Seconds";
                count /= 1000.0f;
            }
        }

        std::cout
            << "Elapsed: " << count << units.data() << std::endl;
    }
private:
    Clock::time_point mStart = Clock::now();
};

constexpr long long max = 10000000000;


#include <iostream>
#include <functional>
#include <memory>

class Digit : public std::enable_shared_from_this<Digit> {
public:
    int value;
    std::shared_ptr<Digit> previous;
    std::shared_ptr<Digit> next;

    static std::shared_ptr<Digit> create(std::shared_ptr<Digit> previous, int value) {
        auto new_digit = std::shared_ptr<Digit>(new Digit(previous, value));
        if (value < 9) {
            new_digit->next = create(new_digit, value + 1);
        }
        return new_digit;
    }

private:
    Digit(std::shared_ptr<Digit> previous, int value)
        : value(value), previous(previous) {
    }

public:
    void use() {
        if (previous) previous->next = next;
        if (next) next->previous = previous;
    }

    void yield() {
        if (previous) previous->next = shared_from_this();
        if (next) next->previous = shared_from_this();
    }
};



bool find3(const std::shared_ptr<Digit>& start, const std::shared_ptr<Digit>& head, int remaining, long long value, long long max, const std::function<void(long long)>& listener) 
{
    for (auto current = start; current != nullptr; current = current->next) 
    {
        long long newValue = value + current->value;
        if (remaining == 1) 
        {
            if (newValue > max) return true;
            listener(newValue);
        }
        else
        {
            current->use();
            auto newHead = (current == head) ? head->next : head;
            if (find3(newHead, newHead, remaining - 1, newValue * 10, max, listener)) 
            {
                return true;
            }
            current->yield();
        }
    }
    return false;
}

void findAll3(const std::function<void(long long)>& listener) 
{
    auto zero = Digit::create(nullptr, 0);
    auto one = zero->next;
    for (int length = 1; length <= 10; length++) {
        if (find3(one, zero, length, 0, max, listener)) return;
    }
}


bool find2(const int& first, const int& remaining, long long value, const int& used, const std::function<void(long long)>& listener)
{
    std::stack<std::tuple<int, int, long long, int>> stack;
    stack.push({ first, remaining, value, used });

    while (!stack.empty())
    {
        auto [cur_first, cur_remaining, cur_value, cur_used] = stack.top();
        stack.pop();

        int mask = 0;
        for (int digit = cur_first; digit < 10; ++digit, ++cur_value)
        {
            mask = 1 << digit;
            if (!(cur_used & mask))
            {
                if (cur_remaining == 1)
                {
                    listener(cur_value);
                }
                else
                {
                    stack.push({ 0, cur_remaining - 1, cur_value * 10, cur_used | mask });
                }
            }
        }
    }
    return false;
}

void findAll2(const std::function<void(long long)>& listener)
{
    for (int length = 1; length < 11; length++)
    {
        if (find2(1, length, 1, 0, listener))
            return;
    }
}

bool find(const int &first, const int &remaining, long long value, const int &used, const std::function<void(long long)>& listener)
{
    static int total = 0;
    total++;
    int mask = 0;
    for (int digit = first; digit < 10; ++digit, ++value)
    {
        mask = 1 << digit;
        if (!(used & mask))
        {
            if (remaining == 1)
                listener(value);
            else 
                find(0, remaining - 1, value * 10, used | mask, listener);
        }
    }
    return false;
}

void findAll(const std::function<void(long long)>& listener) 
{
    for (int length = 1; length < 11; length++) 
    {
        if (find(1, length, 1, 0, listener)) 
            return;
    }
}

int main()
{
    //std::vector<long long> results{};
    //results.reserve(9000000);
    static int i = 0;

    auto listener = [&](long long value)
    {
        i++;
        //results.push_back(value);
    };
    {
        ExecutionTimer tm;
        findAll(listener);
    }
    std::cout << i << " Results" << std::endl;

    i = 0;
    {
        ExecutionTimer tm;
        findAll3(listener);
    }
    std::cout << i << " Linked List Results" << std::endl;

    //std::cout << "Results contains " << results.size() << std::endl;
    //results.clear();
    i = 0;
    {
        ExecutionTimer tm;
        findAll2(listener);
    }
    std::cout << i << " Non recursive Results" << std::endl;
    ///std::cout << "Non recursive Results contains " << results.size() << std::endl;
    std::cout << "Done" << std::endl;
    return 0;
}