Spotify Puzzle Lottery - Logikfehler oder Problem mit spotify-bot ?-



  • Hallo,

    ich bin seit ca. 3 Wochen dabei, C zu lernen und habe mich an dem Spotify-Puzzle "Lottery" versucht (http://www.spotify.com/se/jobs/tech/ticket-lottery/). Nach einiger Zeit hatte ich den ersten Code zusammen, der meiner Meinung nach korrekt ist. Nach Einsenden des Codes erhielt ich eine Bot-generierte Antwort: "Wrong Answer". Da ich (auch nach Abgleich mit öffentlichen Lösungen zu dem Problem) nicht nachvollziehen kann, wo der Fehler liegt, hier meine Frage:

    Habe ich in der Tat einen Logikfehler im Programm oder ist der ergibt sich die Problematik durch den Bot (z.B. fehlerhaftes Eingabe/Ausgabeformat)?

    Ich hoffe ich konnte mich verständlich ausdrücken, um eine Antwort wäre ich sehr dankbar.

    Ich lerne C online über www.cs50.tv , nutze daher die CS-50-Appliance (Fedora-basierend) und GCC.

    Ich wäre jedem sehr dankbar, der mir als Anfänger da einen Hinweis geben könnte

    Best

    Hier mein Code:

    /******************************************************************************************
    *lottery.c
    * 
    *Spotify Puzzle - Ticket Lottery
    *
    *
    *solves Spotify Ticket Lottery Puzzle (http://www.spotify.com/ch-de/jobs/tech/ticket-lottery/)
    *******************************************************************************************/
    
    #include <stdio.h>
    #include <stdlib.h>
    
    // function prototype for factorial function
    long double fact(int);
    
    int 
    main(void)
    {
        int m, n, t, p;
        scanf("%d %d %d %d", &m, &n, &t, &p);
        // sanity check
        if(m < 1 || m > 1000 || n < 1 || n > m || t < 1 || t > 100 || p < 1 || p > m)
        {   
            printf("Please provide valid input\n");
            return 1;
        }
         // x people needed to win in order to gain sufficient tickets for group
        int x; 
        float d = ( (float) p / (float) t );
        if ((d - (int) d) == 0)
            x = (int) d;
        else
            x = (int) d + 1;
        long double prob = 0;
        long double temp;
        // checks if enought tickets for group exists
        if ( n*t < p)
            prob = 0;
        else 
        {    
            int y;
            if ( p < n )
                y = p;
            else
                y = n;
            // for loop sums up probabilities for x to min(p, n) people to be chosen as winners
            for (int q = x; q <= y; q++)
            {
                /*
                 *Calculates Probability of q (x <= q <= y, y = min(p, n)) group-members to be chosen as winners according to:
                 *
                 *P(WinnersOutOfGroup=q, WinnerOutsideGroup=n-q)= ((pCq)*((m-p)C(n-q)))/(mCn)
                 *
                 *with "nCk" binominal coefficent "n chose k", 
                 *"pCq" equals number of ways to chose q person(s) out of the group (of size p)
                 *"(m-p)C(n-q)" equals number of ways to chose the remaining (n-q) people of lottery-winners out of the people outside the group (m-p)
                 *"(m)C(n)" equals total number of ways to chose n lottery-winners out of total participants (m)
                 *
                 */
                temp=(fact(p)/(fact(q)*fact(p-q))*(fact(m-p)/(fact(n-q)*fact(m-p-n+q))))/(fact(m)/(fact(n)*fact(m-n)));
                prob += temp;
            }
        }
        printf("%.10Lf\n", prob);
        return 0;
    }
    
    /*
     *calculates factorial of number, used in main to calculate binominal coefficent
     */
    
     long double
     fact(int x) 
     { 
         if(x>1) 
            return x*fact(x-1); 
         else 
            return 1; 
     }
    

    Best


  • Mod

    Ich kann auf den ersten und auch auf den zweiten Blick keinen logischen oder technischen Fehler entdecken. Es ist sicherlich nicht das beste Programm, welches ich jemals gesehen habe, sollte die Aufgabe jedoch erfüllen.

    Hat denn der Bot nicht mehr gesagt?

    Aufgabenstellung schrieb:

    Within minutes you will get a reply indicating whether your source code solved the problem, and if it didn't, an indication of what was wrong.



  • Ohne mir das jetzt weiter angesehen zu haben: Kann es sein, dass deine Fakultäten überlaufen? Überleg mal, ob es nicht vielleicht einen clevereren Weg gibt, Binomialkoeffizienten zu berechnen ... bei dem die Zwischenergebnisse nicht so groß sind.



  • @Bashar
    Meinst du das lustige Pyramidending?



  • Das Pascalsche Dreieck? Nein, das meinte ich nicht.



  • Aaaaaah, du meintest das mit dem lustigen "Korinthische Säulen mit Brett drüber" Symbol 😃


  • Mod

    Ich vermute eher, es soll in Richtung clevere Reihenfolge der Berechnung gehen, nicht in die Richtung umständlicher Algorithmus 😉 . Man braucht ja nicht erst den kompletten Zähler mit einem Wert von 20 Quadrilliarden auszurechnen, um ihn dann durch 5 Quadrilliarden im Nenner zu teilen, so dass man am Ende eine 4 heraus bekommt.



  • Versteh ich grade euren Humor nicht? Ich meine, dass man da ein bisschen kürzt und nicht ständig solche Ausdrücke ausrechnet:

    fact(p)/(fact(q)*fact(p-q))
    

    => (nk)=n!k!(nk)!=n(n1)(nk+1)k!\binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n(n-1)\cdots(n-k+1)}{k!}

    Das ist wirklich Schema F. Eigentlich kann man sich die Formel auch gleich so merken, die mit den Fakultäten ist wirklich praktisch nicht zu gebrauchen. Wenn das nicht reicht, kann man noch mehr kürzen, aber das ist dann schon etwas schwieriger zu organsieren.

    PS: (nk)=(nnk)\binom{n}{k} = \binom{n}{n-k} sollte man auch wissen.



  • @Bashar
    Deine Formel kann man dann noch dazu umformeln:
    http://de.wikipedia.org/wiki/Binomialkoeffizient#Algorithmus_zur_effizienten_Berechnung

    Da werden die Zwischenergebnisse nämlich noch weniger gross.

    @SeppJ
    Was ist daran umständlich?


  • Mod

    Bashar schrieb:

    Versteh ich grade euren Humor nicht?

    Der Humor bezog sich nur auf hustbaer.

    Ich meine, dass man da ein bisschen kürzt und nicht ständig solche Ausdrücke ausrechnet:

    fact(p)/(fact(q)*fact(p-q))
    

    => (nk)=n!k!(nk)!=n(n1)(nk+1)k!\binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n(n-1)\cdots(n-k+1)}{k!}

    Ich dachte (und so würde ich es machen) du wolltest noch einen Schritt weiter, dass man nicht erst die potentiell sehr großen Zähler und Nenner berechnet, sondern mal ein ppar aus dem Nenner und dann wieder ein paar aus dem Zähler. Netterweise sind das ja ähnlich viele Einzelausdrücke oben und unten.



  • Vielen Dank an alle für den guten Input!

    SeppJ schrieb:

    Hat denn der Bot nicht mehr gesagt?

    Leider nicht, ich bekam nur die Antwort "Wrong Answer".

    Bashar schrieb:

    Kann es sein, dass deine Fakultäten überlaufen?

    Das stimmt wohl: Die höchste Fakultät, die das Programm errechnen muss, ist 1000! (da m <= 1000). Dessen Wert liegt laut Wolfram Alpha bei 4.02E+2567 , was natürlich den long double sprengt. Werde die vorgeschlagene effiziente Berrechnungmethode implementieren und den Code nochmal submitten, sag euch dann Bescheid, ob das was bracht.

    Danke nochmals!

    **
    EDIT**

    Habe jetzt für den Binominalkoeffizienten folgende Funktion geschrieben:

    long double
     binominal(int a, int b)
     {
        float n = (float) a;
        float k = (float) b;
        long double bin = 1;
        if (k == 0)
        {
            bin = 0;
            return bin;
        }
        if (k > (n/2) )
            k = n-k;
        for(int i = 1; i <= k; i++)
        {   
            long double temp = (n-k+i)/(i);
            bin *= temp;
        }
        return bin;
    }
    

    und demnach Zeile 60 des ursprünglichen Codes wie folgt geändert:

    temp=(binominal(p, q)*binominal((m-p), (n-q)))/(binominal(m, n));
    

    Der Bot gibt leider immer noch "Wrong Answer" aus. Scheint also nicht am Binominalkoeffizienten liegen.


Anmelden zum Antworten