What is DFSM minimization?

First, let us consider what does it mean for two DFSM to be equivalent? Imagine having two DFSM that both accept the same input symbols. You then pass all the possible inputs to those two machines. If and only if the answers are the same for all the inputs then the two machines are equivalent. That is: they accept exactly the same inputs, even though their inner workings might not be the same.

This means that there are many equivalent DFSM. For example all three DFSM in the below picture accept the same input which can be written as a regular expression (0+1)^*.

The three DFSM vary in the number of states and also in the number of the transitions. Nonetheless, I hope you will agree with me that they all accept the same input.

In this example case the machines are simple. But what would happen if the machines were complex - how would we determine if they are equivalent?

The answer is minimization. Minimization transforms a machine into an equivalent machine that has minimum number of states. We can then easily check if two DFSM are are equivalent. We just need to check if they have the same number of states and if all the transitions are the same.

Why minimization

Like I described in the previous paragraph you can use minimization to check the equivalence of the DFSM. Two other benefits (when using DFSM in programming) are:

• performance increase due to less states and transitions (faster input checking, less memory consumed),
• easier reasoning about the minimized machine since it has fewer moving parts.

Two types of states to remove

When minimizing there are two types of states that we can either completly remove or merge with other states of the machine:

• unreachable states are those states that are not reachable from the initial state of the DFA, for any input string,
• nondistinguishable states are those that cannot be distinguished from one another for any input string.

Unreachable states

First, let us look at an algorithm for finding the unreachable states. The algorithm starts from the known reachable states which are the start states - the start states are always reachable. It then expands the list of reachable states by adding all the states that can be reached from the start states. It continues this expansion using the newly added states until it cannot add any new states to the list of reachable states. The states of the DFSM that did not end up in the list of reachable states are unreachable.

To me this algorithm feels like flooding the pipes: we have a system of pipes some of which are connected and some of which are not. We open the water and check which pipes did the water reach and which it did not reach.

Below is the algorithm in C#¹:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

var reachableStates = new HashSet<string>{Q0};
var newStates = new HashSet<string>{Q0};
do{
  var temp = new HashSet<string>();
  foreach (var q in newStates){
      foreach (var c in Sigma){
          var transition = Delta.Find(t => t.StartState == q &&
                                             t.Symbol == c);
            if (transition != null){
              temp.Add(transition.EndState);
            }
        }
    }
    temp.ExceptWith(reachableStates);
    newStates = temp;
    reachableStates.UnionWith(newStates);
} while (newStates.Count > 0);
var unreachableStates = Q.Where(q => !reachableStates.Contains(q));

The part of the algorithm that finds the possible transitions from the new states is quite inefficient. For each new state it tries all the symbols from sigma. This causes us to loop over all the transitions for every symbol and every new state. A better solution is shown below. In it we are just selecting all the states that are reachable from the current state:

1
2
3
4
5

foreach (var q in newStates){
  var reachableFromQ = Delta.FindAll(t => t.StartState == q)
                            .Select(t => t.EndState);
    temp.UnionWith(reachableFromQ);
}

Now that we have found all the unreachable states we can remove them (along with transitions to and from them):

1
2
3
4
5
6
7
8
9
10

for (int i = Delta.Count - 1; i >= 0; i--){
  var transition = Delta[i];
  if (unreachableStates.Contains(transition.EndState) ||
      unreachableStates.Contains(transition.StartState)){
      Delta.Remove(transition);
    }
}
foreach (var unreachableState in unreachableStates){
  Q.Remove(unreachableState);
}

Nondistinguishable states

And now for the hard part - the nondistinguishable states. Here, we will use Brzozowski’s algorithm for minimization, which works like this:

Reversing the edges of a DFA produces a non-deterministic finite automaton (NFA) for the reversal of the original language, and converting this NFA to a DFA using the standard powerset construction (constructing only the reachable states of the converted DFA) leads to a minimal DFA for the same reversed language. Repeating this reversal operation a second time produces a minimal DFA for the original language.

To implement the described algorithm we will need the following:

1. an algorithm that reverses a DFSM and produces a corresponding NDFSM,
2. an algorithm for powerset construction (this algorithm converts a given NDFSM into an equivalent DFSM)
3. an algorithm for detecting and removing unreachable states (see above).

Reversing a DFSM

The algorithm for reversing a DFSM is quite easy to implement and is presented below ²:

1
2
3
4
5
6
7
8
9

private NDFSM Reverse(DFSM d){
    var delta = new List<Transition>();
    foreach (var transition in d.Delta) {
        delta.Add(new Transition(transition.EndState,
                                 transition.Symbol,
                                 transition.StartState));
    }
    return new NDFSM(d.Q, d.Sigma, delta, d.F, d.Q0);
}

Powerset construction

Here is how I implemented the powerset constructions algorithm in my previous post³:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

 private static DFSM PowersetConstruction(NDFSM ndfsm){
     var Q = new List<string>();
     var Sigma = ndfsm.Sigma.ToList();
     var Delta = new List<Transition>();
     var Q0 = new List<string> { string.Join(" ", ndfsm.Q0) };
     var F = new List<string>();

     var processed = new List<string>();
     var queue = new Queue<string>();
     queue.Enqueue(string.Join(",", ndfsm.Q0));

     while (queue.Count > 0){
        var setState = queue.Dequeue();
        processed.Add(setState);
        Q.Add(CleanupState(setState));

        var statesInCurrentSetState = setState.Split(',').ToList();
        foreach (var state in statesInCurrentSetState){
           if (ndfsm.F.Contains(state)){
              F.Add(CleanupState(setState));
              break;
           }
        }
        var symbols = ndfsm.Delta
           .Where(t => statesInCurrentSetState.Contains(t.StartState))
           .Select(t => t.Symbol)
           .Distinct();
        foreach (var symbol in symbols){
           var reachableStates =
              ndfsm.Delta
                 .Where(t => t.Symbol == symbol &&
                             statesInCurrentSetState.Contains(t.StartState))
                 .OrderBy(t => t.EndState).
                 Select(t => t.EndState);
           var reachableSetState = string.Join(",", reachableStates);

           Delta.Add(new Transition(
                                    CleanupState(setState),
                                    symbol,
                                    CleanupState(reachableSetState)));

           if (!processed.Contains(reachableSetState)){
              queue.Enqueue(reachableSetState);
           }
        }
     }
     return new DFSM(Q, Sigma, Delta, Q0, F);
  }

  private static string CleanupState(string state){
     return state.Replace(",", " ");
  }

Putting it all together

Now that we have all the pieces we can combine them into Brzozowski’s algorithm:

1
2
3
4
5
6
7
8
9

 public static DFSM MinimizeDFSM(DFSM fsm){
   var reversedNDFSM = Reverse(fsm);
   var reversedDFSM = PowersetConstruction(reversedNDFSM);
   reversedDFSM.RemoveUnreachableStates();
   var NDFSM = Reverse(reversedDFSM);
   var DFSM = PowersetConstruction(NDFSM);
   DFSM.RemoveUnreachableStates();
   return DFSM;
}

If you check the powerset construction algorithm (or read my previous post) you can see that the implementation has the nice property that it constructs a DFSM with only reachable states. Which is why we can remove the two calls to RemoveUnreachableStates method. The final algorithm:

1
2
3
4
5
6

public static DFSM MinimizeDFSM(DFSM fsm){
   var reversedNDFSM = Reverse(fsm);
   var reversedDFSM = PowersetConstruction(reversedNDFSM);
   var NDFSM = Reverse(reversedDFSM);
   return PowersetConstruction(NDFSM);
}

And lets see how the minimization works on an example. This is how the four steps of the above minimization look like on the third DFSM from the beginning .

So this is it for minimization. The source code can be found at github.

Powerset construction algorithm

Like I discussed in my previous blog post, the only difference between the DFSM and the NDFSM is that the DFSM does not allow multiple transitions for a given state and symbol. If we wish to transform a NDFSM into a DFSM we need to remove these multiple transitions. We can achieve this by combining all the states that we can reach with a given symbol from a given state into a new state which is a set of all the reachable states.

As you can see on the left side of the above picture we can reach states q1 and q2 from the state q0 using the symbol a. This means that the state q0 has multiple transitions defined for the symbol a and we wish to get rid of these multiple transitions. The powerset construction combines states q1 and q2 into a new state that is the set of these two states as can be seen on the right side of the picture. The new state is denoted as {q1, q2}. When we do this transformation for the combined states, like the {q1, q2}, we need to look at the transitions for all the states that make this combined state, in this case q1 and q2.

The good news is that this does exactly what we need: it gets rid of the multiple transitions. The bad news though is that in the worst case the number of states explodes and we end up with the states that are all the possible subsets of our original set of states.

Ouch.

So how would we approach this constructions programmatically? Probably the easiest way would be to keep a queue of states that we wish to process. The initial queue would only contain the starting states. We would then add all the possible states that are reachable from the starting states. If there are multiple transitions from a state with a given symbol we would create a new combined state like described in the previous paragraph and add it to the queue. For the symbols that only have one transition we would just add the ending state of the transition to the queue. We would then remove a state from the queue and repeat the described algorithm until we empty the queue.

Determining the finish states of the DFSM machine is easy. The finish states will be all the finish states of the original NDFSM plus the combined states that have a least one of the finish states as one of their elements.

During the execution of the algorithm we would of course need to keep track of the already processed states and the transitions between them so that we can construct our NDFSM.

Here is one possible implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

public static DFSM Convert(NDFSM nd){
  var Q = new List<string>();
  var Sigma = nd.Sigma.ToList();
  var Delta = new List<Transition>();
  var Q0 = nd.Q0.ToList();
  var F = new List<string>();
  
  var processed = new List<string>();
  var queue = new Queue<string>(Q0);
  while (queue.Count > 0){
     var setState = queue.Dequeue();
     processed.Add(setState);
     Q.Add(setState);

      var statesInCurrentSetState = setState.Split(',').ToList();
      foreach (var state in statesInCurrentSetState){
          if (nd.F.Contains(state)){
              F.Add(setState);
              break;
         }
      }
      var symbols = nd.Delta
         .Where(t => statesInCurrentSetState.Contains(t.StartState))
         .Select(t => t.Symbol)
         .Distinct();
      foreach (var symbol in symbols){
         var reachableStates =
            nd.Delta
               .Where(t => t.Symbol == symbol &&
                           statesInCurrentSetState.Contains(t.StartState))
               .OrderBy(t => t.EndState)
               .Select(t => t.EndState);
         var reachableSetState = string.Join(",", reachableStates);

         Delta.Add(new Transition(setState, symbol, reachableSetState));

         if (!processed.Contains(reachableSetState)){
            queue.Enqueue(reachableSetState);
         }
      }
  }
  return new DFSM(Q, Sigma, Delta, Q0, F);
}

Conclusion

This algorithm was actually easier to implement than I thought. I thought that I would need to generate the powerset and then all the possible transitions between all the states. I took a different approach which only goes through the reachable states and only generates the states of the powerset that are actually needed. The algorithm turned out much simpler and on top of that it also produces a better results since the unreachable states are pruned away!

The source code is available at Github.

The only difference between the DFSM and NDFSM is that while the DFSM can only have a single transition for a given state and input symbol the NDFSM is not limited in that regard. It can have multiple transitions for a given state and input symbol.

With multiple possible next moves we get the non-deterministic way of operating. This is usualy depicted as a “magic wand” that correctly decides which transition to choose when multiple options are available. Unfortunatelly for us programmers we don’t have that magic wand. We need to try all the possible options before we can answer wheater the NDFSM accepts the input or not. My first thought when seeing something like this is backtracking:

• pick one of the possible transitions,
• if it leads to the solution great,
• if not backtrack and try something else.

But let us not get ahead of ourselves. Let us start with something simpler.

Valid transitions

With the before discussed difference in mind I looked at the DFSM implementation to see what will I need to change (If you didn’t read the previous article this would be a good time, since I will mostly skip the parts that will remain the same and only focus on the differences. And even if you have already read it, it might help to have another window opened with the source code of the solution.).

One of the first things I noticed was the logic that checks the validity of transitions. We no longer need to check if a similar transition has already been defined, so we can remove that part:

1
2
3
4
5

private bool ValidTransition(Transition transition){
    return  Q.Contains(transition.StartState) &&
            Q.Contains(transition.EndState) &&
            Sigma.Contains(transition.Symbol);
}

All the other validation logic can remain the same. Which brings us to the biggest change: the Accepts method.

Non-deterministic Accept

Like I already mentioned above the non-determinism often looks like magic. This kind of behavior is usually implemented by recursive backtracking. Let us look at a high level overview of the method:

• find all the posible transitions from the current state using the current symbol,
• recursively select one transition and try to accept the remaining input by using that transition,
• if we managed to read the whole input and ended up in a final state, accept the input,
• if the state is not final or no transitions are possible, backtrack and select a different transition.

First, we need a method that will start our recursive calls. The logic here is a bit different than in the deterministic case where we could easily determine if the input is not accepted:

• there was no valid transition for current state and symbol symbol or
• we read all the input and ended up in a non finite state.

For the non-deterministic case we need to do that for all the possible transitions from a given state and symbol. And we should start this from the starting state and the whole input:

1
2
3
4
5
6
7
8

public void Accepts(string input){
    ConsoleWriter.Success("Trying to accept: " + input);

    if (Accepts(Q0, input, new StringBuilder())){
        return;
    }
    ConsoleWriter.Failure("Could not accept the input: " + input);
}

Next we need to write the recursive function that checks if there is any sequence of steps that leads from the current state to the final state using the specified input:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

private bool Accepts(string currentState, string input, StringBuilder steps){
    if (input.Length > 0){
        var transitions = GetAllTransitions(currentState, input[0]);
        foreach (var transition in transitions){
            var currentSteps = new StringBuilder(steps.ToString() + transition);
            if (Accepts(transition.EndState, input.Substring(1), currentSteps)){
                return true;
            }
        }
        return false;
    }
    if (F.Contains(currentState)){
        ConsoleWriter.Success("Successfully accepted the input " + input + " " +
                               "in the final state " + currentState +
                               " with steps:\n" + steps);
        return true;
    }
    return false;
}

If there are more symbols to read we find all the possible transitions for the current state and current symbol. We then recursively try each of these transitions by calling the Acecepts method on the EndState of the transition with the remaining input. The remaining input here is the current input except for the first symbol which we used in the transition. We also need to add the current transition to the steps. For that I created a new StringBuilder or we would add some transitions that did not lead to the solution in the foreach loop.

The recursion stops when we either tried all the transitions and none of them worked. Or if we came to the end of the input in which case we accept the input only if we stoped in a finish state.

The only thing remaining is the GetAllTransitions method which simply goes through all transitions and finds the ones with the specified start state and symbol:

1
2
3
4

private IEnumerable<Transition> GetAllTransitions(string currentState, char symbol){
    return Delta.FindAll(t => t.StartState == currentState &&
                         t.Symbol == symbol);
}

Conclusion

While the difference between the DFSM and NDFSM is quite small on paper their algorithms are quite different. Reading the input in the case of DFSM proceeds in linear fashion, we are always reducing the number of symbols we still need to read. But for NDFSM this is not the case. We might read all the input but not finish in the end state and then backtrack back to the begining with whole input left to read. This also makes the NDFSM algorithm perform much slower.

Also the implementation above is not really the best when it comes to performance. We are calling the GetAllTransitions method over and over again. A better way would be to store the possible transitions so that we don’t have go through all the transitions every time. But I’ll leave this to the readers (as well as implementing epsilon transitions).

You can find the source code for NDFSM on github.

This is why I decided to implement the finite state machine and the Turing machine in C# as an exercise. In this blog post I will start with the easier of the two, the finite state machine (FSM).

Programming by wishful thinking

I will not bore you with the theory, since you can read all about it in the wikipedia article, which explains the logic behind FSM better than I ever could. So I will just start with programming by wishful thinking. This is how I would like to consume an implementation of a deterministic FSM (DFSM):

1
2
3
4
5
6
7
8
9
10
11

// Declaration
var Q = new List<string>{"q0", "q1", "q2"};
var Sigma = new List<char>{'a'};
var Delta = new List<Transition>{
    new Transition("q0", 'a', "q1"),
    new Transition("q1", 'a', "q2"),
    new Transition("q2", 'a', "q1")
};
var Q0 = "q0";
var F = new List<string>{"q0", "q2"};
var dFSM = new DeterministicFSM(Q, Sigma, Delta, Q0, F);

As you can see I define the five components that make a DFSM: the states of the machine Q, the alphabet Sigma, the list of transitions Delta, the start state Q0, and the set of finish states F. I then construct the machine by passing the components to the constructor.

I expect the upper definition to construct the FSM that is visible on the image below. As you can see the machine accepts all the words with an even number of “a” characters.

After constructing the machine we wish to test if some input is a part of the machine’s language:

1
2
3
4

// Asking the machine if certain inputs are a part of it's language
dFSM.Accepts("");
dFSM.Accepts("a");
dFSM.Accepts("aa");

I want the Accept method to print out if the machine accepted the input or not. Also I would like to see the steps that led to the finish state if the input was accepted.

Transitions

With that, I had all the specification I needed, so I started by implementing the first thing the compiler complained about: the Transition object.

The transitions define how we can move between the states. So the Transition class needs to hold the information about the StartState, the Symbol and the EndState of the transition. Appart from that I added a ToString() method that will be used later on.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class Transition{
    public string StartState { get; private set; }
    public char Token { get; private set; }
    public string EndState { get; private set; }

    public Transition(string startState, char token, string endState){
        StartState = startState;
        Token = token;
        EndState = endState;
    }

    public override string ToString(){
        return string.Format("({0}, {1}) -> {2}", StartState, Symbol, EndState);
    }
}

Deterministic finite state machine

Now that we have the Transition, we can start implementing the machine. Here is how the constructor might look like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public class DeterministicFSM{
    private readonly List<string> Q = new List<string>();
    private readonly List<char> Sigma = new List<char>();
    private readonly List<Transition> Delta = new List<Transition>();
    private string Q0;
    private readonly List<string> F = new List<string>();

    public DeterministicFSM(IEnumerable<string> q, IEnumerable<char> sigma,
                            IEnumerable<Transition> delta, string q0,
                            IEnumerable<string> f){
        Q = q.ToList();
        Sigma = sigma.ToList();
        AddTransitions(delta);
        AddInitialState(q0);
        AddFinalStates(f);
    }
}

I just copied the list of states and the alphabet to the internal properties, but for the other three components we need some basic validation. For the transitions we want to verify that:

• they connect the states that are defined in Q,
• they use only symbols from Sigma.

There is an additional constraint with deterministic machine and that is: each state can only have one transition for a given symbol.

Considering all the requirements this is how the AddTransitions method might look like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

private void AddTransitions(IEnumerable<Transition> transitions){
    foreach (var transition in transitions.Where(ValidTransition)){
        Delta.Add(transition);
    }
}

private bool ValidTransition(Transition transition){
    return  Q.Contains(transition.StartState) &&
            Q.Contains(transition.EndState)   &&
            Sigma.Contains(transition.Symbol) &&
            !TransitionAlreadyDefined(transition);
  }

 private bool TransitionAlreadyDefined(Transition transition){
    return Delta.Any(t => t.StartState == transition.StartState &&
                          t.Symbol == transition.Symbol);
 }

The validations for the start state and the finish states are much simpler. We only need to check if they are defined in Q:

1
2
3
4
5
6
7
8
9
10
11
12

private void AddInitialState(string q0){
    if (Q.Contains(q0)){
        Q0 = q0;
    }
}

private void AddFinalStates(IEnumerable<string> finalStates){
    foreach (var finalState in finalStates.Where(
               finalState => Q.Contains(finalState))){
        F.Add(finalState);
    }
}

Accepting the inputs

That brings us to the meat of our DFSM implementation: the Accepts method. We will need to do the following:

• read the input symbol by symbol,
• try to find a transition from the current state that uses the current symbol,
• move to the next state defined by the found transition,
• if we have read all the symbols and have ended up in one of the finish states we can accept the input,
• in all other cases (no transition possible, ending up in non finish states) we don’t accept the input.

The upper pseudo algorithm is implemented below. The main logic is in the foreach loop that reads the next symbol and tries to transition to the next state. If the transition is successful it records the current step in the steps variable. I have also added a simple ConsoleWriter class that deals with simple print outs to the console.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public void Accepts(string input) {
    var currentState = Q0;
    var steps = new StringBuilder();
    foreach (var symbol in input.ToCharArray()) {
        var transition = Delta.Find(t => t.StartState == currentState &&
                                         t.Symbol == symbol);
        if (transition == null) {
            ConsoleWriter.Failure("No transitions for current state and symbol");
            ConsoleWriter.Failure(steps);
           return;
        }
        currentState = transition.EndState;
        steps.Append(transition + "\n");
    }
    if (F.Contains(currentState)) {
        ConsoleWriter.Success("Accepted the input with steps:\n" + steps);
        return;
    }
    ConsoleWriter.Failure("Stopped in state " + currentState +
                         " which is not a final state.");
    ConsoleWriter.Failure(steps);
}

Conclusion

I have omitted some additional validations and the code behind the ConsoleWriter for the sake of brevity, but the full source code can be found at GitHub.

Building the DFSM was quite fun! I have already implemented the non-deterministic one as well and will present it in one of the coming posts, and for sure I’ll do the Turing machine as well.

Before I say goodbye let me show you a test run of the DFSM on the following inputs:

1
2
3
4
5

dFSM.Accepts("");
dFSM.Accepts("a");
dFSM.Accepts("aa");
dFSM.Accepts("aaa");
dFSM.Accepts("aaaa");

1
2

Series series = Globals.ThisAddIn.Application.Selection;
series.Format.Fill.ForeColor.RGB = Color.Red.ToArgb();

For brevity’s sake let’s suppose that we have a series of a chart selected and we run the code above. One would expect that the color of the selected series would be set to red, but what happens is this:

And if we try to color the series blue then the result is red!

Red and Blue components of the RGB property are reversed

Since I intentionally used the red color that resulted in a blue series on the chart, some of you might have figured out the bug. But imagine yourself trying to apply some color from the middle of the RGB color range and consitently getting the wrong results.

Well the workaround is easy: just use a wrapper function that swaps the red and blue components of the color:

1
2
3
4
5
6
7
8

private void ApplyColorToSeries(){
    Series series = Globals.ThisAddIn.Application.Selection;
    series.Format.Fill.ForeColor.RGB = InteropColor(255, 0, 0);
}

public int InteropColor(int red, int green, int blue){
    return Color.FromArgb(blue, green, red).ToArgb();
}

After searching the web I found that this bug has already been mentioned on the StackOverflow. It is interesting that this has not yet been fixed in the newer versions of Excel. I have first stumbled upon this issue with the Excel 2007 interop library but it is still present in the current one. The only reason that comes to my mind is backwards compatibility with the numerous Excel solutions out there. So it seems we should just get used to it.

Update:

It seems that this is not an Excel interop bug. Apparently the reason for this strange behavior is that VBA has a different representation of colors. For more see the comments.

It’s great to:

• have your whole blog in version control,
• forget about hosting since it’s only a bunch of static pages and you can host them on GitHub pages ¹ ,
• style your blog with the help of many free themes,
• easily customize and extend your blog by plugging in different pieces of functionality.

Today I’m going to show you how easy it is to add social share buttons below each of your posts. Let’s get started.

Octopress by default supports the Add this social buttons. But it was a bit too limiting for my taste, so I removed it all and started from scratch.

The first thing to do is to create the account at Add This. This will allow you to customize your social buttons just the way you want them. I went for the “Original sharing buttons” and have set them like this:

There’s many options to choose from, but not all are available for free.

Below the services selection window you will see the code that you should copy and paste to your blog. But where should you put it? I decided to put the social buttons below each blog post similar to what Octopress offers by default. So I needed to find the post template which is under source/_layouts/post.html. In it we can see that the social share buttons are already rendering beneath the article template:

1
2
3
4
5
6

<article class="post" itemscope itemtype="http://schema.org/BlogPosting">
  {% include article.html %}
</article>
{% unless page.sharing == false %}
  {% include post/sharing.html %}
{% endunless %}

If you wanted you could have easily displayed the buttons even above the article just by copying the {% include post/sharing.html %} on the top of the template. Or at any other place of your blog.

Because the sharing template is already rendering we just need to paste our code from Add this to sharing.html which is under source/_includes/posts/sharing.html:

1
2
3
4

<script type="text/javascript"
  src="//s7.addthis.com/js/300/addthis_widget.js#pubid=yourPubId">
</script>
<div class="addthis_native_toolbox"></div>

We could have just pasted the code in the unless block, but I think that separating the parts is a better idea. It makes our site more modular and its easy to reuse the modules / partials / templates in different parts of our blog.

If we now regenerate the files we should see the social buttons beneath every blog post. Another nice thing about this is that if we wish to change how our buttons looks or if decide we wish to add some other buttons we only need to update our template at the Add this webpage and our buttons will update all across our site!

If you don’t want to use Add This you can use this same logic for any other buttons you wish to add.

• detecting the Excel window state and left edge position
• calculating from points to pixels ¹
• coping with the Windows DPI
• taking Ribbon / Formula Bar / Excel version into consideration
• serious lack of events on many of Excel’s objects
• …

The last nail in the coffin were the Panes which also need to be considered when a user uses the Freeze Panes option, which basically splits the worksheet into 2 or 4 Panes. At first it seemed like a simple adjustment until I started digging into the object model and ultimately found out that:

ActivePane’s Index property doesn’t work correctly

According to the Excel Object Model specification the ActivePane property:

Returns a Pane object that represents the active pane in the window.

and you can:

Use the Index property to obtain the index of the active pane.

Here is a simple code that is used to display the index of the current ActivePane:

1
2
3

var window = Globals.ThisAddIn.Application.ActiveWindow;
var activePane = window.ActivePane;
MessageBox.Show(activePane.Index.ToString());

Let’s see it in action.

As you see when there are 2 panes it always returns 2 and when we have 4 panes it always returns 4. I’m guessing it is just returning the number of the panes :)

The workaround

I needed to determine in which of the Panes is the current selection so I started looking at the Panes members. The only promising one was the VisibleRange. I didn’t want to use the Excel function INTERSECT since is quite costly performance wise. I figured out that just comparing the Left property of the VisibleRange with the Left property of the current selection should be enough (the same for the Top property). So I came up with this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

private int GetPaneIndex(){
    Range selection = Globals.ThisAddIn.Application.Selection;
    var window = Globals.ThisAddIn.Application.ActiveWindow;
    var paneCount = window.Panes.Count;
    if (paneCount == 2){
        Pane secondPane = window.Panes[2];
        if (secondPane.ScrollRow > 1
          && secondPane.VisibleRange.Top < selection.Top)
            return 2;
        if (secondPane.ScrollColumn > 1
          && secondPane.VisibleRange.Left < selection.Left)
           return 2;
    }
    else if (paneCount == 4){
        Pane secondPane = window.Panes[2];
        Pane thirdPane = window.Panes[3];
        if (selection.Left < secondPane.VisibleRange.Left
          && selection.Top < thirdPane.VisibleRange.Top)
           return 1;
        if (selection.Left > secondPane.VisibleRange.Left
          && selection.Top > thirdPane.VisibleRange.Top)
           return 4;
        if (selection.Left > secondPane.VisibleRange.Left )
           return 2;
        return 3;
     }
     return 1;
}

This works just fine with Ranges and pretty much every Excel object that has Left and Top properties. You get the correct index of the ActivePane.

However, what you also get, are some triggered events as soon as you access the VisibleRange property. I have no clue why this happens. Even a simple assigment like var range = pane.VisibleRange; causes the active chart to get deactivated, which again caused quite a few additional problems that are beyond the scope of this post.

How do I [blank] in Excel?

StackOverflow is full of questions like:

“How do I change the color of a Chart Series in Excel in VBA / C#?”

While doing it manually is easy, the problem occurs when you wish to start talking to Excel from the code. This is not surprising, considering the number of different objects present in the Excel Object Model. One can spend an insane amount of time trying to figure out the exact five steps to reach the desired effect. It is easy to get lost in all the objects, and their methods and properties. Which is why I love the macro recording option.

After learning about it you will be able to do all the tasks you already know how to do manually in code as well. Well, almost all. I’ll write about this in a future post.

The primary use of macro recording is to automate repetitive tasks. You just start the recording, perform the task and stop the recording. After that you can replay the recorded macro as many times as you wish. And not only that, you can also see all the steps that were performed in code!

How to record a macro

First of all I recommend that you show the Developer ribbon tab. You can do this under File | Options | Customize Ribbon, where you need to check the Developer ribbon tab:

After enabling the tab you gain access to macro recording and viewing options. You are now ready to record your first macro:

1. Click on the Record macro button under Developer tab
2. Perform the selected task, like changing a color of a Chart Series
3. Stop the macro recording
4. View the results

As you can see at the end of the animation all of the steps that I performed during the recording are saved in the macro. It is now easy to find the object / property you need. I use this extensively, almost every day. It mainly serves as a way of finding the specific object / property to set, after which I use the Intellisense to explore the options a bit further.

Tip:

If you will be using the described technique as much as I do, I even recommend adding it to the Quick Access Toolbar. Click on the arrows in the Toolbar, Select More commands and then add Record macro and View macro commands to your Toolbar:

^{Image source}

Git in Visual Studio

In January 2013 the Visual Studio team announced that Visual Studio will have Git support and you can download it from here if you want. You will need Visual Studio 2012 Update 2 at least.

I have tried the extension but I don’t recommend it just yet. It is still lacking many features and it seems very rushed. In a few iterations it might be worth to install it but for now I would say stay away. This is why I decided to discuss possible alternatives, namely: command line, Git Extensions and Source Tree.

Command line

So how can you start using Git? The easiest way in terms of required software is the command line. First of all you need to download and install Git. After that you just need to read the documenation and you can immediately start using it from the command line.

And that is a good way to start using it if you are not familiar with it. Since you have to type in all the commands you will think twice if this is the right thing to do. And you won’t get overwhelmed by all the possible commands. You will learn one or two commands and really get to know those. For starters you just need init and commit. Soon after that you will want to save the source code on another computer, not only on your own. That’s when remotes, push and pull come into play. And when you start to work in a team, sharing the code, you will need to learn about branches and maybe even about branching models like GitFlow for example.

Does this work with Visual Studio. Absolutely. That’s why I don’t understand why so much fuss about Git being incorporated into Visual Studio. Many developers only use git from the command line. Some would even argue that that’s the only way to use it. I understand that commiting directly from the IDE is probably faster and that visual representation of the branch tree is nice. However, writing a few additional lines every day sholdn’t keep you from using Git!

Git Extensions

The next option is a Visual Studio extension called Git Extensions. It’s the only one of the three alternatives that I mention that is completely integrated into Visual Studio. After installing you get an additional toolbar in your workspace:

The most used commands are directly exposed on the toolbar, but you can open up a window where all git commands are only a click away. You can also see your branch tree and commit messages.

^{Image source}

If you like the integrated way you might also want to check Git Source Control Provider which allows you to see the status of your files in the solution explorer. It makes it easy to see which files were newly added, which were changed,…

I’ve had some minor problems with Git Extensions. Sometimes the window crashed if I had it opened for too long. I also ran into some authentication problems when pushing to Bitbucket. This problem was solved by manually running their git-credentials-windstore executable. Apart from that I quite liked it. It is really rich with options and possibilities and also works remarkably well.

Source Tree

The last option is a standalone desktop application called Source Tree from Atlassian. While the Mac version has been around for quite some while they have released the Windows version not so long ago.

^{Image source}

I must admit that lately I’ve been using Source tree the most. I really like the nice user interface, it is also very easy to keep track of multiple projects. And there is another little gem: it has support for Gitflow. So you can easily start new features, hotfixes, releases.

So until the Visual Studio team improves their extension I think any of the three proposed options is better. Once again it will come down to personal preference. Do you want visual control or do you like command line? Do you want to have integration with Visual Studio or is a standalone application also ok?