brute force & iterative solution to the self-descriptive ten-digit base-ten number problem. generalized to N digits, base 10. (1 <= N <= 10)

digits.cpp

#include <iostream>
#include <iomanip>
#include <set>
#include <vector>

void printIt(uint64_t n, char s[11], size_t digits = 10) {
    char format[100];
    snprintf(format, 100, "%%0%dju", digits);
    snprintf(s, 11, format, n);
}

size_t occurrencesOf(char thisChar, const char* inThisString) {
    size_t ret = 0;
    const char* p = inThisString;
    for (const char* p = inThisString; *p != '\0'; ++p) {
        ret += (size_t)(*p == thisChar);
    }

    return ret;
}

bool approach1(uint64_t& answer) {
    uint64_t n = 0;

    //    n = 6210001000;

    size_t foundCount = 0;

    for (; n <= 9999999999; ++n) {
        char s[11];
        printIt(n, s);

        if (n % 10000000 == 0) {
            std::cout << s << ".." << std::endl;
        }


        bool found = true;
        for (char m = 0; m <= 9; ++m) {
            const char c = m + '0';
            const char expecting = s[m] - '0';
            if (occurrencesOf(c, s) != expecting) {
                found = false;
                continue;
            }
        }

        if (found) {
            foundCount += 1;
            std::cout << "vvvvvvvvvv-------------------------" << std::endl;
            std::cout << s << std::endl;
            std::cout << "^^^^^^^^^^-------------------------" << std::endl;
            answer = n;
        }
    }

    std::cout << "Found " << foundCount << " solutions" << std::endl;

    return foundCount > 0;
}

void toArray(uint64_t n, uint8_t arr[10]) {
    for (size_t i = 0; i < 10; ++i) {
        arr[9 - i] = n % 10;
        n = n / 10;
    }
}

uint64_t fromArray(const uint8_t arr[10]) {
    uint64_t ret = 0;
    for (uint8_t i = 0; i < 10; ++i) {
        ret *= 10;
        ret += arr[i];
    }

    return ret;
}

size_t occurrencesOf(uint8_t needle, uint8_t haystack[10]) {
    size_t ret = 0;
    for (uint8_t n = 0; n < 10; ++n) {
        ret += (size_t)(haystack[n] == needle);
    }
    return ret;
}

bool approach2(uint64_t &answer) {

    uint64_t n = 9000000000;

    std::set<uint64_t> seen;

    bool keepGoing = true;

    while (keepGoing) {
        if (seen.find(n) != seen.end()) {
            std::cout << "stuck in a loop on " << n << std::endl;
            keepGoing = false;
        }
        else {
            seen.insert(n);

            uint8_t arr[10];
            toArray(n, arr);
            bool valid = true;
            for (uint8_t m = 0; m < 10; ++m) {
                size_t occurrences = occurrencesOf(m, arr);
                bool validDigit = (occurrences == arr[m]);
                if (!validDigit) {
                    valid = false;
                    arr[m] = (uint8_t)occurrences;
                }
            }
            if (valid) {
                answer = n;
                return true;
            }
            else {
                n = fromArray(arr);
            }
        }
    }

    return false;
}

uint64_t fromVec(const std::vector<uint8_t>vec) {
    uint64_t ret = 0;
    for (size_t n = 0; n < vec.size(); ++n) {
        ret *= 10;
        ret += vec[n];
    }

    return ret;
}

void toVec(uint64_t val, std::vector<uint8_t> &vec) {
    for (size_t n = 0; n < vec.size(); ++n) {
        vec[vec.size() - 1 - n] = val % 10;
        val /= 10;
    }
}

size_t occurrencesOf(uint8_t needle, const std::vector<uint8_t>& haystack) {
    size_t ret = 0;
    for (size_t n = 0; n < haystack.size(); ++n) {
        ret += (size_t)(haystack[n] == needle);
    }

    return ret;
}

// brute force but without sprintf
// performance is similar to brute force w/ printf.
bool approach3(uint8_t digits, uint64_t& answer) {
    std::vector<uint8_t> asVec;
    asVec.reserve(digits);

    for (size_t n = 0; n < digits; ++n) {
        asVec.push_back(9);
    }

    uint64_t maxValue = fromVec(asVec);

    bool ret = false;

    for (uint64_t value = 0; value <= maxValue; ++value) {
        if (value % 10000000 == 0) {
            char s[11];
            printIt(value, s, digits);
            std::cout << s << std::endl;
        }
        toVec(value, asVec);

        bool valid = true;
        for (size_t n = 0; n < digits; ++n) {
            size_t occurrences = occurrencesOf((uint8_t)n, asVec);
            if (asVec[n] != occurrences) {
                valid = false;
                continue;
            }
        }

        if (valid) {
            ret = true;
            answer = value;
            std::cout << "vvvvvvvvvv-------------------------" << std::endl;
            std::cout << value << std::endl;
            std::cout << "^^^^^^^^^^-------------------------" << std::endl;
        }
    }

    return ret;
}

// variable number of digits, iterate.
bool approach4(uint8_t digits, uint64_t& answer) {
    bool ret = false;

    for (size_t pass = 1; pass <= 2; ++pass) {
        std::set<uint64_t> seen;
        bool keepGoing = true;

        std::vector<uint8_t> asVec;
        asVec.reserve(digits);

        // this doesn't matter.
        asVec.push_back(digits - 1);
        for (size_t n = 1; n < digits; ++n) {
            asVec.push_back(0);
        }
        while (keepGoing) {
            uint64_t value = fromVec(asVec);

            if (seen.find(value) != seen.end()) {
                //  std::cout << "stuck in a loop on " << value << std::endl;
                keepGoing = false;
            }
            else {
                seen.insert(value);

                bool valid = true;
                std::vector<uint8_t> vecCopy = asVec;
                for (uint8_t m = 0; m < digits; ++m) {
                    size_t occurrences;
                    bool validDigit;
                    if (pass == 1) {
                        occurrences = occurrencesOf(m, vecCopy);
                        validDigit = (occurrences == vecCopy[m]);
                    }
                    else {
                        occurrences = occurrencesOf(m, asVec);
                        validDigit = (occurrences == asVec[m]);
                    }
                    if (!validDigit) {
                        valid = false;
                        asVec[m] = (uint8_t)occurrences;
                    }
                }
                if (valid) {
                    answer = value;
                    return true;
                }
            }
        }
    }

    return ret;
}
int main()
{
    uint8_t digits = 5;
    uint64_t answer;

    for (digits = 1; digits <= 10; digits += 1) {
        bool found = approach4(digits, answer);
        std::cout << std::setw(2) << (int)digits << " : ";
        if (found) {
            std::cout << answer;
        }
        else {
            std::cout << "---";
        }
        std::cout << std::endl;
    }

    //  1 - 0
    //  2 - 0
    //  3 - 0
    //  4 - 2
    //  5 - 1
    //  6 - 0
    //  7 - 1
    //  8 - 1
    //  9 - 1
    // 10 - 1

    /*

    if (found) {
        char s[11];
        printIt(answer, s, digits);
        std::cout << "found answer: " << s << std::endl;
    }
    else {
        std::cout << "no answer." << std::endl;
    }
    */
}