[Tutor] Bounded Linear Search

[Peter Otten]

toganm at users.sourceforge.net wrote:

> Hi,
> I am trying to learn programming and python and one of the books I use has
> an exercise for "Bounded Linear Search algorithm" under the heading in
> Accumulating Unique Values at
> 
<http://homepage.mac.com/s_lott/books/nonprog/html/p08_sequence/p08_c04_list.html#list-
> exercises>
> 
> I have coded the exercises as below and what I can not figure it out is
> the code works along as spin[0] and spine[-1] are not same but when it is
> the code does not work. What am I missing ?
> 
> 
> spin=[18, 10, 2, 19, 20, 10, 2, 7, 26, 10,2,2,18]
> 
> uniq=[]
> 
> for v in spin:
>     i=0
>     uniq.append(v)
>     while uniq[i]!=v:
>         i+=1
>         if uniq[i]==v:
>             if i!=len(uniq)-1:
>                uniq.pop(-1)
> 
> print(uniq)

Consider the simple example spin = [42, 42]

First iteration of the for loop:
v = 42
i = 0
uniq = [42]
while uniq[0] != 42: # False, while loop will not be entered
    ...

Second iteration of the for loop:

v = 42
i = 0
uniq = [42, 42]
while uniq[0] != 42 # False, while loop while not be entered

The fix is to move the if ... check out of the while loop

for v in spin:
    i = 0
    uniq.append(v)
    while uniq[i] != v:
        i += 1
    # at this point uniq[i] == v is guaranteed, so we don't need the outer 
if
    if i != len(uniq) - 1:
        uniq.pop(-1) # or: del uniq[-1]

First iteration of the for loop:
v = 42
i = 0
uniq = [42]
while uniq[0] != v: # False, while loop will not be entered
if 0 != len([42]) - 1 # 0 != 0, False, last item of uniq will not be removed

Second iteration of the for loop:
v = 42
i = 0
uniq = [42, 42]
while uniq[0] != 42: # False, while loop will not be entered
if 0 != len([42, 42]) -1: # 0 != 1, True, last item of uniq will be removed

To verify that the algorithm is correct now you could walk through 
increasingly more complex sample data, which may be possible in this case, 
but rarely ever for an entire script. Instead the common approach is to pick 
a few samples along with the expected outcomes, feed them to your function 
and verify that they give the expected output

def unique_values(items):
   ...
   return uniq

assert unique_values([42, 42]) == [42]
assert unique_values([1, 2, 3, 2]) == [1, 2, 3]
...