Комментарии 27
Условия выполняются, и билет считается "счастливым".
У вас тут ошибочка, видимо
Хех хех
Где же Вы такие "классические" тестовые по python находите?
Это задачка скорее для решения на собесе...
Судя по условию билет 133122 счастливый.
А по вашему коду он не пройдет.
if part1 == part2 == part3
Наивный способ разобрали подробно, а оптимальное решение декларировали, ограничившись коротким описанием. Не буду врать, не понятным что там и как. Пришлось лезть в debug, чтобы разобраться с нуля. Хотелось бы увидеть более детальное разъяснение (с применение кроме описательного словами метода и других), которое кстати позволит поискать как ошибки в проектировании, так и другие, а также другие решения.
Вот этот текст - "Билет считается 'счастливым', если сумма первых двух цифр равна сумме следующих двух цифр, и эта сумма равна сумме последних двух цифр. При этом не должно возникнуть ситуации, когда конкатенация пары цифр первого блока равна конкатенации пары цифр второго блока и третьего." почему-то вызывает у меня когнитивный диссонанс. Я бы интерпретировал его таким образом, что три пары двузначных чисел, из которых состоит номер билета, должны иметь одинаковую сумму своих цифр, и при этом быть различны между собой. При такой интерпретации в вашем "наивном" решении вместо if part1 == part2 == part3: я бы написал if (part1 == part2) or (part2 == part3) or (part1 == part3):, что привело бы к тому, что всего счастливых билетов 3240.
Ну и мое видение чуть менее "наивного" решения выглядело бы как-то так:
Чуть менее "наивное" решение
from collections import Counter
# для каждой суммы пары цифр из диапазона 0..9 подсчитываем
# количество чисел из диапазона 0..99, сумма цифр которых равна
# этой сумме.
# Заметьте, что все числа из диапазона 0..99 у нас уникальны,
# что гарантирует отсутствие совпадающих чисел
# (условие различия всех 3-х двузначных чисел, составлющих номер билета)
counter = Counter([i + j for i in range(10) for j in range(10)])
# На "счастливость" могут претендовать только те суммы пары цифр,
# для которых имеется не менее 3-х различных чисел, чтобы
# было что расставлять по 3-м позициям в номере билета
lucky_numbers = {
s: count for s, count in counter.items() if count >= 3
}
total_lucky_tickets = 0
for i in range(10):
lucky_tickets = 0
for j in range(10):
if i + j in lucky_numbers:
# n - число различных чисел для суммы i+j,
# за исключением числа ij
n = lucky_numbers[i + j] - 1
# эти n различных чисел можно разместить
# по двум позициям n*(n-1) способом
lucky_tickets += n * (n - 1)
total_lucky_tickets += lucky_tickets
print(f"roll №{i + 1} -> {lucky_tickets}")
print(f"total lucky tickets = {total_lucky_tickets}") # 3240Что думаете о такой интерпретации?..
Если оставаться в рамках интерпретации автора вопроса, то:
# 20 итераций: фиктивный 20-й элемент - чтобы упростить последующий цикл
res = [v * v - 1 for v in [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]]
sm = sum(res[:10]) # 10 итераций
for i in range(10): # 10 итераций
print('рулон %d имеет: %d счастливых билетов' % (i + 1, sm))
sm += res[i + 10] - res[i]Итого имеем 40 итераций.
Количество вариантов каждой суммы считается в уме - для этого не надо делать 100 итераций посредством product.
А можно поподробнее суть решения?
Всего у нас 19 возможных сумм двух цифр: от 0 (0 + 0) до 18 (9 + 9). При этом для каждой суммы k количество способов её получения n[k] = 10 - |k - 9| (я не стал вычислять циклом, а просто загнал все значения в массив, где индекс - сумма, а кол-во способов - значение).
Всего существует n[k]² комбинаций двух групп с суммой k каждая.
Из невозможности тройного равенства получаем, что для каждой левой группы цифр со значением k существует n[k]² - 1 счастливая комбинация двух правых групп.
Если первая цифра билета - i, то k может принимать значения от i до i + 9. И для получения кол-ва счастливых билетов s[i] достаточно просуммировать значения от n[i]² - 1 до n[i + 9]² - 1 включительно.
Если у нас уже вычислено s[i], то не надо пересчитывать s[i + 1] целиком - достаточно от s[i] отнять n[i]² - 1 и прибавить n[i + 10]² - 1 (скользящее окно).
А т.к. и исходная сумма чисел 1²-1 .. 10²-1, и каждое из значений n[i]² - 1 считаются простыми формулами без циклов (которые ещё и сокращаются в процессе вычислений), то всю программу можно ужать до единственного цикла:
sm = 10 * (10 + 1) * (2 * 10 + 1) // 6 - 10 # сумма 1²-1 .. 10²-1 без цикла
for i in range(0, 10): # в программе осталось 10 итераций
print(sm)
sm += 80 - 20 * i # скользящее окно после раскрытия скобок и сокращений
def first_n2_sum(n):
# формула для суммы первых n2 натуральных чисел
return n*(n+1)*(2*n+1)//6
def last_n2_sum(n):
return first_n2_sum(9)-first_n2_sum(9-n)
def happy_tickets(pack_num):
# вычитаем 10 вариантов, которые не подходят под условие с конкатенацией
return first_n2_sum(10) - first_n2_sum(pack_num) + last_n2_sum(pack_num) - 10
ticket_pack = {i: happy_tickets(i) for i in range(10)}
for k, v in ticket_pack.items():
print(f"рулон {k + 1} имеет: {v} счастливых билетов")10 итераций :)
конкатЕнация же!)
А еще можно ускорить почти в сотню раз, воспользовавшись математикой.
Сумму S от 2 до 18 двумя цифрми можно набрать 
способами. Для каждой суммы есть 
счастливых билетов (каждая треть может быть любым способом, но надо вычесть плохие-счастливые билеты, где все три части совпадают). Общее количество билетов - сумма по S. Стоит рассмотреть отдельно случаи когда S не превышает 10, и наоборот. Тогда модули можно раскрыть, причесать выражение и использовать формлу суммы кубов/квадратов/арифметической прогресии.
При этом не должно возникнуть ситуации, когда конкатенация пары цифр
первого блока равна конкатенации пары цифр второго блока и третьего.
Что значит "не должно возникнуть ситуации"? Во время выполнения вычисления не должно возникнуть такой ситуации? Можно понять именно так. В вашем первом решении (которое "в лоб") такая ситуация возникает целых 100 раз - на участке `if part1 == part2 == part3`. Чтобы ситуации не возникло, можно попробовать что-то математичное, как в комментарии выше. Да и то - не ясно, что именно понимать под "ситуацией". Согласен, что это занудство, но расплывчатые формулировки иногда вызывают страшные флешбэки :)
map - встроенная функция питона. Перекрывать встроенные функции своими переменными - нехорошо, потом сюрпризы будут, когда вы встроенными функциями захотите воспользоваться.
Ну и количество "ашипог" в тексте просто удручает.
О боже... Задача должна быть решаема со сложностью O(1). При чем тут питон вообще?
Кто же создаёт переменную с зарезервированным именем?
Не нравятся такие задачи: решение в лоб думается(вру, думать не надо) и пишется ну пусть за пару минут и рассчитывается за секунду. Итоговое время - 2м 1с. Решение не в лоб - если думается и пишется за 3 минуты то оно уже хуже "неоптимального" решения в полтора раза.
А если это собес, начинается игра "угадай что от меня хотят" - послушать про "какая гадость этот полный перебор. это зло" или "Преждевременная оптимизация — корень всех зол. KISS"
На собесе такие задачи даются для того, чтобы вот вы и рассказали, какая вычислительная сложность у какого решения, что вы вообще в курсе, что задачки можно решать по-разному и вы способны оценить вычислительную сложность. Чтобы потом, когда дело дойдёт до реальных задач, где нужно обработать уже миллиарды записей, вы понимали, что решение сложности O(n^2) там уже точно не потянет и нужно сразу придумывать что-то алгоритмически более эффективное.
Ну вот выше решение за О(1). Только к 1ккк элементов его не применить, а на переделку и адаптацию может уйти огромное количество времени. Ладно бы на собесе сразу так и делали: "вот тебе наш датасет, сделай вот это, тестсьют автоматически прибивает решение, если оно работает слишком долго", но нет же, дают какую-то чушь на пять элементов, в которой очевидно, что О(n*n) — вообще пустяк, на вызов функций CPython потратит кратно больше времени, чем на эту вашу сложность.
А то, что собеседующие не дают соответствующий датасет, означает, что они сами даже представить себе не могут ту ситуацию, которую собеседуемый должен для них угадать.
А если первое решение распараллелить на десяток процессов, что по времени получим не заморачиваясь?)
Никакое распараллеливание не даст ускорения больше, чем число процессов. Число же процессов обычно бессмысленно делать больше числа ядер процессоров. А в реальности ускорение ещё меньше из-за накладных расходов. Сравните с ускорением в 3000 раз от смены алгоритма. Именно поэтому в первую очередь нужно искать оптимальный алгоритм, а распараллеливать уже в последнюю очередь, когда алгоритм дальше не оптимизируется, а всё-равно хочется ещё хотя бы 2х выжать.
Разбор классического тестового задания на позицию Python Developer