Author: matyushkin

03
Май
2020

70 YouTube-каналов для фронтенд-разработчика

Подборка YouTube-каналов, плейлистов и подкастов, посвящённых фронтенду: вёрстка, JS, библиотеки и фреймворки, уроки и скринкасты, доклады на конференциях и записи встреч локальных сообществ. Приятного просмотра!

30
Апр
2020

Наша работа над Proglib. Апрель 2020

В конце каждого месяца мы рассказываем о работе над proglib.io, проведённой за этот период. Лучшие материалы за апрель и описание нововведений: тёмная тема, авторизация через Telegram, интерактивные статьи.

30
Апр
2020

Наша работа над Proglib. Апрель 2020✨

В конце каждого месяца мы рассказываем о работе над proglib.io, проведённой за этот период. Лучшие материалы за апрель и описание нововведений: тёмная тема, авторизация через Telegram, интерактивные статьи.

19
Апр
2020

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

Внутри поста две алгоритмические головоломки. Предложите в комментариях самое быстрое/лаконичное решение на любимом языке программирования – покажите класс!

В конце марта Библиот…

13
Апр
2020

Нейросети в помощь геймдев-художнику: машинное обучение для создания игрового пиксель-арта

О том, как генеративно-состязательные нейросети с Pix2Pix-архитектурой помогают художникам ускорить создание игрового дизайна.

Приведённые на заголовочной картинке спрайты взяты …

25
Мар
2020

Суперподборка: более 70 бесплатных русскоязычных онлайн-курсов по IT-специальностям

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

Пандемия COV…

29
Фев
2020

Наша работа над Proglib. Февраль 2020

Что сделала команда Библиотеки программиста для своих читателей за второй месяц 2020 года. Рассказываем о телеграм-боте для мероприятий, головоломках, топовых публикациях и новом тесте.

19
Фев
2020

Обыграй Сфинкса: логическая головоломка о разрезании лестниц

При каком числе квадратов в основании «лестницы» она может быть разрезана на фигуры тримино? Описание задачи подробнее – внутри поста.

Условие задачи

Вы – расхититель гробниц. Нужно пройти над пропастью по лестнице, охраняемой Сфинксом. Как водится, Сфинкс задает загадку. Решите задачу неверно – и лестница провалится в пропасть, когда вы по ней пойдете.

Условие задачи. Строительными блоками лестницы являются балки с квадратным сечением, соединенные по три таким образом, что срез имеет форму тримино (как у правой фигуры на рисунке). Для каких n можно составить лестницу из таких тройных блоков, если n – число квадратных балок в ее основании? На рисунке приведено поперечное сечение лестницы для n = 8.

Другими словами, какие лестничнообразные фигуры с основанием из n квадратов можно разрезать нацело на тримино?

Подсказка

Попробуйте решить задачу для n, равных 3, 5, 6, 9, а далее – обобщить результаты.

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

Эта задача – пятнадцатый эпизод нашего сериала головоломок. После описания задачи идёт ответ на предыдущую – алгоритмическую задачу о прыгающих лягушках. Ответ и новая задача будут опубликованы в 14:00 в субботу.

***

Решение алгоритмической задачи о лягушках

Если вы не решали эту задачу, прежде чем читать приведенный ниже текст, прочитайте условие и попробуйте решить самостоятельно!

Решение. Движение лягушки сводится либо к прыжку через лягушку противоположного вида, либо к переходу лягушки на соседнюю пустую клетку. Таким образом, если мы найдем общее количество прыжков и переходов, мы узнаем общее количество ходов.

Прыжок – единственный способ, которым лягушки противоположного вида могут преодолеть друг друга. Мы сталкивались с этим ранее в предыдущих задачах: получается, что для того, чтобы преодолеть друг друга, им необходимо совершить n2 прыжков в случае n настоящих и n виртуальных лягушек.

Сдвиг. Рассмотрим далее ситуацию для лягушек одного вида. Мы знаем, что они не могут перепрыгивать друг через друга. Первая лягушка переместится на n + 1 клеток и окажется в ячейке n + 2, вторая лягушка передвинется на n + 1 клеток до ячейки n + 3, и т. д. Чтобы оказаться в нужной позиции, вместе все лягушки одного вида должны переместиться на n (n + 1) клеток. Аналогично должны сделать их виртуальные аналоги. То есть все эти реальные и виртуальные земноводные переместятся на 2 n (n + 1) клеток. Поскольку один прыжок охватывает две ячейки, и их n2, количество сдвигов должно составить 2n (n + 1) – 2n2 = 2n.

Алгоритм. Существует два симметричных алгоритма для решения головоломки: один начинается со сдвига крайней к пустой ячейки настоящей лягушки, другой – со сдвига виртуальной. Опишем первый. Алгоритм может быть получен методом грубой силы: его ходы определены однозначно, потому что альтернативные ходы приводят к очевидным тупиковым ситуациям. В частности, когда есть выбор между сдвигом и прыжком, должен быть сделан прыжок.

Ниже приведены алгоритмы для n = 2 и n = 3 соответственно. Настоящие лягушки обозначены T, виртуальные – F.

Решение для n = 2
            1 TT_FF 
2 T_TFF
3 TFT_F
4 TFTF_ 
5 TF_FT 
6 _FTFT
7 F_TFT
8 FFT_T
. FF_TT
        
Решение для n = 3
            1  TTT_FFF
2  TT_TFFF
3  TTFT_FF
4  TTFTF_F
5  TTF_FTF
6  T_FTFTF
7  _TFTFTF
8  FT_TFTF
9  FTFT_TF
10 FTFTFT_
11 FTFTF_T
12 FTF_FTT
13 F_FTFTT
14 FF_TFTT
15 FFFT_TT
.  FFF_TTT
        

Головоломка может быть легко обобщена на случай с m и n лягушками разных видов. Общее количество необходимых ходов равно mn + m + n, из которых mn – количество прыжков, а m + n – число сдвигов.

Ответ: для 3 лягушек с каждой стороны достаточно 15 ходов.

Ответ на вопрос со звёздочккой: Для m и n лягушек достаточно mn + m + n ходов.

Как ответили читатели Библиотеки программиста? Сам ответ о числе переходов первым дал пользователь wil4, но без указания решения:

15 для n=3

Первым ответ с решением, но с чуть большим числом ходов дал пользователь mr.fantazylight:


В комментариях к решению задачи мы обсудили, откуда берутся два лишних хода.

Программное решение, находящее алгоритм для любого m и n, реализовал на С++ пользователь krotbsod. Вот пример для m = 3 и n = 5:


Автор решения krotbsod будет рад получить комментарии относительно кода: https://pastebin.com/Qm3Ru08L.

            #include <iostream>
#include <cstring>
 
using namespace std;
 
//!!! P.S. Некоторые проверки в программе не выполняются, для упрощения восприятия
 
/**
 * @brief Генерируем лягушек
 * @param frogs Указатель на массив с лягушками [m + n + 1] размерности
 * @param m T лягушек
 * @param n F лягушек
 **/
void generateFrogs(char *frogs, const int m , const int n) {
    int count = m + n + 1;
    memset(frogs, ' ', count);
 
    for(int i = 0; i < m; i++) {
        frogs[i] = 'T';
    }
    for(int i = m + 1; i < count; i++) {
        frogs[i] = 'F';
    }
}
 
/**
 * @brief Заданные шаблоны поведения лягушек возле свободной ячейки
 */
struct Patterns{
public:
 
    // T1 <-- Цифра - количество шагов
    // ^
    // |
    // Символ - тип лягушки
    /**
     * @brief Задаем шаблоны в конструкторе структуры и записываем указатели в m_list
     */
    Patterns() {
        m_list[0] = "TF FT"; // T2
        m_list[1] = "FT TF"; // F2
 
        m_list[2] = "FF FT"; // F1
        m_list[3] = "TT TF"; // F2
 
        m_list[4] = "FF TF"; // F2
        m_list[5] = "TT FT"; // T1
 
        m_list[6] = "TF FF"; // T2
        m_list[7] = "FT TT"; // T1
 
        m_list[8] = "FT FF"; // F1
        m_list[9] = "TF TT"; // T2
 
        m_list[10] = "FT FT"; // F1 or T1
        m_list[11] = "TF TF"; // lock
 
        m_list[12] = "TT FF"; // F1 or T1
 
        m_list[13] = "FF FF"; // F1;
        m_list[14] = "TT TT"; // T1;
 
        m_list[15] = "FF TT"; // done
    }
    /**
     * @brief Возвращает указатель на заданный шаблон.
     * Нужна лишь для итеративного поиска.
     * @param num Номер шаблона в m_list
     * @return Указатель на заданный шаблон
     */
    const char *pattern(const int &num) {
        // Проверку не стал делать, для упрощения восприятия
        return m_list[num];
    }
    /**
     * @brief Возвращает число шаблонов
     * @return Число шаблонов
     */
    int size() {
        return m_size;
    }
 
private:
    static const int m_size = 16;
    // Массив с указателями на массивы шаблонов
    const char *m_list[m_size];
 
} frog_patterns;
 
/**
 * @brief Получение текущего состояния (шаблона) в массиве с лягушками
 * @param currentPattern Указатель на формируемый массив для записи в него шаблона
 * @param frogs Указатель на массив с лягушками
 * @param count Размер массива с лягушками
 * @param iter Текущее положение пробела
 */
void getCurrentPattern(char *currentPattern, char *frogs, const int &count, const int &iter) {
    //Задаем шаблон текущего положения для последующего сравнения с заданными шаблонами
    memcpy(currentPattern, &frogs[iter - 2], 5); // dangerous !!! Опасно, выходим за рамки заданного массива. Но работает
 
    // Задаем МНИМЫХ лягушек в текущий шаблон для последующего сравнения с заданными шаблонами.
    // Когда символ пробела находится с краю, например: 'FF |' или '|T FF'  (где | край массива)
    // То приходим в несколько неодназначную ситуацию.
    // Проще всего этого избежать добавив МНИМЫХ лягушек в шаблон для сравнения.
    // Для конечных точек характеры следующие МНИМЫЕ лягушки:   Для начального положения(крайнего левого предела) характерна мнимая F
    //                                                          Для последнего положения(крайнего правого предела) характерна мнимая T
    // P.S. МНИМЫЕ лягушки на то и мнимые, они ни как не дополняют исходный массив, они лишь заполняют шаблон для сравнения.
 
    if(iter == 0) {
        currentPattern[0] = 'F';
        currentPattern[1] = 'F';
    }
    if(iter == 1) {
        currentPattern[0] = 'F';
    }
    if(iter == (count - 1)) {
        currentPattern[3] = 'T';
        currentPattern[4] = 'T';
    }
    if(iter == (count - 2)) {
        currentPattern[4] = 'T';
    }
}
 
/**
 * @brief Перемещение лягушки на место пустой ячейки
 * @param frogs Указатель на массив с лягушками
 * @param iter Текущее положение пробела
 * @param type Тип лягушки
 * @param step Шаг для перемещения лягушки
 */
void moveFrog(char *frogs, const int &iter, const char &type, const int &step) {
    if(type == 'F') {
        frogs[iter] = frogs[iter + step];
        frogs[iter + step] = ' ';
    }
    if(type == 'T') {
        frogs[iter] = frogs[iter - step];
        frogs[iter - step] = ' ';
    }
}
 
/**
 * @brief Основной цикл сравнения состояний
 * @param frogs Указатель на массив с лягушками
 * @param m T лягушек
 * @param n F лягушек
 * @param iter Текущее положение пробела
 * @return Возвращает 1, если перемещение всех лягушек завершено. В остальных случаях 0.
 */
int move(char *frogs, const int &m , const int &n, const int &iter) {
    int count = m + n + 1;
 
    char currentPattern[5];
    memset(currentPattern, ' ', 5);
    getCurrentPattern(currentPattern, frogs, count, iter);
 
    // Проходим по всем заданным шаблонам
    for(int i = 0; i < frog_patterns.size(); i++) {
        // Сравниваем
        int rescmp = memcmp(currentPattern, frog_patterns.pattern(i), 5);
        if(rescmp == 0) {
            // При совпадении перемещаем
            switch (i) {
            case 0:
                moveFrog(frogs, iter, 'T', 2); // T2
                break;
            case 1:
                moveFrog(frogs, iter, 'F', 2); // F2
                break;
            case 2:
                moveFrog(frogs, iter, 'F', 1); // F1
                break;
            case 3:
                moveFrog(frogs, iter, 'F', 2); // F2
                break;
            case 4:
                moveFrog(frogs, iter, 'F', 2); // F2
                break;
            case 5:
                moveFrog(frogs, iter, 'T', 1); // T1
                break;
            case 6:
                moveFrog(frogs, iter, 'T', 2); // T2
                break;
            case 7:
                moveFrog(frogs, iter, 'T', 1); // T1
                break;
            case 8:
                moveFrog(frogs, iter, 'F', 1); // F1
                break;
            case 9:
                moveFrog(frogs, iter, 'T', 2); // T2
                break;
            case 10:
                moveFrog(frogs, iter, 'F', 1); // F1 or T1
                break;
            case 12:
                if((m % 2) == 0) {
                    moveFrog(frogs, iter, 'T', 1);
                } else {
                    moveFrog(frogs, iter, 'F', 1);
                }
                //moveFrog(frogs, iter, 'F', 1); // F1 or T1 //if m is even use T1
                break;
            case 13:
                moveFrog(frogs, iter, 'F', 1);
                break;
            case 14:
                moveFrog(frogs, iter, 'T', 1);
                break;
            case 15:
                return 1;
                break;
            }
        }
    }
    return 0;
}
 
/**
 * @brief Запуск цикла алгоритма
 * @param m T лягушек
 * @param n F лягушек
 */
void jumpAlg(const int m , const int n) {
    int count = m + n + 1;
    char frogs[count + 1];      // +1 чтобы добавить символ \0 в конец, для корректного вывода через printf
    frogs[count] = '\0';        // тут и добавим
    generateFrogs(frogs, m, n); // Генерируем массив с лягушками
 
    int counter = 0;
    while(true) {
        printf("%s\n", frogs);
        int ret = 0;
        for(int iter = 0; iter < count; iter++) {
            // При нахождении пробела, входим в Основной цикл сравнения состояний
            if(frogs[iter] == ' ') {
                ret = move(frogs, m, n, iter);
                break;
            }
        }
        if(ret == 1) {
            printf("Count steps: %d\n", counter);
            break;
        }
        counter++;
    }
}
 
int main()
{
    //
    // T, F
    jumpAlg(3, 5);
    return 0;
}
        

Спасибо, что присылаете в комментарии свои ответы и решения!

15
Фев
2020

Прыг-прыг. Алгоритмическая головоломка о лягушках

За сколько ходов лягушки обменяются местами? Лягушки прыгают по очереди на пустую клетку, когда та рядом или через одну лягушку противоположного цвета. Подробнее – в тексте публикации.

Условие задачи

Как вы могли заметить по логотипу, Библиотеке программиста нравятся лягушки 🐸. Как настоящие (T), так и игрушечные (F). Однажды мы наблюдали такую сценку. На одномерной доске с 2n + 1 ячейками в первых n ячейках разместились n истинных лягушек в n первых ячейках и n лягушек-игрушек в последних n ячейках. По одной лягушке в ячейке, и ещё одна ячейка, разделяющая семейства. На рисунке показан случай для n = 3.

T и F делают ходы по очереди. В рамках хода лягушка прыгает на пустую клетку. Напрямик или перепрыгнув через представителя противоположного семейства. Через своих сородичей лягушки одного типа не прыгают, это считается неуважительным. Трушные лягушки двигаются только вправо, фейковые – влево. В результате перепрыгиваний они хотят обменяться местами, как на картинке.

Вопрос: сколько ходов потребуется для 3 T и 3 F? Предложите алгоритм решения задачи.

Вопрос со звёздочкой 🌟: сколько ходов нужно для m T и n F, если m и n не равны?

Программное решение✨: попробуйте реализовать визуализацию решения для общего случая (из вопроса со звёздочкой) на любимом языке программирования. Напишите функцию, которая принимает на вход числа m и n, а возвращает число ходов, а также последовательность строк, содержащих T, F и пробел для пустой ячейки. Каждая строка соответствует одном ходу.

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

Эта задача – четырнадцатый эпизод нашего сериала головоломок. После описания задачи идёт ответ на предыдущую – задачу о взломе банковского замка. Ответ и новая задача будут опубликованы в 14:00 в среду.

***

Решение задачи о взломе банковского замка

Ответ: 85.

Решение. Решим задачу в общем случае, то есть для любого числа n. Пронумеруем переключатели слева направо от 1 до n и обозначим состояния переключателя «включено» и «выключено» соответственно как 1 и 0. Чтобы помочь себе в решении общего случая головоломки, начнём с решения четырёх самых простых примеров.


Теперь рассмотрим общий пример головоломки, когда исходная строка состоит из n единиц:

111, ... , 1.

Прежде чем мы сможем выключить самый левый переключатель, переключатели должны находиться в состоянии

110, ... , 0.

Следовательно, для начала нам нужно отключить последние n – 2 переключателей и сделать это за минимальное количество ходов. Другими словами, мы должны сначала решить ту же проблему, что и для последних n – 2 переключателей. Это может быть сделано рекурсивно с использованием решений для случаев n = 1 и n = 2.

После этого мы сможем переключить первый переключатель, чтобы получить

010, ... , 0.

Теперь, прежде чем мы сможем переключить второй переключатель, нам придётся пройти через такое состояние, при котором все переключатели, следующи за ним будут «вкл». Перевести все переключатели с третьего по последний на «вкл» можно, поменяв последовательность ходов, сделанных ранее, на обратную, чтобы переключить последние n – 2 переключателей из положения «вкл» в положение «выкл». Это даст нам

011, ... , 1.

Обозначим M(n) количеством переключений, сделанных алгоритмом. Получится следующее рекуррентное выражение:

или сокращённо:

для

Решение рекуррентного уравнения по стандартной методике для линейных неоднородных рекуррентных уравнений второго порядка с постоянными коэффициентами даёт следующий необычный результат:

для

Для чётных n данная формула сводится к

Для нечётных:

Действительно: если n = 7, то M(n) = 85.

Как ответили читатели Библиотеки программиста? Алгоритмические ответы с указанием рекуррентных соотношений дали читатели lasangqwerty и maximzombi:

f(n) = f(n-1) + 2*f(n-2) + 1, f(7) = 85
Посчитаем ответ для случая с 1 и 2 тумблерами: f(1)=1 f(2) = 2 Пусть тумблеров n штук. Чтобы выключить самый левый, нужно, чтобы (n-1)-ый тумблер слева остался вкл, а остальные выкл. Чтобы выключить n-2 левых, нужно f(n-2) переключений. Также нужно переключить сам левый тумблер (т.е. еще одно переключение). Итого этими действиями мы привели тумблеры к виду: 0100…00, где 1 – вкл, 0 – выкл Чтобы выключить (n-1)-й тумблей, нужно включить все тумблеры правее него(т.е. нужно включить только (n-2)-й тумблер, но для его включения нужно включить (n-3)-й тумблей и т.д.). Чтобы включить все тумблеры правее (n-1)-го, необходимо также f(n-2) действий. Теперь тумблеры имеют вид 0111…11 Осталось перевести все тумблеры левее самого левого в режим выкл., на что понадобится f(n-1) действий. Итого получаем рекуррентную формулу: f(1)=1, f(2)=2, f(n)=f(n-2) * 2 + f(n-1) + 1 => f(7) = 85

Читатель wil4 привёл саму последовательность переключений:

1111111 1111110 1111010 1111011 1111001 1111000 1101000 1101001 1101011 1101010 1101110 1101111 1101101 1101100 1100100 1100101 1100111 1100110 1100010 1100011 1100001 1100000 0100000 0100001 0100011 0100010 0100110 0100111 0100101 0100100 0101100 0101101 0101111 0101110 0101010 0101011 0101001 0101000 0111000 0111001 0111011 0111010 0111110 0111111 0111101 0111100 0110100 0110101 0110111 0110110 0110010 0110011 0110001 0110000 0010000 0010001 0010011 0010010 0010110 0010111 0010101 0010100 0011100 0011101 0011111 0011110 0011010 0011011 0011001 0011000 0001000 0001001 0001011 0001010 0001110 0001111 0001101 0001100 0000100 0000101 0000111 0000110 0000010 0000011 0000001 0000000

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

85, рекуррентно, для включения четного тумблера надо повторить все предыдущие переключения, для нечетного еще одно, a(2n) = 2*a(2n-1), a(2n+1) = 2*a(2n)+1
12
Фев
2020

Как ограбить банк? Логическая задача

Эту задачу трудно решить аналитически… Но можно попробовать сделать это хотя бы программно. Смогли бы вы вскрыть необычный банковский замок?

Условие задачи

09
Фев
2020

Рисуем, программируя. Машинная генерация художественных узоров в векторных полях

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

08
Фев
2020

Карточная головоломка Конвея

Алгоритмическая задача об одиночной карточной игре. Головоломка придумана известным британским математиком Джоном Х. Конвеем.

Условие задачи

04
Фев
2020

Python и динамическое программирование на примере задачи о рюкзаке

Как собрать ценные вещи в поездку так, чтобы хватило места? Без избыточной терминологии рассказываем о классической задаче, решаемой методом динамического программирования.

Момент настал – вы переезжаете в Сан-Франциско, чтобы стать известным дата сайентистом. Будете работать в крупной компании и скоро прославитесь. Но не всё сразу. Поначалу придётся ютиться в жилище, много меньшем, чем нынешний дом. Нужно решить, что взять с собой. Вы аналитик и намерены решить задачу эффективно. Обсудим алгоритм?

Описание проблемы

Представим, что на данный момент вы живёте в довольно большой квартире площадью 100 м2, а вещи занимают 50 м2. Вы знаете, что площадь нового жилья составит 40 м2 и хотите, чтобы вещи занимали не более 20 м2. Вы любите, когда на полу есть свободное место, да и не всё можно поставить впритык друг к другу. Нужно составить список вещей, определить площадь, занимаемую каждой вещью и составить рейтинг ценности предметов. Конечная цель – максимизировать материальную ценность того, что разместится на 20 квадратных метрах.

Перечисляем предметы

Вы составили список вещей и выразили занимаемую площадь в квадратных дециметрах (1 дм2 = 0.01 м2). Каждому предмету сопоставили ценность по шкале от 0 до 100. Получилась сводка данных о 29 предметах, которую можно оформить как словарь вида {'название предмета':(площадь, ценность) }:

            stuffdict = {'couch_s':(300,75), 
             'couch_b':(500,80), 
             'bed':(400,100), 
             'closet':(200,50), 
             'bed_s':(200,40), 
             'desk':(200,70), 
             'table':(300,80),
             'tv_table':(200,30),
             'armchair':(100,30),
             'bookshelf':(200,60), 
             'cabinet':(150,20),
             'game_table':(150,30),
             'hammock':(250,45),
             'diner_table_with_chairs':(250,70),
             'stools':(150,30),
             'mirror':(100,20),
             'instrument':(300,70),
             'plant_1':(25,10),
             'plant_2':(30,20),
             'plant_3':(45,25),
             'sideboard':(175,30),
             'chest_of_drawers':(25,40),
             'guest_bed':(250,40),
             'standing_lamp':(20,30), 
             'garbage_can':(30,35), 
             'bar_with_stools':(200,40), 
             'bike_stand':(100,80),
             'chest':(150,25),
             'heater':(100,25)
            }
        

Готово! Теперь видно, что кровать ('bed') занимает 400 дм2, а её ценность составляет 100, игровой стол ('game_table') занимает 150 дм2 квадратных метра и имеет ценность 30.

Максимазация ценности

Как максимизировать суммарную ценность объектов так, чтобы суммарная площадь не превышала 2000 дм2? Можно попробовать перебрать все возможные комбинации и рассчитать суммарную ценность для каждой из комбинаций. Решение получится, если выбрать максимальную суммарную ценность для 2000 дм2. Но вот незадача: и комбинаторика, и теория множеств утверждают, что 29 предметов дают 2²⁹ возможных комбинаций выбора предметов.

То есть более 536 миллионов. Похоже, такой перебор займёт некоторое время. Нельзя ли быстрее?

Стоит подумать о других вариантах. Что если начать с наиболее ценного предмета, затем следующего за ним по ценности, и так до тех пор, пока не заполнятся 20 квадратных метров? Такой алгоритм явно быстрее. Но даст ли он оптимальное решение? Есть сомнения. Как быстро решить задачу и найти лучшее решение?

Примечание: описанные выше случаи соответствуют полному перебору (метод «грубой силы», англ. brute force) и жадному (англ. greedy) алгоритму.

***

Динамическое программирование

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

К счастью, знакомый слышал об этом классе задач и подсказал вам более разумный способ справиться с проблемой. Он объяснил, что можно рекурсивно разделить проблему на более мелкие подзадачи. Сохраняя результаты в ячейках таблицы мемоизации и используя их на следующих итерациях, вы быстро найдёте оптимальное решение. Вы как бы обменяете программную память на время. То есть воспользуетесь методом динамического программирования.

Этапы решения задачи с помощью динамического программирования

  1. Создаём словарь со списком элементов и их параметрами (площадь, ценность).
  2. Создаём списки значений площади и ценности.
  3. Используем списки для построения таблиц мемоизации.
  4. Получаем элементы из последней строки таблицы. Последняя строка таблицы мемоизации содержит оптимальное решение. Возможно, существует несколько оптимальных решений. Например, когда есть два предмета с одинаковой площадью и стоимостью или ряд предметов имеют суммарные площадь и ценность, как у другого предмета.

Рассмотрим, как реализовать этот план на практике. Первый шаг мы предусмотрительно выполнили ранее, перейдём ко второму.

Создаём списки значений площади и ценности

Разделяем списки значений исходного словаря, например, так:

            def get_area_and_value(stuffdict):
    area = [stuffdict[item][0] for item in stuffdict]
    value = [stuffdict[item][1] for item in stuffdict]        
    return area, value
        

Используем списки для мемоизации

Пусть n – общее число предметов, A – их максимально допустимая суммарная площадь в новом жилище (2000 дм2). Составим таблицу из n + 1 строк и A + 1 столбцов. Строки пронумеруем индексом i, столбцы – индексом a (чтобы помнить что в столбцах площадь, area). То есть в качестве номеров столбцов мы рассматриваем дискретные значения площади, отличающиеся друг от друга на 1.

            def get_memtable(stuffdict, A=2000):
      area, value = get_area_and_value(stuffdict)
      n = len(value) # находим размеры таблицы
      
      # создаём таблицу из нулевых значений
      V = [[0 for a in range(A+1)] for i in range(n+1)]

      for i in range(n+1):
            for a in range(A+1):
                  # базовый случай
                  if i == 0 or a == 0:
                        V[i][a] = 0

                  # если площадь предмета меньше площади столбца,
                  # максимизируем значение суммарной ценности
                  elif area[i-1] <= a:
                        V[i][a] = max(value[i-1] + V[i-1][a-area[i-1]], V[i-1][a])

                  # если площадь предмета больше площади столбца,
                  # забираем значение ячейки из предыдущей строки
                  else:
                        V[i][a] = V[i-1][a]       
      return V, area, value
        

Вначале создаётся и заполняется таблица в виде вложенных списков. Нулевую строку и нулевой столбец заполняем нулями. Это базовый случай: когда площадь или количество элементов равны нулю, значение ячейки равно нулю. Далее таблица значений V будет заполняться строка за строкой слева направо и сверху вниз:


Если площадь текущего элемента меньше или равна площади (номеру столбца) текущей ячейки, вычисляем значение ячейки следуя правилу:

            V[i][a] = max(value[i-1] + V[i-1][a-area[i-1], V[i-1][a])
        

То есть выбираем максимальное из двух значений:

  1. Сумма ценности текущего предмета value[i-1] и величины элемента из предыдущей строки i-1 с площадью, меньшей на величину площади текущего предмета area[i-1]. Обратите внимание: нужно помнить, что элементы в таблице отличаются по нумерации на единицу из-за нулевой строки.
  2. Значение элемента предыдущей строки с той же площадью, то есть из того же столбца, что текущая ячейка. То же значение устанавливается в случае, если площадь текущей ячейки меньше, чем площадь текущего элемента (см. блок else)

За счёт такого подхода при одной и той же суммарной площади элементов происходит максимизация суммарной ценности.

Забираем нужные элементы из последней строки таблицы

Найдём набор предметов с максимальной суммарной ценностью для указанной возможной площади. Начнём с нижнего правого угла таблицы с максимальным значением, и соберём предметы:

            def get_selected_items_list(stuffdict, A=2000):
      V, area, value = get_memtable(stuffdict)
      n = len(value)
      res = V[n][A]      # начинаем с последнего элемента таблицы
      a = A              # начальная площадь - максимальная
      items_list = []    # список площадей и ценностей
    
      for i in range(n, 0, -1):  # идём в обратном порядке
            if res <= 0:  # условие прерывания - собрали "рюкзак" 
                  break
            if res == V[i-1][a]:  # ничего не делаем, двигаемся дальше
                  continue
            else:
                  # "забираем" предмет
                  items_list.append((area[i-1], value[i-1]))
                  res -= value[i-1]   # отнимаем значение ценности от общей
                  a -= area[i-1]  # отнимаем площадь от общей
            
      selected_stuff = []

      # находим ключи исходного словаря - названия предметов
      for search in items_list:
            for key, value in stuffdict.items():
                  if value == search:
                        selected_stuff.append(key)
            
      return selected_stuff
        

Итак, мы нашли список:

            >>> stuff = get_selected_items_list(stuffdict)
>>> print(stuff)
['bike_stand', 'garbage_can', 'standing_lamp', 'chest_of_drawers',
'plant_3', 'plant_2', 'diner_table_with_chairs', 'bookshelf',
'armchair', 'table', 'desk', 'bed', 'couch_s']
        

Проверим суммарные площадь и ценность собранных предметов:

            >>> totarea = sum([stuffdict[item][0] for item in stuff])
>>> totvalue = sum([stuffdict[item][1] for item in stuff])
>>> print(totarea)
2000
>>> print(totvalue)
715
        

Получилось! Собираем вещи и отправляемся в путь (звучит песня Mamas & Paps – San Francisco).

***

Бонус: Тепловая карта таблицы

Тепловая карта ниже отображает рассмотренную выше таблицу. По оси абсцисс отложена доступная площадь, по оси ординат – список предметов. Цветовая шкала соответствует суммарной ценности. Можно видеть, как значения возрастают по мере продвижения по таблице снизу вверх.


Для построения использовалась библиотека matplotlib:

            def plot_memtable(V, stuffdict):
    plt.figure(figsize=(30,15))
    item_list = list(stuffdict.keys())
    item_list.insert(0, 'empty')
    sns.heatmap(V, yticklabels=item_list)
    plt.yticks(size=25)
    plt.xlabel('Area', size=25)
    plt.ylabel('Added item', size=25)
    plt.title('Value for Area with Set of Items', size=30)
    plt.show()
        

А тем, кто следит за нашим сериалом головоломок, динамическое программирование также поможет решить текущую задачу (головоломку о беглеце).

02
Фев
2020

Что нового будет в C# 9?

Предупреждён — значит вооружён. Обсуждаем предлагаемые нововведения, которые могут коснуться разработчиков в девятой версии С#.

Следующим релизом C# станет С# 9. В плане развития…

01
Фев
2020

Задача о беглеце

Новая головоломка о спасении заключённого и подробно иллюстрированный ответ на решение задачи о шести шахматных конях.

Условие задачи о беглеце

29
Янв
2020

Rough.js: как заставить компьютер рисовать «от руки»

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

Rough.js – небольшая графическая библиотека (< 9 кБ в gzip), позволяющая рисовать на JavaScript в скетчевом стиле, то есть получать графику, как бы сделанную от руки. Пакет определяет примитивы для рисования линий, кривых, дуг, многоугольников, кругов и эллипсов.

В середине января вышла версия 4.0. В этой публикации мы постараемся обединить известные данные и нововведения.

Rough.js работает как с Canvas, так и с SVG.

Установка

Устанавливаем Rough.js из менеджера пакетов:

            npm install --save roughjs
        

Используем в коде:

            import rough from 'roughjs';
        

Примеры использования

Полная документация API Rough.js доступна на Github. Приведём сначала несколько простых примеров графических элементов и кода, с помощью которого они были получены.

Прямоугольник


            const rc = rough.canvas(document.getElementById('canvas'));
rc.rectangle(10, 10, 200, 200); // x, y, ширина, высота
        

Для SVG-варианта:

            const rc = rough.svg(svg);
let node = rc.rectangle(10, 10, 200, 200); // x, y, ширина, высота
svg.appendChild(node);
        

Линии и эллипсы


            rc.circle(80, 120, 50); // centerX, centerY, диаметр
rc.ellipse(300, 100, 150, 80); // centerX, centerY, ширина, высота
rc.line(80, 120, 300, 100); // x1, y1, x2, y2
        

Заполнение


            rc.circle(50, 50, 80, { fill: 'red' }); // fill with red hachure
rc.rectangle(120, 15, 80, 80, { fill: 'red' });
rc.circle(50, 150, 80, {
  fill: "rgb(10,150,10)",
  fillWeight: 3 // thicker lines for hachure
});
rc.rectangle(220, 15, 80, 80, {
  fill: 'red',
  hachureAngle: 60, // angle of hachure,
  hachureGap: 8
});
rc.rectangle(120, 105, 80, 80, {
  fill: 'rgba(255,0,200,0.2)',
  fillStyle: 'solid' // solid fill
});
        

Стили заливки фигур могут быть следующие: обычная штриховка (по умолчанию), сплошной цвет, зигзагообразное заполнение, перекрёстная штриховка или заполнение точками.


Стиль зарисовки


            rc.rectangle(15, 15, 80, 80, { roughness: 0.5, fill: 'red' });
rc.rectangle(120, 15, 80, 80, { roughness: 2.8, fill: 'blue' });
rc.rectangle(220, 15, 80, 80, { bowing: 6, stroke: 'green', strokeWidth: 3 });
        

Рисование в формате SVG-path


            rc.path('M80 80 A 45 45, 0, 0, 0, 125 125 L 125 80 Z', { fill: 'green' });
rc.path('M230 80 A 45 45, 0, 1, 0, 275 125 L 275 80 Z', { fill: 'purple' });
rc.path('M80 230 A 45 45, 0, 0, 1, 125 275 L 125 230 Z', { fill: 'red' });
rc.path('M230 230 A 45 45, 0, 1, 1, 275 275 L 275 230 Z', { fill: 'blue' });
        

Примеры посложнее


            const rc = rough.canvas(document.getElementById('canvas'));

//line and rectangle
rc.rectangle(10, 10, 100, 100);
rc.rectangle(140, 10, 100, 100, {
  fill: 'rgba(255,0,0,0.2)',
  fillStyle: 'solid',
  roughness: 2
});
rc.rectangle(10, 130, 100, 100, {
  fill: 'red',
  stroke: 'blue',
  hachureAngle: 60,
  hachureGap: 10,
  fillWeight: 5,
  strokeWidth: 5
});

// ellipse and circle
rc.ellipse(350, 50, 150, 80);
rc.ellipse(610, 50, 150, 80, {
  fill: 'blue'
});
rc.circle(480, 50, 80, {
  stroke: 'red', strokeWidth: 2,
  fill: 'rgba(0,255,0,0.3)', fillStyle: 'solid'
});

//overlapping circles
rc.circle(480, 150, 80, {
  stroke: 'red', strokeWidth: 4,
  fill: 'rgba(0,255,0,1)', fillWeight: 4, hachureGap: 6
});
rc.circle(530, 150, 80, {
  stroke: 'blue', strokeWidth: 4,
  fill: 'rgba(255,255,0,1)', fillWeight: 4, hachureGap: 6
});

// linearPath and polygon
rc.linearPath([[690, 10], [790, 20], [750, 120], [690, 100]], {
  roughness: 0.7,
  stroke: 'red', strokeWidth: 4
});
rc.polygon([[690, 130], [790, 140], [750, 240], [690, 220]]);
rc.polygon([[690, 250], [790, 260], [750, 360], [690, 340]], {
  stroke: 'red', strokeWidth: 4,
  fill: 'rgba(0,0,255,0.2)', fillStyle: 'solid'
});
rc.polygon([[690, 370], [790, 385], [750, 480], [690, 460]], {
  stroke: 'red',
  hachureAngle: 65,
  fill: 'rgba(0,0,255,0.6)'
});

// arcs
rc.arc(350, 200, 200, 180, Math.PI, Math.PI * 1.6);
rc.arc(350, 300, 200, 180, Math.PI, Math.PI * 1.6, true);
rc.arc(350, 300, 200, 180, 0, Math.PI / 2, true, {
  stroke: 'red', strokeWidth: 4,
  fill: 'rgba(255,255,0,0.4)', fillStyle: 'solid'
});
rc.arc(350, 300, 200, 180, Math.PI / 2, Math.PI, true, {
  stroke: 'blue', strokeWidth: 2,
  fill: 'rgba(255,0,255,0.4)'
});

// draw sine curve
let points = [];
for (let i = 0; i < 20; i++) {
  // 4pi - 400px
  let x = (400 / 20) * i + 10;
  let xdeg = (Math.PI / 100) * x;
  let y = Math.round(Math.sin(xdeg) * 90) + 500;
  points.push([x, y]);
}
rc.curve(points, {
  roughness: 1.2, stroke: 'red', strokeWidth: 3
});
        

            const rc = rough.canvas(document.getElementById('canvas'), {
  async: true,
  options: {
	simplification: 0.2, roughness: 0.65
  }
});
const width = 960, height = 500;
const projection = d3.geo.albersUsa().scale(1070).translate([width / 2, height / 2]);
const path = d3.geo.path().projection(projection);
const randomColor = () => {
  let r = `rgb(${Math.round(Math.random() * 255)}, ${Math.round(Math.random() * 255)}, ${Math.round(Math.random() * 255)})`;
  return r;
}
const randomAngle = () => {
  return (Math.random() > 0.5 ? -1 : 1) * (1 + Math.random() * 88);
}
const randomStyle = () => {
  return (Math.random() > 0.5 ? 'solid' : '');
}
d3.json("./us.json", async (error, us) => {
  if (error) throw error;
  let topo = topojson.feature(us, us.objects.states).features;
  for (let feature of topo) {
	rc.path(path(feature), {
	  fill: randomColor(),
	  fillStyle: randomStyle(),
	  hachureAngle: randomAngle()
	});
  }
});
        

            var canvas = document.getElementById('canvas');
const rc = rough.canvas(canvas, {
  options: {
	fill: "blue",
	roughness: 0.8,
	bowing: 0.7
  }
});

var context = canvas.getContext("2d");
var margin = { top: 20, right: 20, bottom: 30, left: 40 },
  width = canvas.width - margin.left - margin.right,
  height = canvas.height - margin.top - margin.bottom;
var x = d3.scaleBand()
  .rangeRound([0, width])
  .padding(0.1);
var y = d3.scaleLinear()
  .rangeRound([height, 0]);
context.translate(margin.left, margin.top);

d3.tsv("data.tsv", function (d) {
  d.frequency = +d.frequency;
  return d;
}, function (error, data) {
  if (error) throw error;

  x.domain(data.map(function (d) { return d.letter; }));
  y.domain([0, d3.max(data, function (d) { return d.frequency; })]);

  var yTickCount = 10,
	yTicks = y.ticks(yTickCount),
	yTickFormat = y.tickFormat(yTickCount, "%");

  data.forEach(function (d) {
	rc.rectangle(x(d.letter), y(d.frequency), x.bandwidth(), height - y(d.frequency));
  });


  context.beginPath();
  x.domain().forEach(function (d) {
	context.moveTo(x(d) + x.bandwidth() / 2, height);
	context.lineTo(x(d) + x.bandwidth() / 2, height + 6);
  });
  context.strokeStyle = "black";
  context.stroke();

  context.textAlign = "center";
  context.textBaseline = "top";
  x.domain().forEach(function (d) {
	context.fillText(d, x(d) + x.bandwidth() / 2, height + 6);
  });

  context.beginPath();
  yTicks.forEach(function (d) {
	context.moveTo(0, y(d) + 0.5);
	context.lineTo(-6, y(d) + 0.5);
  });
  context.strokeStyle = "black";
  context.stroke();

  context.textAlign = "right";
  context.textBaseline = "middle";
  yTicks.forEach(function (d) {
	context.fillText(yTickFormat(d), -9, y(d));
  });

  context.beginPath();
  context.moveTo(-6.5, 0 + 0.5);
  context.lineTo(0.5, 0 + 0.5);
  context.lineTo(0.5, height + 0.5);
  context.lineTo(-6.5, height + 0.5);
  context.strokeStyle = "black";
  context.stroke();

  context.save();
  context.rotate(-Math.PI / 2);
  context.textAlign = "right";
  context.textBaseline = "top";
  context.font = "bold 10px sans-serif";
  context.fillText("Frequency", -10, 10);
  context.restore();
});
        

Что нового в версии 4.0?

Задание поля случайных чисел. Rough.js вычисляет фигуры, генерируя много случайных смещений. В результате каждый рендер создаёт уникальную нарисованную от руки форму. Однако в некоторых случаях такое поведение нежелательно. Бывает необходимо, например, сохранить форму штриховки при разных размерах фигуры. API теперь позволяет пользователю передавать начальное значение seed, которое используется для генерации предсказуемой последовательности случайных чисел. Параметр является опциональным:


            const seed = rough.newSeed();
rc.rectangle(10, 10, 200, 200, { fill: 'red', seed });
rc.rectangle(240, 10, 250, 250, { fill: 'blue', seed });
        

Новый алгоритм штриховки. Как описано выше, Rough.js может заполнить фигуру штриховыми линиями. Старый алгоритм был адаптацией кода Handy с небольшими изменениями. Код не очень хорошо обрабатывал вогнутые формы под некоторыми углами штриховки. Могли создаваться такие некорректные ситуации:


Новый алгоритм основан на алгоритме растеризации Scan-line. При создании линий штриховки строки обрабатываются пошагово с указанным межстроковым расстоянием hachureGap. Этот алгоритм, однако, предназначен для горизонтальных линий сканирования. Чтобы работать с различными углами штриховки, сначала производится поворот фигуры на угол hachureAngle и заполнение горизонтальными линиями. Потом найденные горизонтальные линии поворачиваются обратно на угол -hachureAngle, как показано на рисунке ниже.


Динамическая оценка шероховатости. Частью создания схематичного представления является создание несовершенных артефактов, генерируемых путём рандомизации определённых параметров. Некоторые из параметров при масштабировании могли приобретать слишком большие значения. Особенно это было заметно при отрисовке эллипсов. Обратите внимание, как на изображении ниже, окружности имеют одинаковую форму, но внешние получились более грубыми.


Алгоритм теперь автоматически настраивается в зависимости от размера фигуры. Ниже приведён тот же набор окружностей, созданный с применением автоподстройки.


Фигура без контура

Другой часто запрашиваемой функцией было добавление возможности рисовать фигуры без контура. Этого можно было бы достигнуть путём установки прозрачного цвета обводки. Однако наличие контура раньше учитывалось при заполнении основной фигуры. Теперь эти инструкции разделены, и для контура можно просто указать значение none.


            rc.rectangle(240, 10, 250, 250, { stroke: 'none', fill: 'blue' });
        

Заключение

Напоследок несколько примеров использования библиотеки:

  1. Wired elements – набор элементов на основе Rough.js.
  2. Змейка из элементов графики Rough.js
  3. Semiotic – визуализация данных для React, использующая Rough.js для рендеринга.
  4. Плагин Rough.js для Leaflet – библиотека JavaScript с открытым исходным кодом для мобильных интерактивных карт.
  5. React Bindings для Rough.js
  6. Инструмент для создания графиков, есть возможность использовать Rough.js
29
Янв
2020

Задача о шести шахматных конях

Сегодня нам предстоит алгоритмическая задача с позиционным обменом двух типов объектов. Наглядно такое движение можно представить через перемещение шахматных коней.

Услов…

29
Янв
2020

Как опубликовать свою Python библиотеку на PyPI

Делаем так, чтобы вашу библиотеку на Python любой мог установить с помощью pip install.

Трудно представить программу Python без набора операторов import. Но как опубликовать библиотеку, чтобы её также легко могли импортировать другие разработчики?

Благодаря импортированию, модули Python удобно использовать

В этом руководстве мы покажем на примере, как создать собственную библиотеку Python, которую можно будет установить с помощью менеджера пакетов pip, как другие сторонние решения. Если ваш код может приносить пользу, это отличный способ внести вклад в сообщество Python. Любой разработчик сможет установить пакет и импортировать его.

1. Создаём элементы библиотеки

Публикация пакета требует знания некоторых деталей. В этом примере мы будем рассматривать предварительно опубликованный пакет под названием dist_alx. Чтобы вам было удобнее сверяться, эта директория доступна в виде zip-папки в репозитории на GitHub.

Каталог содержит все необходимые элементы, которые должен иметь пакет перед публикацией. Мы будем использовать этот пример в качестве эталона, поскольку все пакеты Python должны иметь одинаковую структуру. Если вам интересно, что именно делает пакет dist_alx, это объяснено там же в README-файле.

Корневой каталог dist_alx содержит следующие файлы и директории:

  • setup.py – содержит метаданные пакета,
  • setup.cfg – конфигурационный файл, используемый для хранения настроек,
  • подпапку с тем же именем, что и родительская папка (в данном примере dist_alx), где хранится фактический код вашего пакета на Python.

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

setup.py
            from setuptools import setup

setup(name='dist_alx',
      version='0.0',
      description='Gaussian and Binomial distributions',
      packages=['dist_alx'],
      author_email='mihajlovic.aleksa@gmail.com',
      zip_safe=False)
        
setup.cfg
            [egg_info]
tag_build = 
tag_date = 0

        

Любая публикуемая на PyPI библиотека обязана иметь три вышеуказанных элемента. Помимо этого, пакет должен выполнять следующие условия:

  • Уникальное имя библиотеки. Никакие два существующих пакета Python не могут одинаково называться.
  • Файл setup.py должен содержать параметры name и packages. Они также должны иметь то же имя, что и пакет (см. пример выше).
  • Параметр version: в случае если что-то в пакете изменилось, нужно изменить и значение version.
  • Файла setup.py должен иметь параметр author_email с адресом электронной почты для связи. Используйте действующий e-mail, это важно для дальнейшей регистрации программы в репозитории PyPI.

2. Подготавливаем код

Как указано выше, внутри вложенной папки должен находиться фактический код библиотеки. Если вы откроете подпапку dist_alx, вы увидите, что она содержит файл _init_.py. По умолчанию ядро ​​Python ищет файл _init_.py в качестве отправной точки при чтении кода. Файл _init_.py связан со всеми другими сценариями Python в подпапке. Например, в нашем файле _init_.py, есть строка импорта from .Gaussiandistribution import Gaussian. Все .py-файлы связаны. Хорошей идеей, прежде чем пытаться написать код пакета, будет обновить свои знания о классах Python.

3. Создаём аккаунт PyPI

Большинство общедоступных пакетов Python хранятся в репозитории PyPI. При установке пакета на свой компьютер инструкцией pip, вы фактически скачиваете его из репозитория PyPI. Соответственно для публикации нового пакета его нужно наоборот, загрузить на сервер PyPI. Чтобы опубликовать библиотеку, нужно завести аккаунт (это бесплатно). Адрес электронной почты должен быть тот же, что внутри setup.py в параметре author_email.

Скриншот окна регистрации в репозитории PyPI

4. Публикуем библиотеку

Публикация осуществляется из командной строки или терминала. Команды идентичны в Windows и Linux.

Для публикации нам потребуется установить две библиотеки – setuptools и twine:

            pip install setuptools
        
            pip install twine
        

Переходим к родительскому каталогу.


Развёртываем пакет запустив setup.py:

            python setup.py sdist
        

Обратите внимание, что теперь в родительской папке будут созданы две новых директории (egg-info и dist).


Теперь с помощью twine развёртываем пакет на PyPI:

            twine upload dist/*
        

Здесь нужно указать своё имя пользователя и пароль PyPI.


Вуаля! Пакет размещён на сервере и готов к использованию!

Переходим в учётную запись на PyPI, идём в раздел Your projects. Если всё в порядке, вы увидите библиотеку.


Обратите внимание, что PyPI не поддерживает на сайте символ подчёркивания в именах файлов. Поэтому dist_alx отображается как dist-alx. Однако это не влияет на использование библиотеки – при последующем импорте мы будем вводить, как и задумано, dist_alx.

5. Используем

Переходим к любимому клиенту Python (например, Jupyter) и устанавливаем пакет с помощью pip. Импортируем и пользуемся в своё удовольствие!


Заключение

Прежде чем размещать пакет на главном сервере, опубликуйте его сначала на тестовом сервере PyPI.

Итак, последовательность создания библиотеки Python следующая:

  1. Изготовление необходимых элементов упаковки, проверка значений параметров.
  2. Подготовка кода пакета.
  3. Создание учётной записи PyPI (если её ещё не было).
  4. Публикация пакета на PyPI.
  5. Тестирование: pip-установка, импорт и запуск модуля.

Если вы думаете, что пока не готовы публиковать свою библиотеку, вам могут быть полезны такие наши публикации: