CodeGym/Help with Java Tasks/Make a worst chain

Level 50

Kraków

17.03.2023
335views
8comments

Make a worst chain

Question about the task

Under discussion

Ok for me this task is like big head ache. After analize code Lisa L. from help section in Antony Chalk, I got a little grasp how to do it. I try do it by mysefl a little simpler and here what we get. (maybe not simpler, but with tools which I knows better, she use streams so ellegantly) But when I tried validate I got "TIME OUT" "The program ran too long and was closed!". Maybe you can tell me for start whether algorithm is accurate, and then why it's so robust for memory, and how to slim memory usage.

In the main method, read the name of a file that contains words separated by spaces from the console.
In the getLine method, use StringBuilder to order all the words as follows: the last letter of a word must match the first letter of the next word (ignore case).
Each word should be used once.
The getLine method can return any variant.
Separate words with a space.
Display the resulting string on the screen.

Example input file:

Okinawa Washington Auckland Kalamazoo Norfolk

Result:

Washington Norfolk Kalamazoo Okinawa Auckland

Requirements:

The main method must read the filename from the keyboard.
There should not be static fields in the Solution class.
The getLine method must use StringBuilder.
The getLine method must return an empty string (an empty StringBuilder) if it is not passed arguments (words).
The getLine method must not change the arguments (words).
All words passed to the getLine method must be included in the resulting string, if possible.
The screen output must match the task conditions.

package com.codegym.task.task22.task2209; /* Make a word chain Okinawa Washington Auckland Kalamazoo Norfolk Washington Norfolk Kalamazoo Okinawa Auckland /home/mati/temporary/file4.txt */ import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Solution { public static void main(String[] args) throws IOException { // ... String fileName = ""; try (BufferedReader nameReader = new BufferedReader(new InputStreamReader(System.in));) { fileName = nameReader.readLine(); } String string = ""; try (BufferedReader reader = new BufferedReader(new FileReader(fileName));) { while (reader.ready()) { String line = reader.readLine(); string += line; } } String[] words = string.split("\\s+"); System.out.println(getLine(words)); } // Okinawa Washington Auckland Kalamazoo Norfolk public static StringBuilder getLine(String... words) { if (words.length == 0) return new StringBuilder(); // list for every possible accurate chains List<String[]> fullList = new ArrayList<>(); for (int i = 0; i < words.length; i++) { String word = words[i]; List<String> wordsList = new ArrayList<>(Arrays.asList(words)); for (int j = 0; j < wordsList.size(); j++) { String secondWord = wordsList.get(j); if (word.equals(secondWord)) continue; if (!isEqual(word, secondWord)) continue; word = word + " " + secondWord; wordsList = new ArrayList<>(Arrays.asList(words)); wordsList.remove(secondWord); j = -1; } fullList.add(word.split("\\s+")); } // choose which chains is better int length = 0; for (String[] s : fullList) { if (s.length > length) length = s.length; } for (String[] s : fullList) { if (s.length == length) return new StringBuilder(Arrays.toString(s)); } return new StringBuilder(); } public static boolean isEqual(String s1, String s2) { return s1.toLowerCase().charAt(s1.length() - 1) == s2.toLowerCase().charAt(0); } }

Comments (8)

Popular
New
Old

You must be signed in to leave a comment

matemate123

Level 50 , Kraków, Poland

18 March 2023, 07:44

public static StringBuilder getLine(String... words) {
       if (words == null || words.length == 0)
           return new StringBuilder();

       // list for every possible accurate chains
       List<String[]> fullList = new ArrayList<>();
       List<String> wordsList = new ArrayList<>(Arrays.asList(words));
       for (int i = 0; i < words.length; i++) {
           String word = words[i];
           wordsList.remove(word);
           for (int j = 0; j < wordsList.size(); j++) {
               String secondWord = wordsList.get(j);
               if (!isEqual(word, secondWord))
                   continue;
               word = word + " " + secondWord;
               wordsList.remove(secondWord);
               j = -1;
           }
           String[] strings = word.split("\\s+");
           if (strings.length == words.length)
               return new StringBuilder(Arrays.toString(strings));
           fullList.add(strings);
           wordsList = new ArrayList<>(Arrays.asList(words));
       }

       // choose which chains is better
       int length = 0;
       for (String[] s : fullList) {
           if (s.length > length)
               length = s.length;
       }
       for (String[] s : fullList) {
           if (s.length == length)
               return new StringBuilder(Arrays.toString(s));
       }
       return new StringBuilder();
   }

I did a few changes. 20. return if list is full -> if (strings.length == words.length) 23. restarting wordList after inner loop --> wordsList = new ArrayList<>(Arrays.asList(words)); 10.remove word to not check it with itself. Validator not checking for 15 s and return TOO LONG, now after 1s Validator get me two red: All words passed to the getLine method must be included in the resulting string, if possible. I get good result for Lupe test from Ian De Bie post

Thomas

Level 41 , Bayreuth, Germany

18 March 2023, 10:49

useful

Have you tried to return the requested format? line 21: return new StringBuilder(String.join(" ", strings)); and line 34: return new StringBuilder(String.join(" ", s));

matemate123

Level 50 , Kraków, Poland

18 March 2023, 14:16

Unbelievable how stupid I am :D, I don't know why I don't see that, now only one red left: All words passed to the getLine method must be included in the resulting string, if possible. I don't know what else I can do.

Thomas

Level 41 , Bayreuth, Germany

18 March 2023, 15:49

useful

I don't really get what you do there ;) But if you want to find the best set (or any of the best sets) then I usually start to find all possible variants and make sure my algorithm really finds these.

public class AllPossib {
    public static void main(String[] args) {
        new AllPossib().permute(new ArrayList<>(Arrays.asList("a", "b", "c")),
        // new AllPossib().permute(new ArrayList<>(Arrays.asList("Okinawa", "Washington", "Auckland", "Kalamazoo", "Norfolk")),
                new ArrayList<>(),
                new ArrayList<>()
        ).stream().sorted(Comparator.comparing(List::size)).forEach(System.out::println);
    }

    List<List<String>> permute(List<String> allWords, List<String> lastIterationResult, List<List<String>> result) {

        for (int i = 0; i < allWords.size(); i++) {
            List<String> currentAllWords = new ArrayList<>(allWords);
            List<String> currentIterationResult = new ArrayList<>(lastIterationResult);

            String word = currentAllWords.remove(i);
            currentIterationResult.add(word);

            // add all possible variations to the result list
            result.add(currentIterationResult);

/*
            // in your case just add if lastIterationResult.size > 0 && lastIterationResult last index last char matches
            // this word first char
            String lastWord;
            if (lastIterationResult.size() == 0 ||
                    Character.toLowerCase((lastWord = lastIterationResult.get(lastIterationResult.size() - 1))
                            .charAt(lastWord.length() - 1)) == Character.toLowerCase(word.charAt(0)))
                result.add(currentIterationResult);
            else
                continue;
*/
            permute(currentAllWords, currentIterationResult, result);
        }
        return result;
    }
}
</

Thomas

Level 41 , Bayreuth, Germany

18 March 2023, 15:56

useful

If you run the above code then it ouputs all possible variations of abc

[a]
[b]
[c]
[a, b]
[a, c]
[b, a]
[b, c]
[c, a]
[c, b]
[a, b, c]
[a, c, b]
[b, a, c]
[b, c, a]
[c, a, b]
[c, b, a]

This you should try for your algorithm, too. If that does not work you need to rethink the entire approach. Now you can add code that just adds a word to the current iterations result if that result list is either empty or if the last words last char equals current words first char. That's pretty much all the magic. To test uncomment 22-32 and comment out 20. Also adapt lines 3 and 4. (This algorithm here is far from being optimized, it uses lists for everything incl. intermediate results -> not really good ;) ) The task itself however does not ask for the best set, just for one possible set. So it should work if you just start with any word, and test the next if it fits at the beginning or the end. If not, try the next till you're at the end, repeat the whole loop till no more adding of a word is possible (ahh, Lupe already said that, just more eloquently, hahaha).

Guadalupe Gagnon

Level 37 , Tampa, United States

17 March 2023, 14:19

useful

This may or may not be a problem depending on Codegym's test data but lines 29-30 present a bug. Imagine we have a file such as: "Okinawa Washington Auckland Kalamazoo Norfolk" That bit of code would read the file and create this as the String: "Okinawa WashingtonAuckland KalamazooNorfolk" There is an issue in the algorithm that is more of a problem where the code comes to reaches a dead end and can't append the remaining words onto the chain but continues to try to do so infinitely. Take, as an example, the input: "Kalamazoo Norfolk Washington Auckland Oconomowoc Okinawa" In this scenario "Oconomowoc" confuses the algorithm and an infinite loop is achieved.

Guadalupe Gagnon

Level 37 , Tampa, United States

17 March 2023, 14:28

useful

The task doesn't say every word must be used. It doesn't even say that the longest chain must be used. The task wants you to return any complete chain that exists in the data that is given. If the data contains 100 words and your algorithm returns a **complete chain of only 2 of those 100 words, then that is acceptable. **complete means that no other words can fit on the chain. Either at the beginning, anywhere in the middle, or at the end.

matemate123

Level 50 , Kraków, Poland

17 March 2023, 15:50

Thanks like always Lupe! First problem in line 30 I resolved change for

string += line + " ";

I tried commented line 58 with : j = -1; (little simplify and memory saving) But now when I only 3 results Verificator tell me: "Test your solution using the example in the task conditions. All the words should be displayed." because All words passed to the getLine method must be included in the resulting string, if possible. Ok I must go for long driving but after couple hours I sit and try something different. Thanks mate!