Maximum Date String from 12 Random Digits

[dixitjain]

Date Time

Problem Description

Arun and his sister Usha are challenging each other with some mathematical puzzles. Usha, the cleverer one, has come up with the idea of givingArun 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 digits (any of 0-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.

[mtf]

To solve for the MM we need to determine if 0, 1, or 2 are present. If none are present, or only one of the three, then a month cannot be formed.

>>> from random import randrange
>>> import itertools
>>> digits = [randrange(10) for _ in range(12)]
>>> digits
[9, 3, 3, 5, 7, 9, 5, 5, 2, 5, 1, 1]
>>> mm_digits = list(filter(lambda x: 0 <= x < 3, digits))
>>> mm_digits
[2, 1, 1]
>>> mm_list = list(itertools.permutations(mm_digits, 2))
>>> mm_list
[(2, 1), (2, 1), (1, 2), (1, 1), (1, 2), (1, 1)]
>>> mm_candidates = sorted([''.join([str(x[0]), str(x[1])]) for x in mm_list])
>>> mm_candidates
['11', '11', '12', '12', '21', '21']
>>> mm_usable = list(filter(lambda x: int(x) < 13, mm_candidates))
>>> mm_usable
['11', '11', '12', '12']
>>> mm = max(mm_usable)
>>> mm
'12'
>>> rem_digits = list(mm)
>>> for x in rem_digits:
	digits.remove(int(x))

	
>>> digits
[9, 3, 3, 5, 7, 9, 5, 5, 5, 1]
>>> 

In the last step we removed the two digits used for mm from the digits list.

Now to find the largest date in mm. This in itself a project but we can simplify this by predeclaring a list of month lengths.

mon_days = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

or create a lookup table…

mon_days = {
  '01':31,
  '02': 28,
  '03': 31,
  '04': 30,
  '05': 31,
  '06': 30,
  '07': 31,
  '08': 31,
  '09': 30,
  '10': 31,
  '11': 30,
  '12': 31
}

>>> month_len = mon_days[mm]
>>> digits
[9, 3, 3, 5, 7, 9, 5, 5, 5, 1]
>>> dd_list = list(itertools.permutations(digits, 2))
>>> dd_candidates = sorted([''.join([str(x[0]), str(x[1])]) for x in dd_list])
>>> dd_usable = list(filter(lambda x: int(x) <= month_len, dd_candidates))
>>> dd_usable
['13', '13', '15', '15', '15', '15', '17', '19', '19', '31', '31']
>>> dd = max(dd_usable)
>>> dd
'31'
>>> rem_digits = list(dd)
>>> for x in rem_digits:
	digits.remove(int(x))

	
>>> digits
[9, 3, 5, 7, 9, 5, 5, 5]
>>> 

Now to extract hour and minutes…

>>> hr_list = list(itertools.permutations(digits, 2))
>>> hr_candidates = sorted([''.join([str(x[0]), str(x[1])]) for x in hr_list])
>>> hr_usable = list(filter(lambda x: int(x) < 24, hr_candidates))
>>> hr_usable
[]
>>> hr = max(hr_usable)
Traceback (most recent call last):
  File "<pyshell#393>", line 1, in <module>
    hr = max(hr_usable)
ValueError: max() arg is an empty sequence
>>> 

We have no valid hour data so the program should output 0. Let’s pretend we do have a valid hour and complete the minutes. Assume the digits list has been updated prior to this step.

>>> mins_list = list(itertools.permutations(digits, 2))
>>> mins_candidates = sorted([''.join([str(x[0]), str(x[1])]) for x in mins_list])
>>> mins_usable = list(filter(lambda x: int(x) < 60, mins_candidates))
>>> mins_usable
['35', '35', '35', '35', '37', '39', '39', '53', '53', '53', '53', '55', '55', '55', '55', '55', '55', '55', '55', '55', '55', '55', '55', '57', '57', '57', '57', '59', '59', '59', '59', '59', '59', '59', '59']
>>> mins = max(mins_usable)
>>> mins
'59'

Last of all we will construct a valid date string.

    print ("{}/{} {}:{}".format(mm, dd, hr, mins))

This has been essentially a thought experiment and can no doubt be refactored and simplified. Python gives us so many ways to do the same thing.

---

I’ve created a function and refactored slightly (no sorting, usable set) and get these results…

import itertools
from random import randrange
print (max_date_str([randrange(10) for _ in range(12)]))

============== RESTART: D:/cc/discuss/users/mtf/max_date_str.py ==============
09/30 20:59
>>> 
============== RESTART: D:/cc/discuss/users/mtf/max_date_str.py ==============
0
>>> 
============== RESTART: D:/cc/discuss/users/mtf/max_date_str.py ==============
12/30 23:49
>>> 
============== RESTART: D:/cc/discuss/users/mtf/max_date_str.py ==============
12/30 09:59
>>> 
============== RESTART: D:/cc/discuss/users/mtf/max_date_str.py ==============
12/19 09:58
>>> 

[mtf]

============== RESTART: D:/cc/discuss/users/mtf/max_date_str.py ==============
12/31 23:58
>>>