4
\$\begingroup\$

Problem description:

The task is to calculate the amount of money earned from roller coaster rides on any given day.

  • There is a queue in front of the attraction.
  • Visitors might be alone or in groups. All members of the same group will want to ride together.
  • The ride begins once the roller coaster runs out of sufficient space for the next group.
  • Once a ride is over, passengers go back to the end of the queue in the same order.
  • Each passenger pays one dirham to ride the roller coaster once.
  • The roller coaster can only operate a limited number of times each day.

  • Here is my code:

    public static class RollerCoaster
    {
        private static int CountDirhamsEarnedInOneOperation(int numAvailablePlaces, LinkedList<int> numPeopleInEachGroup)
        {
            //Each passenger pays one dirham to take the ride once.
            int dirhamsEarned = 0;
            int numGroupsInQueue = numPeopleInEachGroup.Count();
    
            while (numPeopleInEachGroup.First() <= numAvailablePlaces && numGroupsInQueue > 0)
            {
                dirhamsEarned += numPeopleInEachGroup.First();
                numAvailablePlaces -= numPeopleInEachGroup.First();
                numPeopleInEachGroup.AddLast(numPeopleInEachGroup.First()); 
                numPeopleInEachGroup.RemoveFirst();
                numGroupsInQueue--;
            }
    
            return dirhamsEarned;
        }
    
        public static long CalculateDirhamsEarned(int numAvailablePlaces, int numOperationsPerDay, LinkedList<int> numPeopleInEachGroup)
        {
            long dirhamsEarned = 0;
    
            while (numOperationsPerDay > 0)
            {
                dirhamsEarned += (long)CountDirhamsEarnedInOneOperation(numAvailablePlaces, numPeopleInEachGroup);
                numOperationsPerDay--;
            }
    
            return dirhamsEarned;
        }
    }
    
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Please enter:\nThe number of places available;\nThe number of times the attraction can function per day;\nThe number of groups in the queue.");
            string[] inputs = Console.ReadLine().Split(' ');
    
            int numAvailablePlaces = int.Parse(inputs[0]);
            int numOperationsPerDay = int.Parse(inputs[1]);
            int numGroupsInQueue = int.Parse(inputs[2]);
            LinkedList<int> numPeopleInEachGroup = new LinkedList<int>();
    
            Console.WriteLine("Please enter, line by line, the number of people in each group: ");
            for (int i = 0; i < numGroupsInQueue; i++)
            {
                int numPeopleInGroup = int.Parse(Console.ReadLine());
                numPeopleInEachGroup.AddLast(numPeopleInGroup);
            }
    
            long dirhamsEarned = RollerCoaster.CalculateDirhamsEarned(numAvailablePlaces, numOperationsPerDay, numPeopleInEachGroup);
            Console.WriteLine(dirhamsEarned.ToString());
        }
    }
    

    I'm a C# beginner, so I'd appreciate any kind of advice, though I am specifically looking for suggestions that help me improve the time-complexity of my algorithm. My program takes way too long to run when numOperationsPerDay is, say, 10,000,000.

    \$\endgroup\$
    5
    \$\begingroup\$

    One of the suggestions I would make is to improve your input handling. You don't handle invalid integers well at all.

    string input = "invalid int";
    int numAvailablePlaces = 0;
    
    while (!int.TryParse(input, out numAvailablePlaces))
    {
        Console.WriteLine("Please enter a valid integer for the number of places available.");
        input = Console.ReadLine();
    }
    

    And similarly for the other int's you grab. (You could also do them all in one loop.)


    This method:

    private static int CountDirhamsEarnedInOneOperation(int numAvailablePlaces, LinkedList<int> numPeopleInEachGroup)
    {
        //Each passenger pays one dirham to take the ride once.
        int dirhamsEarned = 0;
        int numGroupsInQueue = numPeopleInEachGroup.Count();
    
        while (numPeopleInEachGroup.First() <= numAvailablePlaces && numGroupsInQueue > 0)
        {
            dirhamsEarned += numPeopleInEachGroup.First();
            numAvailablePlaces -= numPeopleInEachGroup.First();
            numPeopleInEachGroup.AddLast(numPeopleInEachGroup.First()); 
            numPeopleInEachGroup.RemoveFirst();
            numGroupsInQueue--;
        }
    
        return dirhamsEarned;
    }
    

    Does too much. Break the inside of that while loop to a new method.


    Other than that, there's little to say in my opinion.

    \$\endgroup\$
    2
    • 1
      \$\begingroup\$ Thanks for your comment! Will you kindly explain what you meant by your comment that the method "does too much"? It is meant to only calculate the revenue earned from one ride, so how is that doing too much? Sorry if I sound defiant because that is not my intention; I am just confused. :-) \$\endgroup\$
      – M.Y. Babt
      Oct 6 '15 at 14:47
    • 1
      \$\begingroup\$ @MY_G Methods should have one responsibility. That one has two: looping through each group, and calculating the new information. These are separate actions and as such should be in separate methods (with one calling the other). \$\endgroup\$ Oct 6 '15 at 14:48
    3
    \$\begingroup\$

    Imagine that instead of a line, your queue is a loop. Every time the rollercoaster runs, the same thing happens:

    • You earn some money
    • The loop remains in the same order, but the index of the head of the group changes

    How much money, and what the new index changes to, depends on the make-up of the queue (which is constant), and the previous index.

    This, I think, is the basis of your updated solution in your answer, but I think it can be done a lot more cleanly. From the description above, you can see that what you have is a mapping headOfQueue -> (moneyEarned, headOfQueue), so the data structure we're going to want is something like Dictionary<int,Tuple<int,int>>

    Based on that, we need two things: to populate the dictionary, and to iterate over it accumulating money. The second one is easy:

    public static int RunRollercoaster(Dictionary<int,Tuple<int,int>> queue, int runs)
    {
        var queueHead = 0;
        var money = 0;
    
        for(int i=0; i<runs;i++)
        {
            var outcome = queue[queueHead];
            queueHead = outcome.Item1;
            money += outcome.Item2;
        }
    
        return money;
    }
    

    The first has a little more to it. I think it's worth special-casing the situation where everyone can fit on the rollercoaster:

    public static Dictionary<int,Tuple<int,int>> AnalyseQueue(List<int> groups, int capacity)
    {
        if (groups.Sum() <= capacity)
        {
            return new Dictionary<int,Tuple<int,int>>
            {
                {0, Tuple.Create(0, groups.Sum())
            };
        }
    
       var result = new Dictionary<int,Tuple<int,int>>();
       var queueHead = 0;
    
       while(true)
       {
           if(result.ContainsKey(queueHead)) { return result; }
    
           result[queueHead] = GetQueueOutcome(groups, capacity, queueHead);
       }
    }
    
    public static Tuple<int,int> QueueOutcome(List<int> groups, int capacity, int queueHead)
    {
        var admitted = 0;
        while(!(capacity - admitted < groups[queueHead]))
        {
            admitted += groups[queueHead];
            queueHead = queueHead + 1 % groups.Count;
        }
    
        return Tuple.Create(queueHead, admitted);
    }
    

    Another point for your original code is naming. Your instincts are good in that you're allowing your names to be as long as they need to be for descriptiveness. However, names shouldn't actually say more than is appropriate for the context.

    • The prefix num in numPeopleInEachGroup is confusing, as it's actually a list of numbers. But even in other cases where you really do have a number, that prefix is just unnecessary noise. numOperationsPerDay doesn't tell me anything that operationsPerDay wouldn't, both are quite obviously numbers.

    • The phrase "in each" in the same variable is misleading. For me it makes me think of a phrase like "there are 5 people in each group" or "the number of people in each group is 5". "Each" is often used like that to mean "every". So for me this actually degrades clarity rather than adding to it.

    • Sometimes you're needlessly specific, like in numOperationsPerDay or dirhamsEarned. This could just as well be operationsPerTimePeriod or moneyEarned. (Or, my preference operations and earned). The fact that it's a day or that you're using a specific currency isn't something you want to encode into your solution without reason, it makes it needlessly rigid

    \$\endgroup\$
    3
    \$\begingroup\$

    It seems to me that using a LinkedList means moving the data around a lot. Using a List instead and changing the index should be more efficient and also cut down on your code quite a bit. Something like this should work:

    public static long CalculateRevenue(int numAvailablePlaces, int numOperationsPerDay, List<int> groups)
    {
        int queueTotal = groups.Sum();
        if(queueTotal < numAvailablePlaces)
        {
            return queueTotal * numOperationsPerDay;
        }
        long revenue = 0;
        int groupIndex = 0;
        for (int ride = 1; ride <= numOperationsPerDay; ride++)
        {
            int currentSize = 0;
            while (currentSize + groups[groupIndex] <= numAvailablePlaces)
            {
                currentSize += groups[groupIndex++];
                if (groupIndex == groups.Count)
                {
                    groupIndex = 0;
                }
            }
            revenue += currentSize;
        }
        return revenue;
    }
    
    \$\endgroup\$
    1
    • \$\begingroup\$ If everyone can fit on the rollercoaster, this could potentially count the same group multiple times on one ride. \$\endgroup\$ Oct 7 '15 at 12:14
    1
    \$\begingroup\$

    Why is no one suggesting to use the Queue Class? It is designed as a first in first out (FIFO) queue. I don't know if there would be a need for ae temporary lists to move folks around, but waiting in line is still a FIFO thing... Hey, no cuts!

    1. Assumption: We take the next person - or group - in line and put them on the coaster if there is room. If no room just wait for next time.
    2. No group can be larger than the coaster capacity. For now, just ignore them.
    3. Use the Queue class
    4. Write a single method (sub-methods as needed!) to fill the waiting line. Prompt the user or hard code it.
    5. If a 10-person group shows up. WaitingLine.Enqueue(10).
    6. If 1 person shows up. WaitingLine.Enqueue(1).
    7. WaitingLine.Dequeue() to get next in line. Add that value to a DailyRiderCount.
    8. When the day is done, multiply the DailyRiderCount by the cost of a ticket.
    9. 2/3 of the original code now goes away.
    10. Now it is running faster too.

    The following focuses on structure, not queuing huristics. Think Single Responsibility Principle and Information Hiding (encapsulation). Good structure will simplify client code significantly.

    public static main () {
        RollerCoaster theRattler = new RollerCoaster();
        TicketTaker barnum = new TicketTaker( theRattler );
        barnum.LetsHaveFun();
    }
    
    
    public class TicketTaker {
        protected int DailyRiderCount { get; set; }
        protected double DailyReceipts { get; set; }
        protected int CurrentRiders { get; set; }
        protected Queue WaitingLine { get; set; }
        protected RollerCoaster theRide { get; set; }
    
        public TicketTaker ( RollerCoaster theRattler ) {
            if ( theRattler == null) 
                throw new ArgumentNullException ("Where is the roller coaster?");
    
                theRide = theRattler;
        }
    
        public void LetsHaveFun() {
            Open();
            while ( ! theRide.AtRunLimit ) { NewRun(); };
            Close();
        }
    
        protected void Open () {
            Console.WriteLine ("We're open! Step right up and get your tickets!");
            DailyReceipts = 0;
            DailyRiderCount = 0;
            theRide.Open();
        }
    
        protected void Close () {
            Console.WriteLine("Closed for the day folks");
            Console.WriteLine("You don't have to go home but you can't stay here. \n\n");
            CalculateRevenue();
            theRide.Close();
        }
    
        protected void NewRun () {
            FillCoaster();  // some logic to optimize group integrity
            SellTickets();  // calc revenue for current ridership.
            theRide.Run();
            Console.WriteLine (theRide);
            RemovePassengers();  // re-queue riders.
        }
    }
    
    
    public class RollerCoaster {
        protected int Capacity { get; protected set; }
        protected int DailyRunLimit { get; protected set; }
        protected int RunsToday { get; set; }
        public bool AtRunLimit { get { return DailyRunLimit - RunsToday <= 0; } }
    
    
        public RollerCoaster ( int capacity = 32, int dailyRunLimit = 100 ) {
            Capacity = capacity;
            DailyRunLimit = dailyRunLimit;
        }
    
        public void Open () {
            RunsToday = 0;
        }
    
        public void Close () {
            // don't know if there is anything to do yet
        }
    
        public void Run() {
            RunsToday++;
        }
    
        public override string ToString() {
            return string.Format ( "Current Run: {0}, Runs Left {1}", RunsToday, 
                DailyRunLimit - RunsToday );
        }
    }
    
    \$\endgroup\$
    -1
    \$\begingroup\$
    1. COMMENTS!!!
    2. Making the Roller Coaster a static class with static functions means you can only have one in your park, so I wouldn't do that.
    3. numPeopleInEachGroup.AddLast(numPeopleInEachGroup.First()); everybody gets back on the coaster after their ride?
    4. While loops are generally less popular than for loops, you might want to see if you can use them instead.
    5. Try preincremnting and decrementing rather than post i.e. ++aVariable rather than aVariable++. The reason is once you start working with things other that ints it is going to be faster.
    \$\endgroup\$
    1
    • \$\begingroup\$ Thanks for your comment! "everybody gets back on the coaster after their ride?" Yes, that is indeed the case :-) \$\endgroup\$
      – M.Y. Babt
      Oct 6 '15 at 14:49

    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.