Генерация числа с использованием заданного списка чисел и арифметических операторов

11

Вам предоставляется список номеров L = [17, 5, 9, 17, 59, 14], пакет операторов O = {+:7, -:3, *:5, /:1}и номер N = 569.

задача

Выведите уравнение, которое использует все числа Lслева и только число Nсправа. Если это невозможно, выведите False. Пример решения:

59*(17-5)-9*17+14 = 569

Ограничения и разъяснения

  • Вы не можете объединять числа ( [13,37]нельзя использовать как 1337)
  • Только натуральные числа и ноль появятся в L.
  • Порядок в Lне имеет значения.
  • Вы должны использовать все числа в L.
  • Только операторы +, -, *, /появятся O.
  • Oможет иметь больше операторов, чем нужно, но, по крайней мере, |L|-1операторов
  • Вы можете использовать каждый оператор любое количество раз до значения в O.
  • Все четыре операции в Oявляются стандартными математическими операциями; в частности, /это нормальное деление с точными дробями.

Точки

  • Чем меньше очков, тем лучше
  • Каждый символ вашего кода дает вам одно очко

Вы должны предоставить версию без гольфа, которая легко читается.

Фон

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

Вычислительная сложность

Как сказал Питер Тейлор в комментариях, вы можете решить сумму с помощью этого:

  1. У вас есть экземпляр подмножества sum (отсюда набор S целых чисел и число x)
  2. L: = S + [0, ..., 0] (| S | умноженное на ноль), N: = x, O: = {+: | S | -1, *: | S | - 1, /: 0, -: 0}
  3. Теперь решите этот случай моей проблемы
  4. Решением для подмножества суммы являются числа S, которые не умножаются на ноль.

Если вы найдете алгоритм, который лучше, чем O (2 ^ n), вы докажете, что P = NP. Так как P против NP является проблемой призов тысячелетия и, следовательно, стоит 1 000 000 долларов США, очень маловероятно, что кто-то найдет решение для этого. Поэтому я удалил эту часть рейтинга.

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

Следующие ответы не являются единственными действительными, существуют и другие решения:

  • ( [17,5,9,17,59,14], {+:7, -:3, *:5, /:1}, 569)
    => 59 * (17-5)- 9 * 17 + 14 = 569
  • ( [2,2], {'+':3, '-':3, '*':3, '/':3}, 1)
    => 2/2 = 1
  • ( [2,3,5,7,10,0,0,0,0,0,0,0], {'+':20, '-':20, '*':20, '/':20}, 16)
    => 5+10-2*3+7+0+0+0+0+0+0+0 = 16
  • ( [2,3,5,7,10,0,0,0,0,0,0,0], {'+':20, '-':20, '*':20, '/':20}, 15)
    => 5+10+0*(2+3+7)+0+0+0+0+0+0 = 15
Мартин Тома
источник
Есть m = |L|? Если да, как вы можете ожидать, что время выполнения не будет зависеть от размера этого списка? Например, [2,2],[+,+,...,+,/],1. Фактически, поскольку n - это O (m), вы можете просто написать все это в терминах m.
Boothby
3
Какую арифметику использовать: точные дробные числа, целые числа ( /div), просто с плавающей запятой и ошибки без надежды на округление, ...?
перестал поворачиваться против часовой стрелки
4
Почему сложные правила подсчета для вычислительной сложности? Существует легкое сокращение от суммы подмножества, поэтому все, что лучше, чем O (2 ^ n), стоит миллион долларов.
Питер Тейлор
1
Связанный: stackoverflow.com/questions/3947937/…
Доктор Белизарий
1
3-й тест не является ложным ...5+10+2*3+7*0+0...
Shmiddty

Ответы:

3

Python 2,7 / 478 символов

L=[17,5,9,17,59,14]
O={'+':7,'-':3,'*':5,'/':1}
N=569
P=eval("{'+l+y,'-l-y,'*l*y,'/l/y}".replace('l',"':lambda x,y:x"))
def S(R,T):
 if len(T)>1:
  c,d=y=T.pop();a,b=x=T.pop()
  for o in O:
   if O[o]>0 and(o!='/'or y[0]):
    T+=[(P[o](a, c),'('+b+o+d+')')];O[o]-=1
    if S(R,T):return 1
    O[o]+=1;T.pop()
  T+=[x,y]
 elif not R:
  v,r=T[0]
  if v==N:print r
  return v==N
 for x in R[:]:
  R.remove(x);T+=[x]
  if S(R,T):return 1
  T.pop();R+=[x]
S([(x,`x`)for x in L],[])

Основная идея заключается в использовании постфиксной формы выражения для поиска. Например, 2*(3+4)в постфиксной форме будет 234+*. Таким образом, проблема состоит в том, чтобы найти частично перестановку L+, Oкоторая оценивается как N.

Следующая версия - версия без гольфа. Стек stkвыглядит так [(5, '5'), (2, '5-3', (10, ((4+2)+(2*(4/2))))].

L = [17, 5, 9, 17, 59, 14]
O = {'+':7, '-':3, '*':5, '/':1} 
N = 569

P = {'+':lambda x,y:x+y,
     '-':lambda x,y:x-y,
     '*':lambda x,y:x*y,
     '/':lambda x,y:x/y}

def postfix_search(rest, stk):
    if len(stk) >= 2:
        y = (v2, r2) = stk.pop()
        x = (v1, r1) = stk.pop()
        for opr in O:
            if O[opr] > 0 and not (opr == '/' and v2 == 0):
                stk += [(P[opr](v1, v2), '('+r1+opr+r2+')')]
                O[opr] -= 1
                if postfix_search(rest, stk): return 1
                O[opr] += 1
                stk.pop()
        stk += [x, y]
    elif not rest:
        v, r = stk[0]
        if v == N: print(r)
        return v == N
    for x in list(rest):
        rest.remove(x)
        stk += [x]
        if postfix_search(rest, stk):
            return True
        stk.pop()
        rest += [x]
postfix_search(list(zip(L, map(str, L))), [])
луч
источник
1
Вау, это короче, чем я ожидал. Я набросал алгоритм, который включал в себя постфиксный префикс <=> преобразования, но мой набросок был не намного короче, чем ваша реализация. Впечатляющие. И спасибо за строительство P[opr](v1, v2). Я никогда не думал о комбинировании лямбд и словарей, как это, хотя сейчас это кажется очевидным.
Мартин Тома
Я пытался проверить ваше решение с помощью моего 4-го теста. Через 2 часа я остановил казнь.
Мартин Тома
@moose Я попытаюсь добавить эвристику, чтобы сделать это быстрее. Но после этого длина кода может удвоиться.
Рэй
Использование дроби, как я сделал здесь, устраняет проблему в вашем ответе. Просто попробуйте для данного экземпляра по ссылке, которую я предоставил. Ваш текущий код не находит ответа, но когда вы используете дробь, он находит.
Мартин Тома