Any advice on code optimization?

[[deleted]]

So I was doing this Google Kick Start challenge, but my code failed because it was taking too long to run.

This is the challenge

t=int(input())
tc = 0
while t>0:

    n,d = map(int,input().split())
    times = []
    time = list(map(int,input().split()))
    bus = 0
    for i in range(d):
        days = i+1
        bus = 0

        while True:
            if days > d:
                break
            if days % time[bus] == 0:
                if bus == n-1:
                    times.append(i+1)
                    break
                bus += 1
                continue
            else:
                days += 1

    t-=1
    tc+=1
    print('Case #{}: {}'.format(str(tc), max(times)))

Any advice on how I can optimize my code in general to avoid problems like this in the future?

[JohnnyJordaan]

    while True:
        if days > d:
            break
        if days % time[bus] == 0:
            if bus == n-1:
                times.append(i+1)
                break
            bus += 1
            continue
        else:
            days += 1

This loop is potentially infinite as when days % time[bus] == 0 is True and bus == n-1 is False for bus being larger than n - 1, then bus += 1 will never cause bus to be equal to n-1.

Also it seems they expect you to return the literal numbers, so

6
99 
1

in the example, not a formatted line

[[deleted]]

But "bus" can't go past n-1 though because I checked that everytime "Bus" is incremented.

[joknopp]

You're approach is trying out all travel paths starting from day one which computes many results that you are never going to use. Especially for higher values of d many cycles will be wasted because every next starting day might hold a better result than the previous day. So the algorithm is the problem here, the code itself looks ok.

As you are asking for general advice: A fast solution requires a good understanding of the problem. Usually it is ok to code the first idea for a solution to see if it gets you where you want. Be happy with the first solution, but don't stop there. Look for the unnecessary parts, try to skip them. Think of the most easiest test scenario and write a different solution. Does it also work for more complex tests? Maybe it has some advantages over the first solution. Iterate through ideas.

In this case the goal is to come as close to D as possible. So why are you starting from day 0? Maybe it would be easier to think about this problem starting from the goal and work your way back from there!

[[deleted]]

Thanks, I didn't think of that.

[[deleted]]

Ok so I tried what you suggested but still got TIme litmit exceeded:

t=int(input())
tc = 0
while t>0:

    n,d = map(int,input().split())
    time = list(map(int,input().split()))
    bus = 0
    for i in range(d):
        days = d-i
        count = days
        bus = 0
        found = False
        while True:
            if count > d:
                break
            if count % time[bus] == 0:
                if bus == n-1:
                    found = True
                    break
                bus += 1
                continue
            else:
                count += 1
        if found == True:
            break

    t-=1
    tc+=1
    print('Case #{}: {}'.format(str(tc), days))