Output correct, solution not accepted

Frage zur Aufgabe

In der Diskussion

Once again, my solution produces a correct output, but it is not accepted. Except for using Math.random() - which is not an analytical way to a solution - where could I have gone wrong this time? Besides... the lection was about StringBuilder. Is this task about StringBuilder, too? PS: sorry for the commented out code. I thought I uploaded an updated version, but never mind...

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

Anforderungen:

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 */ 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;// = "f2209.txt"; List<String> words = new ArrayList<>(); try (BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in))) { fileName = bufferedReader.readLine(); } try (BufferedReader reader = new BufferedReader(new FileReader(fileName))) { while (reader.ready()) { words.addAll(Arrays.asList(reader.readLine().split(" "))); } } StringBuilder result = getLine(words.toArray(new String[0])); System.out.println(result.toString()); } public static StringBuilder getLine(String... words) { //System.out.println(Arrays.toString(words)); //ConnectedWord: checks first and last character, creates a list of connection candidates List<ConnectedWord> connectedWords = new ArrayList<>(); for (String word : words) { ConnectedWord connectedWord = new ConnectedWord(word); connectedWords.add(connectedWord); } //check for candidates for (ConnectedWord cwOuter : connectedWords) { for (ConnectedWord cwInner : connectedWords) { if (cwOuter == cwInner) { //check reference continue; } if (cwOuter.lastChar == cwInner.firstChar) { cwOuter.candidates.add(cwInner); } } } /*for (ConnectedWord cw : connectedWords) { System.out.println(cw.toString()); }*/ //Set<List<String>> combinations = new HashSet<>(); int maxSize = 0; List<String> maxCombination = null; for (ConnectedWord cw : connectedWords) { List<String> combination = new ArrayList<>(); ConnectedWord current = cw; for (int i = 0; i < connectedWords.size(); i++) { combination.add(current.word); int currentCandidatesSize = current.candidates.size(); if (currentCandidatesSize == 0) { break; } current = current.candidates.get((int)(Math.random() * currentCandidatesSize)); } if (maxSize < combination.size()) { maxSize = combination.size(); maxCombination = combination; } //combinations.add(combination); //System.out.println(combination); } //System.out.println(maxCombination); StringBuilder sb = new StringBuilder(); if (words.length == 0) { return sb; } if (maxCombination != null && !maxCombination.isEmpty()) { sb.append(String.join(" ", maxCombination)); } return sb; } }

Kommentare (6)

Beliebt
Neu
Alt

Du musst angemeldet sein, um einen Kommentar schreiben zu können

Thomas

Level 41 , Bayreuth, Germany

28 September 2023, 22:15

I tried your code and it outputs wrong results (that is not reproducible because of Math.random) test case:

words.addAll(Arrays.asList("Okinawa", "Washington", "Auckland", "Kalamazoo", "Norfolk", "na"));

output

Norfolk Kalamazoo Okinawa Auckland

that's not correct as you could put Washington in front have a look here Lupe gives a lot of good hints and I posted (nearly) a complete solution that's doing more than the task requires (finding the best solution). You just need to write a getLine method (that's basically what's in the main, just let it get one of the longest lists, collect joining and pass to a StringBuilder constructor), uncomment the block comment and delete line 20. Ah, I do a quick rewrite ;)

Thomas

Level 41 , Bayreuth, Germany

28 September 2023, 22:15

public class Task2209 {
    public static void main(String[] args) throws IOException {
        String[] data;
        try (BufferedReader console = new BufferedReader(new InputStreamReader(System.in));
             Stream<String> in = Files.lines(Paths.get(console.readLine()))) {

            data = in.flatMap(line -> Stream.of(line.split("\\h+"))).toArray(String[]::new);
        }
        System.out.println(getLine(data));
    }

    public static StringBuilder getLine(String... words) {
        // todo: add check words == null || empty
        return new StringBuilder(String.join(" ",
                new Task2209().permute(new ArrayList<>(Arrays.asList(words)), new ArrayList<>(), new ArrayList<>()) // returns a list of all possible permutations
                .stream().max(Comparator.comparing(List::size)).get())); // get one of the lists with the most elements, join and pass to sb constructor
    }

    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);

            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;
    }
}

resLin

Level 25 , Austria

30 September 2023, 00:12

Thanks for your help. I do not understand much of your code, I'm just a 23-level student.

Thomas

Level 41 , Bayreuth, Germany

30 September 2023, 06:52

The important part is in the link I posted before. There you can see how to get all permutations of a set of objects. And it shows you how to filter for the relevant parts. That you may want to look at closer and that only contains syntax level code (except the recursion? I do not remember) The additions here are neither important nor very pretty. They are just to run the code and press it into the getLine method. A proof of concept so to say. You easily can rewrite that. The main method you coded yourself already. So that should be clear. The getLine method now starts the permutation, the permute method expects three lists. The first contains the source strings (the ones you want to have all permutations from), then two empty lists. The result as said is a list with lists of strings. You now find the lists with the most elements and that are the best variants to group the strings. Take one and add the elements to a StringBuilder and return to main. That's what that code is doing. The getLine method rewritten:

public static StringBuilder getLine(String... words) {
        List<List<String>> allFilteredPermutations = new Task2209().permute(new ArrayList<>(Arrays.asList(words)), new ArrayList<>(), new ArrayList<>());
        // alternative 1, very basic
        int max = 0;
        for (List<String> e : allFilteredPermutations) {
            max = e.size() > max ? e.size() : max;
        }

        for (List<String> best : allFilteredPermutations) {
            if (best.size() == max)
                return new StringBuilder(String.join(" ", best));
        }
        return null;
        // alternative 2, with sorting... my initial code just no stream api
        // allFilteredPermutations.sort(Comparator.comparing(List::size));
        // return new StringBuilder(String.join(" ", allFilteredPermutations.get(allFilteredPermutations.size() - 1)));
}

resLin

Level 25 , Austria

9 Oktober 2023, 00:31

Thanks again for your help. I don't like recursion very much, because I'm too dumb for the concept and I think it does not improve code quality (except for some Field's Medal/Turing Award candidates). Also I did not want to go through all permutations of a set (resp. a list, because repetitions are not forbidden...(?)) and to have O(n!) complexity, so I just inquired the given words list for last-char -> first-char connections, I used that connections information and built lists of it, avoiding possible loops (i.e. _not_ allowed repetitions)... .. . My solution ist not pretty, not smart and not elegant, but it was accepted. This task has taken about a week of my time. I don't figure what I have learned from it, but maybe this is part of a strategy to tell "unfitted students" like me to quit studying.

Thomas

Level 41 , Bayreuth, Germany

9 Oktober 2023, 07:18

Some of the tasks are hard and there is not always a dedicated goal that you're supposed to achieve (at least that's what I always thought). Some cover basic problems and let you just code and gain practice. The easiest solution here is just to go through all the words and check if the first or last character of the picked word matches the first or last character of the result set. If no source words fit anymore you're finished (or maybe better, if the source list doesn't change anymore in an iteration). For every recursive approach you usually can form an iterative solution. Recursion however seems to be sometimes a lot more understandable but has the disadvantage of the resource usage (there's a limited method stack). Commonly used is recursion for problems similar to this one or for tree searches (iterating over trees).