To infinity...

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, ...


Find the sum of all the even-valued terms in the sequence which do not exceed four million.


There it is: sum up all even fibonacci numbers below 4 million. I already know how to sum and checking the value and even-ness of the number is easy. The only thing left to do is create a function for generating fibonacci numbers. Haskell doesn't have a built-in fibonacci number generator but there is one in the tutorials.

fibs = 1 : 1 : [ a+b | (a,b) <- zip fibs (tail fibs) ]


There is that fibs function that returns a list of fibonacci numbers. The first two elements of the list has the value of 1 followed by a list comprehension zips the current fibs it's tail and then adds the values of each item. This function creates an infinite list of fibonacci numbers so when I run it in winhugs, I get this:

Main> fibs
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987{Interrupted!}


I edited the output to remove the pages and pages of fibonacci numbers that got generated in the two seconds that the function was running before I was able to press Ctrl-C. Looking at the output, I know that it's generating the correct values. But I don't need the whole infinite list of fibonacci numbers: I only need the first ones that are under 4 million.

In Haskell, you can get the first few items of the list by using the take function:

Main> take 20 fibs
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765]


Good, I got the first two fibonacci numbers. Now, I should probably get more and then visually check how many do I need before I hit the first number that is above 4 million.

Main> take 30 fibs
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765, 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040]
Main> take 40 fibs
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765, 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040, 1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,
63245986,102334155]
Main> take 35 fibs
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765, 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040, 1346269,2178309,3524578,5702887,9227465]
Main> take 33 fibs
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765, 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,
1346269,2178309,3524578]


There you go. I got the first 40 and then noticed that the last item is now on the hundred million, did some manual binary search of take 35 fibs and then take 33 fibs until I found that last item is under 4 million.

Next step is take just the even numbers. There is this filter method meant just for that:

Main> filter (even) [1..10]
[2,4,6,8,10]


Looks good. Now I only have to plugin the take 33 fibs in there and I have a list of all the fibs under 4 million, and then sum it up.

sum (filter (even) (take 33 fibs))


Good.Project Euler accepted my answer.

Am I done? Well, I don't really like the hardcoded take 33 in the code. I want the code decide when to stop taking numbers out of fibs. Good thing take has this brother takeWhile that does the same thing butis more helpful. The takeWhile function expects two parameters: a predicate and a list. I can use takeWhile and then pass in a lambda that returs true as long as the current number is under 4 million. Let me test that:

Main> takeWhile (\x -> x < 5) [1..10]
[1,2,3,4]


Cool. I can now use takeWhile lambda instead of the hardcoded take 33 and it should still give me the correct result:

sum (filter (even) (takeWhile (\x -> x < 4000000) fibs))


I also read somewhere (I can't find the link) that you can sequence nested function calls like this using the $ function/operator. Let me try that:

sum $ filter (even) $ (takeWhile (\x -> x < 4000000) fibs)


It worked. That's it. Here's the complete source.

fibs = 1 : 1 : [ a+b | (a,b) <- zip fibs (tail fibs) ]
euler2 = sum $ filter (even) $ takeWhile (\x -> x < 4000000) fibs


Done.

Posted by jop | with no comments
Filed under: ,

Project Euler

 

I wanted to try my hand on solving the Project Euler problems. Here is my solution for the first problem.


If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

I've been trying to learn Haskell for a long time, so here's my chance. Fortunately, this is surprisingly easy in Haskell.

sum [x | x <- [3..1000], mod x 3 ==0 || mod x 5 ==0]

Basically, what it does is sum up all the x, where x is from 3 to 1000, and where x is divisible by 3 or 5. There is also a simpler way of solving the problem.

sum ([3,6..1000]++[5,10..1000]) - sum[15,30..1000]

This sums up the multiples of 3 and multiples of 5, but since the multiples of 15 exists two lists (on the multiples of 3 as well as the multiples of 5), subtract one set of multiples of 15 so you get the correct value.

Posted by jop | with no comments
Filed under: ,

Echo: Writing Testable Code

Miško Hevery:

To keep our code at Google in the best possible shape we provided our software engineers with these constant reminders. Now, we are happy to share them with the world.

 

Posted by jop | with no comments
Filed under:

Slow Start - Testaments and Books

Here is my answer to Keith's Bible App challenge. I know the deadline has already passed but I want to do it the TDD way, so here it is.

Again, the requirements.

  1. The user should be able to search for books based on a selected Testament (Old and New).
  2. The user should be able to see the contents of each Book
  3. The user should be able to search the contents of the Bible based on different search criterias like "Luke", "Genesis 1", "John 3:16", "love", "Abraham" and the application should be able to return the matching results.
  4. The user should be able to jump from one book to another.
  5. The user should be able to jump from one chapter to another.

So, five requirements, one rule: you have to use the database provided and you are not allowed to use any 3rd party libraries.

How do I approach this?

There's the direct form of attack. I can paint the screen, then generate the datasets and datatables from the database (with permissions from the wizards of vs.net, of course), and then use my lucky One Ring of Power to bind them all together. Nothing wrong with that really. A simple app like this can be written that way.

If this is how you would do it and you are not interested in another way, then press Ctrl-F4 or move on to the next item in your blog/feed/news reader. I wouldn't discuss that here.

What I'm presenting here is the alternative way of attacking this project - one where every piece of non-trivial code is driven and covered by tests - either unit test or integration tests. I'm sure someone would argue that for a simple application such as this, the technique that I'll be using is just plain overkill. I would agree with you. But that's not the point of this article. This is about demonstrating how to write tests for your code.

OK? Good. Let's start.

I've already decided on just copying the look of CryptoKnight's application - treeview on the left hand side, book contents on the right hand side and then a search box on top. I already know what the application does - allow the user to view and navigate through the bible, perform searches, etc. I can think of a couple of ways of implementing this.

  • Option 1 - on launch, the application loads all the data from the mdb file and into memory. This is not unlike how CryptoKnight did it - except that I won't be using datasets but actual objects. The advantage here is that I'll be working with objects for the majority of the application. I can represent the book concepts clearly and without translation - testaments have books, books have chapters and chapters have verses. I can just navigate through the graphs of objects to get from one place to another. Drawbacks: the app should load a little slower because it is loading the data from the database during launch. It should also have a higher memory footprint. I also need to write my own searching algorithm. That shouldn't be that hard though. I should be able to use the String methods to perform the searching and the I'll just wire up the objects themselves to perform the searching for me. It'll should also present a few interesting concepts. For example, I can ask each Book to search their own Chapters and all those can be done on their own separate threads! Not sure if that is needed here, but it's a possibility.

  • Option 2 - only load the root nodes (the testaments) on launch and then load the rest on demand. This should give me a faster launch time. After that, I have two choices - either I only retain the viewable contents in memory, or lazy load the contents as they are being requested. Either one is not a simple as working with the whole set of objects or data in memory though, so that's one of the disadvantages of this approach.

CryptoKnight's version is written using DataSets and all the data is loaded into during launch. So it has already been proven that whole bible can be loaded into memory. Searching is also done in memory - using the dataviews. That is essentially the same as the first option.

Cruizer took the second route.

I think for now I'll do the first scenario. During launch, I'll be loading all the tables and into an object graph rooted at the Testament level. The testaments, books and chapter are in the treeview. Contents will be on the contents pane on the right hand side. Searches are done in-memory.

Here are the initial list of tests based on the requirements.

  • a testament can hold many books
  • a book can hold many chapters
  • a chapter can hold many verses
  • a verse is searchable
  • a chapter is searchable
  • a book is searchable
  • a testament is searchable
  • load object graph from database

The last item is a 'technical requirement'. We can delay the implementation for that as long as we can and we will still have a running application. We can just create the testaments, books, chapters, verses in code. In fact, that is not even interesting - I have written a lot of DALs in my lifetime and that piece is just another DAL. I'd rather start with the real interesting parts of the application -- searching and displaying the book.

The first test - let's check if the tools are properly hooked up.

    using NUnit.Framework;
    
    namespace BibleApp.UnitTests
    {
        [TestFixture]
        public class CoreTests
        {
            [Test]
            public void TestShouldFail()
            {
                Assert.IsTrue(false);
            }
    
            [Test]
            public void TestShouldPass()
            {
                Assert.IsTrue(true);
            }
        }
    }

I run the test. The first test failed and the second test passed. That means the tools are configured properly. I can now write my first real test.

I'll start with the test "a testament can hold many books". I think this can be easily done in one shot but I'll go slow for now. I'll start with a fresh testament.

    using NUnit.Framework;
    
    namespace BibleApp.UnitTests
    {
        [TestFixture]
        public class CoreTests
        {
            [Test]
            public void NewTestamentHasNoBooks()
            {
                Testament t = new Testament("Old Testament");
                Assert.AreEqual(0, t.BookCount);
            }
        }
    }

It doesn't compile because Testament doesn't exist. I'll let Resharper generate the class and properties using a flurry of F12 (Goto next error) and Alt-Enter (QuickFix).

    internal class Testament
    {
        public Testament(string name)
        {
            throw new NotImplementedException();
        }

        public int BookCount
        {
            get { throw new NotImplementedException(); }
        }
    }

Now it compiles but it when I run the test - it fails. Not surprising since I'm throwing NotImplementedExceptions. I'll fix that

    internal class Testament
    {
        public Testament(string name)
        {
        }

        public int BookCount
        {
            get { return 0; }
        }
    }

Now the test passes. But it doesn't do anything - it just returns a fake value. Let's ignore that bit for now and add another test:

    [Test]
    public void TestamentCanHoldOneBook()
    {
        Testament t = new Testament("Old Testament");
        t.AddBook(new Book("Genesis"));
        Assert.AreEqual(1, t.BookCount);
    }

Then create the new class and method.

    internal class Book
    {
        public Book(string name)
        {
        }
    }

    internal class Testament
    {
        public Testament(string name)
        {
        }

        public int BookCount
        {
            get { return 0; }
        }

        public void AddBook(Book book)
        {
        }
    }

It compiles but the test fails. I can fake it again - or not. I will have to implement this properly sooner or later, so why not do it now. I'll use a generic list to hold the book and then simply return the list count as the book count.

    internal class Testament
    {
        private List<Book> _books;
        public Testament(string name)
        {
            _books = new List<Book>();
        }

        public int BookCount
        {
            get { return _books.Count; }
        }

        public void AddBook(Book book)
        {
            _books.Add(book);
        }
    }

There you have it - a unidirectional association of Testaments to Books. I ran both tests and the both pass. I think the test "a testament can hold many books" will now work. Let's see.

    [Test]
    public void TestamentCanHoldManyBooks()
    {
        Testament t = new Testament("Old Testament");
        t.AddBook(new Book("One"));
        t.AddBook(new Book("Two"));
        t.AddBook(new Book("Three"));
        Assert.AreEqual(3, t.BookCount);
    }

And it does - all three tests pass.

There you go - a Testament that can hold many books. Let's scratch off one test.

  • a testament can hold many books
  • a book can hold many chapters
  • a chapter can hold many verses
  • a verse is searchable
  • a chapter is searchable
  • a book is searchable
  • a testament is searchable
  • load object graph from database

You might have notice that the Book and Testament classes are both internal. That is because resharper did not generate separate files for them. I transferred them to their own files, made them public, re-ran the tests, they all pass, and I'm done for now.

Next up, I'm going to show testament objects into the UI and give you a taste on how to write unit tests against the user interface.

Posted by jop | 4 comment(s)
Filed under: ,

Markdown Viewer

I'm not really fond of browser based text editors - especially the one used in here in devpinoy. I still write my posts using my favorite editor - gvim, and then paste them over to the blog software.

That is sufficient if you are only writing plain text all the time. What if you wanted to have code in your post and you want it to have syntax highlighting?

The only browser-based editor that I can tolerate is the one in StackOverflow and it uses Markdown.

Markdown is a text-to-HTML conversion tool for web writers. Markdown allows you to write using an easy-to-read, easy-to-write plain text format, then convert it to structurally valid XHTML (or HTML).

Markdown isn't really something new. If you open up a on old text document that you have, chances are, it's already using markdown. :-) What's cool with StackOverflow's editor is that has an markdown autopreview and you can mark a block as code and it will apply syntax highlighting magic using Google's prettify script.

So, what's should a programmer do? I can't just leave my favorite editor and then type all my posts in StackOverflow just so I could use the generated HTML? Nope - what I wanted is to still use gvim for editing (it even has a markdown mode) and then have another app that watches the file I'm editing and then transforms it into HTML everytime I save my changes.

That's what I have here. I'm typing the content using gvim...

Gvim Markdown

...and then I get to see the preview of what I am typing on my Markdown Preview application.

Markdown Preview

Then, all I need to do now is click on the Copy button and I paste the HTML over to the blog editor. The only missing piece is devpinoy - it does not yet support prettify! Keith!


This wouldn't be possible without Milan Negovan's Markdown.NET and Google's prettify. You can download a copy of the source code here if you find this useful.

Posted by jop | 3 comment(s)
Filed under:

Not a PC

John Hodgman: A brief digression on matters of lost time.

Posted by jop | with no comments

Google Tech Talks -- Unit Testing

 

A 32-min intro on unit testing. Watch it. Four stars.

Posted by jop | with no comments
Filed under: , ,

I told you so.

 I can't stop but smile at what I've written in this forum thread.

A decade ago, I am constantly having this similar debate with my managers, project leader, team leader, quality engineers, etc. about the merits of unit testing. As I was still inexperienced then, I am not really in favor of unit testing because (1) I'm the one doing the task, (2) I have to spend a lot of time doing it - that takes away from 'coding' time, and (3) I can't see the benefit of doing it because we already have a dedicated team of system testers that will catch the defects anyways. I get annoyed because the people on the other end of the debate aren't really doing any of the coding so they definitely don't understand what they are saying.

Now, a decade after, it feels like I'm channelling my managers/project/team leaders. I've gained enough knowledge to know the benefits of unit testing, had enough practice to know how to do it properly so I don't really spend a lot of additional time writing tests and I don't mind doing the task because it still is coding. I'm now on the other side of the debate - pro-unit-testing, pro-TDD even, and I'm still on the trenches, writing code.

Posted by jop | 6 comment(s)
Filed under: ,

How to use Patterns

Erich Gamma said:

Do not start immediately throwing patterns into a design, but use them as you go and understand more of the problem. Because of this I really like to use patterns after the fact, refactoring to patterns. One comment I saw in a news group just after patterns started to become more popular was someone claiming that in a particular program they tried to use all 23 GoF patterns. They said they had failed, because they were only able to use 20. They hoped the client would call them again to come back again so maybe they could squeeze in the other 3.


Trying to use all the patterns is a bad thing, because you will end up with synthetic designs—speculative designs that have flexibility that no one needs. These days software is too complex. We can't afford to speculate what else it should do. We need to really focus on what it needs. That's why I like refactoring to patterns. People should learn that when they have a particular kind of problem or code smell, as people call it these days, they can go to their patterns toolbox to find a solution.

Posted by jop | 2 comment(s)
Filed under: ,

Estimation

Today, I attended a seminar about Function Point Analysis.


To me, this seems to be a very magical way of estimating a piece of functionality. It is so different from that way I used to come up with my estimates that, though I haven't tried it yet, I can't help but think of reasons why it won't work.


Such type of thinking is not beneficial if you are trying to learn something. So, I'll give FPA some chance. In the end, I might end up not liking it after all, but at least I would know why.

Posted by jop | 7 comment(s)
Filed under:

Domain Experience

How come certifications are based on the technical skills of a programmer rather than business expertise?

If a manager of a company needs a C# programmer for their accounting system, isn't it more logical to look for a developer that has a good grasp of accounting which also happens to know how to program in the target language?

Unless your business is teaching technology, why would a company look for those certified in a certain brand of technology?

Posted by jop | 15 comment(s)
Filed under:

VS.NET: Reference EXE assemblies

Nice! Visual Studio 2005 now allows Class Library projects (DLL) to reference Applications (EXE).

On Visual Studio 2003, EXE projects are not listed on the Add Reference dialog. The .NET framework does not put any restrictions on what you can reference. I think the IDE programmers thought they're helping us (or me) by only showing the DLLs there.

It's a problem because I used to work on some applications that are not big enough to warrant separating the UI and the core logic. I would only have a single EXE assembly but I am forced to create a separate assembly for classes that needs to be tested because my test projects can not reference the EXE file.

I am currently working on a small utility application so I tried it just now and it worked! Very nice...

Posted by jop | 1 comment(s)
Filed under:

Now that's what I call a desktop!

Think of the possibilities:

  1. Magic the Gathering
  2. Internet mahjong; with realistic tile shuffling -- none of that randomizer stuff
  3. Solitaire, the way it should be played
  4. CRC cards!
  5. UML
  6. Billiards
  7. Table Hockey
  8. Piano
  9. Drums (pressure sensitive?)
  10. Massage tutorial !
  11. DJ mixing table
  12. Computer sculptures
  13. StarCraft II
  14. And finally, tables that turns blue all of a sudden...

http://www.microsoft.com/surface/ 


Posted by jop | 3 comment(s)
Filed under:

Hex

Open a file on Binary Editor using Visual Studio's Command Window

> File.OpenFile myfile.dat /editor:"Binary Editor"

 

Posted by jop | with no comments
Filed under:

Composed Method Pattern

Msg #129624 on the extremeprogramming Yahoo! Group

Some people swear that they would rather see all the code in line,
rather than separated out into small methods. I think that the
in-line people should be prevented from breeding.
-- Ron Jeffries regarding the Compose Method pattern.

Haha!

Posted by jop | 1 comment(s)
Filed under:
More Posts Next page »