Tävlingsprogrammering/Introduktion/Lösningar i Haskell

Talföljdsproblemet

Den lista som vi är intresserad av, numberSequence definieras av sig själv och en lista av ökningar.

Exempel:

En lista på alla ökningar kan vi generera med notationen, [2, 3 ..].

numSeq = 1 3 6 10 15 21

ökningar = 2 3 4 5 6 7

Vi ser hur varje kommande tal i numSeq definieras av det föregående talet plus en ökning. Ökningens ökning är linjär alltså kan alla dessa skrivas som en generell lista [b-a, c-b ..]

prob1 :: Int -> Int -> Int -> [Int]
prob1 a b c = take 10 numberSequence
  where numberSequence = a:zipWith (+) numberSequence [b-a, c-b ..]

Klockproblemet

På en minut ökar vinkeln för minutvisaren med 360/60. Med samma resonemang ökar också vinkeln för timvisaren med 360/(12*60) för samma minut.

prob2 :: Int -> String
prob2 a = printf "%d:%02d" (totalMinutes `div` 60) (totalMinutes `mod` 60)
  where totalMinutes = head [x | x <- [0..719], (x*60 - x*5) `mod` 3600 == a]

Plankproblemet

Här har jag bifogat två lösningar. Andra lösningen är segare, men enklare; klarar det övre gränsfallet på under 1 sekund. Första lösningen utnyttjar några egenskaper hos Haskells listor och är en memoiserad version av den andra. Anledningen till att vi skriver ut funktionsvärdet för 1, 2 och 3 är för att inte försöka nå negativa index. Det finns andra sätt att lösa detta på, men det här ansåg jag vara det lättaste.

prob3 :: Int -> Integer
prob3 = (map prob3' [0..] !!)
  where prob3' 0 = 1
        prob3' 1 = 1
        prob3' 2 = 2
        prob3' 3 = 4
        prob3' n = prob3 (n-3) + prob3 (n-2) + prob3 (n-1)

prob3_slow :: Int -> Integer
prob3_slow x
  | x < 0 = 0
  | x == 0 = 1
  | otherwise = prob3_slow (x-3) + prob3_slow (x-2) + prob3_slow (x-1)

En möjlig linjär lösning är att inse att man bara behöver memorera de tre senaste värdena och addera dessa för att få nästa värde i serien. Talen 1,0,0 avser lösningarna för plankor av längderna 0, -1, -2.

pl :: Int -> Integer
pl  n = pl2 [1,0,0] n
pl2 :: [Integer] -> Int -> Integer
pl2 (i:is) 0= i
pl2 (i:j:k:ks) n = pl2 [i+j+k,i,j] (n-1)