initial commit

1 files changed, 171 insertions, 0 deletions

diff --git a/comp6771/1/src/word_ladder.test.cpp b/comp6771/1/src/word_ladder.test.cpp
new file mode 100644
index 0000000..34eec4a
--- /dev/null
+++ b/comp6771/1/src/word_ladder.test.cpp
@@ -0,0 +1,171 @@
+#include "word_ladder.h"
+
+#include <catch2/catch.hpp>
+
+// Fixture to handle cleanup of temporary file between both tests for
+// word_ladder::read_lexicon.
+struct lexicon_fixture {
+    static const constexpr char* const path = "words.txt";
+    ~lexicon_fixture() noexcept { std::filesystem::remove(path); }
+};
+
+TEST_CASE_METHOD(lexicon_fixture,
+                 "word_ladder::read_lexicon works as expected") {
+    const std::vector<std::string> words = {"test", "words", "for", "writing"};
+    {
+        std::ofstream out{lexicon_fixture::path};
+        if (!out.is_open()) {
+            FAIL("failed to open test file for writing");
+        }
+        for (const auto& word : words) {
+            out << word << '\n';
+        }
+    }
+
+    const auto lexicon = word_ladder::read_lexicon(lexicon_fixture::path);
+    CHECK(std::size(lexicon) == std::size(words));
+    for (const auto& word : words) {
+        CHECK(lexicon.contains(word));
+    }
+}
+
+TEST_CASE_METHOD(lexicon_fixture,
+                 "word_ladder::read_lexicon fails with a non-existent file") {
+    REQUIRE_THROWS(word_ladder::read_lexicon(lexicon_fixture::path));
+}
+
+namespace {
+
+auto check_generate(const std::string& from, const std::string& to,
+                    const std::unordered_set<std::string>& lexicon,
+                    const std::vector<std::vector<std::string>>& expected)
+    -> void {
+    const auto ladders = word_ladder::generate(from, to, lexicon);
+    CHECK(ladders == expected);
+}
+
+}  // namespace
+
+TEST_CASE("\"\" -> \"\"") {
+    check_generate("", "", word_ladder::read_lexicon("./english.txt"), {});
+}
+
+TEST_CASE("at -> it") {
+    const auto expected = std::vector<std::vector<std::string>>{{"at", "it"}};
+    check_generate("at", "it", word_ladder::read_lexicon("./english.txt"),
+                   expected);
+}
+
+// Previous test ensures at->it is correct.
+// Ensure that the words in the lexicon are respected and do not generate
+// solutions for an empty lexicon, for this same test case.
+TEST_CASE("at -> it, empty lexicon") { check_generate("at", "it", {}, {}); }
+
+TEST_CASE("fly -> sky") {
+    const auto expected =
+        std::vector<std::vector<std::string>>{{"fly", "sly", "sky"}};
+    check_generate("fly", "sky", word_ladder::read_lexicon("./english.txt"),
+                   expected);
+}
+
+TEST_CASE("code -> data") {
+    const auto expected = std::vector<std::vector<std::string>>{
+        {"code", "cade", "cate", "date", "data"},
+        {"code", "cote", "cate", "date", "data"},
+        {"code", "cote", "dote", "date", "data"}};
+    check_generate("code", "data", word_ladder::read_lexicon("./english.txt"),
+                   expected);
+}
+
+// Previous test ensured that code->data returned correct solutions. We now
+// ensure that some of the solutions are impossible to retrieve given that we
+// modify the lexicon to make those solutions impossible.
+TEST_CASE("code -> data, modified lexicon") {
+    const auto expected = std::vector<std::vector<std::string>>{
+        {"code", "cade", "cate", "date", "data"}};
+    const auto lexicon = []() -> std::unordered_set<std::string> {
+        auto lexicon = word_ladder::read_lexicon("./english.txt");
+        lexicon.erase("cote");
+        return lexicon;
+    }();
+    check_generate("code", "data", lexicon, expected);
+}
+
+TEST_CASE("work -> play") {
+    const auto expected = std::vector<std::vector<std::string>>{
+        {"work", "fork", "form", "foam", "flam", "flay", "play"},
+        {"work", "pork", "perk", "peak", "pean", "plan", "play"},
+        {"work", "pork", "perk", "peak", "peat", "plat", "play"},
+        {"work", "pork", "perk", "pert", "peat", "plat", "play"},
+        {"work", "pork", "porn", "pirn", "pian", "plan", "play"},
+        {"work", "pork", "port", "pert", "peat", "plat", "play"},
+        {"work", "word", "wood", "pood", "plod", "ploy", "play"},
+        {"work", "worm", "form", "foam", "flam", "flay", "play"},
+        {"work", "worn", "porn", "pirn", "pian", "plan", "play"},
+        {"work", "wort", "bort", "boat", "blat", "plat", "play"},
+        {"work", "wort", "port", "pert", "peat", "plat", "play"},
+        {"work", "wort", "wert", "pert", "peat", "plat", "play"}};
+    check_generate("work", "play", word_ladder::read_lexicon("./english.txt"),
+                   expected);
+}
+
+TEST_CASE("awake -> sleep") {
+    const auto expected = std::vector<std::vector<std::string>>{
+        {"awake", "aware", "sware", "share", "sharn", "shawn", "shewn", "sheen",
+         "sheep", "sleep"},
+        {"awake", "aware", "sware", "share", "shire", "shirr", "shier", "sheer",
+         "sheep", "sleep"}};
+    check_generate("awake", "sleep", word_ladder::read_lexicon("./english.txt"),
+                   expected);
+}
+
+TEST_CASE("airplane -> tricycle") {
+    check_generate("airplane", "tricycle",
+                   word_ladder::read_lexicon("./english.txt"), {});
+}
+
+TEST_CASE("warm -> cold") {
+    const auto expected = std::vector<std::vector<std::string>>{
+        {"warm", "ward", "card", "cord", "cold"},
+        {"warm", "ward", "word", "cord", "cold"},
+        {"warm", "ward", "word", "wold", "cold"},
+        {"warm", "worm", "corm", "cord", "cold"},
+        {"warm", "worm", "word", "cord", "cold"},
+        {"warm", "worm", "word", "wold", "cold"},
+    };
+    check_generate("warm", "cold", word_ladder::read_lexicon("./english.txt"),
+                   expected);
+}
+
+// There are many solutions to this problem, but we can check that one of them
+// is equal to a solution found here:
+// http://datagenetics.com/blog/april22019/index.html
+// Unfortunately I had to add some words that were not present in english.txt
+// as the author uses an expanded dictionary (eg, unfaded didn't exist).
+TEST_CASE("atlases -> cabaret") {
+    const auto solution = std::vector<std::string>{
+        "atlases", "anlases", "anlaces", "unlaces", "unlaced", "unladed",
+        "unfaded", "unfaked", "uncaked", "uncakes", "uncases", "uneases",
+        "ureases", "creases", "cresses", "crosses", "crosser", "crasser",
+        "crasher", "brasher", "brasier", "brakier", "beakier", "peakier",
+        "peckier", "pickier", "dickier", "dickies", "hickies", "hackies",
+        "hackles", "heckles", "deckles", "deciles", "defiles", "defiled",
+        "deviled", "develed", "reveled", "raveled", "ravened", "havened",
+        "havered", "wavered", "watered", "catered", "capered", "tapered",
+        "tabered", "tabored", "taboret", "tabaret", "cabaret"};
+    const auto lexicon =
+        std::accumulate(std::begin(solution), std::end(solution),
+                        word_ladder::read_lexicon("./english.txt"),
+                        [](auto&& lexicon, const auto& word) {
+                            lexicon.emplace(word);
+                            return lexicon;
+                        });
+    const auto ladders = word_ladder::generate("atlases", "cabaret", lexicon);
+
+    if (const auto it = std::find_if(
+            std::begin(ladders), std::end(ladders),
+            [&solution](const auto& ladder) { return ladder == solution; });
+        it == std::end(ladders)) {
+        FAIL("failed to find solution");
+    }
+}