How to resolve the algorithm Last letter-first letter step by step in the Java programming language
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:
-
Class and Constants:
- The program defines a final class named
LastLetterFirstLetter
. - It declares static integer variables
maxPathLength
to track the maximum path length found andmaxPathLengthCount
to count paths of that length. - A static
StringBuffer
variablemaxPathExample
is used to store an example path of the maximum length.
- The program defines a final class named
-
Input List:
- The program provides a string array
names[]
containing a list of Pokemon names.
- The program provides a string array
-
Recursive Function
recursive
:-
The
recursive()
function takes two parameters:part[]
: A subset of thenames[]
array representing the current path.offset
: The current position in thepart[]
array.
-
The function checks if the current
offset
exceeds the current maximum path length (maxPathLength
):- If it does, it updates
maxPathLength
andmaxPathLengthCount
accordingly. - If it's equal to the maximum length, it increments
maxPathLengthCount
and constructs an example path inmaxPathExample
.
- If it does, it updates
-
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 positionoffset
.- If a word's first letter matches the
lastChar
, it swaps that word with the word at positionoffset
in thenames[]
array. - It then calls
recursive()
recursively to explore this new path, incrementingoffset
by 1. - After exploring this path, it swaps the words back to their original positions.
- If a word's first letter matches the
-
-
Main Logic:
- In the
main()
method, the program iterates through each word innames[]
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.
- In the
-
Output:
- Finally, the program prints:
- The maximum path length found.
- The number of paths with that length.
- An example path of that length.
- Finally, the program prints:
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