Author Archives: ericlippert

Unknown's avatar

About ericlippert

http://ericlippert.com

Producing combinations, part three

Posted on by
43

All right, we have an immutable stack of Booleans and we wish to produce all such stacks of size n that have exactly k true elements. As always, a recursive algorithm has the following parts:

  • Is the problem trivial? If so, solve it.
  • Otherwise, break the problem down into one or more smaller problems, solve them recursively, and aggregate those solutions into the solution of the larger problem

Let’s start with a signature. What do we have? integers n and k. What do we want? A sequence of Boolean stacks such that the size is n, and there are k bits turned on. We therefore require that n and k both be non-negative, and that n be greater than or equal to k. Continue reading →

Producing combinations, part two

Posted on by
69

Last time we saw that producing all the subsequences of a given size k from a given sequence of size n is essentially the same problem as computing all the sequences of n Booleans where exactly k of them are true. How do we do that?

An approach that I often see is “enumerate all sequences of n Booleans, count the number of on bits, and discard those which have too many or too few”. Though that works, it’s not ideal. Suppose we are seeking to enumerate the combinations of 16 items chosen from a set of 32. There are over four billion possible combinations of 32 bits, and of those over three billion of them have more or fewer than 16 true bits, so that’s a lot of counting and discarding to do. We can do better! To do so, we’ll use a combination of all my favourite techniques:

  • Immutable data structures
  • Abstract classes with derived nested classes
  • Recursion

Long-time readers of this blog will have seen me use these techniques before, but for new readers, a quick introduction is in order. Continue reading →

Confusing errors for a confusing feature, part three

Posted on by
9

One of the nice things about a project as large as the Roslyn project is that you have an opportunity to really think hard about your past mistakes and hopefully fix them. When I was working on getting these error messages reported in Roslyn I realized that trying to match exactly the behavior of the original compiler would be actively making the world a worse place, so I took a big step back and started sending a lot of emails to Mads, Neal, Anthony and the rest of the Roslyn gang to try and get a better design worked out. All the godawful nonsense I told you about in the previous two episodes will be fixed in Roslyn.

Continue reading →

Confusing errors for a confusing feature, part two

Posted on by
10

Last time I gave you the challenge to find a case where the same simple name means two different things, without introducing a new local/parameter/range variable into scope, that produces an error. It seems like it ought to be impossible; if nothing new has been introduced to a local scope then how can name resolution choose two different things? The relevant section of the C# specification (7.6.2.1 Invariant meaning in blocks) only gives the example I gave last time, of a local having the same name as a field.

The key to solving the riddle is a little-known rule about resolving a name from a set of possible class members: Continue reading →

Confusing errors for a confusing feature, part one

Posted on by
70

There’s a saying amongst programming language designers that every language is a response to previous languages; the designers of C# were, and still are, very deliberate about learning from the mistakes and successes of similar languages such as C, C++, Java, Scala and so on. One feature of C# that I have a love-hate relationship with is a direct response to a dangerous feature of C++, whereby the same name can be used to mean two different things throughout a block. I’ve already discussed the relevant rules of C# at length, so review my earlier posting before you read on.

OK, welcome back. Summing up:

  • C++ allows one name to mean two things when one local variable shadows another.
  • C++ allows one name to mean two things when one usage of a name refers to a member and a local variable of the same name is declared later.
  • Both of these features make it harder to understand, debug and maintain programs.
  • C# makes all that illegal; every simple name must have a unique meaning throughout its containing block, which implies that the name of a local variable may not shadow any other local or be used to refer to any member.

I have a love-hate relationship with this “unique meaning” feature, which we are going to look at in absurd depth in this series.
Continue reading →

ATBG: randomness

Posted on by
7

Today on the Coverity Development Testing Blog’s continuing series Ask The Bug Guys I’m turning it around and asking you to figure out why a seemingly correct and totally awesome implementation of random.Next has a serious bug. That’s right, it’s everyone’s favourite game, Spot the Defect! Can you figure out where I wrote a bug without running the program? Check it out.

Continue reading →

Melting aluminum

Posted on by
32

Today another in my ongoing, seldom-updated series of posts about building my own backyard foundry. Today I’ll describe how the final step works: actually melting and pouring the metal. First, see my previous post on how to make a green sand mold.

Start by assembling all the equipment you’ll need in one place, on a day with no chance of rain. (Click on any photo for a larger version.)

DCIM152GOPRO
Continue reading →