Вам предоставляется список номеров 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
являются стандартными математическими операциями; в частности,/
это нормальное деление с точными дробями.
Точки
- Чем меньше очков, тем лучше
- Каждый символ вашего кода дает вам одно очко
Вы должны предоставить версию без гольфа, которая легко читается.
Фон
Аналогичный вопрос был задан вопрос о переполнении стека. Я подумал, что это может быть интересным испытанием для игры в гольф.
Вычислительная сложность
Как сказал Питер Тейлор в комментариях, вы можете решить сумму с помощью этого:
- У вас есть экземпляр подмножества sum (отсюда набор S целых чисел и число x)
- L: = S + [0, ..., 0] (| S | умноженное на ноль), N: = x, O: = {+: | S | -1, *: | S | - 1, /: 0, -: 0}
- Теперь решите этот случай моей проблемы
- Решением для подмножества суммы являются числа 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./
≡div
), просто с плавающей запятой и ошибки без надежды на округление, ...?5+10+2*3+7*0+0...
Ответы:
Python 2,7 / 478 символов
Основная идея заключается в использовании постфиксной формы выражения для поиска. Например,
2*(3+4)
в постфиксной форме будет234+*
. Таким образом, проблема состоит в том, чтобы найти частично перестановкуL
+,O
которая оценивается какN
.Следующая версия - версия без гольфа. Стек
stk
выглядит так[(5, '5'), (2, '5-3', (10, ((4+2)+(2*(4/2))))]
.источник
P[opr](v1, v2)
. Я никогда не думал о комбинировании лямбд и словарей, как это, хотя сейчас это кажется очевидным.