Codex instance
39ff5cb340
Full-height skyline columns partition the remaining board. Add sound gcd and bounded subset-sum checks for the resulting component areas, with boundary-event and periodic benchmark schedules. Keep the rules disabled by default because their small tree reductions do not recover their measured cost. Record the rejected default and scheduling evidence so it can be revisited only with new data. Tests: Debug CTest (14 passed) Tests: ASan+UBSan CTest (14 passed) Refs: #13
811 lines
32 KiB
C++
811 lines
32 KiB
C++
/*
|
|
* Copyright 2025, Matthew Gretton-Dann
|
|
* SPDX-License-Identifier: Apache-2.0
|
|
*/
|
|
|
|
#define PARTRIDGE_TESTING
|
|
#include "../main.cc"
|
|
|
|
#include <algorithm>
|
|
#include <array>
|
|
#include <span>
|
|
#include <sstream>
|
|
#include <string>
|
|
|
|
namespace {
|
|
struct Placement {
|
|
std::uint64_t x;
|
|
std::uint64_t y;
|
|
std::uint64_t side;
|
|
|
|
auto operator==(Placement const &) const noexcept -> bool = default;
|
|
};
|
|
|
|
struct Validation {
|
|
std::vector<std::string> diagnostics;
|
|
|
|
[[nodiscard]] auto valid() const noexcept -> bool { return diagnostics.empty(); }
|
|
|
|
[[nodiscard]] auto text() const -> std::string {
|
|
std::ostringstream result;
|
|
for (auto const &diagnostic: diagnostics) {
|
|
result << diagnostic << '\n';
|
|
}
|
|
return result.str();
|
|
}
|
|
};
|
|
|
|
struct IndependentResult {
|
|
std::uint64_t width;
|
|
std::uint64_t height;
|
|
std::vector<Placement> placements;
|
|
};
|
|
|
|
auto describe(std::size_t index, Placement const &placement) -> std::string {
|
|
return "placement " + std::to_string(index) + " at (" +
|
|
std::to_string(placement.x) + ", " + std::to_string(placement.y) +
|
|
") with side " + std::to_string(placement.side);
|
|
}
|
|
|
|
auto validate(std::uint64_t order, std::uint64_t width, std::uint64_t height,
|
|
std::vector<Placement> const &placements) -> Validation {
|
|
Validation result;
|
|
auto const expected_side = order * (order + 1) / 2;
|
|
if (width != expected_side || height != expected_side) {
|
|
result.diagnostics.emplace_back(
|
|
"board dimensions must both equal the triangular number for the order");
|
|
}
|
|
|
|
std::vector<std::uint64_t> multiplicities(order + 1);
|
|
std::vector<int> occupied(width * height, -1);
|
|
for (std::size_t index = 0; index < placements.size(); ++index) {
|
|
auto const &placement = placements[index];
|
|
if (placement.side == 0 || placement.side > order) {
|
|
result.diagnostics.push_back(describe(index, placement) +
|
|
" has an invalid side length");
|
|
continue;
|
|
}
|
|
++multiplicities[placement.side];
|
|
|
|
if (placement.x >= width || placement.y >= height ||
|
|
placement.side > width - placement.x ||
|
|
placement.side > height - placement.y) {
|
|
result.diagnostics.push_back(describe(index, placement) +
|
|
" is outside the board bounds");
|
|
continue;
|
|
}
|
|
|
|
int overlapping_placement = -1;
|
|
for (auto y = placement.y; y < placement.y + placement.side; ++y) {
|
|
for (auto x = placement.x; x < placement.x + placement.side; ++x) {
|
|
auto &cell = occupied[x + y * width];
|
|
if (cell != -1) {
|
|
overlapping_placement = cell;
|
|
} else {
|
|
cell = static_cast<int>(index);
|
|
}
|
|
}
|
|
}
|
|
if (overlapping_placement != -1) {
|
|
result.diagnostics.push_back(
|
|
describe(index, placement) + " overlaps placement " +
|
|
std::to_string(overlapping_placement));
|
|
}
|
|
}
|
|
|
|
for (std::uint64_t side = 1; side <= order; ++side) {
|
|
if (multiplicities[side] != side) {
|
|
result.diagnostics.push_back(
|
|
"side " + std::to_string(side) + " has multiplicity " +
|
|
std::to_string(multiplicities[side]) + "; expected " +
|
|
std::to_string(side));
|
|
}
|
|
}
|
|
|
|
if (std::ranges::find(occupied, -1) != occupied.end()) {
|
|
result.diagnostics.emplace_back("board is not completely covered");
|
|
}
|
|
return result;
|
|
}
|
|
|
|
auto to_independent(Results const &result) -> IndependentResult {
|
|
IndependentResult converted{result.length(), result.length(), {}};
|
|
converted.placements.reserve(result.squares().size());
|
|
for (auto const &square: result.squares()) {
|
|
converted.placements.push_back({
|
|
square.pos() % result.length(),
|
|
square.pos() / result.length(),
|
|
square.length(),
|
|
});
|
|
}
|
|
return converted;
|
|
}
|
|
|
|
auto validate(std::uint64_t order, Results const &result) -> Validation {
|
|
auto const converted = to_independent(result);
|
|
return validate(order, converted.width, converted.height,
|
|
converted.placements);
|
|
}
|
|
|
|
auto known_order_8() -> std::vector<Placement> {
|
|
return {
|
|
{0, 0, 8}, {8, 0, 8}, {16, 0, 8}, {24, 0, 8},
|
|
{32, 0, 4}, {32, 4, 4}, {0, 8, 8}, {8, 8, 8},
|
|
{16, 8, 8}, {24, 8, 6}, {30, 8, 6}, {24, 14, 5},
|
|
{29, 14, 7}, {0, 16, 6}, {6, 16, 3}, {9, 16, 8},
|
|
{17, 16, 7}, {6, 19, 3}, {24, 19, 5}, {29, 21, 7},
|
|
{0, 22, 7}, {7, 22, 2}, {17, 23, 1}, {18, 23, 6},
|
|
{7, 24, 6}, {13, 24, 5}, {24, 24, 5}, {29, 28, 3},
|
|
{32, 28, 4}, {0, 29, 7}, {13, 29, 7}, {20, 29, 7},
|
|
{27, 29, 2}, {7, 30, 6}, {27, 31, 5}, {32, 32, 4},
|
|
};
|
|
}
|
|
|
|
auto renderable_result(std::uint64_t side,
|
|
std::vector<Placement> const &placements) -> Results {
|
|
std::vector<Square> squares;
|
|
squares.reserve(placements.size());
|
|
for (auto const &placement: placements) {
|
|
squares.emplace_back(placement.x + placement.y * side, placement.side);
|
|
}
|
|
return Results(side, std::move(squares));
|
|
}
|
|
|
|
auto expect(bool condition, std::string const &message) -> int {
|
|
if (condition) {
|
|
return 0;
|
|
}
|
|
std::cerr << "FAIL: " << message << '\n';
|
|
return 1;
|
|
}
|
|
|
|
auto has(Validation const &validation, std::string_view diagnostic) -> bool {
|
|
return std::ranges::any_of(validation.diagnostics,
|
|
[diagnostic](std::string const &candidate) {
|
|
return candidate.find(diagnostic) != std::string::npos;
|
|
});
|
|
}
|
|
|
|
auto d4_orbit(Placement const &placement, std::uint64_t const length)
|
|
-> std::array<Placement, 8> {
|
|
auto const far_x = length - 1 - placement.x;
|
|
auto const far_y = length - 1 - placement.y;
|
|
return {{
|
|
{placement.x, placement.y, placement.side},
|
|
{far_y, placement.x, placement.side},
|
|
{far_x, far_y, placement.side},
|
|
{placement.y, far_x, placement.side},
|
|
{far_x, placement.y, placement.side},
|
|
{far_y, far_x, placement.side},
|
|
{placement.x, far_y, placement.side},
|
|
{placement.y, placement.x, placement.side},
|
|
}};
|
|
}
|
|
|
|
auto canonical_members(Placement const &placement, std::uint64_t const length)
|
|
-> std::vector<Placement> {
|
|
auto orbit = d4_orbit(placement, length);
|
|
std::vector<Placement> members;
|
|
for (auto const &member: orbit) {
|
|
if (canonical_unit_position(member.x, member.y, length) &&
|
|
std::ranges::find(members, member) == members.end()) {
|
|
members.push_back(member);
|
|
}
|
|
}
|
|
return members;
|
|
}
|
|
|
|
auto test_validator() -> int {
|
|
int failures = 0;
|
|
auto const valid = known_order_8();
|
|
auto validation = validate(8, 36, 36, valid);
|
|
failures += expect(validation.valid(),
|
|
"known order-8 solution was rejected:\n" + validation.text());
|
|
|
|
validation = validate(8, 35, 36, valid);
|
|
failures += expect(has(validation, "dimensions"),
|
|
"invalid board dimensions were not diagnosed");
|
|
|
|
auto invalid = valid;
|
|
invalid.pop_back();
|
|
validation = validate(8, 36, 36, invalid);
|
|
failures += expect(has(validation, "side 4 has multiplicity 3; expected 4"),
|
|
"invalid square multiplicity lacked side and counts");
|
|
failures += expect(has(validation, "completely covered"),
|
|
"incomplete coverage was not diagnosed");
|
|
|
|
invalid = valid;
|
|
invalid.front().x = 36;
|
|
validation = validate(8, 36, 36, invalid);
|
|
failures += expect(
|
|
has(validation,
|
|
"placement 0 at (36, 0) with side 8 is outside the board bounds"),
|
|
"out-of-bounds diagnostic lacked placement details");
|
|
|
|
invalid = valid;
|
|
invalid[1].x = invalid[0].x;
|
|
invalid[1].y = invalid[0].y;
|
|
validation = validate(8, 36, 36, invalid);
|
|
failures += expect(
|
|
has(validation,
|
|
"placement 1 at (0, 0) with side 8 overlaps placement 0"),
|
|
"overlap diagnostic lacked placement details");
|
|
|
|
invalid = valid;
|
|
invalid.front().side = 9;
|
|
validation = validate(8, 36, 36, invalid);
|
|
failures += expect(
|
|
has(validation,
|
|
"placement 0 at (0, 0) with side 9 has an invalid side length"),
|
|
"invalid-side diagnostic lacked placement details");
|
|
return failures;
|
|
}
|
|
|
|
auto test_construction() -> int {
|
|
auto predecessor = renderable_result(36, known_order_8());
|
|
auto const predecessor_count = predecessor.squares().size();
|
|
auto const constructed = construct_odd_solution(9, std::move(predecessor));
|
|
auto const converted = to_independent(constructed);
|
|
auto const validation = validate(9, constructed);
|
|
|
|
int failures = 0;
|
|
failures += expect(
|
|
validation.valid(),
|
|
"even-to-odd construction was rejected:\n" + validation.text());
|
|
failures += expect(constructed.length() == 45,
|
|
"constructed board has the wrong side length");
|
|
failures += expect(converted.placements.size() == predecessor_count + 9,
|
|
"construction did not add exactly nine squares");
|
|
|
|
auto const expected_border = std::array<Placement, 9>{{
|
|
{36, 0, 9}, {36, 9, 9}, {36, 18, 9}, {36, 27, 9},
|
|
{0, 36, 9}, {9, 36, 9}, {18, 36, 9}, {27, 36, 9},
|
|
{36, 36, 9},
|
|
}};
|
|
failures += expect(
|
|
std::ranges::equal(
|
|
std::span(converted.placements).subspan(predecessor_count),
|
|
expected_border),
|
|
"constructed border coordinates are incorrect");
|
|
failures += expect(
|
|
std::ranges::equal(
|
|
std::span(converted.placements).first(predecessor_count),
|
|
known_order_8()),
|
|
"construction translated predecessor coordinates unexpectedly");
|
|
return failures;
|
|
}
|
|
|
|
auto test_odd_solver_route() -> int {
|
|
SearchCounters even_counters;
|
|
SearchCounters odd_counters;
|
|
auto const even =
|
|
find_solution_instrumented(8, even_counters, SearchPolicy::best_fit);
|
|
auto const odd =
|
|
find_solution_instrumented(9, odd_counters, SearchPolicy::best_fit);
|
|
|
|
int failures = 0;
|
|
failures += expect(
|
|
!uses_odd_construction(1) && !uses_odd_construction(7) &&
|
|
!uses_odd_construction(8) && uses_odd_construction(9) &&
|
|
!uses_odd_construction(10) && uses_odd_construction(11),
|
|
"odd construction route does not preserve direct handling boundaries");
|
|
auto const validation = validate(9, odd);
|
|
failures += expect(validation.valid(),
|
|
"order-9 routed result is invalid:\n" + validation.text());
|
|
failures += expect(odd.squares().size() == even.squares().size() + 9,
|
|
"order-9 route did not construct from order 8");
|
|
failures += expect(
|
|
odd_counters.search_nodes == even_counters.search_nodes &&
|
|
odd_counters.loop_iterations == even_counters.loop_iterations &&
|
|
odd_counters.attempted_placements ==
|
|
even_counters.attempted_placements &&
|
|
odd_counters.backtracks == even_counters.backtracks,
|
|
"order-9 route did not perform exactly the order-8 search");
|
|
return failures;
|
|
}
|
|
|
|
auto test_rendering() -> int {
|
|
auto const result = renderable_result(36, known_order_8());
|
|
std::ostringstream rendered;
|
|
auto *const original_buffer = std::cout.rdbuf(rendered.rdbuf());
|
|
result.output();
|
|
std::cout.rdbuf(original_buffer);
|
|
|
|
int failures = 0;
|
|
std::istringstream lines(rendered.str());
|
|
std::string line;
|
|
std::uint64_t line_count = 0;
|
|
while (std::getline(lines, line)) {
|
|
++line_count;
|
|
failures += expect(line.size() == result.length(),
|
|
"rendered row has incorrect width");
|
|
failures += expect(line.find('.') == std::string::npos,
|
|
"valid solution left an unrendered cell");
|
|
}
|
|
failures += expect(line_count == result.length(),
|
|
"rendered output has incorrect height");
|
|
return failures;
|
|
}
|
|
|
|
auto test_small_solver() -> int {
|
|
int failures = 0;
|
|
for (auto const order: std::array<std::uint64_t, 2>{2, 3}) {
|
|
auto const solution = find_solution(order);
|
|
auto const converted = to_independent(solution);
|
|
auto const expected_side = order * (order + 1) / 2;
|
|
failures += expect(converted.width == expected_side &&
|
|
converted.height == expected_side,
|
|
"result adapter returned incorrect board dimensions");
|
|
failures += expect(!has(validate(order, solution), "dimensions"),
|
|
"result adapter supplied invalid validator dimensions");
|
|
failures += expect(converted.placements.empty(),
|
|
"solver reported a solution for an unsatisfiable order");
|
|
}
|
|
|
|
Results const encoded(10, {Square(23, 2)});
|
|
auto const converted = to_independent(encoded);
|
|
failures += expect(
|
|
converted.width == 10 && converted.height == 10 &&
|
|
converted.placements.size() == 1 &&
|
|
converted.placements.front().x == 3 &&
|
|
converted.placements.front().y == 2 &&
|
|
converted.placements.front().side == 2,
|
|
"result adapter did not convert encoded placement coordinates");
|
|
return failures;
|
|
}
|
|
|
|
auto test_search_counters() -> int {
|
|
SearchCounters counters;
|
|
auto const solution = find_solution_instrumented(2, counters);
|
|
int failures = 0;
|
|
failures += expect(solution.squares().empty(),
|
|
"instrumented solver changed an infeasible result");
|
|
failures += expect(counters.search_nodes > 0 &&
|
|
counters.loop_iterations >= counters.search_nodes,
|
|
"instrumented solver did not count search work");
|
|
failures += expect(counters.attempted_placements > 0 &&
|
|
counters.backtracks > 0,
|
|
"instrumented solver did not count placements/backtracks");
|
|
failures += expect(counters.prune_checks >= counters.prune_hits &&
|
|
counters.valley_capacity_checks >=
|
|
counters.valley_capacity_prunes &&
|
|
counters.large_square_checks >=
|
|
counters.large_square_prunes &&
|
|
counters.component_area_checks >=
|
|
counters.component_area_prunes &&
|
|
counters.component_area_prunes ==
|
|
counters.component_gcd_prunes +
|
|
counters.component_subset_prunes &&
|
|
counters.generated_tasks == 0 &&
|
|
counters.completed_tasks == 0,
|
|
"search counters are inconsistent");
|
|
return failures;
|
|
}
|
|
|
|
auto test_d4_symmetry() -> int {
|
|
int failures = 0;
|
|
|
|
// A generic cell has eight distinct images: identity, three rotations,
|
|
// and four reflected rotations. Exactly one must survive.
|
|
auto const generic = d4_orbit({5, 9, 1}, 36);
|
|
auto distinct_generic = std::vector<Placement>(generic.begin(),
|
|
generic.end());
|
|
std::ranges::sort(
|
|
distinct_generic, {}, [](Placement const &placement) {
|
|
return std::array{placement.x, placement.y};
|
|
});
|
|
distinct_generic.erase(
|
|
std::ranges::unique(distinct_generic).begin(),
|
|
distinct_generic.end());
|
|
failures += expect(distinct_generic.size() == generic.size(),
|
|
"generic D4 test point does not have eight images");
|
|
for (std::size_t index = 0; index < generic.size(); ++index) {
|
|
failures += expect(
|
|
canonical_members(generic[index], 36) ==
|
|
std::vector<Placement>{{5, 9, 1}},
|
|
"D4 transform " + std::to_string(index) +
|
|
" did not select the same canonical representative");
|
|
}
|
|
|
|
// Closed boundaries are important because diagonal, midline, corner, and
|
|
// centre cells have non-trivial stabilizers and therefore smaller orbits.
|
|
for (auto const test_case:
|
|
std::array<std::pair<std::uint64_t, Placement>, 8>{{
|
|
{36, {0, 0, 1}},
|
|
{36, {0, 17, 1}},
|
|
{36, {7, 7, 1}},
|
|
{36, {7, 17, 1}},
|
|
{45, {0, 22, 1}},
|
|
{45, {11, 11, 1}},
|
|
{45, {11, 22, 1}},
|
|
{45, {22, 22, 1}},
|
|
}}) {
|
|
failures += expect(
|
|
canonical_members(test_case.second, test_case.first).size() == 1,
|
|
"boundary orbit did not retain exactly one distinct representative");
|
|
}
|
|
failures += expect(
|
|
canonical_unit_position(7, 17, 36) &&
|
|
!canonical_unit_position(8, 7, 36) &&
|
|
!canonical_unit_position(7, 18, 36) &&
|
|
canonical_unit_position(22, 22, 45) &&
|
|
!canonical_unit_position(22, 23, 45),
|
|
"canonical triangle mishandled a diagonal or midline boundary");
|
|
|
|
SearchCounters enabled_counters;
|
|
SearchCounters disabled_counters;
|
|
auto const enabled = search_solution_instrumented(
|
|
8, enabled_counters, SearchPolicy::ascending,
|
|
SymmetryBreaking::d4_unit_square, Pruning::disabled,
|
|
ComponentPruning::disabled);
|
|
auto const disabled = search_solution_instrumented(
|
|
8, disabled_counters, SearchPolicy::ascending,
|
|
SymmetryBreaking::disabled, Pruning::disabled,
|
|
ComponentPruning::disabled);
|
|
auto enabled_validation = validate(8, enabled);
|
|
auto disabled_validation = validate(8, disabled);
|
|
failures += expect(
|
|
enabled_validation.valid(),
|
|
"symmetry-enabled solution failed independent validation:\n" +
|
|
enabled_validation.text());
|
|
failures += expect(
|
|
disabled_validation.valid(),
|
|
"symmetry-disabled solution failed independent validation:\n" +
|
|
disabled_validation.text());
|
|
|
|
auto const unit = std::ranges::find_if(
|
|
enabled.squares(),
|
|
[](Square const &square) { return square.length() == 1; });
|
|
failures += expect(
|
|
unit != enabled.squares().end() &&
|
|
canonical_unit_position(unit->pos() % enabled.length(),
|
|
unit->pos() / enabled.length(),
|
|
enabled.length()),
|
|
"symmetry-enabled search placed the unique unit square outside the "
|
|
"canonical region");
|
|
failures += expect(
|
|
enabled_counters.prune_checks > 0 && enabled_counters.prune_hits > 0 &&
|
|
disabled_counters.prune_checks == 0 &&
|
|
disabled_counters.prune_hits == 0,
|
|
"symmetry instrumentation did not distinguish enabled and disabled "
|
|
"search");
|
|
return failures;
|
|
}
|
|
|
|
auto test_skyline_search() -> int {
|
|
int failures = 0;
|
|
auto const narrowest =
|
|
smallest_valley(std::vector<std::uint64_t>{4, 2, 2, 4, 0, 0, 0, 4});
|
|
failures += expect(
|
|
narrowest.x == 1 && narrowest.height == 2 && narrowest.width == 2,
|
|
"skyline did not select the smallest-width valley");
|
|
|
|
auto const tie =
|
|
smallest_valley(std::vector<std::uint64_t>{4, 1, 4, 4, 2, 4});
|
|
failures += expect(tie.x == 1 && tie.height == 1 && tie.width == 1,
|
|
"skyline valley tie-break is not deterministic");
|
|
|
|
SearchCounters descending_counters;
|
|
auto const descending = search_solution_instrumented(
|
|
8, descending_counters, SearchPolicy::descending);
|
|
auto validation = validate(8, descending);
|
|
failures += expect(
|
|
validation.valid(),
|
|
"descending skyline search returned an invalid order-8 solution:\n" +
|
|
validation.text());
|
|
|
|
SearchCounters direct_nine_counters;
|
|
auto const direct_nine = search_solution_instrumented(
|
|
9, direct_nine_counters, SearchPolicy::ascending);
|
|
validation = validate(9, direct_nine);
|
|
failures += expect(
|
|
validation.valid(),
|
|
"direct skyline search returned an invalid order-9 solution:\n" +
|
|
validation.text());
|
|
failures += expect(
|
|
direct_nine_counters.search_nodes != descending_counters.search_nodes,
|
|
"direct order-9 coverage unexpectedly reused predecessor construction");
|
|
|
|
SearchCounters ascending_exhaustive;
|
|
SearchCounters descending_exhaustive;
|
|
SearchCounters best_fit_exhaustive;
|
|
static_cast<void>(search_solution_instrumented(
|
|
5, ascending_exhaustive, SearchPolicy::ascending));
|
|
static_cast<void>(search_solution_instrumented(
|
|
5, descending_exhaustive, SearchPolicy::descending));
|
|
static_cast<void>(search_solution_instrumented(
|
|
5, best_fit_exhaustive, SearchPolicy::best_fit));
|
|
failures += expect(
|
|
ascending_exhaustive.search_nodes == descending_exhaustive.search_nodes &&
|
|
ascending_exhaustive.search_nodes == best_fit_exhaustive.search_nodes,
|
|
"candidate policy changed the exhaustive skyline search space");
|
|
return failures;
|
|
}
|
|
|
|
auto test_valley_capacity_pruning() -> int {
|
|
int failures = 0;
|
|
Avail available(5);
|
|
|
|
available[1] = 1;
|
|
failures += expect(
|
|
!valley_has_sufficient_capacity(
|
|
{1, 0, 1}, std::vector<std::uint64_t>{4, 0, 4}, available),
|
|
"width-one gap accepted insufficient unit-square capacity");
|
|
|
|
available = {};
|
|
available.resize(5);
|
|
available[2] = 1;
|
|
failures += expect(
|
|
!valley_has_sufficient_capacity(
|
|
{1, 0, 2}, std::vector<std::uint64_t>{4, 0, 0, 4}, available),
|
|
"width-two gap accepted insufficient narrow-piece area");
|
|
available[2] = 2;
|
|
failures += expect(
|
|
valley_has_sufficient_capacity(
|
|
{1, 0, 2}, std::vector<std::uint64_t>{4, 0, 0, 4}, available),
|
|
"width-two gap rejected exactly sufficient narrow-piece area");
|
|
|
|
available = {};
|
|
available.resize(5);
|
|
available[1] = 1;
|
|
available[2] = 1;
|
|
failures += expect(
|
|
!valley_has_sufficient_capacity(
|
|
{1, 2, 2}, std::vector<std::uint64_t>{5, 2, 2, 5}, available),
|
|
"general valley accepted less area than required to reach its rim");
|
|
available[2] = 2;
|
|
failures += expect(
|
|
valley_has_sufficient_capacity(
|
|
{1, 2, 2}, std::vector<std::uint64_t>{5, 2, 2, 5}, available),
|
|
"general valley rejected sufficient fitting-square area");
|
|
|
|
for (auto const order: std::array<std::uint64_t, 5>{1, 2, 3, 4, 5}) {
|
|
SearchCounters pruned_counters;
|
|
SearchCounters unpruned_counters;
|
|
auto const pruned = search_solution_instrumented(
|
|
order, pruned_counters, SearchPolicy::ascending,
|
|
SymmetryBreaking::disabled, Pruning::valley_capacity,
|
|
ComponentPruning::disabled);
|
|
auto const unpruned = search_solution_instrumented(
|
|
order, unpruned_counters, SearchPolicy::ascending,
|
|
SymmetryBreaking::disabled, Pruning::disabled,
|
|
ComponentPruning::disabled);
|
|
failures += expect(
|
|
pruned.squares().empty() == unpruned.squares().empty(),
|
|
"valley pruning changed exhaustive order-" +
|
|
std::to_string(order) + " feasibility");
|
|
failures += expect(
|
|
pruned_counters.search_nodes <= unpruned_counters.search_nodes,
|
|
"valley pruning enlarged the exhaustive order-" +
|
|
std::to_string(order) + " search");
|
|
}
|
|
|
|
SearchCounters counters;
|
|
static_cast<void>(search_solution_instrumented(
|
|
5, counters, SearchPolicy::ascending, SymmetryBreaking::disabled,
|
|
Pruning::valley_capacity, ComponentPruning::disabled));
|
|
failures += expect(
|
|
counters.valley_capacity_checks > 0 &&
|
|
counters.valley_capacity_prunes > 0 &&
|
|
counters.prune_checks == counters.valley_capacity_checks &&
|
|
counters.prune_hits == counters.valley_capacity_prunes,
|
|
"valley pruning instrumentation did not count checks and hits");
|
|
return failures;
|
|
}
|
|
|
|
auto test_large_square_pruning() -> int {
|
|
int failures = 0;
|
|
auto const fragmented =
|
|
std::vector<std::uint64_t>{0, 5, 0, 5, 0, 5};
|
|
failures += expect(
|
|
!skyline_has_empty_square(fragmented, 2),
|
|
"large-square check accepted a fragmented state without a 2x2 box");
|
|
failures += expect(
|
|
skyline_has_empty_square(
|
|
std::vector<std::uint64_t>{0, 0, 5, 5, 5, 5}, 2),
|
|
"large-square check rejected an available 2x2 box");
|
|
|
|
Avail available(4);
|
|
available[1] = 1;
|
|
available[2] = 1;
|
|
failures += expect(
|
|
!remaining_large_square_fits(fragmented, available),
|
|
"remaining-square check ignored the impossible largest square");
|
|
available[2] = 0;
|
|
failures += expect(
|
|
remaining_large_square_fits(fragmented, available),
|
|
"remaining-square check did not use geometric size monotonicity");
|
|
|
|
// The fragmented profile has 21 empty cells, more than the area of the
|
|
// remaining 2x2 square, but no two adjacent columns have two free rows.
|
|
std::uint64_t filled_area = 0;
|
|
for (auto const height: fragmented) {
|
|
filled_area += height;
|
|
}
|
|
failures += expect(
|
|
filled_area <= 36 - 4,
|
|
"fragmented test state does not have sufficient total empty area");
|
|
|
|
for (auto const order: std::array<std::uint64_t, 5>{1, 2, 3, 4, 5}) {
|
|
SearchCounters pruned_counters;
|
|
SearchCounters baseline_counters;
|
|
auto const pruned = search_solution_instrumented(
|
|
order, pruned_counters, SearchPolicy::ascending,
|
|
SymmetryBreaking::disabled, Pruning::all,
|
|
ComponentPruning::disabled);
|
|
auto const baseline = search_solution_instrumented(
|
|
order, baseline_counters, SearchPolicy::ascending,
|
|
SymmetryBreaking::disabled, Pruning::valley_capacity,
|
|
ComponentPruning::disabled);
|
|
failures += expect(
|
|
pruned.squares().empty() == baseline.squares().empty(),
|
|
"large-square pruning changed exhaustive order-" +
|
|
std::to_string(order) + " feasibility");
|
|
failures += expect(
|
|
pruned_counters.search_nodes <= baseline_counters.search_nodes,
|
|
"large-square pruning enlarged the exhaustive order-" +
|
|
std::to_string(order) + " search");
|
|
}
|
|
|
|
SearchCounters counters;
|
|
static_cast<void>(search_solution_instrumented(
|
|
5, counters, SearchPolicy::ascending, SymmetryBreaking::disabled,
|
|
Pruning::large_square, ComponentPruning::disabled));
|
|
failures += expect(
|
|
counters.large_square_checks > 0 &&
|
|
counters.large_square_prunes > 0 &&
|
|
counters.prune_checks == counters.large_square_checks &&
|
|
counters.prune_hits == counters.large_square_prunes,
|
|
"large-square instrumentation did not count checks and prunes");
|
|
return failures;
|
|
}
|
|
|
|
auto test_component_area_pruning() -> int {
|
|
int failures = 0;
|
|
auto const components =
|
|
empty_component_areas(std::vector<std::uint64_t>{2, 4, 1, 1});
|
|
failures += expect(
|
|
components == std::vector<std::uint64_t>{2, 6},
|
|
"full-height boundary did not split the expected component areas");
|
|
failures += expect(
|
|
empty_component_areas(
|
|
std::vector<std::uint64_t>{2, 1, 4, 4}) ==
|
|
std::vector<std::uint64_t>{5},
|
|
"adjacent non-full columns did not remain one empty component");
|
|
|
|
Avail gcd_available(3);
|
|
gcd_available[2] = 2;
|
|
failures += expect(
|
|
component_area_feasibility(
|
|
std::vector<std::uint64_t>{2, 4, 1, 1}, gcd_available,
|
|
ComponentPruning::gcd) ==
|
|
ComponentFeasibility::gcd_failure,
|
|
"component gcd check accepted indivisible component areas");
|
|
|
|
Avail subset_available(3);
|
|
subset_available[1] = 1;
|
|
subset_available[2] = 1;
|
|
failures += expect(
|
|
component_area_feasibility(
|
|
std::vector<std::uint64_t>{2, 4, 1, 4}, subset_available,
|
|
ComponentPruning::gcd) ==
|
|
ComponentFeasibility::feasible,
|
|
"component gcd check rejected a gcd-one state");
|
|
failures += expect(
|
|
component_area_feasibility(
|
|
std::vector<std::uint64_t>{2, 4, 1, 4}, subset_available,
|
|
ComponentPruning::subset_sum) ==
|
|
ComponentFeasibility::subset_sum_failure,
|
|
"bounded subset sum accepted unreachable component areas");
|
|
failures += expect(
|
|
component_area_feasibility(
|
|
std::vector<std::uint64_t>{3, 4, 0, 4}, subset_available,
|
|
ComponentPruning::subset_sum) ==
|
|
ComponentFeasibility::feasible,
|
|
"bounded subset sum rejected reachable component areas");
|
|
|
|
for (auto const order: std::array<std::uint64_t, 5>{1, 2, 3, 4, 5}) {
|
|
SearchCounters pruned_counters;
|
|
SearchCounters periodic_counters;
|
|
SearchCounters baseline_counters;
|
|
auto const pruned = search_solution_instrumented(
|
|
order, pruned_counters, SearchPolicy::ascending,
|
|
SymmetryBreaking::disabled, Pruning::all,
|
|
ComponentPruning::subset_sum);
|
|
auto const periodic = search_solution_instrumented(
|
|
order, periodic_counters, SearchPolicy::ascending,
|
|
SymmetryBreaking::disabled, Pruning::all,
|
|
ComponentPruning::subset_sum,
|
|
ComponentSchedule::periodic_eight);
|
|
auto const baseline = search_solution_instrumented(
|
|
order, baseline_counters, SearchPolicy::ascending,
|
|
SymmetryBreaking::disabled, Pruning::all,
|
|
ComponentPruning::disabled);
|
|
failures += expect(
|
|
pruned.squares().empty() == baseline.squares().empty() &&
|
|
periodic.squares().empty() == baseline.squares().empty(),
|
|
"component pruning changed exhaustive order-" +
|
|
std::to_string(order) + " feasibility");
|
|
failures += expect(
|
|
pruned_counters.search_nodes <= baseline_counters.search_nodes &&
|
|
periodic_counters.search_nodes <=
|
|
baseline_counters.search_nodes,
|
|
"component pruning enlarged the exhaustive order-" +
|
|
std::to_string(order) + " search");
|
|
}
|
|
|
|
SearchCounters counters;
|
|
static_cast<void>(search_solution_instrumented(
|
|
5, counters, SearchPolicy::ascending, SymmetryBreaking::disabled,
|
|
Pruning::disabled, ComponentPruning::subset_sum));
|
|
failures += expect(
|
|
counters.component_area_checks > 0 &&
|
|
counters.component_area_prunes > 0 &&
|
|
counters.component_area_prunes ==
|
|
counters.component_gcd_prunes +
|
|
counters.component_subset_prunes,
|
|
"component-area instrumentation did not count checks and prune kinds");
|
|
return failures;
|
|
}
|
|
|
|
auto test_solver_completion() -> int {
|
|
int failures = 0;
|
|
for (auto const order: std::array<std::uint64_t, 2>{1, 8}) {
|
|
auto const solution = find_solution(order);
|
|
auto const validation = validate(order, solution);
|
|
failures += expect(
|
|
validation.valid(),
|
|
"solver returned an invalid order-" + std::to_string(order) +
|
|
" solution:\n" + validation.text());
|
|
}
|
|
return failures;
|
|
}
|
|
}
|
|
|
|
int main(int argc, char **argv) {
|
|
if (argc != 2) {
|
|
std::cerr << "usage: partridge_tests TEST-NAME\n";
|
|
return 2;
|
|
}
|
|
|
|
auto const test = std::string_view(argv[1]);
|
|
if (test == "validator") {
|
|
return test_validator();
|
|
}
|
|
if (test == "construction") {
|
|
return test_construction();
|
|
}
|
|
if (test == "solver-odd-route") {
|
|
return test_odd_solver_route();
|
|
}
|
|
if (test == "rendering") {
|
|
return test_rendering();
|
|
}
|
|
if (test == "solver-small") {
|
|
return test_small_solver();
|
|
}
|
|
if (test == "solver-completion") {
|
|
return test_solver_completion();
|
|
}
|
|
if (test == "search-counters") {
|
|
return test_search_counters();
|
|
}
|
|
if (test == "skyline-search") {
|
|
return test_skyline_search();
|
|
}
|
|
if (test == "d4-symmetry") {
|
|
return test_d4_symmetry();
|
|
}
|
|
if (test == "valley-capacity") {
|
|
return test_valley_capacity_pruning();
|
|
}
|
|
if (test == "large-square") {
|
|
return test_large_square_pruning();
|
|
}
|
|
if (test == "component-area") {
|
|
return test_component_area_pruning();
|
|
}
|
|
std::cerr << "unknown test: " << test << '\n';
|
|
return 2;
|
|
}
|