10
\$\begingroup\$

The best solution I've found so far for a golf code puzzle I'm working on includes two rather fat-looking invocations of range. I'm very new at code golf, especially in Python, so I could use a few tips.

The relevant fragment is this

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

The upper limit of the first range is not a sharp one. It should be at least 98690, and all else being equal (golf-wise, that is), the smaller the difference between this upper limit and 98690 the better, performance-wise1. I'm using 76 (=117649) because 7**6 is the shortest Python expression I can come up with that fits the bill.

In contrast, the lower limit in the first range, as well as both limits in the second one, are firm. IOW, the program (in its current form) will produce incorrect results if those limits are changed.

Is there a way to shorten one or both of the expressions

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

?

BTW, in this case, aliasing range to, say, r gains nothing:

r=range;rr
rangerange

EDIT: FWIW, the full program is this:

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) should be the smallest palindromic prime greater than n. Also, p should not be recursive. Warning: It is already obscenely slow!


1Yes, I know: performance is irrelevant in code golf, but that's why I wrote "all else being equal (golf-wise, that is)". For example, my choice of 7**6, and not the more immediately obvious, but poorer-performing, "golf-equivalent" alternative 9**9. I like to actually run my code golf attempts, which means not letting the performance degrade to the point that it would take years to run the code. If I can help it, of course.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ fwiw, you could make yours much faster for testing purposes by using generators; it's equivalent except for that: p=lambda n:(x for x in xrange(n+1,7**6)if`x`==`x`[::-1]*all(x%i for i in xrange(2,x))).next(). Of course, while your at that, might as well change xrange(2,x) to xrange(2,int(x**.5+1)) and make your testing really fast. Clearly this code is equivalent to yours, just longer and faster. \$\endgroup\$
    – Justin
    Nov 23, 2014 at 20:55
  • 1
    \$\begingroup\$ It's impossible to come up with many good golf tricks with a short fragment isolated from its context. The best-golfed programs often make surprising connections between different part of the programs. For example, a seemingly useless discarded variable may prove key, or two unrelated loops combined into one. \$\endgroup\$
    – feersum
    Nov 23, 2014 at 21:09
  • \$\begingroup\$ @feersum: I posted the whole thing (in an EDIT) quite a while ago. It was before you posted your comment. Didn't you see it? \$\endgroup\$
    – kjo
    Nov 23, 2014 at 22:47
  • \$\begingroup\$ @FryAmTheEggman: yes, the statement of the puzzle is that it has to be a function, and, what's worse, the function can't be recursive. \$\endgroup\$
    – kjo
    Nov 23, 2014 at 22:50
  • 1
    \$\begingroup\$ You might want to look here \$\endgroup\$
    – Beta Decay
    Nov 24, 2014 at 7:41

3 Answers 3

7
\$\begingroup\$

Make it a single loop

As is, you have two loops: one iterating over x that might be palindromic primes, another iterating over i to check if x is prime by trial division. As you noticed, loops is Python take many characters, often to write range, but also to write while _: or for x in _. So, a golfed Python solution should take pains to use as few loops as possible.

feersum's comment "The best-golfed programs often make surprising connections between different part of the programs" is very applicable here. The prime-checking might seem like a separate subroutine for which all(x%i for i in range(2,x)) is the classic expression. But we'll do it another way.

The idea is to use Wilson's Theorem. For each potential prime k, we keep a running product of (k-1)!, and check is it's a multiple of k. We can keep track of (k-1)! while we test potential k to be prime palindromes by keeping a running product P.

Actually, we'll use the stronger version of Wilson's Theorem that (k-1)! % k equals 0 for composite k and only for composite numbers, except k=4 gives 2, and so (k-1)!**2 % k equals 0 exactly for composite numbers. We'll update P to equal k!**2 via the update P*=k*k.

(See this answer for this method used to find primes in Python.)

Putting it all together:

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

This isn't yet fully golfed -- the condition in particular is written inefficiently. We can compress the condition to check that k is a palindrome while at the time enforcing the other conditions via a chained inequality.

def p(n):
 k=P=1
 while`k`*(P%k>0>n-k)!=`k`[::-1]:P*=k*k;k+=1
 return k
\$\endgroup\$
6
  • 1
    \$\begingroup\$ a dazzling solution. i'm grateful to see it, even though it goes into a realm beyond my reach... Up to now my improvements in golf had all been a matter of picking up tricks like using backticks instead of str, but these tricks get one only so much... the big improvements come from better algorithms, as always. \$\endgroup\$
    – kjo
    Nov 24, 2014 at 1:18
  • 1
    \$\begingroup\$ Following FryAmTheEggman's solution, one can rewrite the condition as `k`*(k>n)*(P%k>0)!=`k`[::-1], which shaves off 4 \$\endgroup\$
    – kjo
    Nov 24, 2014 at 1:57
  • 1
    \$\begingroup\$ @kjo Yes, and even more similarly if you chain the inequalities into a single one. You should also check out Python Golf Practice too see tricks like this \$\endgroup\$
    – xnor
    Nov 24, 2014 at 4:55
  • \$\begingroup\$ that's very nicely done! thank you all! this has been a very eye-opening thread for me... the shortest solution lengths I know of, for Python 2.7 and 3.3 are, respectively, 28 and 32 characters shorter than the version I posted originally (my absolute best effort), and when I found about this i was incredulous; i thought there had to be some foul play somewhere (e.g. by reverse engineering the automated solution-testing program). but after seeing how the experts here quickly shaved up to 16 characters from my best effort, i am now more willing to believe those numbers. \$\endgroup\$
    – kjo
    Nov 24, 2014 at 14:15
  • \$\begingroup\$ @kjo I'm glad you're seeing the magic the magic of golfing. Are you saying there's a 55 char solution? If so, I'm intrigued. Is this an anarchy golf problem? Could you please link me to the problem statement? There might be shortcuts possible from gaps in the test cases, in particular the exception with the number 4. \$\endgroup\$
    – xnor
    Nov 24, 2014 at 20:59
4
\$\begingroup\$

AFAIK, not really.

Range is commonly used in python golfs because it is the shortest way to generate lists of increasing/decreasing numbers.

That said, it appears to be slightly (7 bytes) shorter to avoid using range and instead call a wrapped while loop:

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

Thanks to @xnor (as always) for improving the while condition's logic :)

\$\endgroup\$
4
  • \$\begingroup\$ @kjo No trouble :) You might want to add what you told me about it having to be a non-recursive function to the question, as otherwise this answer is rather poor ;) \$\endgroup\$ Nov 23, 2014 at 23:55
  • 2
    \$\begingroup\$ You can save on the condition by implicitly negating it: while(`n`!=`n`[::-1])+0in(n%i for i in range(2,n)):n+=1. I can't seem to get rid of the first pair of parens due to operator precedence issues. \$\endgroup\$
    – xnor
    Nov 24, 2014 at 0:26
  • 2
    \$\begingroup\$ Getting rid of the parens: while`n`*all(n%i for i in range(2,n))!=`n`[::-1]:n+=1 \$\endgroup\$
    – xnor
    Nov 24, 2014 at 0:32
  • \$\begingroup\$ @FryAmTheEggman: that's very sportsmanlike of you! done \$\endgroup\$
    – kjo
    Nov 24, 2014 at 23:35
1
\$\begingroup\$

When using iterative algorithms such as Newton method or calculating fractals, where you usually need to perform iterations without actually caring about the index you can save some characters by iterating over short strings instead.

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

At seven iterations this breaks even with range. For more iterations use backtics and large numbers

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

This runs 56349 times which should be enough for all practical purposes. Playing around with numbers and operators lets you hardcode a wide range of numbers this way.

\$\endgroup\$
1
  • \$\begingroup\$ While this is interesting, you can see quite clearly that he does care about the index (as the candidate prime is the index). I think this fits better as a part of this answer on the tips page instead :) (Also note that '1'*4 is shorter than 'asdf') \$\endgroup\$ Nov 25, 2014 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.