Programming: Love It Or Leave It?

Nice post here from Jeff Atwood:

Unless you're fortunate enough to work for a top tier software development company, like Google, Microsoft, or Apple, you've probably experienced first hand the huge skill disparities in your fellow programmers. I'm betting you've also wondered more than once why some of your coworkers can't, well, program. Even if that's what their job description says.

Over the last twenty years, I've worked with far too many programmers who honestly had no business being paid to be a programmer. Now, I'm not talking about your average programmer here. We're all human, and we all make mistakes. I'm talking about the Daily WTF crew. People that actively give programming a bad name, and you, as their coworker, a constant headache.

On the other hand, I would not go as far as Jeff when he states:

So if a programmer ever hints, even in passing, that they might possibly want to exit the field -- they probably should.

Some of the most talented people I know have had thoughts like this once in a while. And the reason was mainly one of two things: Horrible management mistakes or incompetent co-workers (or even worse, both).

Which brings us back to Jeff's original argument: Most programmers don't know how to program. And not only does that screw the associated work of the highly-skilled folks, it kills their motivation too.

If just more bozos would decide to leave the field, well - problem solved! Unfortunately they don't. As they are missing one of the most importat qualifications for this job, namely a healthy bit of self-reflection and the drive to improve, it's quite unlikely most of them have even noticed their deficiencies yet.

I was tempted to start another long rambling article on this whole topic, but instead of repeating myself let me just shortly refer to several of my older postings:

• Top Ten List Of Programming Perversions
• The Fallacy Of Cheap Programmers
• Handling The Bozo Invasion
• Hire The Right People
• Why Can't Programmers... Program?

Robin Sharp writes:

A lot of research on programmer productivity shows that the best programmers are up to 20 times more productive than the worst programmers. If the income differential between the best and worst programmers is even 5 times, it means employers are getting incredible value for money hiring the best programmers.

Why then don't companies hire a few very good programmers and leave the rest flipping Big Macs? There is one very good reason: the psychology of managers. Managers simply can't believe that one programmer can be as productive as 3, let alone 5 or even 20 times. Managers believe that productivity is a management issue.

They believe that simply by re-organising their human resources it is they who can gain leaps in productivity, and reap the rewards. But the reality of management, as we all know, is that most projects are late and over budget.

And from Jeff's older articles (Why Can't Programmers.. Program?, Skill Disparities in Programming):

In programming specifically, many studies have shown order of magnitude differences in the quality of the programs written, the sizes of the programs written, and the productivity of the programmers. [...] They studied professional programmers with an average of 7 years' experience and found that the ratio of intitial coding time between the best and worst programmers was about 20:1; the ratio of debugging times over 25:1; of program sizes 5:1; and of program execution speed about 10:1.

Unless you truly enjoy programming you should seek another profession. Be realistic: are you programming to collect a paycheck, or are you programming because you are driven to? I know this sounds harsh, but it's an economic reality-- in an enviroment of global offshoring, the world simply can't support any more highly paid mediocre coders. There are a hundred thousand well educated Indian developers who will do what you do at a fraction of the price, and thousands more coming of age in other third world countries. Blame the Internet if you want, but just being "good with computers" is no longer a free ticket to a high paying tech job.

Finally, here is a very good quote from the comment section on Jeff's site:

Actually most programmers are bad programmers. No really, they are. The problem is that everyone can be a programmer. This isn't true for other jobs. Not everyone can work as a lawyer or doctor for example. However nobody forbids you to work as a programmer, you don't need a special license, there is no mandatory education either. If a company hires you as a coder, no matter if you ever had any education on this matter or not, you work as a coder; period. And this itself is not even bad. Some of the best coders on earth never had any education in computer science, still they are brilliant coders. However, many people had no education and are just horrible coders.

Disappearing Permissions On MS Team Foundation Server 2008

We had just finished migrating one of our Team System projects from TFS 2005 to a new TFS 2008 machine, when we suddenly noticed that all Team Foundation Server group permissions that had been set on certain project folders via Properties / Security would not show up in the Security tab the next time the Property dialog was opened. The funny thing is - the permissions themselves seemed to work! There was just no way to view, edit or remove them. Same was true for the tf.exe commandline tool ("tf permission ...") - it did not list any existing permissions.

After hours of internet research I finally found this posting. And sure enough, after checking which .NET 3.5 Framework servicepack level was installed on the server (SP1 in our case), and identifying the Team Foundation Server 2008 servicepack level (TFS 2008 RTM, which is not so easy to find out and includes checking the assembly version number of Microsoft.TeamFoundation.Server.dll located in %PROGRAMFILES%\Microsoft Visual Studio 2008 Team Foundation Server\Web Services\Services\Bin (simply google the version number to obtain the release definition)), we had confirmation that it was really that combination of product releaes which caused the group permissions to not show up.

It's highly recommended to have matching .NET Framework and Team System releases installed side-by-side (.NET 3.5 SP1 and TS 2008 SP1 in this example).

Nietzsche On Software Development

What we do is never understood, but only praised and blamed.

(Friedrich Nietzsche)

Update And Quotes On Programming

It has been a while since my last posting. We are currently starting a new project and I deeply buried myself into some technology evaluation. So for the meantime, just some random thoughts...

• How come there is no usable Database-to-HBM/POCO reverse engineering tool for NHibernate out there? I must have tried five or six of them, some didn't work at all (but one Visual Studio Add-In screwed my IDE altogether), some managed do produce some kind of output, but were missing essential parts like relationship definitions, etc. I am really tempted to write one on my own.


• Entity Framework is nice from an API point of view, but lacks some first-class support for disconnected / n-tier scenarios (yes you can detach entities, but it gets kind of complicated when re-attaching them including change state).


• Microsoft's new IoC-framework Unity is a big step ahead in comparison to ObjectBuilder. Nice IoC core. Spring.NET is another IoC framework out there, and includes an additional feature stack: support for AOP (e.g. declarative transaction management), NHibernate, Quartz.NET, etc.

I especially like .NET 3.5, Visual Studio 2008 and Team System. Great stuff. WPF is outstanding - what an improvement in productivity!

I am also involved in some old legacy projects. I don't want to go into much detail, but can only reinforce the importance of:

• Plan for the future, choose wisely which path to take both in a microcosm of software components as in the realm of the whole project.


• Avoid mistakes at the beginning, or pay for them big time later.


• People make products. No tools, no process model, no extra hours will counterbalance for poor staffing.

Time and time again I am amazed by the difference in developers' productivity and the variance in code quality. I wonder why our profession is so prone to that dilemma?

These quotes from a stackoverflow.com thread might provide some further insights:

"A computer lets you make more mistakes faster than any other invention in human history, with the possible exceptions of handguns and tequila."

"There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult."

"The trouble with programmers is that you can never tell what a programmer is doing until it's too late."

"Most software today is very much like an Egyptian pyramid with millions of bricks piled on top of each other, with no structural integrity, but just done by brute force and thousands of slaves."

"It is practically impossible to teach good programming style to students that have had prior exposure to BASIC. As potential programmers, they are mentally mutilated beyond hope of regeneration."

"Three virtues of a programmer:

Laziness - The quality that makes you go to great effort to reduce overall energy expenditure. It makes you write labor-saving programs that other people will find useful, and document what you wrote so you don't have to answer so many questions about it. Hence, the first great virtue of a programmer. Also hence, this book. See also impatience and hubris.

Impatience - The anger you feel when the computer is being lazy. This makes you write programs that don't just react to your needs, but actually anticipate them. Or at least pretend to. Hence, the second great virtue of a programmer. See also laziness and hubris.

Hubris - Excessive pride, the sort of thing Zeus zaps you for. Also the quality that makes you write (and maintain) programs that other people won't want to say bad things about. Hence, the third great virtue of a programmer. See also laziness and impatience."

"Any fool can write code that a computer can understand. Good programmers write code that humans can understand."

ADO.NET Entity Framework Vote of No Confidence?

Several MVPs and other .NET Entity Framework testers (partly from the NHibernate camp) signed an open letter some weeks ago describing their concerns on some design decisions and the current state of what is about to become version 1.0 of the ADO.NET Entity Framework. Here is Microsoft's Tim Mallalieu's response.

Now I won't pretend to be an expert on Entity Framework (I spent two or three days playing around with it). I do have some Hibernate experience though (admitted, in the Java space). So this clearly qualifies me to throw in my 5 cents too, now doesn't it? ;-)

Here is what I think:

INORDINATE FOCUS THE DATA ASPECT OF ENTITIES LEADS TO DEGRADED ENTITY ARCHITECTURES
To be honest, my Hibernate POJOs never contained any logic code, they were plain data holders. This was a design decision that always worked fine for me, even if luminaries like Martin Fowler tend to criticize it. I think the requirement to combine data and logic code in entity objects, although comprehendible from an OOP perspective, is kind of overrated. Anyway one can still place that code in partial classes, what else can we ask for? What might be problematic in some application scenarios is that entity classes are linked to the whole Entity Framework by inheritance and code. They cannot exist "standalone" (e.g. in another tier without EF being around). One alternative are dynamic proxy classes being generated at runtime, but they have some drawbacks as well.

EXCESS CODE NEEDED TO DEAL WITH LACK OF LAZY LOADING
Once again, some people can't live without lazy loading. But lazy loading also might open a can of worms, e.g. in distributed environments like the ones I have to deal with. LazyInitializationException, anybody? I mostly prefer other loading strategies, like "Join Fetch". It boils down whether you (A) want to abstract the fact that there is a SQL database behind the hoods and only want to work on a cloud of objects or (B) the reason you use an ORM is to prevent tight coupling, database dependency and writing loads of mapping, routine SQL and infrastructure code (transaction management, etc) on your own, but still need to be in control of when and how data access actually happens. I am more of kind (B). EntityCollection.Load is just fine for me!

SHARED, CANONICAL MODEL CONTRADICTS SOFTWARE BEST PRACTICES
In this case the "best practice" depends on the type of application one is building. Nobody is being forced to have only "one model to rule them all" - one can as well apply the EF model within a single layer only.

LACK OF PERSISTENCE IGNORANCE CAUSES BUSINESS LOGIC TO BE HARDER TO READ, WRITE, AND MODIFY, CAUSING DEVELOPMENT AND MAINTENANCE COSTS TO INCREASE AT AN EXAGGERATED RATE
While I agree that PI-support is desirable in this area, this is not really a killer argument in my current project scenario. And from what I have heard this issue is going to be addressed in EF V2.

EXCESSIVE MERGE CONFLICTS WITH SOURCE CONTROL IN TEAM ENVIRONMENTS
This is true, that was one of the first things I noticed when I got introduced to the Entity Framework.

But hey guys, this is only version 1.0 of the Entity Framework. To me it still looks promising. Please keep up the good work. And you have a Vote of Confidence from me!

Battleship Game Algorithm Explained (Part 4)

This is part 4 of the mini-series explaining the inner workings of the Cubido C# Pirates Winner Algorithm.

Please note:

This code was not optimized for speed and has plenty of potential for performance improvement, esp. regarding nested looping. The competition rules included an upper time limit of 500ms per shot. This implementation runs at 1ms per shot in average, so there was no point in tuning that esp. as readability might have suffered.

The algorithm does not take into consideration opponents' behavior. The C# Pirates competition environment itself placed the ships randomly, and did not provide state storage on any larger scope than a single game, so it was not possible to react on opponent's behavior when shooting, or on different ship placement strategies.

Here is the resulting sourcecode:

using System;
using System.Collections.Generic;
using SoftwareArchitects.Battleships;

namespace Battleships
{

  [Player(Name = "The Privateer")]
  public class ThePrivateer : Player
  {
    private class ShipPositionOption
    {
      private int free;
      private bool done;
      private Direction dir;
      private Coordinates nextCoord;

      public ShipPositionOption(Direction posDir)
      {
        dir = posDir;
        free = 0;
        done = false;
        nextCoord = null;
      }

      public void Reset()
      {
        free = 0;
        done = false;
        nextCoord = null;
      }

      public void MarkInvalid()
      {
        free = 0;
        done = true;
        nextCoord = null;
      }

      public Coordinates NextCoord
      {
        get { return nextCoord; }
        set { nextCoord = value; }
      }

      public int Free
      {
        get { return free; }
        set { free = value; }
      }

      public bool Done
      {
        get { return done; }
        set { done = value; }
      }

      public Direction Dir
      {
        get { return dir; }
      }

    }

    private class Direction
    {
      private Orientation orient;
      private int dX;
      private int dY;

      public Direction(Orientation or, int x, int y)
      {
        orient = or;
        dX = x;
        dY = y;
      }

      public Orientation Orient
      {
        get { return orient; }
      }

      public int DX
      {
        get { return dX; }
      }

      public int DY
      {
        get { return dY; }
      }
    }

    private class SinkTryResult
    {
      private Direction dir;
      private Coordinates sinkCoord;

      public SinkTryResult(Coordinates sinkCoordParam, Direction dirParam)
      {
        sinkCoord = sinkCoordParam;
        dir = dirParam;
      }

      public Coordinates SinkCoord
      {
        get { return sinkCoord; }
        set { sinkCoord = value; }
      }

      public Direction Dir
      {
        get { return dir; }
        set { dir = value; }
      }
    }

    private enum Orientation : int
    {
      EAST = 0,
      WEST = 1,
      NORTH = 2,
      SOUTH = 3
    }

    private enum Mode { ScanMode, SinkMode };

    private static readonly IDictionary<Orientation, Direction> DIRECTIONS = new Dictionary<Orientation, Direction>();
    private const int FIELD_DIM_X = 10;
    private const int FIELD_DIM_Y = 10;

    private const int EAST_IDX = (int)Orientation.EAST;
    private const int WEST_IDX = (int)Orientation.WEST;
    private const int SOUTH_IDX = (int)Orientation.SOUTH;
    private const int NORTH_IDX = (int)Orientation.NORTH;

    private Random rnd = new Random();
    private Mode mode = Mode.ScanMode;
    private Coordinates sinkCoord = null;
    private bool[,] impossibleCoords = new bool[10, 10];

    private int seekedShipSize = 5;
    private int hitCount = 0;

    private int[] sinksRequired = new int[] { 0, 0, 1, 2, 1, 1 };

    static ThePrivateer()
    {
      DIRECTIONS[Orientation.EAST] = new Direction(Orientation.EAST, 1, 0);
      DIRECTIONS[Orientation.WEST] = new Direction(Orientation.WEST, -1, 0);
      DIRECTIONS[Orientation.SOUTH] = new Direction(Orientation.SOUTH, 0, 1);
      DIRECTIONS[Orientation.NORTH] = new Direction(Orientation.NORTH, 0, -1);
    }

    public ThePrivateer()
    {
    }

    public override void Move(PlayingField playingField)
    {
      if (mode == Mode.ScanMode)
      {
        Coordinates coord = GetNextScanCoord(playingField);
        if (playingField.Fire(coord.X, coord.Y) == State.HitShip)
        {
          sinkCoord = coord;
          mode = Mode.SinkMode;
          hitCount = 1;
        }
      }
      else if (mode == Mode.SinkMode)
      {
        SinkTryResult sinkTry = GetNextSinkTry(playingField);

        State res = playingField.Fire(sinkTry.SinkCoord.X, sinkTry.SinkCoord.Y);

        if (res == State.HitShip || res == State.SunkShip)
        {
          sinkCoord = sinkTry.SinkCoord;
          hitCount++;

          if (res == State.SunkShip)
          {

            sinksRequired[hitCount] = sinksRequired[hitCount] - 1;

            int sunkX = sinkCoord.X;
            int sunkY = sinkCoord.Y;

            for (int i = 0; i < hitCount; i++)
            {
              SetImpossibleCoord(sunkX - 1, sunkY - 1);
              SetImpossibleCoord(sunkX - 1, sunkY);
              SetImpossibleCoord(sunkX - 1, sunkY + 1);
              SetImpossibleCoord(sunkX, sunkY - 1);
              SetImpossibleCoord(sunkX, sunkY);
              SetImpossibleCoord(sunkX, sunkY + 1);
              SetImpossibleCoord(sunkX + 1, sunkY - 1);
              SetImpossibleCoord(sunkX + 1, sunkY);
              SetImpossibleCoord(sunkX + 1, sunkY + 1);

              sunkX = sunkX - sinkTry.Dir.DX;
              sunkY = sunkY - sinkTry.Dir.DY;
            }

            while (seekedShipSize > 0 && sinksRequired[seekedShipSize] == 0)
            {
              seekedShipSize--;
            }

            hitCount = 0;
            sinkCoord = null;
            mode = Mode.ScanMode;
          }
        }
      }
    }

    private ShipPositionOption[] CreateShipPositionOptions()
    {
      ShipPositionOption[] options = new ShipPositionOption[4];
      options[EAST_IDX] = new ShipPositionOption(DIRECTIONS[Orientation.EAST]);
      options[WEST_IDX] = new ShipPositionOption(DIRECTIONS[Orientation.WEST]);
      options[SOUTH_IDX] = new ShipPositionOption(DIRECTIONS[Orientation.SOUTH]);
      options[NORTH_IDX] = new ShipPositionOption(DIRECTIONS[Orientation.NORTH]);
      return options;
    }

    private Coordinates GetNextScanCoord(PlayingField playingField)
    {
      ShipPositionOption[] options = CreateShipPositionOptions();
      Coordinates bestCoord = null;
      int bestCnt = 0;
      int bestNeighborFact = 0;
      bool bestMatching = false;

      for (int x = 0; x < FIELD_DIM_X; x++)
      {
        for (int y = 0; y < FIELD_DIM_Y; y++)
        {
          if (IsUnknown(playingField, x, y))
          {
            int cnt = 0;
            int neighborFact = 0;

            for (int shipSize = 0; shipSize < sinksRequired.Length; shipSize++)
            {
              if (sinksRequired[shipSize] > 0)
              {
                for (int optIdx = 0; optIdx < options.Length; optIdx++)
                {
                  ShipPositionOption option = options[optIdx];
                  option.Reset();
                  for (int d = 1; d < shipSize && !option.Done; d++)
                  {
                    if (IsUnknown(playingField, x + d * option.Dir.DX, y + d * option.Dir.DY))
                    {
                      option.Free = option.Free + 1;
                    }
                    else
                    {
                      option.Done = true;
                    }

                  }

                }
                int cntHor = Math.Max(0, options[EAST_IDX].Free + options[WEST_IDX].Free + 2 - shipSize);
                int cntVer = Math.Max(0, options[SOUTH_IDX].Free + options[NORTH_IDX].Free + 2 - shipSize);
                cnt += cntHor + cntVer;

              }

            }

            foreach (Direction dir1 in DIRECTIONS.Values)
            {
              int x1 = x + dir1.DX;
              int y1 = y + dir1.DY;
              if (IsUnknown(playingField, x1, y1))
              {
                foreach (Direction dir2 in DIRECTIONS.Values)
                {
                  int x2 = x1 + dir2.DX;
                  int y2 = y1 + dir2.DY;
                  if (x2 != x || y2 != y)
                  {
                    if (IsWaterOrImpossible(playingField, x2, y2))
                    {
                      neighborFact++;
                    }
                  }
                }
              }
            }

            bool matching = MatchesScanPattern(x, y);
            if (cnt > bestCnt || (cnt == bestCnt && (neighborFact > bestNeighborFact || (neighborFact == bestNeighborFact && ((!bestMatching && matching) || (bestMatching == matching && rnd.Next(2) == 1))))))
            {
              bestCnt = cnt;
              bestNeighborFact = neighborFact;
              bestMatching = matching;
              bestCoord = new Coordinates(x, y);
            }
          }
        }
      }
      return bestCoord;
    }

    private SinkTryResult GetNextSinkTry(PlayingField playingField)
    {
      ShipPositionOption[] options = CreateShipPositionOptions();

      for (int i = 1; i < seekedShipSize && (!options[EAST_IDX].Done || !options[WEST_IDX].Done || !options[SOUTH_IDX].Done || !options[NORTH_IDX].Done); i++)
      {
        for (int optIdx = 0; optIdx < options.Length; optIdx++)
        {
          ShipPositionOption option = options[optIdx];
          if (!option.Done)
          {
            Coordinates nextCoord = new Coordinates(sinkCoord.X + i * option.Dir.DX, sinkCoord.Y + i * option.Dir.DY);
            if (!IsValidCoord(nextCoord) || impossibleCoords[nextCoord.X, nextCoord.Y])
            {
              option.Done = true;
            }
            else
            {
              State state = playingField.GetState(nextCoord.X, nextCoord.Y);
              if (state == State.Unknown)
              {
                if (option.NextCoord == null)
                {
                  option.NextCoord = nextCoord;
                }
                option.Free = option.Free + 1;
              }
              else if (state == State.HitShip)
              {
                if (option.Dir.Orient == Orientation.EAST || option.Dir.Orient == Orientation.WEST)
                {
                  options[SOUTH_IDX].MarkInvalid();
                  options[NORTH_IDX].MarkInvalid();
                }
                else
                {
                  options[EAST_IDX].MarkInvalid();
                  options[WEST_IDX].MarkInvalid();
                }
              }
              else
              {
                option.Done = true;
              }
            }
          }
        }
      }

      ShipPositionOption bestOpt;
      ShipPositionOption option1;
      ShipPositionOption option2;

      int horFree = options[EAST_IDX].Free + options[WEST_IDX].Free;
      int verFree = options[SOUTH_IDX].Free + options[NORTH_IDX].Free;
      int minHorFree = Math.Min(options[EAST_IDX].Free, options[WEST_IDX].Free);
      int minVerFree = Math.Min(options[SOUTH_IDX].Free, options[NORTH_IDX].Free);

      if (horFree > verFree || (horFree == verFree && (minHorFree > minVerFree || (minHorFree == minVerFree && rnd.Next(2) == 1))))
      {
        option1 = options[EAST_IDX];
        option2 = options[WEST_IDX];
      }
      else
      {
        option1 = options[SOUTH_IDX];
        option2 = options[NORTH_IDX];
      }

      if (option1.Free > option2.Free)
      {
        bestOpt = option1;
      }
      else if (option2.Free > option1.Free)
      {
        bestOpt = option2;
      }
      else
      {
        bestOpt = rnd.Next(2) == 1 ? option1 : option2;
      }

      return new SinkTryResult(bestOpt.NextCoord, bestOpt.Dir);
    }

    private bool IsUnknown(PlayingField playingField, int x, int y)
    {
      return IsValidCoord(x, y) && !impossibleCoords[x, y] && playingField.GetState(x, y) == State.Unknown;
    }

    private bool IsWater(PlayingField playingField, int x, int y)
    {
      return IsValidCoord(x, y) && playingField.GetState(x, y) == State.Water;
    }

    private bool IsWaterOrImpossible(PlayingField playingField, int x, int y)
    {
      return IsValidCoord(x, y) && (impossibleCoords[x, y] || playingField.GetState(x, y) == State.Water);
    }

    private bool MatchesScanPattern(Coordinates coord)
    {
      return coord != null && MatchesScanPattern(coord.X, coord.Y);
    }

    private bool MatchesScanPattern(int x, int y)
    {
      return (x + y) % 2 == 0;
    }

    private bool IsValidCoord(Coordinates coord)
    {
      return IsValidCoord(coord.X, coord.Y);
    }

    private bool IsValidCoord(int x, int y)
    {
      return x >= 0 && x < FIELD_DIM_X && y >= 0 && y < FIELD_DIM_Y;
    }

    private void SetImpossibleCoord(int x, int y)
    {
      if (IsValidCoord(x, y))
      {
        impossibleCoords[x, y] = true;
      }
    }

  }
}

Previous Postings:

• Battleship Game Algorithm Explained (Part 1)
• Battleship Game Algorithm Explained (Part 2)
• Battleship Game Algorithm Explained (Part 3)

Where Jeff Atwood Is Wrong On Stackoverflow.Com

I have been reading Jeff Atwood's Coding Horror Blog for many years and have high regards for it, but I am starting to get a little disillusioned by some of his later writings and also several comments on the Stackoverflow.Com Podcast. Anyway, considering all that interesting and entertaining stuff he has been blogging over time I suppose it's also OK if I can't identify with his opinion once in a while.

There is this blog entry on the Model/View/Controller design pattern, and Jeff and Joel Spolsky also discussed that during their podcast. I consider the "Model=HTML, View=CSS and Controller=Browser"-explanation misleading (I would not go so far to call it "completely wrong", it's just not a great analogy). HTML and CSS are declarative languages, not Models/Views in an OOP sense. The browser application's code and data structures are the building blocks for Model, View and Controller. So the browser IS Model, View and Controller.

By definition, the Model represents application state, the View defines how Model data is rendered into the UI and the Controller takes user input and changes the Model accordingly, resp. invokes application functionality.

One could favorably argue that HTML is a source of data for the browser's Model, and that CSS also affects the way the View does the rendering. But Model and View themselves are something else, they are browser-internal software components that represent web content (Model) resp. are responsible for visualizing that web content on a UI platform (View). Remember the View serves as an Observer on Model data - that just doesn't fit with CSS and HTML. And that's why I think the comparison is a little bit far-fetched.

Take a CAD application as another example of a Model that contains some kind of graphical artefacts simply because that's the nature of the application (just like web content in case of a browser). The CAD Model might consist of shapes and polygon definitions, and the CAD View then renders that into a two-dimensional UI.

Here is a diagram taken from the J2EE Architecture blueprints that pretty much sums up things (yeah I know this article refers to N-tier architecture, but the diagram is valid for all MVC-secnarios).



Jeff Atwood noted that he could not find any MVC documentation that really pleased him and that he could do better (hey, why not take the GoF book - MVC is described in the introduction chapter). Sorry to say that in this case he didn't comply with his own high standards.

Then there was a remark about SqlServer as being pretty much standalone self-tuning. As much as I appreciate SqlServer, it's really not self-tuning. Don't get me started on all that query optimizer issues I have been through (admitted this has gotten better in the latest versions). It's also a must to define a customized maintenance plan on SqlServer. But maintenance plans are kind of cumbersome or even impossible on desktop/express engines, and on those engines self-tuning would be essential (as there is no database admin to take care of such things). If I had to name a self-tuning database, it would be Sybase SQLAnywhere Personal Server - no big surprise as it has been designed for smaller-than-enterprise usage.

Finally Jeff stated that he sees no difference between computer science and software engineering. I'd like to quote Steve McConnell at this point (and by the way, coincidently the term "Coding Horror" descends from Steve McConnell's book "Code Complete"):

Scientists learn what is true, how to test hypotheses, and how to extend knowledge in their field. Engineers learn what is true, what is useful, and how to apply well-understood knowledge to solve practical problems.

Scientists must keep up to date with the latest research. Engineers must be familiar with knowledge that has already proven to be reliable and effective. If you are doing science, you can afford to be narrow and specialized. If you are doing engineering, you need a broad understanding of all the factors that affect the product you are designing.

Scientists don't have to be regulated because they are chiefly accountable to other scientists. Engineers do have to be regulated because they are chiefly accountable to the public.

An undergraduate science education prepares students to continue their studies. An undergraduate engineering education prepares students to enter the workforce immediately after completing their studies.

But hey, just as Jeff remarked repeatedly, it's also fine to disagree every now and then.

Battleship Game Algorithm Explained (Part 3)

This is part 3 of the mini-series explaining the inner workings of the Cubido C# Pirates Winner Algorithm. We have talked about how to find the cell best suited for a trial shot. Now let's see what we can do to improve the accuracy of sinking shots, that is the follow-up shots once a trial shot hit on a ship.

So what needs to be decided at this point is in which direction to continue shooting after the first hit. The stakes are high - after all it's possible to produce three unnecessary misses until we know for sure were the ship is really located.

Let's have a look at the following scenario, and suppose that there is one ship left of size 4, one ship of size 3 and one ship of size 2:



It somehow seems tempting to select the eastern neighbor cell for the next sink shot, because of the large unknown space in that direction. But as it turns out that would be a mistake.

A better approach is to calculate the probabilities for the ships that are still left on the battlefield to be located on each unknown neighbor cell (of course considering the fact where we have hit the ship already). This is very similar to our strategy when placing trial shots.

The ship of size 2 can be located in either of the four directions, so this does not really help.

There is 1 possibility for the ship of size 3 to be located on the western neighbor cell, 2 possibilities on the northern neighbor cell, 2 possibilities on the eastern neighbor cell and 2 possibilities on the southern neighbor cell. So the western cell is out of the game.

Regarding the ship of size 4, there is 1 possibility to the west, 2 to the north, 2 to the east and 3 to the south. The southern neighbor is our target of choice.

In case we miss we'll give it another try the next round by applying the same mechanism. After all the probabilities have changed by then (the ship is then more likely to be positioned horizontally).

Once we hit a second ship cell we can be sure about its orientation, but may still not know about the exact location. So we continue to calculate probabilities for neighbor cells on each side until the ship has been sunk. After that we store the information about which ship size just has been sunk, mark all cells surrounding the ship with State Impossible, and switch back to trialshot mode (as explained in part 1).

In part 4 we are going to put all of that together, and have a look at the resulting sourcecode.

Previous Postings:

• Battleship Game Algorithm Explained (Part 1)
• Battleship Game Algorithm Explained (Part 2)

Followup Postings:

• Battleship Game Algorithm Explained (Part 4)

Battleship Game Algorithm Explained (Part 2)

This is part 2 of the mini-series explaining the inner workings of the Cubido C# Pirates Winner Algorithm. We previously examined how to basically choose the next battlefield cell to shoot at, that is by calculating each cell's probability to contain a ship. If there is more than one top-ranked cell, we need to decide among those cells.

So far we have done our best to hit a ship. But let's face it, it's more likely to hit the water. How can we benefit from a missed shot as well?

By applying a checkerboard-like shooting pattern we will find each ship by only having to hit only 50% of the cells (and that's a worst case scenario). E.g. there is no way for a ship of size 2 to hide anywhere here:



Great, we now have an additional selection criteria for choosing the next target cell: the checkerboard pattern.

Still there might be plenty of cells left with equal ship location probabilities which also fit into the checkerboard. Which other value can be gained from a missed shot? The value of learning something about unknown neighbor cells! When an unknown cell A has a water cell neighbor B (or an impossible cell neigbor, which is a cell that adjoins a sunk ship), this clearly limits the options for a ship to be located on cell A - because cell B is out of the game for a joined ship location.

If cell A is surrounded by two water/impossible cells the probabilities decrease further, and even more of course with three water/impossible neighbors (just one direction left to place a ship). Finally if we happen to shoot at the last remaining unknown neighbor cell of A (and hit water only), we can abandon that cell A for future consideration all together.

So what we are going to do is to count the water and impossible neighbors for each of our potential target's unknown neighbors (our target's unknown neighbors' water/impossible neighbors so to speak), and prefer the one target with the highest score.

This cell here might be a good choice for a shot (neighbor score is 7, 2 water neighbors for the western unknown neighbor + 2 water/impossible neighbors for the northern unknown neighbor + 0 for the eastern impossible neighbor + 3 water/impossible neighbors for the southern unknown neighbor):



In the following case that cell would score even higher (neighbor score is 9, 3 water neighbors for the western unknown neighbor + 3 water/impossible neighbors for the northern unknown neighbor + 0 for the eastern impossible neighbor + 3 water/impossible neighbors for the southern unknown neighbor):



So the neigbor score becomes our second target selection criteria, right after to the ship location probability.

If there are cells with equal ship location probability and equal neighbor score, we choose one that fits the checkerboard (by the way, applying the neighbor score almost naturally leads to a checkerboard as well, so this is just to go sure for special cases, e.g. a more or less empty battlefield). If more than one of the top-ranked cells fits the checkerboard, we'll randomly select any of them.

In part 3 we will discuss how to proceed once the first cell of a ship has been hit. There is a lot of potential for tuning as well.

Previous Postings:

• Battleship Game Algorithm Explained (Part 1)

Followup Postings:

• Battleship Game Algorithm Explained (Part 3)
• Battleship Game Algorithm Explained (Part 4)

Battleship Game Algorithm Explained (Part 1)

Several people have approached me about this, so here is the first article in a mini-series describing the Cubido C# Pirates Winner Algorithm. It's final score was 38.19 shots (average shot count on 10,000 battleship games). 17 contentors scored under 39.00 shots, so this clearly was a very close match. 83 algorithms took part overall. The sourcecode is available, too.

Please note:

The code was not optimized for speed and has plenty of potential for performance improvement, esp. regarding nested looping. The competition rules included an upper time limit of 500ms per shot. This implementation runs at 1ms per shot in average, so there was no point in tuning that esp. as readability might have suffered.

The algorithm does not take into consideration opponents' behavior. The C# Pirates competition environment itself placed the ships randomly, and did not provide state storage on any larger scope than a single game, so it was not possible to react on opponent's behavior when shooting, or on different ship placement strategies.

Here is the spec: The battlefield consists of 10x10 cells. Ships are laid out either horizontally or vertically, with a margin of at least one cell between each ship. There is one ship of size 5, one of size 4, two of size 3 and one of size 2. Battleship algorithms are being called back on each round and must return the cell to shoot at next. The state of each cell can be queried through the C# Pirates API. Those states are: Unknown (cell has not been shot at yet), Water (cell has been shot at before and contains no ship) and Ship (cell has been shot at before and contains a ship).

Unknown cell

Water cell

Ship cell

So on each round of the game there is a decision to be made: at which cell to shoot at next. It soon becomes clear that we need two different modes of operation: Trialshot mode and Sinkshot mode. Trial shots occure while scanning the battlefield for ships. Sink shots happen once a ship has been hit in order to continue sinking it. We are going to talk about trial shots in part 1 and part 2, while sink shots will be covered in part 3.

In trialshot mode it's clearly a good idea to choose the cell that is most likely to be occupied by a ship. The probability of a ship residing at a certain cell can be calculated by scanning for unknown neighbor cells in each direction.

Let's have a look at an example. Say that there are the following ships left to be sunk: One of size 5, one of size 3 and one of size 2 (we know that because we kept track on which ships we sank already), and we are about to examine the cell marked with a shot impact.



There are following possibilities for this cell to contain a ship: 1 option for a ship of size 5 (filling out the whole horizontal space), 1 option for a ship of size 3 (to the east), and 2 options for a ship of size 2 (north and east). So this gives us 4 options for ships to be placed on that very cell.

What about the next unknown cell?



Again there is 1 option for a ship of size 5 (horizontally), 2 options for a ship of size 3 (both horizontally, one to the east, the other one with the proposed target cell located in the center of the ship), and 3 options for a ship of size 2 (east, west and south). There is no way for a ship to fit to the north although the northern neighbor has not been shot at yet, as it's itself restricted by the sunken ship next to it (one cell margin between ships). Still, 6 options beat 4 options, so the algorithm would choose the second cell among those two cells.

The fact that there is a margin of one cell between ships creates another cell state that we must consider: the cell has not been shot at, but is next to a ship, hence cannot be part of a ship itself. Let's call that state Impossible, and keep this information in an internal data structure between callbacks, because the C# Pirates API does not support that state, and querying all neighbors of state Unknown each time is kind of cumbersome.

So what we basically do is to iterate over all cells of state Unknown, calculate their probabilities to contain a ship, and select the highest-rated option. The question is what to do when there are several target cells with the same probability (which by the way is quite likely to happen). Making a good decision at that point is crucial and will differentiate our algorithm from competing ones which apply the same basic strategy. We will discuss that in part 2.

Followup Postings:

• Battleship Game Algorithm Explained (Part 2)
• Battleship Game Algorithm Explained (Part 3)
• Battleship Game Algorithm Explained (Part 4)

Cubido C# Pirates Programming Competition

As luck would have it I won the Cubido C# Pirates Programming Competition for the best Battleship Game Algorithm last week, and took home an XBox 360 Premium Edition as first prize.



Tuning was absolutely necessary as 17 algorithms scored under 39 shots at the end (around 70 players took part over all). My algorithm attained 38.19 shots, with the closest competitor finishing at 38.33.

The final competition was a public event (a big thank you goes to the kind folks at Cubido), and many contestants dropped by at the Cubido Headquarters and watched the progress on a large scoreboard (which was also available online). The battle lasted nearly four hours. 10,000 games had been played eventually (each algorithm was required to finish 10,000 identical battlefields). With results so close this large number of games was a must to avoid any "accidental winner", a winner that would have benefited by certain random distributions (as a matter of fact during the preliminary rounds, which only consisted of 50 games each, my implementation scored at between 34.5 and 40.5 shots, so that's quite a spread - a spread that was caused both by the random distribution of ships on the battlefield, as well as the algorithm's internal randomizer, which is applied when choices are evaluated as being equal otherwise).

As I have promised before, I am going to talk about the ideas behind the algorithm and post the complete sourcecode over the next few days.

Battleship Game Algorithm Competition

I am one of the C# Pirates taking part in Cubido's Battleship Game Algorithm Competition. Dozens of computer programs battling it out against each other - in batch mode on the server (current ranking), as well as viewable in any Silverlight-enabled web browser.

Last week I attended Microsoft Austria's Big Days 2008 and found out about the contest - two nights of coding later, and Captain Alex (namesake of my older son) reached the top position. Captain Ahab, the old swashbuckler, is still a tough competitor though.


And by the way kudos to Cubido. What a great idea! This is the kind of stuff that excites most software developers. And their Silverlight client does have really cool visuals.


I am going to blog about the algorithm once the contest has ended (it is quite simple).

DrawCircle Performance Tuning

A while ago a friend of mine asked me an interesting programming question: "How would you implement a DrawCircle() function?". "I'd loop and invoke Sin() and Cos() in order to obtain coordinates" I answered. "OK", he replied, "and how would you make it fast? I have heard of an incremental way to do this, without the need for floating point operations at all." (that was on some embedded hardware back then, where floating point operations were really expensive)

This kept me thinking. So why not give it a try right here and now! Let's start with something like this (C#, .NET 2.0 - using a managed environment is OK, as .NET is guaranteed to JIT this code immediately anyway; floating point operations are much faster on modern hardware, still we should see some effect). For sake of brevity, let's draw our circles centered at (x = 0, y = 0):

private static void DrawCircle1(int radius)
{
  double angle = 0;

  do
  {
    double rad = angle * Math.PI / 180.0;
    double x = Math.Cos(rad);
    double y = Math.Sin(rad);

    DrawPixel(x, y);

    angle++;
  } while (angle < 360);
}

Sure enough, a circle appears on the screen. It looks weird - the line is dotted, not solid. Right, incrementing the angle by 1 each time might imply advancing too fast. An increment value better suited is the angle between two pixels on the circle. Something like this:

private static void DrawCircle2(int radius)
{
  double angle = 0;

  double step = Math.Asin(1.0 / radius) * 
                180.0 / Math.PI;

  do
  {
    double rad = angle * Math.PI / 180.0;
    double x = Math.Cos(rad) * radius;
    double y = Math.Sin(rad) * radius;

    DrawPixel(x, y);

    angle += step;
  } while (angle < 360);
}

This works, so that's something to start with. To get an idea about its speed, let's ignore the call to DrawPixel() for a second (and assume that we have a lightning-fast DrawPixel() implementation at that point - and by lightning-fast I mean inlined native code that just does something like an indexed array lookup, a little pointer arithmetic, and one or two bitwise operations on a bitmap bytearray, not slow stuff like SetPixel(), Bitmap.SetPixel() or BufferedImage.setRGB()). Oh yeah, and no synchronous screen refreshing ;-)

Some profiling tells us that his function can calculate the pixels for 160,000 circles (of radius 100) per second (all numbers refer to release mode compiling).

Another way of speeding up the algorithm is to take advantage of the fact that a circle is symmetric. Wouldn't it be enough to calculate one quarter of the circle, and then just mirror it on the x- and y-axis. But wait - what about calculating only one eighth of the circle, and mirroring it on the diagonal, too? No sooner said than done:

private static void DrawCircle3(int radius)
{
  double angle = 0;

  double step = Math.Asin(1.0 / radius) * 
                180.0 / Math.PI;

  do
  {
    double rad = angle * Math.PI / 180.0;
    double x = Math.Cos(rad) * radius;
    double y = Math.Sin(rad) * radius;

    DrawPixel(x, y);
    DrawPixel(x, -y);
    DrawPixel(-x, y);
    DrawPixel(-x, -y);
    DrawPixel(y, x);
    DrawPixel(y, -x);
    DrawPixel(-y, x);
    DrawPixel(-y, -x);

    angle += step;
  } while (angle <= 45);
}

This gives us something close to the expected 8-fold speedup (1,200,000 circle calculations per second to be exact). Still it seems like a dead end. We need a different approach.

Let's search for a way to draw a circle without the need of invoking Sin() and Cos(). What does a circle function look like? It's

x^2 + y^2 = 1

so:

y = sqrt(1 - x^2)

Let's also take advantage of the fact that we know that x is always incremented while looping. How do we know that? Because we just calculate 1/8th of the circle. We are starting at coordinate (x = 0, y = radius), hence on each step will either move right only, or move right and down.

private static void DrawCircle4(int radius)
{
  double x = 0;
  double y = radius;

  do
  {
    DrawPixel(x, y);
    DrawPixel(x, -y);
    DrawPixel(-x, y);
    DrawPixel(-x, -y);
    DrawPixel(y, x);
    DrawPixel(y, -x);
    DrawPixel(-y, x);
    DrawPixel(-y, -x);

    x++;
    //cast to get rid of decimal places
    y = (int)((Math.Sqrt(1.0 - 
        Math.Pow(x / radius, 2)) * radius));
  } while (x <= y);
}

100,000 circles per second, what a disappointment. I did some quick check, it seems that Math.Pow() does not have dedicated FPU-support, so this might be a reason.

Still this might open a new perspective. Having a look at two neighboring pixels on the circle, what does make them neighbors? Their x- and y-coordinates differ by 1, either x does, or y, or both. Starting at a well-known pixel, e.g. (x = 0, y = radius) we could move along the circle just be deciding whether we increment x and leave y as it is, or decrement y and leave x as it is, or increment x and decrement y.

Once more the circle function:

x^2 + y^2 = 1

which equates to:

x^2 + y^2 - 1 = 0

Drawing a perfect circle on a discrete field of pixels, there is always a deviation, an error. An error e that can be expressed like this:

x^2 + y^2 - 1 = e

The pixel we draw is either inside the perfect circle or outside. When we have moved outside the perfect circle, we have to pull back to the inside, and vice versa. In each iteration, we must keep e as close to 0 as possible.

How does e change on each iteration? Let's assume we increment x and decrement y, so the next pixel is at (x + 1, y - 1):

e = x^2 + y^2 - 1
nextE = (x + 1)^2 + (y - 1)^2 - 1 
      = (x^2 + 2x + 1) + (y^2 - 2y + 1) - 1

The difference between nextE and e is influenced by the following factors:

dx = (x^2 + 2x + 1) - x^2 = 2x + 1
dy = (y^2 - 2y + 1) - y^2 = -2y + 1

This is how nextE looks like when x is incremented and y is decremented:

nextE = e + dx + dy

If we decide only to increment x and leave y as it is, nextE would be:

nextE = e + dx

And in case we only decrement y, nextE is:

nextE = e + dy

At this point we just have to figure out whether e stays smallest by moving along the x-axis only, or the y-axis only, or both.

Wow, no need to invoke Sin(), Cos(), Sqrt() or Pow(), no need for floating point functions or values, we can do it all with integers only. Note that we could even avoid the multiplications by a factor of 2 simply by writing (x + x) and (- y - y), but compilers normally replace that by a left-shift anyway. Also, we do not invoke Math.Abs(), but get rid of minus signs on our own.

private static void DrawCircle5(int radius)
{

  int e = 0;
  int x = 0;
  int y = radius;

  do
  {
    DrawPixel(x, y);
    DrawPixel(x, -y);
    DrawPixel(-x, y);
    DrawPixel(-x, -y);
    DrawPixel(y, x);
    DrawPixel(y, -x);
    DrawPixel(-y, x);
    DrawPixel(-y, -x);

    int dx = 2*x + 1;
    int dy = -(2*y) + 1;

    int e1 = e + dx;
    int e2 = e + dx + dy;
    int e3 = e + dy;

    e1 = e1 < 0 ? -e1 : e1;
    e2 = e2 < 0 ? -e2 : e2;
    e3 = e3 < 0 ? -e3 : e3;

    if (e1 <= e2 && e1 <= e3)
    {
      x++;
      e += dx;
    }
    else if (e2 <= e1 && e2 <= e3)
    {
      y--;
      x++;
      e += dx + dy;
    }
    else
    {
      y--;
      e += dy;
    }
  } while (x <= y);

}

2,100,000 circle calculations a second. It cannot possibly get better, can it?

Yes it can. Similar to DrawCircle4(), when we always incremented x because of calculating 1/8th of the circle only, we can assume here that we will never enter the last else-block in DrawCircle5(), as it does not increment x either.

And since we are always moving to the right incrementing x, the delta of e depends entirely on whether we also move down and decrement y. The change in the error value caused by decrementing y is (-2*y + 1), so let's choose to decrement y each time e is greater or equal to y, as this will move e closer to 0 again.

All of this allows us to get rid of several statements, and some local variables too. Also, let's do the left-shifting explicitly this time instead of multiplying by 2 (as mentioned above, we may expect our compiler to take care of that, but I have experienced cases when that did not happen, e.g. when writing -2*y instead of -(2*y)).

private static void DrawCircle6(int radius) 
{
  int e = 0;
  int x = 0;
  int y = radius;

  do
  {
    DrawPixel(x, y);
    DrawPixel(x, -y);
    DrawPixel(-x, y);
    DrawPixel(-x, -y);
    DrawPixel(y, x);
    DrawPixel(y, -x);
    DrawPixel(-y, x);
    DrawPixel(-y, -x);

    if (e < y) 
    {
      e += (x<<1 -="" 1="" e="" else="" lt="" while="" x="" y--="" y="">

6,400,000 circles per second. It is now 40 times faster than at the beginning.

I guess this is a good example that there is always room for improvement, and the solution that comes to mind first probably is not the quickest.

By the way, if you know an even faster algorithm, please drop me a line, and I will post a follow-up.

Update 2011:

I did some further research recently, and found out that what I did back then is kind of a variant of the Midpoint Circle Algorithm, dating back to 1967. Plus after all, I had received two initial hints, namely that there should be an algorithm without the need of floating point operations, and that it might work in a kind of incremental way. So I can't really claim it to be a "stand-alone" creation [ ;-) ].

Windows Forms DataBound-Controls On TabPages

I stumble over this issue every once in a while: Windows Forms controls will only data-bind when they are visible or have been visible once - this can become an issue when controls are located on a TabPage that has never been shown. The control's bound value then has never been pushed into the UI.

Especially validation-code that checks on properties like TextBox.Text is vulnerable to this - e.g., no matter what the bound value is, TextBox.Text returns an empty string as long as it has not been visible (anyway, in my opinion validation code should always work on model values, not on view properties).

One way to work around this is to check on Control.Created before validating a control's content.

.NET Webcasts

I am currently watching lots of .NET Webcasts. Some of the best can be found at:

• DotNetRocks TV
• MSDN On-Demand Webcasts
• Channel 9 Screencasts
• Mike Taulty's Screencasts from Microsoft UK

Especially Mike Taulty's screencasts are great. They have the highest entropy - tons of information in a relatively short amount of time. He exactly delivers all the facts I need to know - straight to the point.

I also try to save time when watching screencasts by switching to double playback speed in MediaPlayer.


With some concentration its possible to do so without missing any piece of information.