Chess in C (Part 6) - Potential moves of a bishop: up-right

This post is a continuation of Chess in C (Part 4). No fancy introductions or recaps. If you don't read that, you won't understand this.

Radiating up-right

Mission: write an algorithm that returns the up-right diagonal from a bishop in position (X,X).

We need to get (2,5), (1,6) and (0,7). We can modify the algorithm used to figure out the up-left diagonal as follows

1. Start at the last square and iterate through the board backwards
2. For each square, check if the upper-right square is within the board
1. If it is, check if there's a bishop or breadcrumb in the upper-right square
1. If there is, this square is a potential move. Mark this square with a breadcrumb.
3. Repeat until you reach (0,0).

Just like in the up-left algorithm, we need to iterate through the board backwards. If we iterate forwards, we won't pickup all the potential moves. Here's an illustration: start at square (0,0). Ask yourself, "Is there a bishop or breadcrumb in the lower-left diagonal square?" Progress to the next square. Ask yourself the same question. At position (0,7), your answer will still be no, even though (0,7) is a potential move!

You call yourself a bishop?!.

This is what happens when we iterate backwards.

The code to implement this algorithm is similar to the up-left diagonal. Unfortunately, it's a little too similar!

If we reuse the code, the breadcrumbs for each of the algorithms will trip up over each other! The solution is to modify the macros and board drawing code to differentiate between the breadcrumbs of each algorithm. I've made a few more POTENTIAL_BISHOP_MOVE macros and appended _UL (upper-left diagonal), _UR (upper-right diagonal), _DL (down-left diagonal) and _DR (down-right diagonal) to them. Here's the code you'll need to begin this lesson.

Now it's time to code up this algorithm.

The code is similarly straight forward. Lines 4 and 5 contain the for loops which iterate through each element in the array backward. Line 8 prevents us from checking the row below or the cell to the left if it doesn't exist. Imagine we're in square (2,5). Because we want to know if the square is a potential up-right diagonal move of a bishop, the bishop must be in the lower-left direction. Here's an illustration.

Put your finger on square (2,5). Yes, it's covered by an X. Pretend you don't know where the bishop is.
If you were trying to find out of the square you're in (2,5) was up-right of a bishop, which way would you search?

The location of the bishop relative to the X is (+1,-1). We're at (2,5), so we're checking if (3,4) exists. Which it does. But what if we were at square (7,0)? Square (8,-1) definitely doesn't exist, and if we try to check that square we'll exceed the bounds of the array. Which is bad.

Line 10 checks the actual cell for a bishop or a breadcrumb. If it does, line 12 marks the square with a breadcrumb for the board drawing code to interpret. Time to test!

Bishop in position (0,0).
You know what we're not doing?
Testing if there's a bishop in (1,-1)

Bishop in position (4,4).
It looks like the algorithm has been implemented correctly.

Bishop in position (3,4).
That looks nice!

Bishop in position (4,7).
We're testing an edge case. It works.

Bishop in position (7,7).
Another edge case to test.
And it works!

Done! Here's the code.

Chess in C (Part 5) - Potential moves of a bishop: up-left, cardinal, pope

On a chess board, the bishop can move diagonally forward or back by any number of squares. I've never seen a bishop in person, but I can say with a high degree of certainty that they don't move diagonally in real life. But just to be on the safe side, if I ever meet a bishop in real life I'm going to stand directly infront of them so they don't bump into me. Wikipedia has a technically correct but literally impenetrable explanation of how bishops move on chess boards, but I believe I've bested the Wikipedia community with my diagram.

Potential moves of the bishop,
aka "the diagonal piece"

Given a square on a chess board, how do we draw the potential moves of a bishop? In the diagram above, the bishop is in position (3,4). There are four possible directions the bishop can move in.

• Up-left: (0,1) (1,2) (2,3)
• Up-right: (0,7) (1,6) (2,5)
• Down-left: (4,3) (5,2) (6,1) (7,0)
• Down-right: (4,5) (5,6) (6,7)

Each direction radiates outward from the bishop like rays from the sun. To make this easy, work on each diagonal separately.

Radiating up-left.

Mission: write an algorithm that returns the upper-left diagonal.

The bishop is at (3,4). We need an algorithm that returns us the positions (0,1) (1,2) (2,3). If the bishop wanted to move up-left one square from (3,4), it would be in (2,3). If it wanted to move up-left two squares, it would be in (1,2). If it moved up-left three squares, it would be in (0,1). It seems simple enough to generate the list of potential moves: you start from the bishop, then work backwards from there. 

Now let's implement it. Remember the code used to iterate through each square on the board from part one of the blog post? I'll post it here.

The code iterates uses two for loops to iterate through each square on the board. The code starts at board position (0,0) and iterates to the end of the row (0,7). It repeats this until it reaches position (7,7). We used this code to clear the board (overwrite each array element with a zero) and also to draw the board. Here's an illustration of how that code works.

The catch is that you can't use this code to work out where the bishop's potential moves are. Imagine the bishop is at (3,4). When the iteration code reaches (3,4), it will be too late already: you'll have passed some of the squares which are potential bishop moves. The iteration code is only useful if you're trying to work out the potential down-right bishop moves. To work out the potential up-left diagonal bishop moves, you need to work backwards.

In the first post of this blog series, I put some code in the original program to iterate through the two-dimensional board array backwards, just for fun. Here's the code to iterate through the board backwards.



Here's our logic. It's incorrect, but let's run with it for now.

1. Start at the last square and iterate through the board backwards.
2. For each square, check if there's a bishop in the lower-right square.
1. If there is, mark this square as a potential move.
3. Repeat until you reach (0,0).
4. All potential diagonal up-left moves have been marked.

Let's model this theory before we code it. If you need to, put your finger on position (7,7) on the diagram and ask yourself the question: for this square, is there a bishop in the lower-right square?

This algorithm correctly identifies (2,3) as a potential move, but not (1,2) or (0,1) which are also potential moves. Close, but no cigar. We can modify our algorithm to mark some squares with breadcrumbs. A breadcrumb is a marker for a potential move. Why do we need breadcrumbs? Well, it's obvious that (2,3) is a potential move and our algorithm works for this. But this check doesn't work for (1,2). What we can do at (2,3) is drop a breadcrumb: a marker that can be checked for when we get to (1,2). We can modify the algorithm to drop and detect breadcrumbs as follows:

1. Start at the last square and iterate through the board backwards.
2. For each square, check if there's a bishop OR breadcrumb in the lower-right square
1. If there is, this square is a potential move. Mark this square with a breadcrumb.
3. Repeat until you reach (0,0).

Let's model this theory. Again, put your finger on the square and ask the question, is there a bishop or breadcrumb in the lower-right square?

Hey, this works! Time to pop the champagne? Well, no. There's still another flaw in this code. When you're at position (7,7), you're asking the question, is there a bishop or breadcrumb in the lower-right square? In this instance, the lower-right square is (8,8), which doesn't exist. The memory allocated outside of the array could be anything. If you check for position (8,8), you'll get undefined behaviour: when you run your program, board[8][8] could be equal to 0. The next time you run, it could be equal to 5. Or 9. Or 42. I've described why this happens in part two. Basically, you don't know what information is stored outside of the array. All you need to know is that you must not check array locations that don't exist. This will require one final change to the algorithm.

1. Start at the last square and iterate through the board backwards.
2. For each square, check if the lower-right square is within the board
1. If it is, check if there's a bishop OR breadcrumb in the lower-right square
1. If there is, this square is a potential move. Mark this square with a breadcrumb.
3. Repeat until you reach (0,0).

Let's code it! I'll also put the code containing #define lines that contain the cell to piece mapping. This is so you know that an array element with value 5 is a bishop, and value 50 is a breadcrumb for a bishop.

Here's an implementation of the algorithm.


Line 1 and 2 contain the for loops that perform the iteration. Because we are iterating backwards, the conditions of the for loop are slightly different.

• Instead of i being equal to 0, i starts at 7 (the end).
• Instead of i iterating until 7, i iterates while it is larger than or equal to 0.
• Instead of incrementing, i decrements.

Line 8 does the bounds checking. The if statement performing the bounds checking has two checks: (j+1 != 8) and (i!=7). If j+1 is equal to 8, that means you're in the final column, so don't check further! If i is equal to 7, you're in the bottom row so don't check further! Line 11 checks whether the down-left square has a breadcrumb or a bishop. Line 11 is only executed if the bounds checking in line 8 is successful. And finally, if all these tests have passed, line 13 marks the square as containing a breadcrumb. Here's the code so far. Copy and pasta it into your IDE and hit compile!


Let's see the output.

Bishop in position (0,0).
This is easy.

Bishop in position (4,4).
Yay, it works!

Bishop in position (3,4).
Woo hoo!

Bishop in position (7,7).
It can move right across the board. Great!
No nasty errors from trying to check array elements
that don't exist. 

Bishop in position (4,7).
It works! And no nasty out of bounds errors.

Great! We've written the code that works out the potential upper-left diagonal moves of a bishop. This was the most difficult diagonal move of the bishop to work out: you needed to combine your knowledge of iterating backwards through two-dimensional arrays, bounds checking, and algorithms. It's easy from here on in! In the next post, I'll discuss how to code the other potential moves of the bishop.

Other posts in this series

Chess in C (Part 1)
Chess in C (Part 2) - Insert Pawn Pun Here
Chess in C (Part 3) - Rook, Rooks, Rookies, Wookies, same thing
Chess in C (Part 4) - I'm asking for input
Chess in C (Part 5) - Potential moves of a bishop: up-left, cardinal, pope

Chess in C (Part 4) - I'm asking for input

Input validation is extremely important. Whether it's a C application or a public-facing website, if you're taking input from a user, you are giving that user an invitation to input garbage. If the user is required to input their name, they'll input their phone number. If required to choose between 1 to 3, they'll enter negative 42. If required to select Yes or No, they'll find a way of typing in their cat's name. And that's if you're lucky.

If you're unlucky, it'll be an attacker trying to overflow your input buffer to break your application so they can steal your password database. But if you're lucky, it'll just be your tutor/lecturer/coworker trying to teach you a lesson. One of my C assignments at university involved writing code to parse command line arguments. The lecturer had warned us that we should treat all user input as hostile, and that our code would be tested for invalid user input. I believed I had thought of every category of invalid data and asked the the tutor to confirm my code was perfect. He looked at my code then asked, "What happens if you specify an argument and leave it blank?" My response was along the lines of...

...this.

This post is part three of the Chess in C series and covers input validation. This series is for beginners. If you know how to iterate through two dimensional arrays and write basic algorithms, this isn't the blog post you're looking for! Unless you want to feel smug and superior.

Chess in C (Part 1)
Chess in C (Part 2) - Insert Pawn Pun Here
Chess in C (Part 3) - Rook, Rooks, Rookies, Wookies, same thing
Chess in C (Part 4) - I'm asking for input
Chess in C (Part 5) - Potential moves of a bishop: up-left, cardinal, pope

So last time I left you, I challenged you to take input from the user then draw the position of the rook. I'll explain the answer, then I'll post some working code. To begin, here's a reminder of the possible moves of a rook. In the following diagram, the rook is in position (3,4).

A representation of an array.
NOT a Cartesian plane. Do NOT draw this in a maths exams.

You might think, "What the heck? Why isn't (0,0) in the bottom left-hand corner like my maths textbooks?" Remember, this diagram is not a Cartesian plane. It's a representation of a two-dimension array in C that happens to look like a chess board. And the top array value is (0,0), because in C we start counting at zero.

Okay, so you want to take input from the user? Ask for it! Here's one way of doing it.

There are lots of ways to get input from the user. Asking a programmer the best way of getting string input from a user is like asking which car is the best. You'll get a long winded answer and if you're unlucky, everyone in earshot will hear the question and give you their opinion as well. The method I've written does a simple check to see whether it's a number, check whether the user didn't just press enter (which would appear as a '\n' in position zero of a character array) and some simple bounds checking. It's a quick and dirty way of getting a row and column number, and you'll see why it's dirty later. Don't reuse this code if you're writing the user interface to a insulin pump or a medical device.

Now, let's glue it all together. Copy and paste the following code into your IDE and compile it.



Let's run it with some inputs and see what we get...

Seems legit to me.

It's always good to do "bounds testing". Test the maximum column value allowed. 

Test the maximum row.

Test the maximum row and column.

Test one over and one under the bounds.
Hey, just wait...we're getting some strange output here!

Test one invalid input and one valid input.
Strange input, again!

Test some letters.

...and remove the pickle.

I pressed enter without typing anything.
You'd be surprised how many students programs break
when you just press enter at prompts.

It seems like the code works, but invalid input can result in strange results! How do we avoid a situation where invalid output is displayed? A few points:

• If the user answers the first question (for the row number) incorrectly, you won't be able to draw the board correctly so there's no point in asking the second question.
• If the user answers the first question correctly but the second question incorrectly, there isn't drawing the board.

How best to implement this decision tree? Well, the easiest way is to nest the code for the second question in the code path executed when the user answers the first question correctly. This method would be both straightforward and easy but horrible to maintain. The decision tree is simple today, but what if you asked a third question? Or a fourth? You could have if statements nested in if statements nested in if statements! I know Chess in C is just an introductory level blog series, but I don't want you to get into the habit of writing unmaintainable code!

The questions we need to ask and the target state.
But how do we implement this?

A more maintainable way to handle this situation would be to use an additional variable for flow control. You could create an extra variable called badAnswer which is initially set to 0. If either of the questions were answered incorrectly, badAnswer would be set to 1. You could then wrap an if/then statement around any code you only wanted to execute if the answers given weren't bad. This would stop the second question from being asked if the answer to the first question was bad, and it would stop the board from being drawn if the answer to the second question was bad. Here's the code. Copy and paste and experiment.



Now let's retry the tests that broke the code.

Seems ok this time.

Also seems ok this time.

Also also seems ok this time.

No cheese burger for you!

I pressed enter when prompted. It works!

Great! We've rewritten the code so that if incorrect inputs are given, the program will close gracefully without showing a board that looks like gibberish.

VMware training is expensive in Australia: go to Singapore!

Vendors have a history of overcharging Australians for software. Someone realised it was cheaper to fly to the United States to purchase Adobe Creative Suite than to purchase it locally. Unfortunately, it’s the same case with VMware training.

VMware vSphere: Install, Configure, Manage – the course you have to sit

This course (also known as the VMware ICM) is required if you want the VCP (VMware Certified Professional) certification. The course is mandatory if you want to be certified: if you haven't attended the course, you can't be a VCP even if you passed the exam. The good news about this arrangement is that every VCP has a minimum common level of knowledge, and the VCP hasn't been watered down like the equivalent Microsoft certifications. The bad news is that the course is AUD$3850 + GST. It's a nice cash cow for VMware, but not so good if you’re paying for the course yourself (like I did).

Why would you pay for the course yourself and not have your employer pay? Maybe your employer isn't interested in upskilling you in virtualization, or you're a contractor, or just someone trying to break into an infrastructure role. Getting VCP certified is a serious commitment and I hope to save you a few dollars if you're not lucky enough to have your training paid for.

All of VMware's training courses are listed on myLearn. If you click the Find a Class link, you'll have the option of searching for ICM. Here's a screenshot of the course details for ICM in Sydney.

Unfortunately, a 10% GST is applicable. 

However, the same course is available in Singapore for USD$2620, or only AU$2580! Is it cheaper to fly to Singapore, stay 7 nights, do the ICM course, then fly back for less?!

$3850 vs $2620? That's a saving of at least...fifty bucks!

It may very well be! Let’s put my theory to the test. To begin, the Australian price we need to beat is $3850 + GST (which is $4235, but I'll assume you don't own a company to claim GST). The course I've selected is at the VMware Singapore office on Temasek Boulevard. It starts on the 11th of March, but I like to arrive in a city a a day or two beforehand so I can settle in. If you were to fly from Sydney on the Saturday beforehand and return the next Saturday, it would cost you...

...after the customs user fee, immigration user fee, APHIS fee, federal transport tax fee,
security fee, passenger movement charge, passenger service charge, international surcharge,
facility charge and credit card fee, that comes to...

...$558.30, which leaves a few dollars for a hotel. The Porcelain Hotel is nice and it's close to the Chinatown NE4 MRT station, which is only four stops away from the Esplanade CC3 MRT station. Esplanade MRT is directly below the VMware Singapore office.

 You could stay at Hotel 81 for half the price,
but that place is a little strange.

The Porcelain is small and quirky, but at $953 it's very reasonably priced and has all the expected luxuries. In summary:

Cost of course in Australia if you don't own a company: $4235 ($3850 AUD + 10% GST)

Cost of course in Australia if you own a company: $3850

Cost of course in Singapore: $2620 USD ($2580 AUD, as at 2013-03-06 via Citibank)

Cost of return flights: $558.30

Cost of hotel for 7 nights: $953

Total: $4091.30

If you don't own a company and you're unable to claim GST, there's a $143 benefit in flying to Singapore, staying 7 nights, and attending the course at VMware's Singapore office! If you own a company, the GST rebate lets you attend the course approximately $250 cheaper than doing it in Singapore. But if I were you, I'd still do the course overseas because

• You'll get to meet people in the wider Asia Pacific VMware community you wouldn't normally meet. It's a good opportunity to network with other IT infrastructure professionals from a different region and see what their challenges are.
• The quality of the instructors is the same worldwide. It seems that the VCP instructors fly around the world.
• You'll be interrupted by phone calls if you attend the course in Australia. How many times have you attended course and seen people miss important lessons because they answered work phone calls during class time?
• The concepts taught in the ICM course are important and you'll be more focused if you don't have to worry about your usual day to day urgencies. The urgent always seems to overtake the important.
• The VMware Singapore office has a well stocked pantry with plenty of drinks and Toblerones!

If you're considering going to Singapore for the VMware ICM but want to reduce the price, you could use airbnb and stay in someone's spare room. And if travelling isn't an option, you can attend the course online via WebEx: it's the same price as classroom delivery, without any of the interaction.

Whether you attend the course in Australia, over WebEx, in Singapore, or any country, there's a lot of content in the VMware ICM to cover. And if you're new to VMware, be sure to pick the method of course delivery which is most conducive to your learning. It might not be the cheapest, but I hope it is!

The Hong Kong guide to the Paris guide to IT infrastructure

There are many metaphors for enterprise architecture. The most common one I've heard is that enterprise architects are the glue between an organisation's strategy and execution. This reads well as a LinkedIn status update or tweet, but you could say the same about project managers responsible for executing strategic projects, or CFOs who pick strategic projects and ensure they're funded. Whenever someone asks for my view on the role of enterprise architects, I like to say I'm a student of the "Paris" school of enterprise architecture.

The Paris Guide to IT architecture was an article published in the McKinsey Quarterly in 2000. It talks about the history of Paris and how the city's architecture and buildings have a consistent feel and theme despite architects who've had over 200 years to "improve" it. The consistency of Paris is used as a metaphor for IT architecture: just as the roads and public transport of Paris unite the buildings, define the landscape and set the terms for evolution (Laartz, 2000), enterprise architecture involves the systems and frameworks that unite applications and provide a way of integrating and accommodating disparate systems in a coherent way. Although it doesn't say it, the article hints that enterprise architects are the town planners of IT. I've never visited Paris, but the concept resonates when I compare Hong Kong or Singapore to lesser planned cities in Asia.

The IFC check-in service in Hong Kong strikes me as an example of a system that exists because other systems have been architected well. The Hong Kong International Airport (HKIA) allows you to check-in to your flight and drop your bags in the city, leaving you with a boarding pass and the opportunity to spend your day shopping and exploring the city instead of waiting in an airport lounge surrounded by stereotypes. While you do your shopping, your bags are securely transported to the airport, saving you the stress of carrying them or having to stop at your hotel before the airport.

International Finance Center (IFC): the building Batman jumps from in The Dark Knight.

The architecture for IFC check-in relies on the availability and openness of other systems like

• airline systems, to facilitate check-in at IFC.
• airport systems, to provide airport services including security, timetabling, messaging, alerting.
• the Airport Express rail system which provides mass transit from IFC (or any station) to HKIA
• luggage transport systems that move traveller luggage securely from IFC to the airport and provide handoff to the airport luggage routing system
• network systems, to facilitate secure and reliable communication with the airport
• et cetera

The actual specifics behind system integration isn't enterprise architecture: that's application architecture. The fact the required functionality and systems were available was because of enterprise architecture. During the architecture of the baggage system, the application and infrastructure architects may have developed the best solution for accepting baggage from an on-premise airline check-in desk and delivering it to a plane. But was their solution service-oriented? Was it open? How flexible would the solution be if a new requirement for bag drop from off-premise sources (such as the IFC check-in) was introduced? Or if bag drop from hotels was introduced? Upfront completeness of requirements is important, but part of enterprise architecture is knowing when to keep the door open and how to do it.

A town planner might know that every premise requires lines for sewage, electricity, water, gas and telephone, but they still might keep the door open for future services by requiring ducting infrastructure from streets to the home. If a new technology came along to replace copper telephone lines, existing ducting infrastructure would make the job a heck of a lot easier. And like in the real world, if you don't think ahead, rectification could either be costly or impossible.