Code Vita: Form the maximum possible time in the HH:MM:SS format using any six of nine given single digits 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] &lt; 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 &lt;= 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 &lt;= 4:
                hrs[1]=x
                seq_a.remove(x)
                break
    else:   
        for x in seq_a:
            if x &lt;= 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 &lt; 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 &lt;= 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 &lt; 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 &lt;= 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')
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 &lt;= tests for most of those loops, but &lt; 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.

    &gt;&gt;&gt; placewise_max('91210', list('02301'))
    '31200'
    &gt;&gt;&gt; placewise_max('elmo', 'abcdefghijklm')
    'elmk'
    &gt;&gt;&gt; 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 &lt;= 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!