Introdução

Este é um dos meus quebra-cabeças matemáticos favoritos.

Dado um dígito (digamos 3) e o número de vezes para usá-lo (digamos 5), gere 10 expressões que resultam em 1, 2, 3, 4, 5, 6, 7, 8, 9 e 10 usando apenas +, -, ×, ÷, ^ e √ (raiz) (colchetes são permitidos para agrupar operações).

Por exemplo:

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

Observe que todas as opções acima usam cinco 3 e as operações matemáticas e resultam em 5. Você também pode usar um 3 antes de √ para indicar uma raiz do cubo. O mesmo vale para o uso de 4 antes de √ para denotar uma quarta raiz.

Observe também que dois 3 podem ser usados ​​para formar 33 ou três 3 podem ser usados ​​para formar 333 e assim por diante.

Desafio

• Você receberá dois números (ambos variando de 1 a 5) como argumento de função, STDIN ou argumento de linha de comando.
• O primeiro número indica qual dígito usar e o segundo número indica o número de vezes que esse dígito deve ser usado na expressão.
• Seu programa deve gerar uma matriz de tamanho 10 (ou 10 números separados por espaço), em que cada elemento indica se uma expressão matemática (usando apenas os operadores permitidos) resultante do (index + 1)número é possível ou não usando um valor de verdade / falsidade.

Por exemplo, se a entrada for

1 3

Então a saída deve ser

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

porque apenas 1, 2, 3 e 10 podem ser expressos usando três 1s.

Ponto

• Este é um código-golf, portanto o comprimento mínimo do código em bytes vence.

Bônus

Imprimir em tudo [-50]

Subtraia 50 da sua pontuação se os elementos da matriz de saída forem iguais ao número total de combinações plausíveis para obter o (index + 1)valor em vez de valores verdadeiros ou falsos.

Por exemplo, se há apenas três possíveis combinações de cinco 3 de que resultam a 5, em seguida, a matriz de saída de 4 ^th entrada deve ser de 3.

Matemática Extrema [-100]

Subtraia 100 da sua pontuação se os elementos da matriz de saída contiverem pelo menos uma das expressões reais que resultam no (index + 1)valor.

Por exemplo, se usando cinco de 3, 4 da matriz de saída ^th entrada pode ser qualquer um (3^3 + 3)/(3 + 3), (33 - 3)/(3 + 3)ou3 + 3/3 + 3/3

Excesso de habilidades [-200]

Subtraia 200 da sua pontuação se os elementos da matriz de saída contiverem todas as combinações possíveis (separadas por |). Este bônus é adicionado sobre o bônus Extreme Maths , para que você obtenha -300 no total.

Por exemplo, se usando cinco de 3, 4 da matriz de saída ^th elemento deve ser(3^3 + 3)/(3 + 3)|(33 - 3)/(3 + 3)|3 + 3/3 + 3/3

Nota: Quaisquer duas expressões para obter o mesmo resultado devem ser logicamente diferentes, com uma abordagem diferente em ambas.

Por exemplo, obter 5 usando cinco 3 3 + 3/3 + 3/3é igual 3/3 + 3 + 3/3ou 3/3 + 3/3 + 3porque a mesma abordagem é adotada para cada um deles. (3^3 + 3)/(3 + 3)e (33 - 3)/(3 + 3)diferem, pois os 30 no numerador são alcançados por diferentes abordagens.

ATUALIZAÇÃO : Após analisar todas as respostas, verificou-se que todas as respostas apresentavam imperfeições devido a casos extremos de unários -e √. Assim, a falta desses casos extremos foi considerada aceitável, na medida em que as respostas estejam completas.

Essa é uma pergunta difícil, mas interessante.

Feliz golfe!

Python 3 (imperfeito), 449 - 300 = 149

Sofre com as mesmas deficiências da solução da KSab : nenhum operador unário, totalmente entre parênteses, contém expressões equivalentes como (1+1)+1e 1+(1+1). Eu eliminei duplicatas exatas passando os resultados para set(). A saída pode ser um pouco mais feia para salvar alguns bytes, mas eu gosto dessa maneira. Eu também não criei enésimas raízes, porque não parece que elas compram muito nesse problema.

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 _]

Isso levará alguns minutos para ser executado se o segundo argumento for 5. Teste chamando 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 

Python (imperfeito) 493 474 - 300 = 174

Há um número razoável de problemas com esta solução, primeiro que ela ignora qualquer expoente muito grande (qualquer um em que o expoente seja maior que 100). Na verdade, acho que isso não remove possibilidades de entradas menores ou iguais a 5, mas não tenho 100% de certeza.

Outra coisa é que ela não considera nenhuma raiz quadrada unária, pois seria complicada (qualquer solução com qualquer termo igual a 0 ou 1 produziria um número infinito de soluções). Também não considera nenhuma negação unária (o símbolo '-') pela mesma razão, bem como o fato de que não tenho certeza se a pergunta foi feita.

Também considerei quais critérios deveriam decidir se duas expressões eram equivalentes, mas não consegui encontrar uma maneira de defini-la rigorosamente de uma maneira que me pareceu intuitiva; portanto (pelo menos por enquanto) não implementei nada disso. Isso significa que ele produz muitos resultados e também usa parênteses de uma maneira bastante ingênua.

Em uma nota lateral, acho que isso pode incluir a linha de código mais longa que eu escrevi, especialmente antes de ter sido totalmente jogada no golfe.

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]

Exemplo: ('v' representa '√')

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

Python 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)]")

Aqui está uma versão bastante não-destruída:

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

Para testar, recomendo mudar (9)para algo menor, pois esse é o número de múltiplas raízes quadradas consideradas, o que tem um enorme impacto no desempenho.

Finalmente, isso me fez pensar, se o menos unário é realmente necessário em alguns casos ...

Mathematica - 246 caracteres (nenhum bônus reivindicado)

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&]

Explicação

A função jconcatena dois números digitos.

A função zobtém um resultado r, número ne lista de funções L, cada uma delas operando com dois argumentos. Em seguida, aplica a lista de funções seqüencialmente aos argumentos [r,n]usando recursão, até que a lista esteja vazia e, em seguida , retorna o resultado.

A função aobtém um número ne um número de cópias t. Ele cria todas as tuplas de comprimento (t-1) da lista de funções {Plus, f, Times, g, Power, h, j}e envia cada tupla através da função z; em seguida, retorna uma lista de todos os números de 1 a 10 que foram criados.

Exemplo de execução a[2,3]retornando {1, 2, 3, 6, 8}.

Limitações

Como a lista de funções é aplicada seqüencialmente, consumindo uma cópia do número a cada vez, ela pode perder algumas combinações. Por exemplo, ao operar com quatro pares, ele perderia 22/22 = 1 devido à sua incapacidade de avaliar a lista de funções fora de ordem. Obviamente, 2/2 * 2/2 = 1 cobre este caso.