Suche nach kürzeren Alternativen zu `range (…)`

Die beste Lösung, die ich bisher für ein Golf-Code-Puzzle gefunden habe, an dem ich arbeite, sind zwei ziemlich fett aussehende Aufrufe von range. Ich bin sehr neu im Code Golf, besonders in Python, also könnte ich ein paar Tipps gebrauchen.

Das relevante Fragment ist dies

[x for x in range(n+1,7**6)if`x`==`x`[::-1]*all(x%i for i in range(2,x))]

Die Obergrenze der ersten rangeist nicht scharf. Es sollte mindestens 98690 sein, und alles andere ist gleich ( dh golfmäßig). Je kleiner der Unterschied zwischen dieser Obergrenze und 98690 ist, desto besser ist die Leistung ¹ . Ich verwende 7 ⁶ (= 117649), weil dies 7**6der kürzeste Python-Ausdruck ist, den ich mir vorstellen kann.

Im Gegensatz dazu sind die Untergrenze in der ersten rangesowie beide Grenzen in der zweiten fest. IOW, das Programm (in seiner aktuellen Form) führt zu falschen Ergebnissen, wenn diese Grenzwerte geändert werden.

Gibt es eine Möglichkeit, einen oder beide Ausdrücke zu verkürzen?

range(n+1,7**6)
range(2,x)

?

Übrigens, in diesem Fall gewinnt das Aliasing rangevon beispielsweise rnichts:

r=range;rr
rangerange

EDIT: FWIW, das vollständige Programm ist das folgende:

p=lambda n:[x for x in range(n+1,7**6)if`x`==`x`[::-1]*all(x%i for i in range(2,x))][0]

p(n)sollte die kleinste palindromische Primzahl größer sein als n. Auch psollte nicht rekursiv sein. Achtung: Es ist schon obszön langsam!

_{¹ Ja, ich weiß: Leistung ist beim Code-Golf irrelevant, aber deshalb habe ich geschrieben, dass "alles andere gleich ist (was das Golf betrifft)". Zum Beispiel meine Wahl 7**6und nicht die unmittelbar offensichtliche, aber leistungsschwächere "Golf-Äquivalent" -Alternative 9**9. Ich mag es , meine Code-Golf-Versuche tatsächlich auszuführen , was bedeutet, dass die Leistung nicht so stark beeinträchtigt wird, dass es Jahre dauern würde, bis der Code ausgeführt wird. Wenn ich helfen kann, natürlich.}

Machen Sie es zu einer einzigen Schleife

Wie es ist, haben Sie zwei Schleifen: eine, die über xpalindromische Primzahlen iteriert, eine andere, die iteriert, um izu überprüfen, ob xes sich um eine Primzahl handelt, die durch die Testteilung primiert wird. Wie Sie bemerkt haben, benötigt Python in vielen Schleifen viele Zeichen, oft zum Schreiben range, aber auch zum Schreiben while _:oder for x in _. Eine Golf-Python-Lösung sollte sich also Mühe geben, so wenig Loops wie möglich zu verwenden.

Der Kommentar von feersum "Die besten Golfprogramme stellen oft überraschende Verbindungen zwischen verschiedenen Teilen der Programme her" ist hier sehr zutreffend. Die Primprüfung scheint wie eine separate Unterroutine zu sein, für die all(x%i for i in range(2,x))der klassische Ausdruck gilt. Aber wir machen es anders.

Die Idee ist, Wilsons Theorem zu verwenden . Für jede potenzielle Primzahl kbehalten wir ein laufendes Produkt von (k-1)!bei und prüfen, ob es ein Vielfaches von ist k. Wir können den Überblick behalten, (k-1)!während wir das Potenzial testen k, erstklassige Palindrome zu sein, indem wir ein laufendes Produkt behalten P.

Eigentlich werden wir die stärkere Version von Wilsons Satz verwenden , die (k-1)! % k0 für Verbunde gleich kund nur für zusammengesetzte Zahlen, mit Ausnahme k=4gibt 2, und so (k-1)!**2 % kentspricht 0genau für zusammengesetzte Zahlen. Wir werden über das Update Pauf gleich k!**2aktualisieren P*=k*k.

(Siehe diese Antwort für diese Methode zum Suchen von Primzahlen in Python.)

Alles zusammen:

def p(n):
 k=P=1
 while(`k`!=`k`[::-1])+(k<=n)+(P%k==0):P*=k*k;k+=1
 return k

Dies ist noch nicht vollständig golfen - insbesondere die Bedingung ist ineffizient geschrieben. Wir können die Bedingung komprimieren, um zu überprüfen, ob kes sich um ein Palindrom handelt, während wir gleichzeitig die anderen Bedingungen über eine verkettete Ungleichung erzwingen.

def p(n):
 k=P=1
 while`k`*(P%k>0>n-k)!=`k`[::-1]:P*=k*k;k+=1
 return k

AFAIK, nicht wirklich.

Die Reichweite wird häufig in Python-Golfspielen verwendet, da dies der kürzeste Weg ist, um Listen mit zunehmenden / abnehmenden Zahlen zu erstellen.

Das heißt, es scheint etwas (7 Bytes) kürzer zu sein, um die Verwendung von range zu vermeiden und stattdessen eine umschlossene while-Schleife aufzurufen:

def p(n):
    n+=1
    while`n`*all(n%i for i in range(2,n))!=`n`[::-1]:n+=1
    return n

Vielen Dank an @xnor (wie immer) für die Verbesserung der Logik der while-Bedingung :)

Wenn Sie iterative Algorithmen wie die Newton-Methode oder die Berechnung von Fraktalen verwenden, bei denen Sie normalerweise Iterationen durchführen müssen , ohne sich um den Index zu kümmern , können Sie einige Zeichen speichern, indem Sie stattdessen über kurze Zeichenfolgen iterieren.

for i in range(4):x=f(x)
for i in'asdf':x=f(x)

Bei sieben Iterationen ist dies ausgeglichen range. Verwenden Sie für weitere Iterationen Backtics und große Zahlen

for i in`9**9**5`:pass

Dies läuft 56349 Mal, was für alle praktischen Zwecke ausreichen sollte. Wenn Sie mit Zahlen und Operatoren herumspielen, können Sie auf diese Weise eine Vielzahl von Zahlen fest codieren.