I serien av hvordan jeg har løst Project Euler problemer kommer problem 3. Til nå har mine løsninger vært relativt naiv brute force framfor eleganse.

Problemet 2 var å finne summen av alle partall i en fibbonaccirekke.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Fordelen med å brute force, er at en får muligheten til å se hvordan VANVITTIG smarte mennesker har løst problemet du nettopp jobbet gjennom. For eksempel ville jeg aldri oppdaget at fibbonaccirekker har et mønser som ser slik ut:

O, O, P, O, O, P...

Med andre ord, i stedet for å lagre alle tallene for så sjekke om de er partall som jeg gjorde i første forsøk, så kan en bare holde tellingen på hvor en er i rekken og plukke ut hvert tredje tall.

Min første naive løsning

public class Problem2
{
    int sum = 0;
    List<int> fibbseq;

    public int fib(int first, int second)
    {
        fibbseq = new List<int>();

        fibbseq.Add(first);
        fibbseq.Add(second);
        int counter = 1;

        while (fibbseq.Last() <= 4000000)
        {
            fibbseq.Add(fibbseq.ElementAt(counter) + fibbseq.ElementAt(counter-1));
            counter++;
        }

        foreach (int i in fibbseq)
        {
            if (i % 2 == 0)
                sum += i;
        }

        return sum;
    }
}

Hadde egentlig tenkt til å løse problemet rekursivt med memoization, men kom frem til at det ville være raskere å bruke en liste slik at jeg raskt kunne løpe over den etterpå for å hente ut partallene. Ja, i perspektiv av etterpå ser jeg at det var mange bedre måter å gjøre det på.

Refaktorert løsning

public class Problem2Alt
{
    int sum = 2;

    public int fib(int first, int second)
    {
        int temp;
        int counter = 0;

        while (second <= 4000000)
        {
            temp = second;
            second += first;
            first = temp;
            counter++;

            if (counter % 3 == 0)
                sum += second;
        }
        return sum;
    }
}

Kort fortalt har jeg droppet listen, gått tilbake til "klassiske fibbonacci swap"* og hver gang jeg er på en plass det er partall legges det til den totale summen.

Utregningen tar nå 0.0002638 sekunder, i motsettning til vanvittige 0.0132318 sekunder (~13ms) det tok på den orginale brute forcingen. Dette på en 2.33GHz quad core Xeon cpu med 4GB minne. Skal jeg være ærlig så er begge helt akseptabel, i den store sammenheng, men det er morsomt å se at en kan forbedre hastigheten bare fordi en kan.

"We do what we must because we can." - John Coulton

* Jeg har hovedsaklig sett tre måter å løse fibbonacci på:

• Rekursivt
• Swap med a, b, tmp
• Rekursivt med memoization