Boost.uBLAS solution for parquet tiles coding exercise

boost_ublas.cpp

// Boost.uBLAS solution by Stephan T. Lavavej
// for https://www.reddit.com/r/cpp/comments/z1xich/c_interview_coding_exercise_with_solution/

#include <algorithm>
#include <cassert>
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <format>
#include <iostream>
#include <numeric>
#include <vector>
#include <boost/numeric/ublas/matrix_sparse.hpp>
#include <boost/numeric/ublas/vector.hpp>
using namespace std;

constexpr int total_length{30};

constexpr int num_strips{11};

[[nodiscard]] constexpr uint32_t encode_strip(const vector<int>& strip) {
    uint32_t bits{0u};
    int sum{0};

    assert(!strip.empty());
    for (auto it = strip.begin(), stop = strip.end() - 1; it != stop; ++it) { // stop before the final (outer) edge
        sum += *it;
        assert(sum < 32);
        bits |= 1u << sum;
    }

    return bits;
}

constexpr void add_permutations(vector<uint32_t>& encoded_strips, const int twos, const int threes) {
    vector<int> strip(twos + threes);
    fill(strip.begin(), strip.begin() + twos, 2);
    fill(strip.begin() + twos, strip.end(), 3);
    assert(is_sorted(strip.begin(), strip.end()));

    do {
        encoded_strips.push_back(encode_strip(strip));
    } while (next_permutation(strip.begin(), strip.end()));
}

[[nodiscard]] constexpr vector<uint32_t> get_all_encoded_strips() {
    vector<uint32_t> encoded_strips;

    for (int threes = 0; threes * 3 <= total_length; threes += 2) { // micro-optimization, due to parity
        const int remaining_length = total_length - threes * 3;
        assert(remaining_length % 2 == 0);
        add_permutations(encoded_strips, remaining_length / 2, threes);
    }

    return encoded_strips;
}

int main() {
    const auto start = chrono::steady_clock::now();

    const vector<uint32_t> encoded_strips = get_all_encoded_strips();

    const size_t possible_strips = encoded_strips.size();

    namespace ublas = boost::numeric::ublas;

    ublas::compressed_matrix<uint64_t> compatible_strips(possible_strips, possible_strips);

    // Inefficient O(N^2) solution, where N is the number of possible strips.
    // I'm sure there are cleverer ways to do this.
    for (size_t i = 0; i < possible_strips; ++i) {
        for (size_t k = i + 1; k < possible_strips; ++k) {
            if ((encoded_strips[i] & encoded_strips[k]) == 0u) { // they're compatible!
                compatible_strips(i, k) = 1;
                compatible_strips(k, i) = 1; // this is a symmetric matrix
            }
        }
    }

    // For the first row of the floor, we can choose any possible strip.
    // After completing it, we record how many choice-paths led to it.
    // By definition, there's 1 path for each possible choice for the first row.
    ublas::vector<uint64_t> valid_paths{ublas::scalar_vector<uint64_t>{possible_strips, 1}};

    for (int row_idx = 1; row_idx < num_strips; ++row_idx) { // we've completed row 0, start with row 1
        valid_paths = ublas::prod(compatible_strips, valid_paths);
    }

    const uint64_t grand_total = accumulate(valid_paths.begin(), valid_paths.end(), uint64_t{0});
    cout << format("Boost.uBLAS Grand Total: {}\n", grand_total);

    const auto finish = chrono::steady_clock::now();
    cout << chrono::duration_cast<chrono::milliseconds>(finish - start) << "\n";
}