Skip to content

Instantly share code, notes, and snippets.

@olligobber
Last active July 12, 2023 13:06
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save olligobber/465bbba51c44bc6bc769b8758b0e52a2 to your computer and use it in GitHub Desktop.
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
Loaded dictionary with 82222 words
Longest match has length: 7
Looping over 1 sets of matches
Set number 1
abjurer
nowhere
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