Пришло время заняться математикой

14

Вступление

Это одна из моих любимых математических головоломок.

Учитывая цифру (скажем, 3) и количество раз, чтобы использовать эту цифру (скажем, 5), сгенерируйте 10 выражений, которые приводят к 1, 2, 3, 4, 5, 6, 7, 8, 9 и 10, используя просто +, -, ×, ÷, ^ и √ (корень) (в скобках разрешено группировать операции).

Например:

(3^3 + 3)/(3 + 3) = (33 - 3)/(3 + 3) = 3 + 3/3 + 3/3 = 5

Обратите внимание, что все вышеперечисленное использует пять 3 и математические операции и приводит к 5. Вы также можете использовать 3 перед √ для обозначения корня куба. То же самое касается использования 4 перед √ для обозначения четвертого корня.

Также обратите внимание, что два 3-х можно использовать для формирования 33, или три 3-х можно использовать для формирования 333 и так далее.

Вызов

  • Вам будет дано два числа (оба в диапазоне от 1 до 5) в качестве аргумента функции, STDIN или аргумента командной строки.
  • Первое число обозначает, какую цифру использовать, а второе число указывает, сколько раз эта цифра должна использоваться в выражении.
  • Ваша программа должна вывести массив размером 10 (или 10 чисел, разделенных пробелами), где каждый элемент обозначает, возможно ли математическое выражение (используя только разрешенные операторы), приводящее к (index + 1)числу, или не использует значение truey / false.

Например, если вход

1 3

Тогда вывод должен быть

[1, 1, 1, 0, 0, 0, 0, 0, 0, 1]

потому что только 1, 2, 3 и 10 можно выразить с помощью трех 1.

Гол

  • Это код-гольф, поэтому выигрывает минимальная длина кода в байтах.

бонус

Print-em-all [−50]

Вычтите 50 из вашей оценки, если элементы выходного массива равны общему количеству вероятных комбинаций, чтобы получить (index + 1)значение вместо истинных или ложных значений.

Например, если есть только 3 возможные комбинации из пяти 3, что приводит к 5, то четвертая запись выходного массива должна быть 3.

Экстремальная математика [−100]

Вычтите 100 из вашей оценки, если элементы выходного массива содержат хотя бы одно из фактических выражений, которые приводят к (index + 1)значению.

Например, если с помощью пяти 3 - х, 4 выходного массива го входа может быть либо (3^3 + 3)/(3 + 3), (33 - 3)/(3 + 3)или3 + 3/3 + 3/3

Избыток [−200]

Вычтите 200 из вашей оценки, если элементы выходного массива содержат все возможные комбинации (разделенные |). Этот бонус добавляется к бонусу Extreme Maths , поэтому вы получаете в сумме -300.

Например, если используется пять 3, 4- й элемент выходного массива должен быть(3^3 + 3)/(3 + 3)|(33 - 3)/(3 + 3)|3 + 3/3 + 3/3

Примечание. Любые два выражения для достижения одного и того же результата должны логически отличаться друг от друга с использованием разных подходов.

Например, чтобы получить 5 с использованием пяти 3, то 3 + 3/3 + 3/3же самое, что 3/3 + 3 + 3/3или 3/3 + 3/3 + 3для каждого из них, используется тот же подход. (3^3 + 3)/(3 + 3)и (33 - 3)/(3 + 3)отличаются, так как 30 в числителе достигается с помощью различных подходов.

ОБНОВЛЕНИЕ : после просмотра всех ответов, было обнаружено, что все ответы имеют недостатки из-за крайних случаев унарных -и √. Таким образом, пропуск этих крайних случаев считался нормальным, если речь идет о полноте ответов.

Это сложный вопрос, но довольно интересный.

Удачного игры в гольф!

code-golf math arithmetic expression-building оптимизатор
источник
1
Извините, это может быть глупо, но как вы получаете 10 всего за три 1с?
FryAmTheEggman
3
@FryAmTheEggman 11-1
Оптимизатор
1
Ах, так я был туп: p
FryAmTheEggman
4
Это очень расплывчатое правило. Я могу решить, что квадратный корень из 1, квадратный корень из квадратного корня из 1 и т. Д. - это разные подходы, и у меня есть бесконечное количество ответов. Отличается ли a + b от b + a? (-A) * (-b) отличается от b * a?
Feersum
2
Я знаю об этом, но я не могу представить 4 ^ (4 ^ (4 ^ (4 ^ 4))) в любом обычном числовом формате - сохраняя 4 ^ (4 ^ (4 ^ 4)), поскольку целое число уже требует больше битов чем есть атомы во вселенной). Поэтому, если я не использую систему компьютерной алгебры, способную обрабатывать такие числа (если она вообще существует), я должен рассматривать их как особые случаи. Это, однако, почти наверняка требует больше персонажей, чем я выигрываю из-за перебором Поэтому эти награды бессмысленны, если вы не исключаете несколько квадратных корней.
Wrzlprmft

Ответы:

1

Python 3 (несовершенный), 449 - 300 = 149

Страдает от тех же недостатков, что и решение KSab : ни один унарный оператор, полностью заключенный в скобки, не содержит эквивалентных выражений, подобных (1+1)+1и 1+(1+1). Я удалил точные дубликаты, передав результаты set(). Вывод может быть немного уродливым, чтобы сохранить несколько байтов, но мне это нравится. Я также не делал nth root, потому что не похоже, что они много покупают в этой проблеме.

R=range
E=lambda z:eval(z.replace("^","**"))
def m(d,n):_=R(1,11);s={i:[]for i in _};r=R(1,n);n<2 and s[d].append(str(d));d=str(d);t=[[(d*i,i)for i in r]]+[[]]*n;h=[];[(h.append("("+A+o+B+")"),t[l].append((h[0],a+b))if a+b<n else E(*h)in _ and s[E(*h)].append(h[0]),h.pop())for l in r for j in R(l)for A,a in t[j]for k in R(l)for B,b in t[k]if a+b<=n for o in"+-*/^"if(o=="^"and-~-(0<E(B)<9)or 0==E(B)and"/"==o)-1];[print(i,set(s[i])or'')for i in _]

Это займет несколько минут, если второй аргумент равен 5. Проверьте, вызвав m(digit, number):

>>> m(1,3)
1 {'((1*1)^1)', '(1^(1+1))', '((1-1)+1)', '((1/1)/1)', '((1*1)*1)', '((1^1)/1)', '(1*(1*1))', '(1^(1*1))', '(1+(1-1))', '(1^(1^1))', '((1^1)*1)', '(1^(1/1))', '((1/1)*1)', '(1-(1-1))', '(1/(1^1))', '(1/(1*1))', '(1/(1/1))', '(1*(1^1))', '((1+1)-1)', '((1*1)/1)', '((1^1)^1)', '(1*(1/1))', '((1/1)^1)'}
2 {'(1*(1+1))', '((1^1)+1)', '((1+1)/1)', '((1*1)+1)', '((1+1)^1)', '(1+(1*1))', '((1/1)+1)', '(1+(1^1))', '(1+(1/1))', '((1+1)*1)'}
3 {'((1+1)+1)', '(1+(1+1))'}
4 
5 
6 
7 
8 
9 
10 {'(11-1)'}
>>> m(3,3)
1 {'((3/3)^3)'}
2 {'(3-(3/3))', '((3+3)/3)'}
3 {'(3-(3-3))', '((3-3)+3)', '((3/3)*3)', '(3*(3/3))', '(3/(3/3))', '((3+3)-3)', '(3^(3/3))', '(3+(3-3))', '((3*3)/3)'}
4 {'((3/3)+3)', '(3+(3/3))'}
5 
6 {'((3*3)-3)'}
7 
8 
9 {'(3+(3+3))', '((3+3)+3)', '((3^3)/3)'}
10
DLosc
источник
4

Питон (несовершенный) 493 474 - 300 = 174

Существует довольно много проблем с этим решением, во-первых, оно игнорирует любой показатель слишком большой (любой, в котором показатель больше 100). Я на самом деле не думаю, что это удаляет какие-либо возможности для входных данных, меньших или равных 5, но я не уверен на 100%.

Другое дело, что он не учитывает унарные квадратные корни, поскольку это усложняется (любое решение с любым членом, равным 0 или 1, приведет к бесконечному числу решений). Он также не учитывает унарное отрицание (символ «-») по той же причине, а также тот факт, что я на самом деле не уверен, задан ли вопрос для него.

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

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

R=range
F=lambda s:lambda a,b:eval(s)
L=lambda D,N:[(int(str(D)*N),str(D)*N)]+[(o(u,v),"(%s%s%s)"%(s,c,t))for p in R(1,N)for u,s in L(D,p)for v,t in L(D,N-p)for c,o in[('+',F('a+b')),('-',F('a-b')),('*',F('a*b')),('/',F("1.*a/b if b else''")),('^',F("''if(a<0 and int(b)!=b)|(a and b<0)|(b>99)else a**b")),('v',F("b**(1./a)if a and(a>=0 or b)and(b>=0 or int(1./a)==1./a)&(1./a<99)else''"))]if o(u,v)!='']
A=L(*input())
for i in R(11):
 for v,s in A:
    if v==i:print i,s[1:-1]

Пример: («v» представляет «√»)

2,3

0 2*(2-2)
0 2v(2-2)
0 (2-2)*2
0 (2-2)/2
0 (2-2)^2
1 2^(2-2)
1 2-(2/2)
1 2v(2/2)
1 (2/2)^2
2 2v(2+2)
2 2+(2-2)
2 2-(2-2)
2 2v(2*2)
2 2*(2/2)
2 2/(2/2)
2 2^(2/2)
2 2v(2^2)
2 (2+2)-2
2 (2+2)/2
2 (2-2)+2
2 (2*2)-2
2 (2*2)/2
2 (2/2)*2
2 (2/2)v2
2 (2^2)-2
2 (2^2)/2
3 2+(2/2)
3 (2/2)+2
6 2+(2+2)
6 2+(2*2)
6 2+(2^2)
6 (2+2)+2
6 (2*2)+2
6 (2^2)+2
8 2*(2+2)
8 2*(2*2)
8 2*(2^2)
8 (2+2)*2
8 (2*2)*2
8 (2^2)*2
KSab
источник
Я нашел пару вещей, которые вы можете сделать, чтобы сократить L:L=lambda D,N:[(int(str(D)*N),str(D)*N)]+[(o(u,v),"(%s%s%s)"%(s,c,t))for p in R(1,N)for u,s in L(D,p)for v,t in L(D,N-p)for c,o in[('+',F('a+b')),('-',F('a-b')),('*',F('a*b')),('/',F("1.*a/b if b else''")),('^',F("''if(a<0 and int(b)!=b)|(a and b<0)or b>100 else a**b")),('v',F("''if a==0 or(b<0 and int(1./a)!=(1./a))or(b or a<0)or(1./a)>100 else b**(1./a)"))]if o(u,v)!='']
FryAmTheEggman
Извините, этот комментарий выглядит очень плохо: Во всяком случае, чтобы объяснить: при сравнении с 0, я пытался опровергнуть утверждение, а затем поменять последствия. Я также нашел несколько мест для использования |и &вместо orи and. Оба эти трюки можно использовать для сокращения последнего вызова F, но для этого потребуются некоторые деморганы, и у меня не хватит времени клюва; p
FryAmTheEggman
@FryAmTheEggman О, это хороший улов, я обновил свой ответ тем, что вы написали, и когда у меня будет время, я посмотрю последний. Те условия для проверки правильности ввода стали немного более здоровенными, чем я ожидал: /
KSab
+10 за блеск вложенных evalлямбд и - мне потребовалось много времени, чтобы понять вашу вторую строчку! Я думаю, что я заставил тебя победить на "самой длинной одиночной линии". ;) Я согласен игнорировать большие показатели; на самом деле, я думаю, что любой показатель больше 9 не будет полезен (за исключением случая, когда базовое значение равно 1).
DLosc
@DLosc Ну, один сценарий, который вы можете иметь, это что-то вроде 3 = 33 √ (3 ^ 33). На самом деле, когда я пишу это, я понимаю, что две (возможно, только две?) Комбинации, которые мой ответ пропускает, являются 4 = (4^4) √ (4 ^ (4^4))эквивалентным выражением с 5s. По общему признанию корни, кажется, не добавляют много к проблеме, поскольку подавляющее большинство из них или используются как no-ops на 0 или 1, no-ops, когда root равен 1, или просто для отмены мощности.
KSab
3

Питон 3 - 349 346

r=range
l=lambda s:eval("lambda a"+s)
def T(u,f,X,Y):
    try:return u(f(X,Y))
    except:0
c=l(',x:{x}.union(*[{u(int("1"*a)*x)}|{T(u,f,X,Y)for j in r(1,a)for X in c(j,x)for Y in c(a-j,x)for f in[l(",b:a%sb"%o)for o in{"**"}|set("+-*/")]+[l(",b:a**b**-1")]}for u in[l(":-a")]+[l(":a**.5**%i"%k)for k in r(9)]])')
R=l(",i:[{n+1}<c(i,a)for n in r(10)]")

Вот довольно нелепая версия:

def R(x,i):
    # Unary Operations
    U = [lambda a:-a] + [eval("lambda a:a**(1/2.**%i)" % j) for j in range(9)]
    # Binary Operations
    F = [eval("lambda a,b:a%sb"%o) for o in ["+","-","*","/","**"]] + [lambda a,b:a**(1./b)]

    def combos(i):
        L = {x}
        for u in U:
            # 3, 33, 333, etc.
            L |= {u(int(str(x)*i))}

            for j in range(1,i):
                for X in combos(j):
                    for Y in combos(i-j):
                        for f in F:
                            # To avoid trouble with division by zero, overflows and similar:
                            try:
                                L |= {u(f(X,Y))}
                            except:
                                pass
        return L

    return [n in combos(i) for n in range(1,11)]

Для тестирования я рекомендую изменить его (9)на что-то меньшее, так как это число множественных квадратных корней, которое имеет огромное значение для производительности.

Наконец, это заставило меня задуматься, нужен ли в каком-то случае унарный минус ...

Wrzlprmft
источник
1
Я думаю, что вы правы насчет унарного слова «-», вероятно, ничего не добавляющего (по крайней мере, к базовому вопросу без бонусов). Единственный нетривиальный сценарий, о котором я могу думать, был бы чем-то подобным 1 = 3^3 * 3^(-3), но даже учитывая их, я сомневаюсь, что есть какие-то цифры, для которых это возможное решение, когда нет других.
KSab
1
Вы можете сохранить 3 байта, используя a**.5**%iвместо a**(1/2**%i)вычисления несколько квадратных корней.
DLosc
@DLosc: Действительно, спасибо.
Wrzlprmft
Вы можете сохранить шесть байтов, уменьшив отступ четырех пробелов до одного пробела.
Бета-распад
@BetaDecay: я никогда не использую отступы в четыре пробела (дрожь), я использую вкладки. Просто загляните в источник моего поста. Обмен стека просто отображает их как четыре пробела.
Wrzlprmft
2

Mathematica - 246 символов (бонусы не требуются)

f[x_,y_]:=x-y
g[x_,y_]:=x/y
h[x_,y_]:=x^(1/y)
j[x_,y_]:=FromDigits@Join[IntegerDigits@x,{y}]
z[{r_,n_,L_}]:=z[{L[[1]][r,n],n,Rest@L}]
z[{r_,n_,{}}]:=r
a[n_,t_]:=Union@Select[z[{n,n,#}]&/@Tuples[{Plus,f,Times,g,Power,h,j},t-1],IntegerQ@#&&0<#<11&]

объяснение

Функция jобъединяет два числа в цифровом виде.

Функция zполучает результат r, число nи список функций L, каждая из которых работает с двумя аргументами. Затем он последовательно применяет список функций к аргументам [r,n]с использованием рекурсии, пока список не станет пустым, после чего он возвращает результат.

Функция aпринимает количество nи количество копий t. Он создает все кортежи длины (t-1) из списка функций {Plus, f, Times, g, Power, h, j}и отправляет каждый кортеж через функцию z, затем возвращает список всех созданных чисел от 1 до 10.

Пример выполнения a[2,3]возвращается {1, 2, 3, 6, 8}.

Ограничения

Поскольку список функций применяется последовательно, потребляя одну копию числа каждый раз, он может пропустить некоторые комбинации. Например, при работе с четырьмя двойками он пропустит 22/22 = 1 из-за невозможности оценить список функций не по порядку. Конечно, 2/2 * 2/2 = 1 охватывает этот случай.

фосген
источник