Honest Illusion

Dev102's Challenge #13 : Brackets

2008-07-21T17:18:03Z

Many people skipped last week's challenge (like I had planned to). As it turned out, I was the only blogger to responded.

For this week's challenge, they've gone back to a platform-neutral algorithm question:

Your input is a string which is composed from bracket characters. The allowed characters are:’(', ‘)’, ‘['. ']‘, ‘{’, ‘}’, ‘<’ and ‘>’. Your mission is to determine whether the brackets structure is legal or not.

The simple sentence answer is "use a stack, pushing on an open character, and popping on a close character". There are a few other things to look out for, but that's the basic concept. For the actual code, I bypassed any kind of library Stack class, since we wanted the most efficient and for the very limited need of this function, I could jury-rig a faster one out of a char array. Complexity is speed: O(N), space O(N)

static bool TestBrackets(string testcase)
{
    // create a very simple stack.  
    // Since we push on open & pop an close, stack need only be half the
    // size of the input string.  The +1 is needed because we only check
    // for too many opens after we've pushed.
    char[] stack = new char[(testcase.Length / 2) +1];
    
    int SP=0;
    foreach(char chr in testcase)
    {
        switch(chr)
        {
            // For each open character, push the close char.
            case '[':
                stack[SP++] = ']';
                break;
            case '<':
                stack[SP++] = '>';
                break;
            case '{':
                stack[SP++] = '}';
                break;
            case '(':
                stack[SP++] = ')';
                break;
                
            case ']':
            case '>':
            case '}':
            case ')':
                // check for stack underflow (too many closes)
                // or a character we weren't expecting (bad  nesting)
                if (SP==0 || stack[--SP] != chr)
                    return false;  
                break;
        }
        // Check for stack overflow (too many opens)
        if (SP==stack.Length)
            return false;
    }
    // Finally, it's good if we've closed everything we've opened.
    return SP==0;
}

Share this post: Email it! | bookmark it! | digg it! | reddit!

Dev102's Challenge #12 : Managed & unmanaged

2008-07-16T18:52:52Z

My solution(s) for last week's challenge were cited, but, only as an "honorable mention" / "also run".

This week's challenge is a different sort of animal. Not that it is particularly difficult --- actually I suspect it's quite easy --- it's just that it requires a fairly specialize knowledge (Managed Extensions for C++ in this case). A couple of them in the past required some basic knowledge of .Net & the CLR, but most of the time, the challenge involve a non-platform specific algorithm.

So, knowing nothing about Managed Extension, I was just going to let this one pass. But, I happened to run into an old friend (Will Depalo) from my days as a VC++ MVP. When I went to .Net, I also switched to C#, but he stayed with C++, so I figured he would have some insight. Reducing the problem to one sentence ("we have a unmanaged class accessing an instance variable of a managed class"), and he immediately knew the answer ("you'll need to pin it"), and offered some advice ("look up '__pin' in the msdn"). However, didn't realize exactly how good that advice was, as the folk's at DEV102 apparently took the example source code from the __pin article to create the challenge. So, here's my answer (I love stuff that can be answer via copy'n'paste):

int main() 
{
   ManagedClass __pin * pMngdClass = new ManagedClass;
   UnmanagedClass* pUnmngd = new UnmanagedClass;
   pUnmngd->incr(&(pMngdClass->i));
}

The rest is unchanged.

Share this post: Email it! | bookmark it! | digg it! | reddit!

Dev102's Challenge #11 - Summing Numbers

2008-07-08T13:55:37Z

My answer was acknowledged as correct for last week's challenge. So, let's see if we can make it two in a row. This week:

Given a list of n integers and another integer called m, determine (true / false) if there exist 2 numbers in that list which sum up to m.
Example: 2,6,4,9,1,12,7 and m=14 -> 2 and 12 sum up to 14, so the answer is true.

This one is rather tricky. There is no obvious (to me) solution. I can see three viable methods, each with its own pros & cons.

Method 1: We'll call this "brute force". The obvious answer. We add the values of list[1] and list[2], then list[1] and list[3], then list[1] and list[4] and so forth, until we reach list[1] and list[ n ]. If we haven't found a match yet, we then move on to adding list[2] to list[3], then list[2] to list[4] etc. In code that would be:

for(int i= 0; i <N-1; ++i) 
    for(int j= i+1; j < N; ++j) 
       if (list[ i ] + list[ j ] == M)

The complexity for this would be Summation N which is officially O(N*N) (although it's closer to O(N*N/2) ). However, that's the worst case: we can exit early as soon as we find a valid match, making the average case O(N*N/4). It's also important to note the basic operation that's being repeated (adding two number) is very fast. Hence, this would be the winner for small values of N (and probably some very large "small values of N").

Method 2: Which we'll call the "bi-directional search". This would clearly be the winner, except for it's precondition: start with a sorted list. Add the first and last elements of the list (list[1] + list[ N ]). If they equal to goal, we're done. If they are more than the goal, add the first and second-to-last elements(list[1] + list[ N-1 ]). If they are less, then add the second element to the last element (list[2] + list[ N ]). Continue this way, moving up from the front when the sum is too low, and down from the back when it's too high until you either find a match, or meet in the middle. The complexity of this algorithm in O(N) --- for a sorted list. We're given an unsorted list, which means we'd have to sort it first. Sorting is, at best, O(N*logN), making the total complexity O(N*logN + N), which I believe is still less than method 1, but the basic task being done for the sort (comparing and swapping) is much more expensive than for method 1. Further, you must complete the sort before you can start the search, so you've taken the big hit before you get a chance for an early exit, making the average case O(NlogN+N/2), so this will win for large values of N, but they'd have to be very large values of N.

And, finally, Method 3, which we'll call the "partitioned search". Partition the list into two sublists, one with values less the M/2 and one with values greater than M/2. (The value equal to M/2 can be ignored, as we would need two of them, and we've been assured that the values in the list are unique). If a solution exists, it will require one from each list; any combination of two from the lower sublist will be two low. Any two from the upper list will be too high. So we just try every combination of one from each sublist. In the worst case, that's O((N/2) * (N/2)) or O(N*N/4), with an average case of O(N*N/8). To explain with examples: Say we are given a list of 10 numbers. Method 1 would require 55 additions to try every possibility. If we partitions the list into sublists of 5 & 5, then this method would require only 25 additions. However, if the numbers break down so that the partitions are 8 & 2, then we'd need only 16 additions. And, as before, we can exit early as soon as we find a match. Partitioning can be done in O(N): Start by pointing at the first and last elements, just as in Method 2. Seek forward looking for an element greater than N/2. When one is found, seek from the end, looking for an element less then N/2. When you have one of each, swap 'em and continue. When the pointers meet, the list is partitioned in place. That required only one pass through the list, so the step is O(N), making the total for the average case O(N*N/8 + N).

Overall, Method 1 wins for small lists, Method 3 for larger lists, and Method 2 for very large lists. Since memory read/write efficiency is the last bottleneck (how many additions is one swap worth?) the exact point where one method passes another is heavily platform dependant.

In the back of my mind, two other ideas for other methods keep flowing through. The first tells me that there should be some way to accomplish this through summing the list. This would be O(N), but I just can't think of a way to make it work. The other involves building a matrix. I'm pretty sure I could make that work, in a way that O(N) once the matrix is built, but building it would be greater the O(N) itself, so the whole task would be no faster than the means described above.

Share this post: Email it! | bookmark it! | digg it! | reddit!

Dev102's Challenge #10 - The Missing Number

2008-07-01T18:50:34Z

I didn't actually skip last week's challenge for Dev102. I did write up a solution. I just forgot to post it. It was wrong anyway.

Well, no sense it looking backward... This week's:

Your input is an unsorted list of n numbers ranging from 1 to n+1, all of the numbers are unique, meaning that a number can’t appear twice in that list. ..One of the numbers is missing and you are asked to provide the most efficient method to find that missing number.

And Shahar was right, it was rather easy. We just add up the number we get, and subtract that value from the sum we should have gotten if the missing number wasn't missing.

int FindMissingNumber(IEnumerable<int> list)
{
    int actualSum = 0;
    int expectedSum = 0;
    int n = 1;
    foreach(int i in list)
    {
        actualSum += i;
        expectedSum += n++;
    }
    expectedSum += n;
    return expectedSum - actualSum;
}

Things to note:

The complexity of the algorithm in O(n).
I assured that complexity by using the least powerful collection interface (IEnumerable), and iterated through it only once.
I summed the expected total manually instead of an formula on list.Count, but for some collection types (such as a linked lists) Count is, by itself, O(n).
The method will work for an empty sequence, returning 1.

Share this post: Email it! | bookmark it! | digg it! | reddit!

DEV102's Programming Job Interview Challenge #8

2008-06-18T19:23:13Z

I skipped last week's DEV102 challenge. I didn't think my answer was right. Turns out that it was. I was assuming that it had a limitation that would disqualify it. I assumed that my solution would only work if you placed the coins in a tight grid with each newly-placed coin touching an existing coin. As a practical matter, this is true. It would be virtually impossible to properly place a coin mirroring the freely-placed previous coin without resorting to a tape measure and protractor. And the placement would have to be exact for it to work. So I suppressed my solution for lack of practicality, when all they really wanted was a theoretic solution.

Anyway, onward to this week's challenge, #8 (excerpted):

You are writing a software component that receives a binary record every 20 millisecond. .... Your component goal is to alert whenever it identifies a specific expression (which is provided at the initialization process) in the stream of records - you are looking for a specific combination of binary records.

The answer is, of course, a Finite State Machine. To explain how one works, we need to come up with a example expression to search for. Let's say these records come it four formats: Type A, type B, type C and Type D, and we are looking a sequence of records in the following pattern: ABACB (if you'd like, you can assume that there are many record types, and Type D represents "any record that's not type A, B or C"). So, we start in state "0". State 0 can be called "looking for first A record". At state 0, if we find an A record, we move into state 1 ("Find first A, looking for first B"). If we find any other kind of record, we stay in state 0. This can be expressed in table form as:

	Next state	when	record	found
Current State VV	A	B	C	D
0	1	0	0	0

Next when we are in state 1, if we find a B record, we move into state 2, but the other transitions are a bit trickier. If we find a C or D, we're back to state 0 ("looking for 1st A"), but if we find another A, we have to stay in state 1. Adding that to our graph:

	Next state	when	record	found
Current State VV	A	B	C	D
0	1	0	0	0
1	1	2	0	0

Ok, now, we are in state 2 ("found AB, looking for 2nd A"), Here if we find an A, we move on to state 3 --- anything else, and we're back to state 0.

	Next state	when	record	found
Current State VV	A	B	C	D
0	1	0	0	0
1	1	2	0	0
2	3	0	0	0

State 3 ("found ABA, looking for C"), is a bit trickier again. If we find a C, naturally, we move into state 4. And if we find a D, were back into state 0. But, if we an A, we step back to state 1. And if we find a B, we step back only to state 2 (ie, we've found "ABAB" and the second "AB" may be the start of the pattern we want.

	Next state	when	record	found
Current State VV	A	B	C	D
0	1	0	0	0
1	1	2	0	0
2	3	0	0	0
3	1	2	4	0

At state 4, we enter the endgame. We're trying to find "ABACB", and so far we're found "ABAC". If the next record is a B, we have success ("Let loose the pigeons!"). If it's an A, we go to state 1 (as usually). Anything else, and we start over at state 0.

	Next state	when	record	found
Current State VV	A	B	C	D
0	1	0	0	0
1	1	2	0	0
2	3	0	0	0
3	1	2	4	0
4	1	*	0	0

Now, to put this into C# code, we merely need a simple pre-initialize int array following the structure of the chart we just built, and start with our state at 0.

const int[,] states = new int [5,4]{

{ 1,0,0,0},

{1,2,0,0}

{3,0,0,0}

{1,2,4,0}

{1,-1,0,0}

};

int state = 0;

Then as a new record comes in, we just determine it's type, and update the state:

bool MatchFound(Record newRecord)
{

// return 0,1,2 or 3 for record type A,B,C or D respectively.
// can be assumed to be present, as per the spec.
int type = GetRecordType(newRecord);

// Here's where the magic happens
// just a simple index into an array.
state = states[state, type];

return state < 0; // Report success or failure.

}

And that's it. Total state held between records: one integer. Total work needed per record to determine pattern: one array lookup and one int comparison.

And the real beauty of this approach is that if we wanted to look for other patterns at the same time, it could be done. For example, by just changing the states[] array in the above to this

const int[,] states = new int [13,4]{

{1,5,9,0},
{1,2,9,0},
{3,6,9,0},
{1,2,4,0},
{10,-1,9,0},
{1, 6, 9, 0},
{1, 6, 7, 0},
{10, 5, 8, 0},
{-2, 5, 9, 0},
{10,5, 9, 0},
{1, 11, 9, 0},
{3, 6, 12, 0},
{-3, 6, 9, 0}

};

Then we'd be able to search for ABACB (as before, found when state = -1) and BBCCA (found when state = -2), plus one more pattern (found when state = -3).

Class Homework

1) (simple) Try to figure out the third pattern that can be found using that state table. (It's a sequence of 5 records using just A B & C)

2) (hopefully not possible) Try to figure out a sequence of records that would cause the state machine to miss one of those patterns (Note: after one is found, we start over at state 0, so it's not intended to find overlapping sequences, such as "ABACBBCCA". It's find the first but not the second.)

Share this post: Email it! | bookmark it! | digg it! | reddit!

DEV102's Programming Job Interview Challenge #6

2008-06-02T14:16:00Z

Another week, another C# interview question from the good folk's at Dev102.com -- Although I use the term "good folks" advisedly, as this week they did not even acknowledge the solution I posted for last weeks puzzle (which was both correct, and, I believe, the first blog post about it).

Anyway, time to move on to this week's question.

Look at the following Code segment written in C#:

   1: ArrayList a = new ArrayList();

   2: ArrayList b = new ArrayList();

3:

   4: a.Add(1);

   5: b.Add(1);

   6: a.Add(2);

   7: b.Add(2.0);

8:

   9: Console.WriteLine((a[0] == b[0]));

  10: Console.WriteLine((a[1] == b[1]));

What will be typed into the console? And WHY?

This one is fairly trivial (They seem to be alternating between difficult and easy questions). And, as requested, I formulated my answer before typing it into VS (actually, I copy'n'pasted in SnippetCompiler), but the compiler DID confirm the answer I'd already theorized.

This answer is short enough that we can use the cool "white-on-white; select to see it" trick--- However, RSS feed (and apparently the theme of this blog) seem to ignore the color style, so it's probably visible to you below..

ArrayList is deep-down, just an object[]. To store an valuetype, like an int or float, in an ArrayList, that value would first have to be boxed. Each valuetype is boxed separately, in distinct objects, even if they do happen to have the same value. When we get to the WriteLines, we are just performing (object) == (object) (actually, Object.ReferenceEquals(object1, object2); ) ReferenceEquals knows nothing about unboxing. It just asks, "Are these two references pointing to the exact same object?". For any two boxed objects, regardless of their value, the answer would be "No". Hence, both lines print "False".

(select the blank space above)

Share this post: Email it! | bookmark it! | digg it! | reddit!

DEV102's Programming Job Interview Challenge #5

2008-05-26T12:57:20Z

DEV102 announced the correct responses to last weeks challenge today. Since I announced in my blog I got a prominent spot in their post, which is good considering I was one of about 10,000 correct answers and I gave it rather late in the process. Hopefully, I can improve on both those areas this week.

Two other things they messages showed. 1) It apparently takes a lot of hunting on this blog to figure out my name (James Curran), and 2) They like it if you hide the solution with HTML tricks. Unfortunately, while last week's answer was three simple lines of code, this week's so going to be too long to do that effectively.

Anyway, on to this week's puzzle:

You are asked to sort a collection of records. The records are stored in a file on the disk, and the size of the file is much bigger than available memory you can work with. Assume a record size is 10 bytes and file size is 1GB. you read and write data to/from disk in units of pages where each page is 1KB big. You have few (less than 10) available pages of physical memory. Assume you are given a method to compare two records.

How can you sort the records under the described conditions?

The trick here is to do lots of merge sorts, but we get to that in a minute. But first to prepare, we have to sort each page, hence, read one page, and sort it's records in memory. Exactly how it's sorted is irrelevant. A page only has 100 10-byte records so Quicksort is probably overkill -- an Insertion sort is probably best. Then that page is written back to the file in place, and we more to the next one.

When we finish sorting each page individually, then we begin the Mergesort. Read two pages and merge them by comparing the first items in each list. Once the new list fills a page, it's written to a new file. Repeat this, and eventually, you have half as many segments, each two pages long. Then, do it all over again, merging two-page segments into four page segment. The trick is, since the two-page segments are already sorted, they can be read in one page at a time, and the output can be written to disk as soon as a page is filled.

Keep repeating the process, merge four-page segment into eight-page segments, 8-pages into 16-page, etc. Eventually you will be merging two 512-page segments, and you're done.

The process own requires three pages of physical memory, and we have a bit more, so some optimizing can be done, but that's essentially it.

Share this post: Email it! | bookmark it! | digg it! | reddit!

DEV102's Programming Job Interview Challenge #4

2008-05-23T13:58:31Z

The folks at Dev102.com are offering weekly programming challenges, where they offer questions, and let bloggers post about them. I meant to write an answer for last week, but never got around to it. Just as well -- my answer would have been wrong. SO, let's move on to this week's:

How would you implement the following method: Foo(7) == 17 and Foo(17) == 7. Any other input to that method is not defined so you can return anything you want. Just follow those rules:

Conditional statements (if, switch, …) are not allowed.

Usage of containers (hash tables, arrays, …) are not allowed.

My first thought was, since we can't use conditional statements, to use conditional expressions instead:

int foo(int n)
{
return (n==7) ? 17 : (n==17) ? 7 : n;
}

But clearly, that is just cheating. (And, besides, it turns out, it's not the best solution).

My next attempt was to use subtraction to create factors of zero.

int foo(int n)
{
return n + (10 * (n-17) * (n-6)) + (-10 * (n-16) * (n-7)) ;
}

There may be a formula in there that works, but that one doesn't, and before I found it, I stumble upon the correct solution, which was just sitting there staring me in the face:

int foo(int n)
{
return 24-n;
}

Yep, it's just that simple.

Share this post: Email it! | bookmark it! | digg it! | reddit!

The Need for Common Search Keywords.

2008-04-19T00:01:10Z

if you ever tried to Google something like "how to write a linked list in C#" you may have noticed a problem. Most search engines have trouble dealing with the pound sign (hash/number sign/octothorpe). You run into the same problem search for information on ".Net" or "COM" or, for that matter, "Word" or "Access".

I hit upon a similar problem a few years ago. I was trying to set up Microsoft Money to access my bank accounts online. I went to my banks' websites, but had trouble finding the setup instructions. Searching a bank's website for "Money" provides many false hits. Searching for "Microsoft" isn't much better, when every page's footer contains "Best view on Microsoft Internet Explorer 2.0 or later". Finally, I hit upon the trick: I searched the site for "Quicken". The instruction for Microsoft Money were always on the same page as the instruction for Quicken.

This lead to to the idea to solve the problem I mentioned up top. Basically, for very technology or product with an inconvenient name, we need a standard searchable keyword, so that whenever someone writes a blog post about a C# topic, if he includes the "csharp" keyword, then someone searching on "csharp" will be able to find it. Of course, there's two problems with this: first we have to get bloggers to use the keywords and then we have to make sure the seekers know enough to use them.

Last night I was at a .Net (dotnet) users' group meeting where some folks from MSDN (the website) were soliciting suggestions on improvements. I presented this suggestion to them, and they were receptive to it, but it really isn't MSDN targeted at them. The real solution would be to be a list of officially sanctioned keywords coming direct from Microsoft and promoted by them (so that banks know to put "msmoney" on a page that described the setup for Microsoft Money.

But in the mean time, I figured I could leverage some of the blogosphere to help push this idea along.

So, let's start defining the ground rules.

A keyword needs to be a single term ("csharp", not "c sharp")
A keyword needs to uniquely (or very close to it) indicate the subject ("msword", not "word") (If your spell-checker says it's misspelled, that's a good sign)
A keyword should be a string that is decipherable when written as one word in all lowercase. (so we don't run into the problem of "expertsexchange")
Unfortunately, there are probably trademark issues to deal with (Microsoft will probably want it to be "microsoftword" instead of "msword")

So, to start us off, here are a few I thought up. Be sure to include them in any blog post (in the body or tags or header) on the subject.

"C#" = "csharp"
"C++" = "cplusplus"
".Net" = "dotnet"
"ASP.NET" = "aspnet" (or should we go for "aspdotnet"?)
"ASP.NET Ajax" = "aspnetajax"
"LINQ" = "linq" (that was easy -- maybe Microsoft is learning).

Share this post: Email it! | bookmark it! | digg it! | reddit!

How can I easily log a message to a file for debugging purposes?

2008-04-16T14:06:47Z

Today, either Bloglines.com or blogs.MSDN.com blinked, and suddenly I'm seeing old entries on the 'C# Frequently Asked Questions' blog as new. No one has posted anything there in over two years.

Anyway, reading the most recent message, it offered a method for logging a message. Now, ignoring side debates over log4net vs nLog vs. the Event log vs. Trace, and just concentrating on the code post --- It's not very good. Look for yourself (then come back here) http://blogs.msdn.com/csharpfaq/archive/2006/03/27/562555.aspx

Despite being written by a C# MVP (*), it shows a lack of understanding of basic .Net library features, and well as C#. So, I figured, I'd rewrite it. I limited myself to taking what's there and fixing it instead of going an entirely different way (ie, log4net vs nLog vs etc). Here's the revised code:

using System.IO;

public void LogMessageToFile(string msg)

    string logFilepath = Path.Combine(Environment.GetEnvironmentVariable("TEMP"),"My Log File.txt");

    using (StreamWriter sw = File.AppendText(logFilepath))

        string logLine = String.Format("{0:G}: {1}.", DateTime.Now, msg);

        sw.WriteLine(logLine);

A few years ago, I bought a number of books, all with the title of same variation of "C# Cookbook". Again, a lot of bad code. I've been meaning to start a series of articles about revising them.....

(*) Years ago, I was one of the very first C++ MVPs. After ten years, I was dropped from the program. Since then I've tried to become a C# MVP, without any luck. I'm beginning to get bitter about it. ;-)

Share this post: Email it! | bookmark it! | digg it! | reddit!

Predictions

2008-03-26T03:16:00Z

My friend Chris is, like me, a staunch Democratic. Unlike me, he's also an incredible pessimist. In 2006, he made what he called his "optimistic" prediction for the midterm election: The democrats would gain 3 Senate seat, 10 house seats, and 3 governorships. (Actual results: Democrats gained 6 Senate seats, 30 House seats, and 6 Governors). I didn't make any predictions then.

Since another election is looming, he's made is his predictions for the elections, and in the interest of balance, I've made mine. And, since I'm probably going to lose the napkin I wrote them down on before November, I figured I'd record them here, so I know where I can find them, after the election.

So, here goes:

Chris's Predictions

Republicans will gain 8 house seats, 2 governorship while the Senate will stay the same. McCain will become president, winning 36 states.

James's Predictions:

Democrats will gain 10 House seats, 4 Senate seats, and 2 governorships. The democrat will win the White House, winning 20 (mostly large) states.

Neither of us ventured a prediction on who will be the Democratic candidate. Chris wants Obama, because he things he has the best chance of winning. I want Clinton, because I think she'll be the best president.

Share this post: Email it! | bookmark it! | digg it! | reddit!

Joins - LINQ's critical, overlooked feature.

2007-12-19T01:35:00Z

As i was planning my rewrite of NJTheater.com I looked at a couple different Object-Relationship Mappers (mostly code generators which examined a database schema and produced one class per table to read and write rows to it. All seemed particularly lacking because of this. Then I find LINQ, and realized that I had found exact the system I was looking for.

To understand the problem, consider the main page of NJTheater.com, which on your average day looks something like this:

The Blue Bird (11/27/2007 - 12/31/2007)
by Shakespeare Theatre of New Jersey (at F.M. Kirby Theater in Madison)

Doubt (11/27/2007 - 12/23/2007)
by George Street Playhouse (at George Street Playhouse in New Brunswick)

Seussical: The Musical (12/1/2007 - 12/23/2007)
by Bergen County Players (at Little Firehouse Theatre in Oradell)

The database is heavily normalized, so to retrieve that data, I need an SQL query that looks like this:

Select pl.Title, p.StartDate, p.EndDate, t.Name, v.Name, v.City
From Productions P
inner join Troupes T on p.TroupeID = t.TroupeID
inner join Venues V on p.VenueID = v.VenueID
inner join Plays pl on p.PlayID = pl.PlayID
where p. FirstDate >= GetDate() and p.FirstDate <= GetDate() + 7

p>The actual query is a bit more complicated, but we'll go with that for now.

That's one SQL statement which returns 3 to 30 rows (depending on the week) which holds all the data to be displayed.

Which brings us to the problem. Most ORM systems would have me translate that into something like

ProductionList productions = db.Productions.WhereBetween("StartDate", datetime.Now, DateTime.Now.AddDay(7));

And then use it like this:

foreach (Production prod in productions)
Print prod.Play.Title +" ( " +prod.StartDate + " - " + prod.EndDate + ")"
Print "by " + prod.Troupe.Name " (at " + prod.Venue.Name + " in "+ prod.Venue.City +")"

(I made that syntax up, but it's fairly typical.)

Which brings us to the problem. The first line would generate one SQL query which would look something like this:

Select p.*
From Productions P
where p. FirstDate >= GetDate() and p.FirstDate <= GetDate() + 7

and would return about 15 records. However, when it goes into the loop to render the actual page, then we sudden have a lot more SQL queries:

Select title from play where playid = 123;
select name from troupe where troupeid=131;
select name, city from venue where venueid=102;

Select title from play where playid = 143;
select name from troupe where troupeid=134;
select name, city from venue where venueid=202;

etc etc. We go from one query returning N rows, to 3N+1 queries. We've just massively increased the amount of work needed to be done to render the front (and most popular)page on the web site.

Which brings us back to LINQ. The LINQ query I use is:

var productions = from prod in db.Productions
        where prod.StartDate < DateTime.Now.AddDays(7)
        && prod.StartDate > DateTime.Now
        orderby prod.Play.Title
        select new
               {
                   Title = prod.Play.Title,
                   Troupe = prod.Troupe.Name,
                   Venue = prod.Venue.Name,
                   City = prod.Venue.City,
                   StartDate = prod.StartDate ,
                   EndDate = prod.EndDate

};

foreach (Production prod in productions)
Print prod.Title +" ( " +prod.StartDate + " - " + prod.EndDate + ")"
Print "by " + prod.Troupe " (at " + prod.Venue + " in "+ prod.City +")"

The first thing you should notice is that except for the verbose select clause, this syntax is rather close to the one for my theoretic ORM.

A more subtle difference is that I've slipped in a orderby based on one of the JOINs, which I'm not sure how I'd do in the ORM.

But the most important thing you should notice is that this will produce a single SQL statement, one that is virtual identical to the hand-crafted one I started this article with.

If you don't believe me, here's output from LINQPad:

SELECT [t].[Title], [t2].[ Name ] AS [Troupe], [t3].[ Name ] AS [Venue], [t3].[City],
[t0].[FirstPerformance] AS [StartDate], [t0].[LastPerformance] AS [EndDate]
FROM [Productions] AS [t0]
INNER JOIN [Plays] AS [t1] ON [t1].[PlayID] = [t0].[PlayID]
INNER JOIN [Troupes] AS [t2] ON [t2].[TroupeID] = [t0].[TroupeID]
LEFT OUTER JOIN [Venues] AS [t3] ON [t3].[VenueID] = [t0].[VenueID]
WHERE ([t0].[FirstPerformance] < @p0) AND ([t0].[LastPerformance] > @p1)
ORDER BY [t1].[Title]

-- @p0: Input DateTime (Size = 0; Prec = 0; Scale = 0) [12/25/2007 7:00:54 PM]
-- @p1: Input DateTime (Size = 0; Prec = 0; Scale = 0) [12/18/2007 7:00:54 PM]
-- Context: SqlProvider(Sql2005) Model: AttributedMetaModel Build: 3.5.21022.8

Share this post: Email it! | bookmark it! | digg it! | reddit!

My Second CodePlex Project : State Theater

2007-12-17T17:35:09Z

Well, as I promised months ago, I've created my second CodePlex project. Actually, I created months ago, while this site was down (as the artist I am, I think I'll refer to that as it's "black period"), But now that I'm back, I guess it's time to make a formal announcement.

The State Theater Project is my attempt to completely rewrite my main web site (www.njtheater.com). The original (still at that web address for now) was written by me, mostly 10 years ago, in classic ASP. The ASP pages are almost purely presentational -- they just read stuff from the database and display it on the screen, using a lot of questionable techniques (in some spots, I was formatting HTML in SQL select statements)

I added a few pages "recently" (i.e. within the last five years) in C#/ASP.NET. These were interactive, and mostly hidden from view of most users. Only registered users having certain roles saw them, and those pages allow those users to enter updates directly into the web site's database.

However, most of the theater companies just emailed the details of the shows, and hoped I found time to enter them. (Especially, since most of the important info can't be entered via the web pages, so only I could do it).

The main problem is that I needed a Ajax-based drop-down listbox, because the database is heavily normalized, so when someone entered "William Shakespeare", I needed to know they really meant Person ID#74.

Some years ago I paid good cash for one such control, which allowed me to get the few pages working that I did. But it was rather limited (I still don't think it works with Firefox) and has a spotty update & support history and in general wasn't letting me advance. When the Ajax craze start two years ago, a number of new, better and free DDL controls became available, so I started to look into a new approach.

Originally, I planned on a complete ASP.NET approach, and started to work on that in the spring of 2006. The first problem I had was my membership/roles data. Membership was based on the FORUM_MEMBER table from Snitz Forums, which I had been using for the Forums section of the site.

Now, Snitz is a fine forums packages, but it's also Classic ASP, but is getting kinda old -- it hasn't had a major update in year, and in fact, has had only two minor updates (most fixing security breaches) in the last 2 1/2 years. But mostly, the problem with it is that it's membership system was intended to be used strictly for the forums themselves, and any allowance for it to be used as a general web site membership subsystem were clearly an afterthought.

What I wanted to do was to use the ASP.NET membership system that came with v2.0. The trouble here was that Snitz stored passwords as a one-way hash. There is no way to convert them back into the original password. Which means that there's no way to more the account to the new database structure. I'd have to assign new passwords to my 2000+ users. That's wasn't workable.

Ah, but the ASP.NET membership system works on the provider model. The SqlMembershipProvider that comes with 2.0 is just one example. I could just write my own provider which used the existing table structure as a backing store. I began this project in the summer of 2006.

The next problem was my laptop. I was doing most of the work my lunch hour and one the train to & from work. But my laptop was excessively old. (It was three years old when I bought it on eBay, and that was three years earlier). It was taking much of the train trip just to awake from hibernation. I was just days away from buying a brand-spanking new laptop when I completely new problem arose -- I was laid off from my job.

Now, I bounced back from that fairly quickly --- but the time out of work chewed up the saving I was planning on using to buy the laptop--- but the new job gave me a laptop --- but the new job took away train ride to work (I had to drive there), and because I was consulting, I had to take short lunches.

Anyway, seven months later, that contract ended, and a new one began -- back on the train to NYC, and this time it was one long ride instead of two short ones, so I could get more done. After a few weeks of saving, I finally got that new laptop, and I could finally complete the SnitzMembershipProvider which became the first CodePlex project, only a year after I had started it.

And so then I finally began the work on revising the web site. But, by this time, I'd become fascinated with Castle Monorail and LINQ, and decided to try those for the web site. Plus, as much of the graphic design was mixed with the code, I tried for a more generic, skinnable approach of putting everything in <DIV>s and using CSS for styling it. Finally, I'm trying to make it generic enough so that some other group in a different state could take the code and create there own similar web site for their state -- with a completely different look, just by changing the CSS file.

For the Ajax work, and pretty much all the interactive forms, I'm using the Ext.Js library, except for large textboxes, for which I'm using TinyMCE.

You can see what I've done so far as www.NJTheater.org.

Share this post: Email it! | bookmark it! | digg it! | reddit!

Oh My God! It's back!

2007-12-04T20:40:09Z

Yes, after about 5 months of downtime, I finally was able to restore my blog.

What happened was, sometime mid-July, the PC that was running Sql Server on my network died. It was acting funny for a few weeks, so I took it off line. I removed the hard disk from it and attempted to install it on a different machine. It worked OK as a second drive, but I couldn't boot from it. At this point, I should have just left it as a second drive, but I didn't....

I tried re-installing Windows on that drive, and as I was doing this, the second PC failed. That PC was my Internet gateway, so it was imperative that I get that one back online. I shuffled disks around a bit, and got it working again.

Map of PCs:

pcA - Internet Gateway (old Compaq, circa 2001)

pcB - Sql Server 2000 (identical old Compaq)

pcC - Sql Server 2005 (more recent generic PC, circa 2004)

pcD - Web server (Micron PC, circa 2002)

pcE - Work machine (generic PC, circa 2006)

pcF - HomeServer Beta 2 (generic PC, circa 2007)

Now, pcB had been decommissioned, by was still was on the table with the others. pcC died, which is why the blog went down. I tried moving the disk to pcA, which then proceeded to die itself. I move the system disk from pcA to pcB to regain access to the Internet. (Complication -- they had different NIC cards). I then had to install the other apps that were running on pcC (notably my mail server). In midst of all this disk swapping, twice I forgot to power down the PC before pulled & reattaching a ribbon cable to a disk -- which killed the disks, one of which was the system disk to pcC.

So, all I needed to do now was to restore the back up of pcC from HomeServer onto a new hard disk. pcA seemed to recover and I bought a new HD at a computer show, so, mid-August, you would think I was good to go. No such luck. HomeServer refused to restore the disk. Which was crazy, as I had already restore that disk a few weeks earlier -- You'll recall that I said that pcC had been flaky for a while; one of those acts of flakiness was crashing it's hard disk.

One bought a new PC, which we'll call pcG (Woot.com had a close-out for $250). HomeServer refused to restore to that machine either. Finally, I had an idea: I put a disk back into pcC, and boot up HomeServer's restore disk on that. This time it would restore the disk. I then quickly copied the database files off it. (The website is now being run off SqlServer Express on pcD, which means beside reducing the number of mission-critical PCs from two to one, the setup is now finally LEGAL).

In the coming days, I plan on installing HomeServer RTM on pcF, and decommission my pcG (or at least salvage the most of the hard disks from it, for the new HomeServer). I'm not sure what pcG's eventual use will be, but I'm happy just to be back to square one.

Share this post: Email it! | bookmark it! | digg it! | reddit!

My First CodePlex Project : SnitzMember

2007-06-20T18:33:33Z

After many months to checking out the new projects on CodePlex almost daily, it's finally time for me to create one.

As you might know, I also run the website, NJTheater.com. Written about 10 years ago, all in classic ASP, it has a forum section -- which uses the open source Snitz Forum package.

Over the years, the membership has grown (over 3000 registered users), and I started to use the forum membership database, to manage authorization in other others of the website.

Now ASP.Net v2 came out, with it's built in Authentication/Authorization system, I thought "That's exactly what I need for my website" --- except it used a completely different db schema then the one I already had (and each hashed the passwords in different ways, so no conversion from one to the other was possible).

Fortunately, the membership system was built on using the Provider model, so I just had to create a Membership provider which fitted the interface, but used the existing membership database. SnitzMember is the provider.

Also, you may have noticed that I referred to this as my first CodePlex project. Well, you may have also noticed that I referred to NJTheater.com as 10 years old, and written in Classic ASP. Stay Tuned.

Share this post: Email it! | bookmark it! | digg it! | reddit!