[Tävling] Programmerare

Våran examinator i en funktionell programmerinskurs (haskell) visade en lösning på 3 rader (inklusive funktionsdeklarationen).

Har du källkoden? Skulle vara väldigt interesant att se.

Jo det har jag.
Jag skickar den som PM tills det är säkert att helgens tävling inte blir i towers of hanoi.

Där ser man, ja. Jag kom tydligen ihåg rätt.

Kan du skicka den till mig med?

Men vad fånigt. Skriv den här. Det lär knappast ha varit ett fulhack, och inte särskilt svårt att komma på. F ö spelar det väl ingen roll om folk får den via PM eller läser på forumet?

Här kommer den.

{-
hanoi (n, from, to, help) flyttar ett torn med höjden n från pinnen
med nummer  from  till pinnen med nummer  to  genom att ta hjälp av
pinnen med nummer  help.
-}

hanoi :: (Int, Int, Int, Int) -> [(Int, Int)]
hanoi (0,_,_,_) = []
hanoi (n, from, to, help) = hanoi (n-1, from, help, to) ++ [(from, to)] ++ hanoi (n-1, help, to, from)

{-
Main> hanoi (3,1,2,3)
[(1,2), (1,3), (2,3), (1,2), (3,1), (3,2), (1,2)] :: [(Int,Int)]
Main> hanoi (4,1,2,3)
[(1,3), (1,2), (3,2), (1,3), (2,1), (2,3), (1,3), (1,2), (3,2), (3,1),
(2,1), (3,2), (1,3), (1,2), (3,2)] :: [(Int,Int)]
Main>
-}

Är du insatt i haskell, funktionell programmering och/eller rekursion då?

Har tråkigt på jobbet så jag kan lika gärna roa mig med att förklara koden.

hanoi :: (Int, Int, Int, Int) -> [(Int, Int)]
hanoi (0,_,_,_) = []
hanoi (n, from, to, help) = hanoi (n-1, from, help, to) ++ [(from, to)] ++ hanoi (n-1, help, to, from)

Den första raden deklarerar att funktionen hanoi har fyra parametrar av typen int och returnerar en lista med tupler av typen int. Den första parametern anger antalet skivor och de tre övriga kan ses som index för pinnarna. Skivorna ska flyttas från den första (from) till den andra (to) med hjälp av den tredje (help).

Den andra raden beskriver basfallet, dvs om första parametern är 0 (alltså då antalet skivor som skal flyttas är noll) så returneras en tom lista oberoende av vad resten av parametrarna är.

Den tredje raden är det allmänna fallet (med n skivor som ska flyttas) och gör en konkatenering av hanoi (n-1, from, help, to), [(from, to)] och hanoi (n-1, help, to, from). Detta är i princip ett steg i den rekursiva algoritmen. För att flytta n skivor från "from" till "to" flyttar man först n-1 skivor från "from" till "help", sedan flyttar man den n:te skivan från "from" till "to" och sedan n-1 skivor från "help" till "to".

Utskriften är sedan en lista av tupler som berättar från vilken pinne man ska flytta och vart.

Kan bara påpeka att om man vill fula sig lite kan man lägga in basfallet i den sista raden (tex med en case) i hanoi-programmet, så man får ett program på 2 rader istället, fast med en något längre andra rad..

Nu när du säger det så.

hanoi :: (Int, Int, Int, Int) -> [(Int, Int)]
hanoi (n, from, to, help) = if n == 0 then [] else hanoi (n-1, from, help, to) ++ [(from, to)] ++ hanoi (n-1, help, to, from)

Tufft

Jag kom just på veckasproblem Det kommer inte bli sådär en såndär tväroptimerings uppgift utan snarare att hitta på en smart lösning som genererar ett bra resultat. Förmodligen kommer det mer information imorgon och jag kommer skriva ett litet framework för C/C++ med testdata. Sedan kan ni andra skriva liknande för andra språk. Denna gång kan ALLA språk vara med typ. Ny tråd kommer startas när uppgiften är klar

Skulle vara trevligt om uppgiften kunde släppas innan 12.00

Innan 12:00 imorgon? Kanske.. kan bli lite jobbigt. Får se när jag vaknar. Måste rita lite skisser och sånt så folk vet vad det handlar om. Plus att jag skall sova nu

låter toppen, hoppas jag inte tänker cp den här gången

Kul.. Hoppas på en tradition här.

forka gärna tråden/ämnet.. annars blir det så rörigt

kl 11:00 kommer ny trådskapas med problemet skrivet.

Vars är den då... ???

jaja.. var 10 minuter sen