Programming by Robert Massaioli

Learning through Programming Adventures

Read and write a RIFF (or RIFX)

What is RIFF anyway?

The RIFF file format is an old file format that is used as a container format for WAVE files among other things. Recently I decided that I wanted to write some pure Haskell code that could parse this file format so that I can start working my way towards building audio libraries in pure Haskell.

So you wrote a Haskell RIFF package did you?

Yes. You can view the results of my efforts on hackage: The riff package. You can even view the code on BitBucket if you like.

That package contains:

  • The riff library with the following features:
    • The ability to parse both RIFF and RIFX files. (Only perfectly formatted RIFF files are currently supported, we currently have no best effort support)
    • Convenience methods to make parsing / assembling RIFF files easier.
    • Written in pure Haskell so that you can run your code everywhere and be assured by all of the nice type safety that Haskell gives you.
  • A riff-structure executable that will print out the structure of all of the riff files that you provide it with.
  • A riff-convert executable that will let you convert RIFX files into RIFF files and vice versa.
  • A riff-identity executable that is pretty useless for practical purposes (it just makes a clone of the RIFF file you give it) but great for testing the library and it serves as a good code example.
  • Complete documentation coverage so that you know how to use each and every method in the library and what the limitations are.

You can give it a try today to read some RIFF files and it is all pretty self explanitory. I hope somebody gets some good use out of this. I am going to try and keep this library small and focused; please feel free to contribute and let me know what you think. And if you use it for something then especially let me know. It would make me very happy.

Fixing a Play Framework Java Compiler Version Warning

So I was doing some play development when compiling my code gave me the following warnings:

[warn] there were 1 feature warning(s); re-run with -feature for details
[warn] one warning found
[warn] warning: /home/robert/installed/play-2.2.1/framework/../repository/cache/com.atlassian.connect/ac-play-java_2.10/jars/ac-play-java_2.10-0.6.4.jar(com/atlassian/connect/play/java/controllers/AcController.class): major version 51 is newer than 50, the highest major version supported by this compiler.
[warn] It is recommended that the compiler be upgraded.
[warn] warning: /home/robert/installed/play-2.2.1/framework/../repository/cache/com.atlassian.connect/ac-play-java_2.10/jars/ac-play-java_2.10-0.6.4.jar(com/atlassian/connect/play/java/AC.class): major version 51 is newer than 50, the highest major version supported by this compiler.
[warn] It is recommended that the compiler be upgraded.
[warn] warning: /home/robert/installed/play-2.2.1/framework/../repository/cache/com.atlassian.connect/ac-play-java_2.10/jars/ac-play-java_2.10-0.6.4.jar(com/atlassian/connect/play/java/AcHost.class): major version 51 is newer than 50, the highest major version supported by this compiler.
[warn] It is recommended that the compiler be upgraded.
[warn] warning: /home/robert/installed/play-2.2.1/framework/../repository/cache/com.atlassian.connect/ac-play-java_2.10/jars/ac-play-java_2.10-0.6.4.jar(com/atlassian/connect/play/java/CheckValidOAuthRequest.class): major version 51 is newer than 50, the highest major version supported by this compiler.
[warn] It is recommended that the compiler be upgraded.
[warn] warning: /home/robert/installed/play-2.2.1/framework/../repository/cache/com.atlassian.connect/ac-play-java_2.10/jars/ac-play-java_2.10-0.6.4.jar(com/atlassian/connect/play/java/token/CheckValidToken.class): major version 51 is newer than 50, the highest major version supported by this compiler.
[warn] It is recommended that the compiler be upgraded.
[warn] 5 warnings

In this particular case you should notice that it says “major version 51 is newer than 50″. This means that we are using a Java 6 Compiler when we should be using a Java 7 compiler and you can confirm this by:

$ javac -version                       
javac 1.6.0_27
$

As you can see it is, in-fact, the Java 6 compiler (1.6 means Java version 6). So what do we do to fix this problem? Simple, you just make it so that a Java 7 version of javac is higher in your PATH environment variable than the one that is currently being used. You’ll know when you have it working and setup correctly when you see something like this:

$ javac -version
javac 1.7.0_40
$

For more information on how to change your path variable see this StackOverflow post.

Connecting Haskell HUnit tests to Cabal TestSuite

The Cabal logo.This is a quick guide that should explain how to connect Haskell HUnit tests to the Cabal TestSuite. I’m going to explain the simplest possible method in which you could do so and then leave it up to you to take the method further. For this post I am going to be using the following versions of Haskell software:

We are going to go through this guide in the following order:

  • Understand the data structures in Cabal TestSuite and their expected use cases.
  • Understand the data structures in Test.HUnit
  • Walk through a simple way to combine the two.

After that is done then you should be able mesh the two together easily. If you already feel that you understand the first two sections then feel free to skip straight to the final section to see how the two are joined together.

Understanding the structure of Cabal TestSuite

I am going to attempt to connect them together for the sake of running all of my test cases easily using Cabal. It also means that other people reading my project for the first time will be able to follow conventions and run my test cases with ease. The first thing that you have to understand is the structure of the Cabal TestSuite. Here is the source code for Distribution.TestSuite:

data Test
    = Test TestInstance
    | Group
        { groupName     :: String
        , concurrently  :: Bool
            -- ^ If true, then children of this group may be run in parallel.
            -- Note that this setting is not inherited by children. In
            -- particular, consider a group F with "concurrently = False" that
            -- has some children, including a group T with "concurrently =
            -- True". The children of group T may be run concurrently with each
            -- other, as long as none are run at the same time as any of the
            -- direct children of group F.
        , groupTests    :: [Test]
        }
    | ExtraOptions [OptionDescr] Test

You will notice that this data structure has three constructors. The first constructor Test expects a single test instance, the Group constructor gathers a number of TestSuite test cases under the same name and also, interestingly, gives us the option to run the test cases concurrently. The final constructor ExtraOptions lets us pass extra options to test cases. For the sake of making the integration very simple so that you can get up and running in minutes we will be ignoring everything except the Test constructor. Now you may have noticed that the Test constructor expects a TestInstance but what does that even look like. Here is the code that makes up a TestInstance:

data TestInstance = TestInstance
    { run       :: IO Progress      -- ^ Perform the test.
    , name      :: String           -- ^ A name for the test, unique within a
                                    -- test suite.
    , tags      :: [String]         -- ^ Users can select groups of tests by
                                    -- their tags.
    , options   :: [OptionDescr]    -- ^ Descriptions of the options recognized
                                    -- by this test.
    , setOption :: String -> String -> Either String TestInstance
        -- ^ Try to set the named option to the given value. Returns an error
        -- message if the option is not supported or the value could not be
        -- correctly parsed; otherwise, a 'TestInstance' with the option set to
        -- the given value is returned.
    }

So a TestInstance expects to be able to run something that will return a progress, it expects to have a name, a list of zero or more tags, a list of zero or more options and a method that allows you to set new options and get back a modified test. The name is pretty self explanatory, it lets you name the test. The list of tags to selectively run different test cases is extremely useful and large companies that choose to write a ton of test cases and have them run in automated builds (like in Bamboo) will use this feature a massive amount to be very selective in the test cases that they run. The options are partially useful too but we will be ignoring them for the sake of speed of development. Out of all of these fields the run is perhaps the most interesting. Lets take a look at the Progress data structure that is supposed to be the result of the IO action:

data Progress = Finished Result
              | Progress String (IO Progress)

data Result = Pass
            | Fail String
            | Error String
  deriving (Eq, Read, Show)

Now the Progress data structure is actually quite interesting. It has one constructor that tells us that a test case has Finished and that the Result of the test was a Pass, Fail or Error. That is the easy part to understand, the next constructor seems to say that the progress of this test case is that it is still in Progress; it also provides a message and gives an IO action to continue the progress. This is a way of reporting progress of the test cases before the test case finishes; this would be really useful if you have some very long running test cases and you wanted to get them to give you messages sooner rather than later. For the sake of our simple test cases we will only be using the Finished constructor and the Result data structure to show success.

Now you understand how the Cabal Distribution expects Test cases to be structured. You have Test cases that have TestInstances. The TestInstances are capable of being run and reporting their Progress. Eventually the Progress will be Finished and you will be able to get a result which will be reported back to you on the screen. Now we have to learn the structure of the HUnit module so that we can figure out how to put the two together.

Understanding the structure of the HUnit Module

The Test.HUnit module provides some similar structures to write HUnit test cases. Specifically it has a Test data structure that looks like this:

-- | The basic structure used to create an annotated tree of test cases.
data Test
    -- | A single, independent test case composed.
    = TestCase Assertion
    -- | A set of @Test@s sharing the same level in the hierarchy.
    | TestList [Test]
    -- | A name or description for a subtree of the @Test@s.
    | TestLabel String Test

As you can see we have a tree based data structure with a TestCase being the smallest node that can be defined. Each test case asserts something. You can also have a list of tests that make up one larger test and you can use labels to give names to other tests or groups of tests. I’m going to just assume that you know how to write HUnit test cases (as that is not the point of this document) but how do you run a test case?

You could use the performTest function but it is quite low level and would take to long to wire up. So instead we can use the runTestTT function to do the job for us with a much simpler return type:

-- | Provides the \"standard\" text-based test controller. Reporting is made to
--   standard error, and progress reports are included. For possible
--   programmatic use, the final counts are returned.
--
--   The \"TT\" in the name suggests \"Text-based reporting to the Terminal\".

runTestTT :: Test -> IO Counts
runTestTT t = do (counts', 0)                  return counts'

As you can see we just give this function our test cases and it gives us the results in the form of a Counts object that looks like this:

-- | A data structure that hold the results of tests that have been performed
-- up until this point.
data Counts = Counts { cases, tried, errors, failures :: Int }
  deriving (Eq, Show, Read)

From this Counts object we can derive the number of test cases that we tried to run as well as any failures or errors that occurred. We will use that in the next section to join the two together.

Combining HUnit and Cabal TestSuite together

Now that we know how it all works we can, quite easily, join the two together. Now because both Cabal TestSuite and HUnit define a Test data structure we need to have qualified imports and that makes the code a little harder to read but I am sure that you will see straight through it. Therefore I am just going to show you the final results and then just highlight the important sections:

module Test where

import qualified Distribution.TestSuite as TS
import qualified Test.HUnit as HU

test1 = HU.TestCase (HU.assertEqual "one equals three" 1 3)

hunitTests = HU.TestList [HU.TestLabel "Test 1" test1]

runHUnitTests :: HU.Test -> IO TS.Progress
runHUnitTests tests = do
   (HU.Counts cases tried errors failures) <- HU.runTestTT tests
   return $ if errors > 0
      then TS.Finished $ TS.Error "There were errors in the HUnit tests"
      else if failures > 0
         then TS.Finished $ TS.Fail "There were failures in the HUnit tests"
         else TS.Finished TS.Pass

tests :: IO [TS.Test]
tests = return [ TS.Test hunit ]
  where
    hunit = TS.TestInstance
        { TS.run = runHUnitTests hunitTests
        , TS.name = "HUnit Test Cases"
        , TS.tags = ["hunit"]
        , TS.options = []
        , TS.setOption = \_ _ -> Right hunit
        }

Breaking down the code segment above:

  • The first two highlights are lines 3 and 4 which show us importing the TestSuite as TS and the HUnit test classes as HU. You’ll have to remember that for the remainder of the tests.
  • The next highlight is the definition of the hunitTests which are HUnit Test classes. You can provide this wherever you want and, to make your code nicer to read, you should probably split this off into a separate test module and then import it back in.
  • The next highlight shows the function that does the majority of the work. It runs the test cases using runTestTT and then inspects the result counts to figure out what Result type to return back to the Cabal TestSuite.
  • In the next highlight you can see that we are using the runHUnitTests function to provide a runner for the TestInstance. At this point in time we have fully connected our HUnit test cases and our Cabal TestSuite and you should be able to “cabal install –enable-tests” and watch your HUnit test cases run.

That is all for this guide and I hope that it help you get your test cases up and running quickly.

Further reading: This is obviously a very simple integration of the two and you have plenty of room to improve that integration dramatically. However, I have spotted a library that seems to be in development (and not on Hackage) called cabal-test-hunit that you might want to look at for more information.

The Internals of a Quartz Clock Mechanism

A cheap $3 Quartz Clock

Introduction

Most of the world has seen and used a clock; but how many of you have actually opened up your clocks to see what is inside and how it works. In this guide inside clock mechanism I will attempt to discover as much as I can about how clocks work and how they are controlled internally; it’s going to be a bit of a journey of discovery and I hope you enjoy it as much as I will. For this video I bought a cheap clock from KMart for AUD$3 (you can see it on the right).

I must prefix this guide with the following statement: I know nothing about the construction of clocks, but I am going to attempt to reason about this one anyway. In this video I mention how the solenoid works and how it creates the clocks “tick” but I do not know if that information is accurate. Please feel free to correct me in the comments if I got it wrong.

Gear Ratios

After doing all of that work making the video I decided that it would also be a good idea to record the gear ratios that are present inside the clocks and discovered that they both have exactly the same gear ratios on every part. I am just going to write down the details for each gear and explain how it is connected to the next gear:

Gear Name Teeth on Top Half Teeth on Bottom Half Connection to Next Gear
Pinion / Motor Gear 12 Magnet Top to Top
Pinion To Seconds 48 8 Bottom to Bottom
Seconds 8 60 Top to Top
Seconds To Minutes 64 8 Bottom to Top
Minutes 60 16 Bottom to Top
Minutes To Hours 48 8 Bottom to Top
Minutes To Hours 32 NA NA – No Next Gear

Now that we know these gear ratios we can work out how long it will take each gear to make a complete revolution. We can do this because we know that the small pinion gear takes 2 seconds to make a complete revolution (because it makes half revolution per tick). Therefore we can work back the time it takes for each gear to perform a full revolution by starting with the pinion gear and working it forwards.

Gear Name Calculation Seconds per Full Rotation
Pinion / Motor Gear Given 2
Pinion to Seconds 2 * 48 / 12 8
Seconds 8 * 60 / 8 60 (One Minute)
Seconds to Minutes 60 * 64 / 8 480
Minutes 480 * 60 / 8 3600 (One Hour)
Minutes to Hours 3600 * 48 / 16 10800
Hours 10800 * 32 / 8 43200 (Twelve Hours)

Now the first thing that we should notice is that the seconds hand takes one minute to rotate once, the minutes hand takes an hour to rotate once and the hours hand takes twelve hours to rotate once: this is excellent. If that did not work correctly then this would not be a very accurate clock at all; it would be completely wrong.

The other thing that you should notice is that Minutes to Hours gear will rotate once every three hours (10800 seconds). But remember that this is also the gear that we indirectly spin by using the control on the back of the Quartz Clock Mechanism. This control gear has 16 teeth internally and it is connected to the top of the “Minutes to Hours” gear which has 48 teeth. This means that every full revolution of the control dial on the back of Quartz Clock will rotate the “Minutes to Hours” gear by one quarter. This means a quarter of three hours which is 45 minutes. That tells you exactly the granularity that you have with the control dial on the back of the device. You give it one full spin for 45 minutes worth of time. This means that it takes sixteen (12 * 60 / 45) complete revolutions of the control dial to rotate the full twelve hours around the clock. However, since you can go in both directions with the control dial, it will only take a maximum of 8 spins to set the clock to any time that you like.

The Minutes to Hours Gear with the teeth highlighted in groups of five.

I used GIMP to draw dots on photos of the gears in order to count the number of teeth per gear.

For those of you that are wondering how I counted the number of teeth on each gear then the answer is simple. I took photos of each and every gear and marked the photos such that increments of five teeth were easy to see and thus the number of teeth on the entire gear was trivial to calculate. For example, on the gear above I can see 9 groups of 5 gears and an extra three spare, making 48 teeth in total. A much simpler task than individually counting each and every tooth; much more accurate too.

Concluding Words

Hopefully you have learned something fun from this video and you now understand fully how a Quartz Clock works on the inside. Please feel free to comment below. I will happily take any comments that you may have and would be more than interested in discussing anything about Quartz Clocks.

A line based file splitter for the command line.

Have you ever wanted to extract only a certain set of lines from a file? Maybe you wanted to get everything from line 400 onwards, or just lines 25 to 50? Well I did. I call the end result ‘splitter’.

Splitter is a program designed to be used on the command line and it has been written entirely in Haskell. I have uploaded Splitter so that it is available on Hackage. You can find the source code for splitter on BitBucket, along with the source code for ‘range’ the library that I wrote in order to make the splitter program easier to deal with. The repositories are here:

But words are just words and I really need to show you some examples.

Show me an Example!

For this demo lets make a file that has twenty lines in it and, on every line, are the numbers one to twenty, like this one: Twenty Numbers.

If you were to get that file (calling it ‘twenty.txt’) then the following commands would have the following results. You could get single lines from files:

$ cat twenty.txt | splitter 3
three
$

You could get an entire range of lines from a file:

$ cat twenty.txt | splitter 5-9
five
six
seven
eight
nine
$

You could get multiple ranges from the file:

$ cat twenty.txt | splitter 10-14,2-4
two
three
four
ten
eleven
twelve
thirteen
fourteen
$

You can get ranges that are only bounded on one side:

$ cat twenty.txt | splitter -5,15-
one
two
three
four
five
fifteen
sixteen
seventeen
eighteen
nineteen
twenty
$

You can invert the selection if you chose to:

$ cat twenty.txt | splitter -i -5,15-
six
seven
eight
nine
ten
eleven
twelve
thirteen
fourteen
$

And you can specify an infinite range if you really want to (even though it would be the same as ‘cat’):

$ cat twenty.txt | splitter *
one
two
three
four
five
six
seven
eight
nine
ten
eleven
twelve
thirteen
fourteen
fifteen
sixteen
seventeen
eighteen
nineteen
twenty
$

And the are a few more options that you can choose from that you can see by running ‘splitter –help’. I would recommend that you have a play around with it yourself. It will be possible to install it on any platform that has a cabal-install installed. Which will be part of the Haskell Platform.

Concluding Words

The bottom line is that splitter makes it really easy to only extract certain lines from your files. It also has the following features so that you can:

  • Select any range that you like; whether infinite or fixed.
  • Select infinite ranges.
  • Invert your selection so that you get all of the lines that you did NOT specify.
  • You can get the line numbers printed out with the lines in the file.
  • Lines are printed out when they are ready. Meaning that you can use splitter on a logfile in the same way that you can use ‘tail -f’.

I have tried to make it a highly useful and focussed tool to get certain lines from files using an easy to understand format to specify which lines that you want. For more detailed information you should check out the README file on BitBucket. It is perhaps the most comprehensive and up to date resource on the way to use the splitter tool.

Extra: Range code huh? That sounds useful.

While I was writing this I did indeed look around for Range libraries that would meet my criteria. I discovered the following:

  • ranges
    A nice looking package that has been marked as Obsolete by the Author. I did not want to have to be stuck on an obsolete version of code that would not be updated. Also, this library cannot handle infinite ranges.
  • Ranged-set
    T
    his is a nice library and it makes good use of Haskell classes but it does not support infinite ranges either and thus was not suitable for this project

So, getting excited and wanting to start from scratch, I wrote my own library called: range. That I have now placed on Hackage. Please feel free to use it for your own purposes and I will happily accept pull requests on that work.

Solving Minesweeper with Matrices

What is your motivation for writing this?

Note: skip to the next section if you don’t care about the back-story and want to get straight to the actual algorithm.

Back in 2008 I was starting Computer Science at UNSW. I was actually enrolled in the course that became those famous YouTube video lectures on Computer Science by Richard Buckland. I was also enrolled in your standard first year Maths course at the time and we were just learning Matrix mathematics. While in the computing lectures and in the grounds and basements around campus I had a friend that loved to play Minesweeper and boy were they fast. But as I watched them play I came to realise that it really was a simple game and probably something that would be better suited to a computer solving. And then, as I wrote out a simple game of minesweeper it hit me, you could solve Minesweeper with matrices  I then proceeded to write program that did exactly that, it solved minesweeper as best as it could without probabilities.

Fast forward to just last month, just before Christmas, when I checked Reddit and saw the following blog post get released: http://luckytoilet.wordpress.com/2012/12/23/2125/

It was a pretty cool blog post and it explained a method of solving minesweeper and how you would go about doing that. I commend the author on writing it. However, one thing bugged me, nobody seemed to realise that you can actually solve Minesweeper by using Matrices (and one special lemma specific to minesweeper). So I made a comment to that affect on Reddit and I gained some interest from people that wanted to know how to do that and how it was possible. So I have decided to explain this method fully and provide a working implementation. It was a fair bit of work but I hope that you enjoy the end results.

Just as a side note: I want you to know that I am not unique in finding this method of solving Minesweeper. Here is a website of somebody that discovered it two years after I did. And I am sure that there are people that worked that out before we did again. I believe that Matrices are just the natural way to solve this kind of problem.

Quick Overview

This blog post is going to cover:

  • A simple example of how this method works and can be used to find solutions to Minesweeper configurations.
  • A robust and reasonably efficient general algorithm that explains how to apply this in the real world.
  • A brief description of my implementation of this method which is available on BitBucket: http://bitbucket.org/robertmassaioli/minesweeper-and-matricies/overview
  • Please note that I will try and provide code links, where possible, so that you can follow along in the code. If you are like me then you enjoy reading code more because it is more precise.

Prerequisites

You will need to have the following skills to read this blog post:

  • Linear Algebra Knowledge that includes Matrices. If you don’t know what matrices are then go lean about them, they are very useful tools in a programmers toolkit and you certainly need them for Video Game Development. Really go learn about it; it will take time but it is worth it.
  • How to play Minesweeper. I don’t explain the general rules of minesweeper, if you want to know how to play then go read the rules or, better yet, go play a game before reading this post. You can play Minesweeper on Windows, Linux and OSX; there are ports for every OS.

To read the code you will also need to understand C++; the coding could have been better, sorry. On the plus side, your C++ reading comprehension will improve.

The General Idea (aka How it works)

When dealing with a new problem it helps to first start with a simple example. You use a simple example because it is easier to conceptualise. Using the simple example you then develop a rigorous model for solving the problem in general. Once you have that model you then apply it to more complicated scenarios and problems and you discover, to your pleasure, that you did it. That is exactly the process that we are going to go through here.

A Simple Example

Here is a very small minesweeper configuration and we will be using this as our simple example:

A simple minesweeper example.

A simple example of minesweeper. (Image sprites taken from kmines.)

Those of you that have played minesweeper before should be able to solve this configuration as best as you can using the intuition that you have learned from playing many games. That is good, but I want a robust math-based solution to this problem. So lets look at what this Minesweeper configuration tells us. The first thing that I note here is that we have five squares that have not been clicked yet. They are our ‘unknowns’; these squares either contain mines or they do not, there is no other alternative. So since they are our unknowns then lets label them and make them our variables. I have done that in the following image:

The unknown squares are labeled.

All of the unknown squares labeled from x1 to x5. Each of them either contains a mine or it does not.

Now for any unclicked square xi look at the square x1, lets say that if it is a mine then it has a value of 1 and if it is not then it has a value of 0. Therefore mines are ones and non-mines are zeros; simple.

Now take a look at the top right hand corner square of the previous image; it contains a 1 (from here on in we will call clicked squares that contain numbers ‘numbered squares’). That means that it is adjacent to one, and only one, mine. So first we look to see which non-clicked squares are adjacent to it and we discover that x1 and x2 are the only squares adjacent to it. Therefore we know that the number of mines in both x1 and x2 must add up to equal 1. Another way of writing that is the following:

First simple equation.

Now we can come up with similar equations for the other numbered squares on the right hand side of the simple Minesweeper example. If we do that we get the following equations:

All of the equations in a messy format.

You may not be able to see (just yet) why the previous set of equations is incredibly useful, but the key insight here is to realise that you now have a set of five linear equations with five variables. It will be even clearer if you let me add in the co-efficients and the non-clicked squares that had co-efficients of zero:

The same equations as before just written a little more clearly.

The same equations as before just written a little more clearly.

As you can see this looks exactly like it should be solved using a Matrix that is exactly what we are going to do. Here is the previous results in an augmented matrix:

The augumented matrix which we can now use to solve this grid.

At this point in time we want to get a solution to this matrix so, as usual, we Gaussian Eliminate to find a solution. The solution is on the next line but I recommend that you solve this yourself on a pen and paper if you have one handy. If you don’t then you can take my word for it and just move to the next line:

Gaussian Eliminated Augumented Matrix

On first glance at this eliminated matrix you can immediately tell that there is no unique solution to the vector x (this is where I am relying upon your prerequisite knowledge). This may mislead you into thinking that the Gaussian Elimination failed but that would be incorrect; it worked perfectly and it has given us a partial solution to the vector x. To see why you need to remember that each non-clicked square in the minesweeper grid is either a mine underneath or it is not a mine (1 or 0). Therefore each value in the vector x has the following property:

Every value x is either a 1 or a 0.

Every value x is either a 1 or a 0.

This means that the matrix above has an extra property that we do not get when the expected values of the vector x could be anything in a set of infinite numbers, like the set of integers or reals. Remember that we are in the boolean set and this will all make sense.

To understand this property lets take a look at the third row of the eliminated matrix. As you can see x3 is the only column of the matrix with a non-zero co-efficient and the row adds to give 1. Setting x3 to be 1 is the only value that makes the row work (conversely, if it last value in the row was 0 then x3 would have to be zero). This means that we can tell that x3 is a mine even though we do not know what the other squares are. It is interesting to note that we can only tell that from the Gaussian eliminated matrix; not the original matrix. So even though the elimination does not find a complete solution it still simplifies the matrix and allows us to get partial solutions. But what is the general rule to get partial solutions from eliminated matricies?

A Special Rule

Lets see a few more example rows that can help us to intuitively derive that rule:

These are some examples of some extra rows that may be possible end results after gaussian elimination.

These are some examples of some extra rows that may be possible end results after gaussian elimination.

Pretend each of the rows in the above image are unique rows taken from unique matrices (what I am trying to say is that each row above is not correlated, they are all unique). Let me deal with each row in a dot point:

  1. If we take a look at the first row you should be able to tell that x1 and x4 are both mines because that is the only way that they will equal 2.
  2. If you look at the second row you can see that both x1 and x4 must not be mines because that is the only possible solution for x1 + x4 = 0 when the only potential values for any x are ones and zeroes.
  3. The third row is interesting because it has a negative number, that means that the equation is x1 – x4 = 1. This can only be true if x1 is a mine and x4 is not. Now things start to get interesting, clearly we need some concept of a minimum and maximum bound for each equation. In this example the maximum value the equation could take is 1 and the minimum value that it could take is minus one. Since this row meets that upper bound we can solve for it.
  4. This is the same as the previous example except that it meets the lower bound. This also means that we can solve for it.

As we can see the general solution to getting more information from each row is to to work out the lower and upper bounds and see if the value on the other side of the equality is the same as one of the bounds. If it is then you know that there is only one possible configuration of mines that will allow that to occur and you can quickly rattle that off. Because of that uniqueness property you can only apply this rule to a row if it is equal to an upper or lower bound; if it does not then multiple solutions are possible and you have strayed into the area of probabilistic analysis that this blog post will not attempt to cover. This grid shows what logic you use, on a per-square basis, to partially solve the matrix:

Co-Efficient is Positive Co-Efficient is Negative
Row meets lower bound Not Mine Mine
Row meets upper bound Mine Not Mine
Row meets neither bounds Unsure Unsure

You can use this rule on any Gaussian Eliminated Minesweeper matrix to get partial solutions from rows. Just so that you can really see how that works here is a rough algorithm (and here is a link to the actual C++ code):

Set the maximum bound and minimum bound to zero
For each column in the row (not including the augmented column of course) if the number is positive add it to the maximum bound and if it is negative then add it to the minimum bound.
If the augmented column value is equal to the minimum bound then
   All of the negative numbers in that row are mines and all of the positive values in that row are not mines
else if the augmented column value is equal to the maximum bound then
   All of the negative numbers in that row are not mines and all of the positive values in that row are mines.

Finishing the Simple Example

So now lets wind back to the Gaussian Eliminated matrix. As we can see the only row that we can apply this rule to is row 3 which tells us that x3 is a mine. Therefore we can flag that square:

This is the final result of our simple minesweeper configuration.

The final result of our simple minesweeper configuration.

And that is it for our simple example, we have worked out as much as we possibly can without more information. The game is still in progress but if we want to move forward we would have to make a guess or some probability based decision that could fail. This method of solving Minesweeper only works for grids that are completely solvable without guesswork and it is my future plan to expand this method to include probabilistic analysis as well.

The Robust Algorithm

Taking what we have learned from the simple example we can create an algorithm that is a fair bit more robust:

  1. Get a list of the squares that contain numbers AND are adjacent to at-least one square that has not been clicked or flagged. (code link)
  2. For every numbered square in the list assign a unique matrix column number to that square. This is so that we can map our Matrix columns to Minesweeper squares. (code link)
  3. For every numbered square in the list create a matrix row that represents the adjacent non-clicked squares and the number they touch. Don’t forget to put zeroes in all of the matrix columns that are not adjacent. (code link)
  4. Gaussian Eliminate the Matrix. (code link)
  5. Attempt to use standard matrix reduction, and the special rule that we developed, to get a partial (or even full) solution to the the current Minesweeper configuration. Remember to tackle the matrix from the bottom row up so that you can make use of partial solutions as you go. (code link)
  6. Use the (possibly partial) solution you worked out to generate the list of clicks that should be made: flagging known mines and clicking known empty squares. Leave everything else alone and wait for more information. (code link)
  7. Keep running all of the previous steps in a loop until you either cannot make any moves (meaning that you cannot get further without guessing) or until the game is finished and won. (code link)

And that is all that there is to it. Writing those steps can get a little complicated at times but totally manageable with a decent working knowledge of Matrix mathematics. I have not explained those steps in really great detail because if you want that information then you have now got to the point where you should really check out my code and have a run and read.

The Implementation

All of this talk would mean nothing if I was not able to implement it and show you some working code. Therefore, I have implemented this algorithm from scratch and have provided the source code to everybody under the MIT license. If you use this code anywhere or use the idea, then I would really appreciate it if you mentioned my name or gave me attribution somehow; really it would make my day.

Go get the code from BitBucket: http://bitbucket.org/robertmassaioli/minesweeper-and-matricies/overview (By the way, while we are here, did I mention that I love pull requests)

How do I compile your code? Read the README.markdown file that is in the root directory of the project. It will always have up to date details.

What design choices did you make?

Haha, design choices, that’s a good one. This code is not the most beautiful code that I have ever written. I wrote it all myself to avoid spurious dependencies in the hope of easy cross platform compilation. I have not even used RAII principles in this code and frankly that makes the delete’s sprinkled all over the code quite ugly. If I was writing this without a care in the world for dependencies then I would have used Boost and gained a large amount of nice looking code for free. Also the solver looks like a bit of a monster method at the moment, sorry, it should be re-factored.

How fast is it?

Short answer: very fast and much faster than it needs to be to solve a single game of minesweeper. The longer answer is that his code was written in C++ and it is lightning fast even though it only uses a single core to do the processing and thus does no parallelism whatsoever. It is fast because working with Matrices is quick. I gain speed just by the fact that I used efficient mathematical constructs. To give you an example, it takes less than a minute and thirty seconds to play one hundred thousand minesweeper games on a single core on my computer (I have a machine that contains an “Intel(R) Core(TM) i7-2670QM CPU @ 2.20GHz”). I would expect you to see similar speed results on your own machine.

Results of playing many Games

My minesweeper implementation plays a great many games but here are the results of it attempting to play 100000 games of Beginner, Intermediate and Expert minesweeper. Please keep in mind that there are three states that the game can end up in:

  • The Win state: we were able to completely solve the grid without guessing.
  • The Progress state: we got to a point in the game where the only move we could make would have to be a guess. As a result we stopped making moves and left the game partially completed and still ‘in progress’.
  • The Lost state: this happens when you click on a mine. That should not be possible using our method and, if you see that you can consider it a bug and please report it to me.

Beginner

A ‘Beginner’ grid is 8×8 or 9×9 with only 10 mines.  have chosen the easier of the two and gone for the 9×9 grid:

WINs: 74090 (74.09%)
PROGRESSes 25910 (25.91%)
ERRORS (losses) 0
./localbuild/src/mnm 8.68s user 0.00s system 99% cpu 8.697 total

As you can see a beginner grid is pretty easy, it only took ~9 seconds for my computer to do play 100000 games and it won ~74% of the time.

Intermediate

An ‘Intermediate’ grid is 16×16 squares with 40 mines and this is how my run performed:

WINs: 43432 (43.432%)
PROGRESSes 56568 (56.568%)
ERRORS (losses) 0
./localbuild/src/mnm 43.56s user 0.01s system 99% cpu 43.627 total

In an intermediate game there is less chance that you can win without guessing. I have run this a number of times and you have about a 45% chance that you will be given an intermediate grid that you can win without guessing. That makes the intermediate games a fair bit harder.

Expert

An ‘Expert’ grid is 30×16 squares with 99 mines and this is how this current run performed:

WINs: 1707 (1.707%)
PROGRESSes 98293 (98.293%)
ERRORS (losses) 0
./localbuild/src/mnm 83.87s user 0.00s system 99% cpu 1:23.98 total

As you can see from these combined results the solver is very fast and the difficulty levels of Microsoft’s minesweeper are appropriately chosen; you have a very small chance of getting a grid in Expert mode that lets you win without making at-least one guess.

Next Steps

There are a few extra things that I would like to do to the codebase if I had some time:

  • I would make a probabilistic solver to attempt to solve the majority of the games instead of leaving them in the ‘Progress’ state.
  • I would make the code multi-threaded where I could. Specifically it would be good to run multiple test games in parallel because they are a great example of a ‘painfully parallel’ problem.
  • The code should have better test cases. Currently only the matrix code is tested reasonably well. The game and the solver should have more test cases too.

So just to wrap it up quickly, this is how you solve Minesweeper with Matrices. Please feel free to ask any questions you like or make suggestions below.

Google Calendar Subtle Duration Bug

Sometimes it is the most subtle and simple bugs that can really get under your skin and annoy you like nothing else. Recently I was dealing with data that I get sync from Google Calendear and I used RFC2445 and RFC5545 to get the specification for a ‘Duration’. Durations are important because according to the spec a VEVENT must have either a DTEND or a DURATION. Therefore I need to be able to parse durations when dealing with data that I get back from Google. The RFC’s define the duration as:

       dur-value  = (["+"] / "-") "P" (dur-date / dur-time / dur-week)

       dur-date   = dur-day [dur-time]
       dur-time   = "T" (dur-hour / dur-minute / dur-second)
       dur-week   = 1*DIGIT "W"
       dur-hour   = 1*DIGIT "H" [dur-minute]
       dur-minute = 1*DIGIT "M" [dur-second]
       dur-second = 1*DIGIT "S"
       dur-day    = 1*DIGIT "D"

But Google Calendar does not follow that pattern…Google Calendar events have a subtle difference:

       dur-value  = (["+"] / "-") "P" (dur-date / dur-time / dur-week)

       dur-date   = dur-day "T" [dur-time]
       dur-time   = (dur-hour / dur-minute / dur-second)
       dur-week   = 1*DIGIT "W"
       dur-hour   = 1*DIGIT "H" [dur-minute]
       dur-minute = 1*DIGIT "M" [dur-second]
       dur-second = 1*DIGIT "S"
       dur-day    = 1*DIGIT "D"

You probably did not even notice it but the ‘T’ character has moved. This caused my parser (generated with JavaCC) to fail and was an annoying problem to debug. It has also forced me to write many annoying test cases to make sure that I can easily ascertain if Google is doing the right thing in the future.

Just so that you know, this means that it generates incorrect periods. So Google Calendar generates a period that looks like this “P300S” whereas it should generate a valid period like this “PT300S”.

Original LotR (Lord of the Rings) Funny Gifs

I’m taking a break from my usual programming posts to instead save an important part of internet history in an easy to discover place: this blog. If you are here then you probably know about the “One does not simply X” meme. But where did it all begin? I do not know who the original authors are but I do remember that sometime around 2008 (IIRC) I came across four gifs in a row that made me rofl. I must have watched them a million times all in this particular order that I liked. I never found out who the authors are but they are completely awesome and it is my hope that they will contact me or claim ownership eventually; the internet would like to thank them. The order that I like watching them in are:

  • One does not simply walk into Mordor
  • What about a Catapult (Part 1)
  • What about a Catapult (Part 2)
  • LotR: The Short Version

And without any more talking, here they are, in that order (If you want to download them all then I have a Zip file in Google Drive that you can download):

(Click on any of the images to open them in a new tab/window and play from the start)

One does not simply walk into Mordor

What about a Catapult (Part 1):

What about a Catapult (Part 2):

LotR: The Short Version

And that is all of them. I hope you enjoyed this post. Take the reference to the author on the last gif with a grain of salt. When I saw the original I do not remember it having any attribution so I will have to verify that they are in-fact the authors.

LibGDX, Blender and G3D Exporting

LibGDX is working on exporting your work from Blender or SoftImage (see the model-loaders) straight into a file format that it can handle; the file format that it has coined is G3D. Now, as far as I know the G3D file format has no specification, if you want to understand how the file format works then there is no better way than to just look straight at the implementation in the libgdx/extensions/model-loaders code (we check out this repository in step one).

This blog post explains a nice an easy way to install the Blender G3DT exporter on an OSX or Linux machine.

  1. The first step is to check out the libgdx source code which is a lovely git repository (thanks go out to the LibGDX team that recently changed it over from SVN to Git, it was a good move):
    git clone git://github.com/libgdx/libgdx.git
  2. When the source code is checked out you will need to symlink the files into your blender addons directory.
    On Mac OSX:

    cd /path/to/libgdx-read-only
    ln -s extensions/model-loaders/model-loaders/doc/blender/io_scene_g3dt /Applications/blender.app/Contents/MacOS/$(/Applications/blender.app/Contents/MacOS/blender --version | grep "^Blender" | cut -d\  -f2)/scripts/addons

    On Linux:

    mkdir -p ~/.blender/$(blender --version | grep "^Blender" | cut -f2 -d\  )/scripts/addons
    cd /path/to/libgdx-read-only
    ln -s extensions/model-loaders/model-loaders/doc/blender/io_scene_g3dt ~/.blender/$(blender --version | grep "^Blender" | cut -f2 -d\  )/scripts/addons

    On Windows: Windows has the equivalent of Symlinks since Windows Vista. You can use the mklink command instead of the ln command to link the ‘extensions/model-loaders/model-loaders/doc/blender/io_scene_g3dt’ directory straight to your blender addons directory. That will work but unfortunately I do not have any instructions that I can guarantee will work for that; but you are pretty clever. You should be able to figure out how to use the mklink command.

  3. Now open Blender and navigate to File > User Preferences (Ctrl+Alt+U). Click on the Import-Export in the left hand side panel and then enable the G3DT Plugin by ticking the Check box next to the Import-Export: G3DT Exporter box.

    Click this simple box to activate the plugin.

    (Click on this image to get a large version of the button that you are supposed to press to activate the G3DT Exporter)

And now you are done. You can now export your blender files to the G3DT format for use with LibGDX. Not only that, but if you spot any problems with the G3DT Exporter and you manage to solve them then you can easily commit you code straight back to the larger project. You could contribute to libgdx just like that.

Friends don’t let friends write Javascript in Velocity templates.

The Problem

Very recently I was writing an Atlassian plugin for JIRA. I was trying to add some Javascript directly to a Velocity template instead of including it from its own file (I know; naughty me). But the problem that I was seeing is that trying to use the JQuery ajax function that Atlassian wraps in AUI (Atlassian User Interface) was coming out incorrectly. In-fact this:

AJS.$.ajax({

Was being converted from the template into HTML to look like like this:

AJS..ajax({

And obviously that is not even valid Javascript and Google Chrome spat out some parsing errors in the console.

The Cause

In hindsight the problem in obvious. In velocity templates the ‘$’ symbol is very special: it is what velocity uses to refer to variables. Velocity is used to seeing ‘$object.getSomeMethod’ so when it saw ‘$.’ it just said I have no object that matches ” (empty string) and therefore I will render ‘$.’ as the empty string. Which resulted in us not getting our dollar symbol back and Javascript errors popping up.

The Solution

The best solution is to simply not write Javascript in your templates (please) doing that is just not nice and you should be encapsulating your CSS and Javascript into separate resource files by default. If you are not then please start doing that now. Look at the documentation and examples on how to do that in Atlassian Plugins.

However, I know that there are going to be some of you in the crowd that are going to say “But what if I really really really do want to write Javascript in my template?” Well for those people I give you this post from StackOverflow:

In Velocity 1.7b1 new syntax #[[this is included in output but not parsed]]# was introduced:
#[[          
    $(document).ready(function() {
         ...     
    }); 
]]#

I hope this helps you fix any problems you may have been having and also to have convinced you to stop using Javascript in Velocity templates.


Follow

Get every new post delivered to your Inbox.

Join 176 other followers