magic_sequence.cpp

/*
 * @brief [Magic sequence](https://www.csplib.org/Problems/prob019/)
 * implementation
 *
 * @details Solve the magic sequence problem with backtracking
 *
 * "A magic sequence of length $n$ is a sequence of integers $x_0
 * \ldots x_{n-1}$ between $0$ and $n-1$, such that for all $i$
 * in $0$ to $n-1$, the number $i$ occurs exactly $x_i$ times in
 * the sequence. For instance, $6,2,1,0,0,0,1,0,0,0$ is a magic
 * sequence since $0$ occurs $6$ times in it, $1$ occurs twice, etc."
 * Quote taken from the [CSPLib](https://www.csplib.org/Problems/prob019/)
 * website
 *
 * @author [Jxtopher](https://github.com/Jxtopher)
 */

#include <algorithm>  /// for std::count
#include <cassert>    /// for assert
#include <iostream>   /// for IO operations
#include <list>       /// for std::list
#include <numeric>    /// for std::accumulate
#include <vector>     /// for std::vector

/**
 * @namespace backtracking
 * @brief Backtracking algorithms
 */
namespace backtracking {
/**
 * @namespace magic_sequence
 * @brief Functions for the [Magic
 * sequence](https://www.csplib.org/Problems/prob019/) implementation
 */
namespace magic_sequence {
using sequence_t =
    std::vector<unsigned int>;  ///< Definition of the sequence type
/**
 * @brief Print the magic sequence
 * @param s working memory for the sequence
 */
void print(const sequence_t& s) {
    for (const auto& item : s) std::cout << item << " ";
    std::cout << std::endl;
}

/**
 * @brief Check if the sequence is magic
 * @param s working memory for the sequence
 * @returns true if it's a magic sequence
 * @returns false if it's NOT a magic sequence
 */
bool is_magic(const sequence_t& s) {
    for (unsigned int i = 0; i < s.size(); i++) {
        if (std::count(s.cbegin(), s.cend(), i) != s[i]) {
            return false;
        }
    }
    return true;
}

/**
 * @brief Sub-solutions filtering
 * @param s working memory for the sequence
 * @param depth current depth in tree
 * @returns true if the sub-solution is valid
 * @returns false if the sub-solution is NOT valid
 */
bool filtering(const sequence_t& s, unsigned int depth) {
    return std::accumulate(s.cbegin(), s.cbegin() + depth,
                           static_cast<unsigned int>(0)) <= s.size();
}

/**
 * @brief Solve the Magic Sequence problem
 * @param s working memory for the sequence
 * @param ret list of the valid magic sequences
 * @param depth current depth in the tree
 */
void solve(sequence_t* s, std::list<sequence_t>* ret, unsigned int depth = 0) {
    if (depth == s->size()) {
        if (is_magic(*s)) {
            ret->push_back(*s);
        }
    } else {
        for (unsigned int i = 0; i < s->size(); i++) {
            (*s)[depth] = i;
            if (filtering(*s, depth + 1)) {
                solve(s, ret, depth + 1);
            }
        }
    }
}

}  // namespace magic_sequence
}  // namespace backtracking

/**
 * @brief Self-test implementations
 * @returns void
 */
static void test() {
    // test a valid magic sequence
    backtracking::magic_sequence::sequence_t s_magic = {6, 2, 1, 0, 0,
                                                        0, 1, 0, 0, 0};
    assert(backtracking::magic_sequence::is_magic(s_magic));

    // test a non-valid magic sequence
    backtracking::magic_sequence::sequence_t s_not_magic = {5, 2, 1, 0, 0,
                                                            0, 1, 0, 0, 0};
    assert(!backtracking::magic_sequence::is_magic(s_not_magic));
}

/**
 * @brief Main function
 * @returns 0 on exit
 */
int main() {
    test();  // run self-test implementations

    // solve magic sequences of size 2 to 11 and print the solutions
    for (unsigned int i = 2; i < 12; i++) {
        std::cout << "Solution for n = " << i << std::endl;
        // valid magic sequence list
        std::list<backtracking::magic_sequence::sequence_t> list_of_solutions;
        // initialization of a sequence
        backtracking::magic_sequence::sequence_t s1(i, i);
        // launch of solving the problem
        backtracking::magic_sequence::solve(&s1, &list_of_solutions);
        // print solutions
        for (const auto& item : list_of_solutions) {
            backtracking::magic_sequence::print(item);
        }
    }
    return 0;
}