Введение

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

Задача

Тип зпдач весьма классический, про билетики:

У нас имеются автобусные билеты с номерами от 000000 до 999999. Билет считается 'счастливым', если сумма первых двух цифр равна сумме следующих двух цифр, и эта сумма равна сумме последних двух цифр. При этом не должно возникнуть ситуации, когда конкатенация пары цифр первого блока равна конкатенации пары цифр второго блока и третьего.

Для примера, рассмотрим билет с номером 123456:

• Сумма первых двух цифр: 1 + 2 = 3

• Сумма следующих двух цифр: 3 + 4 = 7

• Сумма последних двух цифр: 5 + 6 = 11

Обозначим символом || операцию конкатинации:

• конкатинация первых двух цифр: 1 || 2 = 12

• конкатинация следующих двух цифр: 3 || 4 = 34

• конкатинация следующих двух цифр: 5 || 6 = 56

Условия не выполняются, и билет считается не "счастливым".

Теперь мы хотим определить, сколько "счастливых" билетов находится в каждом рулоне троллейбуса.

Каждый рулон включает в себя 100 000 билетов (номера от 000000 до 099999, от 100000 до 199999 и так далее)

Решение "в лоб"

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

if __name__ == '__main__':

    for i in range(1000000): 
        ticket_number = f'{i:06d}'
        print(ticket_number)

Код использует цикл от 0 до 999999 и форматирует каждое число как строку, добавляя ведущие нули при необходимости с использованием f-строки и форматирования числа с шестью знаками. Таким образом, формируется последовательность номеров от 000000 до 999999.

Далее код выделяет три нужные подстроки (пары чисел) [partn].

if __name__ == '__main__':

    for i in range(1000000):

        ticket_number = f'{i:06d}'

        part1 = ticket_number[0:2]
        part2 = ticket_number[2:4]
        part3 = ticket_number[4:6]

        print(part1, part2, part3)

отфильтрем номера, которые не сооветствую условию об конкатинации, для этого достататочно их сравнить "="

    for i in range(1000000):


        ticket_number = f'{i:06d}'

        part1 = ticket_number[0:2]
        part2 = ticket_number[2:4]
        part3 = ticket_number[4:6]

        if part1 == part2 == part3:
            continue

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

def sum_digits(pair):
    return int(pair[0]) + int(pair[1])

и отфильтруем пары по равенству чисел

if sum_digits(part1) == sum_digits(part2) == sum_digits(part3):
    print(part1, part2, part3)

Остается только записать результат в карту (map) и вывести его.

def sum_digits(pair):
    return int(pair[0]) + int(pair[1])


if __name__ == '__main__':

    map = {i: 0 for i in range(10)}

    for i in range(1000000):

        ticket_number = f'{i:06d}'

        part1 = ticket_number[0:2]
        part2 = ticket_number[2:4]
        part3 = ticket_number[4:6]

        if part1 == part2 == part3:
            continue

        if sum_digits(part1) == sum_digits(part2) == sum_digits(part3):
            map[int(ticket_number[0])] += 1


    for k, v in map.items():
        print(f"рулон {k + 1} имеет: {v} счастливых билетов")

Результат:

рулон 1 имеет: 375 счастливых билетов
рулон 2 имеет: 455 счастливых билетов
рулон 3 имеет: 515 счастливых билетов
рулон 4 имеет: 555 счастливых билетов
рулон 5 имеет: 575 счастливых билетов
рулон 6 имеет: 575 счастливых билетов
рулон 7 имеет: 555 счастливых билетов
рулон 8 имеет: 515 счастливых билетов
рулон 9 имеет: 455 счастливых билетов
рулон 10 имеет: 375 счастливых билетов

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

Замерим время выполнения (самым преметивным способом):

start_time = time.time()
  //предыдущий код
print(time.time() - start_time)

Время выполнения составило 1.136587381362915 некотрых едениц времени.

Более оптиальное решение

Однако вместо того, чтобы перебирать все 100000 значений, достаточно ограничиться перебором всех возможных пар от 00 до 99. Это осуществимо, зная, сколько каждой паре соответствует других пар с той же суммой цифр. Сначала мы рассчитаем и запишем эту информацию в мапу (где ключ это сумма двух цифр, а значение количество таких сумм).

map = defaultdict(int)

for n1, n2 in product(range(10), repeat=2): //перебор всех двоек
    map[n1 + n2] += 1 // добовляем 1 в ту сумму которой соответствует двойка 

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

    res = {}

    for n1 in range(0, 10):
        res[n1] = 0
        for n2 in range(0, 10):
            res[n1] += (map[n1 + n2] ** 2) - 1

После этого мы возводим результат в квадрат, так как помимо перебираемой двойки есть еще две пары. Затем вычитаем 1, так как это представляет собой случай, который не соответствует требованию конкатенации.

Запишем это еще проще:

    res = {n1: sum((map[n1 + n2] ** 2) - 1 for n2 in range(10)) for n1 in range(10)}

Итого имеем:

from collections import defaultdict
from itertools import product

if __name__ == '__main__':

    map = defaultdict(int)

    for n1, n2 in product(range(10), repeat=2):
        map[n1 + n2] += 1

    res = {n1: sum((map[n1 + n2] ** 2) - 1 for n2 in range(10)) for n1 in range(10)}

    for k, v in res.items():
        print(f"рулон {k + 1} имеет: {v} счастливых билетов")

Результат:

рулон 1 имеет: 375 счастливых билетов
рулон 2 имеет: 455 счастливых билетов
рулон 3 имеет: 515 счастливых билетов
рулон 4 имеет: 555 счастливых билетов
рулон 5 имеет: 575 счастливых билетов
рулон 6 имеет: 575 счастливых билетов
рулон 7 имеет: 555 счастливых билетов
рулон 8 имеет: 515 счастливых билетов
рулон 9 имеет: 455 счастливых билетов
рулон 10 имеет: 375 счастливых билетов

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

Это существенное ускорение достигается за счет уменьшения числа итераций в циклах с 100 000 до всего 200. Стоит также отметить, что количество итераций можно уменьшить вдвое, учитывая симметрию результата (делать я этого конечно же не буду).

Вывод

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

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

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

P.S. код можно глянуть на GitHub