Pure Evil: Eval
a=lambda x,y:(y<0)*x or eval("a("*9**9**9+"x**.1"+",y-1)"*9**9**9)
print a(input(),9**9**9**9**9)//1
Instrukcja wewnątrz eval tworzy ciąg o długości 7 * 10 10 10 10 10 10 8.57, który składa się wyłącznie z wywołań funkcji lambda, z których każde będzie konstruować ciąg o podobnej długości, tak długo, aż w końcu stanie ysię 0. Pozornie ma to tę samą złożoność co poniższa metoda Eschew, ale zamiast polegać na logice „i-lub-lub”, po prostu rozbija gigantyczne łańcuchy razem (a wynik netto jest coraz większy stosów ... prawdopodobnie?).
Największą ywartością, jaką mogę podać i obliczyć bez zgłaszania błędu przez Python, jest 2, co jest już wystarczające do zmniejszenia wartości wejściowej max-float do zwracania 1.
Łańcuch o długości 7,625,597,484,987 jest po prostu zbyt duży: OverflowError: cannot fit 'long' into an index-sized integer.
Powinienem przestać
Unikaj Math.log: Przechodząc do (dziesiątego) źródła (problemu), Wynik: funkcja skutecznie nie do odróżnienia od y = 1.
Importowanie biblioteki matematycznej ogranicza liczbę bajtów. Pozbądźmy się tego i zastąpmy log(x)funkcję czymś w przybliżeniu równoważnym: x**.1i która kosztuje w przybliżeniu taką samą liczbę znaków, ale nie wymaga importu. Obie funkcje mają podliniowe wyjście względem wejścia, ale x 0,1 rośnie jeszcze wolniej . Jednak nie obchodzi nas to zbytnio, dbamy tylko o to, że ma ten sam podstawowy wzorzec wzrostu w odniesieniu do dużych liczb, zużywając porównywalną liczbę znaków (np. x**.9Jest taka sama liczba znaków, ale rośnie szybciej, więc jest to pewna wartość, która wykazałaby dokładnie taki sam wzrost).
Teraz, co zrobić z 16 postaciami. Co powiesz na ... rozszerzenie naszej funkcji lambda o właściwości Sekwencji Ackermanna? Ta odpowiedź dla dużej liczby zainspirowała to rozwiązanie.
a=lambda x,y,z:(z<0)*x or y and a(x**.1,z**z,z-1)or a(x**.1,y-1,z)
print a(input(),9,9**9**9**99)//1
z**zCzęść tutaj powstrzymuje mnie przed uruchomieniem tej funkcji w dowolnym miejscu blisko do rozsądnych wejść do yi znajwiększe wartości mogę wykorzystać to 9 i 3 , dla którego wrócę wartość 1,0, nawet dla największych podpór pływak Pythona (Uwaga: podczas 1,0 jest liczbowo większy niż 6.77538853089e-05, zwiększone poziomy rekurencji zbliżają wyjście tej funkcji do 1, pozostając większe niż 1, podczas gdy poprzednia funkcja przenosiła wartości bliższe 0, pozostając większa niż 0, w ten sposób nawet umiarkowaną rekurencję dla tej funkcji powoduje tyle operacji, że liczba zmiennoprzecinkowa traci wszystkie znaczące bity).
Ponowna konfiguracja oryginalnego wywołania lambda w celu uzyskania wartości rekurencji 0 i 2 ...
>>>1.7976931348623157e+308
1.0000000071
Jeśli zostanie wykonane porównanie z „przesunięciem od 0” zamiast „przesunięciem z 1”, funkcja ta zwraca wartość 7.1e-9, która jest zdecydowanie mniejsza niż 6.7e-05.
Rzeczywista podstawowa rekurencja programu (wartość z) wynosi 10 10 10 10 1,97 poziomów głębokości, gdy tylko y się wyczerpie, resetuje się z 10 10 10 10 10 1,97 (dlatego wystarcza wartość początkowa 9), więc nie nawet nie wiem, jak poprawnie obliczyć całkowitą liczbę rekurencji: doszedłem do końca mojej wiedzy matematycznej. Podobnie nie wiem, czy przeniesienie jednego z **nwykładników z początkowego sygnału wejściowego na wtórny z**zpoprawiłoby liczbę rekurencji, czy też nie (podobnie jak odwrotnie).
Idziemy jeszcze wolniej z jeszcze większą rekurencją
import math
a=lambda x,y:(y<0)*x or a(a(a(math.log(x+1),y-1),y-1),y-1)
print a(input(),9**9**9e9)//1
n//1 - oszczędza 2 bajty int(n)import math, math.oszczędza 1 bajtfrom math import*a(...) oszczędza łącznie 8 bajtów m(m,...)(y>0)*x zapisuje bajt overy>0and x9**9**99zwiększa liczbę bajtów o 4 i zwiększa głębokość rekurencji o około 2.8 * 10^xgdzie xjest stara głębokość (lub głębokość zbliżona do googolplex w rozmiarze: 10 10 94 ).9**9**9e9zwiększa liczbę bajtów o 5 i zwiększa głębokość rekurencji o ... szaloną ilość. Głębokość rekurencji wynosi teraz 10 10 10 9,93 , dla porównania, googolplex wynosi 10 10 10 2 .- deklaracja lambda zwiększa rekursji przez dodatkowy krok:
m(m(...))do a(a(a(...)))kosztów 7 bajtów
Nowa wartość wyjściowa (przy 9 głębokości rekurencji):
>>>1.7976931348623157e+308
6.77538853089e-05
Głębokość rekurencji eksplodowała do punktu, w którym ten wynik jest dosłownie bez znaczenia, z wyjątkiem porównania z wcześniejszymi wynikami używającymi tych samych wartości wejściowych:
- Oryginał nazwany
log25 razy
- Pierwsza poprawka nazywa to 81 razy
- Rzeczywisty program będzie nazwać 1e99 2 lub około 10 10 2,3 razy
- Ta wersja nazywa to 729 razy
- Rzeczywisty program będzie to (9 wywołać 9 99 ) 3 lub nieco mniej niż 10 10 95 -krotnie).
Lambda Incepcja, wynik: ???
Słyszałem, że lubisz lambdas, więc ...
from math import*
a=lambda m,x,y:y<0and x or m(m,m(m,log(x+1),y-1),y-1)
print int(a(a,input(),1e99))
Nie mogę nawet tego uruchomić, układam przepełnienie nawet przy zaledwie 99 warstwach rekurencji.
Stara metoda (poniżej) zwraca (pomijając konwersję do liczby całkowitej):
>>>1.7976931348623157e+308
0.0909072713593
Nowa metoda powraca, używając tylko 9 warstw wtargnięcia (zamiast ich pełnego googola ):
>>>1.7976931348623157e+308
0.00196323936205
Myślę, że to działa podobnie do sekwencji Ackermana, tylko małe zamiast duże.
Również dzięki produktom ETH za 3-bajtowe oszczędności w przestrzeniach, o których nie wiedziałem, że można je usunąć.
Stara odpowiedź:
Skrócenie liczb całkowitych dziennika funkcji (i + 1) iterowało 20 25 razy (Python) przy użyciu lambda'd lambda.
Odpowiedź PyRuleza można skompresować, wprowadzając drugą lambdę i układając ją w stos:
from math import *
x=lambda i:log(i+1)
y=lambda i:x(x(x(x(x(i)))))
print int(y(y(y(y(y(input()))))))
99 100 używanych znaków.
Powoduje to iterację 20 25, w stosunku do oryginału 12. Dodatkowo zapisuje 2 znaki, używając int()zamiast tego floor()dozwolonego dla dodatkowego x()stosu. Jeśli spacje po lambda można usunąć (nie mogę w tej chwili sprawdzić), y()można dodać piątą . Możliwy!
Jeśli istnieje sposób na pominięcie from mathimportu przy użyciu w pełni kwalifikowanej nazwy (np. x=lambda i: math.log(i+1))), To zaoszczędziłoby jeszcze więcej znaków i pozwoliłoby na inny stos, x()ale nie wiem, czy Python obsługuje takie rzeczy (podejrzewam, że nie). Gotowy!
Jest to w zasadzie ta sama sztuczka, którą zastosowano w blogu XCKD na dużą liczbę , jednak narzut związany z deklarowaniem lambdas wyklucza trzeci stos:
from math import *
x=lambda i:log(i+1)
y=lambda i:x(x(x(i)))
z=lambda i:y(y(y(i)))
print int(z(z(z(input()))))
Jest to najmniejsza możliwa rekurencja z 3 lambdami, która przekracza obliczoną wysokość stosu 2 lambdas (zmniejszenie dowolnej lambdy do dwóch wywołań obniża wysokość stosu do 18, poniżej wysokości wersji 2-lambda), ale niestety wymaga 110 znaków.
