Posts Tagged ‘wirth’

Programming Praxis – Stepwise Program Development: A Heuristic Algorithm

December 11, 2012

In today’s exercise, our goal is to write an algorithm that, given an alphabet and a length, generates all possible sequences that do not have two adjacent indentical subsequences. Let’s get started, shall we?

Some imports:

import Control.Monad
import Data.List

We build up the list of possible sequences from the end. Whenever we add a character we check that we do not generate a repeated subsequence. This bit could be optimised a little since checking past the first half of the list is pointless, but performance wasn’t a problem so I didn’t bother. Although not explicitly stated in the problem description, two sequences are considered identical if one can be obtained by permuting the other’s alphabet, e.g. 123 is considered the same thing as 321. Therefor we add the criterium that in the final list of permutations all unique characters must occur in ascending order.

nonAdjacent :: Ord a => [a] -> Int -> [[a]]
nonAdjacent xs = sort . filter (and . zipWith (==) xs . nub) . f where
    f 0 = [[]]
    f n = filter (\x -> not . or . tail $ zipWith isPrefixOf (inits x) (tails x)) $
          liftM2 (:) xs (f $ n - 1)

Some tests to see if everything is working properly:

main :: IO ()
main = do mapM_ putStrLn $ nonAdjacent "123" 5
          mapM_ putStrLn $ nonAdjacent "123" 12
          mapM_ putStrLn $ nonAdjacent "123" 20

Programming Praxis – Wirth Problem 15.12

December 7, 2012

In today’s Programming Praxis exercise, our goal is to generate the first 100 terms of a mathematical set defined by Niklaus Wirth. Let’s get started, shall we?

A quick import:

import Data.List.Ordered

Thanks to Haskell’s lazy evaluation, we can simply define the set recursively and we don’t have to bother with a queue of items. Initially I just wrote out the union function (which merges two ascending lists in ascending order) my self, but I then I figured that there was probably a library somewhere that had this function.  A bit of googling revealed Data.List.Ordered.

m :: [Integer]
m = 1 : union (map ((+1) . (*2)) m) (map ((+1) . (*3)) m)

All that’s left to do is to take the first 100 elements of the sequence.

main :: IO ()
main = print $ take 100 m