CODEWITHSUNDEEP
pythonalgorithmdatedata-structurestime
mourinho
mourinho

Reputation: 783

Find the Next Closest Time in Python

I have a problem where I have to find the next closest time where a given time is in the format HH:MM.

I wrote the following algorithm:

def nextClosestTime(time):
    time = list(time)
    c = (int(time[0])*10 + int(time[1]))*60 + int(time[3])*10 + int(time[4])
    digits = [time[0],time[1],time[3],time[4]]

    diff = 24*60
    # there are 4 x 4 x 4 x 4 permutations 
    ans = []
    ans = ans + time

    one = [x for x in digits if int(x)<3]
    two = [x for x in digits]
    three = [x for x in digits if int(x)<6]
    four = [x for x in digits]

    for i in range(len(one)):
        time[0] = one[i] 
        for j in range(len(two)):
            time[1] = two[j]
            if time[0]==2 and time[1]>4:
                continue
            for k in range(len(three)):
                time[3] = three[k]
                for l in range(len(four)):
                    time[4] = four[l]                    
                    t = (int(time[0])*10 + int(time[1]))*60 + int(time[3])*10 + int(time[4])
                    if t>c and t-c< diff:
                        diff = t-c 
                        ans = time

    return "".join(x for x in ans)

print(nextClosestTime("19:34"))

However, my answer is 14:44 even though the ans gets updated only once when the time is valued at 19:39.

After that ans never gets updated as 19:39 has the minimum diff. So, why does the ans change?

It this some shallow copy or deep copy issue in python?

I thought so and thus instead of just doing ans = time while defining the variable, I did ans = [] and then ans = ans + time to initialize.

Any help would be great. Also, any better way is welcome. Thanks.

Upvotes: 0

Views: 1427

Answers (1)

trincot
trincot

Reputation: 350079

Indeed, after you have assigned time to ans you continue to change the contents of time elements. Those elements are the same as the ones you see in ans, as ans and time refer to the same list.

You need to take a copy of time when you assign it to ans:

               if t>c and t-c< diff:
                    diff = t-c 
                    ans = time[:] # take a copy

Now your function will output:

19:39

Optimisation

A more efficient algorithm would first check which is the unique list of digits, sort them and determine the position of each original digit in that sorted list.

Then, starting with the last digit, look up what the next available digit is in that sorted list. If there is one, and the resulting time is valid, return that as solution.

If it was already the last digit in the sorted list, or the resulting time is invalid, change that digit to the smallest available value (first digit in the sorted list). Then repeat the above for the remaining digits.

Code:

def nextClosestTime(time):
    digits = [int(digit) for digit in time if digit.isdigit()]
    uniques = sorted(set(digits))
    pos = [uniques.index(digit) for digit in digits]

    for i in range(3, -1, -1):
        pos[i] += 1
        if pos[i] < len(uniques):
            digits[i] = uniques[pos[i]]
            if digits[2] < 6 and digits[0]*10+digits[1] < 24:
                return "{}{}:{}{}".format(*digits)
        digits[i] = uniques[0]

    return "no solution"

print(nextClosestTime("15:56")) # 16:11

Upvotes: 2

Related Questions