To fill in that spreadsheet you only need two pieces of information:
How much energy your home consumes per day (in kWh).
How much you drive per day (in km)
With that information you can work out how many solar panels you would need on your roof and how many Tesla Powerwalls you would need to store all of the energy that they generate. I think that you should give it a shot.
However, my conclusion is this: most people that drive close to or under the average for Australian drivers (<= 43km per day) will find that they don’t need significantly bigger Solar Systems and power packs to cover the costs of their Tesla car. And every single home owner on the planet should be able to get enough Solar panels and Powerwalls to cover their household and car energy usage. Good news!
Note: Currently there is no cost analysis here of how much those components will cost. But I will add that companies like Solar City and Sun Edison make getting solar panels a breeze. Also the Gigafactories being build in America right now should dramatically bring down the price of Solar Panels and Powerwalls.
Hopefully this helps somebody and, if you have any questions then please let me know in the comments.
Note: All submissions have everything but the sound of your voice stripped from them (like filename), ensuring that you remain anonymous except for your voice. And even then, your voice will be in a database of hundreds or more of other voices.
Why are you collecting these audio samples?
I am collecting this data for the purpose of aiding some speech recognition work that I am doing and thought that, while I was at it, I may as well make a big collection of audio samples than anybody can use for any purpose. I hope that you submit to the audio database.
At 100 samples collected I will release the first version of this database for public consumption, at the moment I only have 6 samples collected so we could use all of the help that we could get! Please contribute. Your voice may be what helps us to bring speech recognition forwards.
How big could this get?
There are roughly 335 million English speakers on the planet. I think it is completely reasonable to hope that you will be one of the awesome english speakers that will submit to the database. With your help we could get submissions in the thousands. I hope to eventually fill this database with 100,000 samples.
In the past I have spoken about the Internals of a Quartz Clock Mechanism explaining how it works and how it all comes together with a handy video. However, even though I explained how the solenoid spins the pinion gear I did not explain very precisely how you might go about manipulating a Quartz Clock Mechanism.
In this blog post I present you with another video that explains “How to control a Quartz Clock Mechanism”. In the video I explain and show how to connect the clock to a custom electric circuit that you construct and I then provide a method to speed up and slow down a regular quartz clock. I hope you enjoy the video, if you like the video then please let me know in the comments or share it around:
In the video I run through a number of concepts and I want to provide you the links to those concepts here in one convenient location:
Hopefully you can use these resources to control you own Quartz Clock Mechanisms or other electronic circuits.
I have attempted to explain clearly how to control a Quartz Clock Mechanism in the hope that other people might follow suit. With any luck you can now go out there and do something really interesting with Quartz Clock Mechanisms. If you do then please let me know about it. If you have any comments at all, or would like to see me do something else that is interesting with Quartz Clock Mechanisms then please let me know!
Very recently I was writing a shared service in Haskell and we realised that we would need to integrate with an email service provider. After a little bit of research I concluded that Mailgun was a great service for developers to send their emails so I looked for Mailgun integration libraries that looked like they were being groomed to be “the” Mailgun library for Haskell and I was disappointed to find that the existing libraries did not seem to be very comprehensive or did not make use of type safety.
It supports simple email sending just like the existing libraries.
The type system is stricter, leaving less room for incorrect usage of the API. Giving you the assurance that you will be sending emails correctly.
There is a backlog of issues that has been roadmapped such that the library will have full Mailgun API support. It just needs time to develop it.
The support for the various parts of the API is being implimented and released incrementally so that people can get the benefits of the hailgun library now.
It comes with the hailgun-send executable out of the box. This executable can be used on the command line to send emails through the Mailgun API.
This library has been written in pure Haskell and does not use any FFI wrappers around another Mailgun library: the goal of this library is to work on any platform.
And this is just for version 0.1.0.0. To people that read this in the future, you should check out the library on hackage to see what it impiliments now.
Sending a test email
I’m going to explain here how to send a test email using hailgun-send so that you can quickly see that the library works and can be used to send your emails in pure Haskell code.
If you don’t have a Mailgun account and a sandbox for it then go sign up for one. Once you have created your account you should have been given an API key and have a sandbox domain name. Please create a file called ‘hailgun.send.conf’ in the current directory and make the contents of the file:
You will notice that I provided a from and to address, an email subject and the content of the email in two files. You should create the email.text and email.html files yourself or you could simply use the ones that are avaliable in the repository. Please note that the HTML version of the email is optional but the text version is always required.
You should see something like the following email appear in your inbox:
In short you should now be able to send emails, via Mailgun, with Haskell and the library should be improved to have more API support as time goes by. I hope this is useful to some peoplee and, if a Mailgun developer should happen to swing by this post then please feel free to review my code.
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.
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.
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.
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.
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.
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.
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:
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:
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:
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:
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:
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:
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:
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.
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.
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.
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
Row meets upper bound
Row meets neither bounds
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:
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:
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)
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)
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)
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)
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)
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.
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.
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.
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.
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.
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.
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.
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:
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”.