Archive for April, 2013

Programming Praxis – First Unrepeated Character In A String

April 30, 2013

In today’s Programming Praxis exercise, our goal is to find the find the first unrepeated character in a string, along with its index. Let’s get started, shall we?

import Data.Maybe
import Data.List

We traverse the list from right to left, keeping a list of characters we’ve already encountered and a list of possible options. When we check a character, we first check if it’s in the list of duplicate characters. If not, we then check the list of options. If the letter in question is there already, we remove it from the list of options and add it to the list of duplicates. Otherwise, we add the current character to the list of options. At the end, we return the first unique element (if any).

unrepeated :: String -> Maybe (Integer, Char)
unrepeated = listToMaybe . snd . foldr f ([], []) . zip [0..] where
    f (i,c) (ds,us) = if elem c ds then (ds, us) else
        maybe (ds, (i,c):us) (\(fi,fc) -> (fc:ds, delete (fi,fc) us)) $
        find ((== c) . snd) us

Some tests to see if everything is working properly:

main :: IO ()
main = do print $ unrepeated "aaabc"       == Just (3, 'b')
          print $ unrepeated "aaabbbcddd"  == Just (6, 'c')
          print $ unrepeated "aaaebbbcddd" == Just (3, 'e')
          print $ unrepeated "aabbcc"      == Nothing
          print $ unrepeated "aba"         == Just (1, 'b')

Programming Praxis – Correct Horse Battery Staple

April 23, 2013

In today’s Programming Praxis exercise, our goal is to generate xkcd-style passphrases consisting of four words. Let’s get started, shall we?

import Data.Char
import System.Random.Shuffle

First, we define our criteria for acceptable words, in this case lowercase words between 5 and 9 letters.

valid :: String -> Bool
valid s = length s > 4 && length s < 10 && all isLower s

Generating a passphrase is then a simple matter of loading a dictionary, filtering the valid words, shuffling them and printing the first four chosen words.

main :: IO ()
main = putStrLn . unwords . take 4 =<<
       shuffleM . filter valid . lines =<<
       readFile "en_US.dic"

Programming Praxis – Cyclic Equality

April 9, 2013

In today’s Programming Praxis exercise, our goal is to determine if one list is cyclically equal to another. Let’s get started, shall we?

import Data.List

Rather than the provided solution which involves keep track of a bunch of pointers, we use a simple fact of cyclical lists: repeating either list twice produces a list that contains the other one if they are indeed cyclically equal. In order to prevent false positives, we also have to check whether the lengths are equal.

cyclic :: Eq a => [a] -> [a] -> Bool
cyclic xs ys = length xs == length ys && isInfixOf xs (ys ++ ys)

Some tests to see if everything is working properly:

main :: IO ()
main = do print $ cyclic [1,2,3,4,5] [3,4,5,1,2]
          print $ cyclic [1,1,2,2] [2,1,1,2]
          print $ cyclic [1,1,1,1] [1,1,1,1]
          print . not $ cyclic [1,2,3,4] [1,2,3,5]          
          print . not $ cyclic [1,1,1] [1,1,1,1]