Since I moved over to Javaland about a year and a half ago I have been a bit out of the loop on .NET stuff. I have made token attempts to stay on top of what’s happening with .NET Core, but it wasn’t a priority so I never really made much of an effort to understand it.
However this week I noticed something major taking place on Twitter around ASP.NET and figured I would take this opportunity to get my head around exactly what is happening in .NET land, and I may as well share what I learned. I went over all of this in a hurry and while on holiday, so please feel free to correct my mistakes!
I’m not linking issues because people dogpile on them. If people care: https://t.co/sVOWSRxtLN Core 2.x won’t run on full framework.
So before we get started we should define some terms. I’ll do this as concisely as possible as this has been gone over ad nauseum on other parts of the web - for a wonderful code-based example I recommend David Fowler’s GitHub gist, How .NET Standard relates to .NET Platforms (this will need to be updated for .NET Core 2.0 and ASP.NET Core 2.0).
.NET Standard (netstandard) - You can think of this as the API that .NET implementations (such as the full Windows-based .NET Framework, Mono, .NET Core, etc) implement. The “lowest common denominator”. Usually specified with a version (eg, netstandard1.0)
NetFx - Shorthand for .NET Framework foundational libraries, this refers to the main Windows-based framework of yore. Usually specified with a version a version in the format netXX (eg, net46).
CoreFx (netcoreapp) - The equivalent to NetFx for .NET Core. Mostly a subset of NetFx at this point, but moving faster. Both of these should implement .NET Standard. Usually specified with a version (eg, netcoreapp1.0).
So what happened this week?
In this GitHub issue a user noted that ASP.NET Core (remember, this is just a library) changed from targeting .NET Core and NetFx 4.6 to targeting only .NET Core (the user specifies the original target as netstandard, which is incorrect but only trivially so - netcoreapp and netfx are the only supported implementations of netstandard for these purposes).
So why did this cause such a kerfuffle? As a developer (I assume if you’re reading this you’re either a developer or are at least steeped in that world) you already know it’s problematic for anything to reference an implementation instead of an interface where one is available. But the problem is deeper than that - because Microsoft initially had a de facto commitment to targeting netstandard in ASP.NET, many people had already started writing their applications using ASP.NET and targeting the full framework. These applications use features of the full framework that are not yet available on netcoreapp (such as System.Drawing and System.DirectoryServices), and it’s not clear if and when such features will become available. Many of these applications are ports of full netfx apps to ASP.NET Core, which appeared to be the way forward.
And perhaps the biggest reason for the response Microsoft received from this move comes from the way it all happened. .NET Core is supposed to represent a new Miccrosoft, a Microsoft that embraces the community and works openly in collaboration with them. This move came after no community consultation and without so much as an announcement. This is not the way that people were hoping .NET Core would be run.
Microsoft appears to have taken feedback on board and reversed the decision to tie ASP.NET Core 2.0 to .NET Core. Although the first preview will indeed ship without support for netfx, Microsoft are now framing it as a temporary measure needed to be taken to get the bits out to devs ASAP.
It would have been nice to see a mea culpa on Microsoft’s end, rather than an attempt to make it seem like this was always the plan. It’s important that Microsoft do as much as possible to maintain developer faith in this fledgling platform, because it’s not necessarily clear that C# and .NET will remain the dominant technologies that they have become.
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.
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’.
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
It might output something like
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
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 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.
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.
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:
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.
There are probably less stupid ways of finding bounding boxes but this works well ¯\(ツ)/¯ This divides the board into 16 square bitmaps, like so:
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’:
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:
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.
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.
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.
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.
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:
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.
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 (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.
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.
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.
And we’ll need a controller which manages this. Create a new Controllers folder and create a file called BlogPostController.cs.
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:
Finally before using this controller you’ll need to setup the ASP.NET MVC framework. Edit your Startup.cs file:
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.
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.
And let’s flesh out the methods we defined earlier.
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).
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.
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
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.
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.
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#:
And in C#
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).
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!
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:
Then just run scriptcs. The easiest way to figure out the API is to run it over itself, like this:
MemberPrint supports a few filtering options. You can filter using BindingFlags, just as though you were doing the reflection yourself:
You can also filter using regular expression text.
You can run it over types as well as instances. Can't remember the constructors for System.DateTime?
There are multiple overloads for each of the following methods:
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.