Убить гидру

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

heads = [135]
hits = [25,67,1,62]
growths = [15,25,15,34]

Тогда ты можешь убить hits[i] головы, но growths[i] головы снова отрастают. Мой подход состоит в том, чтобы каждый раз рандомизировать индекс совпадений, и он работает, но я не думаю, что это слишком эффективно. Конечно, время варьируется для каждого набора попаданий, наростов. Мы должны определить, можно ли убить гидру при заданном ограничении количества итераций.

from timeit import default_timer as timer

start = timer()


import random
import time

heads = [88,135,192,152]

hits = [25,67,1,62]
growths = [15,25,15,34]



def hydra_killing():
    
    iter_limit = 1000

    for head in heads:
        iters = 0           #Resets iters at every new 'hydra'
        while head != 0:
            iters += 1

            if iters == iter_limit:
                print("NO")             
                break
            else:
                i = random.randint(0,3)         #Randomly choose a hit value
                if head >= hits[i]:
                    head -= hits[i]

                    if head == 0:
                        print(f'''
YES...............................................{iters}


''')
                    else:
                        head += growths[i]
                        #print(head, hits[i], growths[i], iters)
                        
                else:
                    iters -= 1 #if the heads remaining are greater than 
#hits[i], then this iteration is not counted

hydra_killing()



end = timer()
print(end - start, " seconds")


            
        

Отзыв по коду

• Используйте линтер! В вашем коде много несоответствий, что говорит о том, что вы не используете какой-либо тип автоформатора для своего кода. Это настоятельно рекомендуется. Я люблю использовать black, но есть много других вариантов.
• Структурируйте свой код с помощью функций
• Удалите неиспользуемый импорт с помощью импорта.
• Разместите только соответствующие части.
• Разделите отпечаток из хитов

Использование маркеров над отправная точка для улучшения вашего кода выглядит так

from timeit import default_timer as timer
import random


def hydra_killing(head, hits, growths, iter_limit=1000):
    growths_ = dict(zip(hits, growths))

    iters = 0
    while (iters := iters + 1) < iter_limit:
        hit = random.choice(hits)
        if head < hit:
            continue
        head -= hit
        if head == 0:
            return True, iters
        head += growths_[hit]

    return False, iter_limit


if __name__ == "__main__":

    heads = [88, 135, 192, 152]
    hits = [25, 67, 1, 62]
    growths = [15, 25, 15, 34]

    for head in heads:
        start = timer()
        is_hydra_dead, iters = hydra_killing(head, hits, growths)
        end = timer()
        print(end - start, " seconds")
        print(is_hydra_dead, iters)

В качестве альтернативы мы могли бы попробовать меньшее значение попадания вместо вызова continue. Это будет выглядеть так

def hydra_killing(head, hits, growths, iter_limit=1000):
    growths_ = dict(zip(hits, growths))

    iters = 0
    while (iters := iters + 1) < iter_limit:
        hit = random.choice(hits)
        if head < hit:
            if small_hits := [hit for hit in hits if hit < head]:
                hit = random.choice(small_hits)
            else:
                return False, iters
        head -= hit
        if head == 0:
            return True, iters
        head += growths_[hit]

    return False, iter_limit

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

Предложение 1 [We only want to know if the Hydra can be killed!]

Итак, у вас есть отличная отправная точка! Случайный выбор количества голов для убийства — это нет плохая идея! Однако, чтобы улучшить код, нам нужно ввести несколько ранних выходов.

• Если head в hits мы возвращаемся. Это достаточно просто, если гидру удастся убить на следующем ходу, мы вернемся.

• Что, если hit - growth в hits? Конкретно, если головки = 72, diff := hit - growth = 25 - 15 = 10 тогда мы знаем, что гидру можно убить на следующем ходу. Так как heads - diff = 62 а также 62 в hits.

• Аналогичным образом мы можем удалить diff снова и снова, пока мы не достигнем hit. Так что любое кратное 72 можно удалить, так как. 92 - 10 - 10 = 62 например. И мы знаем, что смена головок после добавления и удаления 10. У Python есть умный способ проверить это с помощью % оператор (по модулю) Итак, мы просто проверяем, head % diff заключается в hits.

• Если мы сообразительны, мы проверяем, не hit оставляет нас в состоянии выше. Это означает, что мы проверяем, если head - hit % diff заключается в hits, и если это произойдет, мы вернемся.

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

          chunk = max(1, head // chunk_size)
          head += (growths_[hit] - hit) * chunk
  

код 1

from timeit import default_timer as timer
import random


def hydra_killing(head, hits, growths, iter_limit=10 ** 6):

    growths_ = dict(zip(hits, growths))
    positive_hits, differences = zip(
        *[(hit, hit - growth) for hit, growth in zip(hits, growths) if hit > growth]
    )
    chunk_size = 1000
    iters = 0
    while (iters := iters + 1) < iter_limit:

        if head in hits:
            return True, iters
        for diff in differences:
            if head % diff in positive_hits:
                return True, iters
            for h in positive_hits:
                if (head - (h + growths_[h])) % diff in positive_hits:
                    return True, iters

        hit = random.choice(hits)

        if head < hit:
            if small_hits := [hit for hit in hits if hit < head]:
                hit = random.choice(small_hits)
            else:
                return False, iters
        chunk = max(1, head // chunk_size)
        head += (growths_[hit] - hit) * chunk

    return False, iter_limit


if __name__ == "__main__":

    heads = [88, 135, 192, 98767892]
    # heads = [4321]
    hits = [25, 67, 1, 62]
    growths = [15, 25, 15, 34]

    for head in heads:
        start = timer()
        is_hydra_dead, iters = hydra_killing(head, hits, growths)
        end = timer()
        print(end - start, " seconds")
        print(is_hydra_dead, iters)

Предложение 2 [We want the optimal]

Если у вас много голов, я бы рекомендовал просто использовать itertools. Обратите внимание, что до самого последнего удара hit
а также growth может произойти одновременно. То есть мы можем просто поразить гидру и проверить, можно ли убить ее одним ударом.

Гидру можно убить одним ударом, если ее голова находится в hits

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

Код 2

import itertools

def is_hydra_one_hit_from_death(total_heads, hits, number_of_hits, growths):
    """Checks if Hydra is 1 hit away from death after n hits"""
    heads_removed = sum(
        (hit - growth) * number
        for hit, number, growth in zip(hits, number_of_hits, growths)
    )
    return (total_heads - heads_removed) in hits


def kill_hydra_itertools(head, hits, growths):
    """Iterates over all possible number of hits, returns first '1 hit from death'"""
    for hydra_hits in itertools.product(*[range(head // 10) for _ in hits]):
        if is_hydra_one_hit_from_death(head, hits, hydra_hits, growths):
            return hydra_hits
    return ()

if __name__ == "__main__":

    heads = [88, 135, 152, 1002]
    hits = [25, 67, 1, 62]
    growths = [15, 25, 15, 34]

    # Sorts hits and growths in ascending number of hydra heads killed
    # which speeds up the iteration somewhat
    hits, growths = zip(
        *sorted(zip(hits, growths), key=lambda sub: sub[1] - sub[0], reverse=True)
    )

    for head in heads:
        if hits_2_almost_kill := kill_hydra_itertools(head, hits, growths):
            print(hits_2_almost_kill)

Пример

Например, для 152 код возвращает (2, 0, 1, 3) мы можем проверить, что это правильно, выполнив

print(152 - (25 - 15) * 2 - (1 - 15) * 1 - (62 - 34) * 3)

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

Предложение 3 [Mathematics]

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

Мы знаем, что каждый раз, когда мы ударяем по гидре, смена голов равно

change_in_heads = [25-15, 67-25, 1-15, 62-34] = [10, 42, -14, 28]

Это означает, что в принципе мы ищем решение уравнения

10 r + 42 s - 14 t + 28 u = heads

Это известно как Диофантово уравнение который sympy умеет решать.

Обратите внимание, что это возвращает общее решение, что означает, например, что решение

10 r + 42 s - 14 t + 28 u = 88

записывается как

t_0, -35 t_0 + 7 t_1 + 132, t_0 + t_1 + t_2, -20 t_0 + 8 t_1 + 3 t_2 + 88

Где t_0, t_1 а также t_2 — целые числа, которые мы можем изменить, чтобы сгенерировать столько решений, сколько захотим. (Среди ботаники мы говорим, что решение можно записать в видепараметрическое уравнение.) Итак, все, что нам нужно сделать, это использовать sympy для решения уравнения, а затем проверьте, можем ли мы найти конкретное решение с целыми коэффициентами.

Ной 0: Приведенное выше объяснение не довольно верно. Из-за того, как вы выбираете для расчета ударов и повторного роста (ударов до повторного роста). Нам действительно нужно бить Гидру, пока она не окажется на расстоянии одного удара от смерти. Это означает, что полоса здоровья Гидры должна быть в hits Вместо этого это делается путем проверки того,

10 x + 42 y - 14 z + 28 w = 88 - hit

есть решение для каждого hit в hits.

Примечание 1: что переключатель minimize в приведенном ниже коде пытается найти самый короткий или самый быстрый способ убить Гидру. Если вы только какое-либо решение, установите это логическое значение в false.

Заметка 2: приведенный ниже код — это просто предложение. Есть несколько улучшений, которые можно (и нужно внести в приведенный ниже код). Такие как, но не ограничиваясь этим

Работы еще предстоит сделать

• Добавление Подсказки по набору текста PEP484

• Вместо использования вложенных циклов for для поиска положительного решения либо:

  • Используйте рекурсивное решение или используйте itertools как видно раньше.

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

    t_0, -35 t_0 + 7 t_1 + 132, t_0 + t_1 + t_2, -20 t_0 + 8 t_1 + 3 t_2 + 88
    

    Для первой гидры. Это значит, что t_0>0, t_1 > (35 t_0 - 132)/7, и например t_2 > t_1 + t_2. Это может ускорить зацикливание.

Код 3

from sympy.solvers.diophantine import diophantine
from sympy import symbols, solve

r, s, t, u = symbols("r, s, t, u", integer=True)


def is_hydra_killable(heads, hits, growths, minimize_solution=False):
    change_in_heads = [hit - growth for hit, growth in zip(hits, growths)]
    equation = sum(d * var for d, var in zip(change_in_heads, [r, s, t, u]))

    min_hits_2_kill = [float("Inf")] * len(hits)
    for index, hit in enumerate(hits):
        try:
            [solution] = diophantine(equation - (heads - hit))
        except ValueError:
            continue
        hits_2_kill = hydra_hits_required(solution, minimize_solution)
        if sum(hits_2_kill) < float("Inf"):
            if minimize_solution:
                if sum(min_hits_2_kill) > sum(hits_2_kill):
                    min_hits_2_kill = hits_2_kill
            else:
                return True, hits
    return sum(min_hits_2_kill) < float("Inf"), min_hits_2_kill


def hydra_hits_required(solution, minimize_solution=False, max_range=10):
    t_1, t_0, t_2 = solution[3].free_symbols

    length_solution = float("Inf")
    shortest = [float("Inf"), float("Inf"), float("Inf")]
    t0_start = int(nsolve(solution[0], 0) + 1)
    for t0 in range(t0_start, max_range + t0_start):
        sol1 = [expr.subs({t_0: t0}) for expr in solution]
        t1_start = int(nsolve(sol1[1], 0) + 1)
        for t1 in range(t1_start, max_range + t1_start):
            sol2 = [expr.subs({t_1: t1}) for expr in sol1]
            t2_start = max(int(nsolve(sol2[2], 0) + 1), int(nsolve(sol2[3], 0) + 1))
            for t2 in range(t2_start, t2_start + max_range):
                sol3 = [expr.subs({t_2: t2}) for expr in sol2]
                if min(sol3) > 0 and sum(sol3) < length_solution:
                    shortest = sol3
                    length_solution = sum(sol3)
                    if not minimize_solution:
                        return shortest
    return shortest


def is_hydra_one_hit_from_death(heads, hits, number_of_hits, growths):
    """Checks if Hydra is 1 hit away from death after n hits"""
    for hit, number, growth in zip(hits, number_of_hits, growths):
        heads = heads - (hit - growth) * number
    return heads in hits


if __name__ == "__main__":

    heads = [88, 135, 192, 98765672]
    hits = [25, 67, 1, 62]
    growths = [15, 25, 15, 34]

    minimize = True

    for head in heads:
        is_dead, hits_2_kill = is_hydra_killable(head, hits, growths, minimize)
        print(hits_2_kill)
        print(is_hydra_one_hit_from_death(head, hits, hits_2_kill, growths))