# BIO 2021 Q3a: Window Dressing (BFS in C++)

I was practicing question 3a of the British Informatics Olympiad 2021 past paper.

A shop is looking to display some boxes (conveniently labelled A, B, …) in their window. There is a desired order for the boxes to appear in the window but unfortunately the boxes arrive from the warehouse in alphabetical order and access to the window limits how the boxes can be added to the display. There are three possible operations the store manager can employ to change the order of the boxes in the window:

• (Add) The next box from the warehouse can be added to the end of the boxes currently on display;
• (Swap) The ﬁrst two boxes in the window display can be swapped;
• (Rotate) The ﬁrst box can be removed from the display and replaced at the other end of the display.

Given a desired order for the display, the manager wishes to ﬁnd the minimum number of operations needed. For example, suppose the desired order is ACBD:

• The manager could add A then B then C then D (giving ABCD after 4 operations), then rotate (giving BCDA), swap (CBDA) and rotate another 3 times (ACBD). A total of 9 operations.
• The manager could add A then B (giving AB), then swap (BA), add C (BAC), rotate (ACB) and add D (ACBD). A total of 6 operations.

Write a program to determine the minimum number of operations to display the boxes. Your program should input a string of b (1 ≤ b ≤ 8) uppercase letters, a permutation of the ﬁrst b letters of the alphabet. You should output the minimum number of operations required to reach this permutation.

I wrote this code (I split it up into multiple files so that it would be easier to reuse some of the parts in questions 3b and 3c):

q3.h

#include <string>

int find_min_moves(std::string display_order);


q3.cc

#include <queue>
#include <set>
#include <algorithm>

#include "q3.h"

const std::string ALPHABET = "ABCDEFGHIJKLNOPQRSTUVWXYZ";

class State {
private:
std::string display;
std::string next_boxes;
int n_moves;

public:
State(std::string display, std::string next_boxes) {
this->display = display;
this->next_boxes = next_boxes;
n_moves = 0;
}

void add() {
if (next_boxes.length() > 0) {
display += next_boxes.front();
next_boxes.erase(0, 1);
++n_moves;
}
}

void swap() {
if (display.length() >= 2) {
char temp = display[0];
display[0] = display[1];
display[1] = temp;
++n_moves;
}
}

void rotate() {
if (display.length() >= 2) {
display += display[0];
display.erase(0, 1);
++n_moves;
}
}

int get_n_moves() {
return n_moves;
}

bool operator==(const State& other) const {
return display == other.display && next_boxes == other.next_boxes;
}

bool operator<(const State& other) const {
if (display != other.display) {
return display < other.display;
} else {
return next_boxes < other.next_boxes;
}
}
};

void add_if_not_contained(std::queue<State>& next_states, std::set<State>& visited_states, State& new_state) {
if (std::find(visited_states.begin(), visited_states.end(), new_state)
== visited_states.end()) {
next_states.push(new_state);
visited_states.insert(new_state);
}
}

int find_min_moves(std::string display_order) {
State display_order_state = State(display_order, "");

std::queue<State> next_states;

State selected_state("", ALPHABET.substr(0, display_order.length()));

std::set<State> visited_states;
visited_states.insert(selected_state);

while (true) {
State added_state = selected_state;
added_state.add();
if (added_state == display_order_state) {
return added_state.get_n_moves();
}
add_if_not_contained(next_states, visited_states, added_state);

State swapped_state = selected_state;
swapped_state.swap();
if (swapped_state == display_order_state) {
return swapped_state.get_n_moves();
}
add_if_not_contained(next_states, visited_states, swapped_state);

State rotated_state = selected_state;
rotated_state.rotate();
if (rotated_state == display_order_state) {
return rotated_state.get_n_moves();
}
add_if_not_contained(next_states, visited_states, rotated_state);

selected_state = next_states.front();
next_states.pop();
}
}


q3a.cc

#include <iostream>

#include "q3.h"

int main() {
std::string display_order;
std::cin >> display_order;

std::cout << find_min_moves(display_order) << "\n";

return 0;
}


Example run:

ACBD
6


(More test cases can be found in the mark scheme).

I would be grateful to hear about any improvements that could be made to this code. I would also be grateful to hear about any optimizations, as my code isn't fast enough to complete some of the tests in the specified time (1 second), and sometimes it takes so long that it hangs (although this is helped by an optimizer):

$g++ q3.cc q3a.cc -o q3a$ time ./q3a
CFBGAHDE
15

real    0m4.197s
user    0m2.368s
sys     0m0.007s
$g++ q3.cc q3a.cc -o q3a -O$ time ./q3a
CFBGAHDE
15

real    0m2.029s
user    0m0.909s
sys     0m0.005s


## 2 Answers

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.

• Just UV'd for the "work backwards" elaboration. So often, reframing a problem can lead to better solutions! Commented Aug 2 at 7:16
• I couldn't resist implementing that suggestion to see what difference it makes, so I've included the code and results. It certainly increases the problem size I can reach before exceeding the memory quota I give to CR code. Commented Aug 2 at 7:38

First (very trivial) comment:
Shun placing #include directives inside your own header files.
It's a convenience that promotes laziness that leads to tossing "everything including the kitchen sink" into a single app-wide header (made up for 'n' source code files.)

Form the habit of always using "header guards" (and I suggest incorporating the filename, too. Put the filename into "code files", too. It helps!):

// q3.h - yadda yadda

#ifndef Q3_H
#define Q3_H
...
#endif


Discipline comes from starting out being disciplined.

(I think there's a new-school #pragma once(?) that achieves the same effect, but I especially do not know if this works for C++.)

With ..._state and ..._states as a 7 character suffix on almost every variable name, the operations being performed are lost in the cacophony of (imo) too much emphasis on being specific (in a tiny block of code.) If everything tracks something related to "state", then its safe to presume that "state" can be presumed and need not be explicit.

if (std::find(visited_states.begin(), visited_states.end(), new_state)
== visited_states.end()) {


or

if (std::find(visited.begin(), visited.end(), new) == visited.end()) {


Obviously, new - from new_state - must be changed. Perhaps use added as the name of this parameter???

When you see an if/else, look again for ways to simplify the branching:

bool operator<(const State& other) const {
return  display < other.display
|| (display == other.display && next_boxes < other.next_boxes);
}


#### Internal model can depart from External representation

Although they certainly would have been tuned for optimum performance, the problem statement's use of alphabetic representations of "box IDs" leads one to reach for "string object" workers. Consider the problem's limit of 1 <= b <= 8 for the quantity (and the ID's) of boxes. It may be worth exploring using an internal representation that corresponds to BCD values 0x1 to 0x8.

"ACBD" would be translated to 0x00001324 at start-up, then used for comparing. (8 consecutive 4bit BCD digits would fit into a single uint32_t variable.) Likewise, the "delivery" sequence of 4 boxes would be 0x00001234 corresponding to "ABCD".

For example, rotating might become:

// one-time only set up to handle 'b' boxes
// prepare trim mask 0x0000000F to 0xFFFFFFFF to trim to 'b' BCD values
uint32_t TRIM = (b == 8) ? ~0 : ( (1 << (b*4)) - 1 );
uint32_t SHFTDWN = (b-1)*4; // amount to shift leftmost value into rightmost position

void rotate() { // Rotate leftmost digit to right end of collection
curr = ( (curr << 4) | (curr >> SHFTDWN) ) & TRIM;
}


I suspect (but have not tested) that these 4 bitwise operations on a single value would process faster than the string object version of the same operation. I know that the frequent testing checking that the current arrangement matches the objective WOULD be faster (not involving string comparison.)

Left as an exercise: Develop "mask" variables to isolate the two leftmost BCD values (based on 'b' values present) and use those to swap the two leftmost BCD values... and so on... OR, consider the possibilities of the internal model being stored and manipulated as the reverse of what's expected (eg: rightmost positions are easy to access for swapping.)

Like the liberties a compiler can take when optimising C source code when translating it to target machine code, as long as the job gets done correctly, software is free to exploit any avenue it can in the quest for performance.

#### Feedback should not be ignored

There's some feedback posted in comments below this answer regarding its first recommendation about "nested" #include directives. This response must be somewhat more voluminous than a 512 character comment allows.

First, an admission regarding this answer's suggestion about if/else improvements.

The OP's code:

        bool operator<(const State& other) const {
if (display != other.display) {
return display < other.display;
} else {
return next_boxes < other.next_boxes;
}
}


Repeating my cavalierly suggested alternative:

bool operator<(const State& other) const {
return  display < other.display
|| (display == other.display && next_boxes < other.next_boxes);
}


Prompted to revisit this answer, it's worth rewriting that as if it involved simple C strings:

return  strcmp( display, other.display ) < 0
|| (strcmp( display, other.display ) == 0 && strcmp( next_boxes, other.next_boxes) < 0 );


The now obvious improvement for speed:

int ret = strcmp( display, other.display );
return ret < 0 || (ret == 0 && strcmp( next_boxes, other.next_boxes) < 0);


Will a compiler see this optimisation?

@Toby has written an excellent, in-depth answer. Kudos to @Toby.

Pondering the feedback below that I summarise as "trust it, use it and move on to the next issue" and @Toby's suggestion to add another layer of abstraction with <tuple>, I wonder if the OP will achieve the execution speeds being sought... This SO Q&A explains to the neophyte that a "tuple" implementation involves creating (compile time) packages of elements that are, in effect, linked lists of heterogenous datatypes (introducing more overhead). Is this good when one wants to optimise for execution speed?

To round this off, I willingly admit my unbounded respect for compiler writers and for those who have a deep understanding of templates. Most coders (like me, moreso with each passing day) become lost at C when all those pointy angle brackets multiply and exponentiate. Once one has many, many years of experience, one will be in a position to judge when nesting header includes inside other headers is, or is not, appropriate.

I stand by the recommendation that neophytes adhere to KISS principles. Rather than seeking out abstractions (whose overheads are not understood), and/or "click-and-play" packages, in order to solve problems, an arguably "better way forward" is to ponder the question, "How might I solve this problem using the most ordinary and simple-to-understand tools in the shed?" The reader is encouraged to search out the amusing concept of the pen that writes in outer space.

KISS and get on with life.

• IMO the advice to not include headers in headers is terrible. The consumer of a header shouldn't need to audit it for every type mentioned to make sure they include the appropriate headers (especially when they don't directly use those types themselves). You should include what you use in every file (i.e. if you use std::string then #include <string>). What you should not do is have a big "standard_includes.h" that includes everything under the sun (though a handfull of commonly-used headers in a precompiled header can speed up build times). Commented Aug 1 at 15:51
• "Shun placing #include directives inside your own header files." => This is the opposite of all the best practices I've ever come across, which instead recommend that any header should be self-contained. Do you have a pointer to any style guide which would recommend such an exotic practice or did you come by it yourself? Commented Aug 1 at 16:37
• @Fe2O3 I'm not talking about security auditing of third-party codebases here. The comment applies just as well to first-party headers. I'm talking about having to read through 2000 lines of template barf to figure out which 7 headers I need to include to make the compiler not choke on my #include "BuisnessLogicTransformer.h" (note: I am being hyperbolic here). As to how many is "a handful", that will be different for everyone and every project. It's a tradeoff between code cleanliness and build time. Commented Aug 1 at 21:58
• The last thing I'll say is just that I'm glad real libraries don't follow your advice. I'd hate to have to read through all of libstdc++ to figure out that I need to include <bits/stl_algobase.h>, <bits/allocator.h>, <bits/stl_construct.h>, <bits/stl_uninitialized.h>, etc (and all of their dependencies) along with <vector>. Commented Aug 1 at 22:54
• To address my suggested use of std::tie to create a tuple of references - that's something we can confidently expect to resolve to the same object code as the explicitly-branching version - the overhead is incurred just once, at compile-time, not when the resulting program executes. (Interestingly, I found that when running the original or my "cleaned" version, adding -march=native -O3 to my GCC command resulting in two orders of magnitude change in execution time!) Commented Aug 2 at 6:52