5
\$\begingroup\$

Problem

You are planning a big programming conference and have received many proposals which have passed the initial screen process but you're having trouble fitting them into the time constraints of the day -- there are so many possibilities! So you write a program to do it for you.

• The conference has multiple tracks each of which has a morning and afternoon session.
• Each session contains multiple talks.
• Morning sessions begin at 9am and must finish by 12 noon, for lunch.
• Afternoon sessions begin at 1pm and must finish in time for the networking event.
• The networking event can start no earlier than 4:00 and no later than 5:00. • No talk title has numbers in it.
• All talk lengths are either in minutes (not hours) or lightning (5 minutes).
• Presenters will be very punctual; there needs to be no gap between sessions.

Test input:

Writing Fast Tests Against Enterprise Rails 60min

Overdoing it in Python 45min

Lua for the Masses 30min

Ruby Errors from Mismatched Gem Versions 45min

Common Ruby Errors 45min

Rails for Python Developers lightning

Communicating Over Distance 60min

Accounting-Driven Development 45min

Woah 30min

Sit Down and Write 30min

Pair Programming vs Noise 45min

Rails Magic 60min

Ruby on Rails: Why We Should Move On 60min

Clojure Ate Scala (on my project) 45min

Programming in the Boondocks of Seattle 30min

Ruby vs. Clojure for Back-End Development 30min

Ruby on Rails Legacy App Maintenance 60min

A World Without HackerNews 30min

User Interface CSS in Rails Apps 30min

Test output:

Track 1:

09:00AM Writing Fast Tests Against Enterprise Rails 60min

10:00AM Overdoing it in Python 45min

10:45AM Lua for the Masses 30min

11:15AM Ruby Errors from Mismatched Gem Versions 45min

12:00PM Lunch

01:00PM Ruby on Rails: Why We Should Move On 60min

02:00PM Common Ruby Errors 45min

02:45PM Pair Programming vs Noise 45min

03:30PM Programming in the Boondocks of Seattle 30min

04:00PM Ruby vs. Clojure for Back-End Development 30min

04:30PM User Interface CSS in Rails Apps 30min

05:00PM Networking Event

Track 2:

09:00AM Communicating Over Distance 60min

10:00AM Rails Magic 60min

11:00AM Woah 30min

11:30AM Sit Down and Write 30min

12:00PM Lunch

01:00PM Accounting-Driven Development 45min

01:45PM Clojure Ate Scala (on my project) 45min

02:30PM A World Without HackerNews 30min

03:00PM Ruby on Rails Legacy App Maintenance 60min

04:00PM Rails for Python Developers lightning

05:00PM Networking Event

Implementation

using System;
using System.Collections.Generic;
using System.Linq;  
using System.Globalization;
using System.IO;



namespace Scheduler
{

    internal enum SessionType
    {
        MorningSession,
        EveningSession
    }


    /*
    *   This is the class that handles Conference scheduling. The method ScheduleTalks() is the interface for the external code. 
    */

    public class Conference
    {
        private List<Track> Tracks { get; set; }


        public void ScheduleTalks(List<Talk> talks)
        {

            if (talks.Count() == 0)
            {
                Console.WriteLine("No talks to schedule");
                return;
            }

            try
            {

                double totalDuration = talks.Sum(x => x.Duration);
                int numOfTracks = (totalDuration < Track.TotalMinPerTrack) ? 1 : (int)Math.Ceiling(totalDuration / Track.TotalMinPerTrack);

                Tracks = new List<Track>();
                int maxSet = talks.Count() > 6 ? 6 : talks.Count() - 1;

                for (int i = 0; i < numOfTracks; ++i)
                {
                    Tracks.Add(new Track(string.Format("Track {0}", i + 1)));
                    AllocateSessions(talks, i, Track.TotalMinInMorningSession, SessionType.MorningSession, maxSet);
                    AllocateSessions(talks, i, Track.TotalMinInAfterNoonSession, SessionType.EveningSession, maxSet);
                }


                if (talks.Count() > 0)
                {
                    int remainingTalksDuration = talks.Sum(x => x.Duration);
                    for (; maxSet > 0; --maxSet)
                    {
                        for (int index = 0; index < numOfTracks && talks.Count() > 0; ++index)
                        {
                            AllocateSessions(talks, index, Track.TotalMinInMorningSession, SessionType.MorningSession, maxSet);
                            AllocateSessions(talks, index, Track.TotalMinInAfterNoonSession, SessionType.EveningSession, maxSet);
                        }
                    }
                }

                // Write the data to file.
                using (var stream = new StreamWriter(@"output.txt"))
                {
                    CultureInfo culture = CultureInfo.CreateSpecificCulture("en-US");                  
                    string format = "hh:mm tt";

                    for (int i = 0; i < numOfTracks; ++i)
                    {
                        stream.WriteLine(Tracks[i].Id);
                        DateTime today = DateTime.Today.Add(new TimeSpan(09, 00, 00));

                        foreach (var item in Tracks[i].TalksForSession(SessionType.MorningSession))
                        {
                            stream.WriteLine("{0} {1}", today.ToString(format, CultureInfo.CreateSpecificCulture("en-US")), item);
                            today = today.AddMinutes(item.Duration);
                        }

                        today = Track.LunchTime;

                        stream.WriteLine("{0} Lunch", today.ToString(format, culture));
                        today = today.AddMinutes(Track.MinutesPerHour);

                        foreach (var item in Tracks[i].TalksForSession(SessionType.EveningSession))
                        {
                            stream.WriteLine("{0} {1}", today.ToString(format, culture), item);
                            today = today.AddMinutes(item.Duration);
                        }

                        // Networking event can start no earlier than 4:00 PM and no later than 5:00 PM.

                        if (today < Track.FourPM)
                        {
                            today = Track.FourPM;
                        }
                        else if (today > Track.FourPM && today < Track.FivePM)
                        {
                            today = Track.FivePM;
                        }

                        if (today == Track.FourPM || today == Track.FivePM)
                        {
                            stream.WriteLine("{0} Networking Event", today.ToString(format, culture));
                        }
                        else
                        {
                            stream.WriteLine("We went passed the scheduled time for the Networking Event");
                        }
                    }
                }
            }
            catch(Exception ex)
            {
                Console.WriteLine("Failed to schedule the talks due to this error.{0}", ex.Message);
            }
        }

        #region helperemethods
        private static IEnumerable<List<Talk>> GetCombinations(int step, int arrayIndex, List<Talk> combination, List<Talk> talks)
        {
            if (step == 0)
            {
                yield return combination;
            }

            for (int i = arrayIndex; i < talks.Count(); ++i)
            {
                combination.Add(talks[i]);
                foreach (var item in GetCombinations(step - 1, i + 1, combination, talks))
                {
                    yield return item;
                }
                combination.RemoveAt(combination.Count() - 1);
            }

        }

        private static List<Talk> LookForSessions(List<Talk> talks, int trackIndex, int totalMinutes, int maxSet)
        {
            List<Talk> combinations = new List<Talk>(talks.Capacity);

            List<Talk> talksInSession = new List<Talk>(maxSet);

            foreach (var item in GetCombinations(maxSet, 0, combinations, talks))
            {
                talksInSession.Clear();
                bool found = false;
                int availableMin = totalMinutes;
                var distinctUnscheduled = item.Where(x => !x.Scheduled).Distinct(new TalkEqualityComparer());

                foreach (var talk in distinctUnscheduled)
                {
                    availableMin -= talk.Duration;
                    talksInSession.Add(talk);
                    if (availableMin == 0)
                    {
                        found = true;
                        break;
                    }
                    if (availableMin < 0)
                    {
                        break;
                    }
                }

                if (found)
                {
                    break;
                }
                else
                {
                    availableMin = totalMinutes;
                }
            }

            return talksInSession;
        }

        private void AllocateSessions(List<Talk> talks, int trackIndex, int totalNumOfMinutes, SessionType sessionType, int maxSet)
        {

            if (Tracks[trackIndex].TalksExistForSession(sessionType))
            {
                return;
            }

            Action<List<Talk>> RemoveScheduledTalks = (t) =>
            {
                for (int i = 0; i < t.Count(); ++i)
                {
                    int index = i;
                    talks.Remove(t[i]);
                }
            };

            var talksForSession = LookForSessions(talks, trackIndex, totalNumOfMinutes, maxSet);
            if (talksForSession.Any())
            {
                Tracks[trackIndex].AddTalksToSession(sessionType, talksForSession);
                RemoveScheduledTalks(talksForSession);
            }
        }

        #endregion

    }



    internal class Session
    {
        public List<Talk> Talks { get; set; }
        public bool FilleUp { get; set; }
    }

    internal class Track
    {
        private const int SessionStartsAt = 9; // 24 hr format.
        private const int SessionEndsAt = 17;
        private const int LunchHour = 12;
        public static int MinutesPerHour = 60;

        public static int TotalMinPerTrack = (SessionEndsAt - SessionStartsAt - 1) * MinutesPerHour;
        public static int Minutesperhour = 60;
        public static int TotalMinInMorningSession = 60 * (LunchHour - SessionStartsAt);
        public const int TotalMinInAfterNoonSession = 60 * (SessionEndsAt - LunchHour - 1);

        public static DateTime FourPM = DateTime.Today.Add(new TimeSpan(16, 00, 00));
        public static DateTime FivePM = DateTime.Today.Add(new TimeSpan(17, 00, 00));
        public static DateTime LunchTime = DateTime.Today.Add(new TimeSpan(12, 00, 00));


        public string Id { get; set; }
        private Dictionary<SessionType, Session> Sessions { get; set; }

        public Track(string id)
        {
            Id = id;
            Sessions = new Dictionary<SessionType, Session>();
        }

        internal bool TalksExistForSession(SessionType sessionType)
        {
            return Sessions.ContainsKey(sessionType) && Sessions[sessionType].FilleUp;
        }

        internal void AddTalksToSession(SessionType sessionType, List<Talk> talksForSession)
        {
            Sessions.Add(sessionType, new Session() { Talks = talksForSession, FilleUp = true });
        }

        internal IEnumerable<Talk> TalksForSession(SessionType sessionType)
        {
            if (Sessions.ContainsKey(sessionType))
            {
                if (Sessions[sessionType].FilleUp)
                {
                    return Sessions[sessionType].Talks;
                }
            }
            return new List<Talk>();
        }
    }

    public class Talk : IEquatable<Talk>
    {
        public string Title { get; set; }
        public int Duration { get; set; } // in minutes.
        public bool Scheduled { get; set; }

        private string DurationFormat
        {
            get
            {
                return Duration == 5 ? "Lightning" : Duration + "min";
            }
        }

        public override string ToString()
        {
            return string.Format("{0} {1}", Title, DurationFormat);
        }


        public override bool Equals(object obj)
        {
            if (obj == null) return false;
            var talk = obj as Talk;
            if (talk == null) return false;

            return this.Equals(talk);
        }

        public override int GetHashCode()
        {
            return Title.GetHashCode();
        }

        public bool Equals(Talk other)
        {
            return this.Title.Equals(other.Title);
        }
    }


    internal class TalkEqualityComparer : IEqualityComparer<Talk>
    {

        public bool Equals(Talk x, Talk y)
        {
            if (Object.ReferenceEquals(x, y)) return true;

            if (Object.ReferenceEquals(x, null)) return false;

            if (Object.ReferenceEquals(y, null)) return false;

            return x.Title.Equals(y.Title);
        }

        public int GetHashCode(Talk obj)
        {
            return obj.Title.GetHashCode();
        }
    }
}


/*
 * Output: Output is written in a file in the current directory where 
 *         the executable is run. The erors are displayed on the console.
 * Assumption: Based on the sample output in the problem, it's assumed that 
 * the Networking Event should either start at 4 PM or 5 PM and not earlier 
 * than 4 PM or in between 4 and 5 PM or later than 5 PM.
*/

namespace Scheduler
{
    class ConferenceScheduler
    {
        static void Main(string[] args)
        {
            string line;
            var talks = new List<Talk>();

            Func<string, int> GetDuration = (duration) =>
            {
                if (duration.Equals("lightning"))
                {
                    return 5;
                }
                else
                {
                    return Int32.Parse(duration.Substring(0, duration.IndexOf('m')));
                }
            };

            Console.WriteLine("Enter empty line to stop input\n\n");
            while ( (line = Console.ReadLine()).Any())
            {
                var tokens = line.Split(new char[] { ' ' } ) ;
                var durationTime = tokens.Last();
                var title = string.Join(" ", tokens.Take(tokens.Count() - 1));
                talks.Add(new Talk() { Title = title, Duration = GetDuration(durationTime.ToLower()) });
            }

            Conference conference = new Conference();
            conference.ScheduleTalks(talks);

            Console.WriteLine("Done.Press Enter to Exit");
            Console.ReadKey();

        }
    }
}
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

Only focusing on ScheduleTalks()

This method is violating the single responsibility principle because it is filling the Tracks, format the output and writing the output to file.

You should consider to extract these parts to separate methods which makes your code easier to read and also better to maintain.

That being said, let us take a look at the code

        if (talks.Count() == 0)
        {
            Console.WriteLine("No talks to schedule");
            return;
        }  

seeing using the Count() method instead of the Count property on a List<T> always irritates me. Under the hood it will call for a ICollection<T> the Count property also, but needs a cast to check if the object is a ICollection<T>.

From the reference source

        ICollection<TSource> collectionoft = source as ICollection<TSource>;
        if (collectionoft != null) return collectionoft.Count;

Will this

            double totalDuration = talks.Sum(x => x.Duration);
            int numOfTracks = (totalDuration < Track.TotalMinPerTrack) ? 1 : (int)Math.Ceiling(totalDuration / Track.TotalMinPerTrack);

            Tracks = new List<Track>();
            int maxSet = talks.Count() > 6 ? 6 : talks.Count() - 1;  

ever be able to throw an exception ? I guess it won't. You should only place code inside a try..catch which throws an exception and the thrown exception should/could be handled.

Catching the general Exception isn't good either. You should always catch specific exceptions and if you need the algorithm not being interupted by an uncaught exception add the catching of Exception as the last catch.


This

            for (int i = 0; i < numOfTracks; ++i)
            {
                Tracks.Add(new Track(string.Format("Track {0}", i + 1)));
                AllocateSessions(talks, i, Track.TotalMinInMorningSession, SessionType.MorningSession, maxSet);
                AllocateSessions(talks, i, Track.TotalMinInAfterNoonSession, SessionType.EveningSession, maxSet);
            }


            if (talks.Count() > 0)
            {
                int remainingTalksDuration = talks.Sum(x => x.Duration);
                for (; maxSet > 0; --maxSet)
                {
                    for (int index = 0; index < numOfTracks && talks.Count() > 0; ++index)
                    {
                        AllocateSessions(talks, index, Track.TotalMinInMorningSession, SessionType.MorningSession, maxSet);
                        AllocateSessions(talks, index, Track.TotalMinInAfterNoonSession, SessionType.EveningSession, maxSet);
                    }
                }
            }

and especially this

if (talks.Count() > 0)  

irritated me and I needed to check the AllocateSessions() method. I din't expect that somehow magically the items of the talks list will be reduced. I would call this a side effect of the method which shouldn't happen like this.

A better and more obvious way would be to return a List<Talk> form the method which is then assigned to the talks variable. By breaking out of both loops if talks.Count == 0 the inner loop condition would be more obvious. A loop like for (; maxSet > 0; --maxSet) is IMHO not readable and should be replaced.

This would change the code above to

            for (int i = 0; i < numOfTracks; ++i)
            {
                Tracks.Add(new Track(string.Format("Track {0}", i + 1)));
                talks = AllocateSessions(talks, i, Track.TotalMinInMorningSession, SessionType.MorningSession, maxSet);
                talks = AllocateSessions(talks, i, Track.TotalMinInAfterNoonSession, SessionType.EveningSession, maxSet);
            }

            int remainingTalksDuration = talks.Sum(x => x.Duration);

            for (int mSet = maxSet; mSet > 0; --mSet)
            {
                if (talks.Count == 0) { break; }
                for (int index = 0; index < numOfTracks; ++index)
                {
                    talks = AllocateSessions(talks, index, Track.TotalMinInMorningSession, SessionType.MorningSession, mSet);
                    talks = AllocateSessions(talks, index, Track.TotalMinInAfterNoonSession, SessionType.EveningSession, mSet);
                    if (talks.Count == 0) { break; }
                }
            }

After these loops your Tracks property will be filled and the List<Talk> talks won't be needed anymore, so you could anything until now extract to a method private void FillTracks(List<Talk> talks).

Then I would create a method private string ComposeOutput() which composes the output based on the Tracks property by using a StringBuilder.

Writing the output to file or console should then be done by a method private void Export(string content) leaving you former ScheduleTalks() method like so

public void ScheduleTalks(List<Talk> talks)
{

    if (talks.Count == 0)
    {
        Console.WriteLine("No talks to schedule");
        return;
    }

    FillTracks(talks);

    string output = ComposeOutput();

    Export(output);

}
\$\endgroup\$
2
  • \$\begingroup\$ Thanks! I am not aware of the drawback of Count() compared to property Count . I agree with the side effect AllocateSessions() is causing as well. Otherwise, what do you think of the approach ? Can it be done better ? \$\endgroup\$
    – Jagannath
    Jul 30, 2015 at 7:10
  • 1
    \$\begingroup\$ Didn't dig into the overall algorithm, I don't have the time for it, so this short review will be it. Hopefully other reviewers step into and will check the algorithm. \$\endgroup\$
    – Heslacher
    Jul 30, 2015 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.