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

Har kikket litt på Project Euler, god måte å få litt hjernetrim på. Særlig om en ikke jobber med avanserte algoritmer til daglig. Et eksempel på hvilke oppgaver du kan møte på er problem 4:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Da jeg ikke er smart nok til å skrive superintrikate algoritmer i assembly/perl/f# osv så blir det god gammeldags "brute forcing" i C#. Koden er ikke utpreget elegangt, eneste fancy er at den benytter seg av Extension methods for å utvide funksjonaliteten til string.

Vurderer å løse denne pånytt med Linq, bare for å teste hvordan det blir. Sånn som det er nå, føles det ikke som sexy kode.

public class Problem4
{
    int highest = 0;

    public int Calculate()
    {
        for (int i = 999; i > 0 ; i--)
        {
            for (int j = 999; j > 0; j--)
            {
                int sum = i * j;
                if (sum > highest)
                {
                    if (IsPalindrome(sum))
                        highest = sum;
                }
                else
                    break;
            }
        }
        return highest;
    }

    private bool IsPalindrome(int number)
    {
        string numb = number.ToString();

        if (numb == numb.Reverse())
            return true;
        
        return false;
    }
}


public static class Extensions
{
    public static string Reverse(this string s)
    {
        char[] ch = s.ToCharArray();
        Array.Reverse(ch);
        return new String(ch);
        
    }
}

Første problemet i Project Euler. Ble egentlig bare lagt inn her for å teste ut om syntaxhighlighter fungerte som det skulle.

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

public int Calculate(int num)
{
    for (int i = 1; i < num; i++)
    {
        if (i % 3 == 0 || i % 5 == 0)
            sum += i;
    }

    return sum;
}

myWallet.NewRecipt =
     Recipt.
     Description("Mat til grilling").
     From("Meny Oslo City").
     Date("7/8/2008").
     Sum(265.59M);


 myWallet.NewRecipt =
     Recipt.
     Description("Hylle til boden").
     Date("31/31/2008").
     From("Ikea").
     Sum(159M);

 myWallet.NewRecipt =
     Recipt.
     Description("Hageslange").
     Sum(158M).
     From("Ikea").
     Date("2/7/2008");