Google Foobar: Как найти граничные случаи и идентифицировать тестовые случаи. питон

Question

Проблема

Совершенство впрыска топлива

Коммандер Лямбда попросил вашей помощи усовершенствовать систему автоматического впрыска топлива с квантовой антивеществой для своего устройства LAMBCHOP конца света. Для вас это отличный шанс поближе познакомиться с LAMBCHOP - и, может быть, немного саботировать, пока вы там - так что вы с радостью взялись за работу.

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

Механизмы контроля топлива имеют три операции:

Добавьте одну топливную таблетку. Удалите одну топливную таблетку. Разделите всю группу топливных таблеток на 2 (из-за деструктивной энергии, выделяющейся, когда гранула с квантовой антивеществом разрезается пополам, меры безопасности позволят этому случиться только при четном количестве шарики) Напишите функцию с именем answer(n), которая принимает в качестве строки положительное целое число и возвращает минимальное количество операций, необходимых для преобразования числа шариков в 1. Панель управления впускным отверстием для топлива может отображать только число длиной до 309 цифр. так что не будет больше гранул, чем вы можете выразить в таком количестве цифр.

Например: answer(4) возвращает 2: 4 -> 2 -> 1 ответ (15) возвращает 5: 15 -> 16 -> 8 -> 4 -> 2 -> 1

Контрольные примеры

Входные данные: (строка) n = "4" Выходные данные: (int) 2

Входные данные: (строка) n = "15" Выходные данные: (int) 5

Вот мое решение:

import math
import decimal
def answer(n):
    n = long(n)
    if n <= 1 or n >= long('9' * 309):
        return 0
    # 1. Find closest power of 2
    round_threshold_adjust = math.log(3,2)- (1.5)
    log_n = math.log(n, 2)
    power = log_n - round_threshold_adjust

    # Round power down if X.50000. If n is equally between two powers of 2,
    # choose the lower power of 2. E.g. For 6, choose, 4 not 8
    power2 = long(decimal.Decimal(power).quantize(0, decimal.ROUND_HALF_DOWN))

    # 2. Calculate the difference, add to iterations
    # 3. Take log 2 of that, add that to iteration
    iters = abs(n - 2**power) + power
    return(iters)

Мое решение в настоящее время проходит 3 из 10 тестовых случаев. Я полагаю, что другие тестовые случаи - крайние случаи. Можете ли вы дать мне несколько советов о том, как я могу определить, где мой код не работает? (У меня нет доступа к тестам)

Вот некоторые из тестовых случаев, которые я пробовал:

assert answer(15) == 5
assert answer(4) == 2
assert answer(3) == 2
assert answer(2) == 1
assert answer(6) == 4
assert answer(7) == 4
assert answer(10) == 5
assert answer(1024) == 10
assert answer(1025) == 11
assert answer(1026) == 12
assert answer(1027) == 13
assert answer(768) == 256 + 9

Answer 1

Вот мое решение:

#!/usr/bin/python
#fuel-injection-perfection
#Program to count the naximum number of operations needed to recursively divide a number by 2. Add or subtract 1 where needed.
#V2 - Initial version was done using recursion but failed for large numbers due to python limitation & performance issues.  
cnt=0
def divide(x):
    global cnt
    while(x>1):
        if (x & 1==0):
            #Dividing even number by two by shifting binary digits one step to the right.
            x=x>>1
        else:
            a=x+1
            b=x-1
            #counters ac & bc will be used to count trailing 0s
            ac=bc=0
            #count trailing 0's for x+1
            while(a & 1==0):
                a=a>>1
                ac+=1
            #count trailing 0's for x-1
            while(b & 1==0):
                b=b>>1
                bc+=1
            #go with x+1 if it has more trailing 0s in binary format. Exception is number 3 as b10 can be divided in less steps than b100.
            #edge case 3 identified by manually testing numbers 1-10.
            if (ac>bc and x!=3):
                x+=1
            else:
                x-=1
        cnt+=1

def solution(n):
    global cnt
    n=int(n)
    divide(n)
    return cnt

Answer 2

Если я правильно понял, что при 768 гранулах вам нужно 256+9 шагов, чтобы преобразовать это в 1 гранулу?

Я могу сделать это в 10 шагов:

• Разделите 768 на 2
• Повторите еще 7 раз -> вы получите 3 гранулы
• Вычесть 1
• Вычесть 1

Я думаю, что ваш первый шаг, сложение / вычитание, пока вы не достигнете степени 2, не является самым быстрым решением.

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

Answer 3

Это ответ Python3. Я создал функцию буксировки, одну с добавлением 1, а другую с вычитанием 1, а затем сравнение, которое дает лучший ответ с наименьшим количеством шагов.

#function for the adding 1 to the odd number
def np(n):
    c = 0
    while n > 1:
        if n%2 == 0:
            n = n/2
            c += 1
        else:
            n += 1
            c += 1
    return c

#function for the subtracting 1 to the odd number
def nn(n):
    c = 0
    while n > 1:
        if n%2 == 0:
            n = n/2
            c += 1
        else:
            n -= 1
            c += 1
    return c

#Solution function
def solution(n):
    n = int(n)
    if np(n) > nn(n):
        return nn(n)
    else:
        return np(n)

Надеюсь, это сработает, ура.