CodeVita 2018 Round 1 : Date Time

Here I am writing solution of one of the question asked in CodeVita 2018, Round 1. The question is titled as DATE TIME. Go through the below link:

Arun and his sister Usha are challenging each other with some mathematical puzzles. Usha, the cleverer one, has come up with the idea of giving Arun 12 distinct digits from 0 to 9, and have him form the largest date time in 2018 with them.
Arun is a little nervous, and asks you to help him with a computer program.
Usha will give Arun 12 distinct digits. He needs to create a date time combination in the year 2018: the date in the MM/DD form (all four digits must be present), and the time in the format HH:MM (all four digits must be present). 
The date may be from 01/01 to 12/31 and the time may be from 00:00 to 23:59 (in the 24 hour format). The digits provided may be used only once in the answer that Arun gives.
If more than one date time combination may be formed, Arun needs to give the latest valid date time possible in the year 2018.

Constraints : single digit 0 to 9

Input Format: A line consisting of a sequence of 12 (not necessarily distinct) single digits (any of 0-9) separated by commas. The sequence will be non-decreasing.

Output: The maximum possible valid date time in the year 2018. The output must be in the format
MM/DD HH:MM
If no date time can be constructed, the output should be 0

Explanation: 
Example1 :
          Input
          0,0,1,2,2,2,3,5,9,9,9,9
          
          Output
          12/30 22:59
          
          Explanation
          The 12 digits to be used by Arun are given.
          The maximum valid date time using only the digits given, and with each digit used at most once is
          12/30 22:59
          This is the output.
Example 2
          Input
          3,3,3,3,3,3,3,3,3,3,3,3
          
          Output
          0
          
          Explanation
          As no digit less than 3 is present in the input, a valid month cannot be formed. Hence no valid Date time can be               formed with the input digits.

Hope you understand the question, if not , here is its short version:

Given 12 one-digit numbers, you need to make a latest date and time possible for the year 2018, by choosing the numbers at most once. (MM/DD HH:MM)

Input: 0,0,0,1,2,3,4,5,6,7,8,9

Output: 12/30 09:58

So, to make it latest, first we will try to choose the last month possible that is December i.e. 12.

We are left with 0,0,0,3,4,5,6,7,8,9. MM = 12

Now we will try to choose the last day of the month, in this case, it is 31st. But we can’t choose that because there is no ‘1’ left in the list. So we will try to choose 30th. It is possible to choose ‘3’ and ‘0’ as these are available.

We are left with 0,0,4,5,6,7,8,9. DD = 30

Now we need to choose 24-hour time format. HH:MM . Again we will try to choose the maximum out of it . i.e. 23:59 . But wait , there is no ‘2’ and ‘3’ left in out list. So we can go with 22, 21, 20, 19, 18 .. and so on. Similarly we don’t have ‘2’ and ‘1’ left in out list. So we should go for 09, 08, 07, 06…so on.

As we have ‘0’ and ‘9’ left in our list . We can go for it. HH = 09

We are left with 0,4,5,6,7,8. HH = 09

For minutes, we can go for 59, 58, 57, 56, … so on. 59 is rejected as there is no ‘9’. So we will choose 58 as ‘5’ and ‘8’ are available.

So, MM = 58

Final answer : 12/30 09:58 .

Hence, this is the latest date and time of year 2018 we can make by using the number in the given list.

Corner cases:

Input: 0,1,2,3,4,5,6,7,8,9,9,9

Output: 09/29 19:58

Why??

Because if you select ‘1’ and ‘2’ as the month and ‘3’ and ‘0’ as day. Then you will left with nothing to represent the Hour. Because Hour require either ‘0’ , ‘1’ or ‘2’ as its first digit.

How I wrote the solution :

PART 1:

I, first, made the solution using if and else statement and looping in which the solution first iterate for Month, then Day, and then Hour and Minute , and if there is no any solution left then I used to output it as 0. But then I realised “I am missing something”.

I forgot the corner cases and therefore the Online Judge was not accepting my solution.

Then I went for another solution from scratch after realising my mistakes.

Here I used the idea of nested loops .

There were main loop for MONTH within loop for DAYS within loop for HOUR and within loop for MINUTE.

I used the Hash array to store the frequency of digits available to use.

Actually I used two hash arrays. One is for storing previous state of hash array as upd[] and another is for storing current state of hash array as hashfn[].

I made two functions:

switch2pre() : For switching to the previous hash array i.e. upd[] to the current hash array i.e. hashfn[]

updated(): For saving the content of current hash array i.e. hashfn[] to the upd[].

……….Working………

The MONTH loop will find the highest possibility and update the hash array hashfn[], then it will move inside to the next loop i.e. DAY loop and find the highest possibility and then, it will move to the next loop i.e. HOUR loop and if it went right , it will move to the next loop i.e. MINUTE loop.

Now in any loop if it found that there is no possibility left then that element will make it value to -1 and the control went to the parent loop then the parent switch to their previous hashfn and look for next possible value for their element . This process goes on and on.

And if it found one, the loop breaks suddenly and output the found answer.

And if it didn’t find one , the loop reach to the end where one of them has -1 value which indicates to output 0.

I haven’t covered many things in this as I wanted to keep it as short as possible. Comment if you have some doubts.

Thanks for reading!