No Cap (or numbers or symbols)

Ben Taylor — Wed, 20 May 2020 05:02:54 +0000

Calculating Pi in JavaScript with only lowercase letters, parenthesis, and dots

Wow, quarantine is really taking its toll. I didn't actually think this was possible, but then someone told me that it was impossible, so I did it. In just 30,000 hand written characters limited to lowercase a-z, "(", ")", and ".", we have advanced the state of the art and calculated Pi. But how?

If you want to skip ahead and learn by reverse engineering, the final code is up here. It would also be a fun exercise to explore before looking at the explanation below if you have a few hours.

How do we calculate Pi at all?

There are a ton of very mathy ways to approximate pi, and the way we're doing it is probably the worst. We're going to throw a bunch of darts at a unit square, and see the proportion that land in the unit circle centered at the top left corner. Because the area of the quarter of the circle within the square is pi*r^2/4 = pi/4, and the area of the unit square is 1, the proportion of darts that land inside the circle will be pi/4, which means we can multiply our proportion by 4 to get an approximation of Pi.

Note that 4pi should be pi/4 in the visualization :)

A normal JavaScript implementation

We use the following code to implement the algorithm in JavaScript. You'd never want to use this in an actual codebase, but it works great for our purposes.

(new Array(1000))
  .fill(0)
  .map(v => [Math.random(), Math.random()])
  .filter(v => v[0] * v[0] + v[1] * v[1] < 1)
  .length / 1000 * 4

We create an array of 1000 elements, then set each element to be an array of 2 random numbers between 0 and 1. These elements are our darts. We then remove any element that is outside of the circle, checking to see if x^2 + y^2 is less than the radius squared. Finally, we take the number of surviving elements, divide by the number of elements we started with, and multiply by 4.

Starting our Adventure - Numbers

To start, let's take a look at different methods we can use to get strings, numbers, and objects using our limited alphabet. Our foundation is made up of JavaScript's typeof operator, which returns a string corresponding to the type of the operand. We can also use values like true, false, and undefined.

(typeof(true)) => "boolean"
(typeof(undefined)) => "undefined"
(typeof(typeof(true)) => "string"

Now that we have our first building blocks, we can start creating numbers. Since we have strings, we can use the length property to get a few integers. I'm going to use what the previous expressions evaluate to rather than the expressions themselves, just to keep myself from writing typeof a billion times.

"boolean".length => 7
"undefined".length => 8

We'll have to be a little fancier to get the numbers 0 and 1, but once we have those, we can get any nonnegative integer. To find 0, we take the substring of any string starting from the length of that string to get the empty string, then take the length of the empty string. To get 1, we take the substring of the string "boolean" starting from the length of the string "number", giving us a string of length 1.

// to get 0
"boolean".substring(7) => ""
"".length => 0

// to get 1
typeof(7) => "number"
"number".length => 6
"boolean".substring(6) => "n"
"n".length => 1

You can kind of see a pattern here — we're recursively building on previous expressions to unlock new, more complex expressions. Now that we have a string of length 1, we can concat the string to itself n times and take the length to get the integer n.

"n".concat("n").length => 2
"n".concat("n").concat("n").length => 3
...

There are more efficient ways to get some numbers, but I'll leave that as an exercise for the reader.

Making Progress - Letters

We've already seen how to get the letter "n", but that was a special case. "n" was at the end of the substring, so we could easily grab it. But if we want the letter "l" from the middle of "boolean", we need to do a bit more work — substring(start,end) won't work because it uses a comma.

We're going to make use of Arrays here. We can split a string into a character array with String.split(""), and we found the empty string earlier. We can then get the first element by using .shift() or .reverse().pop(), whichever you prefer.

"boolean".substring(3).split("").shift() => "l"

This works for nearly every lowercase letter. If we need a string with a letter that we don't have yet, we can make use of JavaScript's name property on functions. For instance, "".big.name will return the string "big", and "".substring.name will return "substring".

However, a lot of capital letters are out of reach through this method. This is my favorite part — we get to chaotically spam btoa! btoa is a function that takes a normal string and returns the base64 representation of the string. While not completely random, iterating the function with different inputs can give us almost any letter we need (and the equals sign!)

btoa('l') => "bA=="
btoa(btoa('l')) => "YkE9PQ=="
btoa(btoa(btoa('l'))) => "WWtFOVBRPT0="
btoa(btoa(btoa(''))) => "WWtFOVBRPT0="
...

While I don't have a proof that we can get every letter this way, it hasn't let me down yet.

Symbols

You may have noticed that none of the strings we have so far have any punctuation in them, with the exception of the equals sign. This is where things get a little tricky.

To get "(", ")", "{", and "}", we use JavaScript's weird type system to cast a function to a string.

''.concat("".big) => "function big() { [native code] }"

We can extract letters from this string just like any other string, but we can't use the "[native code]" part of the string as easily. This is because not all browsers treat this cast the same — Firefox will add newlines after the first curly brace and before the last curly brace, so the index of the square brackets will change. We can get the last curly brace by considering the position from the end of the string, and the first curly brace by considering the index from the start of the string.

There are a few ways to get the brackets. The easiest that I found was to assume that we're running this on a browser, and cast the document to a string. However, you can also cast an object created by the curly braces we just found to a string.

''.concat(document) => "[object HTMLDocument]"

''.concat(eval('{'.concat('}'))) => "[object Object]"

The final method we have works for arbitrary characters, though it can take more work. We use the inverse of btoa, atob. Because we have access to letters and equal signs, we can build arbitrary base64 encoded strings, then decode them back to regular strings. For instance, the base64 representation of "." is "Lg==". We can build this string easily, then call atob to get ".". Did I mention this works for any character we could ever want?

atob("Lg==") => "."
atob("Kg==") => "*"
atob("Kw==") => "+"
atob("Pg==") => ">"

Awesome, now we can make any string we want!

Evil & Objects

The last step is to get a few objects & arrays. Because JavaScript is a prototype based language, each object is essentially a class, meaning if we have one array we can use its constructor to make more. Lucky for us, we have plenty of arrays with .split().

"".split("").constructor => Array
"".split("").constructor(4).fill(0) => [4,4,4,4]

If we needed something like the Math object, we could build the string "Math" then use the evil eval to get the actual object.

eval("Math") => Math
eval("Math").random() => Math.random() => 0.6787282506292542

We can even construct our own functions from strings of JavaScript code this way!

eval("x => 2 * x + 1") => x => 2 * x + 1
eval("x => 2 * x + 1")(2) => 5

Putting it all together

We have everything we need to rewrite our original program in our restricted alphabet. Here's the version with strings & newlines, if you would like to see the beauty of the expanded program, check it out here.

eval(
  "".concat(Array(1000)
   .fill(0)
   .map(eval("x=>[Math.random(),Math.random()]"))
   .filter(eval("x=>1>x[0]*x[0]+x[1]*x[1]")).length)
 .concat("*4/1000")
)

Notice that we can build every string & number that appears in the program with the building blocks developed throughout this post. Another approach would to just get every lowercase & uppercase letter, get the base64 representation of the program, convert it to a string, and eval it, but then we don't learn nearly as much about how JavaScript works.

Summary & Where to go From Here

Here's a summary of all the features and properties of JavaScript that let us do crazy stuff like this

JavaScript is a prototype based language, which means objects serve as prototypes to build new objects
JavaScript has a weird type system that lets us turn functions and objects into strings on a whim
JavaScript lets us evaluate arbitrary strings with its eval function, which is why eval should always be avoided. You never know what a malicious user might execute
Base64 uses a significantly reduced alphabet that lets us convert our smaller alphabet into a wider range of symbols and characters

From here, you could play around and try to implement your own program in this reduced alphabet. If you want something more advanced, try writing a compiler that can take regular JavaScript and turn it into our brand new flavor (and let me know if you do!)

This post was originally uploaded at https://bentaylor.xyz/post/3

DEV Community: Ben Taylor