Skip to content

Instantly share code, notes, and snippets.

@StephanTLavavej
Created November 23, 2022 05:53
Show Gist options
  • Save StephanTLavavej/726b4f8139f8b45fb2f05b5d29e9eedd to your computer and use it in GitHub Desktop.
Save StephanTLavavej/726b4f8139f8b45fb2f05b5d29e9eedd to your computer and use it in GitHub Desktop.
Boost.uBLAS solution for parquet tiles coding exercise
// 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";
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment