📕 Последовательности символов в строке

Я решаю задачки на сайте DMOJ и одна задача поставила меня в небольшой тупик.
Главная трудность заключалась в написании небольшой функции, которая принимала строку без пробелов, а возвращала бы строку, где каждая непрерывная последовательность одинаковых символов была бы представлена в следующем виде: 3 p, где цифра 3 обозначает сколько символов p было в последовательности. Сейчас будет понятней:

Строка входа

input = 'pppqqq++++'

Строка выхода

output = '3 p 3 q 4 +'

В итоге как с помощью python из строки input получить строку output?

❓ Решение кроется в 14 строках:

def compress_string(string):
    compressed = []
    count = 1

    for i in range(1, len(string)):
        if string[i] == string[i - 1]:
            count += 1
        else:
            compressed.append(f"{count}({string[i - 1]})")
            count = 1
    compressed.append(f"{count}({string[-1]})")
    return " ".join(compressed)

print(compress_string('pppqqq++++'))

Good coding 🧑‍💻

#problem #string #algorithm

⬆️ [INFO] Поиск пересечений

Помните такие конструкции в детских играх или в каких-то туториалах, когда нужно соединить линией элементы, которые подходят друг другу по каким-либо свойствам? Например в левом столбике названия цветов, а в правом их обозначения. Скорее всего, некоторые линии объединенных элементов будут пересекаться. На основании этого описания, представим два списка:

a = [5, 4, 1, 3, 2]
b = [1, 3, 2, 5, 4]

Соедините мысленно все одинаковые числа линиями. Как с помощью python посчитать количество пересечений?

Рассмотрим функцию find_intersections

def find_intersections(left_side, right_side):
    num_fields = len(left_side)
    intersections = 0

    right_indices = {right_side[i]: i for i in range(num_fields)}

    for i in range(num_fields):
        for j in range(i + 1, num_fields):
            left_cow_a = left_side[i]
            left_cow_b = left_side[j]

            right_cow_a = right_indices[left_cow_a]
            right_cow_b = right_indices[left_cow_b]

            if right_cow_a > right_cow_b:
                intersections += 1

    return intersections

Функция find_intersections подсчитывает количество "пересечений" между элементами двух списков — left_side и right_side.

Пересечение — это такая ситуация, когда два элемента в одном списке расположены в одном порядке, а в другом — в обратном.

1. Инициализация переменных:

• num_fields — количество элементов в списках (они одинаковой длины).

• intersections — счетчик пересечений, инициализируется нулем.

2. Создание словаря индексов:

• right_indices — это словарь, где каждому элементу из списка right_side сопоставляется его индекс. Это нужно, чтобы быстро находить позиции элементов из right_side.

3. Два вложенных цикла для перебора пар элементов:

• Внешний цикл (for i in range(num_fields)) перебирает каждый элемент списка left_side как первый элемент пары.

• Внутренний цикл (for j in range(i + 1, num_fields)) перебирает каждый следующий элемент списка как второй элемент пары.

4. Сравнение порядков элементов в списках:

• Для текущей пары элементов left_cow_a (из left_side[i]) и left_cow_b (из left_side[j]), находятся их индексы в right_side с помощью словаря right_indices: это right_cow_a и right_cow_b.

• Если в right_side первый элемент пары (right_cow_a) находится позже второго (right_cow_b), то это пересечение, и счетчик intersections увеличивается на 1.

5. Результат:

• Функция возвращает общее количество пересечений.

Пример: Если:

• left_side = [1, 2, 3]

• right_side = [2, 1, 3]

• То пересечение будет между 1 и 2, так как их порядок в right_side обратен порядку в left_side.

———

Good coding 🧑‍💻

#python #info #list #matrix #algorithm