Я решил задачу бодрствования с помощью одной строчки Python

Делать вещи простыми и эффективными.

СОДЕРЖАНИЕ

∘ Задача
∘ Понимание задачи
∘ Пошаговое выполнение
∘ Набор основных математических операций
∘ Использованные контрольные примеры
∘ Ссылки

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

Большая часть современного профессионального развития состоит из конфигурирования и объединения библиотек вместе, поэтому приятно погрузиться в задачу, которая является чисто логической и ориентированной на производительность.

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

Один конкретный урок застал меня врасплох. Задачи доброжелательности оцениваются в порядке сложности: «Безболезненно», «Уважительно» или «Амбициозно». Эта задача получила оценку «респектабельная», но ее можно эффективно решить с помощью одной строчки кода.

Задание

Уроки Codility состоят из материала для чтения в формате PDF и набора «задач». Первое задание урока «Суммы префиксов» называется «Подсчет Div». Инструкции следующие:

Напишите функцию ... которая для трех целых чисел A, B и K возвращает количество целых чисел в диапазоне [A..B], которые делятся на K

Гарантируется, что A ≤ B.

Понимание проблемы

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

Очевидное решение методом перебора - перебрать все целые числа между A и B, проверяя, делятся ли они на K, используя по модулю (%).

Чтобы быть в безопасности, нам также нужно проверить, что B! = 0:

def solution(a, b, k):
  if b == 0:
    return 0

  count = 0
  for ii in range(a, b + 1):
    if ii % k == 0:
      count += 1

  return count

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

def solution(a, b, k):
  return 0 if b == 0 else len([ii for ii in range(a, b + 1) if ii % k == 0])

Это будет выполняться за линейное время - O(n) - что неидеально, если A равно 0, а B - возможное максимальное значение теста в 2 миллиарда.

Итерация по шагам

Точно так же, как в приведенном ниже примере, поиск наименьшего и наибольшего кратного k в диапазоне от A до B и повторение с шагом, равным K, все равно оставит нас с O(n), что особенно неэффективно, если K равно 1.

def solution(a, b, k):
  if b == 0:
    return 0

  first_divisible = a if a % k == 0 else a + (k - a % k)
  last_divisible = b - b % k

  return len(range(first_divisible, last_divisible + 1, k))

Но здесь вступает в игру некоторая магия Python: язык эффективно знает len диапазона, даже со значением шага. Это работает.

Но это также показывает более удобочитаемое, краткое и эффективное решение. Теперь мы можем видеть, что все, что нам нужно увидеть, это то, сколько раз кратное K встречается между A и B.

Набор основных математических операций

Давайте использовать исходный пример из Codility, a = 6, b = 11, k = 2.

• 11 / 2 = 5.5 - которое мы можем округлить до 5, чтобы получить общее количество способов, которыми 2 делится на 11
• (6 - 1) / 2 = 2.5 - которое мы можем округлить до 2 для количества способов, в которых целые числа меньше 6 без остатка делятся на 2. Мы можем вычесть их из суммы, указанной выше.
• 5 - 2 = 3 - вычтите исключенное количество из общего количества, чтобы получить наш результат.

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

def solution(a, b, k):
  return 0 if b == 0 else int(b // k - (a - 1) // k)

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

Любой из этих двух последних примеров все равно даст 100% результат на Codility.

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

Используемые тестовые примеры

Я подумал, что было бы полезно включить тестовые примеры, с которыми я работал при создании этих примеров.

cases = [
    [4, 10, 3, 2],
    [10, 10, 5, 1],
    [10, 10, 7, 0],
    [10, 10, 20, 0],
    [0, 0, 10, 0],
    [5, 100, 6, 16],
    [5, 100, 5, 20],
    [5, 102, 6, 17],
    [0, 2, 2, 2],
    [0, 5, 5, 2],
    [0, 5, 1, 6],
    [1, 5, 1, 5],
    [0, 2000000000, 1, 2000000001],
    [0, 2000000000, 2, 1000000001],
]

Они были подготовлены с использованием синтаксиса: [a, b, k, expected], чтобы их можно было включить в тест цикла, например:

def test_solution(self):
  for case in self.cases:
    with self.subTest(case):
      self.assertEqual(solution(case[0], case[1], case[2]), case[3])

использованная литература

Примечание: эта статья ранее была опубликована с примерами кода на Ruby.

Больше контента на plainenglish.io