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

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Last letter-first letter step by step in the Java 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 Java programming language

The provided Java program, LastLetterFirstLetter, is designed to find the longest possible path where each subsequent word in the path has its first letter matching the last letter of the previous word. It uses recursion to explore different combinations of words from a given list (names[]) and tracks the longest path and its count.

A detailed breakdown of the program:

  1. Class and Constants:

    • The program defines a final class named LastLetterFirstLetter.
    • It declares static integer variables maxPathLength to track the maximum path length found and maxPathLengthCount to count paths of that length.
    • A static StringBuffer variable maxPathExample is used to store an example path of the maximum length.
  2. Input List:

    • The program provides a string array names[] containing a list of Pokemon names.
  3. Recursive Function recursive:

    • The recursive() function takes two parameters:

      • part[]: A subset of the names[] array representing the current path.
      • offset: The current position in the part[] array.
    • The function checks if the current offset exceeds the current maximum path length (maxPathLength):

      • If it does, it updates maxPathLength and maxPathLengthCount accordingly.
      • If it's equal to the maximum length, it increments maxPathLengthCount and constructs an example path in maxPathExample.
    • It then finds the last character of the last word in the current path (lastChar).

    • It iterates through the remaining words in names[] starting from position offset.

      • If a word's first letter matches the lastChar, it swaps that word with the word at position offset in the names[] array.
      • It then calls recursive() recursively to explore this new path, incrementing offset by 1.
      • After exploring this path, it swaps the words back to their original positions.
  4. Main Logic:

    • In the main() method, the program iterates through each word in names[] as a potential starting point for a path.
    • For each starting point, it calls the recursive() function to explore all possible paths and updates the maximum path length and count accordingly.
  5. Output:

    • Finally, the program prints:
      • The maximum path length found.
      • The number of paths with that length.
      • An example path of that length.

Source code in the java programming language

// derived from C
final class LastLetterFirstLetter {
    static int maxPathLength = 0;
    static int maxPathLengthCount = 0;
    static final StringBuffer maxPathExample = new StringBuffer(500);

    static final 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"};

    static void recursive(String[] part, int offset) {
        if (offset > maxPathLength) {
            maxPathLength = offset;
            maxPathLengthCount = 1;
        } else if (offset == maxPathLength) {
            maxPathLengthCount++;
            maxPathExample.setLength(0);
            for (int i = 0; i < offset; i++) {
                maxPathExample.append((i % 5 == 0 ? "\n  " : " "));
                maxPathExample.append(part[i]);
            }
        }
        final char lastChar = part[offset - 1].charAt(part[offset - 1].length()-1);
        for (int i = offset; i < part.length; i++) {
            if (part[i].charAt(0) == lastChar) {
                String tmp = names[offset];
                names[offset] = names[i];
                names[i] = tmp;
                recursive(names, offset+1);
                names[i] = names[offset];
                names[offset] = tmp;
            }
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < names.length; i++) {
            String tmp = names[0];
            names[0] = names[i];
            names[i] = tmp;
            recursive(names, 1);
            names[i] = names[0];
            names[0] = tmp;
       }
       System.out.println("maximum path length        : " + maxPathLength);
       System.out.println("paths of that length       : " + maxPathLengthCount);
       System.out.println("example path of that length:" + maxPathExample);
    }
}


  

You may also check:How to resolve the algorithm Sierpinski triangle step by step in the PARI/GP programming language
You may also check:How to resolve the algorithm Ordered words step by step in the PowerShell programming language
You may also check:How to resolve the algorithm Forward difference step by step in the Lambdatalk programming language
You may also check:How to resolve the algorithm Sort using a custom comparator step by step in the Zig programming language
You may also check:How to resolve the algorithm Calendar - for REAL programmers step by step in the C programming language