Skip navigation

Once in a while I get deathly bored of writing business code all day long and am in desperate need of some programming puzzle.  One of the sources I use is the webpages for some of the courses I TA’d for during my college years.  The entry level programming courses usually feature algorithmically interesting problems and I like to see how easily (or how not-so-easily) I can implement the solutions.

The most recent challenge I implemented was this – find the “minimum snippet” of a text source that contains all the “search terms.”

The requirement here is better described this way: create a function that returns all substrings of a source string which contain all of a set of possible substrings.

I used C# and LINQ, and it took me about an hour from start to finish – that includes debug time and testing.

At first I figured the problem was trivial – a few loops and some string.Substring functions would do it.  But as I began to think about it a little harder I realized that it isn’t as easy as it sounds if you have more than one search term.

I believe this can probably be done in a single line by constructing the right regular expression, but I decided not to implement it that way because it would defeat my purpose.  I wanted a programming challenge, not to spend an afternoon looking up RegEx syntax.

I started thinking about the problem in terms of numbers and positions.  Given a source string of length n and up to m search terms, you can produce a sequence of indexes into your source string, one index for position where one of the m search terms exist.  At first glance this suggests that at most you’d have n indices, because the very first thing you’d do is ensure that your search terms are not duplicated.

But this is actually not the case.  Imagine a source string of “baa baa black sheep”.  Suppose I search for “b” and “ba”.  I would produce index 0 and index 4 twice, because both “b” and “ba” occur at these positions.

This means that in the worst case, you have n * m total indices, which is a bummer, because m is not necessarily smaller than n (although it would probably be fair to invalidate input where m is larger, because it doesn’t make sense.  You can’t really legitimately search for more substrings than there are letters in the string).

Still, knowing where the search terms occur is a good way to start, because otherwise you can fall into the trap of assuming that the search terms have to be ordered – that is not a requirement of the function.  We must return all substrings that contain all the terms, regardless of which order the terms occur.

However, producing a flat list of positions where any search term occurs is no good either.  We need to produce substrings that contain each term and it is easily foreseeable that a single search term will be repeated many times.  If we produced just a set of positions in the string and didn’t associate them with the search term that exists there, we wouldn’t be able to protect ourselves from duplication.

So I started by essentially looping through each search term and, for each search term, producing a set of indices where that term appears in the source string.   I did this by creating an extension method on string to return an enumeration of all indices of a substring.  I did this using a while loop and a yield return.  In reality, this is a method I had implemented a long time ago that did this, part of my standard C# extension method toolkit.

So I used LINQ to select the set of indices of each m on the source string, which produced me a set of sets of integer.

This algorithm is now simple.  Produce all tuples which contain one member from each set.  In other words, combine them.

The requirement of the project is to produce only the minimum string as fast as possible.  I thought about using a type of greedy algorithm that would go something like this:

Pick an index from the first set, call it a.  Search all other sets for b, which is picked by being closest in position to a (either greater or smaller).  Search the remaining sets for c, which is picked again by having the minimum impact on the resulting length of the string.

The way we pick the “best” item from the remaining sets is by adding it to your existing set of “best” items, then sorting this set, and then subtracting the smallest value from the largest one.  This gives us the distance between the starting position of the first term and the starting position of the last term.  If we don’t know which set our new candidate item is coming from we can’t make this calculation right, because we’re trying to find the minimum string, and that string must include the search term.  If we don’t add the length of the search term to our distance calculation that we can produce bad results.

For example, consider the string “abcdefghijklmnopqrstuvwxyz”, with search terms “a”, “g”, and “efghijk”.  If I use my greedy algorithm without considering the length of the search term, then “abcdefg” would be considered longer than “abcdefghijk” because “efghijk” occurs at position 4 (“e”) and “a” occurs at position 0, and “g” occurs at position 6.  Since 4-0 is less than 6-0, we’d compute our distance wrong.

Once we have produced a candidate minimum length string using the first index in the first set, we now repeat this algorithm for every other index in the first set.  But, at every step, we compare the length we compute for each candidate against the length we’ve already computed.  As long as our length is less than our current best candidate we keep processing.  As soon as our new index causes our candidate to become longer, we abandon that index and don’t process any other sets that include that index.  If we arrive at the last set and find an index that when added to the candidate produces a length shorter than our current best, our new candidate becomes our current best and we repeat until we’ve exhausted all of the starting indexes in the first set.

The resulting best candidate is our result.

In reality, I didn’t implement this algorithm because while it satisfies the CMSC 132 assignment in the best way, it isn’t as useful as a general purpose function, so I wrote a progressive algorithm which returns all possible substrings and simply returns them in order from shrotest to longest.  In big(O) world it’s equally efficient because in the worst case you won’t find the best candidate until you’ve searched every possible combination.  I’m sure there are ways to tweak the above algorithm using some fancy sorts to eliminate a lot of the possible indices to reduce the worst case scenario, probably to something like O(n log n). 

The project challenges students to come up with an O(n) solution “assuming the number of search terms is constant”.  I believe this algorithm satisfies it that requirement but I’m not going to go about proving it.

It was fun to implement and I can see this being pretty challenging for newbie programmers, having worked with them for as long as I have.  I’m glad to see a CS degree still means something.

Advertisements

Whoever designed the imaging framework for WPF needs to be fired.  In fact, that person, or that team of people, needs to retire from computing.

“Pack URIs”?  Seriously?

Images are so easy in the WinForms world.  You add them to your resx file using a nice, already developed UI.  Then you use the internal class created for your resource file, access the image by name, and you get a usable instance of the System.Drawing.Image class that you can assign anywhere WinForms needs an image.

I have spent more than four hours trying to figure out how to set the icon on a ribbon menu item from a resource I’m including in my assembly.  I am not closer to a solution than when I started.

I won’t divulge my hourly rate but let’s put it simply: my employer is paying dearly for this epic blunder.

Today I ran into this:

stsadm -o copyappbincontent

Object reference not set to an instance of an object.

Thanks, Microsoft.

Turns out that stsadm blows up if you put a webconfig.*.xml file in your CONFIG directory with an XML comment inside, like <– blah –>

So, don’t do that.

I’ve spent a few hours trying to unravel SharePoint’s rather scarcely documented schema.xml definition for custom list templates deployeed in features, specifically the <Views> element.

The task: I wanted to render a column in the view that was not based on a field, which as you know, comes from the list values (which come from the database).  In effect, I wanted to create a kind of custom-calculated column.  The “calculation” was an external link to a configurable server URL based on one of the fields in the list.

This was actually easier than I expected.  You need to locate the <View><ViewBody> portion of the schema.xml.  The weirdness comes from the <Fields> element.  As is noted in the Microsoft docs, when the parser comes through and hits the <Fields> element, it treats it as the opening of a loop that essentially says foreach(Field f in list.Fields).  You can render the field in its default manner by using the empty tag <Field/>, so for example in the default view definitions you can copy from the standard SharePoint lists, the body of the <Fields> element is little more than wrapping a <Field> element in some <td> tags to make the columns in table.

If you want to add another column to the end of the table, you are going to want to add a <td> tag after the </Fields> tag (after the loop).  But how do you display a single <Field> value outside of the <Fields> element?

The answer is, I’m pretty sure you can’t.  But what you can do is put a second <Fields> tag in the <ViewBody> tag, and you can use <FieldSwitch> to render only one field.

You do it like this:

         <Fields>
            <FieldSwitch>
              <Expr>
                <Property Select=”Name” />
              </Expr>
              <Case Value=”YourFieldName”>
                <Column/>
              </Case>
            </FieldSwitch>
          </Fields>

As you may know, each field has a collection of properties associated with it.  In the SP Object Model you would get property values by saying list.Fields[“YourFieldName”].GetProperty(“PropertyName”).  In this case, the <expr><property> combo is indicating that you want to compare a field’s “Name” property, and the <Case Value=”YourFieldName”/> means you want to render everything inside the <case> tag when the field’s Name property equals “YourFieldName”.  Pretty straightforward, right?  (By the way, <Column /> is shorthand to render the raw value of the field).

The only problem is that a field’s name according to all of SharePoint’s user interface is actually not its name – it’s its DisplayName property.  For example, the column headers you see at the top of the list are referred to as the field’s name when you modify a list’s columns in the Modify View page, but if you try to use the XML above – namely, select a field based on its Name property by matching <case Value=”YourFieldName”>, nothing will work.  In other words, if the column’s header text is “YourFieldName”, using the above xml snippet just won’t work.

Weird, huh?

In order to figure out what I was doing wrong, I had to set a breakpoint where I could probe my SharePoint list object and figure out what my field’s name was if it wasn’t “MyFieldName”.

Turns out it was “_x0036_F80E0E2_x002d_1798_x002d_”.  Of course.

There’s actually a hint in the SP Object Model API that a field’s “name” for UI purposes is actually not it’s name for API purposes.  Look at this prototype for SPFieldCollection.Add:

C#
public string Add (
    string strDisplayName,
    SPFieldType type,
    bool bRequired
)

A-ha.  A clue.  It turns out that correct property name to use is DisplayName.  We modify our schema.xml this way:

         <Fields>
            <FieldSwitch>
              <Expr>
                <Property Select=”DisplayName” />
              </Expr>
              <Case Value=”YourFieldName”>
                <Column/>
              </Case>
            </FieldSwitch>
          </Fields>

And like magic, it works like a charm.

Don’t let this one bite you – it took me a few hours of trial and error before I finally figured this one out.

So, I’m trying to figure out if an Excel Workbook is Read Only.

So I grab my Workbook from Application.Workbook and it has a property called ReadOnly.

I write a line of code like if (Application.Workbook.ReadOnly == false) { … }

Compiler error!  What?  Can’t convert type ‘bool’ to type ‘MsoTriState‘?  Of course I can’t.

Turns out ReadOnly (and most other properties that should be bools in the Workbook class) are not bool, but are instead an enum called MsoTriState.  Makes sense.  I figured this was probably a holdover from the days before .NET had invented nullable value types.

There’s only one catch.

MsoTriState – which from the tri in its name you might conclude has 3 states – actually has 5 states: msoCTrue, msoFalse, msoTriStateMixed, msoTriStateToggle, msoTrue.

Now because today isn’t the first time Evan has gotten burned, Evan decided rather than assume the obvious which would be to use the msoFalse and msoTrue enumeration values, Evan would consult the documentation first.

To my horror, I see this table:

Member name Description
msoCTrue Not supported.
msoFalse False.
msoTriStateMixed Not supported.
msoTriStateToggle Not supported.
msoTrue True.

So let me get this straight.  The ReadOnly property is not a 2 state true/false bool, it’s a 3 state MsoTriState enum, except the TriState is actually has five states, but only 2 of those states are supported.

*sigh*

The answer is: very rarely.

Method overloading is virtually always done so that the caller of the API can shortcut the parameters since the defaults are in use almost all of the time.  This allows the API consumer to be lazier.  However, for the API developer, this practice – being “good” to your API consumers – will cost you exponentially in the long run.

For write-and-flight consultant coders who work on code for 6 months and then disappear on their way to their next assignment, this isn’t as critical, but for anyone who actually maintains production code, finding unnecessary and excessive overloads is one of the signature callsigns of a coder who has never done exactly that.

The reason is simple.  Methods do not exist in vacuums.  They are called, often in a specific order in conjunction with other calls to other methods before and after – in other words, programmed – and when you suspect there may be a bug with regards to how your method is being used, the very first thing you want to do is get a clear picture of who is using your method and how.

If you have 5 overloads, you can’t do this – you have to find the uses of all 5 different overloads – and your work has just increased unnecessarily.

The best advice I can give to API developers contemplating overloads is this: unless the parameter set is wildly different and it would be extremely frustrating to your consumers to write the code themselves to translate one parameter set into the other (e.g., string and Stream), never include more than one public overload.

This will save you hours of time trying to figure out who’s calling what.

When you are designing a .NET class, always, always use properties.

Don’t create them just as a public accessor.  Wrap 100% of your fields – 100% of which should be private – in properties, even if the property itself is also private.

You should never refer to the field except inside the encapsulating property (including the constructor!  Use the property there, too!).

Before I even begin to point out why you should, I’ll address the immediate knee-jerk reasons why you’ll tell me I’m wrong.

1.  It’s a waste of time.  If you think this is true, you haven’t used Visual Studio long enough.  Right click on your private field and select Refactor, then select Encapsulate Field.  Done.

2.  It bloats the code.  If you think this is true, you haven’t used Visual Studio enough.  Click on the little bordered minus sign in the margin of your code to collapse the property.  You’ve added exactly 1 line to your class definition.  Woe is you!

3.  It’s inefficient.  In practically every place you use them, the C# compiler inlines them.  You were saying?

 4.  It’s non-intuitive from an API consumer’s perspective.  If you don’t have access to the member’s fields, then all you see are properties, which are actually more intuitive because the rest of .NET is written that way.  If you can see the member’s fields and you are following the “everything is private” rule, then you have access to the source code.  If you have access to the source code, then who wrote it, and why are you confused?  Plus, if your team is operating under these guidelines there’s actually less confusion, not more – the confusion would stem from finding a field that doesn’t have a property.

5.  If I make a public property for a field, I don’t want the set to be public, so I don’t include a set on the property and therefore must refer to the field internally.  You need to brush up on your C# – split protection level properties have been around since .NET 2.0.  It’s perfectly legal (although not as common as it should be) to declare a property as:

public string MyString{    get { return _myString; }

    private set { _myString = value; }

}

6.  It’s pointless.  If you have a private field and a corresponding private property that isn’t any more sophisticated than the Studio-generated encapsulator, then why bother?  I’ll get to that in a minute.

Can you think of any more?  I can’t.

Now, let’s discuss why it’s seriously advantageous to always use properties:

1.  Code safety.  When you are in the habit of always using properties, you always have the opportunity to inject logic surrouding the set and get logic of all the fields, which means part of the natural thought process during design is, “what should I do about nulls?” (among other things).  Once you create the property and you see that you have a method rather than just a field definition, you can surround the field with protective code that will ensure, for example, that if null is passed as the value parameter of your mutator, you don’t replace a list that is by definition always non-null with a null value – instead of assignment, you call the list’s Clear method.  This leads to measurable decreases in exceptions, most of which are hard to trace.

2.  Extensibility.  One of the major advantages of using properties is the ability to allow the data members to also be extensible in derived classes.  If you have a property that returns an IDictionary and your subclass wants to provide a different implementation (Hashtable vs. Red/Black tree, for example), you can override the property.  This is still possible with fields if you defined your field to be IDictionary instead of Dictionary (a rarity amongst most programmers), but it is trivial to come up with examples of times when you would want to be able to redefine the return value of a boolean property, for example.  The base class might just return a bool field, but if they wrapped it in a protected property, the subclass could return the result of a comparison instead of the field (or and it with the field) and the rest of the base class code (which also refers to the property instead of the field) doesn’t change.

3.  It’s so much easier to maintain.  If you use properties exclusively, you only have one “Find All References” search to do to see where your data is being used or manipulated.  If you use a mixmash of the field itself and its encapsulating property, you have to search in two places.  You are never sure if someone is going to use the property or the field so you have to check both, which makes everything you do harder.

4.  It’s so much easier to debug.  I could be accused of not using Studio again here because it is possible to set a breakpoint on a field so that if its value ever changes, your execution breaks and you can see the callstack.  I don’t know about you, but navigating to the property and hitting F9 on get{} and set{} takes me about 1/10th the time of setting up a conditional breakpoint on the value of a field.  If you always use properties everywhere, both internally and externally, and you are wondering “hmm, where does this get changed?”  just pop a breakpoint on the property’s set and reproduce.  It’s just that simple.

I’ll say it again: always use properties.

One of the biggest problems of the concept of null in modern programming languages is the choice API designers have to make between returning null or a conceptually empty object, for example string.Empty or new List<Type>();

On one hand, null is the obvious choice because it prevents wasting resources.  Creating an empty list each time a call returns no results is wasteful.  This can be averted by creating a static empty singleton (like string.Empty), but unless the object is immutable (as string is, or returning a ReadOnlyCollection) you can run into trouble here since the caller can modify the result.  Even this is wasteful when what you’re really trying to say is: “hey, I have no results to return.”  That’s what null means, isn’t it?

On the other hand, for the consumer of an API, even when the API author and the consumer is the same person, it’s hard to guess whether a method will return null or an empty object.  Even the .NET API authors struggle with this fact as evidenced by the string.IsNullOrEmpty static method, which is great for argument and return checking.  Since it’s hard to guess, most good programmers are in the habit of always checking for null first even when they know that the method will never return null because they wrote it.

The reason good programmers check for null religiously is because things change.  You may not be returning null today (in favor of an empty list) but tomorrow you may change your mind.  The problem with an API designer changing his mind is that he can’t predict whether or not the consumers of his API are properly checking for null.  As I said, good programmers will.  But what about the bad ones?

In my opinion, you should generally always return null instead of an empty object except with strings.  The reason for this is that it forces even the average programmer to check for null immediately.  A simple negative unit test will result in a a NullReferenceException.  There is no harm in returning null in version 1.0 and then changing it to return an empty object in version 2.0 but the reverse is deadly, because it has the potential of breaking all your consumers.  Checking for null is benign.  Making the assumption that the result of a method will never be null is an exception waiting to be thrown.

The exception to this rule for strings is because of the string.IsNullOrEmpty method.  Good programmers should rarely check strings of being null or empty independently.  Good APIs do not distinguish between the two in the majority of cases.  In some cases, null is different than empty – for example, in a login form, an empty string means an empty password, but a null password may imply an error occurred somewhere (or may imply integrated security, for which a password is unnecessary).  But generally, this distinction should be obvious from the context.

I would have expected an enterprise technology to be smarter than this.

 Want Team Foundation Server for free?  Install it and roll back your computer’s date 10 years.

 If you can tolerate your histories saying “1998” when it actually means “2008” then you have it for free.

 The idiot in charge of installing TFS at our location installed a trial and let it expire.  Since this precludes us from doing anything as basic as a task query or access our team portal, our entire development shop is offline… until I rolled the server’s clock back 1 week.

 You know, they say locks keep honest men honest, but having been involved in implementing concurrent user server-based licensing for our own product, I can tell you that the “rolling back the clock” is not even remotely hard to detect.  All you have to do is encrypt and hide a registry key (the COM registry is a wonderful place to stick something like this) that names the date you installed it, and also encrypt the date of the last login.  If the current machine date is earlier than either of these values, reject.

Anyways… in our situation we can’t really do this because we’d really corrupt our histories and it’s not worth the risk that TFS will go haywire if we have pre-dated checkins, but if we had known this from the start we could have pulled the 10 year trick.  Oh well.

This is a rant.  A brief rant.

How can any intelligent software developer think that throwing an exception when a key is not found with the [] operator is a good idea?

Come on.  The correct behavior should be that it simply returns null like every other collections API before (and hopefully after).

I should not have to write code like this:

object o = null; 

if (dictionary.ContainsKey(key) == true)  { o = dictionary[key]; }

Awful.