0

In the following code, I'm able to add the first number, but I can't add the second number. Inside the class, self correctly updates to [1, 3], but the instance stays at [1]. Why is that and how do I fix it?

from bisect import bisect
class SortedList(list):
    def __init__(self):
        self = []
    def add(self, x):
        index = bisect(self, x)
        if not self:
            self.append(x)
        else:
            self = self + [x] + self[index:] # after the second call self = [1, 3]
            pass
t = 1
for _ in range(t):
    n, a, b = 24, 3, 5
    if b == 1:
        print('yes')
    else:
        sl = SortedList() # sl = []
        st = set()
        sl.add(1) # sl = [1]
        st.add(1)
        i = 0
        while sl[i] < n: # when i == 1, there's an error because sl = [1]
            num1 = sl[i] * a # num1 = 3
            num2 = sl[i] + b
            if num1 > sl[i] and num1 not in st:
                sl.add(num1) # after this, sl = [1] still
                st.add(num1)
            if num2 > 1 and num2 not in st:
                sl.add(num2)
                st.add(num2)
            if n in st:
                break
            i += 1
        print('yes' if n in st else 'no')
Valerie Ogonor
  • 53
  • 2
  • 6
  • 1
    Assigning to `self` in `__init__` does nothing useful. – chepner Jul 03 '21 at 18:14
  • You also can't enforce the invariant that your list remains sorted without overloading every method that lets you insert an element into the list (`append`, `extend`, __setitem__`, etc) – chepner Jul 03 '21 at 18:16

3 Answers3

1
self = []
...
self = self + [x] + self[index:]

This doesn't do what you think it does. Whenever you write a = ... (without indexing on the left hand side, which is special) you don't actually change what a is. Instead, you just take whatever is on the right hand side and give it the name a, ignoring whatever a was before.

Example:

>>> a = [1, 2, 3]
>>> b = a
>>> a is b
True
>>> id(a), id(b)
(140484089176136, 140484089176136)
>>> a.append(4) # Modification.
>>> b
[1, 2, 3, 4]
>>> a = a + [5] # Modification? No! We create a new object and label it 'a'.
>>> a
[1, 2, 3, 4, 5]
>>> b
[1, 2, 3, 4]
>>> a is b
False
>>> id(a), id(b)
(140484995173192, 140484089176136)

What you want is bisect_left and to use list.insert:

index = bisect_left(li, x)
li.insert(index, x)
orlp
  • 112,504
  • 36
  • 218
  • 315
1

Don't modify self, when you assign the resulting list to self you change its reference in the local context of the function. But the remote reference keep unchanged. Better explained in Is it safe to replace a self object by another object of the same type in a method?

By sub-classing list:

import bisect

class SortedList(list):

    def append(self, x):
        if not self:
            super(SortedList, self).append(x)
        else:
            idx = bisect.bisect(self, x)
            self.insert(idx, x)

And then:

>>> import random
>>> l = SortedList()
>>> for i in range(10):
...     l.append(random.randint(0, 100))
>>> print(l)
[5, 31, 50, 58, 69, 69, 70, 78, 85, 99]

In order to keep the list sorted you should also override some magic methods such __add__, __iadd__ ...

By wrapping list:

class SortedList(object):

    def __init__(self):
        self._data = []

    def append(self, x):
        if not self:
            self._data = [x]
        else:
            idx = bisect.bisect(self, x)
            # Here you can change self._data
            # Even `insert` is better, because it don't need to copy the list
            # you can do
            self._data = self._data[:idx] + [x] + self._data[idx:]

But it's very partial, in order to have SortedList look like a list you have to implement the sequence protocol.

Balaïtous
  • 826
  • 6
  • 9
0

Thanks, everyone. I was able to get the code to work as expected by changing the class as follows:

class SortedList(list):
    def add(self, x):
        index = bisect(self, x)
        self.insert(index, x)
Valerie Ogonor
  • 53
  • 2
  • 6