Secret Santa challenge in D

by Pezi 8. February 2015 00:01

I attended the first London meetup group for the D programming language last week with my friend David.  Near the end we had a chance to try and solve a cool programming problem called the secret santa challenge.

disclaimer – I am a complete D 'lol newb' so there might be nicer stuff I could do with syntax etc!  Also I have not yet fixed my syntax highlighter to include auto, mixin, assert, and others

The Challenge

The secret santa problem is deceptively simple.  You are given a list of names like so.

enum string[] names = [ 
        "Vicky Pollard", 
        "Keith Pollard", 
        "Ian Smith", 
        "Dave Pollard", 
        "Maria Osawa", 
        "Mark Kelly", 
        "John Pollard", 
        "Sarah Kelly" 
];

Each person must give and receive a present.  A person may not give to themselves, nor may they give to anyone else in their family as determined by their last names.

Clearly, this problem can easily be brute forced, but that would not be at all efficient and would not work with large sets of data.

We did not have a lot of time for this, and initially David and I designed an way to try and ensure that when sorted, family members would not appear next to each other.  This would allow us to then perform one pass over the array and assign a present to each neighbour with a special wrap-around case at the end.  To achieve this we assigned weights to the members, and where there were more than one family member, the weight would increase by some arbitrarily large amount, to split them away from the others.

This algorithm worked for the data in question (which is not the same as above, I have added some to it) but I later realised that our algorithm had 2 fatal flaws.

  1. It relies on having some families with around the same amount of members in each.  If you have one big family and several loners, it would dump most of the family members together at the end of the array
  2. There was no way to guarantee the start and end members would not be from the same family

It should be possible to still use a weighting approach if you calculated some ratios, but I thought there might be a simpler way.

A revised algorithm

After thinking about this on the train home from work a few days ago, and trying lots of different stuff in my head, I eventually realised the the real problem here is the biggest family.  If x is how big a family is, and you sort the data by x, you can guarantee that by skipping ahead max(x) positions that you will never encounter another of the same family member (unless the problem is unsolvable).

D is a multi-paradigm language and with this algorithm I have used a mainly imperative style, allowing me to make the minimum amount of passes on the data.

struct person { 
    string first; 
    string last; 
};

string distribute(const string[] names) { 
    assert(names.length%2==0); 
    int[string] familyCount; 
    person[] people;

    // create people and max family count 
    int maxFamilyMembers = 0; 
    foreach(name;names) { 
        auto split = split(name); 
        assert(split.length==2); 
        auto p = person(split[0],split[1]); 
        int count; 
        if(p.last in familyCount) count = ++familyCount[p.last]; 
        else count = familyCount[p.last] = 1; 
        if(count > maxFamilyMembers) maxFamilyMembers = count; 
        people ~= p; 
    }

    // sort by family count 
    people.sort!((p1,p2) => familyCount[p1.last] > familyCount[p2.last]);

    string result; 
    // assign presents using max count as an offset 
    for(int i=0; i<people.length; i++){ 
        auto source = people[i]; 
        auto dest = people[(i+maxFamilyMembers)%people.length]; 
        result ~= join([source.first," ",source.last," -> ",dest.first," ",dest.last,"\n"]); 
    }

    return result; 
}

int main(string[] argv) 
{ 
    auto results = distribute(names); 
    writeln(results);        
    readln(); 
    return 0; 
}

You will see in the first section I mix the splitting of strings and creating people, counting the families and remembering the biggest family in the same pass.  The data is then sorted by the family counts, and finally presents are distributed using the maxFamilyCount as an offset and modulus wrap-around logic.

Clearly, it isn’t very random in its gift giving – and your hands are quite tied on this as you must make sure opposing family members cancel each other out before you start using loners to pair with trailing family members.  However, you could quite easily random sort each family in place.  It is also possible to go in opposite direction  within the present-giving part, or even go forwards and backwards together at the same time. Whilst the pairs would be the same,  the giver/receiver would be reversed in the other direction.

Metaprogramming 1

I am mainly interested in D for its awesome metaprogramming features, and given I know a list of names at compile time I should be able to turn this into a metaprogram and have the compiler work this out instead of it happening at runtime, right?  How can I go about that?  Brace yourselves, it is quite difficult.

int main(string[] argv) 
{ 
    static results = distribute(names); 
    writeln(results);        
    readln(); 
    return 0; 
}

D has a rather nifty feature called Compile Time Function Evaluation (CTFE) which essentially lets you call any compatible function (with obvious constraints) either at runtime or compile time, and this is determined at the call site!  So here I simply change auto to static and the compiler executed the same function during compilation and inlined the result for me. Pretty cool!

Metaprogramming 2

D has a very powerful constructed called a mixin which is different from the same-named construct in other languages.  During compilation, D will interpret strings passed to a mixin, and assuming they are interpretable (the D compiler hosts a D interpreter!), the compiler will insert their definitions as if you had written them in the source code yourself.  You can think T4 code gen on acid and steroids simultaneously.  Whilst you might be thinking “strings! surely not”.  Whilst the strings are a bit, will, stringy, they lead themselves to easy and interesting manipulation techniques (as opposed to splicing quoted code expressions or similar) and they are still evaluated at compile time, so you do something wrong, you will know about it up-front.

Let’ see how we can use a mixin to generate some code.  I have decided that I would like a struct created for each person, and each struct will have a method giveTo() that will return a string with some text that shows which person they are giving to this year.  To achieve this I will modify  the distribute function to create the equivalent code strings instead:

string code; 
// assign presents using max count as an offset 
for(int i=0; i<people.length; i++){ 
    auto source = people[i]; 
    auto dest = people[(i+maxFamilyMembers)%people.length]; 
    auto myName = join([source.first,source.last]); 
    auto theirName = join([dest.first," ",dest.last]); 
    code ~= 
        "struct " ~ myName ~ 
          "{ string giveTo() { return \"This year I am giving to " ~  theirName ~ "\"; } " 
            ~ "}\n"; 
}

return code;

Now in the main program I can write

int main(string[] argv) 
{ 
    mixin(distribute(names)); 
    auto vp = VickyPollard(); 
    writeln(vp.giveTo()); 
    readln(); 
    return 0;
}

In this way I am using the CTFE to feed the mixin code-generation facility, which in turn verifies and inserts the code as if it had been written where the mixin statement is.  This means I can now access the VickyPollard struct and call her giveTo() method.  This is not dynamic – all statically checked at compile time!  Combining these CTFE and mixins can be extremely powerful for generating code.  D has another feature called mixin templates that let you define commonly used code blocks to insert into other places, which is more like the mixin from some other languages,  except this is just a scope of code that can contain almost anything at all.  (I think, I am still new to this!)

One more thing

D has single inheritance, interfaces and a really a long stream of other nice bits such as Uniform Function Call Syntax (UFCS) which is basically like automatic extension methods.  What I would like to show in this post however is a feature called alias this.  You can write a bunch of these in your classes / structs, the effect it has is that the compiler can then treat your class as if it was the same type of member.  This allows almost multiple inheritance but is also very useful when combined with the metaprogramming features (although perhaps this will not be apparent from this silly example)

Lets say I would like each of my new structs to also be a person.  I could use inheritance this for but lets not do that – instead I will create a static immutable person object inside each one than then alias this it.  I have changed the string-code to output the equivalent of the following

struct VickyPollard { 
    private static immutable me = person("Vicky","Pollard"); 
    string giveTo() {return "This year I am giving to Mark Kelly";} 
    alias me this; 
}

and now I can fire up any of my mixin generated types and pass them anywhere that accepts person even though they are not a person at all.

void printPerson(person p) { 
    writeln("this is person ", p.first," ", p.last); 
}

int main(string[] argv) 
{ 
    mixin(distribute(names)); 
    auto vp = VickyPollard(); 
    printPerson(vp); 
    writeln(vp.giveTo()); 
    readln(); 
    return 0; 
}

Pretty cool!  This post just explored a couple of the features in D I have played around with so far, but I am working on a roguelike game - the traditional thing I do when learning new languages - so I may write about other interesting language features as I make use of them. 

Tags:

D

Enigma Machine – Type Provider Edition

by Pezi 23. January 2015 07:28

Following up from @isaac_abraham’s awesome F# Enigma machine emulator, I decided it would be 10x cooler if it was in a type provider, because let’s face it, everything is 10x cooler once it’s in a type provider.

Here a some pictures of it in action!

enigma1 enigma2

As you can see, it uses an extensive property system that presents a menu along with the various controls to setup your enigma machine, and then finally to translate some text.  This TP is written with my InteractiveProvider as per usual.  On my first attempt at this during my lunch break today, I did succeed but I was growing increasingly frustrated with the somewhat contrived mechanism with which to process responses from properties, the text to display in intellisense, and the properties to show.

 

The Old System

The InteractiveProvider (henceforth known as IP) presents a very flexible yet slightly complicated interface with which to generate types.  Essentially, you implement IInteractiveState on some state object of your design, and IInteractiveServer on another type, which deals with processing responses.  The IP will display intellisense and options via the state, and when the user selects a property, the server decides what to do with it and returns some new state.

This is very cool as your state object can be whatever you like – record types, DU’s, or full classes.  Responses to property access can similar be of any type you like, and can be different on each property if you like.  The problems with this system are

  1. The creation of the text and properties is separate from the response handling of that property.  This can make it hard to read and reason about.
  2. It is a bit unsafe because everything gets boxed, unboxed, and each time the server has to deal with a response,  based on the current state you have to make sure you are dealing with the correct types coming back from the TP which can be a hit messy and detract from what you are really trying to do
  3. Although each state might require its own unique data, there is not any way to represent one thing without threading all the previous state through.  For example, if I want the user to enter a bunch of letters via properties until they press the [End] property, I can’t do this with just a string, Id have to carry the rest of whatever data I was using as well. This gets unwieldy quickly. There is no way to separate concerns.
  4. Again on with point 3, because of this it is not really possible to create re-usable chunks of state that perform common functions such as accepting input. 

 

 

The new system

In order to address this, I introduced another layer of abstraction, ‘cos you can never have too many layers of abstraction right? :)

type InteractiveState<'a> = 
    { displayOptions : 'a -> (string * obj) list 
      displayText : 'a -> string 
      processResponse : 'a * obj -> IInteractiveState 
      state : 'a } 
    member x.ProcessResponse o = x.processResponse (x.state, o) 
    interface IInteractiveState with 
        member x.DisplayOptions =  x.displayOptions x.state 
        member x.DisplayText = x.displayText x.state

This new record type is essentially a super-duper state object.  It brings together the creation of stuff and the processing of responses into the same place.  You can see it takes 3 functions and a bit of state, ‘a. 

  • displayOptions will be called with the current ‘a and is expected to generate a list of properties to display and a boxed version of some type that will be passed back to the server when the user selects that property.
  • displayText will be called with the current ‘a and used to generate what appears in intellisense when this type is currently selected (more on this later)
  • processResponse will be called with the current ‘a and is expected to return a new IInteractiveState

Because this is a generic type, it does mean when you start to use these together, they are going to need the same ‘a which is a bit of a pain, but it is readily solved by creating a DU of all the possible types that the various states in your system need.

type EnigmaTypes = 
    | Core of EnigmaCore.Enigma 
    | Strings of string 
    | Rotors of MachineRotor 
    with 
        member x.Enigma = match x with Core e -> e | _ -> failwith "" 
        member x.String = match x with Strings s -> s | _ -> failwith "" 
        member x.Rotor = match x with Rotors r -> r | _ -> failwith ""

This is not very nice but a very reasonable trade off for the power attained. Now the server object itself becomes very simple (infact this can be generalized as well)

type Enigma() = 
    interface IInteractiveServer with 
        member x.NewState: IInteractiveState = start() :> IInteractiveState        
        member x.ProcessResponse(state: IInteractiveState, response: obj): IInteractiveState =      
            let state = (state:?>InteractiveState<EnigmaTypes>) 
            state.ProcessResponse(response)

 

Start Your Engines!

Now the system is ready to rock!  You will notice when the server starts it calls start() to obtain its first state.  All the states are now just instances of record types.  start() looks like this

let start() = 
    { displayOptions = fun _ -> ["Begin!",box ()] 
      displayText = fun _ -> "Welcome to the type provider Enigma machine!" 
      processResponse = fun (e,_) -> mainMenu(e) :> _ 
      state = Core defaultEnigma }

this is as simple as it gets and not doing much interesting, you can see it returns one property “Begin!” along with a boxed unit type. I don’t care about the response type as there is only one property so I know it must be that being selected. 

processResponse simply creates the next state using the function mainMenu( .. ) which it passes the current state, in this case the default version of the enigma machine.

mainMenu(..) is much more interesting and too long to show here, so I will show some extracts / condensed versions

type MainMenuResponses = 
    | Nothing 
    | SelectLeftRotor 
    | SelectMiddleRotor 
    | SelectRightRotor 
    | SelectReflector 
    | SetWheelPosition 
    | SetRingPosition 
    | CreatePlugMapping 
    | Translate

let rec mainMenu(enigma:EnigmaTypes) =

{ displayOptions = fun _ -> ["# ",box Nothing; 
                             "Select a new left rotor",box SelectLeftRotor 
                             "Select a new middle rotor",box SelectMiddleRotor ….. ] 

  displayText = fun _ -> printMachine enigma.Enigma 
  processResponse = fun (e,r) -> 
    match unbox<MainMenuResponses> r with 
    | Nothing -> mainMenu(e) 
    | SelectLeftRotor -> 
        enterText("",[for i in 1..8-> sprintf "Rotor %i" i, box (string i)], 
            (fun s -> "Choose the rotor to place on the left"), 
            (fun s -> 
                let e = { e.Enigma with Left = getRotor s , WheelPosition 'A' } 
                mainMenu(Core e) :> IInteractiveState), 
            (fun _ -> false) )

 

The first bits are pretty straight forward, it shows the various menu options and boxes which one was selected using the DU defined above.  processResponse then unboxes the return value, matches on it,  then does something with the result.

In this case, it is calling another function called enterText – and this is where it gets really cool!  enterText is defined as follows

let rec enterText(state:string,options,genDisplayText,continuation,repeatCondition) = 
    { displayOptions = fun _ -> options 
      displayText = fun d -> genDisplayText d 
      processResponse = fun (current:EnigmaTypes,c) -> 
        let s =  current.String + string c 
        if repeatCondition s then enterText(s,options,genDisplayText,continuation,repeatCondition) :> _ 
        else continuation s 
      state = Strings state }

This function is designed based on the observation that when I want to accept an arbitrary amount of text from the user, the following is required

  1. A list of what inputs to be shown
  2. A way of knowing when to stop accepting more inputs (and recursively creating more types)
  3. A continuation function, that accepts the completed output and then generates some other state.

What is really awesome with is is that the enterText function simply takes a string – it doesn’t know or care about the Enigma object – this is made possible by the fact that we can now create a closure over the previous state’s data within the continuation lambda function, allowing us to decouple the recursive-text-entering portion of the type system.  Very nice!

Engage Turbo Mode!

Great!  now I can create re-usable state chunks and control stuff via closures.  However, there is one more usually contrived problem that this system solves very well.  Let’s take the menu function Adjust Wheel Position.  This one is a little bit of a pain because it requires several steps – first you must pick which wheel you want to manipulate, then you choose the letter you wish to set it to.  Usually you would have to model these as separate states, which would be confusing if you wanted to do the same thing somewhere else - but now you can actually compose these functions and closures together so that the whole intent and flow is clear within the same definition.  For example :

let selectMachineRotor(continutation) = 
    { displayOptions = fun _ -> 
        ["Left Wheel", box LeftRotor 
         "Middle Wheel", box MiddleRotor 
         "Right Wheel", box RightRotor] 
      displayText = fun d -> "Select a rotor." 
      processResponse = fun (current,c) -> 
        continutation (c:?>MachineRotor) 
      state = Rotors MachineRotor.LeftRotor }

This function accepts a continuation function and asks the user to select a wheel, and calls the continuation function with their choice

| SetRingPosition -> 
    let apply l  = function 
        | LeftRotor -> { e.Enigma with Left = { fst e.Enigma.Left with RingSetting = l }, snd e.Enigma.Left } 
        | MiddleRotor -> { e.Enigma with Middle = { fst e.Enigma.Middle with RingSetting = l }, snd e.Enigma.Middle} 
        | RightRotor -> { e.Enigma with Right = { fst e.Enigma.Right with RingSetting = l }, snd e.Enigma.Right }

    selectMachineRotor(fun rotor ->                  
        enterText("",[for i in 'A'..'Z' -> sprintf "%c" i, box (string i)], 
            (fun s -> "Choose a letter"), 
            (fun s -> 
                let e = apply (RingSetting s.[0]) rotor 
                mainMenu(Core e) :> IInteractiveState), 
            (fun _ -> false) ) :> IInteractiveState )

When the SetRingPosition menu item is selected, it returns the selectMachineRotor function, and the continuation function passed to uses the enterText function allowing the user to pick a letter, and finally the result is applied to the Enigma object and the whole thin is returned back to the main menu.  Very cool!

Straight away this is useful as the AdjustWheelPosition menu item has to do a very similar thing

| SetWheelPosition -> 
    let apply l  = function 
        | LeftRotor -> { e.Enigma with Left = (fst e.Enigma.Left, l)  } 
        | MiddleRotor -> { e.Enigma with Middle = (fst e.Enigma.Middle, l)  } 
        | RightRotor -> { e.Enigma with Right = (fst e.Enigma.Right, l)  }

    selectMachineRotor(fun rotor ->                  
        enterText("",[for i in 'A'..'Z' -> sprintf "%c" i, box (string i)], 
            (fun s -> "Choose a letter"), 
            (fun s -> 
                let e = apply (WheelPosition s.[0]) rotor 
                mainMenu(Core e) :> IInteractiveState ), 
            (fun _ -> false) ) :> IInteractiveState )

 

Conclusion

The IP has had a bit of a face-lift which makes it easier to write and read what is going on.  Plus you can have an Enigma machine in a type provider.  Who wouldn’t want that!  The code is a little bit of a mess at the moment, but I should clean it up soon and move the new super-state into the common interfaces project. 

Tags:

F# | type providers