So... Let's start with the game of 31. Just call the method `finishGame` with the input string. It runs quite fast.
import List
-- Get the score from a list that is the game
scoreForGame :: (Integral a) => [a] -> a
scoreForGame x = foldl (+) 0 x
-- Change an int into a list
gameFromInt :: (Integral a) => a -> [a]
gameFromInt 0 = []
gameFromInt x = (x `mod` 10) : gameFromInt (x `div` 10)
-- Obtain the player for a game
data Player = A | B deriving (Show)
playerFromGame :: (Integral a) => [a] -> Player
playerFromGame x = if (even $ length x) then B else A
otherPlayer :: Player -> Player
otherPlayer B = A
otherPlayer A = B
-- Score a single move
scoreMove :: (Integral a) => a -> [a] -> a -> a
scoreMove score deck play
| score + play > 31 = -1
| otherwise = if (elem 1 $ map (scoreMove (score+play) deckMinusPlay) (nub deckMinusPlay)) then -1 else 1
where deckMinusPlay = delete play deck
-- Generate deck
deck :: (Integral a) => [a]
deck = [1..6] ++ [1..6] ++ [1..6] ++ [1..6]
-- Finish the game!
-- Takes the game and writes out the winner!
finishGame :: (Integral a) => a -> Player
finishGame a = if (r > 0) then p else otherPlayer p
where
d = deck \\ sort g
g = gameFromInt a
s = scoreForGame g
p = playerFromGame g
r = if (elem 1 $ map (scoreMove s d) (nub d) ) then -1 else 1
Ok. That actually wasn't that bad. And it worked. Some people might complain that scoreMove returns 1 if the current player wins else -1 -- and keeps flipping the numbers between invocations. Note that I check to see if the element is 1 rather than the more intuitive maximum as this allows Haskell to do lazy evaluation (on the first 1 found within the map over elements in deck stop processing since the player won!).
The \\ operator was a challenge to find. It's great! In `List', it subtracts the elements between lists. Eg, [1,2,3,4,5] \\ [2,3] = [1,4,5].
On to problem 2. Factoring large numbers. Actually, using Haskell is probably cheating as you need to maintain a list of prime numbers to at least finish in 30 seconds (Haskell cached it for me)... The code is quite simple:
import Control.Parallel
-- Generate an infinite list of primes?!
divides :: (Integral a) => a -> [a] -> Bool
divides _ [] = False
divides n (x:xs)
| x*x <= n = (n `mod` x == 0) || (divides n xs)
| otherwise = False
firstPrime' :: (Integral a) => [a] -> a -> a
firstPrime' (p:primes) value
| (value `mod` p == 0) = p
| p*p > value = value
| otherwise = firstPrime' primes value
firstPrime :: (Integral a) => a->a
firstPrime = firstPrime' primes
nextPrimes :: (Integral a) => a -> [a] -> [a]
nextPrimes trial primes
| (divides trial primes) = nextPrimes (trial+2) primes
| otherwise = trial:(nextPrimes (trial+2) (primes ++ [trial]))
primes :: (Integral a) => [a]
primes = 2:3:(nextPrimes 5 [3])
-- Return all the factors of a!
factor :: (Integral a) => a -> [a]
factor 1 = []
factor a = p:(factor $ a `div` p)
where p = firstPrime a
main :: IO ()
main = do
print $ factor 90
print $ factor 1234567891
print $ factor 18991325453139
print $ factor 18991325453143
print $ factor 18991325453141
print $ factor 12745267386521023
One comment I should make, lazy evaluation was essential! Also, I am aware that (primes ++ [trial]) will do a complete list traversal of primes to append a single element. Without that, the recursion was destroying the performance on the divides and firstPrime'. In total, it's about 19 seconds to run. Slower when more CPU is used...
Next off! Computing the fibonacci sequence. Once it hit me that I should try to avoid recursion (it's so natural) then I got this very nice and very fast solution:
import Control.Parallel
fib :: (Integral n) => n -> n
fib 1 = 1
fib 2 = 1
fib x = (fib $ x-1) + (fib $ x-2)
fibList' :: Integer -> Integer -> [Integer]
fibList' m1 m2 = m2:(fibList' (m2+m1) m1)
fibList :: [Integer]
fibList = (fibList' 1 1)
fib'' :: [Integer] -> Integer -> Integer
fib'' (x:xs) n
| n <= 1 = x
| otherwise = fib'' xs (n-1)
fib' :: Integer -> Integer
fib' = fib'' fibList
main :: IO ()
main = do
print $ fib' 100
print $ fib' 997
print $ fib' 1000
print $ fib' 1009
print $ fib' 4500
I think for this 3rd problem, the challenge was to work with very large numbers efficiently. Which Haskell does automagically.
Why infinite lists? lazy evaluation is the answer! I find it makes the algorithm cleaner even though a few things had to be shuffled around. I did have fun typing fibList and seeing all the numbers in the fibonacci sequence appear. And hopefully, written in this way it can cache intermediate results (but it runs so fast I don't think it even matters)!
Done a few programming challenges for the day!
No comments:
Post a Comment