[CodeMonkeys] insertFirst - 2 Tests fliegen mit einem Timeout raus

Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
crankicake
Neuling
Neuling
Beiträge: 9
Registriert: 22. Jan 2017 16:02

[CodeMonkeys] insertFirst - 2 Tests fliegen mit einem Timeout raus

Beitrag von crankicake »

Hi zusammen,

folgend erstmal mein Code (bitte keine Kommentare zur Effizienz, ich habe einiges abgeändert um den Fehler irgendwie einzugrenzen :mrgreen: )

Code: Alles auswählen

{
    if(el == null)
    {
        return false;
    }
    
    int groesse = 0;
    boolean istda = false;
    
    ListElement<T> tmp = new ListElement<T>();
    for(ListElement<T> p = el; p != null; p = p.next())
    {
        groesse++;
        tmp = p;
        if(contains(p))
            istda=true;
    }
    
    if(istda)
        return false;
        
    if(isEmpty())
    {
        if(groesse == 1)
        {
            setFirst(el);
            setLast(el);
            setSize(1);
            return true;
        }
        setFirst(el);
        setLast(tmp);
        setSize(groesse);
        return true;
    }
    tmp.setNext(getFirst());
    setFirst(el);
    setSize(size()+groesse);
    return true;
}
Es laufen auch 9/11 Tests durch, jedoch die folgenden beiden leider nicht und ich bin langsam ratlos warum

Code: Alles auswählen

Antwort des Servers
Junitreport
Time – 220
Testcount – 11
Failurecount – 2
Ignorerecount – 0
Failurereport
Testheadder – basic_10_Insertion_with_loop_of_a_non_null_non_single_element_in_the_list(singly_linked_list.insert.test_insertFirst.LinkedList_insertFirst)
Message – test timed out after 100 milliseconds
Trace 
Failurereport
Testheadder – basic_09_Insertion_with_loop_of_a_non_null_non_single_element_in_the_list_with_single_element(singly_linked_list.insert.test_insertFirst.LinkedList_insertFirst)
Message – test timed out after 100 milliseconds
Trace 
Der Trace sagt, der Timeout fliegt bei der contains-methode.

Habt ihr eine Idee?

Viele Grüße
Salim

Robin Ferrari
Erstie
Erstie
Beiträge: 15
Registriert: 15. Apr 2016 10:16

Re: [CodeMonkeys] insertFirst - 2 Tests fliegen mit einem Timeout raus

Beitrag von Robin Ferrari »

Hey Salim

Das Problem ist, dass die beiden Tests endlos Schleifen übergeben. D.h. e1 -> e2 -> e1 (-> = next). Somit wird p nie null und deine for Schleife terminiert nicht.

contains() vergleicht wohl nur das Element mit der bereits vorhandenen Liste, also ab getFirst().

Meine Lösung ist, eine geschachtelte Schleife die schaut, ob el eine Endlosschleife ist:

Code: Alles auswählen

for (ListElement<T> p = el; p != null; p = p.next()) {
    if (contains(p)) {
        return false;
    }
    for (ListElement<T> p1 = p.next(); p1 != null; p1 = p1.next()) {
        if(p1.next() == p.next()) {
            return false;
        }
    }...
LG
Robin

crankicake
Neuling
Neuling
Beiträge: 9
Registriert: 22. Jan 2017 16:02

Re: [CodeMonkeys] insertFirst - 2 Tests fliegen mit einem Timeout raus

Beitrag von crankicake »

Hi Robin,

danke erstmal für deine Antwort. Das wäre natürlich logisch, sollte das der Fall sein.

Wir haben in der Methodenbeschreibung doch stehen
"* @param ListElement<T> el : the element to insert
@constraint ListElement<T> el : valid ListElement<T> or null
@assert ListElement<T> el : valid ListElement<T> or null
"

Würde man ein Element übergeben, dessen nachfolgende Elemente nicht richtig "verknüpft" sind, gelten diese noch als gültig? @Professor Weihe
:?:
LG
Salim

Dadung
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 7. Mai 2017 13:08

Re: [CodeMonkeys] insertFirst - 2 Tests fliegen mit einem Timeout raus

Beitrag von Dadung »

Hallo,

ich habe mich auch mal mit der Aufgabe befasst und bin auch zu dem Problem mit den beiden Timeouts gekommen (obwohl ich eigentlich loops überprüft habe, aber ein Vergleich mit equals mit dem Grundelement scheint nicht effektiv zu sein). ich habe jetzt einfach eine etwas "harte Lösung genommen und zwar nach hundert Durchläufen im Listenelement einfach false zurückzugeben.

Für Interessierte, hier ist der Code, der jetzt alle Tests besteht:

Code: Alles auswählen

{
    if (el == null){
        return false;
    }
    
    if (contains(el)){
        return false;
    }
        
    
    ListElement<T> ell = el;
    int i = 1;
    
    while (ell.hasNext()){
        ell = ell.next();
        i++;
        
        if (contains(ell)){
            return false;
        }
        
        
        if (ell.equals(el)){
            return false;
        }
        
        if (i > 100){
            return false;
        }
    }
    
    ListElement<T> l = getLast();
    if (l == null){
        l = ell;
    }
    ell.setNext(getFirst());
    setFirst(el);
    setSize(size() + i);
    setLast(l);
    return true;
}
er ist zum teil etwas unschön, aber mich hat die Motivation verlassen das noch ordentlich zu machen.

goerlibe
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 24. Apr 2017 19:22

Re: [CodeMonkeys] insertFirst - 2 Tests fliegen mit einem Timeout raus

Beitrag von goerlibe »

Ich und auch einige Freunde von mir haben bereits sehr viel Zeit in diese Aufgabe investiert und wir sind allesamt nicht in der Lage, die Aufgabe vollständig und ohne irgendwelche Tricks zu lösen - und wenn man sich hier im Forum umschaut sind wir damit nicht die Einzigen.
btw. es kann nicht sein, dass man einfach nach 100 Elementen einen Schlussstrich zieht, auch wenn das für die Tests funktionieren mag... an dieser Stelle packt mich dann doch der Ehrgeiz, es richtig umzusetzen!

Daher meine Bitte an Tutoren / Prof. Weihe etc.:
Bitte geben Sie uns eine beispielhafte Implementierung, um unsere Fehler nachzuvollziehen.
Bitte passen Sie die Schwierigkeitsbewertung der Aufgabe entsprechend an - 4 Punkte für so eine offensichtlich aüßerst anspruchsvolle Aufgabe sind nicht zu rechtfertigen.

kommiker
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 24. Apr 2017 19:25

Re: [CodeMonkeys] insertFirst - 2 Tests fliegen mit einem Timeout raus

Beitrag von kommiker »

Hänge nun seit 2 Tagen an dem selben, bzw. an einem ähnlichen Problem.
Die Problematik das man die übergebenen, linked Elemente auf eine Loop untersuchen soll, ist finde ich ziemlich schwer und tritt leider nicht nur bei InsertFirst auf. (Insert und InsertLast sind ebenfalls betroffen.)
Ich, und meine Lerngruppe, finden seit 2 Tagen keine Lösung dafür und wir würden uns wirklich über eine Beispielimplementation freuen.

Liebe Grüße

Robin Ferrari
Erstie
Erstie
Beiträge: 15
Registriert: 15. Apr 2016 10:16

Re: [CodeMonkeys] insertFirst - 2 Tests fliegen mit einem Timeout raus

Beitrag von Robin Ferrari »

Hi Leute ;)

EDIT:

Mir ist aufgefallen, dass meine vorherige Lösung nur loops in einer Liste von 3 Elementen abfängt. Wenn es mehr werden, würde die Lösung nicht funktionieren, die Tests hatten wohl nur max 3 Elemente... Deswegen habe ich eigentlich die Idee von hallo6 eingebaut, weil ich die gut fand und glaube, jetzt sollten beliebig lange Listen abgefangen werden.

Hier mal meine (aktualisierte) Implementierung (die alle Tests besteht):

Code: Alles auswählen

{
    // 1. null
    if (el == null) {
        return false;
    }
    
    // 2. go to end of el
    ListElement<T> tmp = new ListElement();
    int cnt = 0;
     for (ListElement<T> p = el; p != null; p = p.next()) {
        if(contains(p)) {
            return false;
        }
        ListElement<T> p1 = el;
        for (int i = 0; i < cnt; i++) {
            if (p1 == p) {
                return false;
            }
            p1 = p1.next();
        }
        tmp = p;
        cnt++;
    }

    
    // 3. isEmpty
    if (isEmpty()) {
        setFirst(el);
        setLast(tmp);
        setSize(cnt);
        return true;
    }
    
    // 4. else
    tmp.setNext(getFirst());
    setFirst(el);
    setSize(size() + cnt);
    return true;
}
LG Robin
Zuletzt geändert von Robin Ferrari am 16. Mai 2017 16:26, insgesamt 1-mal geändert.

hallo6
Erstie
Erstie
Beiträge: 14
Registriert: 4. Mai 2017 10:36

Re: [CodeMonkeys] insertFirst - 2 Tests fliegen mit einem Timeout raus

Beitrag von hallo6 »

Eine andere Möglichkeit wäre die folgende:

Code: Alles auswählen

        int pointerindex = 0;
        for(ListElement<T> pointer = el; pointer != null; pointer = pointer.next()){
            if(contains(pointer)) return false;
            int cpointerindex = 0;
            ListElement<T> cpointer = el;
            while(cpointerindex < pointerindex){
                if(pointer == cpointer) return false;
                cpointer = cpointer.next();
                cpointerindex++;
            }
            pointerindex++;
        }

Robin Ferrari
Erstie
Erstie
Beiträge: 15
Registriert: 15. Apr 2016 10:16

Re: [CodeMonkeys] insertFirst - 2 Tests fliegen mit einem Timeout raus

Beitrag von Robin Ferrari »

Hallo

habe meinen Beitrag editiert, da im alten ein Fehler war. Der hat zwar alle Tests bestanden, aber nur weil die test Listen mit loops nicht über 3 Elemente war.

Lg
Robin

Antworten

Zurück zu „AuD: Programmieraufgaben“