Code Vita: Form the maximum possible time in the HH:MM:SS format using any six of nine given single digits

Question

Problem Description

The objective is to form the maximum possible time in the HH:MM:SS format using any six of nine given single digits (not necessarily distinct)

Given a set of nine single (not necessarily distinct) digits, say 0, 0, 1, 3, 4, 6, 7, 8, 9, it is possible to form many distinct times in a 24 hour time format HH:MM:SS, such as 17:36:40 or 10:30:41 by using each of the digits only once. The objective is to find the maximum possible valid time (00:00:01 to 24:00:00) that can be formed using some six of the nine digits exactly once. In this case, it is 19:48:37.

Input Format

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

Output

The maximum possible time in a 24 hour clock (00:00:01 to 24:00:00) in a HH:MM:SS form that can be formed by using some six of the nine given digits (in any order) precisely once each. If no combination of any six digits will form a valid time, the output should be the word Impossible

Explanation

Example 1

Input

0,0,1,1,3,5,6,7,7

Output 17:57:36

Explanation: The maximum valid time in a 24 hour clock that can be formed using some six of the 9 digits precisely once is 17:57:36

---

Example 2

Input

3,3,3,3,3,3,3,3,3

Output

Impossible

Explanation: No set of six digits from the input may be used to form a valid time.

The Code:

def bubbleSort(arr):
 n = len(arr)
 for i in range(n):
 for j in range(0, n-i-1):
 if arr[j] < arr[j+1] :
 arr[j], arr[j+1] = arr[j+1], arr[j]
seq_a=list(map(int,input().split(',')))
# print(seq_a)
bubbleSort(seq_a)
# print(seq_a)
hrs=[None,None]
mins=[None,None]
secs=[None,None]
#hrs
for x in seq_a:
 if x <= 2:
 hrs[0]=x
 seq_a.remove(x)
 break
# print(seq_a)
# print(hrs,mins,secs)
if hrs[0]:
 if hrs[0]==2:
 for x in seq_a:
 if x <= 4:
 hrs[1]=x
 seq_a.remove(x)
 break
 else: 
 for x in seq_a:
 if x <= 9:
 hrs[1]=x
 seq_a.remove(x)
 break
# print(seq_a)
# print(hrs,mins,secs)
#mins
if hrs[1]:
 for x in seq_a:
 if x < 6:
 mins[0]=x
 seq_a.remove(x)
 break
# print(seq_a)
# print(hrs,mins,secs)
if mins[0]:
 for x in seq_a:
 if x <= 9:
 mins[1]=x
 seq_a.remove(x)
 break
# print(seq_a)
# print(hrs,mins,secs)
#secs
if mins[1]:
 for x in seq_a:
 if x < 6:
 secs[0]=x
 seq_a.remove(x)
 break
# print(seq_a)
# print(hrs,mins,secs)
if secs[0]:
 for x in seq_a:
 if x <= 9:
 secs[1]=x
 seq_a.remove(x)
 break
# print(seq_a)
# print(hrs,mins,secs)
if secs[1]:
 print(str(hrs[0])+str(hrs[1])+':'+str(mins[0])+str(mins[1])+':'+str(secs[0])+str(secs[1]))
else:
 print('Impossible')

Answer 1

Bugs

Your program produces these erroneous results:

• 0,5,5,5,5,5,5,5,9 → Impossible (should be 09:55:55)
  0,2,5,5,5,5,5,5,5 → Impossible (should be 20:55:55)

  Due to tests like if hrs[0], if hrs[1], if mins[1], and if secs[1], hours, minutes, or seconds is a multiple of 10, or if the hour starts with 0.

• 2,2,4,4,4,4,4,4,7 → 24:47:44 (should be 22:47:44)

  The challenge states that 24:00:00 is the upper bound. The correct answer, 22:47:44, demonstrates that a naïve greedy algorithm is not sufficient to solve this problem. You might optimistically select 24 for the hour (which would work for input such as 0,0,0,0,2,4,9,9,9). However, for the input 2,2,4,4,4,4,4,4,7, you should then find that there is no valid minute if you pick 24 as the hour, and you would need to backtrack and try 22 for the hour.

Algorithm

There is no need to implement bubbleSort. Just call sorted(seq_a, reverse=True). (By PEP 8 naming conventions, the function should be named bubble_sort.)

Your code is repetitive: you write a similar for loop to handle each of the six digits. You should generalize them to be handled by one loop, which accepts different upper limits for each digit. Note that you use <= tests for most of those loops, but < 6 for some loops — the inconsistency is confusing.

Suggested solution

I would define a placewise_max function to generalize all of your loops, then call it with three limiting template strings. Instead of loops with break statements, though, I would use next() with a generator expression.

Note that there is no need to parse each character as a numeric digit: ASCII comparison will work just as well.

def placewise_max(max_template, pool):
 """
 Try to form the lexicographically greatest string from the characters in
 the pool, where the character in each position of the output does not
 exceed the character at the corresponding position in the template.
 Return the empty string if any position cannot be filled.
 >>> placewise_max('91210', list('02301'))
 '31200'
 >>> placewise_max('elmo', 'abcdefghijklm')
 'elmk'
 >>> placewise_max('elmo', 'limo')
 ''
 """
 pool = sorted(pool, reverse=True)
 output = []
 try:
 for t in max_template:
 char = next(c for c in iter(pool) if c <= t)
 pool.remove(char)
 output.append(char)
 return ''.join(output)
 except StopIteration: # next() failed to pick from the pool
 return ''
def max_time(digits):
 best = max(
 placewise_max('240000', digits),
 placewise_max('235959', digits),
 placewise_max('195959', digits)
 )
 if best and (best != '000000'):
 return '{0}{1}:{2}{3}:{4}{5}'.format(*best)
if __name__ == '__main__':
 print(max_time(input().split(',')) or 'Impossible')

Educational tips

The solution above uses some rather advanced techniques, and may be overwhelming for a beginner. However, I would point out an essential next step for improving your coding skills.

It is critical to learn to write functions, each with a clearly defined purpose, that accept parameters, return results, and use no global variables. Document the purpose, parameters, and outputs in a docstring, as I've done. That will force you to package your code into small, reusable chunks. For example, can you write a function that accepts a string (or list) of characters, and that returns a tuple with two items — the best possible hour that can be formed from those characters, and all the leftover characters that were not used to form the hour?

Defining a function is necessary to solve this problem correctly, because, as I've pointed out above, a correct solution requires some trial and error. If you are unable to reuse the code that performs the trials, then you will end up writing if-else statements to handle all of the failure cases, and it's going to be a huge mess!

• Phoenix: To fix the first 2 errors i changed if hrs[1] to if hrs[1]!=None. Even though hrs[1]==0 for 2,0,5,5,5,5,5,5,5 it does not return True thus not satisfying the If condition.
• Phoenix: Is it allowed to make corrections in the above code for the mistakes that you pointed out ?
• 200_success: No, please don't change the code in the question now. See What to do when someone answers for what to do next.

Answer 2

200_success had some great tips for how to make your solution better, however I'd suggest that you use the power of python for your solution. Sure, it won't be as fast as it could be, but if you are looking for speed you can use other languages.

Since we're dealing with permutations of numbers, we can use itertools to generate all permutations. And since we're dealing with times, we can use datetime.datetime and datetime.time.

The idea is simple: let itertools generate all permutations of length 6, and let datetime check if they are valid time strings.

import itertools
from datetime import datetime
inp = [0,9,5,5,5,5,5,5,5]
form = "%H:%M:%S"
possible = False
max_time = datetime.strptime("00:00:00", form).time()
for perm in itertools.permutations(inp, 6):
 time_string = "%d%d:%d%d:%d%d" % perm
 try:
 time_object = datetime.strptime(time_string, form).time()
 possible = True
 max_time = max(time_object, max_time)
 except: pass
if possible:
 print(max_time)
else:
 print("Impossible")

This should pass all test cases since it was literally designed to handle all cases. If it's an interview question they might want you to implement something of your own, but this is the most pythonic way I can think of.