Codility Frog River One

[Westerner]

Heya, I've been running through Codility challenges and came upon a snag.
This program is meant to output the shortest time (K) possible to cross the river (every integer between 0 and X + 1 is covered by a leaf); it runs at 100% correctness but fails on all performance tests.
I'm at a loss as to how to increase the speed here:

def solution(X, A) :
    K = 0
    river = list()
        #UNUSABLE-LEAVES-BE-GONE
    for leaf in range(len(A)) :
        #DUPES-BE-GONE
        if A[K] in river:
            K = K + 1
            continue
        #BUILD A BRIDGE
        else :
            river.append(A[K])
        #BRIDGE IS DONE
        if len(river) == X :
            break
        #HERE BE AN ITERATION INCREMENT
        K = K + 1
        #BRIDGE WAS SUCCESSFUL
    if K < len(A) :
        print('tick',K,'out of:',len(A) - 1)
        #BRIDGE WAS A FLOP
    else :
        print(-1)
    pass

Thanks for any tips! (:

[ndc85430]

I don't know what the task is, but a few things:

1. What's the worst case complexity for len(A)? If it's expensive, do you need to do it 3 times?

2. Remember that searching a list is linear, so doing that on each iteration of the loop (line 7) will be expensive as n grows. Does river need to be a list? If so, you might additionally want to keep the items in a set that you just use for keeping track of which items you've seen, since lookup in a set is done in constant time.

[deanhystad]

You are given a list of random numbers that represent the position of leaves falling in a river. The index of the leaf is the time when that leaf falls. For the frog to cross the river, there must be a leaf in every position. The challenge is to find the earliest time where this is true. So essentially you have a list of slots that must be filled, and the result is the index in the leaf list that fills the last slot.

Since the index of of the first leaf that completes a bridge is the value returned by the function, you cannot use set. Order must be maintained.

I am surprised that the posted code is a valid solution. From reading the description on Codality I thought the solution was supposed to return the "time", not print the time.

As for speed, there are several unnecessary and repeated function calls. I also think building a bridge list is a waste of time. At the start of the function you know how many "slots" you need to find. Can you come up with a more efficient way of recording how many "slots" have been filled that does not involve using list.append() which is known to be slow?

Think about the requirements for solving the problem.
1. You need to keep track of what "positions" are filled. Can you think of another way of doing this that is more efficient than building a list and repeatedly searching the list to see if it already contains a leaf?

2. You need a way to know when you have found a leaf for each position. Can you think of another way to do that that does not require checking the length of a list over and over and over and over and over......