Missing include guards in the header file:
#ifndef Q3_H
#define Q3_H
⋮
#endif
This interface is surprising:
int find_min_moves(std::string display_order);
Does the function really need a copy of the string in order to operate? I'd expect we'd be able to pass it a string view, which reduces the copying burden.
In q3.cc, I recommend including "q3.h" as the first header. That helps us ensure that the header is self-contained - not relying on the implementation file already having any definitions before it's included.
The ALPHABET variable is a good idea - many programmers who have grown up with ASCII and related character encodings mistakenly assume that these characters necessarily have consecutive values. However, I advise not using all-caps for the name, because we normally reserve such names for macros (which behave differently from C++ identifiers), so it's asking for special attention it doesn't need.
I think its global scope is probably a mistake - it can be a static within the one function that uses it.
And in fact all the global scope identifiers that are not part of the public interface should be changed to translation-unit scope (static or anonymous namespaces). That will eliminate the risk of collision with extern identifiers in other translation units.
In class State, the private: label is redundant - class members before the first access qualifier are automatically private.
It's not clear why n_moves needs to be a signed integer.
Instead of default-initialising the members and then assigning to them in the body of the constructor, it's better to value-initialise in the constructor's initialiser list:
std::string display;
std::string next_boxes;
int n_moves = 0;
public:
State(std::string display, std::string next_boxes)
: display{std::move(display)},
next_boxes{std::move(next_boxes)}
{
}
This eliminates a -Weffc++ warning, resulting in a completely clean compilation with my usual options.
Once again, string views might be more appropriate for the members - in most implementations adjusting a view to exclude the first element is a much cheaper operation than removing a character from the beginning of a string. They are only similar if the implementation of string pays the storage cost of separate members for the storage and start position.
I think the get_n_moves() accessor can usefully be declared const.
It's probably worth a comment explaining why n_moves doesn't participate in the comparisons.
Also, consider a simpler implementation using std::tuple comparison:
private:
constexpr auto as_tuple() const
{
return std::tie(display, next_boxes);
}
public:
constexpr bool operator==(const State& other) const
{
return as_tuple() == other.as_tuple();
}
constexpr auto operator<=>(const State& other) const
{
return as_tuple() <=> other.as_tuple();
}
I think this is clearer, without the branching that needs to be carefully read.
add_if_not_contained could/should accept new_state as a reference to const, since it should not be modifying its value.
We can write std::find(visited_states.begin(), visited_states.end(), new_state) == visited_states.end() much more clearly as visited_states.count(new_state) == 0.
We have three very similar blocks in the while(true) loop of find_min_moves(), differing only in which operation is applied to the state object. These can be unified by iterating over the possible operations:
for (auto op: {&State::add, &State::swap, &State::rotate}) {
State next = selected_state;
(next.*op)();
if (next == display_order_state) {
return next.get_n_moves();
}
add_if_not_contained(next_states, visited_states, next);
}
Consider making the State immutable, with operations that return the new state. That would make it easier to reason about and allow the use of more const in the code.
The code isn't very robust when inputs are not valid. If invoked with ABZ as input, we hit undefined behaviour when next_states.empty(). We could test for that before pop(), and return an error indicator in that case (-1 if we're sticking with signed int, perhaps).
Alternatively, we could be much more permissive in what we accept if we assume that characters in ALPHABET are monotonically ascending; although that is not specified by C++, it is true in all character sets I'm aware of, and can be tested at compile-time:
static constexpr bool alphabet_sorted = []{
auto *alphabet = "ABCDEFGHIJKLNOPQRSTUVWXYZ";
std::string sorted = alphabet;
std::ranges::sort(sorted);
return sorted == alphabet;
}();
static_assert(alphabet_sorted, "Requires a character coding with sorted alphabet");
Then we just sort the box names when setting up the initial state:
std::string initial_order = display_order;
std::ranges::sort(initial_order);
State selected_state("", initial_order);
With that modification, I believe the loop will always terminate before underrunning the queue.
Cleaned code
q3.h
#ifndef Q3_H
#define Q3_H
#include <cstddef>
#include <string_view>
std::size_t find_min_moves(std::string_view display_order);
#endif
q3.cc
#include "q3.h"
#include <algorithm>
#include <queue>
#include <set>
#include <string>
#include <tuple>
namespace {
class State
{
std::string display;
std::string_view next_boxes;
std::size_t n_moves = 0;
public:
constexpr State(std::string display,
std::string_view next_boxes)
: display{std::move(display)},
next_boxes{next_boxes}
{
}
constexpr State added() const
{
if (next_boxes.empty()) {
return *this; // do nothing
}
auto next = *this;
next.display += next.next_boxes.front();
next.next_boxes.remove_prefix(1);
++next.n_moves;
return next;
}
constexpr State swapped() const
{
if (display.length() < 2) {
return *this; // do nothing
}
auto next = *this;
std::swap(next.display[0], next.display[1]);
++next.n_moves;
return next;
}
constexpr State rotated() const
{
if (display.length() < 2) {
return *this; // do nothing
}
auto next = *this;
std::ranges::rotate(next.display, std::next(next.display.begin()));
++next.n_moves;
return next;
}
constexpr std::size_t get_n_moves() const
{
return n_moves;
}
private:
constexpr auto as_tuple() const
{
return std::tie(display, next_boxes);
}
public:
constexpr bool operator==(const State& other) const
{
return as_tuple() == other.as_tuple();
}
constexpr auto operator<=>(const State& other) const
{
return as_tuple() <=> other.as_tuple();
}
};
}
std::size_t find_min_moves(std::string display_order)
{
static_assert([]{
auto *alphabet = "ABCDEFGHIJKLNOPQRSTUVWXYZ";
std::string sorted = alphabet;
std::ranges::sort(sorted);
return sorted == alphabet;
}(), "Requires a character coding with sorted alphabet");
const State target_state = State(display_order, "");
std::queue<State> next_states;
std::set<State> visited_states;
auto add_if_not_contained = [&](const State& new_state)
{
if (visited_states.count(new_state) == 0) {
next_states.push(new_state);
visited_states.insert(new_state);
}
};
std::string initial_order = display_order;
std::ranges::sort(initial_order);
State selected_state("", initial_order);
visited_states.insert(selected_state);
while (true) {
for (auto op: {&State::added, &State::swapped, &State::rotated}) {
const State next = (selected_state.*op)();
if (next == target_state) {
return next.get_n_moves();
}
add_if_not_contained(next);
}
selected_state = next_states.front();
next_states.pop();
}
}
q3a.cc
#include "q3.h"
#include <cstdlib>
#include <iostream>
#include <string>
int main()
{
if (std::string display_order; std::cin >> display_order) {
std::cout << find_min_moves(display_order) << "\n";
} else {
std::cerr << "Failed to read input.\n";
return EXIT_FAILURE;
}
}
The code above makes no changes to the algorithm, which is a very simple brute-force search. It could perhaps be improved if you can find a good "closeness" heuristic and use a std::priority_queue for next_states() to explore the most likely operations first. However, that's a major re-work since our queue is currently sorted by the number of moves taken, and we don't want to lose a shorter solution when the heuristic misses.
It's quite likely that you could get a better algorithm simply by working backwards from the end state to the sorted-input position. We commonly find in search algorithms, finding one's way "home" from an arbitrary location is easier than finding our way outwards - just like in real-life navigation, we're more likely to hit a familiar landmark on the inward journey.
In our case, working backwards immediately reduces our branching factor from three to two, because whenever the last element is the largest, we unconditionally remove it.
There are other micro-optimisations that result:
- No need to store the target state - we can simply test
display_order.empty() to know when we've reached the end.
- No need to store the non-displayed box identifiers; we might choose instead to cache the max displayed box, that's next to be removed when it reaches the end position.
- Truncating the string could be cheaper than appending (unlikely here with these short strings; just mentioning for completeness).
I've implemented this suggestion:
namespace {
class State
{
std::string display;
char highest;
std::size_t n_moves = 0;
public:
constexpr State(std::string display)
: display{std::move(display)},
highest{next_box()}
{
}
constexpr State added() const
{
if (display.back() != highest || display.empty()) {
return *this; // do nothing
}
auto next = *this;
next.display.resize(next.display.size() - 1);
next.highest = next.next_box();
++next.n_moves;
return next;
}
constexpr State swapped() const
{
if (display.length() < 2) {
return *this; // do nothing
}
auto next = *this;
std::swap(next.display[0], next.display[1]);
++next.n_moves;
return next;
}
constexpr State rotated() const
{
if (display.length() < 2) {
return *this; // do nothing
}
auto next = *this;
std::ranges::rotate(next.display, std::prev(next.display.end()));
++next.n_moves;
return next;
}
constexpr std::size_t get_n_moves() const
{
return n_moves;
}
constexpr bool empty() const
{
return display.empty();
}
private:
char next_box()
{
return display.empty() ? '\0' : std::ranges::max(display);
}
public:
constexpr bool operator==(const State& other) const
{
return display == other.display;
}
constexpr auto operator<=>(const State& other) const
{
return display <=> other.display;
}
};
}
std::size_t find_min_moves(std::string display_order)
{
static_assert([]{
auto *alphabet = "ABCDEFGHIJKLNOPQRSTUVWXYZ";
std::string sorted = alphabet;
std::ranges::sort(sorted);
return sorted == alphabet;
}(), "Requires a character coding with sorted alphabet");
std::queue<State> next_states;
std::set<State> visited_states;
auto add_if_not_contained = [&](const State& new_state)
{
if (visited_states.count(new_state) == 0) {
next_states.push(new_state);
}
};
State selected_state(std::move(display_order));
while (!selected_state.empty()) {
visited_states.insert(selected_state);
for (auto op: {&State::added, &State::swapped, &State::rotated}) {
add_if_not_contained((selected_state.*op)());
}
selected_state = next_states.front();
next_states.pop();
}
return selected_state.get_n_moves();
}
When executed, this gives a significant improvement in memory usage, and a measurable one in execution time.
Before:
time ./293170 <<<AHGEFDCBML
32
5.90user 0.19system 0:06.09elapsed 99%CPU (0avgtext+0avgdata 371320maxresident)k
After:
time ./293170 <<<AHGEFDCBML
32
4.92user 0.10system 0:05.03elapsed 99%CPU (0avgtext+0avgdata 150420maxresident)k
I'll leave the hunt for further algorithmic improvements open, rather than doing this more open-ended research for you.
