Wprowadzenie

To jedna z moich ulubionych zagadek matematycznych.

Biorąc pod uwagę cyfrę (powiedzmy 3) i liczbę jej użycia (powiedzmy 5), wygeneruj 10 wyrażeń, które dają 1, 2, 3, 4, 5, 6, 7, 8, 9 i 10 używając tylko +, -, ×, ÷, ^ i √ (root) (nawiasy są dozwolone do grupowania operacji).

Na przykład:

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

Zauważ, że wszystkie powyższe używają pięciu 3 i operacji matematycznych i dają wynik 5. Możesz również użyć 3 przed √, aby określić pierwiastek kostki. To samo dotyczy użycia 4 przed √ do oznaczenia czwartego katalogu głównego.

Zauważ też, że dwa 3 mogą być użyte do utworzenia 33, lub trzy 3 mogą być użyte do utworzenia 333 i tak dalej.

Wyzwanie

• Otrzymasz dwie liczby (obie od 1 do 5) jako argument funkcji, STDIN lub argument wiersza poleceń.
• Pierwsza liczba oznacza, która cyfra ma zostać użyta, a druga liczba oznacza, ile razy ta cyfra ma być użyta w wyrażeniu.
• Twój program powinien wypisać tablicę o rozmiarze 10 (lub 10 liczb oddzielonych spacją), w których każdy element wskazuje, czy wyrażenie matematyczne (przy użyciu tylko dozwolonych operatorów) wynikające z (index + 1)liczby jest możliwe, czy też nie, używając wartości prawda / fałsz.

Na przykład, jeśli dane wejściowe to

1 3

Wtedy wyjście powinno być

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

ponieważ tylko 1, 2, 3 i 10 można wyrazić za pomocą trzech 1.

Wynik

• To jest golf golfowy, więc wygrywa minimalna długość kodu w bajtach.

Premia

Print-em-all [−50]

Odejmij 50 od swojego wyniku, jeśli elementy tablicy wyjściowej są równe całkowitej liczbie możliwych kombinacji, aby uzyskać (index + 1) wartość zamiast wartości prawdziwych lub fałszywych.

Na przykład, jeśli istnieją tylko 3 możliwe kombinacje pięciu 3, które dają wynik 5, wówczas tablica wyjściowa jest ^czwarta wpis powinien 3.

Extreme Maths [−100]

Odejmij 100 od wyniku, jeśli elementy tablicy wyjściowej zawierają co najmniej jedno z rzeczywistych wyrażeń, które wynikają z (index + 1) wartości.

Na przykład, za pomocą pięciu 3'S, tablica wyjściowego 4 ^p wpis może być (3^3 + 3)/(3 + 3), (33 - 3)/(3 + 3)lub3 + 3/3 + 3/3

Przekroczony [−200]

Odejmij 200 od swojego wyniku, jeśli elementy tablicy wyjściowej zawierają wszystkie możliwe kombinacje (oddzielone przez |). Ta premia jest dodawana do Extreme Maths premii , więc w sumie dostajesz −300.

Na przykład, za pomocą pięciu 3'S, 4 macierz wynikową w ^ty element powinien być(3^3 + 3)/(3 + 3)|(33 - 3)/(3 + 3)|3 + 3/3 + 3/3

Uwaga: Dowolne dwa wyrażenia, aby osiągnąć ten sam wynik, powinny być logicznie różne z innym podejściem w obu z nich.

Na przykład, aby uzyskać 5 za pomocą pięciu 3, 3 + 3/3 + 3/3jest to samo co 3/3 + 3 + 3/3lub 3/3 + 3/3 + 3dlatego, że dla każdego z nich zastosowano takie samo podejście. (3^3 + 3)/(3 + 3)i (33 - 3)/(3 + 3)różnią się, ponieważ 30 w liczniku jest osiągane za pomocą różnych podejść.

AKTUALIZACJA : Po przejrzeniu wszystkich odpowiedzi stwierdzono, że wszystkie odpowiedzi miały niedoskonałości z powodu skrajnych przypadków jednostkowych- i √. W związku z tym pominięcie tych przypadkowych przypadków uznano za prawidłowe, o ile chodzi o kompletność odpowiedzi.

To trudne pytanie, ale dość interesujące.

Miłej gry w golfa!

Python 3 (niedoskonały), 449 - 300 = 149

Cierpi na te same wady co rozwiązanie KSab : brak jednoargumentowych operatorów, w pełni nawiasowanych, zawiera równoważne wyrażenia, takie jak (1+1)+1i 1+(1+1). Wyeliminowałem dokładne duplikaty, przekazując wyniki do set(). Dane wyjściowe mogą być nieco brzydsze, aby zaoszczędzić kilka bajtów, ale podoba mi się to w ten sposób. Nie zrobiłem też n-tego roota, ponieważ nie wydaje się, żeby kupowali ci dużo w tym problemie.

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

Uruchomienie zajmie kilka minut, jeśli drugim argumentem będzie 5. Przetestuj, wywołując 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 (niedoskonały) 493 474 - 300 = 174

Istnieje wiele problemów z tym rozwiązaniem, po pierwsze, że ignoruje on zbyt duży wykładnik (taki, w którym wykładnik jest większy niż 100). Właściwie nie sądzę, że to usuwa wszelkie możliwości dla danych wejściowych mniejszych lub równych 5, ale nie jestem w 100% pewien.

Inną rzeczą jest to, że nie bierze pod uwagę żadnych jednorzędowych pierwiastków kwadratowych, ponieważ byłoby to skomplikowane (każde rozwiązanie z dowolnym terminem równym 0 lub 1 dałoby nieskończoną liczbę rozwiązań). Nie bierze również pod uwagę jednoznacznej negacji (symbol „-”) z tego samego powodu, a także faktu, że tak naprawdę nie jestem pewien, czy pytanie zostało zadane.

Zastanawiałem się również, jakie kryteria powinny zdecydować, czy dwa wyrażenia są równoważne, ale nie mogłem znaleźć sposobu na rygorystyczne zdefiniowanie go w sposób, który uznałem za intuicyjny, więc (przynajmniej na razie) nie wdrożyłem czegoś takiego. Oznacza to, że generuje całkiem sporo wyników, a także używa nawiasów w dość naiwny sposób.

Na marginesie myślę, że może to obejmować najdłuższy pojedynczy wiersz kodu, jaki napisałem, zwłaszcza zanim został w pełni zagrany w golfa.

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]

Przykład: („v” oznacza „√”)

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

Oto raczej niezgrabna wersja:

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

Do testowania zalecam zmianę (9) na coś mniejszego, ponieważ jest to liczba uwzględnionych wielu pierwiastków kwadratowych, co ma ogromny wpływ na wydajność.

W końcu zastanawiałem się, czy jednostajny minus jest rzeczywiście potrzebny w niektórych przypadkach…

Mathematica - 246 znaków (nie zgłoszono żadnych bonusów)

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

Wyjaśnienie

Funkcjonować j łączy cyfrowo dwie liczby.

Funkcja zprzyjmuje wynik r, liczbę ni listę funkcji L, z których każda działa na dwóch argumentach. Następnie stosuje sekwencyjnie listę funkcji do argumentów [r,n]za pomocą rekurencji, aż lista będzie pusta, po czym zwraca wynik.

Funkcja aprzyjmuje liczbę ni liczbę kopii t. Tworzy wszystkie krotki długości (t-1) z listy funkcji{Plus, f, Times, g, Power, h, j} i wysyła każdą krotkę przez funkcję z, a następnie zwraca listę wszystkich utworzonych liczb od 1 do 10.

Przykład wykonania a[2,3]powracającego{1, 2, 3, 6, 8} .

Ograniczenia

Ponieważ lista funkcji jest stosowana sekwencyjnie, zużywa jedną kopię liczby za każdym razem, może pominąć niektóre kombinacje. Na przykład, gdy pracuje się na czterech dwójkach, straciłby 22/22 = 1 z powodu niemożności oceny listy funkcji w kolejności. Oczywiście 2/2 * 2/2 = 1 obejmuje ten przypadek.