Учим питон (или пайтон)

[_Swetlana]

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

[Hellerick]

Задачу открыли. Вот она
https://stepik.org/lesson/1264319/step/15?unit=1278444

Видимо, только для своих открыли. Я ничего не вижу.

[_Swetlana]

Задачу открыли. Вот она
https://stepik.org/lesson/1264319/step/15?unit=1278444

Видимо, только для своих открыли. Я ничего не вижу.

Ну прям с улицы туда не зайдешь, конечно.
1. Вам нужно завести аккаунт на степике. Это очень просто - можно зайти через гугл-аккаунт или соцсеть.
https://stepik.org/
Зайдите, там огромное количество бесплатных или почти бесплатных курсов и не только по программированию, м.б. что-то понравится.
2. Выбрать курс "Поколение Python": квесты, конкурсы, марафоны, тесты и задачи"
3. Зайти в "Квест на миллион".
4. 14 задача (или 18 шаг).

[_Swetlana]

У меня, оказывается, пошёл 101-й день на степике.
Себя не похвалишь, никто не похвалит Надо подвести итоги, для поддержания собственного интереса.

 

[_Swetlana]

Задача из Поколения Пайтон. Чем-то она мне понравилась, решила сделать ее с помощью ООП.

Вам доступен текстовый файл files.txt, содержащий информацию о файлах. Каждая строка файла содержит три значения, разделенные символом пробела — имя файла, его размер (целое число) и единицы измерения:

cant-help-myself.mp3 7 MB
keep-yourself-alive.mp3 6 MB
bones.mp3 5 MB
...
Напишите программу, которая группирует данные файлы по расширению, определяя общий объем файлов каждой группы, и выводит полученные группы файлов, указывая для каждой ее общий объем. Группы должны быть расположены в лексикографическом порядке названий расширений, файлы в группах — в лексикографическом порядке их имен.

Примечание 1. Например, если бы файл files.txt имел вид:

input.txt 3000 B
scratch.zip 300 MB
output.txt 1 KB
temp.txt 4 KB
boy.bmp 2000 KB
mario.bmp 1 MB
data.zip 900 MB
то программа должна была бы вывести:

boy.bmp
mario.bmp
----------
Summary: 3 MB

input.txt
output.txt
temp.txt
----------
Summary: 8 KB

data.zip
scratch.zip
----------
Summary: 1 GB
где Summary — общий объем файлов группы.

Примечание 2. Гарантируется, что все имена файлов содержат расширение.

Примечание 3. Общий объем файлов группы записывается в самых крупных (максимально возможных) единицах измерения с округлением до целых. Другими словами, сначала следует определить суммарный объем всех файлов группы, скажем, в байтах, а затем перевести полученное значение в самые крупные (максимально возможные) единицы измерения. Примеры перевода:

1023 B -> 1023 B
1300 B -> 1 KB
1900 B -> 2 KB
Примечание 4. Значения единиц измерения такие же, какие приняты в информатике:

1 KB = 1024 B
1 MB = 1024 KB
1 GB = 1024 MB

[_Swetlana]

Вот моя первая самостоятельная ООП-программа на питоне

Код Выделить Развернуть

class File:
    all_ext = [] # список всех встретившихся расширений

    def __init__(self, name: str, ext: str, size: int, unit: str):
        self.name = name # имя файла
        self.ext = ext # расширение
        ind = Group.all_units.index(unit) # размерность ед. измерения
        self.size = size * (1024 ** ind) # размер файла в байтах
   
    @classmethod
    def add_file(cls, f):
        if f.ext not in cls.all_ext:
            cls.all_ext.append(f.ext) # добавляем новое расширение в список расширений
            g = Group(f) # создаем новую группу
            Group.add_group(g) # добавляем ее в список всех групп
        else:
            # ищем подходящую группу и добавляем туда файл
            for g in Group.all_groups:
                if g.ext == f.ext:
                    g.add_file(f)
                    break

class Group:
    all_groups = [] # список всех групп
    all_units = ['B', 'KB', 'MB', 'GB'] # единицы измериния

    def __init__(self, f: File):
        self.ext = f.ext # групповое расширени
        self.flst = [f] # список файлов
        self.size = f.size # размер группы в байтах

    # добавление файла в уже существующую группу
    def add_file(self, f: File):
        self.flst.append(f) # добавляем файл в список файлов
        self.size += f.size # размер группы в байтах
       
    # добавление группы в список всех групп
    @classmethod
    def add_group(cls, g):
        cls.all_groups.append(g)

with open('files.txt', 'r', encoding='utf-8') as my_file:
    temp = my_file.readlines()
temp = [a.strip() for a in temp]

for t in temp:
    name_ext, size, unit = t.split()
    name, ext = name_ext.split('.')
    new_file = File(name, ext, int(size), unit) # создаем файл
    File.add_file(new_file) # добавляем файл куда надо

# все сортировки
Group.all_groups = sorted(Group.all_groups, key=lambda x: x.ext)
for g in Group.all_groups:
    g.flst = sorted(g.flst, key=lambda x: x.name)

for g in Group.all_groups:
    for f in g.flst:
        print(f.name+'.'+f.ext)
    print('----------') 
    sz = g.size
    i = 0
    while sz > 1024:
        sz = sz // 1024
        i += 1               
    print(f'Summary: {round(g.size / (1024 ** i))} {Group.all_units[i]}\n')


[_Swetlana]

А вот как люди делали )) Посмотрела и подумала: чукча не читатель!

Код Выделить Развернуть

with open('files.txt', 'r', encoding='utf-8') as f:
    dfile, mem = {}, {}
    conv = {'B': 1, 'KB': 1024, 'MB': 1024 ** 2, 'GB': 1024 ** 3}
    for line in f:
        l = line.strip().split()
        dfile.setdefault(l[0].split('.')[1], []).append(l[0])
        mem[l[0].split('.')[1]] = mem.get(l[0].split('.')[1], 0) + int(l[1]) * conv[l[2]]
    for k in sorted(dfile):
        mems = [f'{round(mem[k] / conv[i])} {i}' for i in conv if 1 <= mem[k] / conv[i] < 1023.5]
        print(*sorted(dfile[k]), '-' * 10, f'Summary: {mems[0]}', sep='\n')
        print()

[Toman]

А вот как люди делали )) Посмотрела и подумала: чукча не читатель!

Ну так, даже если не брать трудночитаемые способы написания кода, ООП обычно не даёт выигрыша ни в размере, ни в трудоёмкости (а обычно даёт чистый проигрыш) в случае таких программ, размер которых позволяет их написать целиком силами одного человека или даже небольшого коллектива.

Поэтому реалистичные учебные примеры (для написания в одно лицо) на ООП, которые бы не требовали значительно больше трудозатрат для написания, чем то же самое в обычном процедурном стиле - это довольно экзотическая и малореальная штука, имхо.

[Hellerick]

Тут уместно вспомнить питоновский Дзен.

Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
Sparse is better than dense.
Readability counts.
Special cases aren't special enough to break the rules.
Although practicality beats purity.
Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.
There should be one-- and preferably only one --obvious way to do it.
Although that way may not be obvious at first unless you're Dutch.
Now is better than never.
Although never is often better than *right* now.
If the implementation is hard to explain, it's a bad idea.
If the implementation is easy to explain, it may be a good idea.
Namespaces are one honking great idea -- let's do more of those!

[_Swetlana]

Доберусь до компа, покажу, как изящно хакается задачка про функцию с константами a, b, c с помощью функции __rmul__.
ООП - сила 

[_Swetlana]

Вот оно! Переопределяем правостороннее умножение на экземпляр класса: заменяем экземпляр класса на то, что передаётся в __rmul__ в качестве сомножителя

Код Выделить Развернуть

class int(int):
    def __rmul__(self, other):
        return other * other

x = int(1)
print(magic(x, x, x))

[_Swetlana]

Вот оно! Переопределяем правостороннее умножение на экземпляр класса: заменяем экземпляр класса на то, что передаётся в __rmul__ в качестве сомножителя

Код Выделить Развернуть

class int(int):
    def __rmul__(self, other):
        return other * other

x = int(1)
print(magic(x, x, x))

Класс int тоже переопределяем.

[Hellerick]

Ни слова не понял.

[_Swetlana]

Ни слова не понял.

По условиям задачи на вход функции magic мы должны подать три целых числа, три объекта класса int.
1. Определяем свой класс-наследник от int:
class имя_класса(int):
Но функция magic ждет на вход объект типа int, поэтому называем наш класс - int. То есть переопределяем стандартный тип. В языках с динамической типизацией такие фокусы проходят.
2. Далее, наши объекты умножаются справа на числа a, b, c. Поэтому у нашего класса переопределяем правостороннее умножение так, как нам надо.
Просто супер!
P.S. Программа не моя, другого участника конкурса.

[Hellerick]

За такое котел в аду полагается.

[_Swetlana]

За такое котел в аду полагается.

В академических исследованиях нет каких-либо этических критериев. Делаю, потому что могу   

[Hellerick]

@_Swetlana
А вы не могли бы поразмыслить над практической задачей?
Я называю ее задачей линейного раскроя.
Вот нам даны, скажем 9 шестов длинной 6000 мм: `poles={6000:9}`
Их надо разрезать на палки, при этом даны длины палок и требуемые их количества: `sticks={1550:10, 1200:8, 600:12, 550:4, 300:20}`.
Требуется: Напечатать, как следует разрезать шесты на палки оптимальным образом. Примерно так: "Pole #1: 1550*3+1550*3+1200=5850".
Критерий оптимизации: список `remainders`, содержащий в себе неиспользуемые остатки каждого шеста, отсортированный в порядке убывания, должен быть как можно больше (в том смысле, в котором в питоне сравниваются два списка). То есть, надо использовать как можно меньше шестов, при этом от использованных шестов надо оставить как можно бо́льшие остатки.
Я догадываюсь, что это какая-то классическая задача на оптимизацию, но не в курсе, как такие принято решать.
Сейчас я решаю ее в полуавтоматическом режиме: скрипт на питоне подсказывает, как красиво избавляться самого большого числа самых длинных палок, а потом, комбинируя предложенные способы, я нахожу хороший общий раскрой.

[_Swetlana]

Я эту задачу на лекциях рассказывала, с точным и приближенным решением. Прям лекцию сюда выложу, обсудим.
И один товарищ в интернете меня спрашивал, как для изготовления пластиковых окон заготовки нарезать, стали кроить приближенным алгоритмом - вроде остался доволен.
А другой товарищ на хабре написал, как он одномерный раскрой делает генетическим алгоритмом. Я из лучших побуждений написала, что ГА эту задачу делать не надо, а надо вот так, и просто, и отклонение приближенного от оптимального в худшем случае небольшое, а на реальных данных вообще практически как точный работает - меня там заминусовали, как ёжика))

[_Swetlana]

Задача одномерной упаковки - классическая NP-трудная в сильном смысле задача. Что это значит.
1. NP-трудная - никто не знает, как решить её за полиномиальное время точным алгоритмом.
2. ... в сильном смысле - не решается за псевдополиномиальное время динамическим программированием.
На самом деле таких задач полно - и на производстве, и в науке. По факту на производстве чего ни коснись - конгломерат различных NP-трудных задач.
Как такие задачи решают.
а) Для малой размерности (n<= 20) лучше всего воспользоваться точным экспоненциальным алгоритмом, который называется "алгоритм с возвратом" или бэктрекинг. Алгоритмом с возвратом можно решить любую NP-трудную (полную) задачу за экспоненциальное время.
б) Если размерность средняя и задача псевдополиномиальная - то решают динамическим программированием.
в) Если задача оптимизационная (найти максимальное или минимальное решение), а размерность большая и/или задача трудная в сильном смысле - то можно действовать по-разному.
На крайних полюсах - приближенные и эвристические алгоритмы.

В чем разница между приближенным и эвристическим алгоритмом, если они оба решают задачу неточно?
I. У приближенного доказана оценка погрешности: знаем насколько наше решение может отклониться от оптимального в самом худшем случае. Найти такую оценку - доказать теорему. Тот алгоритм, которым мы будем решать задачу одномерной упаковки - FFD-алгоритм (First Fit Decreasing, первый подходящий в порядке убывания) - как раз относится к таким алгоритмам. Собственно, его можно применять к любой задаче на минимум, но именно для одномерной упаковки он поразительно хорошо работает! На очень сложных, специально сконструированных плохих примерах он отклоняется от оптимального решения не более чем на 22%. А на реальных наборах данных работает практически как точный. Для производства - самое то.
II. Эвристические алгоритмы - нам никто ничего не гарантирует. ХЗ, насколько эвристическое решение отклонится от оптимального. Пример - ГА, генетические алгоритмы - стильно, модно, молодёжно. Если соберётесь научную статью писать, в журнал посылать - берите ГА, не прогадаете 
III. Ну и третий путь, которым я часто пользовалась - гибридные алгоритмы. Пример задачи. Госзакупки, на подразделение выделяется сумма денег, ее нужно выбрать. Есть список товаров, которые нужны, известна их стоимость. Только размерность очень большая: и сумма велика, и товаров много.
Как эта задача решается гибридным алгоритмом.
Товары сортируются по убыванию стоимости. Придумывается приближенный алгоритм, который выбирает большую часть суммы, в первую очередь забирая дорогие товары. А на втором этапе начинает работать точный алгоритм: остаток суммы набирается с точностью до нескольких рублей перебором не более 20 товаров.   

[_Swetlana]

Наша задача, неформально. Имеется n одинаковых контейнеров. Вместимость может быть любая, в модельной задаче вместимость равна 1. Имеется n предметов размерами от 0 до 1, не включая 0.
Нужно упаковать предметы в минимальное число контейнеров таким образом, чтобы все предметы были упакованы, и сумма размеров предметов в одном контейнере не превосходила его вместимости, т.е. 1.

Как она решается точным алгоритмом с возвратом, когда предметов <= 20:
общее описание алгоритма с возвратом
алгоритм с возвратом для одномерной упаковки

[_Swetlana]

Ну и как задача одномерной упаковки решается FFD-алгоритмом двойным циклом за O(n²), где n - количество пакуемых предметов.
FFD-алгорит для задачи одномерной упаковки

[_Swetlana]

@_Swetlana
А вы не могли бы поразмыслить над практической задачей?
Я называю ее задачей линейного раскроя.
Вот нам даны, скажем 9 шестов длинной 6000 мм: `poles={6000:9}`
Их надо разрезать на палки, при этом даны длины палок и требуемые их количества: `sticks={1550:10, 1200:8, 600:12, 550:4, 300:20}`.
Требуется: Напечатать, как следует разрезать шесты на палки оптимальным образом. Примерно так: "Pole #1: 1550*3+1550*3+1200=5850".
Критерий оптимизации: список `remainders`, содержащий в себе неиспользуемые остатки каждого шеста, отсортированный в порядке убывания, должен быть как можно больше (в том смысле, в котором в питоне сравниваются два списка). То есть, надо использовать как можно меньше шестов, при этом от использованных шестов надо оставить как можно бо́льшие остатки.
Я догадываюсь, что это какая-то классическая задача на оптимизацию, но не в курсе, как такие принято решать.
Сейчас я решаю ее в полуавтоматическом режиме: скрипт на питоне подсказывает, как красиво избавляться самого большого числа самых длинных палок, а потом, комбинируя предложенные способы, я нахожу хороший общий раскрой.

Немножко удалила, что с телефона отправляла    Будут вопросы - пишите, обсудим. Страсть как люблю производственные оптимизационные NP-полные задачи решать   

[Hellerick]

Попытался почитать материалы по предоставленным вами ссылкам, но, честно говоря, ничего кроме неглубокой мысли, что сначала нужно постараться распределить самые большие изделия, потом -- поменьше, и надеяться, что результат получится неплохим, я не увидел.

Взял конкретный рабочий пример из своей практики: sticks = {2200: 40, 1429: 40, 680: 40, 496: 20, 450: 40, 170: 20}

Для простоты решил все шесты взять по 6000 мм: pole_length = 6000

Попросил ИИ написать мне алгоритм. Тот решил задачу напрямик:

Код Выделить Развернуть

pole_length = 6000
sticks = {2200: 40, 1429: 40, 680: 40, 496: 20, 450: 40, 170: 20}

def cut_poles(pole_length, sticks):
    stick_lengths = list(sticks.keys())
    stick_lengths.sort(reverse=True)

    cutting_plan = []
    poles_used = 0

    while any(count > 0 for count in sticks.values()):
        remaining_length = pole_length
        pole_cutting_plan = []

        for stick_length in stick_lengths:
            while remaining_length >= stick_length and sticks[stick_length] > 0:
                pole_cutting_plan.append(stick_length)
                remaining_length -= stick_length
                sticks[stick_length] -= 1

        if pole_cutting_plan:
            cutting_plan.append(pole_cutting_plan)
            poles_used += 1

    return cutting_plan, poles_used

cutting_plan, poles_used = cut_poles(pole_length, sticks)

print(f"Minimum number of poles needed: {poles_used}")
print("\nCutting Plan:")
for i, pole_plan in enumerate(cutting_plan, start=1):
    print(f"Pole {i}: {' + '.join(str(length) for length in pole_plan)} = {eval(' + '.join(str(length) for length in pole_plan))}")

Результат:

Код Выделить Развернуть

Minimum number of poles needed: 35

Cutting Plan:
Pole 1: 2200 + 2200 + 1429 + 170 = 5999
Pole 2: 2200 + 2200 + 1429 + 170 = 5999
Pole 3: 2200 + 2200 + 1429 + 170 = 5999
Pole 4: 2200 + 2200 + 1429 + 170 = 5999
Pole 5: 2200 + 2200 + 1429 + 170 = 5999
Pole 6: 2200 + 2200 + 1429 + 170 = 5999
Pole 7: 2200 + 2200 + 1429 + 170 = 5999
Pole 8: 2200 + 2200 + 1429 + 170 = 5999
Pole 9: 2200 + 2200 + 1429 + 170 = 5999
Pole 10: 2200 + 2200 + 1429 + 170 = 5999
Pole 11: 2200 + 2200 + 1429 + 170 = 5999
Pole 12: 2200 + 2200 + 1429 + 170 = 5999
Pole 13: 2200 + 2200 + 1429 + 170 = 5999
Pole 14: 2200 + 2200 + 1429 + 170 = 5999
Pole 15: 2200 + 2200 + 1429 + 170 = 5999
Pole 16: 2200 + 2200 + 1429 + 170 = 5999
Pole 17: 2200 + 2200 + 1429 + 170 = 5999
Pole 18: 2200 + 2200 + 1429 + 170 = 5999
Pole 19: 2200 + 2200 + 1429 + 170 = 5999
Pole 20: 2200 + 2200 + 1429 + 170 = 5999
Pole 21: 1429 + 1429 + 1429 + 1429 = 5716
Pole 22: 1429 + 1429 + 1429 + 1429 = 5716
Pole 23: 1429 + 1429 + 1429 + 1429 = 5716
Pole 24: 1429 + 1429 + 1429 + 1429 = 5716
Pole 25: 1429 + 1429 + 1429 + 1429 = 5716
Pole 26: 680 + 680 + 680 + 680 + 680 + 680 + 680 + 680 + 496 = 5936
Pole 27: 680 + 680 + 680 + 680 + 680 + 680 + 680 + 680 + 496 = 5936
Pole 28: 680 + 680 + 680 + 680 + 680 + 680 + 680 + 680 + 496 = 5936
Pole 29: 680 + 680 + 680 + 680 + 680 + 680 + 680 + 680 + 496 = 5936
Pole 30: 680 + 680 + 680 + 680 + 680 + 680 + 680 + 680 + 496 = 5936
Pole 31: 496 + 496 + 496 + 496 + 496 + 496 + 496 + 496 + 496 + 496 + 496 + 496 = 5952
Pole 32: 496 + 496 + 496 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 = 5988
Pole 33: 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 = 5850
Pole 34: 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 = 5850
Pole 35: 450 + 450 + 450 + 450 = 1800

Результат неплохой.

А вот решение, которое я некогда нашел вручную:

Код Выделить Развернуть

2200×2 + 680×1 + 450×2 = 5980 (20 poles)
1429×3 + 680×2 + 170×2 = 5987 (10 poles)
1429×2 + 496×6 = 5834 (3 poles)
1429×4 = 5716 (1 pole)
496×2 = 992 (1 pole)

И там, и там использовано по 35 шестов.
Разница в том, что от последнего шеста ИИ оставил 6000-1800=4200 мм, а я -- 6000-992=5008 мм.
То есть я оставил больший деловой отход, так что мое решение лучше ИИшного.
ИИ решил пять шестов разрезать по схеме 1429+1429+1429+1429=5716, оставляя 6000-5716=284 мм отхода.
На этой длине поместилась бы палка длиной 170 мм, вот только ИИ их все уже использовал в предыдущих раскроях.
Когда я кроил осмысленно, я таких ситуаций не допускаю. Я знаю, что короткие палки дают больше свободы для раскроя, и их надо беречь.

[_Swetlana]

Ну что я могу сказать. Этой неглубокой мысли соответствует доказанная теорема, что в самом худшем специально сконструированном случае FFD ошибётся на 22%, что очень неплохо для NP-hard. Более глубоких мыслей у меня нет 
Сортируйте заготовки по убыванию длины и раскладывайте по принципу "в первый подходящий".

Остатки шестов мы не максимизируем! оптимизация по одному параметру - количеству использованных шестов. Видимо, в вашем примере 35 шестов и есть оптимальное решение.

P.S. Попробую написать FFD на питоне, для тренировки.
 

[_Swetlana]

Попытался почитать материалы по предоставленным вами ссылкам, но, честно говоря, ничего кроме неглубокой мысли...

Еще одна неглубокая мысль. Оценка снизу: складываем длины всех заготовок и делим нацело 6000.
Это я сделала в питоне (вот питон и пригодился  ), получила 33.
Т.е. 33 - оценка снизу, которой явно не хватит, а 35 дает приближенный алгоритм.
Вы думаете, что какая-то очень глубокая мысль даст 34?
Можно проверить, путем точного перебора и логических рассуждений (раскидываем 40 заготовок по 2200 на 34 шеста однозначно, затем заготовки по 1429 тоже без вариантов распределяются), что для этого примера 34 недостаточно.