Javascript for the Insane
So I’ve been playing with Codewars. It’s a well put together website and it’s nice not to have to set up an IDE or testing environment for each new language. But coding katas get boring… which is why this monstrosity is my latest submission:
nextGen=function($,_){return(function($_,_$){for(_$=$_=[]<<(_=[]);$[$_];$_+=!(_$=($[$_][++_$]-~{})?_$:~~{}))(_[$_]=(_[$_]||[]))[_$]=((($[$_][-~_$]>>[])+($[$_][~-_$]<<{})+(($[~-$_]&&(({}|$[~-$_][_$])+([]|$[~-$_][~-_$])+(~[]&$[~-$_][-~_$])))|$)+(($[-~$_]&&((-~{}&$[-~$_][_$])+($[-~$_][~-_$]&-~[])+($[-~$_][-~_$]^{})))&~$)|$[$_][_$])==!!{}-~([]!==!{}))+~~[]})(),_}
Feel free to beautify it and try to figure out what the challenge was and how it works. (It does work.) Otherwise read on and I’ll explain.
Ready for spoilers?
Okay.
The challenge was to implement Conway’s Game Of Life in Javascript. It takes a two-dimensional array of ones and zeros and returns an equivalent array representing the next generation. Start with a sane but verbose implementation of the Game of Life:
function nextGen(cells) {
var isdefined = function(x) { return typeof(x) !== 'undefined' },
undefinedtozero = function(x) { return isdefined(x) ? x : 0 };
var out = [];
for (var x = 0; x < cells.length; ++x) {
out[x] = [];
for (var y = 0; y < cells[x].length; ++y) {
// Note that Javascript lets you index outside an array and returns 'undefined'.
var n =
undefinedtozero(cells[x][y+1]) + undefinedtozero(cells[x][y-1]) +
(isdefined(cells[x-1]) ? (undefinedtozero(cells[x-1][y]) + undefinedtozero(cells[x-1][y-1]) + undefinedtozero(cells[x-1][y+1])) : 0) +
(isdefined(cells[x+1]) ? (undefinedtozero(cells[x+1][y]) + undefinedtozero(cells[x+1][y-1]) + undefinedtozero(cells[x+1][y+1])) : 0);
out[x][y] = (n == 3 || (n == 2 && cells[x][y])) ? 1 : 0;
}
}
return out;
}
First, let’s remove isdefined.
We can remove it from the middle of the loop easily: the ? operator only takes booleans, so whatever object we put in there will be coerced to a boolean. Arrays are truthy and undefined is falsey, so we can remove the function and it still works.
We also have to remove it from undefinedtozero. To do that we need to coerce x to an integer. The simplest way to do that is to do a bitwise operation on it. There are loads of good choices here, so let’s do all of them:
function nextGen(cells) {
var out = [];
for (var x = 0; x < cells.length; ++x) {
out[x] = [];
for (var y = 0; y < cells[x].length; ++y) {
var n =
(cells[x][y+1]>>0) + (cells[x][y-1]<<0) +
(cells[x-1] ? ((0|cells[x-1][y]) + (0|cells[x-1][y-1]) + (-1&cells[x-1][y+1])) : 0) +
(cells[x+1] ? ((1&cells[x+1][y]) + (cells[x+1][y-1]&1) + (cells[x+1][y+1]^0)) : 0);
out[x][y] = (n == 3 || (n == 2 && cells[x][y])) ? 1 : 0;
}
}
return out;
}
Next, let’s get rid of all those nasty var keywords. Javascript is happy for you to pass one argument into a function that expects four, so this works perfectly well:
function nextGen(cells, out, x, y) {
out = [];
for (x = 0; x < cells.length; ++x) {
out[x] = [];
for (y = 0; y < cells[x].length; ++y) {
var n =
(cells[x][y+1]>>0) + (cells[x][y-1]<<0) +
(cells[x-1] ? ((0|cells[x-1][y]) + (0|cells[x-1][y-1]) + (-1&cells[x-1][y+1])) : 0) +
(cells[x+1] ? ((1&cells[x+1][y]) + (cells[x+1][y-1]&1) + (cells[x+1][y+1]^0)) : 0);
out[x][y] = (n == 3 || (n == 2 && cells[x][y])) ? 1 : 0;
}
}
return out;
}
I’d really like to get rid of the two assignment lines just above the for loops. Luckily, if you do a bitwise operation on the empty array, you get zero, and assignment returns the value assigned, so we can write:
function nextGen(cells, out, x, y) {
for (x = 0<<(out = []); x < cells.length; ++x)
for (y = 0>>(out[x] = []); y < cells[x].length; ++y) {
var n =
(cells[x][y+1]>>0) + (cells[x][y-1]<<0) +
(cells[x-1] ? ((0|cells[x-1][y]) + (0|cells[x-1][y-1]) + (-1&cells[x-1][y+1])) : 0) +
(cells[x+1] ? ((1&cells[x+1][y]) + (cells[x+1][y-1]&1) + (cells[x+1][y+1]^0)) : 0);
out[x][y] = (n == 3 || (n == 2 && cells[x][y])) ? 1 : 0;
}
return out;
}
That’s much nicer, by some insane standard of ‘nice’. I’d like to get rid of n, though. That’s tricky, because it appears in the next line twice (and we don’t want to do the calculation twice – that would be bad code). Luckily, n == 3 || (n == 2 && cells[x][y]) is equivalent to (n | cells[x][y]) == 3 which only uses n once. So now we have:
function nextGen(cells, out, x, y) {
for (x = 0<<(out = []); x < cells.length; ++x)
for (y = 0>>(out[x] = []); y < cells[x].length; ++y)
out[x][y] = (((cells[x][y+1]>>0) + (cells[x][y-1]<<0) +
(cells[x-1] ? ((0|cells[x-1][y]) + (0|cells[x-1][y-1]) + (-1&cells[x-1][y+1])) : 0) +
(cells[x+1] ? ((1&cells[x+1][y]) + (cells[x+1][y-1]&1) + (cells[x+1][y+1]^0)) : 0)
| cells[x][y]) == 3) ? 1 : 0;
return out;
}
We’re nearly there now. That ? 1 : 0 at the end is basically a boolean-to-number coersion, so we can change that to + 0. Also, x < cells.length is a bit pedestrian. It would be more fun to say cells[x] and trust the truthiness of arrays and the falsiness of undefined to fix it for us:
function nextGen(cells, out, x, y) {
for (x = 0<<(out = []); cells[x]; ++x)
for (y = 0>>(out[x] = []); y < cells[x].length; ++y)
out[x][y] = (((cells[x][y+1]>>0) + (cells[x][y-1]<<0) +
(cells[x-1] ? ((0|cells[x-1][y]) + (0|cells[x-1][y-1]) + (-1&cells[x-1][y+1])) : 0) +
(cells[x+1] ? ((1&cells[x+1][y]) + (cells[x+1][y-1]&1) + (cells[x+1][y+1]^0)) : 0)
| cells[x][y]) == 3) + 0;
return out;
}
We know that empty arrays and objects are seen as zero by bitwise operations, so let’s make that replacement. Just for fun. In fact, -1 is represented by all 1s in binary, so let’s replace it with Bitwise Not Zero. ‘1’, therefore, is Minus Bitwise Not Zero, where ‘zero’ is an empty array or object. The result?
function nextGen(cells, out, x, y) {
for (x = []<<(out = []); cells[x]; ++x)
for (y = {}>>(out[x] = []); y < cells[x].length; ++y)
out[x][y] = (((cells[x][y+1]>>[]) + (cells[x][y-1]<<{}) +
(cells[x-1] ? (({}|cells[x-1][y]) + ([]|cells[x-1][y-1]) + (~[]&cells[x-1][y+1])) : 0) +
(cells[x+1] ? ((-~{}&cells[x+1][y]) + (cells[x+1][y-1]&-~[]) + (cells[x+1][y+1]^{})) : 0)
| cells[x][y]) == 3) + ~~[];
return out;
}
The other length is trickier to remove because zero is falsy. We need an operation that returns something truthy if given a 1 or a 0, but not undefined. My preferred solution is to add one: undefined becomes NaN (which is falsy). And by ‘one’, obviously I mean Minus Bitwise Not Zero:
function nextGen(cells, out, x, y) {
for (x = []<<(out = []); cells[x]; ++x)
for (y = {}>>(out[x] = []); y < cells[x][y]-~{}; ++y)
out[x][y] = (((cells[x][y+1]>>[]) + (cells[x][y-1]<<{}) +
(cells[x-1] ? (({}|cells[x-1][y]) + ([]|cells[x-1][y-1]) + (~[]&cells[x-1][y+1])) : 0) +
(cells[x+1] ? ((-~{}&cells[x+1][y]) + (cells[x+1][y-1]&-~[]) + (cells[x+1][y+1]^{})) : 0)
| cells[x][y]) == 3) + ~~[];
return out;
}
It pleases me greatly that a little picture of a flower works as an ‘is not undefined’ operator.
The two long ternary operators in the middle can be made more fun. The logical AND in Javascript returns its first parameter if it’s falsy and its second otherwise, making it act like a sort of reverse coalesce operator. Then we just have to coerce the result into a number, but we’re good at that by now so let’s do it in a silly way:
function nextGen(cells, out, x, y) {
for (x = []<<(out = []); cells[x]; ++x)
for (y = {}>>(out[x] = []); y < cells[x][y]-~{}; ++y)
out[x][y] = (((cells[x][y+1]>>[]) + (cells[x][y-1]<<{}) +
((cells[x-1] && (({}|cells[x-1][y]) + ([]|cells[x-1][y-1]) + (~[]&cells[x-1][y+1])) )|cells) +
((cells[x+1] && ((-~{}&cells[x+1][y]) + (cells[x+1][y-1]&-~[]) + (cells[x+1][y+1]^{})) )&~cells)
| cells[x][y]) == 3) + ~~[];
return out;
}
We’re nearly there now. The next step is to remove all those annoyingly readable +1 and -1 expressions. Because of Two’s Complement, you can add one to a number using minus-bitwise-not, and subtract one using bitwise-not-minus. And while we’re at it, let’s replace 3 with !!{}-~([]!==!{}) which is obviously the same:
function nextGen(cells, out, x, y) {
for (x = []<<(out = []); cells[x]; ++x)
for (y = {}>>(out[x] = []); cells[x][y]-~{}; ++y)
out[x][y] = (((cells[x][-~y]>>[]) + (cells[x][~-y]<<{}) +
((cells[~-x] && (({}|cells[~-x][y]) + ([]|cells[~-x][~-y]) + (~[]&cells[~-x][-~y])) )|cells) +
((cells[-~x] && ((-~{}&cells[-~x][y]) + (cells[-~x][~-y]&-~[]) + (cells[-~x][-~y]^{})) )&~cells)
| cells[x][y]) == !!{}-~([]!==!{})) + ~~[];
return out;
}
I’m not a big fan of this next trick, but it seems a shame not to at this stage: you can create a function inline and execute it in one step:
function nextGen(cells, out, x, y) {
(function(){
for (x = []<<(out = []); cells[x]; ++x)
for (y = {}>>(out[x] = []); cells[x][y]-~{}; ++y)
out[x][y] = (((cells[x][-~y]>>[]) + (cells[x][~-y]<<{}) +
((cells[~-x] && (({}|cells[~-x][y]) + ([]|cells[~-x][~-y]) + (~[]&cells[~-x][-~y])) )|cells) +
((cells[-~x] && ((-~{}&cells[-~x][y]) + (cells[-~x][~-y]&-~[]) + (cells[-~x][-~y]^{})) )&~cells)
| cells[x][y]) == !!{}-~([]!==!{})) + ~~[]
})();
return out
}
You can also use Javascript’s completely insane comma operator to execute the function but ignore the result and cram the whole thing onto one absurd line of code:
function nextGen(cells, out) {
return (function(x, y){
for (x = []<<(out = []); cells[x]; ++x)
for (y = {}>>(out[x] = []); cells[x][y]-~{}; ++y)
out[x][y] = (((cells[x][-~y]>>[]) + (cells[x][~-y]<<{}) +
((cells[~-x] && (({}|cells[~-x][y]) + ([]|cells[~-x][~-y]) + (~[]&cells[~-x][-~y])) )|cells) +
((cells[-~x] && ((-~{}&cells[-~x][y]) + (cells[-~x][~-y]&-~[]) + (cells[-~x][-~y]^{})) )&~cells)
| cells[x][y]) == !!{}-~([]!==!{})) + ~~[]
})(), out;
}
All that remains is to replace the variable names with stupid ones with no letters in and remove all the whitespace:
nextGen=function($,_){return(function($_,_$){for($_=[]<<(_=[]);$[$_];++$_)for(_$={}>>(_[$_]=[]);$[$_][_$]-~{};++_$)_[$_][_$]=((($[$_][-~_$]>>[])+($[$_][~-_$]<<{})+(($[~-$_]&&(({}|$[~-$_][_$])+([]|$[~-$_][~-_$])+(~[]&$[~-$_][-~_$])))|$)+(($[-~$_]&&((-~{}&$[-~$_][_$])+($[-~$_][~-_$]&-~[])+($[-~$_][-~_$]^{})))&~$)|$[$_][_$])==!!{}-~([]!==!{}))+~~[]})(),_}
Unless you want to be really anal about it, which naturally I do, in which case you get rid of one of the for loops and implement it manually:
nextGen=function($,_){return(function($_,_$){for(_$=$_=[]<<(_=[]);$[$_];$_+=!(_$=($[$_][++_$]-~{})?_$:~~{}))(_[$_]=_[$_]||[])[_$]=((($[$_][-~_$]>>[])+($[$_][~-_$]<<{})+(($[~-$_]&&(({}|$[~-$_][_$])+([]|$[~-$_][~-_$])+(~[]&$[~-$_][-~_$])))|$)+(($[-~$_]&&((-~{}&$[-~$_][_$])+($[-~$_][~-_$]&-~[])+($[-~$_][-~_$]^{})))&~$)|$[$_][_$])==!!{}-~([]!==!{}))+~~[]})(),_}
This is why Javascript is weird.
I appreciate that I am not really in a position to criticise it.