Generuj liczby Friedmana

9

Liczba Friedmana to liczba, którą można wyrazić, stosując podstawowe operacje matematyczne (^, /, *, +, -) do wszystkich jej cyfr. Operacje nie muszą być stosowane do poszczególnych cyfr, ale wszystkie cyfry muszą być zaangażowane. Oznacza to, że 121 = 11 ^ 2 -> wszystkie cyfry są zaangażowane, ale 1 i 1 zostały połączone razem, aby uzyskać 11.

Użycie nawiasów jest dozwolone, ale trywialne rozwiązanie x= (x)nie jest prawidłowym rozwiązaniem. Również nie jest ważny x= +x.

Przykłady

  • 25 = 5 ^ 2
  • 121 = 11 ^ 2
  • 343 = (3 + 4) ^ 3
  • 2048 = (8 ^ 4) / 2 + 0

Napisz program, który pobierze dodatnie dwie liczby całkowite i wydrukuje liczbę liczb Friedmana w tym zakresie (włącznie) oraz liczby z wyrażeniami w kolejnych wierszach.

Wejście -

n m    | n, m integers, n>=0, m>n

Wynik -

count    | number of Friedman numbers in the given range
fn1 exp1 | Friedman number, expression
fn2 exp2
fn3 exp3
.
.
.

Najkrótszy kod opublikowany do niedzieli 29 lipca 00:00 GMT zostanie zwycięzcą.

Elssar
źródło
2
Czy możesz dodać przykładowe liczby Friedmana i wyjaśnić, jak to /działa? Na przykład co to jest 1/3?
JPvdMerwe
Liczba jest wyrażana poprzez zastosowanie operacji do wszystkich jej cyfr. tj. 25 = 5 ^ 2, 126 = 6 * 21, 343 = (3 + 4) ^ 3 itd.
elssar
Czy pozwalasz na jednoargumentowy minus? na przykład -5?
JPvdMerwe
@JPvdMerwe sprawdź specyfikację wejściową, nie musisz tego robić, ale jeśli chcesz, powal się. Chociaż jednoznaczny plus nie jest dozwolony. tzn. +5 nie jest poprawnym rozwiązaniem
elssar
1
Nie odpowiedziałeś na pytanie JPvdMerwe dotyczące podziału. Czy to musi być dokładne? Czy wyniki pośrednie mogą być niecałkowite?
Peter Taylor,

Odpowiedzi:

3

Rubinowy, 456438408 390 370 349 344 334 [ustalony]

g={}
f=->a,b{a.permutation(b).to_a.uniq.flatten.each_slice b}
F,T=$*
([F.to_i,10].max..T.to_i).map{|c|f[a="#{c}".split(''),v=a.size].map{|m|f[[?+,?-,?*,?/,'','**'],v-1].map{|w|(d=(s=m.zip(w)*'').size)==v&&next
0.upto(d){|y|y.upto(d+1){|u|begin(r=eval t="#{s}".insert(y,?().insert(u,?)))==c&&g[r]=t
rescue Exception
end}}}}}
p g.size,g

Wynik:

% ruby ./friedman-numbers.rb 1 300
9
{25=>"(5)**2", 121=>"(11)**2", 125=>"5**(2+1)", 126=>"(6)*21", 127=>"(2)**7-1", 128=>"2**(8-1)", 153=>"(3)*51", 216=>"6**(1+2)", 289=>"(9+8)**2"}

Działa również stosunkowo szybko dla większych liczb:

% time ruby friedman-numbers.rb 3863 3864   
1
{3864=>"(6**4-8)*3"}
ruby friedman-numbers.rb 3863 3864  14.05s user 0.17s system 99% cpu 14.224 total
defhlt
źródło
1
Pobiegłem go z wejściem 5 40i otrzymał wynik: [11, "11**1", 21, "21**1", 31, "31**1", 41, "41**1"]. Nie ma tam śladu 25i myślę, że właściwym rozwiązaniem (na przykład dla 21) 2*1nie jest21**1
Cristian Lupascu,
@ w0lf Dziękujemy! Myślę, że to naprawiłem.
defhlt
Tak, teraz działa świetnie.
Cristian Lupascu,
@ w0lf dodał wiele znaków, aby sformatować dane wyjściowe zgodnie z wymaganiami
defhlt
2 można uzyskać poprzez zastąpienie znaków '+-*/'.chars.to_a+['','**']z["+","-","*","/","","**"]
Cristian Lupaşcu
4

Python 2,7 - 380 378 372 371 367 363 357 354 352 348 336 znaków

Po prostu proste wyszukiwanie brutalnej siły.

from itertools import*
s=lambda x:[x]['1'>x>'0':]+['(%s%s%s)'%f for i in range(1,len(x))for f in product(s(x[:i]),'*/-+^',s(x[i:]))]
def E(e):
 try:return eval(e.replace("^","**"))
 except:0
A={i:e for i in range(input(),input()+1)for x in permutations(`i`)for e in s("".join(x))[x>='1':]if E(e)==i}
print len(A)
for v in A:print v,A[v]

Przykładowy przebieg:

1
300
9
128 (2^(8-1))
289 ((9+8)^2)
216 (6^(1+2))
121 (11^2)
153 (3*51)
25 (5^2)
125 (5^(2+1))
126 (6*21)
127 ((2^7)-1)

Wyjaśnienie:

s(x) to funkcja, która pobiera ciąg zawierający sekwencję cyfr i zwraca wszystkie wyrażenia korzystające z tych cyfr w tej kolejności.

[x]['1'>x>'0':] ewaluuje do listy zawierającej x, jeśli x jest równe „0” lub ciąg cyfr nie rozpoczynający się od „0”; w przeciwnym razie przejdzie do pustej listy. Zasadniczo dotyczy to przypadku, w którym łączę wszystkie cyfry razem.

['(%s%s%s)'%f for i in range(1,len(x))for f in product(s(x[:i]),'*/-+^',s(x[i:]))] w zasadzie dzieli x na dwie części (obie o niezerowej długości), wywołuje s () na każdej części i łączy wszystkie wyniki wraz z pewnym operatorem między nimi za pomocą product ().

E(e) jest w zasadzie bezpieczną ewaluacją. Zwraca wartość e, jeśli e jest poprawny, a Brak w przeciwnym razie.

A={i:e for i in range(input(),input()+1)for x in permutations(`i`)for e in s("".join(x))[x>='1':]if E(e)==i}

Zasadniczo ten kod wypróbowuje wszystkie liczby z zakresu, permutuje ich cyfry i testuje każde wyrażenie s () generuje dla tej permutacji, ignorując pierwsze wyrażenie, jeśli x nie zaczyna się od „0”, ponieważ jeśli x nie zaczyna się od „ 0 ', wówczas pierwszym wyrażeniem będzie po prostu x.

Wersja alternatywna - 397 znaków

Oto mój kod, jeśli musisz używać ułamków:

from fractions import*
from itertools import*
s=lambda x:["Fraction(%s)"%x]['1'>x>'0':]+['(%s%s%s)'%f for i in range(1,len(x))for f in product(s(x[:i]),'*/-+^',s(x[i:]))]
def E(e):
 try:return eval(e.replace("^","**"))
 except:0
A={i:e for i in range(input(),input()+1)for x in permutations(`i`)for e in s("".join(x))[x>='1':]if E(e)==i}
print len(A)
for v in A:print v,A[v].replace("Fraction","")
JPvdMerwe
źródło
Nie sądzę, if len(x)<2aby kiedykolwiek działał poprawnie s. Ponadto, można wymienić formatz "a[Fraction(%s)%s%s]='(%s%s%s)'"%(x[:i],o,v,x[:i],o,A)aby zaoszczędzić 4 znaków.
beary605
@ beary605: Czasami jest to prawda, gdy i = len (x) -1, następne wywołanie otrzyma pojedynczy znak. Co do drugiego punktu, dziękuję! :)
JPvdMerwe
hę ... except:0mądry ... bardzo mądry. Zapamiętam
Ev_genus,
Podaj przykładowe dane wyjściowe.
DavidC
1
Nie, wciąż działa. Teraz muszę przenieść komputer, ale pozwolę mu działać przez kilka dni i zobaczę, czy się skończy.
JPvdMerwe
3

Python3 (436) (434) (443)

To było trudne. Mogę oszczędzić kilka znaków, jeśli sprawię, że wydruk będzie bardziej natywny.

from itertools import*
r={};k=product;m=map
q=lambda n,h=1:["("+i+c+j+")"for(i,j),c in k(chain(*[k(*m(q,f))for f in sum(([(x[:q],x[q:])for q in range(1,len(x))]for x in m("".join,permutations(n))),[])]),list("+-*/^")+[""]*h)]if 1<len(n)else[n]*h
a,b=m(int,m(input,"nm"))
for i,j in chain(*[k(q(str(n),0),[n])for n in range(a,b+1)]):
    try:exec("if eval(%r)==j:r[j]=i"%i.replace("^","**"))
    except:0
print(len(r))
for j,i in r.items():print(i,j)

Wynik

n100
m200
6
(2^(8-1)) 128
(3*(51)) 153
((11)^2) 121
(5^(1+2)) 125
(6*(21)) 126
((2^7)-1) 127
Rodzaj Ev
źródło
1
Masz więc wiele sprytnych sztuczek; powinienem jednak wspomnieć, że nie radzisz sobie z cyframi od 1 do 9, a Twój wkład nie obejmuje. Możesz usunąć 2 znaki, usuwając spację po "("+i+c+j+")"i zastępując len(n)>1ją, 1<len(n)po czym możesz usunąć spację po tym wyrażeniu.
JPvdMerwe
Targi. Naprawiono wszystkie +7 znaków
Ev_genus
Możesz zastąpić ostatni wiersz, for j in r:print(r[j],j)aby zapisać 7 znaków.
JPvdMerwe
1

Mathematica 456 416 402 404 400 396 znaków

<< Combinatorica`; l = Length; p = Permutations; f = Flatten; c = Cases;
u[d_, o_, s_] := 
 Fold[#2[[1]] @@ If[s == 1, {#1, #2[[-1]]}, {#2[[-1]], #1}] &, 
 d[[1]], Thread@{o, Rest@d}];
q[t_, r_] := {u[t, #, r], u[HoldForm /@ t, #, r]} & /@ 
p[{Plus, Subtract, Times, Divide, Power}, {l@t - 1}];
v[m_, n_] := (t = Table[Union@
  c[f[{#~q~1, #~q~0} & /@ 
     f[p /@ c[
        FromDigits /@ # & /@ 
         f[SetPartitions /@ p@IntegerDigits@j, 1], x_ /; l@x > 1],
       1], 2], {j, _}], {j, m, n}]~f~1; {l@t}~Join~t)

Przykład :

v[1,300]//TableForm

Wyjście :

wyjście Friedmana

DavidC
źródło