Geekality

Interlude

Torleif — Fri, 05 Feb 2010 18:43:23 +0000

Not much is happening at the moment. Well, actually quite a bit is happening. It’s just that I find myself in a rather non-eventful interlude of some sort.

Last Friday (January, 29th) I had my last day at SMS Development & Support AS where I have been working for the last 1.5 years. It was my very first job as a full-time software developer and I learned a lot. Both about developing software and about myself as a developer. Good stuff!

Next up I will return to LifeStyleTV where I spent a year as a Media Missionary. This time I will be working there as a regular employee and help out with various things. Mainly I will be developing some internal software systems with some of the others there, but I will most likely also help out with the TV production. I am going down there the 11th of February and I am looking forward to get started.

What am I doing now, during this interlude? Not a lot. Very little. Extremely little. My computer is dead. I’m sick. My energy reserves are non-existent. I’m sleeping, eating, watching tv, reading… and that’s pretty much it… To be honest I am actually kind of happy I am sick now instead of earlier or later. Just hope I will be back to normal before Thursday…

How to check for duplicates

Torleif — Tue, 19 Jan 2010 16:57:09 +0000

Say you have an IEnumerable of some sort and you want to check if it contains any duplicates. How do you do that?

Terrible solution

I needed to do this a while ago and the first solution that hit me wasn’t exactly good. Linq has method called Distinct, which returns the distinct items in a sequence (weeds out duplicates). Using that to check if duplicates exists you can do something like this:

var hasDuplicates =
subjects.Count() != subjects.Distinct().Count();

This is of course a really bad solution. So don’t use it!

Good solution

The much better solution is to use a HashSet.

The HashSet class provides high performance set operations. A set is a collection that contains no duplicate elements, and whose elements are in no particular order.

In addition to the fact that it cannot contain duplicate items, it also has a very nice add-method which returns false if the item is already in the set.

To check for duplicates using a hash set we can start out by assuming there is no duplicates and then add items to the hash set until we either run out of items, or we try to add an item that already exists. In the first case our assumption was right and in the second it turned out to be wrong.

var set = new HashSet<T>();

var hasDuplicates = false;

foreach (var s in subjects)
if (!set.Add(s))
{
hasDuplicates = true;
break;
}

Good and handy solution

Since we don’t want to type in that stuff over and over again we want this snippet in a nice extension method. Code snippet coming up

using System.Collections.Generic;

namespace Geekality.Snippets
{
public static class EnumerableExtensions
{
public static bool HasDuplicates<T>(this IEnumerable<T> subjects)
{
return HasDuplicates(subjects, EqualityComparer<T>.Default);
}

public static bool HasDuplicates<T>(this IEnumerable<T> subjects, IEqualityComparer<T> comparer)
{
if(subjects == null)
throw new ArgumentNullException("subjects");

if(comparer == null)
throw new ArgumentNullException("comparer");

var set = new HashSet<T>(comparer);

foreach (var s in subjects)
if (!set.Add(s))
return true;

return false;
}
}
}

Simple and handy. You use it for example like this:

if(subjects.HasDuplicates())
{
// Do something
}

Hope it can help someone, somewhere, below and/or over the rainbow

Let me know what you think. I’m always open for improvements and feedback

Test-Driven Development: By Example

Torleif — Tue, 01 Dec 2009 17:36:16 +0000

I earlier wrote about the book, The Art of Unit Testing, which I finished a while ago. That book was very good and was focused on how to write good unit tests. It also mentioned Test-Driven Development, TDD, but not too much. The book I read next, which I finished a few days ago, was kind of the other way around. Pretty much only about TDD. And from the title, Test-Driven Development: By Example, that shouldn’t be much of a shocker

The book is written by Kent Beck and explains the basics about TDD. It does this pretty well, step by step, by example, just like the title says. The book also talks some about TDD in a more general sense. What it is, how it works, why it works, et cetera.

From the back-cover:

Readers will learn to:

Solve complicated tasks, beginning with the simple and proceeding to the more complex.

Write automated tests before coding.

Grow a design organically by refactoring to add design decisions one at a time.

Create tests for more complicated logic, including reflection and exceptions.

Use patterns to decide what tests to write.

Create tests using xUnit, the architecture at the heart of many programmer-oriented testing tools.

It pretty much kept the promises The only part I didn’t really like about this book was that I found much of the coding kind of messy. Could be because the languages used in the examples are Java and Python, which I don’t really like that much syntax-wise. An even more important reason though, is that I just finished reading The Art of Unit Testing So, I suppose I have become a bit demanding when it comes to cleanliness when coding and writing unit-tests. I suppose that is a good thing (I do however not claim in any way that the code I currently write is extremely clean in any way! But I do strive for it to be so )

I can really recommend this book to anyone who are curious to get familiar with TDD. I certainly see the value of doing TDD and is in the process of trying to incorporate it into my development habits.

Red — Write a little test that doesn’t work, and perhaps doesn’t even compile at first.

Green — Make the test work quicky, committing whatever sins necessary in the process.

Refactor — Eliminate all of the duplication created in merely getting the test to work.

Red/green/refactor — the TDD mantra.

You can get it at Amazon, and probably a lot of other places too as it is a pretty well-known book.

How to test asynchronous events

Torleif — Thu, 26 Nov 2009 18:59:59 +0000

The other day I had to test that an event was raised after some asynchronous work had been done. And since I currently am a total test newbie, this was a new thing for me. Say we have this simple shell of a class:

public class Worker
{
public event EventHandler<EventArgs> Done;

public void Start()
{
...
}
}

Let’s just assume it does some work, and is supposed to raise the Done event when it is… well… done.

Synchronous worker

If the Worker class works synchronously, it would be no problem at all to test it. For example:

[TestFixture]
public class WorkerTests
{
[Test]
public void Start_WhenFinished_DoneEventIsRaised()
{
var worker = new Worker();

var eventWasRaised = false;
worker.Done += (s, e) => eventWasRaised = true;

worker.Start();

Assert.That(eventWasRaised);
}
}

We simply add an event handler which sets a boolean flag when called, start the worker and then check if the flag was set or not. Easy peasy.

Asynchronous worker

What now if the Start method just sends the work to a new thread and returns immediately? Our current test can not be trusted at all in that case. It might pass and it might fail. Most likely fail. All depending on if it managed to finish its work and raise the event before we check the flag. And that would be unlikely to happen. Highly unlikely.

So what do we do? We use a ManualResetEvent instead of the boolean flag:

[TestFixture]
public class WorkerTests
{
[Test]
public void Start_WhenFinished_DoneEventIsRaised()
{
var worker = new Worker();

var eventWasRaised = new ManualResetEvent(false);
worker.Done += (s, e) => eventWasRaised.Set();

worker.Start();

Assert.That(eventWasRaised.WaitOne(500));
}
}

Instead of checking that a flag has been set, we check that the event handler gives us a signal within a certain period of time. If it doesn’t give us that signal we can assume that the event was never raised or that the work simply took longer than we expected. Either case could probably be of interest

Brilliant, simple and readable. Just how we like it

Credits

I am still a total testing newbie at the moment and didn’t have a clue what to do, so after some failing google-fu I asked a question about it at StackOverflow. My solution is based on one of the answers I got there

Generics and checking for null

Torleif — Fri, 13 Nov 2009 16:19:15 +0000

When writing C#, in Visual Studio, using generics… have you ever tried checking for null? I have always found that a bit of a hassle.

Say we have this method which returns the subject if it is not null, and the result of a createNew() function if it is null.

public static T NewIfNull<T>(this T subject, Func<T> createNew)
{
if (subject == null)
return createNew();
return subject;
}

Not claiming this is a very useful method, but it was the simplest thing I could come up with Anyways, in Visual Studio you will now probably have a blue (is blue here at least) squiggly line under the equality operator. It states you are doing a Possible compare of value type with ‘null’, which of course is reasonable and correct. We could just ignore it and move on… but we don’t really like squiggly lines, do we? I sure don’t… so lets get rid of it.

Faulty solution

ReSharper suggests that I use default(T) instead of null, like this:

public static T NewIfNull<T>(T subject, Func<T> createNew)
{
if (subject == default(T))
return createNew();
return subject;
}

Now, this won’t do at all. First of all, we don’t really want to check for default(T), we want to check for null. And second of all, we now have a long red squiggly line under the whole equality statement! It says that it Cannot apply operator ‘==’ to operands of type ‘T’ and ‘T’. That messages doesn’t really make much sense to me, to be honest, but I trust that it is true. Either way, we have to get rid of it.

Good solution

ReferenceEquals to the rescue! We can use that method, instead of the equality operator, and compare with null like we intended!

public static T NewIfNull<T>(T subject, Func<T> createNew)
{
if (ReferenceEquals(subject, null))
return createNew();
return subject;
}

That is kind of ugly though… And it is so much longer to type. And, most importantly, it kind of makes the code a bit unreadable… At least if you have a bunch of things you have to check for null, like I did today.

But fear not! Today I came up with a tiny, but brilliant extension method which makes things a lot better:

public static bool IsNull<T>(this T subject)
{
return ReferenceEquals(subject, null);
}

public static T NewIfNull<T>(T subject, Func<T> createNew)
{
if (subject.IsNull())
return createNew();
return subject;
}

Doesn’t that just look a lot cleaner? I think so

And yes, I know this isn’t really a big issue. And I realize you have probably all come up with something similar already. Yes, I am slow But hey, I figured it might be worth sharing this anyways, just in case you hadn’t thought about it before. I sure hadn’t! And I really do think that tiny snippet of code made a huge difference in code readability. And we all want that, don’t we? Yes, yes we do…

Project Euler: Problem 25

Torleif — Fri, 06 Nov 2009 22:51:56 +0000

The Fibonacci sequence is defined by the recurrence relation:
, where and .

Hence the first 12 terms will be:

…

The 12th term, , is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

Solution

We touched on the Fibonacci sequence a while ago in the second euler problem. This time, however, we are in a whole different league. That time we were supposed to sum up all even Fibonacci numbers below 4 million, which might sound like a lot, but not when we compare it to the number we are asked for this time! The last Fibonacci number below 4 million is 3524578. That would be 7 digits. The maximum value of the datatype I used in the generator I made for that (ulong) is 18446744073709551615. That would be 20 digits. Quite a distance left to a thousand!

So, once again we turn to our big integer class, IntX. And since we have that, a solution to this problem is actually pretty straight forward. We simply have to make a new generator that uses the IntX data type instead of tiny ulong (it’s all relative…).

public class LargeFibonacciSequence : IEnumerable<IntX>
{
public IEnumerator<IntX> GetEnumerator()
{
var a = new IntX(0);
var b = new IntX(1);

while (true)
{
yield return a;

var c = a + b;
a = b;
b = c;
}
}

IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}

The straight forward solution should then be fairly obvious.

var n = 0;
var sequence = new LargeFibonacciSequence();

using (var e = sequence.GetEnumerator())
{
while (e.MoveNext() && e.Current.ToString().Length < 1000)
n++;
}

var answer = n;

That pretty much just moves through one Fibonacci number after the other, increasing n as it goes, until it reaches the first one that has 1000 or more digits.

Very brute-force, not very fast (takes around 500 ms) and not very interesting, but that’s pretty much it… ooor is it?

Take two!

Alright, while reading up on Fibonacci numbers I found some interesting mathematical formulas and such. I’m not going to come with an in-depth explanation or lots proofs here, but I will share the formulas that matters and go through how we use them. If you want the elaborate explanations you can find them where smarter people than I reign. For example at Wikipedia, or at this site. Anyways, here we go. Take cover if you fear math…

The Fibonacci sequence

The th number in the Fibonacci sequence, , is defined by the recurrence relation

with the seed values and .

This recurrence, since it is linear, can be expressed by a closed-form solution known as the Binet’s formula:

— (The Golden ratio)

Now, why and is considered the same, or even why that formula works or looks like that, I will leave as an exercise for the reader (Cause I have no idea Please share if you do…). But anyways, as an example, if you put 20 into that formula, you will get 6765 which is the 20th number in the Fibonacci sequence. Fantastic. We could now use that formula to make another brute-force solution to find the term we are after. But that wouldn’t make much sense and would be much much slower. So, we must move on further into this crazy land.

Before we move on to the next part, since we will be working with quite large values of , we can simplify that expression a bit. That is because will move pretty fast towards 0 as increases. In other words, we can pretty much just skip that part and use the following formula instead:

The length of a number

How do you calculate the length of a number? I actually had to do this in an earlier post and then I kind of cheated. I just converted the number into a string and just count the characters (In C#, string.Length). But, I recently discovered that there actually is a way you can do this mathematically! I had no idea… The key lays in the logarithm to base 10.

(often written as just ) for any 1-digit number will give you 0.something. For any 2-digit number it gives you 1.something, and so on. So a formula for getting the length of any number:

In case you were wondering, those weird square brackets are called the floor function.

The length of a Fibonacci number

Now we are able to calculate the length of a certain Fibonacci number by using the following formula, which I for no good reason will call G:

There is a problem here though. And the problem is . Why is it a problem? Because it get’s seriously large very quick. A value of around 500 actually makes my calculator overflow and just give me an error.

But fear not! There are a couple of formulas having to do with roots and logarithms that we can use to our advantage:

With those formulas we can handily rewrite our formula into one that is easier to handle:

Tadaa! Now we can push in 20 and get 4. And as we calculated earlier, the 20th Fibonacci number is 6769, which in fact is 4 digits long! Amazing…

The first Fibonacci number with 1000 digits

Now we are almost ready to solve our problem. The formula we have now works perfectly. The only problem is that it’s backwards! We are not looking for the length of a certain Fibonacci number, but rather what Fibonacci number has a certain length. In other words, we want , not . Luckily, using pretty basic algebra and some guessing, we can make a new formula that finds exactly what we are looking for. (My way of skipping the floor stuff and introducing a ceiling function in the end is purely based on guessing and observation. But it gives the correct answer Now, if you know the proper way of handling it, please let me know! )

Now we can just substitute with 1000, and calculate , which should be the answer to this problem!

As usual, I will not put the actual answer here though

This has been the longest blog post yet about these problems, I think, but I must say it was pretty fun to solve this one. I didn’t really get much at first, just saw that the formulas worked, but now that I have written about it and gone through it all step by step, it actually makes sense. Most of it anyways. If you know how to properly handle that floor and ceiling stuff, let me know

Anyways, that was it for now! Stay tuned for more good stuff like this

Project Euler: Problem 16

Torleif — Thu, 05 Nov 2009 16:46:16 +0000

and the sum of its digits is
.

What is the sum of the digits of the number ?

Solution

With the big integer type IntX (which I added to my project to solve an earlier problem) this one is pretty much as easy as you’d think.

var answer = IntX
.Pow(2, 1000)
.ToString()
.Select(x => x - '0')
.Sum();

It first does the calculation and then gets the string representation of the result. And in case you were wondering, that would be:

10715086071862673209484250490600018105614048117
05533607443750388370351051124936122493198378815
69585812759467291755314682518714528569231404359
84577574698574803934567774824230985421074605062
37114187795418215304647498358194126739876755916
55439460770629145711964776865421676604298316526
24386837205668069376

And as a comparison, here is the largest number that can be represented using built-in .net types. decimal.MaxValue.

79228162514264337593543950335

As you can see, the first number is kind of bigger than the second Aaaanyways, the next bit might be a bit cryptic. But fear not, it is actually quite simple:

A string is an array of characters.
All characters have a character code (a numeric value).
The character codes for the numeric characters (‘0′, ‘1′, and so on) comes after each other, which means that for example ‘1′ has a character code value which is 1 larger than the character code of ‘0′.
If we take a character code and subtracts it from itself, we get zero. (Thank you captain obvious…)
This means that if we subtract ‘0′ from ‘0′, we get 0. And if we subtract ‘0′ from ‘5′, we get 5. (Oh, right, clever!)

So, the last two lines in my code simply converts all the characters in the string into actual numbers and then sums them together. Which would get us the answer! Tadaa

How did you do? Have you found a more interesting solution? Please do share