Return to Revisions

Bugs

Your program produces these erroneous results:

• 0,9,5,5,5,5,5,5,5 → Impossible
2,0,5,5,5,5,5,5,5 → Impossible

  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

  The challenge states that 24:00:00 is the upper bound. The correct answer should be 22:47:44. Note that this means 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!