Решение головоломки в Python

Question

У меня есть одна головоломка, и я хочу ее решить с помощью Python.

Головоломка:

Торговец имеет вес в 40 кг, который он использовал в своем магазине. Однажды он упал из своих рук и разбился на 4 части. Но удивительно, теперь он может весить любой вес от 1 кг до 40 кг с комбинацией этих 4 штук.

Итак, вопрос в том, что такое веса этих 4 штук?

Теперь я решил решить это на Python.

Единственное ограничение я получил от головоломки в том, что сумма 4-х штук 40. С этими словами я мог фильтровать все множество значений 4, сумма которых 40.

import itertools as it 

weight = 40 
full = range(1,41) 
comb = [x for x in it.combinations(full,4) if sum(x)==40] 

length of comb = 297

сейчас Мне нужно проверить каждый набор значений в comb и попробовать все комбинации операций.

Например, если (a,b,c,d) - это первый набор значений в comb, мне нужно проверить a,b,c,d,a+b,a-b, .................a+b+c-d,a-b+c+d........ и так далее.

Я пробовал много, но я застрял на этом этапе, то есть как проверить все эти комбинации вычислений на каждый набор из 4 значений.

Вопрос:

1) Я думаю, что мне нужно, чтобы получить список всех возможных комбинаций [a,b,c,d] and [+,-].

2) У кого-нибудь есть лучшая идея и расскажите мне, как идти дальше отсюда?

Кроме того, я хочу сделать это полностью без помощи каких-либо внешних библиотек, необходимо использовать только стандартные библиотеки python.

EDIT: Извините за позднюю информацию. Его ответ (1,3,9,27), который я нашел несколько лет назад. Я проверил и проверил ответ.

EDIT: В настоящее время ответ fraxel работает с time = 0.16 ms. Всегда приветствуется лучший и быстрый подход.

С уважением

ARK

Answer 1

Ранее проходных anwswer:

Мы знаем a*A + b*B + c*C + d*D = x для всех x между 0 и 40 и a, b, c, d ограничиваются -1, 0, 1. Ясно A + B + C + D = 40. Следующий случай x = 39, так ясно наименьший шаг, чтобы удалить элемент (это единственно возможный шаг, который может привести к успешно противовеса 39):

A + B + C = 39, так D = 1, по Neccessity.

следующая:

A + B + C - D = 38

следующая:

A + B + D = 37, так C = 3

затем:

A + B = 36

, то:

A + B - D = 35

A + B - C + D = 34

A + B - C = 33

A + B - C - D = 32

A + C + D = 31, так что A = 9

B = 27 Поэтому

Так веса 1, 3, 9, 27

Действительно это может быть немедленно выведены из того факта, что все они должны быть кратны 3.

Интересное обновление:

Так вот некоторые питона код найти минимальный набор весов для любого сброшенного веса, который будет охватывать пространство:

def find_weights(W): 
    weights = [] 
    i = 0 
    while sum(weights) < W: 
     weights.append(3 ** i) 
     i += 1 
    weights.pop() 
    weights.append(W - sum(weights)) 
    return weights 

print find_weights(40) 
#output: 
[1, 3, 9, 27] 

Для дальнейшего проиллюстрируем это объяснение, можно рассматривать проблему как минимальное количество весов для охвата числового пространства [0, 40]. Очевидно, что количество вещей, которые вы можете делать с каждым весом, это тройной/тройной (добавьте вес, снимите вес, положите вес с другой стороны). Так что, если мы пишем наши (неизвестные) весов (A, B, C, D) в порядке убывания, наши ходы можно резюмировать следующим образом:

ABCD: Ternary: 
40: ++++  0000 
39: +++0  0001 
38: +++-  0002 
37: ++0+  0010 
36: ++00  0011 
35: ++0-  0012 
34: ++-+  0020 
33: ++-0  0021 
32: ++--  0022 
31: +0++  0100 
etc. 

Я поставил трехкомпонентную считая от 0 до 9 вместе, чтобы показать, что мы эффективно в системе счисления троичной (основание 3). Наше решение всегда может быть записано как:

3**0 + 3**1 +3**2 +...+ 3**N >= Weight 

Для минимального N это верно. Минимальное решение ВСЕГДА будет иметь эту форму.

Кроме того, мы можем легко решить эту проблему для больших весов и найти минимальное количество деталей, чтобы охватить пространство:

Человек падает известный вес W, он распадается на куски. Его новые веса позволяют ему взвесить любой вес до W. Сколько весов есть, и что они?

#what if the dropped weight was a million Kg: 
print find_weights(1000000) 
#output: 
[1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 202839] 

Попробуйте использовать перестановки для большого веса и неизвестное количество штук !!

Answer 2

Вот решение грубой силы itertools:

import itertools as it 

def merchant_puzzle(weight, pieces): 
    full = range(1, weight+1) 
    all_nums = set(full) 
    comb = [x for x in it.combinations(full, pieces) if sum(x)==weight] 
    funcs = (lambda x: 0, lambda x: x, lambda x: -x) 
    for c in comb: 
     sums = set() 
     for fmap in it.product(funcs, repeat=pieces): 
      s = sum(f(x) for x, f in zip(c, fmap)) 
      if s > 0: 
       sums.add(s) 
       if sums == all_nums: 
        return c 

>>> merchant_puzzle(40, 4) 
(1, 3, 9, 27) 

Для объяснения того, как это работает, проверьте the answer Avaris gave, это реализация того же алгоритма ,

Answer 3

Вы близко, очень близко :).

Поскольку это головоломка, которую вы хотите решить, я просто дам указатели.Для этой части:

Например, если (а, б, в, г) первый набор значений в гребенке, мне нужно проверить а, б, в, г, а + B, AB,. ................ a + b + cd, a-b + c + d ........ и т. д.

Рассмотрите это: каждый вес может быть нанесен на одну шкалу, другой или ни один. Таким образом, для случая a это может быть представлено как [a, -a, 0]. То же самое с тремя другими. Теперь вам нужны все возможные пары с этими тремя возможностями для каждого веса (подсказка: itertools.product). Тогда возможное измерение спаривания (скажем: (a, -b, c, 0)) является просто суммой этих (a-b+c+0).

Все, что осталось, просто проверяет, можете ли вы «измерить» все требуемые веса. set может пригодиться здесь.

PS: Как было указано в комментариях, для общего случая может быть не обязательно, чтобы эти разделенные веса были различными (для этой проблемы это так). Вы можете пересмотреть itertools.combinations.

Answer 4

Я грубо вытеснил ад из второй части.

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

http://pastebin.com/4y2bHCVr

Answer 5

Я не знаю синтаксиса Python, но, возможно, вы можете декодировать этот код Scala; начать с 2-го по-цикла:

def setTo40 (a: Int, b: Int, c: Int, d: Int) = { 

val vec = for (
    fa <- List (0, 1, -1); 
    fb <- List (0, 1, -1); 
    fc <- List (0, 1, -1); 
    fd <- List (0, 1, -1); 
    prod = fa * a + fb * b + fc * c + fd * d; 
    if (prod > 0) 
) yield (prod) 

    vec.toSet 
} 

for (a <- (1 to 9); 
    b <- (a to 14); 
    c <- (b to 20); 
    d = 40-(a+b+c) 
    if (d > 0)) { 
    if (setTo40 (a, b, c, d).size > 39) 
     println (a + " " + b + " " + c + " " + d) 
    } 

Answer 6

С весами [2, 5, 15, 18] можно также измерить все объекты между 1 и 40кг, хотя некоторые из них должны быть измерены косвенно. Например, чтобы измерить объект весом 39 кг, вы сначала сравните его с 40 кг, а баланс отложите на сторону 40 кг (потому что 39 < 40), но тогда, если вы удалите вес 2 кг, он переместится на другую сторону (потому что 39> 38), и таким образом вы можете завершить вес объекта 39 кг.

Более интересно, с весами [2, 5, 15, 45] вы можете измерить все объекты до 67 кг.

Answer 7

Если кто не хочет импортировать библиотеку импорта комбо/завивка, это будет генерировать все возможные стратегии 4-ход ...

# generates permutations of repeated values 
def permutationsWithRepeats(n, v): 
    perms = [] 
    value = [0] * n 
    N = n - 1 
    i = n - 1 

    while i > -1: 
     perms.append(list(value)) 

     if value[N] < v: 
      value[N] += 1 
     else: 
      while (i > -1) and (value[i] == v): 
       value[i] = 0 
       i -= 1 

      if i > -1: 
       value[i] += 1 
       i = N 

    return perms 

# generates the all possible permutations of 4 ternary moves 
def strategy(): 
    move = ['-', '0', '+'] 
    perms = permutationsWithRepeats(4, 2) 

    for i in range(len(perms)): 
     s = '' 

     for j in range(4): 
      s += move[perms[i][j]] 

     print s 

# execute 
strategy()