Project Euler

by Kofi Sarfo 25. August 2009 00:43

"Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems." - Project Euler .Net

Maths problems aren't something we've been going out of our way to find. In fact we were looking for Code Katas when we found Project Euler. The first Code Kata, Supermarket Pricing, isn't immediately a programming problem. In fact it doesn't take a tremendous leap to flesh out concrete example code even though the real idea is to practise some modelling. So in pursuit of an immediate problem requiring an immediate solution via code:

#1 Add all the natural numbers below one thousand that are multiples of 3 or 5

No, it's not in the least bit difficult but that's not the idea. The obvious solution:

public static long AddNumbersThatAreMultiplesOf(int Min, int Max, int[] Primes) { long sum = 0; for (int i = Min; i < Max; i++) { foreach (int p in Primes) { if (i % p == 0) { sum += i; break; } } } return sum; }

It's an example of doing just enough to get the right answer. A better solution (cleverly translated from PHP) is below:

public static double GetAnswerUsingMoreOptimalSolution() { long max = 1000; double SumOfMultiplesOfThreeBelowMax = 1.5 * (int)((max-1)/3) * (int)((max+2)/3); double SumOfMultiplesOfFiveBelowMax = 2.5 * (int)((max-1)/5) * (int)((max+4)/5); double SumOfMultiplesOfFifteenBelowMax = 7.5 * (int)((max-1)/15)*(int)((max+14)/15); return SumOfMultiplesOfThreeBelowMax + SumOfMultiplesOfFiveBelowMax - SumOfMultiplesOfFifteenBelowMax; }

This more optimal solution (not mine) looks to be derived from GCSE mathematics, the formula for arithmetic progressions: A sum of terms equals (n/2)(a+l), where n is the number of terms, a is the first term, and l is the last term.

Note: The obvious refactoring in GetAnswerUsingMoreOptimalSolution() has been left intentionally :)

Interview with the Hedge Fund

by Kofi Sarfo 24. August 2009 00:03

We interviewed with a London-based Hedge Fund last Friday and, as usual, it was interesting. The first guy I saw (head of development) is a graduate of Conchango, a company that writes software of excellent quality using good developers, the latest software technology and techniques, etc. Also, they often kindly host the London Dotnet User Group meetings at their offices near London Bridge.

Naturally the interviewer asks fair questions along the lines of Value Types versus Reference Types and Garbage Collection. Inheritence and Shadowing. So far so good. Only when we get to the Messaging architecture used and extended at the previous client's site is there a little uncertainty. Without the source code, which we didn't take with us, we can't remember enough detail about the implementation from July 2008 so there's one shaky answer.

Next up is a question about our exposure to SQL Server 2005. Yup, we used it. Oh, which bits? That will be the new Try-Catch (after a little prodding about error-handling). We mention not having used CLR functions but being aware of the possibility which leads to a question about the components of the CLR... and we've a blank moment!

The JIT compiler! In fact we mentioned just JIT.

This is *all* that arrives. That's it. Nothing about Exception-Handling, Memory Management, Thread Management, Garbage Collection, Security, Managed Code, Type Safety - this is an impressive list already - Portable Executables nor IL never mind debugging and profiling services offered. Oh, there's more that wasn't mentioned. Code management (loading and execution), Application memory isolation, Access to metadata (enhanced type information) and Interop. Nice.

Then comes the first of a few quirky incidents. Hint: If ever an interviewer testing your C# knowledge offers the Base Class Library as a component of the CLR it's probably worth saying something. To prevent an already lengthy entry from growing needlessly still a summary will do here. When Interviewer #1 is replaced by a senior developer I then learn that impersonation does not work the way I've used it. Apparently, I've misundersood all along that using the identity element in the web config for an ASP.NET web application will not allow me to use credentials for a SQL Server connection. Maybe at that point I should have just looked it up on my iPhone and shown him this:


<system.web>
<identity impersonate="true" userName="domain\username" password="password" />
</system.web>
Of course that might have seemed a bit smug. Both nice guys. Both almost certainly good developers. I'd still like to work with them on the enterprise reporting solution due by the end of the year. However, during my next interview we won't assume that the interviewers have a monopoly on .NET understanding.

Mengembalikan Jati Diri Bangsa

by Kofi Sarfo 9. July 2009 16:12

From what we can make out this appears to be a fictitious SEO contest. What's interesting is the digital grafitti it spawned. We're using Kamus.net to try and make sense of it during another brief distraction.

Late last year a web solutions company offered cash prizes to whomever was able to gain the highest position on Google for a specific search term. What surprised me is that the winner had only a handful of links to the winning entry page. Cue hurried attempt at Jerry Springer style closing remarks. It's great that the web opens up possibilities for someone to earn more in a few months via an SEO competion than, say, the typical annual salary according to GDP per capita figures - I thought it might be useful to highlight this figure against that for the country in which I was born - but the problem I suppose is the spam it encourages. Blog post comments are an obvious target, for example.

Notes:

The Anatomy of a Large-Scale Hypertextual Web Search Engine
The paper presented to the Computer Science Department, Stanford University. This doesn't appear to have happened before 1997 at the earliest, demonstrating the beauty of scaleability in a nicely recursive kinda way.

How Bloggers Game Google
Ah, the great democracy of the web at work. Plus rant. Plus explanation.

It's easier to forget the details of SQL Transaction Isolation levels (during interview)

by Kofi Sarfo 26. June 2009 00:45

So I interviewed again yesterday with a City-based asset management company you've probably not heard of but a cash rich client is exactly what we need right now. Shaking off a cold hit-hard mid-week wasn't ideal circumstance but it wasn't feeling less than fabulous that did the trick but in part, in fact, not being able to remember how each of the SQL Server Transaction Isolation levels might impact queries on the same table.

This is partly why I like interviews. Potentially embarrassing situations during which one is able to demonstrate what one cannot remember. Here's what the MSDN entry has to say about the SET TRANSACTION ISOLATION LEVEL (Transact-SQL) command which controls the locking and row versioning behavior of Transact-SQL statements issued by a connection to SQL Server. Yay.

So the story in a nutshell is that using this command it's possible, amongst other things, to allow dirty reads if that's the desired result. In order to try the code below in SQL Management Studio use one tab to run the transaction once all the necessary database objects have been created and another tab to view the results of the different isolation levels.

We create a table to use for holding some random values.

CREATE TABLE RandomLetters
(
     ID int IDENTITY(1,1) NOT NULL
    ,Letter varchar(32) NOT NULL
) 

In order to populate this table with some random values we rely on a stored procedure inspired by one over here.

CREATE PROCEDURE sp_GenerateRandomLetters
     @Length int
    ,@randomLetters varchar(32) OUT
AS
DECLARE @counter smallint
DECLARE @RandomNumber float
DECLARE @RandomNumberInt tinyint
DECLARE @CurrentCharacter varchar(1)
DECLARE @ValidCharactersLength int
DECLARE @ValidCharacters varchar(255)

SET @ValidCharacters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-=+&$'

SET @ValidCharactersLength = len(@ValidCharacters)
SET @CurrentCharacter = ''
SET @RandomNumber = 0
SET @RandomNumberInt = 0
SET @RandomLetters = ''

SET NOCOUNT ON

SET @counter = 1
WHILE @counter < (@Length + 1)
BEGIN
        SET @RandomNumber = Rand()
        SET @RandomNumberInt = Convert(tinyint, ((@ValidCharactersLength - 1) * @RandomNumber + 1))
        SELECT @CurrentCharacter = SUBSTRING(@ValidCharacters, @RandomNumberInt, 1)
        SET @counter = @counter + 1
        SET @RandomLetters = @RandomLetters + @CurrentCharacter
END

And because we're going to populate this table with more than the one record:

DECLARE @randomLetters varchar(32)
DECLARE @randomLettersCount int

SELECT @randomLettersCount = 0

WHILE (@randomLettersCount < 1000)
BEGIN
        EXEC sp_GenerateRandomLetters 12, @randomLetters OUT
        INSERT INTO RandomLetters (Letter)
        SELECT    @randomLetters
        SELECT @randomLettersCount = @randomLettersCount + 1
END

None of this is even nearly shattering. It's not meant to be. Also, the following ought to error the first time it's run.

DROP TABLE ##OriginalRandomLetters

Now let's make that table which gets dropped by the statement above.

CREATE TABLE ##OriginalRandomLetters
    (
         ID int NOT NULL
        ,Letter varchar(32) NOT NULL
    )

And we sync this global temporary table with those values in the permanent table created above

INSERT INTO ##OriginalRandomLetters
    SELECT ID, Letter
    FROM RandomLetters

Confirm that we are good.

SELECT * FROM ##OriginalRandomLetters

And back on that other tab and therefore using another connection...

BEGIN TRANSACTION

    DECLARE @RandomUpdateCount int
    DECLARE @RandomID int
    DECLARE    @randomLetters varchar(32)

    SELECT @RandomUpdateCount = 0

    SET NOCOUNT ON

    WHILE @RandomUpdateCount < 20000
    BEGIN
        SELECT @RandomID = 1 + RAND() * 999
        -- SELECT @RandomID '@RandomID'

        EXEC sp_GeneratePassword 12, @randomLetters OUT
        -- SELECT @randomLetters '@randomLetters'

        UPDATE    RandomLetters
        SET        Letter = @randomLetters
        WHERE    ID = @RandomID

        SELECT @RandomUpdateCount = @RandomUpdateCount + 1
    END

ROLLBACK TRANSACTION

And finally let's try one of these transaction isolation levels

    SET TRANSACTION ISOLATION LEVEL READ UNCOMMITTED
    SET TRANSACTION ISOLATION LEVEL READ COMMITTED
    SET TRANSACTION ISOLATION LEVEL REPEATABLE READ
    SET TRANSACTION ISOLATION LEVEL SNAPSHOT
    SET TRANSACTION ISOLATION LEVEL SERIALIZABLE

And the result of the following query will depend on the chosen isolation level.

SELECT * FROM RandomLetters

For example the READ UNCOMMITTED isolation level will allow you to see the changes being made to the values in the RandomLetters table whilst the transaction to update values is being run whereas most of the other isolation levels will cause SELECT * FROM RandomLetters to hang until the transaction is complete. In the case of SNAPSHOT there's an error: Snapshot isolation transaction failed accessing database 'WimiroDemo' because snapshot isolation is not allowed in this database. Use ALTER DATABASE to allow snapshot isolation.

I might be forgiven for not remembering all this behaviour during interview but not having a handle immediately on the correct strategy for ASP.NET paging and the 10 steps of the ASP.NET Page Life Cycle might have been forgetfulness too far. But that's what the internet is for, I say. Fingers crossed I get the gig anyway.

Tags:

SQL Server

AJAX and the URL short(ening)

by Kofi Sarfo 16. June 2009 23:42

A popular choice for shorterning URLs on Twitter is Bit.ly. It's just so nice and tidy with great analytics. For example, not long after shortening http://cnn.com/ we discovered that there have already been 2,659 clicks to that URL via Bit.ly.

I am using the C# API from @kersney by the way and found out that Bit.ly does do the sensible thing and return the same shortened URL each time you supply an unadulterated URL. What I've not yet done is built chains of shortened URLs that lead to each... seemingly endless possibilities! What the C# API code is missing is &history=1 querystring parameter to have the shortened URL added to the list displayed in Bit.ly History.

Some Default.aspx code to give this a go:


<body>
<form id="form1" runat="server">
<div style="width: 100%;">
Original URL:
<asp:TextBox ID="TextBox1" runat="server" Width="100%"></asp:TextBox>
<div style="text-align: right; width: 100%">
<asp:Button ID="Button1" runat="server" Text="Shorten" onclick="Button1_Click" />
</div>
</div>
<asp:TextBox ID="TextBox2" runat="server"></asp:TextBox>
</form>
</body>

And some codebehind:

protected void Button1_Click(object sender, EventArgs e) { TextBox2.Text = API.Bit("bitlyapidemo", "R_0da49e0a9118ff35f52f629d2d71bf07", TextBox1.Text, "Shorten"); }

Now we pretend that bit.ly takes ages to return a shortened URL so we use javascript instead.


<script src="http://bit.ly/javascript-api.js
?version=latest
&login=bitlyapidemo
&apiKey=R_0da49e0a9118ff35f52f629d2d71bf07"

type="text/javascript">
</script>

<script type="text/javascript">

BitlyClient.addPageLoadEvent(function()
{
BitlyCB.shortenResponse = function(data)
{
var s = '';

var first_result;
// Results are keyed by longUrl, so we need to grab the first one.
for (var r in data.results) {
first_result = data.results[r]; break;
}
for (var key in first_result) {
s += key + ":" + first_result[key].toString() + "\n";
}

document.getElementById("bitlyUrl").value = first_result['shortUrl'];
}
});

function getBitlyUrl()
{
BitlyClient.shorten(document.getElementById("rawUrl").value, 'BitlyCB.shortenResponse');
}
</script>

No prizes for guessing the elements in the document.


<body>
<form id="formeula1" runat="server">
<div style="width: 100%;">
<br />Original URL:
<br /><input type="text" id="rawUrl" size="100" value="http://wimiro.com" />
<input value="Shorten" type="button" onclick="getBitlyUrl()"/>
<br />
<br />Bit.ly URL:
<br /><input type="text" id="bitlyUrl" size="20" />
</div>
</form>
</body>

So, there are no postbacks anymore but does this make it AJAX? Honestly, I have no idea. I see mention of callback_method_name in the bit.ly javascript api so my guess is that, yes, this is asynchronous. But shall we bother to test this or do we try and involve jQuery?

I wonder whether I can piggy-back Twitter authentication

by Kofi Sarfo 15. June 2009 00:46

Didn't really fancy maintaining credentials for an application that is designed to work in tandem with Twitter so enter OAuth.net: "An open protocol to allow secure API authorization in a simple and standard method..."

What is this new thing then and why had I not heard of it before? See October 2007 entry in Hueniverse: Beginner’s Guide to OAuth. Not so new then.

Also, a little while ago we were in a room with developers and they brayed when asked if anyone liked the ASP.NET 2.0 Membership Controls. I think the Login control was mentioned specifically. They worked fine for me. So we go looking for reasons this - their seeming unpopularity - might be. Stack Overflow (because there's been no reference in minutes) answers one question of what to use for membership in ASP.NET. We're still none the wiser.

And there's more from the timely discoveries department. Tweetsharp: "A C# fluent interface for Twitter, designed for app developers" -- downloading source. I remember being corrected for returning this (or it could have been me) circa 2004 which we did so that we could chain methods but I can't remember what the argument against it might have been.

Listening to folks talk REST whilst running 10km

by Kofi Sarfo 12. June 2009 02:24

Caught .NET Rocks show #445 with Kenn Scribner on REST. A useful discussion about REST, SOAP, the evolution of 'web services' technology and where WCF best fits in. Listen here.

Notes:

.NET Rocks talk transcript

Nuff chat. Now code.

by Kofi Sarfo 10. June 2009 01:33

We've spent the last few weeks reading, trying to get up to speed with .NET 3.5 and looking at some code. Meanwhile we've not been writing anything besides snippets for learning generics, LINQ and WCF. No ASP.NET MVC. No WPF. No Silverlight. No worries. It's time to build something.

So the concept is reviews for the Twitterati. Reviews of 120 Characters or less. Tweeviews if you like. Key characteristics should be that it's simple, clean and intuitive.

Key technical features:

  • REST-based architecture
    • API versioning
    • Caching
  • ASP.NET Webforms (initially with AJAX)
  • SQL Server 

Functional areas:

  • Category
  • Review
  • Thumb up or down (as opposed to 4/5 stars)
  • Reviewer
  • Reviewed object (restaurant, etc)

Not sure whether we call those things above entities.

Old school Microsoft approach is database design first. Data-centric rather than domain driven. I think we're still stuck in that world. Will be worth reconsidering this application and how it might have been done differently using NHibernate, Rhino Mocks, etc. Ayendeified. It ought to be an adjective.

What's interesting (for me) about this is that we've never written a publicly accessible API. We've done Web Services for both inter and intra application domain hookups (not in the .NET sense but rather as an interface between disparate applications on the same platform as well as between different platforms). We used Web Services, for example, in the Advert Framework* for FireText. No problems with SOAP. It didn't really need to be WS-* as it never made use of transactions as originally intended. Still, it was fun playing with the PHP SOAP implementation :)

Extra bits:

  • URL shortening API
  • Twitter API
  • Some reporting & filtering type UI

First pass, writing this as quickly as I can using tried/tested approach. Second attempt, a rewrite using shiny newish technology. The idea being then able to compare the old versus new, discern what real advantages the new offers and get some refactoring practice. This should be interesting...

Notes:

* It was subsequently rewritten in PHP because the engineer I handed the code to didn't fancy learning C# but a story for another time...

Full Circle on Action<T>

by Kofi Sarfo 6. June 2009 00:02

Reminded recently of a method for determining Prime Numbers (Sieve of Eratosthenes) and saw some Generic Collection Class action (p. 97 C# In Depth)

            List<int> candidates = new List<int>();

            for (int i = 2; i <= 100; i++)
            {
                candidates.Add(i);
            }
 
            for (int factor = 2; factor <= 10; factor++)
            {
                candidates.RemoveAll(delegate(int x)
                    { return x > factor && x % factor == 0; }
                );
            }
 
            candidates.ForEach(delegate(int prime)
                { Console.WriteLine(prime); }
            );

Bouncing around looking for code samples to see what we're missing in terms of Generics... we spot something. Switch on the Code: The Built-In Generic Delegate Declarations.

Difference between Func<T> and Action<T> is the latter doesn't have a return type. Too obvious to miss? Maybe. Quick search shows difference between new Action() and Lambda at Stack Overflow. Response from author of code sample above. Jon Skeet. 3900 answers on Stack Overflow in 8 months. Or 16 answers a day, every day.

Notes:

MSDN: Lambda Expressions

CodeBetter: Back to Basics - Delegates, Anonymous Methods and Lambda Expressions

Online Hang Outs Part I

by Kofi Sarfo 5. June 2009 16:56

 

I can't remember where I read something about having to read a decent amount of well written code in order to be able to understand how to code well. I think a parallel with writers and books was drawn somewhere nearby... Anyhow, this is why we've been hanging round the The Code Project since 2001 sometime and there appear excellent articles / code samples every so often; for example, the "Best C# article of April 2009" competition winner was Geoplaces. "A hybrid smart client, involving RESTful WCF/WPF and more." It's pretty.

 

It's a while since we wrote anything from scratch and those bits of code we've picked up in the last year don't look much like this. They don't look this good.

The Data Layer is all Entity Framework so happy to give that a miss but the Restful Service Layer is a nice intro into the System.ServiceModel namespace.

The Service Interface provides examples of ServiceContract and OperationContract. Backing up... MSDN: Introduction to Building Windows Communication Foundation Services. Note that this intro was written four years ago! Cut to mid 2009 and we still have indication of pain. Ayende: WCF Works in Mysterious Ways. IColloquialize: WCF Service References Generating Empty Root Proxy Classes. First takes suggest WCF might not be so straightforward.

Kofi Sarfo modified theme by Mads Kristensen



Content by WIMIRO Technology is licensed under a Creative Commons Attribution-Share Alike 2.0 UK: England & Wales License.

Creative Commons License

Powered by BlogEngine.NET 1.5.0.7

About Me

Director, Wimiro Technology
London, United Kingdom

Writes in third person and first person plural; currently commutes to Moorgate.

Kiva Loans

  • Issa Sarr

    Issa Sarr

    Personal Purchases

    Requested loan: $200

    Amount raised: $75

    Dakar, Senegal

    social needs

    Loan Now »

  • Edwin

    Edwin

    Movie Tapes & DVDs

    Requested loan: $800

    Amount raised: $125

    La Paz, Bolivia

    Buy a DVD burner tower

    Loan Now »

  • Soo

    Soo

    Laundry

    Requested loan: $5375

    Amount raised: $2175

    Queens, New York, United States

    To purchase a new dry cleaning machine

    Loan Now »

 To see more entrepreneurs »

Kiva Loans