Difference between revisions of "Haskell Quiz/Posix Pangrams/Solution Burton"
Jump to navigation
Jump to search
(sharpen cat) |
m |
||
Line 31: | Line 31: | ||
hasNew [] _ = False |
hasNew [] _ = False |
||
hasNew (x:xs) w | not $ isAlpha x = hasNew xs w |
hasNew (x:xs) w | not $ isAlpha x = hasNew xs w |
||
− | | |
+ | | x `notElem` w = True |
| otherwise = hasNew xs w |
| otherwise = hasNew xs w |
||
Line 37: | Line 37: | ||
hasDupes _ [] = False |
hasDupes _ [] = False |
||
hasDupes [] _ = False |
hasDupes [] _ = False |
||
− | hasDupes (x:xs) w = |
+ | hasDupes (x:xs) w = x `elem` w || hasDupes xs w |
numDupes :: String -> Int |
numDupes :: String -> Int |
||
numDupes s = numDupes' s 0 |
numDupes s = numDupes' s 0 |
||
where numDupes' [] c = c |
where numDupes' [] c = c |
||
− | numDupes' (x:xs) c = if |
+ | numDupes' (x:xs) c = if x `elem` xs then numDupes' xs (c+1) else numDupes' xs c |
isPangram :: String -> Bool |
isPangram :: String -> Bool |
||
Line 54: | Line 54: | ||
++ ", repeated chars: " ++ (show (numDupes s)) |
++ ", repeated chars: " ++ (show (numDupes s)) |
||
− | main = do |
+ | main = do cs <- readFile "posix-utils.txt" |
− | + | pg <- makePangram (lines cs) "" [] 0 |
|
− | pg <- (makePangram (lines cs) "" [] 0) |
||
putStrLn ("pangram: " ++ pg) |
putStrLn ("pangram: " ++ pg) |
||
putStrLn (stats pg) |
putStrLn (stats pg) |
Latest revision as of 11:22, 14 December 2009
This is a naive solution - it works by taking the sortest subsequence of the original list which is a pangram then trying to replace words in it with shorter, unused ones. The pangrams it produces aren't very short.
module Main
where
import IO
import Char
import List
{--
*Main> main
pangram: admin bc ex fg lp sh tr zcat yacc write who vi uux unlink uniq join
wordcount: 16, total chars: 52, repeated chars: 41
--}
makePangram :: [String] -> String -> [String] -> Int -> IO String
makePangram [] pg rejects pass | isPangram pg = return pg
| pass == 0 = makePangram rejects pg [] 1
| otherwise = return ("ran out of words! " ++ pg)
makePangram (w:ws) pg rejects pass | isPangram pg = return pg
| hasNew w (nub pg) = handleDupes
| otherwise = makePangram ws pg rejects pass
where handleDupes | not (hasDupes (filter isAlpha w) (nub pg))
|| pass == 1 = makePangram ws (pg ++ " " ++ w) rejects pass
| otherwise = makePangram ws pg (w:rejects) pass
hasNew :: String -> String -> Bool
hasNew x [] = True
hasNew [] _ = False
hasNew (x:xs) w | not $ isAlpha x = hasNew xs w
| x `notElem` w = True
| otherwise = hasNew xs w
hasDupes :: String -> String -> Bool
hasDupes _ [] = False
hasDupes [] _ = False
hasDupes (x:xs) w = x `elem` w || hasDupes xs w
numDupes :: String -> Int
numDupes s = numDupes' s 0
where numDupes' [] c = c
numDupes' (x:xs) c = if x `elem` xs then numDupes' xs (c+1) else numDupes' xs c
isPangram :: String -> Bool
isPangram = (==26) . length . nub . filter isAlpha
stats :: String -> String
stats s = "wordcount: "
++ (show (length (words s)))
++ ", total chars: "
++ (show (length (filter isAlpha s)))
++ ", repeated chars: " ++ (show (numDupes s))
main = do cs <- readFile "posix-utils.txt"
pg <- makePangram (lines cs) "" [] 0
putStrLn ("pangram: " ++ pg)
putStrLn (stats pg)