Last active
July 12, 2023 13:06
-
-
Save olligobber/465bbba51c44bc6bc769b8758b0e52a2 to your computer and use it in GitHub Desktop.
Find the longest set of words that are rotation ciphered versions of each other
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Loaded dictionary with 82222 words | |
Longest match has length: 7 | |
Looping over 1 sets of matches | |
Set number 1 | |
abjurer | |
nowhere |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import Data.List (sort) | |
import Data.Foldable (traverse_) | |
-- Locations of word lists to use | |
wordlists :: [String] | |
wordlists = | |
[ "/usr/share/dict/american-english" | |
, "/usr/share/dict/british-english" | |
] | |
isLower :: Char -> Bool | |
isLower c = c >= 'a' && c <= 'z' | |
-- Take the contents of some files and make a list of words | |
normaliseDictionary :: [String] -> [String] | |
normaliseDictionary files = | |
nub . sort . filter (all isLower) $ files >>= lines | |
-- Get all unique entries from a sorted list | |
nub :: Eq x => [x] -> [x] | |
nub [] = [] | |
nub [x] = [x] | |
nub (x:y:xs) | x == y = nub (y : xs) | |
nub (x:xs) = x : nub xs | |
-- Get all duplicated entries from a sorted list | |
dups :: Eq x => [x] -> [x] | |
dups [] = [] | |
dups [_] = [] | |
dups (x:y:xs) | x == y = x : dups (dropWhile (== x) xs) | |
dups (_:xs) = dups xs | |
-- Put a word in standard form | |
toStandard :: String -> [Int] | |
toStandard word@(h:_) = fmap (\x -> (fromEnum x - fromEnum h) `mod` 26) word | |
main :: IO () | |
main = do | |
allFiles <- traverse readFile wordlists | |
let dict = normaliseDictionary allFiles | |
putStrLn $ "Loaded dictionary with " <> show (length dict) <> " words" | |
let longestMatch = maximum $ fmap length $ dups $ sort $ toStandard <$> dict | |
putStrLn $ "Longest match has length: " <> show longestMatch | |
let matches = dups $ sort $ toStandard <$> filter ((== longestMatch) . length) dict | |
putStrLn $ "Looping over " <> show (length matches) <> " sets of matches" | |
flip traverse_ (zip [1..] matches) $ \(i, match) -> do | |
putStrLn $ "\tSet number " <> show i | |
let matchedWords = filter ((== match) . toStandard) dict | |
flip traverse_ matchedWords (putStrLn . ("\t\t" <>)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment