Parking Lot

At a certain college, a small parking lot is arranged in a rectangular shape, with 20 spaces numbered 1, 2, 3….. 19, 20. Traffic flow is one way in a counter- clockwise direction. The lot looks something like this:

         ______________________________________________________

        |                                                      |

        |  20   19   18   17   16   15   14   13   12   11     |

Exit  <<<<      <    <    <    <    <    <    <    <    <      |

        |  v                                            ^      |

Entrance  >>>>  >    >    >    >    >    >    >    >    >      |

        |  1    2    3    4    5    6    7    8    9    10     |

        |______________________________________________________|

Note that the first position encountered upon entering is 1 and the last is 20. Cars may exit or continue to drive in a counter-clockwise direction. The following assumptions apply to this problem:

  • At the start, class is in session and the lot is full (all 20 spaces are occupied by parked cars).
  • In addition to the (20) cars already parked in the lot, K autos are in the lot waiting for positions to become available. ( )
  • Each waiting auto is positioned behind one of the occupied spaces. When a position empties, the space is filled either by the car waiting at that position or, if no car is waiting at that position, by the closest car, bearing in mind that the traffic flow is one way. (There is sufficient room at each position for the car parked in that position to leave and the car waiting at that position to then park.)
  • When an auto advances N positions to a free spot, all other cars advance N positions. Since the lot is circular, advancing 4 positions from position 18 means advancing to position 2.
  • None of the waiting cars exits.

Input 

Write a program that reads data from standard input. Input consist of a line indicating the number of datasets, a blank line, and the datasets separated by a blank line. Each dataset is in two parts. The first part consists of integers, one per line beginning in column 1, representing initial positions of waiting autos. An integer 99 signals the end of this part of the data. The second part consists of integers, in the same format, representing positions vacated.

Positions are vacated in the order in which their numbers appear in the second part of the data.

Output 

The output of each dataset should consist a series of lines giving, for each initial (waiting) car position, the initial position and the final position of that car based on the description and assumptions stated above. The output lines must appear in the same order as the order of the initial positions given in the input. Print a blank line between datasets.

Sample Input 

1

 

6

19

17

13

1

99

1

3

20

16

Sample Output 

Original position 6 parked in 16

Original position 19 parked in 3

Original position 17 did not park

Original position 13 parked in 20

Original position 1 parked in 1

 

using System;

using System.Collections.Generic;

using System.Text;

using System.Collections;

 

namespace ConsoleApplication1

{

    class Program

    {

        static void Main(string[] args)

        {

            int[] parkingLot = new int[20];

            int[] waitingCarPos = { 6, 19, 17, 13, 1 };

            int[] vacatingPos = { 1, 3, 20, 16 };

            Hashtable ht = new Hashtable();

            //Initializing the parking lot with waiting positions

            for (int i = 0; i < waitingCarPos.Length; i++)

            {

                parkingLot[waitingCarPos[i] – 1] = waitingCarPos[i];

            }

            //Simulating the parking operation

            for (int i = 0; i < vacatingPos.Length; i++)

            {

                int j = 0;

                int count = -1;

                for (j = vacatingPos[i] – 1; ; j–)

                {

                    count++;

                    if (j == -1)

                    {

                        j = 19;

                    }

                    if (parkingLot[j] != 0)

                    {

                        break;

                    }

                }

                ht.Add((int)parkingLot[j], (int)vacatingPos[i]);

                parkingLot[j] = 0;

                for (j = 0; j < count; j++)

                {

                    RotateOnceAntiClockWise(parkingLot);

                }

            }

            for (int i = 0; i < waitingCarPos.Length; i++)

            {

                if (ht.ContainsKey((int)waitingCarPos[i]))

                {

                    Console.WriteLine("Original position " + waitingCarPos[i] + " parked in " + ht[waitingCarPos[i]]);

                }

                else

                {

                    Console.WriteLine("Original position " + waitingCarPos[i] + " did not park");

                }

            }

        }

        public static void RotateOnceAntiClockWise(int[] parkingLot)

        {

            int temp = parkingLot[parkingLot.Length – 1];

            for (int i = parkingLot.Length – 1; i >= 1; i–)

            {

                parkingLot[i] = parkingLot[i – 1];

            }

            parkingLot[0] = temp;

        }

    }

}

 

Original position 6 parked in 16
Original position 19 parked in 3
Original position 17 did not park
Original position 13 parked in 20
Original position 1 parked in 1
Press any key to continue . . .

Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s