More TDD

As I mentioned a few weeks ago, Test Driven Design is definitely the way to go for small, well-defined problems. One of our homework problems in algorithms is to create an algorithm that chooses a sequence of babysitters to cover a given time period where each member of the candidate pool can cover some subset of the period. There are a bunch of edge cases that take some thinking through. Or, you could just write a bunch of test cases and code to each until you have a solution. As is so often the case in TDD solutions, the final version is actually a reasonably efficient implementation, but one could very aggressively tune it knowing that there is a reliable test suite to validate your tunings.

Here are the test cases (this is all C# if that isn't immediately obvious):

using System;
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using AlgorithmHarness.Optimization;

namespace OptimizationTests
{
    [TestClass]
    public class BabysitterTests
    {
        private static BabySitter scheduler = new BabySitter();
        private static List<Candidate> result = new List<Candidate>();

        [TestMethod]
        public void ConstructorNonNull()
        {
            Assert.IsNotNull(scheduler);
        }

        [TestMethod]
        [ExpectedException(typeof(ArgumentNullException))]
        public void NullCandidateListShouldThrowException()
        {
            result.Clear();
            scheduler.Schedule(new DateTime(1), new DateTime(10), null, result);
        }

        [TestMethod]
        [ExpectedException(typeof(ArgumentOutOfRangeException))]
        public void StartAfterFinishShouldThrowExectption()
        {
            List<Candidate> candidates = new List<Candidate>();
            result.Clear();
            scheduler.Schedule(new DateTime(10), new DateTime(1), candidates, result);
        }

        [TestMethod]
        public void EmptyListReturnsNoSolution()
        {
            List<Candidate> candidates = new List<Candidate>();
            result.Clear();
            Assert.AreEqual(false, scheduler.Schedule(new DateTime(1), new DateTime(10), candidates, result));
        }

        [TestMethod]
        public void ScheduleSingleInput()
        {
            List<Candidate> candidates = new List<Candidate>()
            {
                new Candidate(1, new DateTime(1), new DateTime(10))
            };
            result.Clear();
            Assert.AreEqual(true, scheduler.Schedule(new DateTime(2), new DateTime(9), candidates, result));
            ValidateCoverage(new DateTime(2), new DateTime(9), result, "Step 1");

            // shouldn't find a solution
            result.Clear();
            Assert.AreEqual(false, scheduler.Schedule(new DateTime(1), new DateTime(11), candidates, result));
        }

        [TestMethod]
        public void ScheduleSingleResult()
        {
            List<Candidate> candidates = new List<Candidate>()
            {
                new Candidate(1, new DateTime(1), new DateTime(2)),
                new Candidate(2, new DateTime(2), new DateTime(5)),
                new Candidate(3, new DateTime(2), new DateTime(7)),
                new Candidate(4, new DateTime(3), new DateTime(12)),
                new Candidate(5, new DateTime(4), new DateTime(8)),
                new Candidate(6, new DateTime(9), new DateTime(15)),
                new Candidate(7, new DateTime(16), new DateTime(20))
            };

            result.Clear();
            Assert.AreEqual(true, scheduler.Schedule(new DateTime(16), new DateTime(18), candidates, result));
            ValidateCoverage(new DateTime(16), new DateTime(18), result, "Step 1");
            Assert.AreEqual(1, result.Count, "Step 1 count");

            result.Clear();
            Assert.AreEqual(true, scheduler.Schedule(new DateTime(4), new DateTime(12), candidates, result));
            ValidateCoverage(new DateTime(4), new DateTime(12), result, "Step 2");
            Assert.AreEqual(1, result.Count, "Step 2 count");

            // no solution
            result.Clear();
            Assert.AreEqual(false, scheduler.Schedule(new DateTime(3), new DateTime(18), candidates, result), "Step 3");

            result.Clear();
            Assert.AreEqual(false, scheduler.Schedule(new DateTime(3), new DateTime(25), candidates, result), "Step 4");
        }

        [TestMethod]
        public void ScheduleSitters()
        {
            List<Candidate> candidates = new List<Candidate>()
            {
                new Candidate(1, new DateTime(1), new DateTime(2)),
                new Candidate(2, new DateTime(2), new DateTime(5)),
                new Candidate(3, new DateTime(2), new DateTime(7)),
                new Candidate(4, new DateTime(3), new DateTime(12)),
                new Candidate(5, new DateTime(4), new DateTime(8)),
                new Candidate(6, new DateTime(9), new DateTime(15)),
                new Candidate(7, new DateTime(16), new DateTime(20))
            };

            result.Clear();
            Assert.AreEqual(true, scheduler.Schedule(new DateTime(1), new DateTime(10), candidates, result));
            ValidateCoverage(new DateTime(1), new DateTime(10), result, "Step 1");
            Assert.AreEqual(3, result.Count, "Step 1 count");

            result.Clear();
            Assert.AreEqual(true, scheduler.Schedule(new DateTime(1), new DateTime(12), candidates, result));
            ValidateCoverage(new DateTime(1), new DateTime(12), result, "Step 2");
            Assert.AreEqual(3, result.Count, "Step 2 count");

            result.Clear();
            Assert.AreEqual(true, scheduler.Schedule(new DateTime(1), new DateTime(15), candidates, result));
            ValidateCoverage(new DateTime(1), new DateTime(15), result, "Step 3");
            Assert.AreEqual(4, result.Count, "Step 3 count");

        }

        private void ValidateCoverage(DateTime start, DateTime finish, List<Candidate> candidates, string test)
        {
            Assert.IsNotNull(candidates, test + ": Null return");
            foreach (Candidate candidate in candidates)
            {
                Assert.AreEqual(true, candidate.Start <= start, test + " start: " + start.Ticks + "Id: " + candidate.Id);
                start = candidate.Finish;
                if (start >= finish) return;
            }
            Assert.Fail(test + " failed to cover finish");
        }
    }
}

and here's the resulting algorithm:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace AlgorithmHarness.Optimization

{

    public class Candidate

    {

        public Candidate(int id, DateTime start, DateTime finish)

        {

            Id = id;

            Start = start;

            Finish = finish;

        }

        public int Id { get; set; }

        public DateTime Start { get; set; }

        public DateTime Finish { get; set; }

    }

    public class BabySitter

    {

        public BabySitter() { }

        public bool Schedule(DateTime start, DateTime finish, List<Candidate> candidates, List<Candidate> result)

        {

            if ((null == candidates) || (null == start) || (null == finish)) throw new ArgumentNullException();

            if (start >= finish) throw new ArgumentOutOfRangeException();

            if (candidates.Count == 0) return false;

            Candidate best = null;

            List<Candidate> next = new List<Candidate>();

            foreach (Candidate candidate in candidates)

            {

                if (candidate.Start <= start)

                {

                    if (candidate.Finish >= finish)

                    {   // this one can cover the remaining time

                        // so that's good enough

                        result.Add(candidate);

                        return true;

                    }

                    else if ((best == null) || (candidate.Finish > best.Finish))

                        // best we've found so far

                        best = candidate;

                    //else - they can't go as long as one we've already got,

                    // so there's no reason to consider them further

                }

                else

                    // this one can't start early enough to use now,

                    // but might work out later

                    next.Add(candidate);

            }

            if (best == null) return false;  // nobody available at this start time

            // try to find an optimal solution for the remaining time

            // using just the sitters with later start times

            result.Add(best);

            return Schedule(best.Finish, finish, next, result);

        }

    }

}

It looks like more than it is because of the exception trapping and comments. The actual algorithm is a mere 11 lines of code.