How I cheated at Wordament, and won

All code for this article can be found here.

You can see the bot in action here.

What is Wordament, and why cheat?

Wordament is a word-searching game for Android, iPhone and Windows Phone (hah). The game displays a four by four grid of letters. The player’s job is to swipe through the letters to find words. Points are awarded for every word found, based on complexity. Every player plays the same board simultaneously and the game ranks players after each 90-second round.

I was always pretty bad at this game, making it to the top 35% on a good day. While playing I noticed that the players at the top of the scoreboard were either extremely good, or not legit. Many have scores and word counts seemingly too high to be achieved by a human being in 120 seconds. So I set out to beat these top players by writing a bot.

Why bother? I don’t care about getting the best score on Wordament, it just seemed like an interesting technical challenge.

Approach

Because I wanted to use this challenge to play with fun technologies my approach was a little convoluted. I wrote a web service that runs on the Microsoft Azure Websites platform (free tier). This service takes a Wordament board as input and gives all possible solutions to the board as output.

I then wrote an Android UI automation test. This test takes a screenshot of the board and finds letters on it. It sends the letters up to my Azure service to get the possible solutions. It then uses UI automation to swipe these solutions into the game board.

I call these components the ‘solver’, the ‘reader’ and the ‘player’.

The solver

Here we need a component that can find every solution given a 16-letter Wordament board. A ‘solution’ in this context is a word plus the tile positions on the board that it will need to swipe to input that word. For example if I give it the board

    LHAS
    DLAM
    INON
    CTAG

It might output something like

[
  {
    "word": "MONTANAS",
    "positions": [
      7,
      10,
      9,
      13,
      14,
      11,
      6,
      3
    ]
  },
  {
    "word": "AMANITA",
    "positions": [
      2,
      7,
      6,
      9,
      8,
      13,
      14
    ]
  },
  ... //etc

I would leave it up to the device-specific code to transform these board coordinates into screen coordinates.

Creating a dictionary

First we need a list of possible words. For this I Google’d ‘word list’ and ‘dictionary list’ and found a bunch of options to download. Towards the end of this project I found that every individual list I found had two deficiencies. None of them had the complete set of words for any given board, and they all had lots of words that you wouldn’t expect to find on a Wordament board.

I solved this by creating a quick program. It takes a directory of word lists and returns all the words which appear in at least three lists. This way every word in my final set is common enough to be found in many dictionaries (high likelihood of being a possible Wordament word). Also any common word missing from one word list is likely to be found in the others.

The data structure

Here’s how I wanted to search a Wordament board for a given word. For each letter on the board, find out if there are any words that start with it and each of the neighbouring letters. If there are, for each neighbouring letter, if any words in the current list finish with this letter then add the solution to the result. Repeat for every connected letter.

Here’s a pseudocode algorithm

foreach letter in board:
  do_search(letter, [])

do_search(current_word, result_set):
  if words.contains(current_word):
    result_set = result_set.add(current_word)

  foreach letter in current_word.neighbours:
    if words.with_prefix(current_word + letter):
      do_search(current_word + letter, result_set)

It happens that there’s a data structure purpose built to perform these kinds of prefix searches. It’s called the prefix tree, or trie (pronounced ‘tray’). I’ve written before about the prefix tree and how I implemented mine in F#. You can find the code here or just grab the binaries from Nuget. I won’t go into details about the prefix tree here. Suffice it to say it exposes exactly the interface I need to perform this prefix search. We’ll see this interface in action in this article.

Searching for solutions

To solve the board with the given 16 letters (see the reader section below for how we get them) we just need to pass them through the search algorithm. We also need to pass our in trie which has been pre-loaded with the word list, described above. Here’s the actual F# code.

// this is our Board module, with some types for the model
[<RequireQualifiedAccess>]
module Board

let cols = 4
let rows = 4
let cells = rows * cols

type Solution(word, positions) =
    member this.word = word
    member this.positions = positions

type Letter(index, character, neighbours) =
    member this.character = character
    member this.neighbours = neighbours
    member this.index = index

let generateNeighbours board currentIndex =
    seq { 
        if currentIndex > cols then
            if currentIndex % cols > 0 then yield currentIndex-(cols+1)
            yield currentIndex-cols
            if currentIndex % cols < (cols-1) then yield currentIndex-(cols-1)
        if currentIndex % cols > 0 then yield currentIndex-1
        if currentIndex % cols < (cols-1) then yield currentIndex+1
        if currentIndex < cells-cols then
            if currentIndex % cols > 0 then yield currentIndex+(cols-1)
            yield currentIndex + cols;
            if currentIndex % cols < (cols-1) then yield currentIndex+(cols+1)
    }

type Board(letters:string) =  
    let charList = List.ofArray(letters.ToCharArray())
    member this.letterGraph = 
        charList
        |> List.mapi (fun index character -> 
            new Letter(index, character, (List.ofSeq (generateNeighbours letters index))))

let depthFirstSearch (board:Board) (shortCircuitFunction:string -> bool) (selectorFunction:string -> bool) =
    let rec search (board:Board) (currNode:Letter) currString path searchedList =
        seq {
            let newString = currString + currNode.character.ToString()
            if not(shortCircuitFunction newString) then
                if selectorFunction newString then
                    yield Solution(newString, List.rev(path))
                for neighbourIndex in currNode.neighbours do
                    if not(path |> List.contains neighbourIndex) then 
                        let nextLetter = board.letterGraph.[neighbourIndex]
                        yield! search board nextLetter newString (nextLetter.index :: path) (currNode.index :: searchedList)
        }
    seq {
        for letter in board.letterGraph do
            yield! search board letter "" [letter.index] []
    }

// and the algorithm
let solve boardLetters trie =
    let board = new Board.Board(boardLetters)
    let solutions = Board.depthFirstSearch board (fun s -> not(Trie.isPrefix(trie, s))) (fun s -> Trie.isWord(trie, s))
                   |> Seq.filter(fun s -> s.word.Length > 2)
                   |> Seq.distinctBy(fun s -> s.word)
                   |> Seq.sortBy(fun s -> s.word)
                   |> Seq.sortByDescending(fun s -> s.word.Length)
    solutions

This is worth explaining.

We define a couple of types. Solution, which is just a word and a list of integers giving the positions of the letters. Letter, which is a node in the board which points to its neighbours (so we can represent the board as a graph). And Board, which takes a string representing the 16 letters and hooks them all together based on their locations on the grid (this is the generateNeighbours function).

Next we define a depth first search. This is a normal DFS algorithm, with the added feature that it takes a “short circuit” function. If this function returns true at any point during the search then the search will halt. This is so that when we search we can tell it to stop if the current word is not a valid prefix for any word in our trie.

The result of this search function is the list of all solutions, including the path required for each one.

The web service

I wrote a web service to host my solver code. It’s a simple ASP.NET MVC service with three controllers.

The first is named ReaderController. This is capable of taking a bitmap image (a screenshot of a Wordament board) from the body of a request and returns the letters on the board as text (more on the Reader later). I mostly used this for testing and debugging - it’s not used in the final application.

The next controller is called SolutionController. It takes 16 letters (the characters on a Wordament board). It sends them to my solver and returns the solutions for the board. Like ReaderController this was mostly for testing and debugging.

And the third controller is the poorly-named SolverController. This guy combines the behaviours of the previous two controllers. It reads a Wordament screenshot from the request and sends the letters as text to my solver. It then returns the solutions to the caller. This one was used by my Android program to find the solutions from a Wordament screenshot.

The reader

Getting the letters from a board took a bit of effort. Presumably to prevent cheating, Microsoft doesn’t put any kind of identifying metadata onto the objects that make up a board. My only option was to analyse a bitmap of the phone screen with the board on it.

I needed a simple OCR algorithm that would allow me to identify letters from bitmaps. After playing with some pretty crappy web services I decided to roll my own. My implementation is simple and inflexible, but it works well on Wordament boards. All the code we’ll discuss here is available in Reader.fs in my Bitbucket repository. This is written in F# but would be easy to port to any language.

First I needed to cut up a Wordament board so that I had individual bitmaps of each of the 16 letters. So I needed to search the bitmap for the orange letter tiles. I start by defining the start and end rows that I wanted to perform the search over. Here I just hard coded ratios of the screen size. I always used ratios and not absolute pixel values because I was testing this app on many devices with different resolutions.

    let findSquares (bitmap:System.Drawing.Bitmap) =
        let startRow = (int)(System.Math.Round((float bitmap.Height) * 0.14));
        let endRow = (int)(System.Math.Round((float bitmap.Height) * 0.7));
        getSquares bitmap startRow endRow

The idea here is that I wanted to divide up the board so that the only orange pixels inside the boundaries are letter tiles. This way I can use that distinctive orange colour to easily divide the letter tiles up. This divided up a Wordament board like this:

Board preparation, part 1.

Next is the getSquares function. Here I iterate through each row of pixels, looking for the first orange pixel on the row. When I find an orange pixel, I iterate across it and then down it until I run out of orange pixels. Now these boundaries make up a bounding rectangle for this tile. I then continue my search for the next tile by starting from the upper right of this rectangle and repeat. When I run out of room on this pixel row, I jump down a full tile’s height and start searching again from this row. Here’s the full code.

    let isOrange (color:Color) =
        color.R > (byte)220 
        && color.G > (byte)130 
        && color.G < (byte)170
        && color.B < (byte)29

        
    let getBounds (bitmap:Bitmap) col row =
        let colUpper = seq { col .. 1 .. bitmap.Width-1 }
                        |> Seq.find (fun p -> not(isOrange (bitmap.GetPixel(p, row))))
        let rowUpper = seq { row .. 1 .. bitmap.Height-1 }
                        |> Seq.find (fun p -> not(isOrange (bitmap.GetPixel(col, p))))
        new Rectangle(col, row, colUpper-col, rowUpper-row)
        
    let getSquares (bitmap:Bitmap) startRow endRow = 
        let mutable row = startRow
        let mutable col = 0
        let mutable rectHeight = 1
        let mutable result = []

        while row < endRow do
            while col < bitmap.Width do
                let color = bitmap.GetPixel(col, row)
                if isOrange color then
                    let rect = getBounds bitmap col row
                    col <- col + rect.Width
                    rectHeight <- rect.Height
                    result <- rect :: result
                else
                    col <- col + 1
            col <- 0
            row <- row + rectHeight
            rectHeight <- 1

        result |> List.rev

There are probably less stupid ways of finding bounding boxes but this works well ¯\(ツ)/¯ This divides the board into 16 square bitmaps, like so:

Board preparation, part 2.

To match each bitmap to a letter, I divided the bitmaps into quarters and assigned each quadrant a value based on the ratio of white to orange pixels. For example, here’s the letter ‘G’, with its so-called ‘letter vector’:

Board preparation, part 3.

How did I get these letter vector values? By painstakingly analysing a ton of screenshots of Wordament boards. In fact, if you look at my code you’ll see I’m actually missing Q and X. these letters appear so infrequently in Wordament that I wasn’t able to snap a screenshot to analyse them.

You may also notice I do not assign a value to the upper left quadrant. After implementing and testing this whole system, I found some letters were not matching when they should have been. I discovered that the digit in the upper left of the letter tile, the score, changes value on certain boards. This happens in special rounds, like where letters in corners are more valuable. This was enough to throw off my simple algorithm. I could have made my algorithm more permissive, but I found that the three other quadrants were enough to uniquely identify a letter. So I just threw that upper-right quadrant away.

So now I have a bitmap from the letter tile and I have a pre-defined vector to letter map. I can break my bitmap tile into quadrants. I can transform my quadrants into a vector of ratios of white to orange. And I can find the vector in my map that most closely matches the vector from my bitmaps. Here’s the code for doing this:

    let vDist (a:float,b,c) (aa,bb,cc) =
        sqrt ((a-aa)*(a-aa) +
              (b-bb)*(b-bb) +
              (c-cc)*(c-cc))

    let matchLetterVector (a,b,c) =
        letters |> List.minBy(fun v -> 
            let (aa, bb, cc, _) = v
            vDist (a,b,c) (aa,bb,cc))

    
    let toLetter (bitmap:Bitmap) (rect:Rectangle) =
        let w = rect.Width / 2;
        let h = rect.Height / 2;
        let size = new Size(w, h);
        let quads = seq {
            yield bitmap.Clone(new Rectangle(new Point(rect.X, rect.Y), size), bitmap.PixelFormat)
            yield bitmap.Clone(new Rectangle(new Point(rect.X + size.Width, rect.Y), size), bitmap.PixelFormat)
            yield bitmap.Clone(new Rectangle(new Point(rect.X, rect.Y + size.Height), size), bitmap.PixelFormat)
            yield bitmap.Clone(new Rectangle(new Point(rect.X + size.Width, rect.Y + size.Height), size), bitmap.PixelFormat)
        }
        let list = quads |> Seq.map (fun q -> whitePixelCount q) |> List.ofSeq
        let vector = (list.[1], list.[2], list.[3])
        let (a,b,c,letter) = matchLetterVector vector
        if (vDist (a,b,c) vector) > 0.02 then "*"
        else letter.ToString();

Now we just combine these two functions to break down the board into 16 bitmap letter tiles, and pass these tiles through the toLetter function. We wind up with 16 letters and return them. We can pass these letters into the solver defined above and out pops the solutions, ready to be input into the game.

The player

Not surprisingly the player was the most finicky and least fun part of this project, but it’s fairly quick to describe.

I created a simple do-nothing Android project with a single test class. The test class takes a screenshot of the game board and sends it up to my web service, which sends it to the reader and solver. When the test receives the solutions it inputs them into the application.

Screenshotting the board

Screenshotting a board in an Android test is straight-forward.

            String dir = Environment
                    .getExternalStorageDirectory()
                    .getAbsolutePath();

            String filename = "file.png";
            File file = new File(dir + File.separator + filename);
            Log.d("Wordament.bot", "Screenshotting board");
            boolean screenshotResult = device.takeScreenshot(file, 0.1f, 20);

            if (!screenshotResult) {
                Log.d("Wordament.bot", "Failed to take screenshot");
            }

Once we’ve taken the screenshot it needs to be prepared and sent to the web service. The important part here is how we compress the screenshot. Remember how we wrote quite a brittle reader? We need to make sure that the orange to white ratios in the image match our expectations. This means using a compression method that preserves colors and edges. JPEG is definitely out, but PNG is a good fit.

I also decided to scale the image down by a factor of two on each side. This preserves the ratios of white to orange but reduces the size of the image by a factor of four, which significantly improves performance (especially if you’re using this on a high-resolution device like a Pixel phone). It could probably scale perfectly fine to much smaller sizes but this was enough for me.

I used pretty standard JSON handling to manage the request and response.

    @NonNull
    private Solution[] getSolutionsFromWeb(File file) {

        try {
            String dir = Environment
                    .getExternalStorageDirectory()
                    .getAbsolutePath();

            File compressedFile = new File(dir + File.separator + "file2.png");

            Bitmap capturedImage = BitmapFactory.decodeFile(file.getPath());
            Bitmap bitmap = Bitmap.createScaledBitmap(capturedImage, capturedImage.getWidth()/4, capturedImage.getHeight()/4, true);
            FileOutputStream fos = new FileOutputStream(compressedFile);
            bitmap.compress(Bitmap.CompressFormat.PNG, 20, fos);
            fos.flush();
            fos.close();
            byte[] bytes = IOUtils.toByteArray(new FileInputStream(file));
            OkHttpClient client = new OkHttpClient();
            Request request = new Request.Builder()
                    .url("http://wordamentbot.azurewebsites.net/solver")
                    .method("POST", RequestBody.create(
                            okhttp3.MediaType.parse("image/png"),
                            bytes))
                    .build();

            Response response = client.newCall(request).execute();
            Gson gson = new Gson();
            return gson.fromJson(response.body().string(), Solution[].class);
        } catch (IOException e) {
            Log.d("Wordament.bot", "Problem contacting OCR service\r\n" + e.getMessage());
            return new Solution[0];
        }
    }

Now that we have the solutions we need to figure out how to input them. The first step is figuring out where is the game board on the screen and where are the letter tiles. Here are a couple of utility methods for achieving this. This uses standard Android UI automation test tools for querying and interacting with the Android object model.

    @NonNull
    private List<Point> getTileCoordinates(UiObject2 board) {
        List<UiObject2> tiles = board.getChildren();
        List<Point> centers = new ArrayList<>();
        for (int i = 0; i < tiles.size(); i++) {
            centers.add(tiles.get(i).getVisibleCenter());
        }
        return centers;
    }

    @NonNull
    private UiObject2 getGameBoard() {
        UiObject2 boardView = null;
        Log.d("Wordament.bot", "Waiting for device");
        do {
            device = UiDevice.getInstance(InstrumentationRegistry.getInstrumentation());
            try {
                List<UiObject2> objects = device.findObjects(By.clazz("android.widget.RelativeLayout"));
                for (UiObject2 view : objects) {

                    // the game board is a view with exactly 16 child views (the letter tiles)
                    // and takes up at least two thirds of the screen (so it's not the half-screen
                    // game board you see between rounds).
                    if (view.getChildCount() == 16 &&
                        view.getVisibleBounds().width() > ((float)device.getDisplayWidth())/1.5f) {
                        Log.d("Wordament.bot", "Found view with 16 subviews");
                        boardView = view;
                        break;
                    }
                }
            } catch (StaleObjectException e) {
                Log.d("Wordament.bot", "Caught StaleObjectException, probably changing screens");
            }
        } while (boardView == null); // if the board is not visible, go back and try again
        return boardView;
    }

The result of these methods is the coordinates of the UIObject2’s that represent the letters. So now we know which letters to swipe and where they are, it’s a matter of performing the swiping with automated testing tools:

                for (Solution solution: solutions) {
                    solution.solve(device, centers);
                    Log.d("Wordament.bot", "Swiped + " + solution.word);
                }
    class Solution {
        public String word;
        public int[] positions;

        // swipe this solution onto the given device with supplied letter tile coordinates
        protected void solve(UiDevice device, List<Point> tileCoords) {
            Point[] coords = new Point[this.positions.length];
            for (int i = 0; i < this.positions.length; i++) {
                int index = this.positions[i];
                coords[i] = tileCoords.get(index);
            }
            device.swipe(coords, coords.length);
        }
    }

The Android test framework supplies very simple API for us to swipe through the UI so there’s little work for us to do here.

The result, and some problems

So here’s a quick video of the result. The bot will get us to the top of the leaderboard on any game it’s capable of solving well.

The limitations

I didn’t go all the way with this project. There are certain boards that this bot won’t solve. There’s an example of such a board to the right.

You can see that this board has a letter combination. Ammending the bot to handle letter combos like this would be straight-forward, except for generating the letter vectors to identify every possible combination. Either a LOT of painstaking work or a smarter OCR system wouwld be required.

Another limitation is the special games that Wordament presents - some of my favourite games. These include games like “E in the corners” where every corner will have an ‘E’ and these tiles are worth much more points. Now, in most cases this bot will do well in such games as a result of being exhaustive, but as discussed in the word list section our dictionaries are not in fact completely exhaustive. If we are missing a significant number of ‘E’ results in our word list then we may miss out on too many points to win the game.

The good news is that in either of these cases the bot will still perform. Letters that are not recognised are returned as “*”, a letter that never occurs. So although that tile will never be used, the bot will continue to work around it.

These are not problems I intend to solve, as this bot was just a muck-around project for me. If you update the bot yourslef I’d love to see how, and am keen to hear any other feedback you have to offer. Thanks for reading!

Marten & ASP.NET Core - Postgresql noSQL storage in ASP.NET Core

What is Marten and why do I care?

Marten (no relation) is an open source .NET driver for Postgresql that focuses on Postgres’ JSON-based document storage capabilities. Think of it like an alternative to MongoDB or RavenDB for your .NET applications.

Getting started

This article is going to walk you through the first steps of getting an ASP.NET Core project up and running with Marten, as well as basic querying. This should work on all operating systems.

The first thing you’ll want to do is start a new ASP.NET Core project. Remember, in the new .NET Core world an ASP.NET Core project is just a regular old .NET Core console app that hosts its own web server and uses ASP.NET libraries. This guide is the canonical reference for getting started here. You’ll end up with three files in your project that look like this.

using Microsoft.AspNetCore.Hosting;

namespace Sample
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var host = new WebHostBuilder()
                .UseKestrel()
                .UseStartup<Startup>()
                .Build();

            host.Run();
        }
    }
}
using Microsoft.AspNetCore.Builder;
using Microsoft.AspNetCore.Hosting;
using Microsoft.AspNetCore.Http;

namespace Sample
{
    public class Startup
    {
        public void Configure(IApplicationBuilder app)
        {
            app.Run(context =>
            {
                return context.Response.WriteAsync("Hello from ASP.NET Core!");
            });
        }
    }
}
{
  "version": "1.0.0-*",
  "buildOptions": {
    "debugType": "portable",
    "emitEntryPoint": true
  },
  "dependencies": {},
  "frameworks": {
    "netcoreapp1.0": {
      "dependencies": {
        "Microsoft.NETCore.App": {
          "type": "platform",
          "version": "1.0.0"
        },
        "Microsoft.AspNetCore.Server.Kestrel": "1.0.0"
      },
      "imports": "dnxcore50"
    }
  }
}

Add a model and a controller

Let’s quickly add a model - this will be the object that maps to our table in Postgresql. Create a new Model directory and add a BlogPost model.

using System;
using System.Collections.Generic;

namespace Sample.Model
{
    public class BlogPost
    {
        public int Id { get; set; }
        public string Title { get; set; }
        public string Body { get; set; }
        public IEnumerable<string> Tags { get; set; }
        public Dates ModifiedDates { get; set; }

        public class Dates 
        {
            public DateTime CreatedDate { get; set; }
            public DateTime LastEditedDate { get; set; }
        }
    }
}

And we’ll need a controller which manages this. Create a new Controllers folder and create a file called BlogPostController.cs.

using System.Collections.Generic;
using Microsoft.AspNetCore.Mvc;
using Sample.Model;

namespace Sample.Controllers
{
    [Route("/posts")]
    public class BlogPostController
    {
        [HttpGet]
        public IEnumerable<BlogPost> Get()
        {
            // TODO get all blog posts from DB
            return new BlogPost[0];
        }

        [HttpGet("{id}")]
        public BlogPost Get(int id) 
        {
            // TODO get the specified blog post from DB
            return null;
        } 

        [HttpPost]
        public BlogPost Create([FromBody]BlogPost post)
        {
            // TODO create a blog post in the DB
            return null;
        }
    }
}

For this step you’ll also need to add a depedency on Microsoft.AspNetCore.Mvc to project.json - while we’re here, add dependencies on Kestrel (the built-in web server for aspnetcore development) and Marten:

{
  "version": "1.0.0-*",
  "buildOptions": {
    "debugType": "portable",
    "emitEntryPoint": true
  },
  "dependencies": {
    "Microsoft.AspNetCore.Server.Kestrel": "1.0.0",
    "Microsoft.AspNetCore.Mvc": "1.0.0",
    "Marten": "0.9.12.563"
  },
  "frameworks": {
// ...etc

Finally before using this controller you’ll need to setup the ASP.NET MVC framework. Edit your Startup.cs file:

using Microsoft.AspNetCore.Builder;
using Microsoft.Extensions.Configuration;
using Microsoft.Extensions.DependencyInjection;
using Marten;
using Microsoft.AspNetCore.Hosting;

namespace Sample
{
    public class Startup
    {
        public void Configure(IApplicationBuilder app)
        {
            app.UseMvc();
        }

        public void ConfigureServices(IServiceCollection services)
        {
            // Add framework services.
            services.AddMvc();
        }
    }
}

At this stage it’s a good idea to fire up the web server and make sure everything is working as expected. Go to your command line terminal and run ‘dotnet run’. It should tell you that the server is running on localhost on some port (default is 5000). Open up a browser, Postman or your HTTP client of choice and make sure that when you hit http://localhost:5000/posts an empty array is returned. If not, something has gone wrong.

Configure dependency injection

The next step is to get the Marten DocumentStore object injected into our controllers so we can use it. Open up your Startup.cs file and edit the ConfigureServices method so that it looks like below. ConfigureServices is the method that the ASP.NET Core framework will call to set up your dependency injection framework - a simple DI container is included with ASP.NET core, so that’s what we’re going to use.

public void ConfigureServices(IServiceCollection services)
{
    // Add framework services.
    services.AddMvc();

    // Marten document store
    services.AddScoped<IDocumentStore>(provider => 
        DocumentStore.For("Server=127.0.0.1;Port=5432;Database=my-database;User Id=admin;Password=admin;"));
}

This line tells the dependency injection framework that we want to be able to ask for instances of IDocumentStore, and when we ask for them you should call that DocumentStore.For() method to get one. Additionally because we use the AddScoped method, this object will exist for the lifetime of a single request. You can read more about object lifetimes in ASP.NET Core here.

Obviously you’ll need to change your connection string to point to your own Postgresql instance. You can find more information about Postgresql connection strings here.

Querying in the controller

Now we should be able to just add an IDocumentStore to the controller’s constructor and the framework will supply it to us, ready to use. Let’s give it a crack. First add a constructor to the controller which takes the IDocumenStore and stores it in an instance variable.

private readonly IDocumentStore _documentStore;

public BlogPostController(IDocumentStore documentStore)
{
    _documentStore = documentStore;
}

And let’s flesh out the methods we defined earlier.

[HttpGet]
public IEnumerable<BlogPost> Get()
{
    using (var session = _documentStore.QuerySession())
    {
        return session.Query<BlogPost>();
    }
}

[HttpGet("{id}")]
public BlogPost Get(int id) 
{
    using (var session = _documentStore.QuerySession())
    {
        return session
            .Query<BlogPost>()
            .Where(post => post.Id == id)
            .FirstOrDefault();
        
    }
} 

[HttpPost]
public BlogPost Create([FromBody]BlogPost post)
{
    using (var session = _documentStore.LightweightSession())
    {
        session.Store(post);
        session.SaveChanges();
        return post;
    }
}

Let’s dig into what we’re doing here. The IDocumentStore can supply sessions which we use to query the database.

You may notice we’re using two different methods to get the DB session - QuerySession() and LightweightSession(). The query session is a read-only session, optimised for read scenarios. LightweightSession is a read-write session which requires you to manage object change tracking yourself.

The other alternatives are OpenSession() which supplies an implementation of IDocumentSession which is backed by an identity map - basically an in-memory cache of any data that has been retrieved. And finally there’s DirtyTrackedSession() which is a session which will track changes you make to any retrieved entities by storing the original document in memory. I don’t recommend using this unless you really need to - other than the performance penalty, in my experience it’s simpler to be explicit with your changes.

Once we have the session we can query it by calling Query<T> where T is the document type we’re trying to look up. The object returned by Query() is a Linq IQueryable so you can call most common Linq extension methods on it (although you should be cautious with how you query a document database - see more query information here).

Test it out

To test this, fire up your app an insert a document by issuing a POST request to http://localhost:5000/posts that looks something like:

{
    title:         "My new blog post",
    body:          "<h2>a blog post</h2><p>this is my new blog post</p>",
    tags:          ["marten", "blog"],
    modifiedDates: {
        createdDate:    "08/09/2015 21:00",
        LastEditedDate: "08/09/2015 22:50"
    }
}

And you’ll receive a response:

{
  "id": 1001,
  "title": "My new blog post",
  "body": "<h2>a blog post</h2><p>this is my new blog post</p>",
  "tags": [
    "marten",
    "blog"
  ],
  "modifiedDates": {
    "createdDate": "2015-08-09T21:00:00",
    "lastEditedDate": "2015-08-09T22:50:00"
  }
}

Interestingly you’ll find that Marten has automatically assigned a value to the Id field on our object. When you use an integer or long, Marten will use an auto-incrementing algorithm, and it will generate GUIDs if your Id field is a GUID. See here for more info on Marten object identity.

You can now point your web browser at http://localhost:5000/posts to see a listing of every document you have inserted, or http://localhost:5000/posts/{id} to find the document with that ID.

Wrapping up

The most interesting thing is how Marten is using Postgres to store your data. If you open your database instance you’ll find a table that’s defined something like

CREATE TABLE public.mt_doc_blogpost
(
  id integer NOT NULL,
  data jsonb NOT NULL,
  mt_last_modified timestamp with time zone DEFAULT transaction_timestamp(),
  mt_version uuid NOT NULL DEFAULT (md5(((random())::text || (clock_timestamp())::text)))::uuid,
  mt_dotnet_type character varying,
  CONSTRAINT pk_mt_doc_blogpost PRIMARY KEY (id)
)
WITH (
  OIDS=FALSE
);
ALTER TABLE public.mt_doc_blogpost
  OWNER TO admin;

The interesting bit is “data jsonb NOT NULL” which is the column that stores all of the data. The json document stored in there looks just like the one that was returned after your POST request. The jsonb data type in Postgresql is much more than just a JSON string - there’s real potential to do some cool stuff with this data type, and that’s why Marten is so interesting.

Read more about Marten here, and check out the code. You can find the full source code for this guide at my Bitbucket.

Prefix tree (trie) in F#

What is a prefix tree?

A prefix tree - otherwise known as a trie (pronounced “tray”) - is a data structure designed for fast searching over prefixes - for example given the list of words [CAT, CATS, CART, CARTS], which words are prefixed with “CAR”? Performing this search on a hashset would require you to check every value (O(n)) complexity). A sorted list would need to perform a fast search for the first item with the prefix and then scan or search the list until no matching items remain - O(logn) + O(logm) where m is the sublist which has the prefix - which is fast, but a sorted list is slow to build, slower than a hashset to search for single items and slow to tell me if a given string is a valid prefix to any word in the list.

With a prefix tree this search is performed in O(m*p) time (again m is the sublist of prefixed strings, and p is the length of the average result string - typically very small compared to the string list) and search for a single string in the prefix tree is performed in O(p) where p is the length of the string to search for (not as fast a a hash set, but very near for most cases). At a glance this seems worse than a sorted list, but in typical use cases, such as storing dictionary words, the length of the word you’re searching for is a much smaller number than the number of words you’re storing.

And the coolest thing about a prefix tree is that it’s actually really simple. A prefix tree is a node with (optionally) a value, and a map of values to subnodes. To construct a prefix tree, start with a node with no value and add a string by appending that node’s map with the first character, mapping to a new trie with that character as its value, and add the rest of the string to that node recursively in the same way.

Implementation

I have implemented a simple prefix tree in F#. The code is available here and you can find it on nuget. This trie works well in C# and F# (and any other CLR language) and unlike other F# prefix trees I’ve spotted around the internet, mine is completely immutable.

Here’s an example of usage from F#:

open FTrie
[<EntryPoint>]
let main argv = 
    let t = Trie(["abcde";"abba";"ababab"])
    printfn "%A" (t.getWords()) // seq ["ababab"; "abba"; "abcde"]

    let t2 = t.withWord("cdfge");
    printfn "%A" (t2.getWordsPrefixedBy("ab")) // seq ["ababab"; "abba"; "abcde"]
    0

And in C#

using FTrie;
using System;
class Program
{
    static void Main(string[] args)
    {
        Trie t = new Trie(new[] { "cars", "carts", "cats", "cartoons" });
        Console.WriteLine(string.Join(", ", t.getWordsPrefixedBy("car"))); // cars, cartoons, carts

        var t2 = t.withWord("carve");
        Console.WriteLine(t.isPrefix("car")); // True
        Console.WriteLine(t.isPrefix("cra")); // False;
        Console.ReadLine();
    }
}

A better add function

This immutable implementation creates a new trie when you call the withWord() function instead of adding the word to the existing data structure. It does this by just pulling out every existing word and calling the Trie constructor with the plus the new one. With very large tries this could become quite memory and computationally intensive.

You could implement a better add function using the following algorithm. I didn’t bother because I didn’t need this functionality, so I leave it as an exercise for you (feel free to open a pull request into my repo if you find a good solution).

add(word)
1. currentNode = root
2. while currentNode contains first letter of word
3.   currentNode = currentNode.children[first letter of word]
4. clone currentNode except with a new children map containing the rest of this word chain
5. replace the chain of parents with new tries that reference the new nodes

What you’ll end up with is two trees that reference identical nodes in all but one branch and have different roots. This would be much faster than creating whole new prefix trees from scratch, and use less memory. Because all branches are immutable no one with a reference to another trie could mess around with data in your branches. Don’t forget to account for the EOW bit!

New scriptcs script pack - MemberPrint

I have just published a really simple little ScriptCs (I'm still not sure if I should be capitalising that or not) script pack. It's intended to be used on the REPL. All it does it print some details about the objects and types to help you navigate the REPL more easily. As usual, the code is available on GitHub.

To install, run the following command:

scriptcs -install scriptcs.memberprint

Then just run scriptcs. The easiest way to figure out the API is to run it over itself, like this:

c:\test>scriptcs
scriptcs (ctrl-c or blank to exit)
> var print = Require();
> print.Methods(print);
+   Constructors(Type t, BindingFlags flags, String regex, Boolean verbose) : Void
+   Constructors(Object o, Boolean verbose) : Void
+   Constructors(Object o, String regex, Boolean verbose) : Void
+   Constructors(Type type, Boolean verbose) : Void
+   Constructors(Type type, String regex, Boolean verbose) : Void
+   Constructors(Object o, BindingFlags flags, Boolean verbose) : Void
+   Constructors(Type t, BindingFlags flags, Boolean verbose) : Void
+   Constructors(Object o, BindingFlags flags, String regex, Boolean verbose) : Void
+   Equals(Object obj) : Boolean
+   Events(Object o, Boolean verbose) : Void
+   Events(Object o, String regex, Boolean verbose) : Void
+   Events(Type t, Boolean verbose) : Void
+   Events(Type t, String regex, Boolean verbose) : Void
..... (etc)

MemberPrint supports a few filtering options. You can filter using BindingFlags, just as though you were doing the reflection yourself:

> print.Methods(new System.Text.RegularExpressions.Regex(""), BindingFlags.Static|BindingFlags.Public);
+ # CompileToAssembly(RegexCompilationInfo[] regexinfos, AssemblyName assemblyname) : Void
+ # CompileToAssembly(RegexCompilationInfo[] regexinfos, AssemblyName assemblyname, CustomAttributeBuilder[] attributes) : Void
+ # CompileToAssembly(RegexCompilationInfo[] regexinfos, AssemblyName assemblyname, CustomAttributeBuilder[] attributes, String resourceFile) : Void
+ # Escape(String str) : String
+ # get_CacheSize() : Int32
+ # IsMatch(String input, String pattern) : Boolean
..... (etc)

You can also filter using regular expression text.

> print.Methods(new System.Text.RegularExpressions.Regex(""), "^Is.+");
+ # IsMatch(String input, String pattern) : Boolean
+ # IsMatch(String input, String pattern, RegexOptions options) : Boolean
+ # IsMatch(String input, String pattern, RegexOptions options, TimeSpan matchTimeout) : Boolean
+   IsMatch(String input) : Boolean
+   IsMatch(String input, Int32 startat) : Boolean

You can run it over types as well as instances. Can't remember the constructors for System.DateTime?

> print.Constructors(typeof(DateTime))
+   .ctor(Int64 ticks)
+   .ctor(Int64 ticks, DateTimeKind kind)
+   .ctor(Int32 year, Int32 month, Int32 day)
+   .ctor(Int32 year, Int32 month, Int32 day, Calendar calendar)
+   .ctor(Int32 year, Int32 month, Int32 day, Int32 hour, Int32 minute, Int32 second)
+   .ctor(Int32 year, Int32 month, Int32 day, Int32 hour, Int32 minute, Int32 second, DateTimeKind kind)
+   .ctor(Int32 year, Int32 month, Int32 day, Int32 hour, Int32 minute, Int32 second, Calendar calendar)
+   .ctor(Int32 year, Int32 month, Int32 day, Int32 hour, Int32 minute, Int32 second, Int32 millisecond)
+   .ctor(Int32 year, Int32 month, Int32 day, Int32 hour, Int32 minute, Int32 second, Int32 millisecond, DateTimeKind kind)
+   .ctor(Int32 year, Int32 month, Int32 day, Int32 hour, Int32 minute, Int32 second, Int32 millisecond, Calendar calendar)
+   .ctor(Int32 year, Int32 month, Int32 day, Int32 hour, Int32 minute, Int32 second, Int32 millisecond, Calendar calendar, DateTimeKind kind)

There are multiple overloads for each of the following methods:

  • Methods(object o)
  • Properties(object o)
  • Events(object o)
  • Constructors(object o)
  • Members(object o) (this one just calls all of the others)

The code is a little rough around the edges at the moment, but so far I have found it useful enough that I decided to share the script pack.

Solutions to some problems hosting Windows Workflow Foundation applications in AppFabric

I'm trying to stand up some Windows Workflow Foundation applications in AppFabric for a spike on an application I'm building and so far it has been... unpleasant. Here are a couple of solutions to some frustrating problems I encountered. Hopefully I can help save someone else a bit of time.

Workflow persistence is not functional because the net.pipe binding is not enabled for this web site

Encountered while trying to configure my WF service on an IIS virtual directory. In particular I encountered this error on the Workflow Persistence tab and a similar one onthe Workflow Host Management tab in the Configure WCF and WF for Application dialog.

Enable the net.pipe protocolNow, in theory this will be automatically fixed when you click Apply. And in theory, even if it's not then it should be resolved by taking the following steps:

  • Right click the web site that hosts your service in the IIS Connections pane, click Manage Websites -> Advanced Settings and add ,net.pipe to the end of the "Enabled Protocols" setting (no spaces!)
  • With the same site selected, click Edit Bindings on the Actions pane and add a net.pipe binding with Binding Information = *

And in theory, practice and theory are the same. But in practice, unfortunately, they are not. If you're not running Windows Server (or your install is a bit wonky) then there's an extra step to take, because you'll find that net.pipe is not an available binding type in the bindings dialog.

To resolve: Open the "Turn Windows features on or off" dialog (find it by searching in the Start menu/screen, under Settings). Open up the Microsoft .NET 3.5 folder and tick "Windows Communication Foundation Non-HTTP Activation". This should make the net.pipe binding available to you. You may need to run iireset in a console as admin first.


Error: Unable to start debugging on the Web Server

or, if you try running without debugging

Error: Cannot obtain Metadata from xamlx The remote server returned an unexpected response: (405) Method Not Allowed.

or, if you drill further into that error

HTTP Error 404.3 - Not Found The page you are requesting cannot be served because of the extension configuration. If the page is a script, add a handler. If the file should be downloaded, add a MIME map

The honest truth is I'm not sure what caused this error. I tried a whole bunch of stuff. I added some handlers to my root Web.config, installed some Workflow hosting modules in IIS, played with permissions, all kinds of stuff and I couldn't get the site to handle the .xamlx request. Ultimately here's what resolved the issue for me. The first step may not be necessary, I honestly don't know (I recommend reading the linked article). But it worked.

  • Run the following command: "%WINDIR%\Microsoft.Net\Framework\v3.0\Windows Communication Foundation\ServiceModelReg.exe" -r
  • Uninstall and reinstall the following Windows features from the "Turn Windows features on or off" dialog: Windows Communication Foundation HTTP Activation, Windows Communication Non-HTTP Activation. They are both under the .NET Framework 3.5 feature.

applicationHost.config : Unrecognised attribute: 'serviceAutoStartMode'

After I got my workflow up and running I realised that every other service and website on my machine was broken. It seems that AppFabric stepped all over my applicationHost.config file and left an invalid attribute in there. Take a look at this thread for the solutions to this issue.