Monday 29 June 2015

The Fifth Problem (4)

Right, so now I can built the solution.  First get all those combinations of  the operations:

let ops = take 6561 (iterate cyclops "________")

Then map mergeops onto all of those to make a list of strings like "1_2_3+4_5_6-7_8_9" etc:

let rawStrings = map (mergeops "123456789") ops

Then use that little filter to remove the underline characters from the strings:

let neatStrings = map (filter (\c -> c /= '_')) rawStrings

Then just extract the ones where the string evaluates to 100:

let hundreds = filter (\s -> eval s == 100) neatStrings

At this point you might be thinking, blimey, Haskell is fast.  Actually of course due to the magic of lazy evaluation Haskell hasn't done anything yet.  Now we actually ask to see the results and the cogs have to turn:

*Main Data.Char> hundreds
["123-45-67+89","12-3-4+5-6+7+89",
"12+3+4+5-6-7+89","123+4-5+67-89",
"1+2+3-4+5+6+78+9","12+3-4+5+67+8+9",
"1+23-4+56+7+8+9","1+2+34-5+67-8+9",
"1+23-4+5+6+78-9","123+45-67+8-9",
"123-4-5-6-7+8-9"]

Now I see how that goes I could make a tidy logical version ("Plan to throw one away")

Looking at the solution posted by the blogger I see he has gone for a neat recursive way to deduce the answers.  Er or I mean neat in concept: I can't work out what the actual code does.  I must admit on this one it never crossed my mind not to use the brute force approach.  Logically I should now try to code up Santiago's solution in Haskell.  Hmm.

The Fifth Problem (3)

And then to evaluate the final string.  Work down the string keeping a running accumulator: each time you hit a digit, multiply your accumulator by 10 and add the value of the digit: but if you hit a plus or a minus, add or subtract the value of the remainder of the string.  So we get this:-

The main function...

val :: String -> Int
val s = valx 0 s

This works by calling its auxiliary function...

valx n [] = n
valx n (c:cs) =
    case c of
      '+' -> n + valx 0 cs
      '-' -> n - valx 0 cs
      _ -> valx ((n * 10) + (ord c - ord '0')) cs

And so...

*Main Data.Char> val "1+2+34-5+67-8+9"
-18

Wrong answer.

The reason is that doing it recursively implicitlty brackets from the end of the string, so we are working out 1+(2+(34-(5+(67-(8+9))))) but really we want to work out (((((1+2)+34)-5)+67)-8)+9

OK so I want an auxiliary function that takes an accumulator for the whole expression, and as I go along a smaller accumulator for the value of the number I'm working through.  And a number -1 or +1 for the last sign character I encountered.

At the start, the accumulators are zero and the sign is +1.

Each time I hit either a + or a - character I either add or subtract the value of my current number to or from the accumulator.  Also I set the sign for the next number, and set the little accumulator back to
zero.

When I hit a digit I use it to increase the value of the current number.

So I get this:

eval :: String -> Int
eval s = evalx 0 0 1 s

evalx :: Int -> Int -> Int -> String -> Int

evalx acc cur sgn "" = 
    acc + (sgn * cur)

evalx acc cur sgn (c:cs) =
    case c of
      '+' -> evalx (acc + (sgn * cur)) 0 1 cs
      '-' -> evalx (acc + (sgn * cur)) 0 (-1) cs
      _ -> evalx acc ((cur * 10) + (ord(c) - ord('0'))) sgn cs


*Main Data.Char> eval "1+2+34-5+67-8+9"
100

This one does work.

The Fifth Problem (2)

So now I will want to merge the list of operations into the list of numbers.  I did a merge function already recently, it went like this:-

mergeops :: String -> String -> String
mergeops ns [] = ns
mergeops [] os = os
mergeops (n:ns) (o:os) = n : o : mergeops ns os

For example two digits then plus then two digits then minus then two digits...

*Main Data.Char> mergeops "123456789" "__+__-__"
"1_2_3+4_5_6-7_8_9"

Ah yes I will want to filter out the "nothing" operation characters, say like this:-

*Main Data.Char> filter (\c -> c /= '_') it
"123+456-789"

The bit in the brackets is a lambda, the function taking c and returning a boolean true if c is not equal to the underline character.

And it is the Haskell shell's way of giving you the result of the previous expression you just evaluated.

The Fifth Problem (1)

The Fifth Problem is to write a program that will output all the possibilities of putting the operations + or - or nothing between the numbers 1, 2 ... 9 (in that order) so that the result is 100.

For example, 1+2+34-5+67-8+9 = 100

Therefore I will want to cycle through all the possibilities for the eight operations (one between each pair of the nine numbers) - - each of which is one of plus + minus - and nothing _.

The function - er - cyclops (hee hee) will take a list of operations each expressed as a character +, - or _ in a string: is the first one is _ it changes to +, if it is + it changes it to -, and if it is - then it changes it back to _ but carried the change forward by cycling the remainder of the string.

cyclops :: String -> String
cyclops [] = []
cyclops ('_':cs) = '+':cs
cyclops ('+':cs) = '-':cs

cyclops ('-':cs) = '_' : cyclops cs

So starting from eight nothings:-

*Main Data.Char> cyclops "________"
"+_______"
*Main Data.Char> cyclops it
"-_______"
*Main Data.Char> cyclops it
"_+______"

Function iterate will repeat as long as we want:-

*Main Data.Char> take 20 (iterate cyclops "________")
["________",
"+_______",
"-_______",
"_+______",
"++______",
"-+______",
"_-______",
"+-______",
"--______",
"__+_____",
"+_+_____",
"-_+_____",
"_++_____",
"+++_____",
"-++_____",
"_-+_____",
"+-+_____",
"--+_____",
"__-_____",
"+_-_____"]

Looking about right.

There will be 3 ** 8 different possibilities = 6561 altogether.

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"
["HORSE","HORES","HOSRE","HOSER","HOERS","HOESR",
"HROSE","HROES","HRSOE","HRSEO","HREOS","HRESO",
"HSORE","HSOER","HSROE","HSREO","HSEOR","HSERO",
"HEORS","HEOSR","HEROS","HERSO","HESOR","HESRO",
"OHRSE","OHRES","OHSRE","OHSER","OHERS","OHESR",
"ORHSE","ORHES","ORSHE","ORSEH","OREHS","ORESH",
"OSHRE","OSHER","OSRHE","OSREH","OSEHR","OSERH",
"OEHRS","OEHSR","OERHS","OERSH","OESHR","OESRH",
"RHOSE","RHOES","RHSOE","RHSEO","RHEOS","RHESO",
"ROHSE","ROHES","ROSHE","ROSEH","ROEHS","ROESH",
"RSHOE","RSHEO","RSOHE","RSOEH","RSEHO","RSEOH",
"REHOS","REHSO","REOHS","REOSH","RESHO","RESOH",
"SHORE","SHOER","SHROE","SHREO","SHEOR","SHERO",
"SOHRE","SOHER","SORHE","SOREH","SOEHR","SOERH",
"SRHOE","SRHEO","SROHE","SROEH","SREHO","SREOH",
"SEHOR","SEHRO","SEOHR","SEORH","SERHO","SEROH",
"EHORS","EHOSR","EHROS","EHRSO","EHSOR","EHSRO",
"EOHRS","EOHSR","EORHS","EORSH","EOSHR","EOSRH",
"ERHOS","ERHSO","EROHS","EROSH","ERSHO","ERSOH",
"ESHOR","ESHRO","ESOHR","ESORH","ESRHO","ESROH"]
*Main> length (permutations "HORSE")
120
*Main> 5 * 4 * 3 * 2 * 1
120
*Main> 

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
["50","2","1","9"]

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

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

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
50219

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]))
95021

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.

Task Number Four Continued

Well what I am feeling my way towards is a Cartesian join between the list of heads of the list ns and the permutation of the tails, where the tail is the numbers in the list except the head one.

So this is where we go for a list comprehension:-

permutations :: [Int] -> [[Int]]
permutations ns = [ h:t | h <- ns, t <- permutations (ns except h) ]

That is too honey not to be right.  There are two generators: the first one cycles through the list of elements and the second one calls the function to get the permutations of the elements of the list except the element that the first generator has just pulled out itself.  This is legitimate as the generators are evaluated left-to-right.  This works in logic so it should work in  Haskell.

However I first need that except operator:-

except :: [Int] -> Int -> [Int]
except ns x = [ n <- ns, n /= x]

*Main> [50, 2, 1, 9] `except` 2
[50,1,9]

No hang on, that would eliminate more than I want:

*Main> [3, 1 , 4, 1, 5, 9] `except` 1
[3,4,5,9]

Just one 1 should go, not all of them.   Ok let's try spelling it out:

except :: [Int] -> Int -> [Int]
except [] x = []
except (n:ns) x =
    if n == x
    then ns
    else n : (ns `except` x)

*Main> [3, 1, 4, 1, 5, 9] `except` 1
[3,4,1,5,9]
*Main> [3, 1, 4, 1, 5, 9] `except` 3
[1,4,1,5,9]
*Main> [3, 1, 4, 1, 5, 9] `except` 9
[3,1,4,1,5]
*Main> [3, 1, 4, 1, 5, 9] `except` 8
[3,1,4,1,5,9]

I'm sure there are already library functions that do all this.

That's the one.  So.  Hang on let's generalise except to take any type where you can do an equality comparison:

except :: (Eq a) => [a] -> a -> [a]
except [] x = []
except (n:ns) x =
    if n == x
    then ns
    else n : (ns `except` x)

Now my permutations function:

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

The generalised version should work on strings:-

*Main> permutations "HORSE"
[]

No hang on it's not returning anything.

*Main> permutations [3,1,4,1,5,9]
[]

Hm.  Must have done something wrong.

Task Number Four

The next problem is this.  Given a list of numbers, you can concatenate them in various orders to make a larger number.  The problem is to work out the order for a given list of numbers that will give you the largest combined number.

My first thought was that this is easy - just sort the numbers into largest first and then join them together.  This would work for say 31 41 59 - - join them in sorted order 59 41 31 and you get 594131 which is the largest possibility.

However this won't work even for the example on the page - 50, 2, 1, 9.  Put them in increasing order and you get 50921 but the largest result possible is 95021.

So is there a way to work out the largest by allowing for the fact that the numbers are different lengths?  I'm sure there is but I haven't got time to try to work that our now.  The clock is supposed to be ticking...

Therefore perhaps the way to do this is to just blindly work out the whole list of permutations of the number list and then get the maximum.

OK so if I have a list of numbers, how do I list all permutations?

Pardon me if I switch language here...

So firstly if I want all permutations I want to start with each of the numbers in turn so I want to be able to rotate my list:

rotate :: [Int] -> [Int]
rotate [] = []
rotate (x:xs) = xs ++ [x]

Now for example:-

*Main> rotate [50, 2, 1, 9]
[2,1,9,50]

So to get a list of all possible rotations of one list:-

rotations :: [Int] -> [[Int]]
rotations ns = take (length ns) (iterate rotate ns)

The function iterate produces a potentially infinite list of repeated calls of the same function: take allows us to get only as much of this infinite list as we need, which here is the number of elements
in the list so each one comes to the front once.

And for this example:-

*Main> rotations [50, 2, 1, 9]
[[50,2,1,9],[2,1,9,50],[1,9,50,2],[9,50,2,1]]

So er yes I want to rotate through the first number of the list and then combine each number with successive permutations of the remainder of the list.  Thinking recursively you see.

So perhaps I want the heads of the list and the tails of the list as separate lists:-

heads :: [Int] -> [Int]
tails :: [Int] -> [[Int]]

heads ns = ns 
tails ns = map tail (rotations ns)

*Main> heads [50, 2, 1, 9]
[50,2,1,9]
*Main> tails [50, 2, 1, 9]
[[2,1,9],[1,9,50],[9,50,2],[50,2,1]]

Tuesday 16 June 2015

All the Classics

The third warm-up test is to create the first 100 members of the Fibonacci series.

OK, so let's consider the series two elements at a time as a and b: we can initialise neatly so:

>>> a, b = 0, 1

And accumulate the series in a list called fibo which we initialise empty:

>>> fibo = []

Then loop 100 times appending each element to our list and then moving on to the next with another neat parallel assignment:

>>> for ix in range(0, 100):
...     fibo.append(a)
...     a, b = b, a+b
...

So what do we get?

>>> print fibo
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4
181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 83
2040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169,
 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 18
36311903, 2971215073L, 4807526976L, 7778742049L, 12586269025L, 20365011074L, 329
51280099L, 53316291173L, 86267571272L, 139583862445L, 225851433717L, 36543529616
2L, 591286729879L, 956722026041L, 1548008755920L, 2504730781961L, 4052739537881L
, 6557470319842L, 10610209857723L, 17167680177565L, 27777890035288L, 44945570212
853L, 72723460248141L, 117669030460994L, 190392490709135L, 308061521170129L, 498
454011879264L, 806515533049393L, 1304969544928657L, 2111485077978050L, 341645462
2906707L, 5527939700884757L, 8944394323791464L, 14472334024676221L, 234167283484
67685L, 37889062373143906L, 61305790721611591L, 99194853094755497L, 160500643816
367088L, 259695496911122585L, 420196140727489673L, 679891637638612258L, 11000877
78366101931L, 1779979416004714189L, 2880067194370816120L, 4660046610375530309L,
7540113804746346429L, 12200160415121876738L, 19740274219868223167L, 319404346349
90099905L, 51680708854858323072L, 83621143489848422977L, 135301852344706746049L,
 218922995834555169026L]

Did we get them all?

>>> print len(fibo)
100

Ah yes.

Merging Lists

The next problem is to write code that will merge two lists by creating a new list that shows alternate elements from your two source lists.

The spec doesn't say what to do if the lists are not the same length. We could imagine the case where the merged list has to show members of alternate lists and so it has to stop if either of the lists stops.

Or we could have the case of a process that is handling elements from two sources in a balanced way, so if one list comes to the end it is free to continue just with the other one.

So let's do it both ways.  Starting with three lists, two the same length and one longer:-

>>> stooges = ["Curly", "Larry", "Moe"]
>>> marxes = ["Groucho", "Harpo", "Chico"]
>>> dwarfs = ["Grumpy", "Dopey", "Happy", "Larry", "Linus", "Charlie", "Bob"]

Now for the case where the merged list stops if either list has stopped - so if we get to the end of xs or ys we return the empty list: otherwise create a new list of the first two elements of the source lists and concatenate this onto the rest of the result from the recursion:-

>>> def merge_lists_1(xs, ys):
if xs == [] or ys == []:
    return []
else:
    return [xs[0], ys[0]] + merge_lists_1(xs[1:], ys[1:])

No horses were scared in the creation of that function.  Does it work?

>>> merge_lists_1(stooges, marxes)
['Curly', 'Groucho', 'Larry', 'Harpo', 'Moe', 'Chico']

And it stops when the shorter list stops:-

>>> merge_lists_1(stooges, dwarfs)
['Curly', 'Grumpy', 'Larry', 'Dopey', 'Moe', 'Happy']

Now for the other case.  If one list comes to the end then return the other list; otherwise get two elements and join to the recursion as before:

>>> def merge_lists_2(xs, ys):
if xs == []:
    return ys
elif ys == []:
    return xs
else:
    return [xs[0], ys[0]] + merge_lists_2(xs[1:], ys[1:])

Now for lists of the same length:-

>>> merge_lists_2(stooges, marxes)
['Curly', 'Groucho', 'Larry', 'Harpo', 'Moe', 'Chico']

And if one list is longer then we finish off the longer list:-

>>> merge_lists_2(stooges, dwarfs)
['Curly', 'Grumpy', 'Larry', 'Dopey', 'Moe', 'Happy', 'Larry', 'Linus', 'Charlie', 'Bob']
>>> 

Monday 15 June 2015

It's...

The boys at Programming Throwdown have drawn attention to a post by Santiago L. Valdarrama provocatively titled Five programming problems every Software Engineer should be able to solve in less than 1 hour.

Is that one hour each or one hour altogether?  Doesn't say.  Anyway I'm curious because it's a chance for me to prove that I really am as clever as I think I am.  That's the draw of a title like that, surely? You say: I will either solve the problems, thereby proving that other software engineers who can't solve them are idiots: or else I can't solve them, proving that the guy who posted the problem is the idiot.  Either way you can't lose...

Also the Throwdown team have mentioned a substitute text shell called Babun that they reckon is worth checking out.

This Babun shell comes with Python.  I've never tried Python so this is a good excuse.  I understand it is supposed to be easy to pick up, but also people do write serious systems with it.  Python has been sitting in the background of the programming world for years patiently waiting for Perl to die, and now it finds that Ruby has appeared from nowhere and claimed its patch.

Anyway, the first task is to write code that works out the sum of a list of numbers three ways, by a for loop, by a while loop, and by recursion.

So, here goes.

Start up Python from the fancy new shell:-

{ ~ }  » python  ~
Python 2.7.8 (default, Jul 28 2014, 01:34:03)
[GCC 4.8.3] on cygwin
Type "help", "copyright", "credits" or "license" for more information.

Python 2.7 classes itself as "legacy" - the current thinking is in Python version 3.  However.

Create a list of numbers with a nice easy sum:

>>> numbers = [50,25,12,7,3,2,1]

Now to use for - well, looks like Python has several way to use a for construction. First we can for over a range of consecutive numbers. Note that in Python, lists start at element zero.  Thank you, note taken.  The range you specify starts at the first number and stops before the second number you specify.  That makes it easy: to scan over all the elements of the array we do this:

>>> sum = 0
>>> for ix in range(0, len(numbers)):
...     sum = sum + numbers[ix]
...
>>> print sum
100

Using sum to accumulate the result each time of course.

>>> is the Python shell prompt at the top level, and ... is the prompt when you are inside a multi-line construction.  Block structure is defined in the syntax by the indentation.  Bold move.

There is also a for construction that gives you the elements in a collection without your having to pick an index, so alternatively we can say this:

>>> sum = 0
>>> for n in numbers:
...     sum = sum + n
...
>>> print sum
100
>>>

To run over the list with a while construction I'll use two index variables, ix to step through and iy to be the first index I don't want to see, which will be the length of the list. I set this before I go into the loop as I don't want to have to evaluate the len() function more than once if I don't have to.

So:-

>>> sum = 0
>>> ix = 0
>>> iy = len(numbers)
>>> while ix < iy:
...     sum = sum + numbers[ix]
...     ix = ix + 1
...
>>> print sum
100
>>>

Yes, I derive an obscure comfort from naming variables after Z80 registers. It's a bit like making a drink in a favourite cup or taking notes with a favourite pen.  You just know where you are, you see.

Now, lst[0] corresponds to (CAR lst) in Lisp.  You get the first element from the list.  In addition to writing lst[ix] to pick a specific element you can get sub-lists.  For example lst[1:] returns the list of elements starting after the zero element in the list - so this corresponds to (CDR lst) in Lisp. With these two in mind we can write the recursive solution that looks just like a Lisp one:

>>> def sum_list(ns):
...     if ns == []:
...             return 0
...     else:
...             return ns[0] + sum_list(ns[1:])
...
>>> print sum_list(numbers)
100
>>>

Hey, we are Python-enabled.  Cool.  Spam.

Did that take an hour?  I don't know, I lost track of time watching Babun download.