Microsoft Rock!

Now there’s a bold way to start a blog entry aimed at programmers. You can complain all you like about monopolies, bugs, security & performance. But then, Microsoft probably didn’t just give you $10,000K worth of software practically for free, so you’ll have to forgive my temporary rush of enthusiasm…

So basically the deal is that Microsoft have a partners scheme, where just about anyone can sign up. If you’re a partner, you are eligible to register for the Microsoft Action Pack, which is a big goody bag of software. You get a nice folder and a big stack of CDs shipped to you, and then a quarterly update of any new version released in the following year.

You can see the full list here but there is a lot of stuff I’ve never heard of so let me give you my highlights, i.e the software I’d actually want:

• Windows Vista Business (32 & 64 bit versions) X 10 licenses
• Office 2007 Enterprise Edition X 10 licenses
• MS Project X 10 licenses
• MS Visio X 10 licenses
• Windows Server 2003 (32 & 64 bit versions)
• Windows Small Business Server
• SQL Server 2005

And next year, I will get full versions of Windows Server 2008 amongst others.

If you’ve never thought how much server software costs, i suggest you take a look. You might have been thinking 10 Vista licenses was worth a lot… not compared to Windows 2003 or SQL Server 2005!

If you’d like to post how much it would cost you for all this where you live, that would be cool. But how much did I pay? Well, for all that software, on actual CDs, delivered to my door from the US, I paid a little under… $500US.

Neat, eh?

Nasty Maze

Background

A very common problem when teaching about algorithms and data structures is to find the shortest path between two points in a maze, where the maze is represented as a grid and each square is either clear or blocked. For example we might be given a grid like this, where black squares are blocked, and told to find the shortest path length between the two red squares. For example in this case the shortest path is shown in purple:

I’m not going to ask you to solve that problem. If you never did this kind of thing before, then it’s pretty fun, and it’s a very useful algorithm in real-life programming – but we’re going to look at a slightly less common problem.

The problem

The challenge is that given 2 points (x1,y1) & (x2,y2), and a square NxN grid, you have to build a maze which maximises the shortest path between the 2 points. In other words the grid starts off all white squares, and you have to add black squares to make the shortest possible journey from one point to the other as long as it can be. You can’t make it impossible to get between the 2 points, and you can’t block either of the two points given.

There are 2 versions of this problem. The easier version is simply to write a function which returns the maximum length the shortest path could be, given x1,x2,y1,y2 & N.
The harder version requires you to also calculate the smallest number of cells in the grid you must block to achieve this path length.
Obviously it gets harder as the grid gets bigger. Initially, how about a solution that would take no more a than a couple of seconds for N<=20. If you can do that, then what about for N=100?

Example function signature (C/C++/Java/C#):
void nastyMaze(int x1,int y1,int x2,int y2,int N);

Please feel free to post your ideas or code as comments. If you find the problem interesting, please tell me – if you find it too hard or too boring then please tell me that too!

Day 1

Today is officially the first day of my new career. It’s 6pm here so I’m just finishing up my first full day of professional freelancing.

I’m visiting some friends who set up their own company tonight, as the first serious investigation into how the legal stuff works. I’ll report back from that once I’ve assimilated it.

ps: Tomorrow, expect a new algorithm problem.

pps: If you have any questions about anything, just post a comment. And if you’ve got me hooked up to RSS, I’d love to know about it. I’m trying to get an idea of the traffic I’m getting…

Career Change!

Until yesterday, I was a full-time software developer working a 9-5 job writing Java web applications. From today, I am a professional contractor / freelancer. I have decided to work entirely from home over the internet, which is potentially both exciting and lucrative… but also lot a little scary!

There is quite a lot to do when you work for yourself. Creating a company to trade as, getting to grips with accounts & tax, liability insurance… and not to forget the small issue of finding work! Fortunately I have done some work previously and am lucky enough to have a contract already. And there is always money available from TopCoder’s design & development projects. Some people make $100K+ a year doing just that! I would certainly recommend it over RentACoder or GetAFreeLancer any day of the week. If you have any questions on that, feel free to ask – and if you register there after reading I’d appreciate it if you put me (d000hg) as referrer.

Anyway, tangent over…

I had it in mind that other people might be interested in the idea of going independent, but aren’t sure where to start. So, I plan to blog my progress in this new adventure. Setting up the legal stuff, what it’s like working from home, if it pays well, everything. If anyone’s familiar with Patrick’s excellent MicroISV on a Shoestring blog, I was imagining something a little like that, only about freelancing.

DiagonalPath

DiagonalPath:
On a grid, you can make moves up, down, left or right. Given starting position (x1,y1) and destination (x2,y2), you should return the maximum number of times that the movement direction may be changed, to still reach the destination in the minimum number of turns. For instance, given (0,0) and (3,3) you could make the following moves: right,right,right,up,up,up – but the movement direction changes just once. Alternatively, you could make the moves: right, up, right, up, right, up – the movement direction changes 5 times, and you still make the minimum possible number of moves, which is 6.
Constraints: x1,x2,y1,y2 are all between -1,000,000 and +1,000,000 inclusive.

Introduction

Hello, I’m d000hg, and this is my blog. I’m going to use it to talk about anything I find interesting. That means, in nearly all cases, something related to programming or software development. As well as that, articles and algorithmic problems I write will appear here.

As well as here, you can find me on www.gamedev.net and www.topcoder.com/tc

So for this first post, here is a problem I wrote, in a style similar to those found on TopCoder, USACO, etc. Feel free to post ideas, code, bugs, … If you want to discuss this problem on TopCoder’s forums I’m fine with that, we discuss USACO, SPOJ there after all, but please link back to this post.

I have a fair few problems stored up so expect them every couple of days…

I’m new to blogging so any tips about the way I write, or how my blog is set up, are welcome.

2D Palindromes.

A palindrome is a sequence of letters which is the same no matter which way it is read. For instance HANNAH or ABCBA. A 2-dimensional palindrome extends this idea for a table of letters. A section of a table is 2D-palindromic if each row is a palindrome and each column is also a palindrome. For instance:
ABCDEDCBA
BCDEFEDCB
ABCDEDCBA

Here each row is a 9-letter palindrome, and each row a 3-letter palindrome.

Given a string[] grid, where the ith element is the ith row of a character grid, return the area of the largest 2-D palindromic region within this grid.

Examples:
“ABCDEDCBA”,
“BCDEFEDCB”,
“ABCDEDCBA” The whole region is a 2D palindromic so return 9×3 = 27.

“AAAAAAAAAAAAA”,
“AAAAAAAAABBBB”,
“AAAAAAAAABBBB”,
“AAAAAAAAABBBB” There is a 9×4 palindromic region consisting entirely of ‘A’ characters.

Notes:
grid may have between 1 and 50 entries; each entry may have between 1 and 50 upper-case characters A-Z; all entries in grid are the same length.