Monday, 22 June 2015

Task Number Four Concluded

Yes I did do something wrong.  The base case of the recursion is the list of permutations of the empty list, which is not empty, because there is a permutation, that is to say the empty list itself.  So what I should have done is this:-

permutations :: (Eq a) => [a] -> [[a]]
permutations [] = [[]]
permutations xs = [ h:t | h <- xs, t <- permutations (xs `except` h) ]

*Main> permutations "HORSE"
*Main> length (permutations "HORSE")
*Main> 5 * 4 * 3 * 2 * 1

That's more like it.

Slipped the factorial in there just for fun: 120 permutations.

Now given a list of integers I want the value of the concatenation of their string representations: build this up...

*Main> let ns = [50, 2, 1, 9]

Convert each integer in the list into the string form, with function show:-

*Main> map show ns

Now concatenate the whole list by folding the binary concatenation operator ++ into the list with "" as the base case:-

*Main> foldr (++) "" (map show ns)

Now read this to get the integer value:

*Main> read (foldr (++) "" (map show ns))
    No instance for (Read a0) arising from a use of `read'

Aha, need to help read by specifying the destination type:

*Main> read (foldl (++) "" (map show ns)) :: Int

So wrap this in a nice function:-

value :: [Int] -> Int
value ns = read (foldl (++) "" (map show ns)) :: Int

Right.  So I can now generate all the permutations and assign a single value to each one.  Finally I need the maximum value from the list.  Aha, there is already a function maximum that does this.

*Main> maximum (map value (permutations [50, 2, 1, 9]))

QED (Quite Easily Done)

I haven't been keeping track but that definitely was more than an hour.

On reviewing the solution posted by the original blogger I see he went down the track of comparing strings, and spotted that the problem is made hard by the fact that the numbers can be represented by strings of different lengths.

I like this Haskell solution because you read that last line of code and it pretty much tells you what it does.

No comments:

Post a Comment