Jamie's Blog

The ramblings of a programmer with a little too much time on his hands

Tag: Code Examples (Page 1 of 2)

Code Project: RGB to Y’UV

Edit (18/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

Jargon

In case you don’t know what they mean, I’ve included the following list of jargon terms and rough descriptions of them.

RGB = Red, Green, Blue

YUV = similar to RGB, except that luma (Y) and chroma (U and V) are stored

Sources?

Most of the information for this post came from the Wikipedia article on YUV. You can visit it here: [LINK]

RGB? YUV?

Last week, a friend of mine wanted to meet in the city centre and go for a nosey around the TV stores. He’d recently bought his own place, and is decorating it and looking for a new TV.

While we were walking around “Electronics-Company-That-Isn’t-Named-After-A-Spicy-Food-At-All”, we spotted the Sony and LG LED TVs. I got to wondering whether TV transmissions are still sent in YUV, and whether those same signals were converted to RGB before being displayed on screen.

When I got home, I decided that I should look into YUV and see just how it works. I didn’t actually get around to reading about YUV until this afternoon, but when I did it made sense.

The human eye is more sensitive to changes in brightness, rather than certain colours. So, why  not send the luma (brightness) information and the chroma (colour difference) information?

Back in the days of blank and white TV, all that the TV broadcasters had to send was the luma (brightness) information. As colour TV was invented, top boffins thought that the best (read: “way that requires less bandwidth over the air”) way to send the colour information was the extend the model of just sending luma information, this time including chroma information.

The best way to understand this is to see it. Luckily, Wikipedia have an amazing example. In the following picture (click to enlarge):

  • The top image is how it is displayed on screen in any picture browser
  • The second (blank and white) image is the luma data for the image
  • The third (mostly blue and green) image is the U chroma data for the image
  • The forth (mostly yellow and orange) images is the V chroma data for the image
An image along with its Y', U, and V components.

Images via Wikipedia

They could have ditched the older system of just sending luma, and gone with a purely RGB system. However, this would have required the transmitters to send redundant, extra data over the airwaves. Plus, the older blank and white TV sets would no longer have worked. If a blank and white TV is used, then it simply ignores the UV portion of a received signal.

Also, the data being sent can be compressed before sending over the airwaves. In fact, the video portion of digital broadcasts are compressed in (almost) the same way. Because the human eye is more sensitive to changes in brightness, the chroma differences can be compressed (sampled fewer times), thus reducing the bandwidth.

Why Are You Telling Me All Of This, Jamie?

Basically, one of the ways that I can tell if I understand something that I’ve just learnt is to test myself in some way.

Ever wondered why you have exams in most of your classes?

Also, this links into my (very basic) teacher training:

  • Teach something to the student(s)
  • Get the student(s) to tell you what you’ve just taught them in their own words

Anyway, I’ve tested myself by taking what I’ve learnt about the RGB to YUV conversion and created a small C program that converts RGB to YUV.

At the minute it only converts a set of user inputted strings that represent the RGB values and returns their YUV equivalents.

My browsers built in spell check system is telling me that “inputted” isn’t a word. I’m sure that it is. In fact, a whole slew of Internet resources tells me that it is.

Anyway, onto the code. I wont write any more information about the code than this (as everything else should be included in the comments for my code, hopefully):

I compiled this on MS Windows 7 x64, with MiNGW’s gcc with the following options/command:

gcc <path to source file> -o RGB.exe -O2

/*
 * Project Name:        	RGB to Y'UV
 * Solution Name:		RGB to Y'UV
 * Original creation date:	19/11/2011
 * Edit date:			18/01/2013
 * Programmer name:		Jamie Taylor (aka "GaProgMan")
 * File name:			YUV.c
 * 
 * Purpose of the project:
 *	I was reading through a wikipedia article on
 * 	the differences between YUV and RGB and found it
 * 	very interesting.
 * 		For those who don't know, YUV is a colour
 * 	space - a way of storing colour for digital images,
 * 	film and TV. It focuses on storing Luma
 * 	(brightness - as Y') and two chrominance (colour
 * 	- as U and V) values.
 * 		Most video and still images are stored  in
 * 	this format, as it takes into account the Human
 * 	eye's ability to perceive differences in brightness
 *	at higher definition than differences in colour. This
 * 	greatly reduces the data bandwidth required to send
 * 	and receive images and film in this format.
 * 		This short program explores the mathematical
 * 	formulae used to convert colour data from the RGB
 * 	colour space to the Y'UV colour space.
 * 		For an in-depth description Y'UV, RGB and
 * 	the formulae used, please see the following
 * 	website:
 * 			http://en.wikipedia.org/wiki/YUV
 * 
 * Formulae used:
 *	To convert from RGB to Y'UV, the following
 * 	will be used:
 * 			Y' = W[r]R + W[g]G + W[b]B
 * 			U = U[max] * (B - Y') / (1 - W[b])
 * 			V = V[max] * (R - Y') / (1 - W[r])
 * 		Where:
 * 			W[r] = 0.299
 * 			W[b] = 0.114
 * 			W[g] = 1 - W[r] - W[b] = 0.587
 * 			U[max] = 0.436
 * 			V[max] = 0.615
 * 		Note:- I have placed square brackes around
 * 	the letters in the formulae that are written in
 * 	subscript. This is to make it easier for the
 * 	reader.
 *
 *	GNU Copyright information
 *	Copyright 2011 Jamie Taylor <jamie@taylorj.org.uk>
 *
 *	This program is free software; you can redistribute
 *	it and/or modify it under the terms of the GNU General
 *	Public License as published by the Free Software
 *	Foundation; either version 2 of the License, or (at
 *	your option) any later version.
 *
 *	This program is distributed in the hope that it will
 *	be useful, but WITHOUT ANY WARRANTY; without even the
 *	implied warranty of MERCHANTABILITY or FITNESS FOR A
 *	PARTICULAR PURPOSE.  See the GNU General Public
 *	License for more details.
 *
 *	You should have received a copy of the GNU General
 *	Public License along with this program; if not, write
 *	to the Free Software Foundation, Inc., 51 Franklin
 *	Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/

/* included libraries */
#include <stdio.h>

/* Constants that will be used for RGB to Y'UV */
#define WEIGHTEDRED	0.299
#define WEIGHTEDGREEN	0.587
#define WEIGHTEDBLUE	0.114
#define UMAX		0.436
#define VMAX		0.615

/* function declarations */
void convertFromRGB ();

/* global variables */
float redValue;
float greenValue;
float blueValue;
float yPrime;
float uValue;
float vValue;

int main () {

  /* read values for RGB into memory */
  printf("Please input a value for RED:");
  scanf("%f", &redValue);
  printf("Please input a value for GREEN:");
  scanf("%f", &greenValue);
  printf("Please input a value for BLUE:");
  scanf("%f", &blueValue);

  /* convert RGB to Y'UV */
  convertFromRGB();

  /*display results */
  printf("\nFor the RGB input (%.2f, %.2f, %.2f),\n",
    redValue, greenValue, blueValue);
  printf("The following Y'UV is outputted (%.2f, %.2f, %.2f)",
    yPrime, uValue, vValue);
  return 0;
}

void convertFromRGB (){
  /* 
   * implement formula:
   * Y' = W[r]R + W[g]G + W[b]B
   */
  yPrime = (WEIGHTEDRED * redValue) +
    (WEIGHTEDGREEN * greenValue) +
    (WEIGHTEDBLUE * blueValue);

  /*
   * implement formula:
   * U = U[max] * (B - Y') / (1 - W[b])
   */
  uValue = UMAX * ((blueValue - yPrime)
    / (1 - WEIGHTEDBLUE));

  /*
   * implement formula:
   * V = V[max] * (R - Y') / (1 - W[r])
   */
  vValue = VMAX * ((redValue - yPrime)
    / (1 - WEIGHTEDRED));
}

One last thing: If you’re going to compile and run this yourself, remember to put a blank line at the end of the source code. It’s ANSI C, after all.

When I added my source code to this page, it had the blank line at the end. But when I previewed the page, the blank line was pruned from the code viewer provided by WordPress.  But if you click on either “View source” or “Copy to clipboard” (when hovering over the source code black), you’ll get the code with the blank line at the end.

Until next time,

J – “Soul, peace and chicken grease” (as my brother says)

Random Quotes Generator Screenshot

Random Quote Generator

Edit (18/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

So, I was looking through some of my old hobby code today and happened on an old quote generator. It’s a neat little (the executable weighs in at 24Kb) C# program that provides the user with a random quote from some of my favourite TV shows.

Random Quotes Generator Screenshot

A screen-grab of my Random Quote generator showing a picture of Professor Ueda Jiro and a quote from the TV show Firefly

The Algorithm

  1. Find a text file called “Quotes.txt”
  2. Load each line in the text file into an element in an array
  3. Display a standard Windows form with a picture and a text box.
  4. When the user pressed the “Generate Quote” button, ‘randomly’ pick one and display it in the text box.

The Code

The code itself is pretty simple. It compiles on .NET 2.0.50727 and will only run with a text file called “Quotes.txt” located in the same folder as the executable.
[gist https://gist.github.com/4569288 /]

For those wanting to compile this code, you’ll need to provide Visual Studio with a JPEG image. In the original solution, I called this image “Dontokoi!” (as this is the catchphrase of the character in the image). Without this image, I doubt that the program will execute correctly.

Post Mortem

Aside from the above comment about the image being required for compilation, I did notice another potential problem with the program.

For some reason, apostrophes (‘) aren’t rendered correctly when the accompanying text file is encoded in anything but UTF-8. Since I know very little about text file encoding and the default way that the .NET libraries import text into a string array and the way that .NET draws this text into a text box, I can only assume that the problem is related to the formatting of the text file (saved, using Notepad++).

Either that, or it’s related to one of the settings within the Visual Studio IDE itself. I do remember that, around this time, I was attempting to compile all of my code with direct support for Unicode, so maybe that’s it.

I’m not sure, to be honest. But I am planning on opening the solution file (at some point) and having a good look around. The reason I haven’t opened the solution file at the minute is because I don’t own a copy of Visual Studio; which makes opening a Visual Studio file quite difficult.

Here’s a link to a zip of the entire solution, in case you wanted to take a look (The executable is in Bin/Release along with an old Quotes text file) [LINK]

Until next time,

J

Problem Six – In C

EDIT (18/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

 

Reading a comment on my most recent post, I felt that I could optimise my code for Project Euler’s Problem Six. So, I went away and read up on the information provided by Kristan (in the comments section), and decided that I’d give it a go… in C.

There were a few reasons for switching to C, the biggest was that I only have a C compiler installed on this machine (a minimal install of MingW), another being that I’m a little more informed about the optimisation options (which I didn’t use for this project) that gcc provides.

Anyway, on with the code.

Firstly

This is a solution to problem 6 on Project Euler. I’ve not posted it up here to gloat, or to provide answers for cheats. I’ve posted it, so that you can see how I solve this kind of problem.

The original problem reads like this:

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 – 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

The Algorithm

Based on my code from the previous version of this project, and the knowledge provided by Kristan and The Internet at large, I’ve used a slightly different algorithm this time around. I’ve covered the algorithm in the comments section for my code, though. So, I guess you should just scroll down and read that.

I’m not a massive fan of providing information twice, in the same format. That and redundancy. That and redundancy

The Code

I’m not going to spend time explaining the code, since it contains enough information in the comments (within the code itself) and in the description of the algorithm above.

So, without further ado, here is the finished code:

By the way, I compiled this code with the following command:

gcc “Problem_Six_In_C.c” -o “Problem_Six_In_C.exe” -Wall

A simple problem with an extremely simple, now optimised,  solution.

Here’s a link to the c file: LINK

Until next time,

J

Sums and Squares – Or: How I Solved Project Euler Problem 6

Edit (18/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

Firstly

This is a solution to problem 6 on Project Euler. I’ve not posted it up here to gloat, or to provide answers for cheats. I’ve posted it, so that you can see how I solve this kind of problem.

The original problem reads like this:

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 – 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

The Algorithm

There’s only one way to solve this problem.

This one is real simple – dependant on your understanding of Mathematics – assuming you can understand Square Numbers.

It’s a two step approach:

  1. Sum (add up) all of the squares of the numbers between 1 and 100
  2. Sum all of the numbers between 1 and 100, then square the answer
  3. Then find the difference between them (subtract one from the other)

There’s a slight problem with this method, though. Skipping ahead – and, hopefully teaching you all a little about speed-of-light Maths – we get:

There is a well known story about Karl Friedrich Gauss when he was in elementary school. His teacher got mad at the class and told them to add the numbers 1 to 100 and give him the answer by the end of the class. About 30 seconds later Gauss gave him the answer.
The other kids were adding the numbers like this:
1 + 2 + 3 + . . . . + 99 + 100 = ?
But Gauss rearranged the numbers to add them like this:
(1 + 100) + (2 + 99) + (3 + 98) + . . . . + (50 + 51) = ?
If you notice every pair of numbers adds up to 101. There are 50 pairs of numbers, so the answer is 50*101 = 5050.  Of course Gauss came up with the answer about 20 times faster than the other kids.

That version of the story comes, courtesy of Dr. Math. The actual story has been around for… well, since the days of Karl Friedrich Gauss

Anyway, skipping to the end, we find that the sum of all the numbers from 1 to 100 comes out at 5050. A quick calculation tells us that 5050 squared (5050 * 5050) is 25,502,500. Quite a big number, wouldn’t you say?

That’s fine, but logic tells me that the other number I’m working out (the sum of the squares) will be huge, compared to this one. So, and int just wont do it.

Dependant on your system, an int can store a value between +2,147,483,647 and – 2,147,483,646 (32 bit)

So because of this, potentially, massive answer, I decided to code this by using an unsigned long long (sometimes called a long int) type.

Again, dependant on your system, an unsigned long long can store a value between 0 and +4,294,967,295 (32bit)

Of course, I’m running 62 bit, so the maximum values that these two variable types can hold are doubled. But that’s not the point.

The Code

I’m not going to spend time explaining the code, since it contains enough information in the comments (within the code itself) and in the description of the algorithm above.

So, without further ado, here is the finished code:


A simple problem with a simple solution.

Here’s a link to the cpp file: LINK

Until next time,

J

Pining For Primes – Or: How I Solved Project Euler Problem 5

Edit (18/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

Firstly

This is a solution to problem 5 on Project Euler. I’ve not posted it up here to gloat, or to provide answers for cheats. I’ve posted it, so that you can see how I solve this kind of problem.

The original problem reads like this:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

The Algorithm

Firstly, there are two ways to solve this problem. One involves brute force, and one requires a little savvy.

Technically, there are a whole bunch of ways to solve this problem – dependant on your understanding of Mathematics. Hopefully, both of these methods will be simple enough to follow – assuming you can understand Prime Numbers.

The brute force check goes like this:

  1. Start at n, check this against all numbers in m
  2. If n divides evenly (i.e there is no remainder) by all the numbers in m, stop. This is the answer
  3. If not, add 1 to n and start again.

“n” starts at 1 (this is the smallest positive number that will divide by all the numbers from 1 to 20)

“m” starts at 1 and goes only as far as 20 (this is the series of numbers that “n” has to divide by)

That’s it.

The smarter algorithm goes like this:

  1. Start with n at 2520
  2. If n divides evenly (i.e there is no remainder) by all the numbers in m, stop. This is the answer
  3. If not, add 2520 to n and start again.

This method assumes that you recognise a few things from the problem statement. Let’s take another look:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Since the numbers between 1 and 20 contain all the numbers between 1 and 10 (1, 2, 3, 4, 5, 6, 7, 8, 9 & 10), some of the work is done for us. We can assume that, since 2520 is evenly divisible by all numbers between 1 and 10, that it must be evenly divisible by all the numbers between 1 and 20.

This algorithm speeds up execution exponentially. Instead of going through every positive integer between 1 and he final answer, we can jump in steps of 2520.

The Code

I’m not going to spend time explaining the code, since it contains enough information in the comments (within the code itself) and in the description of the algorithm above.

So, without further ado, here is the finished code:

And there you have it, another problem solved (and optimised) in minutes.

Until next time,

J

UK Tech Days – Day 2 (Windows 7 Phone)

The publishing of this post as postponed by three days because of problems with Jamie’s connection

Today was the second day of Microsoft’s UK Tech Days conference on the Windows 7 Phone format. It took place at the Fulham Broadway Vue and covered the topics involved in developing and deploying software ‘apps’ for the Windows 7 Phones.

The Start screen of Windows Phone 7

Image via Wikipedia

Content

Today’s content was focused on data loading and types. Whereas most of yesterday was based on loading the data into memory and manipulating it, today’s focus was on getting the data to the device in the most efficient way.

A user wont use your app if they notice that their [phone bill’s] data rates go through the roof

That goes hand in hand with the key point of the Windows Phone 7 presentations:

Reducing app installation regret; we don’t want users to install an app, then have regret about using it for any reason. This can be accomplished by having great quality code on these devices alongside quality data loading

The keynote for today was going to be Brandon Watson going through some of the key information in Microsoft’s press release from last night, but his voice wasn’t up to scratch. Instead, he took us through some key ideas and features that Windows Phone 7 devices have in place of the iDevices and the Android phones.

It says a lot about a device when the best selling app is an app killer. Windows Phone 7 has the best garbage collection service out there…

I’ve been told that the Android devices are better because they have dual cores, but a dual core takes more power, and more power means less run time…

The amount of software libraries that we [Microsoft] provide to developers is ridiculous…

Hardware Limitations?

All phones have compasses built into them, but very few of them have pre-built API’s to access it – something that the Windows Phone 7 SDK has. One thing to remember, though, is that some Windows Phone 7 devices don’t have gyro’s in them.

If a gyro isn’t present, then motion detection and the augmented reality API will be buggy

Software for Developers

Along with Visual Studio – current version is 2010, but there is a new version out soon (2011) – there are a plethora of different tools available for Windows Phone 7 developers.

There are the Mango development tools; which will enable developers to get a handle on the new features coming to version 7.1 (or 7.5, or “Mango”) of the OS FOR FREE

There are design tools; for instance Expression Blend, which allows designers and developers alike to quickly program the UX (User eXperience) with the standard code by dragging and dropping items onto a design area.

There’s obviously Silverlight; which looks like it powers the entire device. Also, it’s NOT a replacement for flash (as most people seem to be saying).

The No 1 Thing to take From the Conference?

The importance of design, rule #1: DON’T GET A MULLET

Mullet’s look out of place more than most hair styles, and so do “dodgy” controls and UI items. If they’re not meant to be there, don’t use them.

UK Tech Days – Day 1 (Windows 7 Phone)

Today was the first day of Microsoft’s UK Tech Days conference on the Windows 7 Phone format. It took place at the Fulham Broadway Vue and covered the topics involved in developing and deploying software ‘apps’ for the Windows 7 Phones.

Windows Phone 7 Review

Image by clintonjeff via Flickr

Content

Most of the content was made up of developers who have created some truly amazing apps, discussing their apps and showing off the code.

That’s one of the things about Software Development that doesn’t make sense. With all the NDA’s (Non Disclosure Agreements), patents and copyrights placed on Software, it almost doesn’t make sense that these guys would be showing off their code with such pride. But, that’s just it: they’re proud of the code that they’ve produced.

The keynote speech was provided by Brandon Watson, one of the many geniuses working over at Mircosoft, trying to make the Windows 7 Phone format as good as it can be. He seems like an awesome guy, and he had plenty of time for questions after his keynote.

He even took the time to answer my, probably zanny questions.

Code Examples

Most of the code discussions and examples revolved around data structures and performance – which is pretty cool. I mean, mobile phones only have a finite amount of CPU power and memory.  Some of the information given makes a lot of sense now that I think about it, again. I mean:

  • When a timeout occurs, or the screen locks, the program that is currently running is terminated. The program will restart from where it left off, when the screen is unlocked
  • De-Serialise (or load) data from storage into memory using a background thread, not the UI thread. Doing it that way works out as a better experience for the user, because you can keep animating your progress bar
  • As long as your program has a splash screen and a progress bar (for loading), most users will wait patiently for the program to load
  • Always assume that the network the phone is connected to is quite flimsy, and could cut out at any time. That way, you force yourself to use it sparingly
  • Target audiences always want simplification when it comes to mobile apps. They don’t need to know how the app works, just that it works

Excellent Quotes

Brandon started the whole day off with the best piece of pseudo-code I’ve ever seen. When a manager is asking you to provide some information about return on investment, just show him this:

[sourcecode language=”cpp”]
if (Developers.Happy())
return OnInvestment;
[/sourcecode]

Then there was this amazing gem of code. It’s C#, but will show up as C++:

[sourcecode language=”cpp”]
SomeFunction myFunction = new SomeFunction();
myFunction.SomeMethod += (s, a) => {
//code in here to catch an exception
};
[/sourcecode]

That code block is a short hand form of the standard way to catch a thrown exception. The only problem is, I’me not sure if it’ll only work on a W7P project, or whether it’ll work in a C# listing. Since I’m not at home, I can’t test it out.

That’s all for now, but I’ll make sure to post about what happens tomorrow (including some of the information about a press release that Microsoft are giving out tomorrow)

J

Folding and Libraries

Libraries

I was once asked what I considered an excellent question in an interview. One I managed to screw up completely.

Why do we used standard libraries in place of our own code?

The context for this question was this: I’d just completed a task were I had to, in pseudo-code, implement a function for combining strings. I think I ended up with something similar to this (again, this is pseudo-code):

[sourcecode language=”cpp”]
string CombineString (string firstString, string secondString) {
//create a new string with enough space for both strings to be copied
string combinedString = new string;
combinedString.malloc(firstString.GetLength() + secondString.getLength());
return combinedString = firstString + " " + secondString;
}
[/sourcecode]

Firstly, this wont work. Secondly, this isn’t what I wrote up on the whiteboard that day. This is just a naff example to give you some kind of context with which I was approaching the question.

Now then, the question itself is very simple to answer:

Standard libraries have, we assume, been through a rigorous testing procedure to make sure that they conform to the design documents perfectly, and to make sure that there aren’t any bugs. They are also very simple to implement, compared to designing a library yourself and having to teach the entire team how to use it. They save time, money, and improve productivity – assuming that they are the right libraries for the right task to begin with.

Simple, ne?

I forget what my answer ended up being, but I don’t remember saying much along those lines.

Folding

Most of the past few weeks has been taken up with building muscle/working out, watching The Soprano’s (I’ve never seen this before) and folding. Although, I’m implying that I’m the one whose done all the folding.

I’ve instructed my PC to use the spare cycles on 3 out of my 4 cpu cores and my gpu core to help understand the process of protein folding. A lot has been said about protein folding, and most of it can be found on The Wiki. Needless to say, I’m doing my part. I care for a lot of people, and the problems that CAN be linked to improper folding of proteins are huge.

My PC is still running very efficiently. I’ve got to hand it to the guys over at Stanford, they know how to write a really good piece of distributed code. I’m still able to browse the Internet, watch videos, and even play games. Excellent coding guys.

Watching

I know that The Soprano’s ended back in [goes to check] 2007, but it takes me a while to get into American TV shows, mainly because there’s that much out there. I don’t want to waste my time and (more importantly) money on something that I’m not going to enjoy. I’ve got to say that I’m enjoying The Soprano’s very much, though. I’ve only just started season 2, but it’s drawn me in already.

Plans For The Weekend

Well, that’s this short update done. I’m hoping to get some coding done over the holiday weekend (4 day weekend!!!), and whatever I get done is getting posted on here. Maybe I’ll come up with something interesting. Probably not, though.

Well, have fun.

J

FizzBuzz

Edit (19/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

Firstly, I realise that I’m not the best developer in the world. I can, certainly, hold my end up in C++; read a lot of C and understand it; work my way through a C# listing with confidence; understand enough of an assembly listing to VERY vaguely get what it’s doing.

Secondly, I’ve been using twitter and the blog-o-sphere for a few weeks now, to try and figure out what’s missing from my virtual tool kit (if you like) of developer skills. So far, the answer has been a resounding “Experience is better than a degree”

For instance, Gaven Woolery over at #AltDevBlogADay mentions that (and I’m paraphrasing):

In this age, with the relative ease of access to both online and offline tutorials/books/whatever, and the relatively un-homogeneous structure of Computer Science degrees in most Higher Education facilities, what’s the point of going to [University] for 4 years, and racking up a large debt, when you can just learn all of that at home?

Here’s a link to the original article : Link

This all is beginning to make sense to me. Don’t get me wrong, I thoroughly enjoyed my studies at University. But there where a few modules (known as classes to some) that were better studied at home, or in the labs than sat in a lecture theatre. Then again, there were modules that required that level of theoretical understanding.

I like to think of Computer Science being a perfect marriage between both vocational and non-vocational training.

This leads me onto something that Richard Banks blogged about in the middle of 2009: Some “Developers” Just Can’t Develop. Basically, his argument is for testing new recruits DURING the interview process. Something I have taken part in for some (not all) of my interviews.

I remember during one interview, in the middle of a question even, the interviewer got up and asked me to write some code “it can be in any language you want, even psuedo code,” to copy two strings

Because of my experience, I can certainly see what Richard is talking about. The cost of hiring the wrong person can be crippling. That being said, he links to a post from early 2007 (a year before I graduated, for those who want to know) by Jeff Atwood called “Why Can’t Programmers.. Program?”

The main thrust of Jeff’s post is to promote the idea of using a standardised test during interview processes to find out if the candidate is “good enough.” That being a completely subjective term (some companies require different skills from their employees, especially graduates), he even goes on to say:

Like me, the author [of, yet another post] is having trouble with the fact that 199 out of 200 applicants for every programming job can’t write code at all. I repeat: they can’t write any code whatsoever.

The post Jeff refers to mentions a test that is used by some professionals to see if a candidate can solve “simple” tasks.

FizzBuzz

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

Fain enough, that’s quite easy. One for loop and three checks. Easy.

Most good programmers should be able to write out on paper a program which does this in a under a couple of minutes. Want to know something scary? The majority of comp sci graduates can’t. I’ve also seen self-proclaimed senior programmers take more than 10-15 minutes to write a solution.

What!? How is that possible?

I really hope that the teaching of programming has improved since 2007, otherwise graduates haven’t got a chance of getting that juicy development role they tell themselves they deserve.

In fact, I think it has improved. At least, my experience of the teaching of programming seems to have been quite an amazing one and I’ll prove it to you.

Taking that basic task, I created a solution with 17 lines (including white space) in, roughly, 3 minutes (damned keyboard’s too stiff) that solves this problem; and it goes a little something like this:

I usually have extra newlines in there for formatting and clarity. But I think it looks just as good without them.

There you have it.  A solution to a simple problem in less time then a “self-proclaimed senior programmer” and, dare I say it, an elegant solution, too?

J

Code Examples 5 – Collision Detection in C++

Edit (19/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

Firstly

The post is not going to explain how the chosen algorithm works, although I might cover the basics. I’m going to leave understanding of the algorithm and code up to the reader. Hopefully it’s not that complex, though.

Why Re-Write It?

I re-installed Visual Studio today, and started itching for something to code. Then I remembered that a friend had recommended that I write a program containing my collision detection code to show it off.

Apparently, the pseudo-code and explanation I’d produced for it was quite good.

So, I decided to turn the pseudo-code into actual code. Thinking it wouldn’t take too long, I sat down at my pc and started coding. Providing the background music was Miles Davis (specifically the album ‘Sketches of Spain’, which I recommend to anyone).

I decided that I’d produce some code in C. But Visual Studio doesn’t have support for C, so I decided to give it a go in C++ instead.

Seeing how C++ is just an extension of C (clever naming convention, eh?), it shouldn’t be that different. Especially since I didn’t use any custom objects.

Two hours later, I emerged from my coding “deluge” with a a whole slew of twitter/facebook messages (I tend to zone out when coding) and some working code… sort of.

The Algorithm

It worked, but not entirely as expected. There was a problem with the internal logic, which I quickly fixed (more on this can be found in the change log, linked at the end of this post). Firstly, though, the algorithm.

When we look at a graph with 2 straight lines plotted on it, we can see instantly if the lines intersect (if they cross over each other) at some point. For instance:

Lines 1 and 2 intersect at the point (3,2), we can see this by looking at the image

Looking at the image, we can see that lines 1 and 2 intersect at the point (3,2). We can see that, because we humans have a power that a computer doesn’t: We can see the image as a whole, whereas the computer would see that image as a collection of pixel locations. So how do we get the computer to look for an intersection?

Firstly, we must decide if there is an intersection. There’s no point checking all of the individual locations if we don’t know whether there is a collision or not, as this is very costly (in CPU time); especially since the image area is likely to be rather large. After we’ve decided that there’s a collision, we’ll look for a point of collision.

There are lots of different ways to do this and each has their own benefit. A simple system, for instance would be to check the x value of some point against the x value of some other point. If those points match, check the y values. If they match, then there has been a collision. This is really simple to write, and very simple to read.

[sourcecode language=”cpp”]
bool checkForCollision () {
if (myXValue == someOtherXValue) {
if (myYValue == someOtherYValue) {
//a collision has occured
}
}
}
[/sourcecode]

The problem with this is that every single x value position needs to be checked, at least, once.

Another way would be to create a bounding box. This is slightly less simple, but easier on the cpu. Basically the idea here is to create a list of points around your object and check those against the positions around the other objects. Here is an article on wikipedia about bounding boxes.

The method I chose was to think of the entire screen as a graph. Working with a start and end position for my objects instead of a single set of x and y values, I can create a virtual line that goes through the space each of the objects takes up. Then, by using some, high level, maths we can find out whether any of these lines have crossed.

Look again at these lines

Line 1 consists of two sets of points, (1, 1) and (4, 3) and Line 2 consists of the points (1, 4) and (4, 1). by taking these points and throwing them at a mathematical formula, we can tell if they intersect. By the way, there are 4 formulae to work this out.

  1. x intersection point = x1 + ua (x2 – x1)
  2. y intersection point = y1 + ua (y2 – y1)
  3. ua = (x4 – x3)(y1 – y3) – (y4 – y3)(x1 – x3) / (y4 – y3)(x2 – x1) – (x4 – x3)(y2 – y1)
  4. ub = (x2 – x1)(y1 – y3) – (y2 – y1)(x1 – x3) / (y4 – y3)(x2 – x1) – (x4 – x3)(y2 – y1)

The format for the points are thus:

Line 1 = (x1, y1) to (x2, y2)

Line 2 = (x3, y3) to (x4, y4)

How Does I Use It?

The first thing we have to do is find out if there is a collision anywhere between these two lines. We do this by working out formulae 3 and 4.

Both formulae 3 and 4

As long as the answers to both of these formulae are greater than 0, then we can say that there is a collision happening. Using the values for ua and ub, we can find out the position of the collision by feeding these values back into formulae 1 and 2.

I Get Ya… Sort Of

Now that I’ve discussed a little about how it works (I, intentionally didn’t cover it all because there are tonnes of websites out there that explain the maths better than I can), I’ll post the code.

A quick note: I’ve intentionally made this code a little hard to read. This is so that anyone who block copies this code wont be able to explain how it works without some intense study of the code.

Until next time, have fun,

J

Page 1 of 2