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

У меня есть одна головоломка, и я хочу ее решить, используя 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.

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

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

Привет

КОВЧЕГ

Ответ 1

Раннее прохождение опроса:

Мы знаем 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, по необходимости.

следующее:

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.

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

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

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]

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

Ответ 2

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

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)

Для объяснения того, как это работает, проверьте ответ, полученный Avaris, это реализация того же алгоритма.

Ответ 3

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

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

Например, если (a, b, c, d) - это первый набор значений в гребенке, мне нужно проверить a, b, c, d, a + 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.

Ответ 4

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

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

http://pastebin.com/4y2bHCVr

Ответ 5

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

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)
  }

Ответ 6

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

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

Ответ 7

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

# 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()