72
\$\begingroup\$

This is a tips question for golfing in Python concerning the Evil Numbers question on Anarchy Golf.

An number is evil if its binary expansion has an even number of 1's. The challenge is to print the first 400 evil numbers 0,3,5,...,795,797,798, one per line.

The Python 2 submissions are led by llhuii with a 42-byte solution. The next best is 46 bytes by mitchs, followed by five 47-byte submissions. It seems llhuii has found something truly magical that has eluded many strong Python golfers for over 2 years. Saving 4 or 5 bytes is huge for such a short golf.

Table of Python 2 scores

I'm still at 47 bytes. I'm hoping we can crack this puzzle as a community. If we get an answer jointly, I'd submit it under the names of everyone who contributed. An answer to this question can be a piece of code or a new idea or a piece of analysis. If you are llhuii, please don't spoil it for us yet.

Though submissions are not revealed because this problem is Endless, we're given some leads. The winning submission took 0.1699 seconds to run, much longer than any other, suggesting an inefficient method. From the byte statistics, of the 42 characters, 23 are alphanumeric [0-9A-Za-z] and 19 are ASCII symbols. This means there is no whitespace in llhuii's solution.

You can test your code on the problem page, choosing Python from the language dropdown or uploading a .py file. Note that:

  • Python 2.7 is used
  • Your code must be a full program that prints
  • There's no input for this problem, like
  • Your program just has to print the 400 values as given, even if it would break on larger values
  • Programs have 2 seconds to run
  • Programs may terminate with error
  • You may use exec; the "exec is denied" refers to shell exec
\$\endgroup\$
  • 2
    \$\begingroup\$ It may also be worthy to note that this sequences is "Indices of zeros in the Thue-Morse sequence A010060." (source: oeis) \$\endgroup\$ – Conor O'Brien Sep 29 '17 at 1:38

11 Answers 11

51
\$\begingroup\$

This isn't the same solution as llhuii's, but it's also 42 bytes long.

n=0;exec'print n;n^=(n^n+2)%3/2;n+=2;'*400

Try it online!

Thanks to @JonathanFrech, we're now at 40 bytes.

n=0;exec'print n;n=n+2^(n^n+2)/2%3;'*400

Try it online!

There's another byte to be saved, for a total of 39.

n=0;exec'print n;n=n+2^-(n^n+2)%3;'*400

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Out of curiosity, how do you know the 42-byte version is not the same as llhuii's? (I have never participated in Anarchy Golf) \$\endgroup\$ – Luis Mendo Sep 29 '17 at 21:20
  • 6
    \$\begingroup\$ @LuisMendo The Statistics tab lists 23 alphanumerical bytes and 19 ASCII symbols, so there's no whitespace. Unless llhuii wrote print+n, their solution must be different from mine. \$\endgroup\$ – Dennis Sep 29 '17 at 21:29
  • \$\begingroup\$ Ah, so you can get some information even if you don't know the code. That's nice. Thanks! \$\endgroup\$ – Luis Mendo Sep 29 '17 at 21:30
  • \$\begingroup\$ Do you think there's chance for a 38? In theory there are some degrees of freedom to potentially remove the - sign by shifting with print~n or print-n and using & or ~, though I haven't gotten anything to work. Also, n=0;exec"print n;d=n^n+2;n^=d^-d%3;"*400 is pretty but 40 bytes. \$\endgroup\$ – xnor Sep 30 '17 at 2:59
  • \$\begingroup\$ print-n seems unlikely as there is no easy relationship between the set bits of n and -n. print~n sounds more promising in theory, but I can't get below 40 bytes with this approach. \$\endgroup\$ – Dennis Sep 30 '17 at 17:28
28
+500
\$\begingroup\$

Getting 39 bytes

This is an explanation of how I got a 39-byte solution, which Dennis and JonathanFrech found separately as well. Or, rather, it explains how one could arrive at the answer in hindsight, in a way that's much nicer than my actual path to it, which was full of muddy reasoning and dead ends.

n=0
exec"print n;n=n+2^-(n+2^n)%3;"*400

Writing this a bit less golfed and with more parens, this looks like:

n=0
for _ in range(400):
  print n
  n=(n+2)^(-((n+2)^n))%3

Bit parities

We start with an idea from my 47-byte solution to output all numbers of the form n=2*k+b where k counts up 0,1,...,399 and b is a parity bit that makes the overall number of 1's even.

Let's write par(x) for the bit parity of x, that is the xor (^) all of bits in x. This is 0 if there's an even number of 1-bits (number is evil), and 1 if there's an odd number of 1-bits. For n=2*k+b, we have par(n) = par(k)^b, so to achieve evil par(n)==0 we need b=par(k), i.e. the last bit of n to be the bit parity of the preceding bits.

My first efforts at golfing were on expressing the par(k), at first directly with bin(k).count('1')%2, and then with bit manipulation.

Parity updates

Still, there didn't seem to be a short expression. Instead, it helped to realize that there's more info to work with. Rather than just computing the bit parity of the current number,

k  ---->  par(k)

we can update the bit parity as we increment k to k+1.

k   ---->  par(k)
      |
      v
k+1 ---->  par(k+1)

That is, since we're counting up k=0,1,2,..., we merely need to maintain the current bit parity rather than calculating it from scratch each time. The bit parity update par(k+1)^par(k) is the parity of the number of bits flipped in going from k to k+1, that is par((k+1)^k).

par(k+1) ^ par(k) = par((k+1)^k)
par(k+1) = par(k) ^ par((k+1)^k)

Form of (k+1)^k

Now we need to compute par((k+1)^k). It might seem like we've gotten nowhere because computing bit parity is exactly the problem we're trying to solve. But, numbers expressed as (k+1)^k have the form 1,3,7,15,.., that is one below a power of 2, a fact often used in bit hacks. Let's see why that is.

When we increment k, the effect of the binary carries is to invert the last 0 and all 1's to its right, creating a new leading 0 if there were none. For example, take k=43=0b101011

      **
  101011  (43)
 +     1
  ------
= 101100  (44)

  101011  (43)
 ^101100  (44)
  ------
= 000111  (77)   

The columns causing a carry are marked with *. These have a 1 change to a 0 and pass on a carry bit of 1, which keeps propagating left until it hits a 0 in k, which changes to 1. Any bits further to the left are unaffected. So, when k^(k+1) checks which bit positions change k to k+1, it finds the positions of the rightmost 0 and the 1's to its right. That is, the changed bits form a suffix, so result is 0's followed by one or more 1's. Without the leading zeroes, there are binary numbers 1, 11, 111, 1111, ... that are one below a power of 2.

Computing par((k+1)^k)

Now that we understand that (k+1)^k is limited to 1,3,7,15,..., let's find a way to compute the bit parity of such numbers. Here, a useful fact is that 1,2,4,8,16,... alternate modulo 3 between 1 and 2, since 2==-1 mod 3 . So, taking 1,3,7,15,31,63... modulo 3 gives 1,0,1,0,1,0..., which are exactly their bit parities. Perfect!

So, we can do the update par(k+1) = par(k) ^ par((k+1)^k) as

par(k+1) = par(k) ^ ((k+1)^k)%3

Using b as the variable we're storing the parity in, this looks like

b^=((k+1)^k)%3

Writing the code

Putting this together in code, we start k and the parity bit b both at 0, then repeatedly print n=2*k+b and update b=b^((k+1)^k)%3 and k=k+1.

46 bytes

k=b=0
exec"print 2*k+b;b^=(k+1^k)%3;k+=1;"*400

Try it online!

We removed parens around k+1 in ((k+1)^k)%3 because Python precedence does the addition first anyway, weird as it looks.

Code improvements

We can do better though by working directly with a single variable n=2*k+b and performing the updates directly on it. Doing k+=1 corresponds to n+=2. And, updating b^=(k+1^k)%3 corresponds to n^=(k+1^k)%3. Here, k=n/2 before updating n.

44 bytes

n=0
exec"print n;n^=(n/2+1^n/2)%3;n+=2;"*400

Try it online!

We can shorten n/2+1^n/2 (remember this is (n/2+1)^n/2) by rewriting

n/2+1 ^ n/2
(n+2)/2 ^ n/2
(n+2 ^ n)/2    

Since /2 removes the last bit, it doesn't matter if we do it before or after xor-ing. So, we have n^=(n+2^n)/2%3. We can save another byte by noting that modulo 3, /2 is equivalent to *2 is equivalent to -, noting that n+2^n is even so the division is actual halving without flooring. This gives n^=-(n+2^n)%3

41 bytes

n=0
exec"print n;n^=-(n+2^n)%3;n+=2;"*400

Try it online!

Finally, we can combine the operations n^=c;n+=2 into n=(n+2)^c, where c is a bit. This works because ^c acts only on the last bit and +2 doesn't care about the last bit, so the operations commute. Again, precedence lets us omit parens and write n=n+2^c.

39 bytes

n=0
exec"print n;n=n+2^-(n+2^n)%3;"*400

Try it online!

\$\endgroup\$
13
\$\begingroup\$

This gives my (xnor's) 47-byte solution and the thinking that led me to it. Don't read this if you want to figure this out yourself.

A natural first idea is to iterate through the numbers 0 to 799, printing only those with an even number of 1's in binary.

52 bytes

for n in range(800):
 if~bin(n).count('1')%2:print n

Try it online!

Here, the ~ takes the bit complement so as to switch even<->odd in the count and give a truthy value only on even counts.

We can improve this method by generating all the values instead of filtering. Observe that the output values are the numbers 0 to 399, each with a bit appended to make the number of 1 bits even.

0 = 2*0 + 0
3 = 2*1 + 1
5 = 2*2 + 1
6 = 2*3 + 0
...

So, the nth number is either 2*n+b with either b=0 or b=1. The bit b can be found by counting 1's in the bits of n and taking the count modulo 2.

49 bytes

for n in range(400):print 2*n+bin(n).count('1')%2

Try it online!

We can cut the 2 bytes for 2* by iterating over 0,2,4,..., which doesn't chance the count of 1's. We can do this by using an exec loop that runs 400 times and increasing n by 2 each loop.

47 bytes

n=0;exec"print n+bin(n).count('1')%2;n+=2;"*400

Try it online!

And, that's my 47-byte solution. I suspect most if not all the other 47-byte solutions are the same.

\$\endgroup\$
  • 1
    \$\begingroup\$ Is your 47 bytes long exec-approach allowed? \$\endgroup\$ – Jonathan Frech Sep 29 '17 at 10:18
  • 1
    \$\begingroup\$ @JonathanFrech Yes, when the page says "exec is denied", it's not referring to Python's exec but the command line exec. \$\endgroup\$ – xnor Sep 29 '17 at 10:25
9
\$\begingroup\$

llhuii’s Python 3 submission

Here are the Python 3 submissions for Evil Numbers at the time of writing:

enter image description here

llhuii probably ported their trick to Python 3, and came up with a solution that is

  • 3 bytes longer than their Python 2 solution, and
  • has 45 − (25 + 18) = 2 bytes of whitespace.

Porting xnor’s 47B to Python 3 literally, we get this 50B:

n=0;exec("print(n+bin(n).count('1')%2);n+=2;"*400)

I submitted it as ppcg(xnor). (It adds parentheses to exec and print, which are now functions.) It has different code stats from the other Python 3 answers, which all have some amount of whitespace in them. Interesting!

There’s a shorter way to rewrite it though (exec tends to lose its competitive edge in Python 3):

n=0
while n<800:print(n+bin(n).count('1')%2);n+=2

It’s 49 bytes. I submitted it as ppcg(xnor,alternative). This has two bytes of whitespace, just like llhui’s answer! This leads me to believe that llhuii’s Python 3 answer looks kinda like this (newline, then a while loop.) So llhuii probably used exec in Python 2 and while in Python 3, just like us; this explains the whitespace discrepancy.


Our 47B became a 49B in Python 3. What’s interesting, now, is that llhuii’s 42B didn’t become a 44B, it became a 45B! Something about llhuii’s solution takes one byte extra in Python 3. This could mean a variety of things.

  • The first thing that comes to mind is division: maybe llhuii uses / in Python 2, which became // in Python 3. (If they’re counting in twos like us, then n/2 might be used to shift n back to the right by one bit?)

  • The other thing that comes to mind is unary operators after print. Our print blah became print(blah) (1 byte extra), but if llhuii wrote something like print~-blah in Python 2, it’d become print(~-blah) in Python 3.

  • Maybe there are other ideas. Please let me know.

Code statistics for all Py3 solutions, including mine now:

enter image description here

\$\endgroup\$
  • 1
    \$\begingroup\$ What I find interesting is that their Python 3 solution is significantly faster than their Python 2 solution. Either they are using some Python feature that got more efficient in Python 3 or it is not a simple port after all (maybe they found a Python 3 solution which is shorter than a direct port would be). \$\endgroup\$ – Jonathan Frech Sep 29 '17 at 15:10
  • 2
    \$\begingroup\$ The runtimes on anagol have huge variance, I commented on the OP that llhuii’s runtime here makes me think that their Py2 runtime is just a red herring/outlier \$\endgroup\$ – Lynn Sep 29 '17 at 15:13
  • \$\begingroup\$ Also, I assume xnor found a very similar trick and improved on it (there can’t be that many ways to print evil numbers, right?!) and their solution is plenty fast! \$\endgroup\$ – Lynn Sep 29 '17 at 15:13
7
\$\begingroup\$

Other approaches

1) Using a formula for A001969

Rather than converting to binary, it might be possible to take advantage of the following formula (from OEIS):

a(1) = 0
for n > 1: a(n) = 3*n-3-a(n/2) if n is even
           a(n) = a((n+1)/2)+n-1 if n is odd

I'm very bad at golfing in Python, so I'm not even going to try. But here is a quick attempt in JS.

NB: I don't think it would be a valid JS submission as it's just filling an array without displaying it. And even so, it's 5 bytes longer than the current best JS solution (which is 45 bytes). But that's not the point here anyway.

for(a=[n=0,3];n<199;)a.push(2*++n+a[n],6*n+3-a[n])

for(a=[n=0,3];n<199;)a.push(2*++n+a[n],6*n+3-a[n])

console.log(a.join`, `)

Hopefully it may give some inspiration.

Using an array is probably not a good idea because it needs to be initialized and updated. It might be more efficient (code size wise) to use a recursive function instead, which would explain why the winning solution is taking more time than the other ones.

2) Building the Thue-Morse sequence with substitutions

In theory, this code should work:

n=0;a="1";b="0";exec"t=a;a+=b;b+=t;print(int(b[n]))+n;n+=2;"*400

Try it online! (runnable version limited to 20 terms)

It computes the Thue-Morse sequence with consecutive substitutions and looks for the position of 1's (Evil Numbers) in the same loop.

But:

  • It's far too long in its current form
  • It quickly leads to a memory overflow

3) Building the Thue-Morse sequence with bitwise operations

Starting from Wikipedia's Direct Definition of the Thue-Morse sequence, I've come to this algorithm (switching back to JS ... sorry):

for(e=n=0;n<799;)(e^=!(((x=n++^n)^x/2)&170))||console.log(n)

where we keep track of the current evilness of the sequence in e and use 170 as a bitmask of odd bits in a byte.

\$\endgroup\$
  • \$\begingroup\$ I like the idea of a recursive function, but Python is very bad at that for boilerplate: f=lambda n:_ for n in range(400):print f(n) already takes 43 bytes. Maybe there's a way to simulate the recursion by building an array that references itself, or an array that adds future elements to the end. \$\endgroup\$ – xnor Sep 29 '17 at 2:25
  • 2
    \$\begingroup\$ Also, llhuii's solution has no spaces in it, so he didn't use def, for, while, lambda (with a parameter at least), etc. \$\endgroup\$ – Stephen Sep 29 '17 at 2:27
  • \$\begingroup\$ @Stephen Something like while~0:print~1 does not require any spaces. \$\endgroup\$ – Jonathan Frech Sep 29 '17 at 12:35
  • \$\begingroup\$ In method number 3, ((x=n++^n)^x/2) seems somewhat verbose just to find the lowest set bit. That whole mess can be replaced by ++n&-n. Try it online! \$\endgroup\$ – primo Mar 23 at 7:54
  • \$\begingroup\$ @primo I've no idea what I was thinking here and how I came to this cumbersome formula. ¯\_(ツ)_/¯ \$\endgroup\$ – Arnauld Mar 23 at 11:32
5
\$\begingroup\$

Nested counters approach

I have an idea for a different approach, but I am not experienced enough in python golfing, so I'll leave it here for you guys to consider as another possible starting point for golfing.

The ungolfed idea:

n=0
i=1
for _ in"01":
 i^=1
 for _ in"01":
  i^=1
  for _ in"01":
   i^=1
   for _ in"01":
    i^=1
    for _ in"01":
     i^=1
     for _ in"01":
      i^=1
      for _ in"01":
       i^=1
       for _ in"01":
        i^=1
        for _ in"01":
          i^=1
          if n<800:print i+n
          n+=2

Try it online!

Nine levels nesting depth, all the loops are the same, so in my mind they should be built by exec"something"*9+"deepest stuff". In practice I don't know if it is possible to do something like this with a for cycle.

Things to consider for golfing:

  • maybe there is some other possibility to cycle twice other than a for loop (I tried a quine-like approach with the string to be executed passed to itself as a formatting argument twice,but my head exploded).

  • there could also be a better alternative to if n<800:, which is needed here because otherwise we would keep printing evil numbers up to 2^10

\$\endgroup\$
  • \$\begingroup\$ 116 bytes. \$\endgroup\$ – Jonathan Frech Sep 29 '17 at 9:51
  • \$\begingroup\$ Maybe try nested list comprehensions instead of nested for loops? \$\endgroup\$ – Sparr Sep 29 '17 at 16:29
  • \$\begingroup\$ @Sparr The problem then is to actually print the numbers. In Python 2, print is a statement, not a function, and thus cannot appear inside a comprehension. \$\endgroup\$ – Jonathan Frech Sep 29 '17 at 16:53
  • \$\begingroup\$ maybe print '\n'.join([[[[[[[[[foo]foo]foo]foo]foo]foo]foo]foo]foo]) \$\endgroup\$ – Sparr Sep 29 '17 at 16:55
  • \$\begingroup\$ @Sparr Then the problem lies in flattening the list; str.join only works on lists containing strings and the extra list characters must not be printed. Formatting alone would take a significant amount of bytes. \$\endgroup\$ – Jonathan Frech Sep 29 '17 at 17:29
5
\$\begingroup\$

Idea: Shorter bit parity

It takes many characters to do bin(n).count('1')%2 to compute the parity of the bit-count. Maybe an arithmetic way is shorter, especially given a limited bit length.

A cute same-length way is int(bin(n)[2:],3)%2, interpreting the binary value as base 3 (or any odd base). Unfortunately, 4 of the bytes are spend removing the 0b prefix. It also works to do int(bin(n)[2:])%9%2.

Another idea comes from combining bits using xor. If n has binary representation abcdefghi, then

n/16 = abcde
n%16 =  fghi

r = n/16 ^ n%16 has binary representation (a)(b^f)(c^g)(d^h)(e^i)

So, r=n/16^n%16 is evil if and only if n is evil. We can then repeat that as s=r/4^r%4, a value s in 0,1,2,3, of which 1 and 2 are not evil, checkable with 0<s<3.

52 bytes

n=0;exec"r=n/16^n%16;print(0<r/4^r%4<3)+n;n+=2;"*400

Try it online!

This turned out a good deal longer. There's many knobs to turn though of how to split the number, how to check the final number (maybe a bit-based lookup table). I suspect these can only go so far though.

\$\endgroup\$
  • \$\begingroup\$ would it be a possibility to use the to_bytes function of integers? I doubt it but something to consider :) \$\endgroup\$ – HyperNeutrino Sep 29 '17 at 2:41
  • \$\begingroup\$ @HyperNeutrino I think that's Python 3 only? \$\endgroup\$ – xnor Sep 29 '17 at 2:42
  • \$\begingroup\$ yup my bad :/ rip \$\endgroup\$ – HyperNeutrino Sep 29 '17 at 2:44
  • 9
    \$\begingroup\$ Simply use the 0b: int(bin(n),13)%2! :D \$\endgroup\$ – Noodle9 Sep 29 '17 at 15:50
  • 3
    \$\begingroup\$ Progress! Noodle9’s trick offers a 44-byte solution: n=0;exec"print~int(bin(n),13)%2+n;n+=2;"*400 \$\endgroup\$ – Lynn Sep 29 '17 at 16:21
4
\$\begingroup\$

By construction, n+n^n is always evil, but my poor Python skills could only come up with a 61-byte solution:

for n in sorted(map(lambda n:n+n^n,range(512)))[:400]:print n

Thanks to @Peilonrayz for saving 5 bytes and @Mr.Xcoder for saving 1 byte:

for n in sorted(n^n*2for n in range(512))[:400]:print n
\$\endgroup\$
  • \$\begingroup\$ 55 bytes: for n in sorted(n^n*2for n in range(512))[:400]:print n. n+n^n is the same as n^n*2 \$\endgroup\$ – Mr. Xcoder Sep 29 '17 at 13:15
3
\$\begingroup\$

Idea: A006068 (“a(n) is Gray-coded into n”)

Neil’s idea of sorting all the 2n XOR n intrigued me, so I tried to find the indices behind this sort. I wrote this code, and it reveals that we can write something like this:

for n in range(400):x=a(n);print 2*x^x

Where a(n) is A006068(n). Try it online!

However, this assumes we have some short way to compute A006068. This is already 38 bytes, assuming we can calculate it in 4 bytes (the a(n) part). The real implementation (in the TIO header) is far longer than that. Not much hope for this I think.

\$\endgroup\$
3
\$\begingroup\$

Idea: Reduce over XOR

If you XOR all the bits of n together, it will be 0 for evil and 1 for non-evil. You can do this with a recursive function (which may have thus taken more time?), like so:

f=lambda n:f(n/2^n&1)if n>1else-~-n

This returns 1 for evil.

That's 35 bytes, and checks whether or not a number is evil. Unfortunately, filter is already 6 bytes so this wasn't the optimal solution verbatim but this idea can probably be golfed.

\$\endgroup\$
  • \$\begingroup\$ I think you can do f=lambda n:n>1and f(n/2^n&1)or-~-n for -1 byte. \$\endgroup\$ – Erik the Outgolfer Sep 29 '17 at 15:26
  • \$\begingroup\$ @EriktheOutgolfer I tried but that causes errors when f(n/2^n&1) returns 0... \$\endgroup\$ – HyperNeutrino Sep 29 '17 at 16:51
2
\$\begingroup\$

Substitution method : {1 -> {1, -1}, -1 -> {-1, 1}}

You can also make this substitution 10 times {1 -> {1, -1}, -1 -> {-1, 1}}, then flatten and check the positions of 1's

here is the mathematica code

(F = Flatten)@
Position[F@Nest[#/.{1->{1,-1},-1->{-1,1}}&,1,10],1][[;; 400]] - 1
\$\endgroup\$
  • \$\begingroup\$ How would you do this in python? \$\endgroup\$ – Aneesh Durg Sep 29 '17 at 20:30
  • 2
    \$\begingroup\$ @AneeshDurg do you find anything interesting in this solution? think out of the box and you may find your way to the meaning of life AKA 42 \$\endgroup\$ – J42161217 Sep 29 '17 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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