Hello World, Euler style


torsdag 24. november 2011 Julekalender C# Clojure Common Lisp Polyglot Ruby

I den oppkommende adventskalenderen, hvor jeg hver dag frem til Jul vil introdusere deg for et nytt programmeringsspråk, har jeg valgt én bestemt oppgave for å vise frem språkene – nemlig den første og enkleste oppgaven på Project Euler.

Oppgaven lyder:

Hvis vi lister opp alle naturlige tall under 10 som er multipler av 3 eller 5 så får vi 3, 5, 6 og 9. Summen av disse er 23. Finn summen av alle multipler av 3 eller 5 under 1000.

Jeg bruker denne oppgaven som min Hello, World når jeg lærer meg nye språk. Den sørger for at jeg raskt lærer meg flere grunnleggende byggestener i språket, som hvordan man itererer, og hvordan man tar avgjørelser basert på numeriske operasjoner.

Jeg har også brukt oppgaven her på bloggen tidligere, i posten Parallellisering av en algoritme i Erlang. I dag gir jeg deg mulighet til å gjøre deg kjent med oppgaven, og viser noen implementasjoner i de språkene du normalt ser på programmeringsbloggen.

Løsning i C#

C# er språket jeg bruker til daglig, så det er et greit sted å begynne. Her følger en komplett løsning som looper gjennom alle tallene opp til 1000, sjekker om de er multipler av 3 eller 5 (ved å bruke modulo), og summerer opp tallene i sum-variabelen. Det siste som skjer er at tallet skrives ut.

10 class Program
11 {
12     static void Main()
13     {
14         int sum = 0;
15         for (int i = 0; i < 1000; i++)
16             if (i % 3 == 0 || i % 5 == 0)
17                 sum += i;
18         System.Console.WriteLine(sum);
19     }
20 }

Som sagt er det en meget enkel oppgave – så sant du kjenner til modulo da.

En alternativ måte å løse oppgaven er å bruke en funksjonell, stream-basert teknikk. I .NET vil dette si Linq. Her er en løsning i C# som bruker Range, Where og Sum:

10 using System.Linq;
11 
12 class Program
13 {
14     static void Main()
15     {
16         System.Console.WriteLine(
17             Enumerable.Range(1, 999)
18             .Where(i => i % 3 == 0 || i % 5 == 0)
19             .Sum());
20     }
21 }
22 

I julekalenderen vil du komme til å se en god mix av disse to fremgangsmåtene, og noen som er helt anderledes.

Løsning i Ruby

Ruby er det språket det er lettest for meg å hoppe inn i om jeg skal lage et kjapt lite verktøy, skal teste ut en algoritme eller noe lignende. Her følger en imperativ løsning:

1 sum = 0;
2 (1...1000).each do |i|
3   sum += i if i.modulo(3) == 0 or i.modulo(5) == 0
4 end
5 puts sum

I Ruby bruker jeg omtrent aldri vanlige for-løkker – å opprette en range, og så kjøre en kodeblokk for hvert element er mere naturlig.

En stream-basert løsning er mere elegant. Da bruker jeg select for å filtrere tallene, og reduce for å summere, slik som dette:

7 puts (1...1000).
8   select{|x| x.modulo(3) == 0 or x.modulo(5) == 0}.
9   reduce(:+)

Løsning i Clojure

Clojure er fortsatt favorittspråket mitt, så jeg må ta med noen løsninger i det også. Selv om det er helt unaturlig å bruke en løkke i Clojure så har jeg kokt sammen en slik løsning for denne ene gangens skyld:

 1 (loop [sum 0, numbers (range 1000)]
 2   (if (seq numbers)
 3     (let [i (first numbers)]
 4       (if (or (zero? (mod i 3))
 5               (zero? (mod i 5)))
 6         (recur (+ sum i) (rest numbers))
 7         (recur sum (rest numbers))))
 8     (println sum)))

Det fungerer, men jeg gremmes! I Clojure er stream-basert programmering det naturlige, og jeg kan bruke range, filter og reduce til å løse oppgaven ganske enkelt:

 1 (println
 2   (reduce +
 3           (filter #(or (zero? (mod % 3))
 4                        (zero? (mod % 5)))
 5                   (range 1000))))

Det er derimot ikke sikkert du synes det er så enkelt å lese denne koden. Trikset med å lese Clojure/Lisp-syntaks er som følger: Skann raskt med øynene fra venstre mot høyre til du kommer til uttrykkets siste del, som i dette tilfellet er (range 1000). Arbeid deg så tilbake mot høyre.

For å gjøre koden litt mere leservennlig tilbyr Clojure deg å gjøre det samme på følgende måte:

10 (->> 1000 range
11      (filter #(or (zero? (mod % 3))
12                   (zero? (mod % 5))))
13      (reduce +)
14      println)

Denne koden kan leses fra venstre mot høyre. "Ta tallet 1000, og lag en range av det. Filtrer med en anonym funksjon som sjekker om tall er delelig på 3 eller 5. Reduser med pluss (altså pluss dem sammen), og skriv til slutt ut".

Løsning i Common Lisp

Og helt på tampen tar jeg med en løsning i Common Lisp – fordi man der finner den kuleste og mest komplette varianten av en for-løkke som finnes i noe språk, nemlig loop makroen:

1 (print (loop for x below 1000
2              when (or (zerop (mod x 3))
3                       (zerop (mod x 5)))
4              sum x)

Du har nå sett oppgaven løst med fire ulike språk, og i desember vil du få se flere løsninger. Da vil jeg sansynligvis bryte oppgaven opp i flere steg eller funksjoner, slik at jeg får presentert enda flere aspekter ved språkene jeg forteller om.

Jeg håper du gleder deg like mye som meg :)


comments powered by Disqus