Solution for parquet tiles coding exercise

stl_tiles.cpp

// Original 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 <cstddef>
#include <cstdint>
#include <format>
#include <iostream>
#include <numeric>
#include <vector>
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 vector<uint32_t> encoded_strips = get_all_encoded_strips();

    const size_t possible_strips = encoded_strips.size();

    { // diagnostic output
        cout << format("possible_strips: {}\n", possible_strips);

        size_t idx = 0;

        for (const auto& encoded_strip : encoded_strips) {
            cout << format("encoded_strips[{}]: {:032b}\n", idx, encoded_strip);
            if (++idx == 3) {
                break;
            }
        }

        cout << "                    ^ bit 30 (never set)          ^ bit 0\n";
        cout << "Note: This printing is big-endian, so bit 0 is rightmost.\n";
        cout << "Also: We don't set bit 30, because that's the final (outer) edge.\n";
    }

    vector<vector<size_t>> compatible_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].push_back(k);
                compatible_strips[k].push_back(i);
            }
        }
    }

    { // diagnostic output
        size_t idx = 0;

        for (const auto& compat : compatible_strips) {
            cout << format("compatible_strips[{}]: ", idx);
            for (const auto& elem : compat) {
                cout << format("{},", elem);
            }
            cout << "\n";
            if (++idx == 8) {
                break;
            }
        }
    }

    vector<uint64_t> valid_paths(possible_strips, 1);
    vector<uint64_t> next_paths(possible_strips, 0);

    // 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.

    for (int row_idx = 1; row_idx < num_strips; ++row_idx) { // we've completed row 0, start with row 1
        for (size_t i = 0; i < possible_strips; ++i) { // for the i'th possible strip,
            for (const auto& predecessor_idx : compatible_strips[i]) { // compatible_strips[i] are valid predecessors,
                next_paths[i] += valid_paths[predecessor_idx]; // so accumulate these paths. (Looks like matrix math.)
            }
        }

        valid_paths.swap(next_paths);
        fill(next_paths.begin(), next_paths.end(), 0);
    }

    // Time for the grand total!
    const uint64_t grand_total = accumulate(valid_paths.begin(), valid_paths.end(), uint64_t{0});
    cout << format("Grand Total: {}\n", grand_total);
}

/***
Output:

C:\Temp>cl /EHsc /nologo /W4 /MTd /std:c++latest stl_tiles.cpp
stl_tiles.cpp

C:\Temp>stl_tiles
possible_strips: 1897
encoded_strips[0]: 00010101010101010101010101010100
encoded_strips[1]: 00001001010101010101010101010100
encoded_strips[2]: 00001010010101010101010101010100
                    ^ bit 30 (never set)          ^ bit 0
Note: This printing is big-endian, so bit 0 is rightmost.
Also: We don't set bit 30, because that's the final (outer) edge.
compatible_strips[0]: 79,
compatible_strips[1]: 80,81,
compatible_strips[2]: 81,82,
compatible_strips[3]: 587,
compatible_strips[4]: 82,83,
compatible_strips[5]: 587,588,
compatible_strips[6]: 587,588,589,
compatible_strips[7]: 83,84,
Grand Total: 1007720438618812

***/