Разбор ДЗ №2

Просьба как можно более срочно сообщать об ошибках/опечатках в случае их обнаружения. Они, очень вероятно, здесь есть по чисто статистическим соображениям.

Множество с размером

Ниже — обычный биномиальный список:

def binlist_new(): return {}

def binlist_append(d,x):
    new = [x]
    level = 0
    while level in d:
        old = d.pop(level)
        new = sorted(old + new)
        level += 1
    
    d[level] = new
    
    return d

from bisect import bisect_left, bisect_right

def binlist_count(d,x):
    total = 0
    for level in d:
        l = d[level]
        total += bisect_right(l,x) - bisect_left(l,x)
    return total
    
def binlist_size(d):
    return sum([len(d[level]) for level in d])

Требовалось поменять в нём функцию добавления элемента binlist_append так, чтобы нельзя было добавить более одного экземпляра каждого элемента. Модификация довольно тривиальна:

def binlist_append(d,x):
    if binlist_count(d, x) > 0: return d  ## вот она!

    new = [x]
    level = 0
    while level in d:
        old = d.pop(level)
        new = sorted(old + new)
        level += 1
    
    d[level] = new
    
    return d

Словарь

Просто немного изменим код предыдущей задачи. Изменения помечены комментариями.

def bindict_new(): return {}

def bindict_append(d,k,x): ## появился ключ
    if bindict_replace(d,k,x): return d
    ## вместо проверки наличия элемента сразу пытаемся его вставить

    new = [(k,x)] ## пара ключ-значение
    level = 0
    while level in d:
        old = d.pop(level)
        new = sorted(old + new)
        level += 1
    
    d[level] = new
    
    return d

## бинарный поиск приходится писать вручную (взят из материалов)
def binsearch(l, k):
    left, right = 0, len(l)
    while right - left > 1:
        m = (right + left - 1) // 2
        if l[m][0] < k: left  = m+1
        else:           right = m+1
    
    if right - left == 1 and l[left][0] == k: return left
    

def bindict_get(d,k):
    for level in d:
        haystack = d[level]
        index = binsearch(haystack, k)
        if index != None: return haystack[index][1]
        
def bindict_replace(d,k,x):
    for level in d:
        haystack = d[level]
        index = binsearch(haystack, k)
        if index != None: 
            haystack[index] = (k,x)
            return True
    
    return False

    
    
def bindict_size(d):
    return sum([len(d[level]) for level in d])

На первый взгляд реализации функций bindict_get и bindict_replace похожи друг на друга. На второй — тоже. Да и на третий... Довольно естественно их обобщить:

def bindict_act(d,k,on_success,on_failure):
    for level in d:
        haystack = d[level]
        index = binsearch(haystack, k)
        if index != None: 
            return on_success(haystack, index)
    
    return on_failure
    

def bindict_get(d,k):
    return bindict_act(d, k, lambda l,i: l[i][1], None)
    
def bindict_replace(d,k,x):
    def replace(l,i):
        l[i] = x
        return True
        
    return bindict_act(d, k, replace, False)

Функциональный ключ

Изменения ещё менее значительны: нужно лишь вычислять ключ по значению, храня вычислитель ключа вместе со структурой данных. Приведены лишь изменившиеся функции:

def bindict_new(keyfunc): return { "keyfunc": keyfunc }

def bindict_append(d,x): ## исчез ключ
    kf = d["keyfunc"]
    k  = kf(x)
    
    if bindict_replace(d,k,x): return d

    new = [(k,x)] ## пара ключ-значение
    level = 0
    while level in d:
        old = d.pop(level)
        new = sorted(old + new)
        level += 1
    
    d[level] = new
    
    return d

def bindict_act(d,k,on_success,on_failure):
    for level in d:
        if level == "keyfunc": continue ## это не уровень, а ключевая функция!
        haystack = d[level]
        index = binsearch(haystack, k)
        if index != None: 
            return on_success(haystack, index)
    
    return on_failure
    
def bindict_size(d):
    ## тут тоже не забываем про исключение ключевой функции из набора
    ## обрабатываемых данных
    return sum([len(d[level]) for level in d if level != "keyfunc"])

Динамизация суммы

Требовалось дописать функцию sum_append к данному в условии коду. Достаточно было взять общий алгоритм динамизации:

def dynfoo_append(d,k,v):
    new = foo_new( [(k,v)] )
    level = 0
    while level in d:
        old = d.pop(level)
        new = foo_new(foo_elements(old)+foo_elements(new))
        level += 1
    
    d[level] = new
    
    return d

И специализировать его:

def sum_append(s,x):  ## k,v ==> x
    new = x ## foo_new( [(k,v)] ) ==> foo_new( x ) ==> x
    level = 0
    while level in d:
        old = d.pop(level)
        new = old+new ## foo_new(foo_elements(old)+foo_elements(new))
        level += 1
    
    d[level] = new
    
    return d

Всё!

Удаление с призраками

Требовалось научить биномиальный список «удалять» свои элементы. Три из пяти функций уже приведены в условии. Осталось написать ещё две. Вот они:

## полностью аналогично spectred_size
def spectred_count(s,x):
    return binlist_count(s["main"],x) - binlist_count(s["spectre"],x)


def spectred_remove(s,x):
    binlist_append(s["spectre"],x)

    if binlist_size(s["spectre"])*2 > binlist_size(s["main"]):
        ## отсев дубликатов
        elements = set(binlist_elements(s["main"]))
        
        to_append = []
        for x in elements:
            to_append += [x]*spectred_count(s,x)
            ## каждый элемент берём столько раз, сколько он должен встречаться
        
        new = binlist_new()
        for x in to_append:
            binlist_append(new,x)

        s["main"]    = new
        s["spectre"] = binlist_new()

    return s

Удаление по ключу

Эта задача существенно проще предыдущей, если помнить об одном «но»: нельзя пересчитывать количество «трупов» при каждом удалении — это приводит к общей квадратичной зависимости многократного удаления от количества удалённых элементов (и линейной в среднем в пересчёте на один элемент).

Здесь приведём лишь интересную часть — функцию bindict_remove:

def bindict_new():
    ## счётчик количества удалённых элементов (наравне с уровнями структуры)
    return { "removed_count": 0 }

def bindict_remove(d,k):
    bindict_append(d,k,None)
    d["removed_count"] += 1

    if d["removed_count"]*2 > bindict_size(d):
        new = bindict_new()
        for k,v in [x for level in d 
                      if level != "removed_count" 
                      for x in d[level] 
                      if x[1] != None]:
            bindict_append(new,k,v)
        
        d.clear()
        
        for level in new:
            if level == "removed_count": d[level] = 0
            d[level] = new[level]

    return d

Косодвоичная система счисления

Это задание для отдыха (только почему-то никто почти этого не заметил...).

def digits(x):
    d = 1
    while d <= x:
        d = 2*d + 1
    
    result = []
    while d > 1:
        d //= 2
        result.append(x // d)
        x = x % d
        
    return result

def digits_str(digits):
    if len(digits) == 0: return "0"
    
    return "".join([str(d) for d in digits])
    
print(digits_str(digits(int(input()))))

Косодвоичная динамизация

А вот тут код уже без особых комментариев (если Вы внимательно изучили всё вышенаписанное, тут вообще всё будет знакомо):

def sum_new(): return [{},None]

def sum_append(s,x):
    d = s[0]
    if s[1] == None:
        return append_to_level(s,0,x)

    l, s[1] = s[1], None
    a,b = d.pop(l)
    return append_to_level(s,l+1,a+b+x)


def append_to_level(s,l,x):
    d = s[0]
    if l in d:
        d[l] = tuple(sorted([x,d[l]]))
        s[1] = l
    else:
        d[l] = x

    return s
    
    
def sum_total(s):
    d = s[0]
    total = 0
    for l in d:
        if type(d[l]) == tuple:
            total += sum(d[l])
        else:
            total += d[l]
    return total

def sum_levels(s):
    s = s[0]
    max_level = max(sorted(s.keys()))
    return [(s[level] if level in s else 0) 
            for level in range(max_level+1)]