Prime js golf

2011-02-24

I love golf. Specifically, I love code golfs. These things get more interesting as you get to know a certain language better.

In case you don't know, "code golf" is the art of coming up with the shortest solution to a given problem in a given language.

The challenge at hand; build the shortest JavaScript function that, given any number, will eventually give you the next prime (any number higher than one that's only dividable by itself and one).

The challenger: Angus

Get next prime # in 81 char. Can u do better? function(n,d){while(!(function(){d=1;while(n%++d);return n==d;})(++n));return n;}

First thing I noticed was the double function and double loop. When it comes to code golfing in js, functions are very expensive. Each function takes up at least six characters (you may think seven, but in most cases, the last semi of the function body may be omitted under the "apply ASI if next token is }"-rule. This is the function boiler-plate for js: function(){}.

Next, there were two nested whiles in there. They can usually be merged, somehow. Note that a for is as expensive as a while, except that if you need to do initialization, the for gives you a semi-colon for free. (And in terms of speed there's no difference either way).

Here comes the list of "swings", in order of appearance. I'm not going to take the trouble of linking to each individual tweet (but if you care enough, feel free to give me the list). This list and order was compiled by Angus himself.

@angustweets
[81] function(n,d){while(!(function(){d=1;while(n%++d);return n==d;})(++n));return n;}

@cowboy
[74] function(n){while(!function(d){while(n%++d);return n==d}(1,++n));return n}

@kuvos
[58] function(n){do{++n;d=1;while(n%++d);}while(n!=d);return n}
(Leaves a global)

@kuvos
[51] function(n,d){while(n%++d||n==d?0:n+=d=1);return n}
Note that this fails. My bad. The principle (of merging the whiles) worked though. See below :)

@angustweets
[58] function(n){do{d=++n;while(--d&&n%d);}while(d-1);return n}

@bga_
[54] function(n,d){do{d=n++;while(n%d--);}while(d)return n}

@bga_
[46] function(n,d){while(n%d?--d>1:d=n++);return n}

@GlobalDomestic
[64] function(n,d){d=1;++n;while(n%++d||(n==d?0:(d=1,++n)));return n}

Near the end, Ben also churned out a simple test program:
(function(f,x,i){for(x=i=0;i++<99;)x+=f(i);return x==5238})( ...function-to-test... )

Kyle and Asen noted that the function should/can stop at n^2. But efficiency is not really important in a code golf :)

So the winner of this code golf is Alexander with a 46 byte function (expression). Hurray :D

So if you're ever hitting a wall while creating your next js1k, always remember that you're probably not there yet ;)