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 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:

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 x_i look at the square x₁, 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 x₁ and x₂ are the only squares adjacent to it. Therefore we know that the number of mines in both x₁ and x₂ must add up to equal 1. Another way of writing that is the following:

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:

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.

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:

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:

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.

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 x₃ is the only column of the matrix with a non-zero co-efficient and the row adds to give 1. Setting x₃ to be 1 is the only value that makes the row work (conversely, if it last value in the row was 0 then x₃ would have to be zero). This means that we can tell that x₃ 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.

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 x₁ and x₄ 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 x₁ and x₄ must not be mines because that is the only possible solution for x₁ + x₄ = 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 x₁ – x₄ = 1. This can only be true if x₁ is a mine and x₄ 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 x₃ is a mine. Therefore we can flag that square:

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 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.

Installing Ubuntu Linux on the MSI GT780DX

Very recently I bought the MSI GT780DX Laptop from PC Case Gear as I was very impressed by its specs. Out of the box it was a beautiful machine and came with windows pre-installed. Pretty stock standard really but I wanted to dual boot linux on it; more specifically Ubuntu Linux. For those of you who do not know what Ubuntu Linux is I suggest that you take a look because it is a complete replacement for Windows and it is completely free (and I don’t mean “free but there is…”. No. I mean free and with no catches.) Please, just click the Ubuntu Linux post above if you have not done so and have a read; at the very least you will not understand why I am doing what I am doing until you do.

For this installation I used a Live USB which contained Ubuntu 10.4 which I immediately upgraded after the install.

This post does not focus on getting a full install working. It just focuses on the extras that I had to go through in the install process to make sure that it worked correctly. So these are the issues that I came across, in order, in the install process:

• Backup Windows Completely first. All I will say is that when you boot into windows for the first time there will be a nifty tool there to make a complete snapshot of the entire OS. Use it and move it to another drive. (I will not talk about this point further; it should just be something you do naturally anyway.)
• If you have a DXR as opposed to a DX (like me) then, according to various forums, you need to get rid of the RAID0 setup before you can install Ubuntu. (I will not talk about this point further; you will need to find this information elsewhere. It is out there. And if you bought a computer with RAID0 on it then you are supposed to know what you are doing anyway.)
• When you put in the boot CD/USB you cannot just hit “Install” straight away; first you must blacklist the nouveau kernel module.
• Choose an appropriate partition size for Windows; I gave Windows 400GB. (I will not talk about this further; go here to learn more about dual booting Windows and Ubuntu)
• Whenever I have mouse issues I use the special: sudo modprobe -r psmouse && sudo modprome psmouse

Blacklisting the Nouveau Driver

NVidia’s drivers are not open source; Nouveau is an open source project that attempts to rectify that. However, their support for newer graphics cards is somewhat flaky, especially in older installation USB’s. Therefore you will need to disable the Nouveau drivers before you continue with the install. The instructions are summed up well in this quote so start the Live USB and then when you get to the “Install Options Screen” just read this:

Righty-o, confirmed here. Something’s amiss with the nouveau module. Blacklisting it will let you boot, using fallback framebuffer instead. When booting, hit TAB to edit the boot parameters. Add this to the end of the line, but before the two dashes (“–”):

nouveau.blacklist=1

Then boot. You may see the screen go messy while you write because the line gets two wide to fit, but don’t worry, all is good. You may see a message complaining that nouveau does not have an option, “blacklist” or something like that, but it does, and it does work, and I think maybe that message should’ve read, “there’s no nouveau module to do ‘blacklist’ on” as the module isn’t loaded, and that’s probably what the complaint it about. It’s also what we want to happen

And that is all that there is to it. Once you have blacklisted the driver you should be able to install the rest of Ubuntu with no issues. When you finally have a working install make sure that you install nvidia-current by opening a terminal and:

sudo apt-get install nvidia-current

You will need the latest drivers to get your computer to work at its maximum potential.

Mouse Problems

Sometimes the mouse on this Laptop stops working; even if you press and re-press the disable mouse button. To get it to work again just restart the mouse kernel module:

sudo modprobe -r psmouse && sudo modprobe psmouse

After that you should notice your mouse become active again.

Conclusion

Ubuntu is an awesome operating system and it is pretty easy to install on this MSI Laptop. If you have any questions on what I did to get Ubuntu to dual boot with windows then please add it to the comments.

Installing keepass2 on Ubuntu Linux 11.10 to work in Google Chrome via KeepassHTTP

Keepass2 is a Password Manager for Linux (and other operating systems) that is awesome and can be made to autofill your passwords in your browser and still keep them all safe. All this functionality at your fingertips and you only need to remember one simple (and single) password. If you really want to see the full list of features for keepass then you can take a look at their list of features.

Keep in mind that this tutorial is performed on the following version of Ubuntu:

% cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=11.10
DISTRIB_CODENAME=oneiric
DISTRIB_DESCRIPTION="Ubuntu 11.10"

We also are trying to install the following software:

• Google Chrome (This is expected to be installed already)
• ChromeIPass (Open up Google Chrome and install that now)
• keepass2 (Instructions Provided)
• keepasshttp (Instructions Provided)

What should installation be like?

Being an Ubuntu user you would think that you could just open up a terminal and type in something like this to install keypass2 and keepasshttp:

 sudo apt-get install keepass2
 wget https://passifox.appspot.com/KeePassHttp.plgx
 sudo mv KeePassHttp.plgx /usr/lib/keepass2

But unfortunately that does not work. The plugin even fails to load.

How to actually install it

Installing keepass2 is actually markedly more complicated then that. This is the full set of instructions that you have to perform:

 sudo apt-add-repository ppa:jtaylor/keepass
 sudo apt-get update
 sudo apt-get install keepass2 mono-complete
 git clone https://github.com/pfn/keepasshttp.git /tmp/keepasshttp
 cd /tmp/keepasshttp/KeePassHttp
 sudo cp KeePassHttp.dll Newtonsoft.Json.dll /usr/lib/keepass2

And now it works exactly like it should. The important extras required to get it to work are, in order:

• The addition of the jtaylor/keepass Personal Package Archive (PPA).
• The extra installation of the mono-complete package.
• The checkout of the git repository to get the KeePassHttp.dll and Newtonsoft.Json.dll library files instead of just using the plgx package file.

We will explain the requirements of those three extra steps in the following section if you really care. But at this point in time you should have keepass2 installed.

Why it is not currently like it should be?

Lets answer each of the three extra steps in a one by one fashion.

Why did we need to install the jtaylor/keepass PPA instead of the one provided and packaged by ubuntu?

Essentially the version of keepass2 was too low to be compatible with all of the latest bug fixes in keepasshttp. As you can see Ubuntu will be getting keepass version 2.18 in Precise Pangolin but in Oneric they only have version 2.16. But if you look here the latest version of keepasshttp requires version 2.17 of keepass as a minimum. That is why we installed a newer version of keepass from a PPA. This means that when you upgrade to Pangolin you can remove this PPA from your Software Sources.

Why did we need to install the mono-complete package?

If you do not install the mono-complete package and attempt to sync Google Chrome with keepass2 through ChromeIPass and keepasshttp then the Newtonsoft.Json.dll will crash with a nasty looking stacktrace. The way to solve this is to get all of the mono libraries.

Why did we need to put the .dll files in the keepass2 directory instead of the .plgx file for keepasshttp to start working?

Because putting the plgx file in the directory did not work for me and putting the .dll files in did. And you can take a look at what this guys says here for more information.

ClassNotFoundException when running Simple XML

The Problem

A few days ago I ran into a problem while using Simple XML in my Android codebase. Since Simple takes about 2-3 seconds to load my level files I could not perform that activity on the main UI thread; as per android design guidelines. So I threw the loading of my level into an AsyncTask as you are supposed to and thought that everything was just perfect. However, I quickly encountered a problem whereby all of my data would be written out correctly to an XML file but when I tried to read it back in I was given a ClassNotFoundException. The error looked something like this:

12-25 12:21:44.565: W/System.err(404): java.lang.ClassNotFoundException: MyCoolJavaObject in loader dalvik.system.PathClassLoader@4001b500

…more messages here…

12-25 12:21:44.575: W/System.err(404):  at org.simpleframework.xml.strategy.Loader.load(Loader.java:50)

…more messages here…

The Solution (Solving The Problem)

Whenever you push a polymorphic type into an XML file Simple XML also adds an attribute called ‘class’ and it is filled with the absolute package path of the object that was just serialised. Like this for example:

<fruit class="com.fruitseller.Apple" seeds="4"> 
<fruit class="com.fruitseller.Bananna"> 
    <parentTree id="4984" /> 
    <energyContent>98</energyContent> 
</fruit>

As you can see in this example, when Simple reads in these classes again it knows which constructors to use by looking up those classes in the hierarchy. Therefore, if that look-up process fails you are going to get a ClassNotFoundExeption, just like the one that I received above.

The ClassPathLoader is what is in charge of finding those classes and that is what needed to be fixed. As it turns out the new thread that the AsyncTask was running on did not have the same class path loader as the one that the UI thread of my app was using. Therefore, all I needed to do was set the class path loader in that AsyncTask before I ran any simple xml read or write functions. To do so I grabbed the one from my Application class, like this:

// The fix is this two lines
ClassLoader thisClassLoader = MyApplication.class.getClassLoader();
Thread.currentThread().setContextClassLoader(thisClassLoader);

// This Persister code
Serializer serial = new Persister();
...more simple code...

As you can see the fix ended up being a meager two line fix that can probably be condensed into one line. And that solved my problem completely. I hope that this helps you and if it does not feel free to ask questions in the comments.

Fixing the PhysX “Failed To Install” Error

Did your version of PhysX fail to install or have you tried to play a game and it errors out and closes due to an error that could be related to missing PhysX libraries? Maybe Wise Installer is claiming that you are missing some files (extensions .wsi / .msi)? Then you have come to the right place and I am going to give you some instructions that should hopefully solve your problem.

The Problem

Recently I had a moment of Nostalgia and bought Overlord II from the Steam store but to my dismay, upon startup it encountered an error and aborted the program. This was the error message that I encountered:

Microsoft Virtual C++ Runtime Library

Assertion failed!!

Program: C:\Overlord II\Overlord2.exe
File: ..\FxSDK\Src\FxName.cpp
Line: 461

Expression FxFalse != removeResult

For information on how your programa can cause an assertion
failure, see the Visual C++ documentation on asserts

(Press Retry do debug the application – JIT must be enabled)

I had no idea what could be causing that problem so I looked it up online and discovered people that said it was due to a PhysX installation error; in the end it turns out that was the case but it took some clever steps to make sure that I properly fixed the problem. Here is the quick guide to solving the problem in a few steps as possible.

The Solution

This problem is usually caused by PhysX trying to get rid of the last installation before it upgrades and failing to do so because it was only a partial install. So to fix that first we have to reinstall/fix the version that was supposed to install properly and then move on to installing the version that you want to install. As one of the viewers of this page put it:

It’s a one step backwards, two steps forwards kinda situation.

Without any further explanation lets just jump straight into the steps:

Important: These steps apply to Windows 7 though they may work in Windows Vista.

Step 1: Discover what version of PhysX installed to your machine or what version your machine thinks it has installed.

To do this press the start button and type in “Programs and Features” and run it:

Then once that is open wait for the list of installed items to populate (it may take some time or be instant depending on your computer) and then scroll down to “Nvidia PhysX”. The version number that is supposed to be installed will be present on the far right (click on the image to enlarge it):

So as you can see my currently installed version number is “9.11.1107″ but yours will be different and that is the one you want because it will be important in the next section.

Step 2: Download the version of PhysX that should have installed correctly but did not.

Important: If you want an easy way to do this just use this simple little form I wrote: http://jsfiddle.net/robertmassaioli/k4y56/7/embedded/result/

This paragraph until Step 3 is now old and is only useful if the link breaks and you need to generate the url yourself. The correct way of doing this is to go to:

http://www.nvidia.com/object/physx-<version_number>-driver.html

Where you are supposed to replace <version_number> with the correct version that you discovered in the step above and then navigate to that url in your browser.

Note: If you did not manage to find the correct download (you get ‘File Not Found’ errors) then please google “physx <version_number>” to find the correct installer / executable for you to run in the next step.

Step 3: Fix the initial install of the program.

Run the program that you downloaded and you should get a screen that asks you to Modify, Repair or Remove the program. You want to select ‘Modify’ and click ‘Next’. If you do not get the screen shown below then you have downloaded the incorrect installer in step 2:

Once you have done that just keep selecting the next option and it should clean up your entire install and run successfully. If it does not then yet another problem has occurred and this guide may not be able to help you further. You may have some luck with an alternative solution that David Orders has suggested in the comments section.

Step 4: Install the latest version of PhysX

Now that you have fixed the installation of PhysX you are free to download and install the latest version of PhysX onto your machine. Go here to do so: http://www.nvidia.com/object/physx_system_software.html

Conclusion

That is all that there is to it. You should now have PhysX working correctly on your machine and be playing games and anything that you want in no time. If you continue to have problems then mention them in the comments to help other people that are trying to solve the same problem. I hope this helps.

A Tribute to CSE and Uni

Breif History

Back in my first year of University I was enrolled in a course called COMP1917. It was an excellent course taught by Richard Buckland and I enjoyed it very much. It was also the exact course in which they taped the famous YouTube video lectures; I look back on those lectures with pride. The purpose of this course was to introduce students to computer science and teach them about the fundamentals that they simply must know. To that end we were taught C as our primary language (a common choice) but we were also given an emulator for an imaginary microprocessor called a “4917 chip” which I will call a “4917″ for short. This blog post is going to focus on that chip.

The imaginary 4917 was a tiny device. It had sixteen nibble sized memory locations and sixteen different instructions. All instructions were either one or two nibbles in size. I hope you notice that this entire machine worked in nibble sized chunks. It also had only two working registers called  R0 and R1; it also technically had a program counter that you manipulate with instructions 13-15. The instruction set of this device is here:

Format:
Instruction in decimal => What the instruction does

One Byte Instructions:

0 => Halt Program
1 => R0 = R0 + R1
2 => R0 = R0 – R1
3 => R0++
4 => R1++
5 => R0- -
6 => R1- -
7 => Ring Bell (Nothing really [Side Effect])

Two Byte Instructions:
8 x => Print x to the output device; maybe a screen but it did not matter because this device is imaginary.
9 x => Load value at location x into R0
10 x => Load value at location x into R1
11 x => Store value in R0 into location x
12 x => Store value in R1 into location x
13 x => Goto x
14 x => If R0 == 0 Then Goto x
15 x => If R0 != 0 Then Goto x

It is actually quite a nice little instruction set. You can even write a quine in this 4917 machine.

The Problem

But what am I even getting at I hear you ask? Well it goes like this, Richard Buckland posed a question to us that said:

I have a bonus question for you. For every different length program, I want you to create/write a program that will print out the most characters that you possibly can to the screen and still terminate. That is you cannot write a program like “8 0 13 0″ which will print ’0′ forever. That program is incorrect because it will never terminate.

And with that the battle was on, if you wrote a program in 4917 that printed out the most characters for that program length, that anybody had found yet, then you gained one ‘brownie point’. Brownie points are tallied up at the end of the session and the person with the most wins. (Spoiler Alert: I had the most brownie points at the end of that session; by far.) You should also know that the length of a program is calculated as 16 – NUM_TRAILING_ZEROES. That means that you must count all of the memory spaces that you actually needed to write to.

Those of you that are clever would have realised that Richard was teaching the class a valuable lesson; and also, quietly, having a laugh at our expense – but I mean that only in the best way, right now I am laughing right there with him. The problem with this problem, as it were, is that you cannot write a fast program to find the best program for you. Any algorithm that attempted to do so would need to ensure that  it eventually terminated; and to do that you need to solve the Halting Problem. Haha Richard, very funny, try and get the first years to solve an impossible problem so that they learn the value of computing theory; actually it was quite a good move in retrospect. It teaches a good respect of theory.

Hovewer, we are also Engineers, and as with most problems this one can be partially solved using brute force methods. You can write your own emulator, count the number of characters that get printed to the screen, and include a timeout for programs that go for too long and are thus deemed “probably infinite”. And that is what this post is really about; me writing a brute force solver to this problem on a PicMicro device for sentimental value.

Past Results and My New Sentimental Solution

At the time of the course I wrote a brute force solver, using some code (an emulator) written by Brett Phillips, and ran it on my laptop (RIP Dell XPS M1710) and on increasingly large program sizes to find the best finite program. These were my results:

program_size: program bytecode => number of printed digits
4: 3 8 10 15 => 32
5: 4 1 8 10 15 => 62
6: 4 8 8 13 2 15 => 93
7: 1 8 10 14 4 1 15 => 172
8: 1 8 10 14 4 2 4 15 => 482
9: 1 3 8 10 15 1 4 2 15 => 512
10: 1 8 8 15 6 8 13 2 5 15 => 1173
11: 1 3 8 10 8 10 15 1 4 2 15 => 1024

And that earned me 8 brownie points in one hit. I was never able to get a solution for the higher values because it would have required me to leave my laptop on for around a week or two for a program of size 12 and much more for the others; class and the exams would have passed before I had an answer.

However, in recent days, for nostalgic purposes, I have engaged the problem again and I am pleased to say that I have written a number of implementations but the ‘best’ one of all would have to the the Microchip PIC16F688 version which I will display for you now via youtube:

This is awesome and makes me very happy. You can find the code for this device on Github. It should be pretty easy to recreate and pretty cheap to buy the parts for.

Conclusion

I enjoyed my time at University very much and I was very happy to have been there. I loved every minute of it and met amazing people and this little tribute is my offering to my time there. To have something to remember it by. A big thanks to Richard for the awesome course and 4917 problem, and also to all of my peers that made it an awesome time. I hope you enjoy this little project and my story.