Prescience

Me, in 2009: "Visual Studio needs achievements."

Microsoft, yesterday: "Visual Studio is getting achievements."

What's Wrong with this Picture?

I snapped this screenshot of Bejeweled 3 right after the words "No more moves" appeared and right before the gems exploded off the screen. See anything wrong?

Double-ewe tee eff, Popcap. Double-ewe tee eff.

(For those interested in what causes this bug to occur, it sometimes happens during a cascade. In the middle of the cascade, the words "no more moves" appear, yet the cascade continues. When it finally comes to rest, there might still be moves, but the "game over" flag has already been tripped. It appears that their algorithm that checks for game over conditions only checks if valid swaps can be made, and does not check if gems are already matched.)

Watch This to be Lulled to Sleep by the Dulcet Sounds of my Voice

...as I talk about one of the most boring subjects known to man.

For those of you with persistent insomnia, a macabre fascination with what I've been doing at work over the last few years, or my adoring fan who just have to know what I'm up to (hi mom!), read on.

Read more »

Life

Well, Joe guessed correctly and first that the previously mentioned batch file is an implementation of Conway's Game of Life.

I wrote a slightly better implementation in C#, and it allows more than just 2 states, but it's not very sophisticated:

While I was writing that version, however, I stumbled across a much more advanced implementation (in the same way that the B-2 is more advanced than a kite), called Golly.

I highly recommend checking it out, but I should warn you that it might cause you to waste hours if not days staring at the blinkenlights.

Nerdvana Moment Of The Day

Copy this to a batch file and run it:

@echo off
setlocal enabledelayedexpansion

set Framefile=dosref.html
set TOCfile=TOC.html

echo ^<html^> >%Framefile%
echo ^<head^> >>%Framefile%
echo ^<title^>DOS Reference^</title^> >>%Framefile%
echo ^</head^> >>%Framefile%
echo ^<frameset cols="120,*"^> >>%Framefile%
echo   ^<frame src="%TOCfile%"/^> >>%Framefile%
echo   ^<frame name="showframe"/^> >>%Framefile%
echo ^</frameset^> >>%Framefile%
echo ^</html^> >>%Framefile%

echo ^<html^>^<head^> >%TOCfile%
echo ^<title^>Table of Contents^</title^> >>%TOCfile%
echo ^</head^>^<body^> >>%TOCfile%

for /f "usebackq skip=5 tokens=1" %%i in (`help ^|sort`) do (
 if not exist %%i.txt (
   help %%i > %%i.txt
   if ERRORLEVEL 1 (
     echo ^<a href="%%i.txt" target="showframe"^>%%i^</a^>^<br/^> >>%TOCfile%
   ) else (
     del %%i.txt
   )
 )
)

echo ^</body^>^</html^> >>%TOCfile%

In case you're suspicious of running strange batch files you see on the internet (aka smart), what it does is create a frame-based DOS command html reference. Tested in Windows XP, Vista should work too.

Gravity Update

Version 1.3 is available! A co-worker told me, "I won't play your little game until I can blow stuff up." Well, now you can blow stuff up (sort of):

This release shall from now on be referred to as the CPU-Eater Edition. To see why, try this:

1. Run the sim

2. Press X to turn on fracture mode

3. Press S to open the Seed number dialog

4. Enter 31500 and click OK

5. Cackle with pitiless glee as whole worlds are rent asunder as they enter the cosmic maelstrom.

I hope you have a multi-core CPU if you want to do other things while this program is running. Other things to try:

• Press 0 (zero) to turn on auto time acceleration
• Press SHIFT+= to set auto acceleration to maximum
• Press I or G or to turn on pretty colors

When auto acceleration is on, the program will adjust the speed and/or graphical detail to try to maintain between 10 and 20 fps. Notice that orbits (and co-orbits) are now displayed with time acceleration on, so you can see how they evolve and affect each other over time.

Answers to the Programming Quiz:

Tom got the answer to number one. The assignment

(-1 ^ (j - 1))

will always be -1 for any integer value of j, because of Visual Basic's order of operations. The carat operator is applied before the minus operator. This added about 15 minutes to my debugging time.

As for the second question, Dave was right on with his assessment:

"it seems to take a set of real numbers and multiplies them against each other, alternately adding/subtracting the products."

That is, in fact, exactly what it does, and had he known the law in question, you probably would have gotten it from here. The law (or maybe formula would be a better term) is the general form of the Addition Law for n Independent, Non-exclusive Events, and is used in the field of probability to determine the chances that at least one of n events occurs, given the probabilities of each individual event.

To explain this, let me first define independent and non-exclusive. Two events are independent if the occurrence of one does not affect the occurrence of the other. Example: a die rolling 6 and a coin landing heads.

Two events are exclusive if they cannot occur at the same time. Example: a coin landing heads, and the same coin landing tails.

So the probability of either of two independent, non-exclusive events occurring is given by the equation:

P(A+B) = P(A) + P(B) - P(A)∙P(B)

Where P(A+B) is the probability that either A or B occurs, P(A) is the probability that A occurs independently, and P(B) is the probability that B occurs independently. (I am using + notation because I can't find the stupid Union symbol in the character map.)

This can be easier to understand with a Venn diagram.

If we want to find the area covered by both ellipses (the probability that at least one of the events occurs), we start by adding the area of each ellipse (P(A)+P(B)). But then we have added the intersection of the two events twice, so we need to subtract it out once (–P(A)∙P(B)).

We can determine the probability that any of three independent, non-exclusive events occurs with the equation:

P(A+B+C) = P(A) + P(B) + P(C) - P(A)∙P(B) - P(A)∙P(C) - P(B)∙P(C) + P(A)∙P(B)∙P(C)

To understand this, let's look at another Venn diagram.

To find the area covered by all three circles, we begin by adding in the area of each circle (the independent probability of each event, P(A) + P(B) + P(C)), but then we have added some regions more than once. To compensate, we can subtract out the intersection of every two circles (–P(A)∙P(B) – P(A)∙P(C) – P(B)∙P(C)). But now we have completely subtracted out the center region, the intersection of all three circles (P(A)∙P(B)∙P(C)).

I think you see where this is going for four events, etc. It gets very complex. In fact, the general form of the Addition Law, for n independent, non-exclusive events is:

(I)

In essence, we add in the independent probability of each event, subtract the products of each combination of two events, add the products of each combination of three events, subtract the products of each combination of four, etc., until we finally add or subtract (depending on if there are an odd or even number of events) the product of every event probability. This is what my VB code was attempting.

(There is an alternate, less complex way of attempting this. Instead of a brute force method, we can instead consider the inverse probabilities. Instead of finding the area covered by the circles/ellipses, we can find the area not covered by them, and subtract that from 1. To wit:

De Morgan's theorem states: P(A+B)' = P(A'∙B') = P(A')∙P(B')

That is, the probability that neither A nor B occurs is the probability that A does not occur and B does not occur. So if we subtract that from 1, we get:

P(A+B) = 1 – P(A')∙P(B') = 1 – (1 – P(A))∙(1 – P(B))

Which, for the general form, expands to:

(II)

)

So what brought this all up?

Probability theory figures heavily in fault tree analysis. A fault tree is, essentially, a collection of events (each with an associated probability of occurrence, specifically a probability of failure) connected via logic gates, such as AND and OR gates (and sometimes VOTE gates).

What? Explanation of the logic gates? Ok, we can do that.

This is an AND gate. It denotes that the output occurs if all of the input events occur.

An OR gate denotes that the output occurs if any of the inputs occurs.

A VOTE gate denotes that the output occurs if at least n of the inputs occurs (in this case 2).

(These symbols may seem familiar to those of you who took computer architecture. The symbols are the same ones used in logic gate diagrams, but turned sideways.)

There are also other miscellaneous gates, such as a NOT gate or XOR gate, but that's a bit beyond the scope of a simple introduction.

So the basic premise of fault tree analysis is we want to know about how often (the probability) a TOP event will occur, based on the occurrence of basic events. The TOP event is usually some hazard that we would like to prevent. A basic event is a failure or occurrence which may cause the TOP event to occur.

So, to create a fault tree, we connect these basic events to the TOP event through intermediate logic gates. These logic gates represent how the failures combine to cause a TOP event occurrence. A small fault tree might look like this:

The way to read this is by looking at the logic symbol of each gate to determine which of its input events must occur to cause the gate to occur. For example, if EVENT5 and EVENT6 occur, this will cause GATE3 to occur, because it's an AND gate and requires the occurrence of all input events. If GATE3 occurs, GATE2 will also occur, because it's an OR gate and the occurrence of any of its inputs will cause its occurrence. Now, if any two of the inputs to GATE1 occurs, say EVENT1 and EVENT3, then GATE1 will occur (because it's a VOTE gate). And if both GATE1 and GATE2 occur, then TOP1 will also occur. So we could say that TOP1 will occur if EVENT1, EVENT3, EVENT5, and EVENT6 all occur at the same time. We call this occurrence of events a minimal cut set. (I might talk more about cut sets in the future, if you wish, but as it is, this post is running too long.) Another minimal cut set might be EVENT2.EVENT3.EVENT4. (Note, EVENT2.EVENT3.EVENT4.EVENT5 is also a cut set, but not minimal. Do you see the difference?)

I will skip over how to produce the full list of minimal cut sets for this tree, and just list them all. They are: 

EVENT1.EVENT2.EVENT5.EVENT6

EVENT1.EVENT2.EVENT4

EVENT1.EVENT3.EVENT5.EVENT6

EVENT1.EVENT3.EVENT4

EVENT2.EVENT3.EVENT5.EVENT6

EVENT2.EVENT3.EVENT4

By this point, you can probably see how to produce them yourself. Now each cut set can be thought of as an event, itself. So, basically, what we have here is a list of non-exclusive, independent events, the occurrence of any of which will cause the TOP event.

Sound familiar?

The obvious way to solve this, then, would be to use... the Addition Law!

And this is exactly what the software (that company I work for) writes does. You tell it the events, how they're logically connected, and some quantitative data, such as a failure rate or MTTF (mean time to failure), and it will calculate:

1) The probability of each event occurring,

2) The probability of each cut set occurring (simple: the product of the probabilities of each event in the cut set)

3) The probability of occurrence of the TOP gate (using the Addition Law).

Note how quickly the addition law gets complex. This small and simple tree produces six cut sets, which would require 6 + 15 + 20 + 15 + 6 + 1 = 63 product terms in the addition law. Just the other day I was working with a fault tree that had 152 cut sets for one intermediate-level gate. This is why our software will use approximation methods and all sorts of other tricks to be able to solve the tree. In fact, one of the approximation methods involves using de Morgan's theorem and equation II. This is called the Esary-Proschan approximation method, but you didn't really want to know that.

If you would like, I could talk a little bit more about fault tree analysis later, and give real examples, instead of odd abstractions. But this post has gone on too long.

And now you know what I do for a living!

So back to the topic at hand, why was I writing a VB program to implement the Addition Law? Basically, I needed to verify the results of a fault tree. By hand.

Programming Quiz of the Day/Week/Month.

Question 1: What is the value of x after this code executes?

dim j as integer, x as integer

j = 5

x = (-1 ^ (j - 1))

Question 2: What mathematical law does the following code implement?

'Globals

dim i as integer, j as integer

dim dValues() as double

Private Function DoEet() As Double

    i = UBound(dValues)

    For j = 1 To i + 1

        DoEet = DoEet + RecursiveHell(-1, 0, -1, 1)

    Next j

End Function

Private Function RecursiveHell(k As Integer, l As Integer, _

    m As Integer, x As Double) As Double

Dim temp As Double

    If k = -1 Then

        k = 0

        RecursiveHell = RecursiveHell + RecursiveHell(k, 1, k, 1)

    Else

        If l < j

            Do While m < i - (j - 1)

                temp = x * dValues(m)

                RecursiveHell = RecursiveHell + RecursiveHell(k, l + 1, m + 1, temp)

                m = m + 1

            Loop

        Else    'l = j

            Do While m < i

                temp  = x * dValues(m) * ((-1) ^ (j + 1))

                RecursiveHell = RecursiveHell + temp 

                m = m + 1

            Loop

        End If

    End If

End Function

(Might want to resize your browser so that this fits on one line:)

-----------------------------------------------------------------------------------

(Don't know what recursion is? Click here to find out.)