Jamie's Blog

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

Tag: Math (Page 1 of 2)

Algorithmically Speaking, Of Course.

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.

This post might get a bit too “Mathsy” for some

A Book To End All Books… Kinda

So, recently I’ve been reading “The Art of Computer Programming”. By that I mean:

I bought a copy of “The Art of Computer Programming Volumes 1-4 just shortly after Christmas, and I’ve been working my way through them.

I’m only 40 pages into volume 1, but when you see the size of the tomes themselves… In fact, here take a look at them

These are just volumes 1-4. Knuth has been working on these since the late 60s

What This Has Taught Me, So Far

As I’ve said: I’m 40 pages into volume 1. So far it’s been all about the maths (pure, that is) of computation. But it also has an amazing section on Algorithm composition.

What’s An Algorithm?

In its most basic form, an algorithm is just a list of instructions. For instance, the algorithm for making a cup of coffee might be:

  1. Get a cup
  2. Add some freeze-dried coffee granules  to the cup
  3. Boil some water
  4. Add boiled water to cup with coffee granules
  5. Stir the mixture a little with a spoon
  6. Add milk and sugar to taste
  7. If you’ve added milk and sugar, stir mixture again

See that wasn’t difficult, was it?

What I did there was took a, so called, “Real World Problem” (How do I make a cup of coffee?) and broke it down into a set of simple steps. That’s all we ever do when writing/composing an algorithm. Seriously, that’s it. One of most important parts of Computer Science is that easy (not just making coffee, but understanding algorithms, too).

Its Taught You a Bunch Of Algorithms?

Nope. It’s taught me an amazing way to compose them.

Say we have a list of things; a shopping list, for example. How do we check through the list to make sure we have all the items in our basket? You might say something like:

Look at each item in the list in turn, and check whether its in the basket. Right?

Exactly. The only problem is, this is a little vague. We have no clear start and end points. How do we know if the thing is in the basket? How about this:

  1. Look at the first thing on the list
  2. Search through the basket for an item that resembles the first thing
  3. If you can find it, excellent. Move onto the next thing in the list
  4. If you can’t, boo. We need to find the thing in the store. Make a note of this thing, and move onto the next thing in the list

We’ve got too many “things”. And it’s still to vague. Let’s remove all the vague terms and construct a simpler way of writing this algorithm. How about something like this:

Initial Setup: Set N ← 1

Beginning: Look at Nth name in the list

Can you find an object that represents the Nth name on the list?

Yes: Set N← N + 1 Go back to the beginning

No: Make a note of the name of the Nth name on the list, set N ← N + 1, go back to the beginning

In this above block of text:

  • N is a number
  • ← means “Set the value of the thing on the left to that of the thing on the right”

Other than that, it should be quite simple to follow. There are other constructs in Knuth’s Algorithm composition, but I wont touch on them in this example.

Real Example

This is a real “problem” that programmers must take care of in at least one program that they will write in their career (I’ll guarantee it):

Look through a list of un-ordered numbers. Find the smallest and the largest. Sum them both. Find the difference between this new number and the largest number.

This is a problem that I remember vividly from my CompSci 101 classes at University. The first thing I ever did was break it down into individual sentences – this way, you break the problem down into single steps:

  • Look through a list of un-ordered numbers.

The list of number’s we’ve been given is in a random order. They are not sorted from smallest to largest, or largest to smallest.

  • Find the smallest and the largest.

We need to find two numbers. One that has the smallest value in the list, and one that has the largest value in the list.

  • Sum them both.

Once we’ve found both of these numbers, we’re going to add them together.

  • Find the difference between sum and the largest number.

Find the difference between the sum and the largest number (subtract one from the other).

The whole point of this exercise was not to write a program that would calculate this for you, but to write an process (an algorithm) for doing this. We were graded on how easy it was to understand our process. Some of the smart-asses in the group just re-wrote the list of things to do, verbatim. The didn’t fail, but were encouraged to give it a proper try.

Here’s what I came up with:

  1. Get the first number
  2. Get the next number
  3. Is the next number bigger than the first number?
  4. If it is, then
  5. ….

I’ll spare you the details, because the listing was massive – I seem to remember it being half a page of A4 (typed). There were a lot of stages where I looped back to the very beginning, and then jumped around a little. It ended up looking like spaghetti code by the end of the algorithm, and you HAD to follow along with a pen so that you could trace back to where you where.

It was terrible.

It taught me a lot of things.

I looked back at this algorithm, today. I shuddered to think that this was ever acceptable – to be fair, it was the first algorithm I’d ever written, and I was young a stupid.

I re-wrote the algorithm. Here it is:

  • Initial Setup: Set N ← 1, M ← 2, Smallest ← 1, Biggest ← 1, Sum ← 0, Difference ← 0
  • Beginning: Is N > M?
  • Yes: Set Biggest ← N, Smallest ← M
  • No: Set N ← N + 1, Set M ← M + 1, Go back to Beginning
  • Set Sum ← Smallest + Biggest
  • Set Difference ← Sum – Biggest

That’s it. Six lines instead of half a page of A4.

Why Algorithms And Note Code?

Let me put it this way: I can think of 5 different ways to implement this in code, off the top of my head. And that’s just in one language.

In C# (pronounced: “SEE SHARP”) you could do something like this:

And that’s not doing it the optimised way.

If we leave the a solution to a problem as an algorithm, that solution is easily implemented in all the different programming languages, in all the difference programming styles, by all the different programmers.

I think I’ll leave it there, for now. Mainly because there are far better resources out there (on The Internet [search for “beginning algorithms”] or in hundreds of books).

So, until next time: Stay frosty, people

J

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)

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

Fun with Fibonacci’s Numbers

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 2 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:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

The Algorithm

The first step I took was to calculate the Fibonacci sequence up to the limit of 4 million. That told me that the 33rd term was my stopping point (since the 33rd term gave the answer 3,524,578 and the 34th term gave the answer 5,702,887). The next step is to sum all of the even numbers between 0 and 33.

At it’s heart, this program is adding even numbers between 0 and 33. But instead of just adding the even numbers (2, 4, 6,… 32) together, I actually had the code calculate the Fibonacci sequence as well as a way of double checking my initial calculation.

This is good coding practise. Heck, it’s good maths practise. You should always check your answer. The last thing you’d want is to be sure that an answer is correct (especially something this large) with out checking it. Because, the chances are, you’ll have the wrong answer.

The Code

I’m not going to spend time explaining the code, since it should be straight forward for anyone with a little experience in the C family.

Psst. It’s written in C++

I’m also not going to explain how we calculate the Fibonacci sequence, since it’s not either terribly exciting, or even that hard to figure out from reading the code.
So, without further ado, here is the finished code:

It’s simple little puzzles like the above that improve your coding skills. Even if you start from a blank canvas.

Until next time,

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

5 Years in the Making

The Problem

Five years ago, I created a software project in C#. The goal was to create a clone of an old computer game called Gorillas. For those who don’t know abut this game, click this link for an article on The Wiki. Most people would have played a variant of this game based around cannons, though.

I’d got the game 90% complete in my time budget. The only things that where missing were textures (I was still only a baby programmer back then), and aiming code.

My not so elegant code for aiming was terrible, to say the least. By pressing left, right, up or down the player could change the position of the projectile (in this case, a banana). When the player pressed the fire button, the banana would be fired out in a straight line from it’s current position. For some reason, I’d felt that I would never be able to put code in that would make this aiming process simple.

Anyone who’s played the original (be it in tank of gorilla form) will know how to use the aiming system: Right to decrease the trajectory and Left to increase it. Simple.

For some reason, my brain couldn’t figure out how this was done. I tried and tried my hardest, but I couldn’t visualise it. At one point, I ended up trying to program a semi circle of points that could be selected by the user, but that went as well as this sentence seems to have done.

The Solution

Last night I was snuggled up in bed, watching an episode of Seinfeld. The episode ended, I turned the DvD player off, then got back into bed and started to fall asleep. All of a sudden the following image popped into my head.

 

Mario and Tanooki are used via Fair Use. No copyright infringment is meant. Both are copyrighted by Nintendo

At first I wasn’t sure what to make of it. Then, I figured out why the axis are there.

Pressing left will decrease the X value, but increase the Y value. Pressing right will increase the X value but decrease the Y value.

Both X and Y have pre-set limits, X can only be between 5 – 20 units in front of Tanooki and Y can only be between 5 – 20 units above Tanooki, for example.

This algorithm will successfully move the projectile (assuming you show it) around your gorilla (or tank, or Tanooki) along a quarter circle in front of it. In pseudocode it might look something like this:

[sourcecode language=”cpp”]
int projectileXPos, projectileYPos;
int upperLimitX, upperLimitY = 20;

// game code in here

switch (key) {
case left:
//without any bounds checking
projectileXPos–;
projectileYPos++;
break;
case right:
//without any bounds checking
projectileXPos++;
projectileYPos–;
}
[/sourcecode]

Calculating the Angle

So, you’re projectile is moving around the character in a quarter circle arc; which is great. But now you want to be able to fire along the correct trajectory? That’s really simple to work out.

If you look back at the image of Tanooki you’ll see a Greek symbol near his face. For those who aren’t familiar, this is symbol is called Theta and in trigonometry it represents an unknown angle. To calculate this angle we’re going to use something called SoH, CaH, ToA.

Copyrighted by processing.org. Used via Fair Use

If you look back again (what’s with all this looking?) at Tanooki, you might be able to see a triangle forming – the X axis and the trajectory forming the adjacent and the Hypotenuse.

We know all three values for the sides of this triangle (we actually only know two, but a quick bit of trig will calculate the Hypotenuse for us), so we can use any part of SoH CaH ToA to work out the angle.

We’ll use ToA for now, as we know both the Adjacent (X value) and the Opposite (Y value). But we could use either, if we worked out the Hypotenuse.

Again with pseudocode, it could look like this:

[sourcecode language=”cpp”]
#include <math.h>

int projectileXPos, projectileYPos;
int upperLimitX, upperLimitY = 20;
double opposite, adjacent, firingAngle;

// working out the angle

switch (key) {
case fire:
opposite = projectileYPos – player.GetYPos();
adjacent = projectileXPos – player.GetXPos() ;
firingAngle = tan(opposite/adjacent);
}
[/sourcecode]

To calculate the Hypotenuse, all you would have to do is basic Pythagoras. Again, in pseudocode it might look like this:

[sourcecode language=”cpp”]
#include <math.h>

int projectileXPos, projectileYPos;
int upperLimitX, upperLimitY = 20;
double opposite, adjacent, hypotenuse;

// working out the hypotenuse

opposite = projectileYPos – Player.GetYPos();
adjacent = projectileXPos – player.GetXPos();
hypotenuse = sqrt((opposite * opposite) + (adjacent * adjacent));
[/sourcecode]

Why Five Years

I know that this is really simple trig, and I know that the code for it is also really simple. For some reason, though it never crossed my mind to code it this way. I have no idea what prompted this “Eureka moment” for me last night, but I’m really glad that it did. Since then, I’ve been finding simple solutions to other coding problems.

I suppose my problem was, at that time, my whole life revolved around that one problem; as such, and to coin an old phrase, I couldn’t see the wood for the trees.  My best advice for anyone confronting a problem with no, obvious solution – regardless of whether it’s coding or math or life or whatever – is this:

Take a step back from it, and look at it from another angle.

If that doesn’t work walk away from it completely. Some of my other problems have actually been solved by me taking a break and going for a long walk.

If all else fails, watch something like Seinfeld.

I’ve found that, Seinfeld is my Plan Nine From Outer Space.

Anyone who has seen a few episodes of the X-Files will know what I mean there.

There’s that little going on, that my sub-concious mind can, and does, wander. This enables me to find the solutions without even thinking about the problems, while still enjoying the show.

More proof, if anyone needed it, that Larry David is a genius

A Promise Fulfilled

Looking back through my previous posts, I found 2 things:

  1. My average post length has dropped dramatically – not necessarily a bad thing
  2. I made a promise a while back to post something here

Post Length

A few of you will know that I’m quite the maths enthusiast. Obviously not on the scale of, say Carol Vordemon, but even so. Yes, I’m a maths nut, get over it. It’s the purest way to show ANY kind of data. Stick it in a graph, and we can all read it, regardless of language.

Being a maths nut, you’d expect me to have quantified my average post length and be providing you with some sort of formulaic break down, maybe with a graph or two.

Well, I’m not going to. I’m sure that the last thing most people will want to see is a whole butt load of stats maths, and graphs.

Needless to say, my average post length has declined. I’m not entirely sure why this is so. I mean, it’s not like I’ve got less time now, than when I started this blog. Maybe I’m just not using my time as effectively as I did back then.

I’ll soon get to the bottom of this… if I can be bothered, that is.

Even so, this can’t be a bad thing for most of the people who read these posts. I mean, the last thing anyone might want to read is a rambling rant of a post, written by me, that goes to over 1000+ words. At least, I’m giving your eyes a break from this drivel.

Plus, most of my rants are on a very specific topic. I mean, one of my longest posts was on Proprietary vs Open Source Software, something that might make sense to some, but may baffle and confuse others.

There’s more than one different kind of Operating System!?

or

What’s an Operating System? I though all computers ran on Windows

Another of my rambling rants of a post was about installing different Operating Systems.

The less of this the better, I feel.

A Promise

A few of you may remember (that is, if my hits counter is actually correct, and if I’ve actually gotten 870+ hits) that I promised to get a short screen play uploaded once I was happy with it. Well, I’m  not happy with it, it’s not finished, and still needs work, but a promise is a promise. I’ve added a link at the bottom of this post to it.

I’d appreciate feedback, but remember it’s all factual (I’ve changed the names of some characters, but it all actually happened).

Obviously, it’s a work in progress, and I’ve copyrighted it. It remains my intellectual property, and I’d appreciate it if it weren’t copied or distributed as you’re own work. I’ve no problem if someone uses it to make something similar, so long as I’m credited

Again, let me know what you think.

It’s 29 pages long, which means that it should be 29 minutes long. That being said, I suck at writing descriptions, so it’s mostly dialogue where I’ve ran out of adjectives.

Link to the PDF version.

It should open in a new window, and will be “zoomed” to 70%. It’s uploaded onto my website’s server, and should be on there permanently. But, if it ever goes down, I’ll upload it elsewhere.

Right, I’d best be off. Have fun, and let me know what you think

J

Page 1 of 2