How to resolve the algorithm Last letter-first letter step by step in the C++ programming language

Published on 7 June 2024 03:52 AM
#cpp

How to resolve the algorithm Last letter-first letter step by step in the C++ programming language

Table of Contents

Problem Statement

A certain children's game involves starting with a word in a particular category.   Each participant in turn says a word, but that word must begin with the final letter of the previous word.   Once a word has been given, it cannot be repeated.   If an opponent cannot give a word in the category, they fall out of the game.

For example, with   "animals"   as the category,

Take the following selection of 70 English Pokemon names   (extracted from   Wikipedia's list of Pokemon)   and generate the/a sequence with the highest possible number of Pokemon names where the subsequent name starts with the final letter of the preceding name. No Pokemon name is to be repeated.

Extra brownie points for dealing with the full list of   646   names.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Last letter-first letter step by step in the C++ programming language

The provided code in C++ implements an algorithm to find the longest path in a directed graph where the last letter of a word is the first letter of the next word. The code uses a recursive function called search to explore different paths and keep track of the longest path found so far. Here's a breakdown of what the code does:

  1. The last_letter_first_letter struct holds information about the longest path, including its length (max_path_length), the number of paths of that length (max_path_length_count), and an example path (max_path_example).

  2. The search function takes a vector of names (words) and an offset (indicating the current position in the path) as inputs. This function explores different paths by swapping the current word with the following words that start with the same letter as the last letter of the current word. It recursively calls itself with the updated vector and offset.

  3. The find_longest_chain function iterates through each word in the input vector, placing it as the first word in the path and calling the search function to explore different paths starting from that word. It keeps track of the longest path found during these iterations.

  4. In the main function:

    • A vector of names (words) is initialized.
    • An instance of the last_letter_first_letter struct is created to store the information about the longest path.
    • The find_longest_chain function is called to find the longest path in the given list of words.
    • The length of the longest path, the count of paths of that length, and an example path of that length are printed to the console.

In this example, the input vector of names contains Pokemon names. The code finds the longest path of Pokemon names where the last letter of one Pokemon's name is the first letter of the next Pokemon's name.

Source code in the cpp programming language

#include <iostream>
#include <string>
#include <vector>

struct last_letter_first_letter {
    size_t max_path_length = 0;
    size_t max_path_length_count = 0;
    std::vector<std::string> max_path_example;

    void search(std::vector<std::string>& names, size_t offset) {
        if (offset > max_path_length) {
            max_path_length = offset;
            max_path_length_count = 1;
            max_path_example.assign(names.begin(), names.begin() + offset);
        } else if (offset == max_path_length) {
            ++max_path_length_count;
        }
        char last_letter = names[offset - 1].back();
        for (size_t i = offset, n = names.size(); i < n; ++i) {
            if (names[i][0] == last_letter) {
                names[i].swap(names[offset]);
                search(names, offset + 1);
                names[i].swap(names[offset]);
            }
        }
    }

    void find_longest_chain(std::vector<std::string>& names) {
        max_path_length = 0;
        max_path_length_count = 0;
        max_path_example.clear();
        for (size_t i = 0, n = names.size(); i < n; ++i) {
            names[i].swap(names[0]);
            search(names, 1);
            names[i].swap(names[0]);
        }
    }
};

int main() {
    std::vector<std::string> names{"audino", "bagon", "baltoy", "banette",
        "bidoof", "braviary", "bronzor", "carracosta", "charmeleon",
        "cresselia", "croagunk", "darmanitan", "deino", "emboar",
        "emolga", "exeggcute", "gabite", "girafarig", "gulpin",
        "haxorus", "heatmor", "heatran", "ivysaur", "jellicent",
        "jumpluff", "kangaskhan", "kricketune", "landorus", "ledyba",
        "loudred", "lumineon", "lunatone", "machamp", "magnezone",
        "mamoswine", "nosepass", "petilil", "pidgeotto", "pikachu",
        "pinsir", "poliwrath", "poochyena", "porygon2", "porygonz",
        "registeel", "relicanth", "remoraid", "rufflet", "sableye",
        "scolipede", "scrafty", "seaking", "sealeo", "silcoon",
        "simisear", "snivy", "snorlax", "spoink", "starly", "tirtouga",
        "trapinch", "treecko", "tyrogue", "vigoroth", "vulpix",
        "wailord", "wartortle", "whismur", "wingull", "yamask"};
    last_letter_first_letter solver;
    solver.find_longest_chain(names);
    std::cout << "Maximum path length: " << solver.max_path_length << '\n';
    std::cout << "Paths of that length: " << solver.max_path_length_count << '\n';
    std::cout << "Example path of that length:\n  ";
    for (size_t i = 0, n = solver.max_path_example.size(); i < n; ++i) {
        if (i > 0 && i % 7 == 0)
            std::cout << "\n  ";
        else if (i > 0)
            std::cout << ' ';
        std::cout << solver.max_path_example[i];
    }
    std::cout << '\n';
}

You may also check:How to resolve the algorithm Wordle comparison step by step in the Raku programming language
You may also check:How to resolve the algorithm Josephus problem step by step in the Quackery programming language
You may also check:How to resolve the algorithm Loops/Wrong ranges step by step in the Wren programming language
You may also check:How to resolve the algorithm Singly-linked list/Element definition step by step in the ooRexx programming language
You may also check:How to resolve the algorithm Sum of squares step by step in the Mathematica/Wolfram Language programming language