The left-to-right algorithm It starts with the leftmost disk and proceeds to the right, doing the swaps as necessary. Now we have one dark disk at the left-hand end and the light disk at the right-hand end. Once it reaches the right-hand end, it goes back to the leftmost disk and proceeds to the right, doing the swaps as necessary. It repeats until there are no more disks to move. For the example shown, the exact list of disks changes as follows at the end of each run (left-to-right): The lawnmower algorithm It starts with the leftmost disk and proceeds to the right, doing the swaps as necessary. Now we have one dark disk at the left-hand end and the light disk at the right-hand end. Once it reaches the right-hand end, it starts with the disk before the rightmost disk and proceeds to the left, doing the swaps as necessary, until it reaches the disk before the left-hand end. It repeats until there are no more disks to move. For the example shown, the exact list of disks changes as follows at the end of each run, half round-trip (left-to-right or right-to-left): /////////////////////////////////////////////////////////////////////////////// // disks.hpp // // Definitions for two algorithms that each solve the alternating disks // problem. // // As provided, this header has four functions marked with TODO comments. // You need to write in your own implementation of these functions. // /////////////////////////////////////////////////////////////////////////////// #pragma once #include  #include  #include  #include  #include  #include  // State of one disk, either light or dark. enum disk_color { DISK_LIGHT, DISK_DARK }; // Data structure for the state of one row of disks. class disk_state { private: std::vector _colors; public: disk_state(size_t light_count) : _colors(light_count * 2, DISK_LIGHT) { assert(light_count > 0); for (size_t i = 0; i < _colors.size(); i += 2) { _colors[i] = DISK_DARK; } } // Equality operator for unit tests. bool operator== (const disk_state& rhs) const { return std::equal(_colors.begin(), _colors.end(), rhs._colors.begin()); } size_t total_count() const { return _colors.size(); } size_t light_count() const { return total_count() / 2; } size_t dark_count() const { return light_count(); } bool is_index(size_t i) const { return (i < total_count()); } disk_color get(size_t index) const { assert(is_index(index)); return _colors[index]; } void swap(size_t left_index) { assert(is_index(left_index)); auto right_index = left_index + 1; assert(is_index(right_index)); std::swap(_colors[left_index], _colors[right_index]); } std::string to_string() const { std::stringstream ss; bool first = true; for (auto color : _colors) { if (!first) { ss << " "; } if (color == DISK_LIGHT) { ss << "L"; } else { ss << "D"; } first = false; } return ss.str(); } // Return true when this disk_state is in alternating format. That means // that the first disk at index 0 is dark, the second disk at index 1 // is light, and so on for the entire row of disks. bool is_alternating() const { // TODO: Write code for this function, including rewriting the return // statement, and then delete these comments. return false; } // Return true when this disk_state is fully sorted, with all light disks // on the left (low indices) and all dark disks on the right (high // indices). bool is_sorted() const { // TODO: Write code for this function, including rewriting the return // statement, and then delete these comments. return false; } }; // Data structure for the output of the alternating disks problem. That // includes both the final disk_state, as well as a count of the number // of swaps performed. class sorted_disks { private: disk_state _after; unsigned _swap_count; public: sorted_disks(const disk_state& after, unsigned swap_count) : _after(after), _swap_count(swap_count) { } sorted_disks(disk_state&& after, unsigned swap_count) : _after(after), _swap_count(swap_count) { } const disk_state& after() const { return _after; } unsigned swap_count() const { return _swap_count; } }; // Algorithm that sorts disks using the left-to-right algorithm. sorted_disks sort_left_to_right(const disk_state& before) { // TODO: Write code for this function, including rewriting the return // statement, and then delete these comments. return sorted_disks(before, 0); } // Algorithm that sorts disks using the lawnmower algorithm. sorted_disks sort_lawnmower(const disk_state& before) { // TODO: Write code for this function, including rewriting the return // statement, and then delete these comments. return sorted_disks(before, 0); } /////////////////////////////////////////////////////////////////////////////// // disks_test.cpp // Unit tests for disks.hpp ///////////////////////////////////////////////////////////////////////////////

#include

#include "rubrictest.hpp"

#include "disks.hpp"

int main() {

Rubric rubric;

const disk_state alt_one(1), alt_three(3);

auto sorted_one(alt_one); sorted_one.swap(0);

auto sorted_three(alt_three); // DL DL DL sorted_three.swap(0); // LD DL DL sorted_three.swap(2); // LD LD DL sorted_three.swap(1); // LL DD DL sorted_three.swap(4); // LL DD LD sorted_three.swap(3); // LL DL DD sorted_three.swap(2); // LL LD DD

rubric.criterion("disk_state still works", 1, [&]() { TEST_EQUAL("total_count() for n=1", 2, alt_one.total_count()); TEST_EQUAL("dark_count() for n=1", 1, alt_one.dark_count()); TEST_EQUAL("light_count() for n=1", 1, alt_one.light_count()); TEST_TRUE("is_index(0) for n=1", alt_one.is_index(0)); TEST_TRUE("is_index(1) for n=1", alt_one.is_index(1)); TEST_FALSE("is_index(2) for n=1", alt_one.is_index(2)); TEST_EQUAL("get(0) for n=1", DISK_DARK, alt_one.get(0)); TEST_EQUAL("get(1) for n=1", DISK_LIGHT, alt_one.get(1));

TEST_EQUAL("total_count() for n=3", 6, alt_three.total_count()); TEST_EQUAL("dark_count() for n=3", 3, alt_three.dark_count()); TEST_EQUAL("light_count() for n=3", 3, alt_three.light_count()); TEST_TRUE("is_index(0) for n=3", alt_three.is_index(0)); TEST_TRUE("is_index(1) for n=3", alt_three.is_index(1)); TEST_TRUE("is_index(2) for n=3", alt_three.is_index(2)); TEST_TRUE("is_index(3) for n=3", alt_three.is_index(3)); TEST_TRUE("is_index(4) for n=3", alt_three.is_index(4)); TEST_TRUE("is_index(5) for n=3", alt_three.is_index(5)); TEST_FALSE("is_index(6) for n=3", alt_three.is_index(6)); TEST_EQUAL("get(0) for n=3", DISK_DARK, alt_three.get(0)); TEST_EQUAL("get(1) for n=3", DISK_LIGHT, alt_three.get(1)); TEST_EQUAL("get(2) for n=3", DISK_DARK, alt_three.get(2)); TEST_EQUAL("get(3) for n=3", DISK_LIGHT, alt_three.get(3)); TEST_EQUAL("get(4) for n=3", DISK_DARK, alt_three.get(4)); TEST_EQUAL("get(5) for n=3", DISK_LIGHT, alt_three.get(5));

TEST_EQUAL("get(0) after swap", DISK_LIGHT, sorted_one.get(0)); TEST_EQUAL("get(1) after swap", DISK_DARK, sorted_one.get(1));

TEST_EQUAL("get(0) after swaps", DISK_LIGHT, sorted_three.get(0)); TEST_EQUAL("get(1) after swaps", DISK_LIGHT, sorted_three.get(1)); TEST_EQUAL("get(2) after swaps", DISK_LIGHT, sorted_three.get(2)); TEST_EQUAL("get(3) after swaps", DISK_DARK, sorted_three.get(3)); TEST_EQUAL("get(4) after swaps", DISK_DARK, sorted_three.get(4)); TEST_EQUAL("get(5) after swaps", DISK_DARK, sorted_three.get(5)); });

rubric.criterion("sorted_disks still works", 1, [&]() { auto temp = sorted_disks(alt_three, 13); TEST_EQUAL("sorted_disks::after", temp.after(), alt_three); TEST_EQUAL("sorted_disks::swap_count", 13, temp.swap_count()); });

rubric.criterion("disk_state::is_alternating", 3, [&]() { TEST_TRUE("is_alternating() for n=1", alt_one.is_alternating()); TEST_TRUE("is_alternating() for n=1", alt_three.is_alternating()); TEST_FALSE("is_alternating() after swap", sorted_one.is_alternating()); TEST_FALSE("is_alternating() after swaps", sorted_three.is_alternating()); });

rubric.criterion("disk_state::is_sorted", 3, [&]() { TEST_FALSE("is_sorted() for n=1", alt_one.is_sorted()); TEST_FALSE("is_sorted() for n=1", alt_three.is_sorted()); TEST_TRUE("is_sorted() after swap", sorted_one.is_sorted()); TEST_TRUE("is_sorted() after swaps", sorted_three.is_sorted()); });

rubric.criterion("left-to-right, n=4", 1, [&]() { auto output = sort_left_to_right(disk_state(4)); TEST_TRUE("actually sorted", output.after().is_sorted()); TEST_EQUAL("number of swaps must be 10", 10, output.swap_count()); });

rubric.criterion("left-to-right, n=3", 1, [&]() { auto output = sort_left_to_right(disk_state(3)); TEST_TRUE("actually sorted", output.after().is_sorted()); TEST_EQUAL("number of swaps must be 6", 6, output.swap_count()); });

rubric.criterion("left-to-right, other values", 1, [&]() {

auto trial = [](unsigned n) { return sort_left_to_right(disk_state(n)).swap_count(); };

TEST_EQUAL("n=10 gives 55 swaps", 55, trial(10)); TEST_EQUAL("n=20 gives 210 swaps", 210, trial(20)); TEST_EQUAL("n=30 gives 465 swaps", 465, trial(30)); TEST_EQUAL("n=40 gives 820 swaps", 820, trial(40)); TEST_EQUAL("n=50 gives 1275 swaps", 1275, trial(50)); TEST_EQUAL("n=60 gives 1830 swaps", 1830, trial(60)); TEST_EQUAL("n=70 gives 2485 swaps", 2485, trial(70)); TEST_EQUAL("n=80 gives 3240 swaps", 3240, trial(80)); TEST_EQUAL("n=90 gives 4095 swaps", 4095, trial(90)); TEST_EQUAL("n=100 gives 5050 swaps", 5050, trial(100)); });

rubric.criterion("lawnmower, n=4", 1, [&]() { auto output = sort_lawnmower(disk_state(4)); TEST_TRUE("actually sorted", output.after().is_sorted()); TEST_EQUAL("number of swaps must be 10", 10, output.swap_count()); });

rubric.criterion("lawnmower, n=3", 1, [&]() { auto output = sort_lawnmower(disk_state(3)); TEST_TRUE("actually sorted", output.after().is_sorted()); TEST_EQUAL("number of swaps must be 6", 6, output.swap_count()); });

rubric.criterion("lawnmower, other values", 1, [&]() {

auto trial = [](unsigned n) { return sort_lawnmower(disk_state(n)).swap_count(); };

TEST_EQUAL("n=10 gives 55 swaps", 55, trial(10)); TEST_EQUAL("n=20 gives 210 swaps", 210, trial(20)); TEST_EQUAL("n=30 gives 465 swaps", 465, trial(30)); TEST_EQUAL("n=40 gives 820 swaps", 820, trial(40)); TEST_EQUAL("n=50 gives 1275 swaps", 1275, trial(50)); TEST_EQUAL("n=60 gives 1830 swaps", 1830, trial(60)); TEST_EQUAL("n=70 gives 2485 swaps", 2485, trial(70)); TEST_EQUAL("n=80 gives 3240 swaps", 3240, trial(80)); TEST_EQUAL("n=90 gives 4095 swaps", 4095, trial(90)); TEST_EQUAL("n=100 gives 5050 swaps", 5050, trial(100)); });

return rubric.run(); }