A Simple Task? Generate Schedules

by John 17. March 2014 02:48

I was recently asked (or rather I volunteered) to build a website for a local sports league which included the ability to generate a schedule of matches, among the list of other to-be-expected functions (such as member management, player rankings, session results, etc).

I knew the scheduling aspect was going to be the most difficult; ensuring that all players play every other member just once and that no member was scheduled to play twice on a given night.  I fired up VS and started writing code.  I knew it was going to involve at least one nested loop that iterated the list of players, found an opponent and added them to the list of matches for that week - but it also had to check all other weeks to ensure these 2 players didn't play each other at some other time.  As the schedule grew in size the performance of the code disintegrated exponentially.  It worked wonderfully for my test data of 8 players, running in a second or 2, but when I put in the list of all the players (17) it grinded to a halt - running over a hundred-throusand iterations of all possible combinations.  I should note that my initial attempt included a random selection of 2 players.  Obviously, this was not going to work for a production website.

I did some research on scheduling and found some wiki articles on the set theory used to most often generate simple sports schedules.  With this new info in mind (and a few other tips picked up from the web) I came up with a solution that runs beautifully.  For 17 players, all playing a match per week, for 17 weeks, it generates a unique schedule in less than half a second.

It bugs me that I had to resort to searching for tips as the final solution appeared to be quite close to one of my iteration-attempts.  I simply ran out of time to get it working before the season was scheduled to begin.  I suppose one evening of coding/testing isn't always enough for "small" projects, heh.

The trick is to handle the first player/team individually for all of their matches, which effectively prevents that player from being in the pool for all the other generation.  Pair the 1st player with each iteration of the pool, then split the remaining list in half and walk through them.  Again, this is set operations (or modular systems or residue systems, depending on your particular brand of math/algebra schooling), so everything had to be mod-the-number-of-{something}.

What my own implementation was missing the special case handling of the first player and the rather ingenius splitting of the field as a starting point for the opponent's index search. Initially I was simply grabbing the next player in line, then grabbing the 3rd one after that (wrapping indexes, of course); checking logic and going forward.  It was something of a "brute force" method, to be sure, but it was quick to code and time is always a factor.  But because the number of players wasn't (or not guaranteed to be) prime, it meants that the value 2 could be found by more than one jump around the list; generating duplicates.  (A [odd] prime-based mod system means that every element in the set can generate every other element; whereas a non-prime system does not.)

My next attempt was to use LINQ to basically cross-join two arrays (as if you were building matrices) and while that did generate the pairings uniquely, assigning the rounds for each match was a bit more complex than I had anticipated; requiring a lot of logic checks and loops.  I didn't like that direction because surely there's a more elegant solution to this common task. So that's when I went to Google/Wikipedia. 

Anyway, I'm including the final code here so anyone else can find/use it:

public void GenerateSchedule()
{
     int numTeams = players.Count;
     int totalRounds = (numTeams - 1);
     int halfSize = numTeams / 2;
     List<Match> matches = new List<Match>();
     List<Player> teams = players.ToList();

     teams.RemoveAt(0);

     int teamsSize = teams.Count;

     for (int round = 0; round < totalRounds; round++)
     {
          int teamIdx = round % teamsSize;

          Match m = new Match();
          m.Round = round + 1;
          m.Player1ID = teams[teamIdx].PlayerID;
          m.Player2ID = players[0].PlayerID;
          matches.Add(m);

          for (int idx = 1; idx < halfSize; idx++)
          {
               int firstTeam = (round + idx) % teamsSize;
               int secondTeam = (round + teamsSize - idx) % teamsSize;
               //Console.WriteLine("{0} vs {1}", teams[firstTeam], teams[secondTeam]);
               m = new Match();
               m.Round = round + 1;
               m.Player1ID = teams[firstTeam].PlayerID;
               m.Player2ID = teams[secondTeam].PlayerID;
               matches.Add(m);
          }
      }

      GridView2.DataSource = matches.OrderBy(o => o.Round);
      GridView2.DataBind();
      lblCount.Text = matches.Count + " total matches.";
}

Tags: , ,

Programming | C#

Some thoughts on MVP

by John 14. January 2013 17:23

I've been pretty slack in updating this blog (as well as my others) lately; although I doubt anyone on the internet has noticed.  The last 7 months I've been working at place that's using the MVP design pattern.  It's, on the surface, a neat and interesting way to manage the UI layer.  In my old age, I see it as essentially breaking the UI into a 3-tier architecture.  The particular system I'm working on doesn't seem to use all the benefits this offers, other than completely separating the UI design from any sort of "load the data on the page" code.  However, that simplicity is replaced by a lot of client-side javascript to set hidden fields to tell the "middle UI" layer what to do.  Matters are complicated by the use of an older version of the Telerik control suite.

Still, it's definitely been something of a learning experience and I'm glad to get the exposure to it. 

When I was given my first assignment to build new sections into the existing app I quickly discovered the ins and outs of MVP. I discovered it required something like 15 new classes/files to adhere to all the object oriented implentation and inheritance structures. Sadly, nearly a 3rd of these classes are completely blank. Intefaces with only one line - inheriting from some other base interface. Or 2nd-level base classes that only implement an interface.  Now, granted, a lot of these classes are at lower levels in the system design that are used as data objects and other inter-level communication objects.  That being said, it's sometimes easy to separate the MVP bulk from the actual business and data layer bulk.

I'm curious to see other MVP systems and see how they actually put those various layers to use.  Perhaps in another place...

Tags:

Ajax | ASP.Net | Programming | VB | Design Patterns

More Jobs Please

by John 5. July 2012 08:41

Well, it tursn out that a risky job isn't always the best idea.  The wonderful client where I was placed and I have parted ways. *sigh*  Back to the drawing board.

Tags:

New Job!

by John 19. March 2012 08:52

I've been pretty busy lately, so I haven't had time to update this.  But, I got a new job. I started the first week of January at Redcard Systems, through Phase5 Consulting. This is a 6months-to-hire contract.  I freakin love this place.  The code is amazing, the people are awesome and the location is damn near superb.  I'll write more later.

Tags: , , , , ,

General | .Net | C#

Back to the drawing board

by John 14. December 2011 06:41

Well, as much as I would love to stay with my current company, sometimes things just don't always line up the way we hope.  Guess I'll be reading all those emails from recruiters and auto-listings from Dice and CareerBuilder now. *sigh*

Tags:

General

T-SQL Utility

by John 5. December 2011 06:18

Here's a handly little routine that will generate INSERT statements from the data in a supplied table.  I wrote this a long time ago and don't often need to use it these days, but when security restricts me from doing any sort of actual table export/import between servers yet that's what I need to do, this is extremely useful.

 

DECLARE @ColName varchar (100) 
DECLARE @colType varchar (100) 
DECLARE @Output varchar (8000)
DECLARE @TableName varchar(50)

SELECT @TableName = '{table_name_here}'

SELECT @ColName = '', @ColType = '', @Output = ''

DECLARE rs CURSOR FOR
	SELECT c.Name,	t.Name
	FROM
		sysobjects o 
		JOIN syscolumns c ON o.ID = c.ID 
		JOIN systypes t	ON c.xType = t.xType
	WHERE
		o.Name = @TableName 
	
OPEN rs 

FETCH NEXT FROM	rs INTO @ColName,@ColType 

--build the field listing...
IF  @@Fetch_Status = 0
SET	@outPut = 'SELECT ''INSERT INTO ' + @TableName + ' (' 

WHILE @@Fetch_Status = 0
BEGIN
SELECT @output = @output + char ( 10 ) + '	' + @colname + ', ' 
	
FETCH NEXT FROM	rs INTO @ColName, @ColType
END
CLOSE rs 

--remove the trailing ', '
SELECT @output = Left(@output, Len(@output) - 1) 

--now build the values list
OPEN rs 
FETCH NEXT FROM rs INTO @ColName, @ColType 

--build the field listing...

IF @@Fetch_Status = 0
SET	@outPut = @output + char(10) + ') VALUES (' 

WHILE @@Fetch_Status = 0
BEGIN
SELECT @output = @output + char ( 10 ) + '	' + 
	CASE
		WHEN  @ColType IN ( 'varchar' , 'char' , 'smalldatetime' , 'timestamp' , 'datetime' , 'nvarchar' , 'nchar' ) 
			THEN ''''''' + replace(ISNULL(' + @ColName + ',''''),'''','''''''') + '''''
		ELSE ''' + convert(varchar,ISNULL(' + @ColName + ',0)) + '
	END

SELECT @output = @output + ''', '
FETCH NEXT FROM rs INTO @ColName, @ColType
END

CLOSE rs 
DEALLOCATE rs 

--remove the trailing  ', '
SELECT @output = Left( @output,Len( @output) - 2)

SELECT @output = @output + ''')''' 
--now we've completed the complicated SELECT clause, just close up the FROM

SELECT @output = @output + Char(10) + 'FROM ' + @TableName

--SELECT @output 
EXEC(@output)

 

Tags: , , , ,

SQL Server

XML Serialization With Custom Namespace Attributes

by John 27. April 2011 05:16

So, after a bit research, I discovered that my brain wasn't working well.  It completely passed me by that the prefix for the attribute names was actually a namespace. With that, I was able to modifiy the property declaration and there's my namespace-prefixed attributes!

<System.Xml.Serialization.XmlAttributeAttribute([AttributeName]:="file", Namespace:="bb", Form:=System.Xml.Schema.XmlSchemaForm.Qualified)> _
Public Property file() As String
        Get
                Return Me.fileField
        End Get
        Set(ByVal value As String)
                Me.fileField = value
        End Set
End Property

Which produced the XML:

<resource xml:base="RSRC4" bb:file="RSRC4.dat" bb:title="New Item" identifier="RSRC4" type="bb-x-doc"  />

Tags: , ,

VB

Custom XML Serialization Question

by John 26. April 2011 05:50

Hello all. I have an object model, a series of classes and whatnot, that needs to be serialized into an XML document. I have all of this working just wonderfully, except for one thing. One of the classes, called Resource, has properties for Filename, Title, Base which need to serialized as attributes named "bb:file", "bb:title" and "xml:base" respectively. When I add to the property declaration, the serializer works just fine, but if I add a 2nd one to either of the other 2 properties, I get an error stating "There was a reflection error in the serializer." - on the line where I create the serializer object; but no further information is available. test code Here is the code of the class:

<System.CodeDom.Compiler.GeneratedCodeAttribute("xsd", "2.0.50727.3038"), _
System.SerializableAttribute(), _
System.Diagnostics.DebuggerStepThroughAttribute(), _
System.ComponentModel.DesignerCategoryAttribute("code"), _
System.Xml.Serialization.XmlTypeAttribute(AnonymousType:=True)> _
Partial Public Class Resource

Private fileField As String

Private titleField As String

Private identifierField As String

Private typeField As String

Private baseField As String

<System.Xml.Serialization.XmlAttributeAttribute([AttributeName]:="xml:base", Form:=System.Xml.Schema.XmlSchemaForm.Qualified)> _
Public Property base() As String
Get
Return Me.baseField
End Get
Set(ByVal value As String)
Me.baseField = value
End Set
End Property

'''<remarks/>
<System.Xml.Serialization.XmlAttributeAttribute(Form:=System.Xml.Schema.XmlSchemaForm.Qualified)> _
Public Property file() As String
Get
Return Me.fileField
End Get
Set(ByVal value As String)
Me.fileField = value
End Set
End Property

'''<remarks/>
<System.Xml.Serialization.XmlAttributeAttribute(Form:=System.Xml.Schema.XmlSchemaForm.Qualified)> _
Public Property title() As String
Get
Return Me.titleField
End Get
Set(ByVal value As String)
Me.titleField = value
End Set
End Property

'''<remarks/>
<System.Xml.Serialization.XmlAttributeAttribute()> _
Public Property identifier() As String
Get
Return Me.identifierField
End Get
Set(ByVal value As String)
Me.identifierField = value
End Set
End Property

'''<remarks/>
<System.Xml.Serialization.XmlAttributeAttribute()> _
Public Property type() As String
Get
Return Me.typeField
End Get
Set(ByVal value As String)
Me.typeField = value
End Set
End Property
End Class

And here is the code I use to create the serializer:

Dim xmlserializor As New Xml.Serialization.XmlSerializer(GetType(BBXSD.Manifest))

Using stream As New IO.FileStream(_outputFile, IO.FileMode.OpenOrCreate, IO.FileAccess.ReadWrite)
xmlserializor.Serialize(stream, objManifest)
stream.Close()
End Using

Manifest is the "parent" class that contains a property reference to an array of Resource class objects. (this is structured this because if I use a collection or list it doesn't get serialized properly).

Any thoughts anyone has would be most welcome.

Tags: , , ,

VB

Certification Bug

by John 23. February 2011 05:16

Everytime someone mentions certification, I get all amped up to get certified again.  I got my MCSD (Microsoft Solution Developer ... for Visual Studio 6.0) back in 1999, and while it didn't give me superpowers, it was certainly nice to have that little graphic on my resume.  That certification has long since expired, and with each new version of Visual Studio, I am constantly reminded of just how "out of date" I am.  

This morning, I was asked if I knew my MCP ID, and it reminded me that I have been meaning to look into certification again, now that my company has a training budget reimbursement program.  It's always a little more incentive to complete when someone else is picking up the tab.  Weird how that works. lol

Well, so I went out to the MCP site and started poking around the tests, requirements, etc and found the process is still very much the way it was 10 years ago; only now things are more expensive.  And, as usual, Microsoft doesn't even offer training materials for all of the tests. Specifically, the Windows Communication Foundation (70-513) MCTS test.  No e-books, no self-paced training kits, just a 3 day course that costs far too much and yields far too little information. Similarly, the final exam to get the MCPD certification, is the test: PRO: Designing and Developing Web Applications (70-519); which also has no training materials other than a FIVE day training course.

Now for the big dilema: Do I get the self-paced training books or the interaction practice tests?  In the past, I've used the books along with the practice tests with decent success.  The books are a nice precursor and the practice exams (at least the Transcender exams) provided a more "real life" test, and gave high detailed results, along with information relating to each and every question - if it's wrong, if it's right, why it's wrong or right.  I don't have a lot of spare time on my hands, so whichever I get will be a long and random process; it could take, perhaps even a year for me to get the certifications (I hope not, but I've known people who haven that long).  Also, books cost half of what the practice tests cost; although I expect (hope) the practice tests are more thorough and a better overall preparation.

Now, granted, I am looking at certification materials for VS 2010, not 2008, so it's a bit newer and it could take some time to get them released, but still, there's no mention of when the new testing materials might be released.

However, here's why I don't like looking into certification.  Here's a practice test question:

An ASP.NET page contains the following markup:
<asp:EntityDataSource ID="dataSource" runat="server" 
ConnectionString="name=EntityConnection" 
DefaultContainerName="AccountingEntities" EnableFlattening="False" 
EntitySetName="Invoices" 
Select="it.[InvoiceNumber], it.[Amount]"> 
</asp:EntityDataSource> .

blah blah blah rest of the question.

I don't know of a single programmer who uses scripted datasource objects in their web forms, yet all the documentation and courses teach that method.  It reminds me that being an MCP only means that I've learned how to take the tests; but has no bearing in the real world.  So, each time I think about getting certified, I end up talking myself out of it.  However, I know the market value for certified people and employers do like abbreviations after your name...

Guess I'll buy a book and see how it goes; then re-evaluate the situation.

Tags: , ,

General | Programming | .Net

What's The Point

by John 16. February 2011 04:45

Someone recently asked me what the point of this blog is.  That's a fair question.  There are hundreds of other tech blogs - most far more technical than this one.  The reason I started this is because every once in a while, I run across something that just strikes my fancy in such a way that I would love to share it.  It could be something I did which I consider to be excellent, it could be something "Dilbert-ish", or it could be something I read that I find share-worthy.

When I post little code snippets, they're one of two things: awesome or entertaining.  Like that little blurb of HTML in the last post.  I mean seriously, p - b - br - /b /p  no text, no labels, no placeholder, no names, no... anything.  That's just hilarious to me.  Maybe I'm too sarcastic to be a programmer? 

Every programmer who has ever been around the block has run into situations where they find themself in a situation which could drive you crazy.  If you don't find a way to deal with it, you will lose it and bad things happen. This blog is an outlet of sorts for me.  

Recently I've been talking about working with some older code.  I don't have a problem with that, but I'd be lying through my teeth if I didn't look at this stuff and remember all the times I spent writing this exact same type of stuff.  Because I've written thousands of lines of the same code, I feel justified is pointing it out in a mocking manner - because I'd be laughing at my own code if I ran across that too. Think about it: How many hours (over the years) have web developers wasted going back through their HTML source to capitalize their tags because that was the standard?  An awful lot.  Now, lowercase is the standard, so when VSIDE starts complaining about XHTML 4.0 compliancy, I just have to laugh.

I laugh because I find it entertaining just how little we programmers stick to our guns.  I'm quite sure that when CAPITALIZATION was the standard, those standard-mongers would go to war over a lowercase anchor tag.  When M$ said "oops, that looks terrible... um... the new standard is lowercase." those same people were the first to write RegEx scripts to parse through all that html and replace A with a.  If the next standard is UpAnDdOwN, I'm sure we'll have hundreds of RegEx's that do just that as well.

As much as I'd love to just do what I know, do what I did best, I can't. No full-time programmer can.  If we did, we'd be out of a job.  We have to evolve, adapt and overcome our own standards to adhere to what the marketplace wants.  I, personally, despise the idea of ending all lines with a semicolon. I hated it in Turbo Pascal, and I hate it in C# - but the difference is, now I get paid to put those semicolons in; and that makes all the difference.  I would prefer not to, but what I want and what the market wants don't always align.  I understand that - and I think any programmer that's been around longer than a few years understands that.  Especially as consultants, we are (or should be) the code-generating equivalent of Mystique.  We conform to whereever we are and however it's done there.  It doesn't mean we aren't still people with our own brand of humor, sarcasm, faith or lifestyle; it just means that the longer we're in this business, the more we become that old man in the bar who's been everywhere, behind the scenes, seen the show and saw the strings.  We should be happy to be that person because that means we've had a nice long run - and hopefully still running.

Tags: , ,

General

About Me

I'm a .Net developer in St. Louis, MO working for Trizetto Provider Solutions. 

Professional Info

Widget Flash Tag cloud not found.

Unable to cast object of type 'ASP.widgets_flash_tag_cloud_widget_ascx' to type 'App_Code.Controls.WidgetBase'.X