Clear Lines Blog

Two level horizontal menu for ASP.NET

mathias — Fri, 06 Nov 2009 15:48:48 -1300

When I decided to have a 2-level horizontal menu for my professional webpage in ASP.NET, it came as a surprise to me that this wasn’t completely straightforward. I expected the standard ASP menu control to support this, but found out that this wasn’t the case.

Fortunately, I came across a post by Peter Kellner, describing how he implemented that for the Silicon Valley Code Camp website, which was pretty much what I envisioned.

The one issue I had with his implementation, however, was that the second level menu uses multiple data sources. The Master Page handles the top-level menu, but each page contains a reference to the specific datasource used to populate the sub-menu. As a result, if you decide to add a page, you need to manually add to that page some code to define what sub-menu should show up, which is cumbersome.

The ideal solution for a lazy developer like me would be to have all the menus handled in the Master Page, so that when you add a new page to your website, you just need to add it to the Sitemap, and the right menu and sub-menu shows up.

After some tinkering about, I figured out how to get this done. The trick is to use the Attribute StartingNodeOffset of the SiteMapDataSource.

I used the CSSFriendlyModified.dll Peter presents in his code sample, but modified the MasterPage, which looks like this:

<div id="Navigation">
    <asp:SiteMapDataSource ID="SiteMapMain" runat="server" 
    showStartingNode="False"/>
    <div class="MainMenuSection">
        <asp:Menu ID="MainMenu" runat="server" DataSourceID="SiteMapMain"
        MaximumDynamicDisplayLevels="0" Orientation="Horizontal">
        </asp:Menu>
    </div>
               
    <asp:SiteMapDataSource ID="SiteMapSecondLevel" runat="server" 
    showStartingNode="False" 
    StartingNodeOffset="1"/>
    <div class="SecondaryMenuSection">
        <asp:Menu ID="SecondaryMenu" runat="server" 
        DataSourceID="SiteMapSecondLevel" 
        Orientation="Horizontal" />
    </div>
</div>

The first block (SiteMapMain and MainMenu) declare what DataSource to use for the top-level menu (the SiteMap), and is pretty much identical to Peter’s code.

The second block declares a second DataSource (SiteMapSecondLevel), which hooks up to the SiteMap. Note the difference with the first DataSource: StartingNodeOffset is set to 1, which essentially tells the DataSource to look one level down in the nodes hierarchy of the SiteMap. The sub-menu “SecondaryMenu” simply uses that DataSource, regardless of the page.

As a result, now there is no need to add any code for pages to handle the second level menu. As long as a page is listed in the SiteMap, and hooked to the MasterPage, it will automatically populate the second level menu with the nodes that are listed under the top-level node. You can see that in action on this page, for instance. Enjoy!

And, give credit where credit is due - thanks a million for Peter Kellner – his code was a total life-saver.

Excel ScatterPlot with labels, colors and markers

mathias — Thu, 29 Oct 2009 10:05:54 -1300

Recently, a client asked me if it was possible to create an Excel scatter plot of his products, adding a label on each data point, and using different colors and symbols for different types of products. You could think of this as plotting 5 dimensions at once, instead of the usual two.

I quickly coded a VBA macro to do that, with a sample workbook to illustrate the usage. The macro is pretty rough, but was sufficient for my needs as is, so I haven’t put extra efforts in: feel free to improve upon it…

Here is a sample of the output:

To use it, you will need to enter the values for the chart in 5 columns, anywhere in the worksheet. Columns 1 and 2 contain the X and Y values for the scatter plot, column 3 the labels you want to add to each data point, column 4 and 5 are integers which represent the code for the marker symbol and color for the data point. Columns 4 and 5 are clearly not an elegant solution, and you’ll probably have to play with the values until you find what you want.

Note that you have to fill in all fields, for every point of the chart.

Once you have your data, simply select the entire range, all 5 columns of it, not including the headers, and click the “Generate ScatterPlot” button – et voila!

Download the ScatterPlot Workbook.

Read the contents of a worksheet with C#

mathias — Tue, 20 Oct 2009 10:46:18 -1300

When working with Excel workbooks with C#, I often need to retrieve the entire contents of a particular worksheet, so that I can process the data within C# code. By “the entire contents”, I mean the content of every cell between cell A1 and the last cell of the sheet, that is, the cell such that there is no cell on its right or below it that contains anything.

To do this, I use the following code, where excelWorksheet is a Worksheet (duh):

Excel.Range firstCell = excelWorksheet.get_Range("A1", Type.Missing);
Excel.Range lastCell = excelWorksheet.Cells.SpecialCells(Excel.XlCellType.xlCellTypeLastCell, Type.Missing);

object[,] cellValues;
object[,] cellFormulas;

Excel.Range worksheetCells = excelWorksheet.get_Range(firstCell, lastCell);
cellValues = worksheetCells.Value2 as object[,];
cellFormulas = worksheetCells.Formula as object[,];

The 2 resulting arrays of objects, cellValues and cellFormulas, contain the values and formulas, or null if the cell has no content.

However, while I was working on Akin recently, I realized 2 interesting things I had never noted before. First, the resulting array is 1-based, even though “C# arrays are zero indexed; that is, the array indexes start at zero”. Then, this code will fail if your spreadsheet contains only one value, in cell A1.

To prove my point, here is a snapshot of a QuickWatch of the cellValues array, reading a small spreadsheet. As you can see, the indexing begins at indexes 1 and 1.

It isn’t especially difficult to handle, but it really came as a surprise to me. Once you got used to zero-based indexes, which are pretty much the norm in .NET, this really is an intriguing oddity.

Once I realized this, I based all my code on the assumption that the array was going to be one-based, and everything went fine, until I realized that the following line was throwing an exception when the worksheet contained only a single populated cell in A1:

cellValues = worksheetCells.Value2 as object[,];

If you want to keep the same code, returning a 2-dimensional array, you have to handle that special case slightly differently, along the lines of:

if (lastCell.Row == 1 && lastCell.Column == 1)
{
    cellValues = new object[1,1];
    cellFormulas = new object[1,1];
    cellValues[0, 0] = firstCell.Value2;
    cellFormulas[0, 0] = firstCell.Formula;
}

But now this creates its own particular problem, because cellValues and cellFormulas are of course 0-based. I looked around and couldn’t find a way to declare a one-based array in C# (does anyone know if this is feasible?), so your best options are to either transform the array obtained in the standard case into a 0-based array, or, much less elegant, read the “special case” into a 0-based array which can be read through as a 1-based array:

if (lastCell.Row == 1 && lastCell.Column == 1)
{
    cellValues = new object[2,2];
    cellFormulas = new object[2,2];
    cellValues[1, 1] = firstCell.Value2;
    cellFormulas[1, 1] = firstCell.Formula;
}

I am frankly a bit torn between the 2 approaches. On the one hand, I feel much more comfortable working with a standard, 0-based array. On the other hand, while I strongly dislike having a method which returns sometimes a non-standard 1-based array, and sometimes a 0-based array but should be handled as a 1-based array (just describing this makes me queasy), it seems counter-productive to incur the cost of transforming a larger array most of the times, for the sake of the one-cell case, which is clearly an unusual boundary case. I’ll let you decide how you want to handle this!

The Art of Unit Testing

mathias — Thu, 15 Oct 2009 18:03:47 -1300

I recently finished reading the Art of Unit Testing, by Roy Osherove (Manning); here are a few thoughts on the book.

Who to give it too

This is an excellent book for the C# developer with solid foundations in object-oriented design, who has already some exposure to writing unit tests. If you have worked on a decent-scale project, and found yourself thinking “hmmm, I am sure there is a smarter way to write these tests”, you should definitely get that book. Note that while it will be extremely useful to the test-driven development practitioner, this is NOT a book on TDD.

3 things I liked about it

Writing maintainable tests: this topic has its own chapter, but you could argue that it is the underlying theme of the book, and Osherove does a great job covering what to look for in a test, and why. I really loved this part.

Design for testability: Osherove presents various refactoring approaches to make code more testable, and goes into it some more in an appendix. Besides the fact that this is a very important topic, I found this part of the book very stimulating, because, as is usually the case for design questions, the answers are not clear cut, and Osherove discusses the pros and cons very honestly.

Mocks and Stubs: not surprisingly, Osherove gives a very good exposition to isolation. I really liked that before going into specific frameworks, he takes the time to show how one would roll stubs and mocks manually. This is very helpful: it focuses the attention on why a mock is needed, and avoids the distraction that the framework syntax can be – and only then introduces the frameworks, showing how they simply reduce the amount of repetitive work needed, and how to use them. This is one of the clearest explanations on stubs and mocks I have seen so far (thank you!).

3 ways to make me happier

Keep the example straight: the LogAnalyzer class is used throughout chapter 2 and 3 as an example. In chapter 2, it is used how to unit test a feature which validates whether a file name is valid, based on the file extension. In chapter 3, however, the same feature is still there, but somehow another rule has mysteriously been added – in addition to the extension, the file name is also supposed to be longer than 5 characters. The code isn’t very complex, but I think the chapter would have gained clarity by either keeping the same example throughout, or by clearly exposing in the beginning of chapter 3 what the feature was, and which class was responsible for it.

Code layout: two small layout gripes. First , the indentation of the code is odd. The curly braces which open and close the class definition are indented with a tab space, the attribute are not aligned with the name of the class… Minor things, but displeasing to the eye. Then, it would be nice if the code examples were entirely on the same page. They are short enough that it seems it should be possible, and having the code visible in its entirety without needing to turn pages back and forth would be nice. On the plus side, I like the annotations/comment of the code.

Arrange, Act, Assert: I wish the section on AAA was a bit more developed. This is of course a matter of opinion, but I find this approach much clearer than record/replay – and it also seems that’s where most isolation frameworks are headed. I would have liked more guidance on this pattern / style - maybe using this as the default would be beneficial.

Final thoughts

As should be clear from the previous paragraphs, I really liked this book, and wish it had been available to me earlier. My experience with unit testing has gone through phases. When I came across Test-Driven Development, I began writing unit tests – lots and lots of them. This worked very well for the type of code I was writing, and I embraced unit testing with enthusiasm. But over time, I came to realize that, just like for “regular” code, it took work and experience to write maintainable tests, and learnt the hard way that some things worked well and some, not so well.

This is where the book shines. Every problem I encountered is listed in here, and some more, of course; the book provides a solid frame to write better, more maintainable tests, as well as guidance on how to better integrate them in the process and the organization.

That being said, I think that maintenance is a bit of an abstract concept. Until you had to maintain a real-size project, it is hard to fully grasp what maintainable code is, and why it is so important – and the same goes for tests. While I am sure this book would have helped me avoid pitfalls in my early attempts at writing good unit tests, I would probably have missed some of the points the book is making, not because there are complex, but because I would not have understood how they applied.

For that reason, I really recommend “the Art of Unit Testing” to the more seasoned developer. It will be an excellent companion, and will help bring your unit-testing game to the next level. If you are just getting started with unit testing, I would recommend starting with something else, like Kent Beck’s “Test Driven Development, by Example”, because it might give you a better sense of how to “do” things, and what it feels like to develop code and unit tests together.

VSTO add-in with multiple assemblies

mathias — Mon, 12 Oct 2009 10:54:03 -1300

I just found a solution to an issue which has been bothering me for a while. The reference article by Microsoft which describes how to deploy a Visual Studio 2005 Tools for Office solution using Windows Installer (a life-saver) doesn’t say anything about how to grant trust to multiple assemblies. This is a problem if you want to use satellite dlls in your add-in.

I figured out a workaround a while back, but I wasn’t convinced this was a good solution. Today, I came across this thread, where the second post (by Lex007) describes a simple way to do that, by modifying the SetSecurity project. Instead of passing only one dll, the tweak allows to pass a comma-separated list of dlls. I just tried it out, and it works like a charm.

Duct tape post-mortem

mathias — Sat, 10 Oct 2009 07:36:02 -1300

Much ado on the interwebs has followed Joel’s recent post on the now-infamous Duct Tape Programmer. You have to give it to Joel, he has a talent for writing pieces which get lots of people really worked up – what in some circles is called trolling. Out of curiosity, I looked up Google Trends, and unless some other piece of hot news related to duct tape surfaced on Sept 23rd, you can see with your naked eye the amount of buzz this one single post managed to generate. Impressive.

At that point I think the question of whether design patterns are an evil over-engineering practice has been discussed to death, by people much more qualified than me. For what it’s worth, I think Joel’s position has merits, to a point. There IS a natural tendency for developers to over-engineer, and I believe it’s a good practice when designing something to keep a dialogue going between two guiding voices:

“how should I design this, if I was not under time or budget constraint?”

“what’s the easiest solution which would get the job done?”

From http://www.dartmouthindependent.com/

One of the issue I have with the glorification of the Duct Tape Programmer is that Duct Tape programming is defined as a negative: to be a Duct Tape programmer, you should

avoid C++, templates, multiple inheritance, multithreading, COM, CORBA, and a host of other technologies that are all totally reasonable, when you think long and hard about them, but are, honestly, just a little bit too hard for the human brain

So how do you become a Duct Tape Programmer? Well, you don’t.

Duct tape programmers have to have a lot of talent to pull off this shtick. They have to be good enough programmers to ship code, and we’ll forgive them if they never write a unit test

This is where I take issue with Joel’s post. In essence, what he is saying is that some people are just so good at what they are doing that no matter how many rules they break, they will smoke your best effort - and that he likes these guys because they are good. That’s obvious – and it’s also both useless and dangerous. Even if you are a genius, you should start by mastering the classics – and then you can start breaking the rules. If you want to become a better software engineer, go study patterns, unit testing, and learn as much as you can. And then, once you clocked in your 10,000 hours, go ahead: pick your tools, and chose what to do and what to ignore.

I came across Joel a long time ago, through the Joel Test. This post was at the time tremendously useful to me, because it provided simple and actionable guidance on what to aim for to establish good practices for my software team. It was good advice on where to start to get better. This Duct Tape Programmer business is doing exactly the opposite. I wish Joel went back to constructive advice – and in the meanwhile, take that duct tape roll out of the software engineering best practices room, and bring it back where it belongs, the garage. But before that, maybe take a strip to close this discussion?

see more Epic Fails

I survived another SVCC iteration

mathias — Tue, 06 Oct 2009 06:09:23 -1300

Silicon Valley Code Camp version 4.0 took place this week-end, and was a big success, judging by the numbers and the happy faces. Congratulations to Peter Kellner and the team for a tremendous organization!

Personally, I wanted to give a big thank-you to the people who attended my session on Test-Driven Development – and for bearing with my voice, which was pretty shaky. I got sick this week and wasn’t sure until Saturday evening if I could do it, because on Thursday my voice was totally gone. I think I had more herbal tea with honey this week than in my entire life, but you guys made it all worth it: I had a great time giving my presentation, and you guys rocked!

As I said during the session, the theory behind TDD is pretty succinct, so there isn’t much in the slides themselves worth posting. Instead, I thought I would list a few pointers:

NUnit: you can find it here. I recommend checking out the Quick Start page, which covers most of what you need to start writing unit tests. I have written a post on data-driven tests here.

While we are talking about tools, I haven’t presented it during the session, but I really like TestDriven.Net. There is a free community version for your personal use. It’s a Visual Studio add-on which allows you to run and debug your tests from Visual Studio.

Even though it’s a Java book, and this session was for .NET developers, I really recommend Kent Beck’s book Test-Driven Development by Example. It’s very easy to read, and will get you started on the right foot. It’s also very well written – one of my favorite books!

The other book I recommend is the Art of Unit Testing, by Roy Osherove. I just finished it, and I wish I had it with me a few years ago, when I began writing tests seriously :) The book is technically about unit testing and not TDD, and it is a .NET book. I highly recommend it, it is chock-full of good advice, and covers way more than just testing.

That’s it! If you are interested in either the slides or code, let me know, and I’ll gladly post them, too. In the meanwhile, thanks again for coming, and… happy testing!

Akin 0.5.0 released

mathias — Sat, 03 Oct 2009 15:10:34 -1300

The current version of Akin, my free Excel worksheet comparison application, has been out for a bit now, and people have sent me some interested suggestions on how to make it better. However, my biggest personal issue so far has been speed. Opening large file hasn’t been an issue, but displaying comparisons of large worksheets (say, 200 x 200 cells) was taking a long time. The typical user for Akin is likely to be working with large files (tracking differences wouldn’t be an issue otherwise), so I had to do something about it.

I have bitten the bullet – I changed the design, and completely re-wrote the user interface where the comparison is displayed, and I hope that you will be pleased with the performance improvement. Where a 200 x 200 cells comparison took over 20 seconds to display, a 500 x 500 cells comparison is now virtually instantaneous. While I was at it, I did some cosmetic improvements on the looks as well.

You can download the new version here. Now that this performance problem is out of the way, I can get back to implementing the features that have been suggested so far. Stay tuned!

Movement is relative

mathias — Tue, 29 Sep 2009 16:02:00 -1300

I had an Eureka moment today, and realized that I was trying hard to resolve the wrong problem, when what was needed was a change of frame.

I have been developing an application which tracks differences between Excel worksheets, and displays them in a layout similar to Excel itself. The user can navigate through the sheet on display by using two scrollbars, just like he would with Excel.

To achieve this, my approach so far has been to read the data, create a grid using WPF, adding one cell control to the grid for each cell in the spreadsheet, and navigate “over” that grid using the scroll bars.

This approach works well as long as the spreadsheet is small, but for larger sheets – say, 200 x 200 cells - the time needed to create the cells and add them to the grid was getting pretty long, so I focused my attention on figuring out a way to populate the grid faster, without much success.

Then yesterday, someone wrote this on StackOverflow:

I'm going to go out on a limb here and say that trying to add 40,000 controls is your real bottleneck; not so much as to how you're adding the controls.

Indeed – that’s completely correct.This didn’t answer my issue directly, but it has been liberating, and got me to rethink the question from a different angle – do I really need 40,000 cells?

The answer is no: I just need controls for the cells which are currently on screen. Rather than compute a graphical representation for the entire spreadsheet, and then display only a small portion of it, I can create just enough cells to cover the visible area, and dynamically update their content to display the content of the visible cells. The cells you see are always the same, only their content gets updated (In hindsight, I looked back at Excel, and I believe that’s how it works). The grid contains a fixed number of cells, independent of the size of the worksheet, and should eliminate the problem altogether.

In a way, this is a small change of perspective. When you take a few steps forward, you can describe it two ways. You are moving forward, relative to the world, or you are immobile and the entire world is moving around you. Both descriptions are correct, but one comes more naturally than the other. My initial representation was similar to moving the whole entire world around the user, whereas the new approach is to simply determine what the user is seeing, and not worry about the world.

Why did it take me so long to accept that I should change my design? In large part, it’s due to the fact that the old design, while not scaling well, did work – and it took me a lot of work to get it to where it is now. I had to go through a few stages of design grief (denial: “What problem? Let’s not go into premature optimization”…), before reaching acceptance – it was a nice design, but it just didn’t fit the problem, so it’s time to let go, call it a proof-of-concept, and restart from fresh with a new design that won’t hold me back! Back to the drawing board…

The PuzzlOR

mathias — Sun, 20 Sep 2009 07:10:32 -1300

I was recently inspired by an article in OR/MS mag to write 2 posts on using Excel data tables to resolve optimization problems. As it turns out, these puzzles are not only published in the magazine: they also have their online home at Puzzlor.com. So if you like optimization and math problems in general, and like puzzles, check it out!

Bugs hiding in plain sight

mathias — Fri, 18 Sep 2009 06:12:05 -1300

I found a bug in my code the other day. It happens to everybody - apparently I am not the only one to write bugs – but the bug itself surprised me. In my experience, once you know a piece of code is buggy, it’s usually not too difficult to figure out what the origin of the problem might be (fixing it might). This bug surprised me, because I knew exactly the 10 lines of code where it was taking place, and yet I had no idea what was going on – I just couldn’t see the bug, even though it was floating in plain sight (hint: the pun is intended).

Here is the context. The code reads a double and converts it into a year and a quarter, based on the following convention: the input is of the form yyyy.q, for instance, 2010.2 represents the second quarter of 2010. Anything after the 2nd decimal is ignored, 2010.0 is “rounded up” to 1st quarter, and 2010.5 and above rounded down to 4th quarter.

Here is my original code:

public class DateConverter
{
    public static int ExtractYear(double dateAsDouble)
    {
        int year = (int)dateAsDouble;
        return year;
    }

    public static int ExtractQuarter(double dateAsDouble)
    {
        int year = ExtractYear(dateAsDouble);
        int quarter = (int)(10 * (Math.Round(dateAsDouble, 1) - (double)year));
        if (quarter < 1)
        {
            quarter = 1;
        }
        if (quarter > 4)
        {
            quarter = 4;
        }
        return quarter;
    }
}

Can you spot the bug?

Here is another hint – only one of these tests fails:

[TestCase(2010.1, Result = 1)]
[TestCase(2010.2, Result = 2)]
[TestCase(2010.3, Result = 3)]
[TestCase(2010.4, Result = 4)]
[TestCase(2010.0, Result = 1)]
[TestCase(2010.5, Result = 4)]
public int ValidateQuarter(double dateAsDouble)
{
    return DateConverter.ExtractQuarter(dateAsDouble);
}

My first thought was, “Oops I did it again, must have made a silly mistake with either rounding or casting somewhere”. But when I saw that the only failing test case was for 2010.3, I knew the logic of the calculation wasn’t the problem.

After some head-scratching, I realized what it was – my math is perfectly OK, thank you, but in the floating point world of the computer, things happen a bit differently. Like,

[Test]
public void HmmmRight()
{
    Assert.AreEqual(0.3, 0.3 - 0.0);
    // all the following fail miserably
    Assert.AreEqual(0.3, 0.4 - 0.1);
    Assert.AreEqual(0.3, 1.3 - 1.0);
    Assert.AreEqual(0.3, 2010.3 - 2010.0);
}

It is such simple math, and it is so obvious to me that 2010.3 – 2010.0 equals 0.3, that I didn’t even consider this was a source of potential errors.

I have changed my code to the following version, which uses doubles as little as possible, and seems to work just fine:

public static int ExtractQuarter(double dateAsDouble)
{
    int year = ExtractYear(dateAsDouble);
    int quarter = (int)(10 * dateAsDouble) - 10 * year;
    if (quarter < 1)
    {
        quarter = 1;
    }
    if (quarter > 4)
    {
        quarter = 4;
    }
    return quarter;
}

I am not sure this is the smartest way to deal with the issue - any suggestions are greatly appreciated! In the meanwhile, for me, the moral of story is that:

1) Write unit tests. For “any piece of code that has some form of logic in it, small as it may be” (The Art of Unit Testing).

2) Beware of floating point arithmetic!

One month to Silicon Valley Code Camp!

mathias — Mon, 07 Sep 2009 13:14:36 -1300

It’s that time of the year again: Silicon Valley Code Camp is coming up on October 3rd and 4th, at Foothill College. If you live in the Bay Area and like to talk code, this is an event you don’t want to miss. The previous editions rocked, and this year looks like it’s going to rock even harder, with well over 100 sessions and close to 1,000 registered! Oh, and did I mention it’s free?

This year again, I will give an introduction to Test-Driven Development for .NET developers. It’s a topic which is dear to my heart; in his book on TDD, Kent Beck says that it “is a way of managing fear during programming”, and I have to say that my life as a developer got significantly more peaceful after reading it. I can’t guarantee that you will feel the same, but I’ll do my best to share the goods!

The session is targeted for beginners. My goal is to get you quick-started so that you are ready to use it when you leave the room. I will write some code live, to show the methodology in action, using only tools you can get for free. This year, I think I will focus mostly on NUnit and keep it to a minimum on the tools provided in Visual Studio, unless there is strong popular demand; hopefully this will give me enough time to squeeze in a few minutes on mocks. I also just ordered Roy Osherove’s “The Art of Unit Testing”, which looks very promising, and may push me to modify my plan a bit.

I hope to see you there – and if you have questions or suggestions, let me know in the comments section!

More What-If analysis with Excel Data Table

mathias — Thu, 03 Sep 2009 17:50:37 -1300

In my last post, I illustrated how to quickly to pick the best value from a selection to get the optimal result, by using Excel Data Tables. This time, we will see how to pick the best possible pair of values.

We are trying to figure out which 2 bridges we should build, in order to minimize the overall travel time for the inhabitants of the island.

I worked out the math for one bridge last time. We will start we a similar setup, but adjust our spreadsheet so that for each islander, we compute the travelling distance for 2 bridges, and select the shortest route.

The ranges B1 and B2 are named Bridge1 and Bridge2. Column I now contains the formula computing the shortest route for each islander. For row 5 for instance, the formula is

=MIN(D5+E5-H5,F5+G5-H5)

Cell I10 is the total of the vertical distances travelled by each individual.

We can select from 4 bridge locations: 2, 4, 7 and 12. What we need is to find out which 2 numbers give us the lowest total travel. Let’s build our data table, this time using 2 bridge positions.

Our first bridge can be located at either 2,4,7 and 12:

Our second bridge can have the same positions:

In the upper-left corner, we specify what value we are interested in. What we want is the total travel distance, so we simply set cell A13 to =I10, the total travel distance:

Almost done. Now we select the entire table A13:E17, go to What-If Analysis, and select Data Table. In the pop-up window, we select B2 as the Row input cell, so that the row of values in B13:E13 corresponds to the second bridge location, and B1 as the Column input cell, so that Bridge1 positions will be selected from the values in A14:A17.

Once we select OK, the table fills in with the corresponding distances:

Looking into the table, we see that the lowest value is achieved for one bridge in position 4, the other one in position 12 – the bridges labeled “One” and “Third”.

We could even check if we could do any better, by trying out every possible bridge, including the ones which were not proposed. We would build a table like the following:

I highlighted the original 4 options. Looking into the table, we can see that there is no better solution – but three other solutions are just as good. The 4 optimal solutions are (4, 11), (4, 12), (5,11) and (5,12).

The data table approach is a bit of an overkill for the specific problem at hand. After all, there are only 4 x 3 x 2 x 1 = 24 options, and it would be feasible to just try them all by hand. However, if you started from scratch and wanted to figure out the best option, that would be 12 x 11 x 10 x 11 possibilities, and checking all 11,880 by hand would turn out to be a serious headache…

It’s interesting to see how the 2-bridges solution differs from the 1-bridge solution. The best single bridge is bridge “Two”, which is more or less in the middle – an average solution which is great for no one, but a decent compromise. The 2-bridge solution picks more extreme locations, serving better specific sub-groups. In a sense, this is similar to picking up a team. If you have a team of one, you would probably pick someone average, with no glaring weakness. If you can pick two, you’ll probably try to mix it up, and select team mates complementing each other, and compensating each other’s weaknesses.

One thing I like about data tables is that it is a good option for small discrete choices problems. The solver (or goal seek) are well suited to optimize for continuous values, but have issues dealing with problems were the solutions are a set of pre-determined values – and data tables handle these well. On the other hand, data tables won’t go beyond 2 values, which is a clear limitation. What if you had to pick the 3 best bridges?

This question actually got me thinking, so here it is a bonus problem. If you could build as many bridges as you wanted, in any location, where should you build them? To be more specific, what is the minimum number of bridges you should build so that everybody’s travel distance is minimal? I started playing with the question, and couldn’t find a satisfactory answer yet, but if I do, I’ll share. Hints and ideas appreciated!

Find an optimal solution with Excel Data Table

mathias — Fri, 28 Aug 2009 17:54:45 -1300

In the current issue of OR/MS Today, I came across this nice optimization puzzle, “Bridges to Somewhere”. There are these two islands. Five people A, B, C, D and F live on the first island, and need to commute to work to the second island. Individual A lives in the spot marked A, and needs to go to spot A on the second island – and so on for the 4 others. People can travel only vertically and horizontally (no diagonals), and will always take the shortest path available.

There is currently no bridge between the islands, but a budget for 2 bridges has been approved (the island just received a stimulus package). There are 4 bridge proposals to chose from (One, Two, Three and Four on the map). Which 2 bridges should be built to minimize the travel distance of the population?

Before trying to figure out which 2 bridges are best, I thought it would be interesting to investigate a simpler problem: if you could build one bridge anywhere, where should you build it?

There are a number of ways you could resolve this using Excel; I will illustrate how to find the best solution, using Excel Data Tables.

Good bridges, bad bridges

What makes a bridge better or worse for an islander?

see more Fail Blog

First, note that no matter where the bridge is located, C (who I will call Charlie) needs to travel the same distance horizontally (8 squares, or 7 moves). What this means is that the horizontal position of each individual doesn’t matter: the only thing which matters is where the bridge is located, on the vertical axis.

Then, any bridge located in the yellow rectangle is optimal for Charlie, who needs to travel only 4 squares down, and 8 squares right. Bridges which are located outside the bounds of the rectangle require extra vertical travel – in our example, an extra 3 squares up and 3 squares down.

Working the math, you can check that the extra travel a bridge requires from Charlie can be written as

Extra Travel = vertical distance from home to brige + vertical distance from work to bridge – vertical distance from home to work.

In our example, the Good bridge has an extra travel of 3+1-4=0 (no extra travel required), and the Bad bridge has an extra travel of 3+7-4=6.

The best bridge

Using this formula, we can now compute the extra cost of a bridge for each islander, and set up a worksheet to compute the total extra travel for each possible bridge.

In cell B1, we enter the vertical position of the bridge, and name the range “Bridge” (I am using the coordinates that are on the first map).

In range B4:C8, we enter the vertical position of the home and workplace of each of the 5 islanders.

In columns D and E, we compute the vertical distance from home and work to the bridge as shown, and we compute the vertical distance from work to home in column F.

In column G, we compute the extra travel as G4 = D4+E4-F4, and we compute the total extra travel in G9. Entering various values in B1 will show you the value of each possible location of the bridge.

You could now use a variety of approaches to find the best solution, from trying out all solutions manually, to using the solver. I’ll illustrate how you could find the optimal solution using Data Table, one of the What-If Analysis features of Excel.

In a nutshell, a Data Table allows you to specify a range of values, and record the result of a formula in your worksheet using each of them as an input.

What we will do here is try every possible location for a bridge, from 1 to 13, and record the Total Extra Travel for each scenario. First, let’s create the range of locations we want to try out:

Then, one column to the right, and one row above the input values, let’s set the formula we want to evaluate. In this case, I want to see the impact on the total extra travel, so that’s what I will set it equal to.

Next, select the range containing your input values and the formula:

Almost there! Let’s go to Data Table in What-If Analysis…

Your input data is organized in columns, so use “Column Input Cell”, and select B1, the bridge location, which is the input value you want to replace.

Press OK, and voila! Range B12:B24 has now been filled with data, which are the extra cost computed for each possible bridge value.

If you had one bridge to build only, you should locate it at position 7 or 8, which have the lowest extra travel for the population. Neat, no? In this example, this approach is probably not much faster that trying out various solutions by hand, but if there were more possible locations (and a less obvious solution…), this would prove very handy.

Next time, we’ll see how we would go about figuring out which 2 bridges are best!

Create an Excel Line – Column combination chart in C#, revisited

mathias — Thu, 20 Aug 2009 05:55:24 -1300

I wrote a post a few days ago describing how to generate a Line – Column chart in Excel through C#. And then a few things happened. Jon Peltier proposed a much nicer approach, I realized that my code worked for Excel 2003 but not Excel 2007, and someone asked for my code, “Jon-Peltier style”. So here we go: assuming your chart has more than one series, and you want the second series to be formatted as a line, all the rest as columns, you would do something like this:

// Create your chart object first
// formatted as column
Chart chart = ExcelCharts.AddChart(targetWorkbook, “my chart”, “the chart title”, XlChartType.xlColumnClustered, dataRange, XlRowCol.xlRows);
// Select the second series and make it a line
Series series = (Series)chart.SeriesCollection(2);
series.ChartType = XlChartType.xlLine;

Here is a simplified version of my AddChart method, which creates the base chart. Nothing fancy, but gets the job done.

public static Excel.Chart AddChart(Workbook workbook, string chartSheetName, string title, XlChartType chartType, Range dataRange, XlRowCol byRowOrCol)
{
    Excel.Chart chart;
    chart = (Excel.Chart)workbook.Charts.Add(Type.Missing, Type.Missing, Type.Missing, Type.Missing);
    chart.ChartType = chartType;
    chart.Location(XlChartLocation.xlLocationAsNewSheet, chartSheetName);
    chart.SetSourceData(dataRange, byRowOrCol);
    chart.HasTitle = true;
    chart.ChartTitle.Text = title;
    return chart;
}

As an aside, I was not happy with myself when I realized the code didn’t run on Excel 2007. I tend to write Excel-related code against Excel 2003 first, assuming it is the smallest common denominator and will likely work with Excel 2007 – but this is a perfect illustration that while it will typically be correct, it will sometimes fail, sometimes in very unexpected and trivial places, like in this example. Moral of the story: as Lenin allegedly said, “Trust is good, control is better”…