Codewars akzeptiert Lösung nicht

[Hallo1234]

Hallo, das ist der Code in Eclipse:

public static String kata3(int num) {


        String a = String.valueOf(num);
        char[] div = new char[a.length()]; //8

        for(int i=0; i<a.length(); i++) {
        div[i] = a.charAt(i);
        }
        
        char temp = 0;
        for(int i=0; i<div.length-1; i++) {
            for(int j=0; j<div.length-1; j++) {
                if(div[j]>div[j+1]) {
                    temp = div[j];
                    div[j] = div[j+1];
                    div[j+1] = temp;
                }
            }
        }
        for(int i=0; i<div.length; i++) {
            System.out.println(div[i]);
        }

        return a;

    }

Es funktioniert. Die Zahlen eines Integers werden in absteigender Reihenfolge sortiert. Bei Codewars klappt es allerdings nicht. Hier mal ein Screenshot:

Ich habe den Rückgabewert zu num geändert. Das ist der einzige Unterschied. Weiß jemand, warum es bei Codewars nicht funktioniert?

 

[Meniskusschaden]

Weiß jemand, warum es bei Codewars nicht funktioniert?

Du sortierst zwar die Ziffern im Array div, aber du lieferst mit dem String a die unsortierten Ziffern an den Aufrufer zurück.

 

[Hallo1234]

num funktioniert als Rückgabewert auch nicht. div ebenfalls nicht.
Ich habe schon damit versucht:
int test = 0;
for(...){
...
test = div
}

return test;

Klappt nicht. Was müsste denn der Rückgabewert sein?

 

[kneitzel]

Also die genaue Aufgabe hast Du uns nicht gegeben. Daher werden wir Dir nicht sagen können, was zurück gegeben werden muss.

Wenn ein String mit den sortierten Zeichen zurück gegeben werden soll, dann musst Du so einen String aufbauen.

 

[Hallo1234]

Das ist die Aufgabe

 

[stg]

Klappt nicht. Was müsste denn der Rückgabewert sein?

.... ein integer, kein String

 

[betatwo]

Countingsort

 

[Barista]

Die Idee mit dem String ist insofern in Ordnung, wenn ein String als Zwischenspeicher benutzt wird.

Die Aufgabe ist leicht, weil sich die einzelnen Teilaufgaben ohne gegenseitige Abhängigkeit lösen lassen.

1. Umwandeln der übergebenen Zahl in einen String.

2. Sortieren der einzelnen Zeichen (Klasse Character) in absteigender Reihenfolge

3. Umwandeln der sortierten Zeichen in einen weiteren String

4. Umwandeln des zweiten String in eine Zahl und zurückgeben.

Zu jeder Teilaufgabe sollte eine Internet-Suche jede Menge Treffer liefern.

Die einzelnen Lösungen einfach zusammenfügen.

 

[Oneixee5]

.... ein integer, kein String

Also wenn ich die Aufgabe richtig lese, dann muss der Rückgabe-Typ der Methode BigInteger oder Long sein.
Zu "any not-negative integer" zählt bei mir auch Integer.MAX_VALUE. Wenn man diesen Wert, entsprechend der Aufgabe, umbaut erhält man: "8776444321". Integer bzw. int kann diesen Wert nicht aufnehmen, es würde wenigstens zu einem Überlauf kommen. Nach dem Überlauf ist es aber eben nicht mehr die "highest possible number".

Hier mal als Testprogramm (inkl. negativer Werte und zusätzlicher innerer Klasse - ich wollte eine mögliche Lösung nicht komplett verraten):

public class App {

    private static final class Iter implements OfInt {

        private static final int DIVIDER = 10;

        private int value;

        Iter(final int value) {
            this.value = value;
        }

        @Override
        public int nextInt() {
            final int ret = value % DIVIDER;
            value = value / DIVIDER;
            return ret;
        }

        @Override
        public boolean hasNext() {
            return value != 0;
        }

    }

    public static BigInteger kata3(final int num) {
        final Spliterator<Integer> spliterator =
                Spliterators.spliteratorUnknownSize(new Iter(num), Spliterator.IMMUTABLE);
        return StreamSupport.stream(spliterator, false)
                .sorted((a, b) -> b - a)
                .map(BigInteger::valueOf)
                .reduce((a, b) -> a.multiply(BigInteger.valueOf(10)).add(b))
                .orElse(BigInteger.ZERO);
    }

    @Test
    void testKata3() {
        assertEquals(new BigInteger("10"), App.kata3(10));
        assertEquals(new BigInteger("9"), App.kata3(9));
        assertEquals(new BigInteger("1"), App.kata3(1));
        assertEquals(new BigInteger("0"), App.kata3(0));
        assertEquals(new BigInteger("-1"), App.kata3(-1));
        assertEquals(new BigInteger("-9"), App.kata3(-9));
        assertEquals(new BigInteger("-1"), App.kata3(-10));

        assertEquals(new BigInteger("54421"), App.kata3(42145));
        assertEquals(new BigInteger("654321"), App.kata3(145263));
        assertEquals(new BigInteger("987654321"), App.kata3(123456789));

        assertEquals(new BigInteger("8776444321"), App.kata3(Integer.MAX_VALUE));
        assertEquals(new BigInteger("-1234446788"), App.kata3(Integer.MIN_VALUE));
    }

}

Man kann den Code leicht auf Integer umbauen, indem man .map(BigInteger::valueOf) und .orElse(BigInteger.ZERO entfernt oder ändert. Ein Test mit Integer.MAX_VALUE wird dann fehlschlagen.

Countingsort - habe ich jetzt mal außen vor gelassen, diese Schleifen-Gedöns ist mir zu hässlich.

 

[betatwo]

Es geht (mit etwas Rechnen) auch ganz ohne Strings und BigInteger:

public class Test {
    public static int kata3(int num) {
        final int n = (int) Math.log10(num) + 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (geti(num, j) < geti(num, j + 1)) {
                    num = swap(num, j, j + 1);
                }
            }
        }
        return num;
    }

    private static int geti(int num, int i) {
        int n = (int) Math.log10(num);
        return num / (int) Math.pow(10, n - i) % 10;
    }

    private static int swap(int num, int i, int j) {
        int a = geti(num, i);
        int b = geti(num, j);
        int n = (int) Math.log10(num);
        int num1 = getPre(num, i) + b * (int) Math.pow(10, n - i);
        int num2 = getMid(num, i, j) * (int) Math.pow(10, n - j + 1);
        int num3 = a * (int) Math.pow(10, n - j) + getPost(num, j);
        return num1 + num2 + num3;
    }

    private static int getPre(int num, int i) {
        int n = (int) Math.log10(num) + 1;
        return num / (int) Math.pow(10, n - i) * (int) Math.pow(10, n - i);
    }

    private static int getPost(int num, int i) {
        int n = (int) Math.log10(num) + 1;
        return num % (int) Math.pow(10, n - i - 1);
    }

    private static int getMid(int num, int i, int j) {
        if (j - i <= 1) {
            return 0;
        }
        int n = (int) Math.log10(num) + 1;
        return num % (int) Math.pow(10, n - i - 1) / (int) Math.pow(10, n - j);
    }

    public static void main(String[] args) {
        System.out.println(kata3(438245789));
    }
}

Als Sortieralgorithmus wählte ich hier BubbleSort...

 

[mihe7]

Es geht (mit etwas Rechnen) auch ganz ohne Strings und BigInteger:

Ja, das gibt es auch in effizient und schön

 

[betatwo]

Ja, das gibt es auch in effizient und schön

Her damit 😁

 

[mihe7]

Das ist nix besonderes: Countingsort und schöne Variablennamen.

 

[betatwo]

Kannst du mir eine pn schreiben?

 

[Oneixee5]

Es geht (mit etwas Rechnen) auch ganz ohne Strings und BigInteger:

Ja klar:

public static void main(final String[] args) {
        System.out.println(kata3(Integer.MAX_VALUE));
    }

Exception in thread "main" java.lang.ArithmeticException: / by zero
        at com.example.Test.geti(Test.java:18)
        at com.example.Test.kata3(Test.java:8)
        at com.example.Test.main(Test.java:50)

 

[betatwo]

Von Integer.MAX_VALUE hat keiner gesprochen. Die höchste im Beispiel angegebene Zahl war 123456789 und das ist erfüllt. Ich weiß nicht was du für ein Problem hast.

Integer.MAX_VALUE darf so oder so als Eingabe nicht erlaubt sein, weil die Ziffern absteigend sortiert kein valides int mehr darstellen. Wenn du long verwenden willst, dann musst du angeben, weshalb du von den Anforderungen abweichen willst.

 

[LimDul]

Von Integer.MAX_VALUE hat keiner gesprochen. Die höchste im Beispiel angegebene Zahl war 123456789 und das ist erfüllt. Ich weiß nicht was du für ein Problem hast.

Integer.MAX_VALUE darf so oder so als Eingabe nicht erlaubt sein, weil die Ziffern absteigend sortiert kein valides int mehr darstellen. Wenn du long verwenden willst, dann musst du angeben, weshalb du von den Anforderungen abweichen willst.

Was als Beispiel angegeben ist, kann man ja nun nicht wirklich heranziehen.
Aufgabenstellung war "Any non negative Integer, damit wäre MAX_VALUE auch erlaubt - interessant ist, dass da steht return "it", was Integer impliziert. Ich würde sagen, die Aufgabe ist an der Stelle unterspezifiziert

 

[kneitzel]

Von Integer.MAX_VALUE hat keiner gesprochen.

Die Aufgabe sprach von "any non-negative integer". Da gehört MAX_VALUE mit dazu.

 

[mihe7]

@betatwo

public class Test {
    public static long sortiere(int zahl) {
        int[] ziffern = new int[10];
        int rest = zahl;
        while (rest > 0) {
            ziffern[rest % 10]++;
            rest /= 10;
        }

        long ergebnis = 0;
        for (int ziffer = 9; ziffer >= 0; ziffer--) {
            while (ziffern[ziffer] > 0) {
                ergebnis = ergebnis * 10 + ziffer;
                ziffern[ziffer]--;
            }
        }

        return ergebnis;
    }

    public static void main(String[] args) {
        System.out.println(Test.sortiere(Integer.MAX_VALUE));
    }
}

Der Algorithmus hat lineare Laufzeit, wobei das bei den paar Stellen eigentlich eh keine Rolle spielt (bei String-/BigInteger-Eingabe sieht das wieder anders aus). Und wenn man will, teilt man den Spaß (sortiere) noch in zwei Methoden auf.

 

[betatwo]

@mihe7 Das ist ja Countingsort. Unverschämtheit!

 

[mihe7]

@mihe7 Das ist ja Countingsort. Unverschämtheit!

Ja, habe ich doch geschrieben - Du im übrigen vorher auch

 

[betatwo]

BTW 1999999999 wäre noch schlimmer als Integer.MAX_VALUE... Man kann praktisch nicht sinnvoll vorher prüfen, welche Ziffernfolgen hinterher absteigend sortiert noch ein valides int wären, ohne den internen Algorithmus zu starten. Intern kann der Algo natürlich mit long hantieren, aber wenn der Rückgabetyp anders sein soll, so muss man wenigstens die Anforderungen (der Aufgabenstellung) beachten. Die Aufgabenstellung ist mir nicht so klar.

@mihe7 Du hast den Schleifenspaß dabei, den wollte ich eigentlich vermeiden... Sollte Performancemäßig aber überhaupt nicht schlimm sein. (Sogar, wenn man des Spaß ganz oft aufrufen würde...)

 

[mihe7]

Du hast den Schleifenspaß dabei, den wollte ich eigentlich vermeiden...

Was meinst Du? (Du hast in Zeilen 4 und 5 ja auch zwei Schleifen)

 

[betatwo]

Was meinst Du? (Du hast in Zeilen 4 und 5 ja auch zwei Schleifen)

Ja, das ist der Sortieralgorithmus. Es geht darum, wie du ergebnis zusammensetzt. Du setzt Ziffer für Ziffer zusammen (Iteration), ich setzte drei Teilzahlen rechnerisch zusammen mit Addition (ohne Iteration). Theoretisch geht es um O(3) vs. O(n). Die Krux an der Sache ist nur, dass deins wahrscheinlich schneller ist, weil dieses O(3) einen laaangen Rattenschwanz nach sich zieht ...

 

[Meniskusschaden]

Theoretisch geht es um O(3) vs. O(n).

Das ist aber ein seltsamer Vergleich, weil deine O(3) bei jeder Vertauschung anfallen - also im schlimmsten Fall O(n²) mal. Die O(n) bei @mihe7 sind dagegen schon der vollständige Aufwand für das Zusammensetzen (und auch für den Gesamtalgorithmus).

 

[betatwo]

Ja, ich schreibe extra dass ich den Sortieralgorithmus aus der Betrachtung genommen habe. Hätte ich auch Countingsort eingesetzt wären die Laufzeiten vergleichbar. Lesekompetenz kann man nicht zu deinen Stärken zählen, oder?

 

[Meniskusschaden]

Du setzt Ziffer für Ziffer zusammen (Iteration)

Wenn es dir besser gefällt, könnte man die innere Schleife bei @mihe7 übrigens auch dadurch ersetzen:

ergebnis = ergebnis * (int)Math.pow(10, ziffern[ziffer]) + ziffer*(int)(1.0/9*(Math.pow(10, ziffern[ziffer])-1));

Aber es geht bestimmt auch irgendwie noch hässlicher.

Hätte ich auch Countingsort eingesetzt wären die Laufzeiten vergleichbar.

Ja, dann wären es bei dir O(3)*O(n) = O(n). Ändert aber wenig daran, dass dein Vergleich O(3) zu O(n) Murks ist, weil man deine Ergebniszusammensetzung nicht isoliert vom Sortierteil betrachten kann. Genau das hast du aber suggeriert. War aber vielleicht nur eine schwächelnde Schreibkompetenz.

 

[Meniskusschaden]

Wenn es dir besser gefällt, könnte man die innere Schleife bei @mihe7 übrigens auch dadurch ersetzen:

Habe noch etwas vergessen: So kommt die Ergebniszusammensetzung von @mihe7 auf O(10) = O(1) (zumindest wenn man die Komplexität von Math.pow() außer Acht lässt).

 

[mihe7]

Genau genommen wäre die Schrittzahlfunktion 10*a + b*n, wobei a und b Konstanten für die anzusetzenden Elementarfunktionen sind (sprich: je nachdem, was man zählt). Die Komplexität wäre also O(n). Da für alle int aber n <= 10 gilt, kann man auch O(1) annehmen. Würde man das auf größere Zahlen ausweiten, dann läge die Komplexität natürlich in O(n). Zumindest, wenn ich das richtig sehe

 

[betatwo]

Na, ich denke, der @mihe7 hat recht. Das Zusammensetzen der Zahl findet bei mir ja innerhalb des Sortieralgorithmus statt. Und hätte ich auch Countingsort gewählt, so hätten wir beide dieselbe asymptotische Komplexität, jedoch wäre meine Variante um den Faktor 10 langsamer.

Derzeit ist meine Variante ja sogar um den Faktor n*10 langsamer... (auch, wenn das n natürlich begrenzt ist ... )

https://i.giphy.com/media/hLjGJlBDqQ4Btfhs0C/giphy480p.mp4