The Functional Student: A Game of Six Integers

When I saw Richard Harris's 'Model Student - A Game Of Six Integers' in Overload 95 [Harris] I thought to myself that this was just crying out for a quick piece of functional programming and, as luck would have it, I had just recently secreted an installation of F# [Microsoft] on my PC between Visio and Powerpoint and was both researching the language and refreshing my mind as to that programming approach.

My first thought for the implementation was to attempt the solution as a logical statement, in the prolog sense, but after reflection I decided not to proceed in that direction because I wanted to be able to show close solutions as well as exact solutions, and I didn't feel I had the time to work out how to implement that in this new-to-me language, F#. Next I thought about a non-binary tree walk, where each of the six possible values for the first number occupied the first layer, then the four operators were four branches from each node, then the five possible numbers in the next layer, then the four operators, etc., etc. This, however, seemed far too messy and, consequently, I realised that I was still thinking about this in terms of the data instead of in terms of the solution process.

Thus the code in Listing 1 (below) was born. The problem has, essentially, two sets of variables; six integers intN; and five operators opN, where each of the five operators can take one of four values, '+', '-', '*' or '/'. I started with the statement of the problem, ie (((((int1 op1 int2) op2 int3) op3 int4) op4 int5) op5 int6)-desiredResult=0, and rearranged it into, more or less, what you see encoded in the countdown function. This function is slightly more complex than above because it maintains a text string describing the path taken simultaneously with the actual calculation.

    open System;;  
    (* modified from stackoverflow *)  
    let calcPermutations list =  
     let rec permutations list taken = [  
     if Set.count taken = List.length list then yield [] else  
      for l in list do  
       if not (taken.Contains l) then  
        for perm in permutations list (Set.add l taken)  do  
         yield l::perm ]  
     permutations list Set.empty;;  
    let rec op (x:(string * int) list) (y:(string*int)) =  
     match (x,y) with  
     | ((hd1,hd2)::tl,(y1,y2)) ->  
       [ (String.Format("({0}+{1}={2})",hd1,y2,hd2+y2),hd2+y2);  
         (String.Format("({0}-{1}={2})",hd1,y2,hd2-y2),hd2-y2);  
(String.Format("({0}*{1}={2})",hd1,y2,hd2*y2),hd2*y2);  
         (if hd2%y2=0 then  
           (String.Format("({0}/{1}={2})",hd1,y2,hd2/y2),hd2/y2)  
          else  
           ("non-integer",0))] @ op tl y  
     | ([],y) -> [];;  
 
    let countdown a b c d e f =  
     calcPermutations [a;b;c;d;e;f] |> List.map  
     (fun x ->  
       match x with  
        | [i1;i2;i3;i4;i5;i6] ->  
         op (  
          op (  
           op (  
            op (  
             op  
              [(String.Format("{0}",i1),i1)]  
              (String.Format("{0}",i2),i2))  
             (String.Format("{0}",i3),i3))  
            (String.Format("{0}",i4),i4))  
           (String.Format("{0}",i5),i5))  
          (String.Format("{0}",i6),i6)  
        | _ -> [("end",0)]);;  
    (* dummy pattern to quiet the compiler *)  
 
    let desiredResult = 195;;  
    let range=5;;  
 
    let doIt i1 i2 i3 i4 i5 i6 =  
     List.map (List.filter (fun ((x:string),(y:int)) ->  
     not( x.Contains("non-integer"))  
      && abs (y-desiredResult)<range))  
      (countdown i1 i2 i3 i4 i5 i6);;  
 
    doIt 1 2 3 4 5 75;;

The core function in this programme is the op function. This takes two parameters; the first is the running total and the second is the next integer to be considered. That is, after the tuples have been 'opened up', hd1 contains the string showing the path taken to reach the running total, which is itself contained within hd2. y2 is the next integer in the sequence to be processed. Each of the four possible operators is applied and this leads to four outputs for each input, all returned in a single list. This list shows all the possible operator combinations for a given ordered sequence of integers. For example, op [1] 2 returns [ 1+2; 1-2; 1*2; 1/2 ] except that 1/2 is discarded because it is not integral. Note that I have considered negative numbers as allowable but, if desired, they could be excluded easily using the same mechanism as after the division.

To utilise the op function, I needed a function to calculate the permutations of a sequence of numbers. I found something on stackoverflow [StackOverflow] which I could modify to do exactly what I wanted. The calcPermutations function determines all the permutations of a list of integers and returns a list of lists of the possibilities, eg calcPermutations [1;2] returns [ [1;2] ; [2;1] ]. This list of lists is then fed into a lambda function whose purpose is to process each of the sub-lists in turn, naming the individual components (the permuted integers) of each sub-list so that they can be used in the op function. At which point it becomes clear that Bob is, as they say, your mother's brother. All that remained now is to filter the resulting list of lists into those lists that satisfy the matching requirement and discard the rest.

Easy! At least, looking at it now, that is how it seems, but believe me, when you're buried beneath tons of virtual paper it quickly becomes a tangled mess of mind-melting code. Still, I managed to push the paper (to one side), dedicated a couple of hours of thinking time and lo! the result.

So, to run it the parameters to countdown are the six integers and the sought result is, unsurprisingly, desiredResult.

Note that I have not proven this works, only shown that it appears to work for the example case, as my day is filled with all those allegedly important tasks that I do in order to keep my team writing code.

Back to the future

Climbing out of my DeLorean [DeLorean], I can tell you that this programme will be extended in a number of interesting ways, not least being a trivial enhancement to use an increased set of operators. All that is required is an additional line for each new operator in the op function. For example, should we decide to consider 'remainder' as a valid operator in this context then we could extend the result list in op to include the tuple (String.Format("{0}%{1}",hd1,y2),hd2%y2). Similarly, I have forseen a change to the code such that it accepts an arbitrary number of integers. As the code stands, it is hard-coded to accept six integers. Also, I have discerned that the programme will be extended to accept data types other than integers as parameters, for example strings, which could be combined using string-related operators. Not wanting to spoil the surprise, however, I shall avoid revealing any more for the present.

References

[DeLorean] http://www.delorean.com/

[Harris] 'The Model Student: A Game Of Six Integers (Part 1)', Overload 95, http://accu.org/index.php/journals/1607

[Microsoft] http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/

[Stackoverflow] http://stackoverflow.com/questions/286427/calculating-permutations-in-f