Jesse van der Pluijm Jesse van der Pluijm - 1 year ago 64
Javascript Question

compressing a string of 0's and 1's in js


I'm currently working on John Conway's Game of Life in js. I have the game working (view here) and i'm working on extra functionalities such as sharing your "grid / game" to your friends. To do this i'm extracting the value's of the grid (if the cell is alive or dead) into a long string of 0's and 1's.

This string has a variable length since the grid is not always the same size. for example:

grid 1 has a length and width of 30 => so the string's length is 900

grid 2 has a length and width of 50 => so the string's length is 2500

The problem

As you can see these string's of 0's and 1's are way too long to copy around and share.

However hard i try I don't seem to be able to come up with a code that would compress a string this long to a easy to handle one.

Any ideas on how to compress (and decompress) this?

I have considered simply writing down every possible grid option for the gird sizes 1x1 to 100x100 and giving them a key/reference to use as sharable code. Doing that by hand would be madness but maybe any of you has an idea on how to create an algorithm that can do this?

GitHub repository

Answer Source


For any of you who are wondering how exactly I ended up doing it, here's how:

First I made sure every string passed in would be padded with leading 0s untill it was devidable by 8. (saving the amount of 0s used to pad, since they're needed while decompressing)

I used Corstian's answer and functions to compress my string (interpreted as binary) into a hexadecimal string. Although i had to make one slight alteration.

Not every binary substring with a lenght of 8 will return exactly 2 hex characters. so for those cases i ended up just adding a 0 in front of the substring. The hex substring will have the same value but it's length will now be 2.

Next up i used a functionality from Arnaulds answer. Taking every double character and replacing it with a single character (one not used in the hexadecimal alphabet to avoid conflict). I did this twice for every hexadecimal character.

For example:
the hex string 11 will become h and hh will become H
01101111 will become 0h0H

Since most grids are gonna have more dead cells then alive ones, I made sure the 0s would be able to compress even further, using Arnaulds method again but going a step further.

00 -> g | gg -> G | GG -> w | ww -> W | WW -> x | xx -> X | XX-> y | yy -> Y | YY -> z | zz -> Z

This resulted in Z representing 4096 (binary) 0s

The last step of the compression was adding the amount of leading 0s in front of the compressed string, so we can shave those off at the end of decompressing. This is how the returned string looks in the end.

amount of leading 0s-compressed string so a 64*64 empty grid, will result in 0-Z

Decompressing is practically doing everything the other way around.

Firstly splitting the number that represents how many leading 0s we've used as padding from the compressed string.

Then using Arnaulds functionality, turning the further "compressed" characters back into hexadecimal code.

Taking this hex string and turning it back into binary code. Making sure, as Corstian pointed out, that every binary substring will have a length of 8. (ifnot we pad the substrings with leading 0s untill the do, exactly, have a length of 8)

And then the last step is to shave off the leading 0s we've used as padding to make the begin string devidable by 8.

The functions

Function I use to compress:

 * Compresses the a binary string into a compressed string.
 * Returns the compressed string.
Codes.compress = function(bin) {
  bin = bin.toString(); // To make sure the binary is a string;
  var returnValue = ''; // Empty string to add our data to later on.

  // If the lenght of the binary string is not devidable by 8 the compression
  // won't work correctly. So we add leading 0s to the string and store the amount
  // of leading 0s in a variable.

  // Determining the amount of 'padding' needed.
  var padding = ((Math.ceil(bin.length/8))*8)-bin.length;
  // Adding the leading 0s to the binary string.
  for (var i = 0; i < padding; i++) {
    bin = '0'+bin;

  for (var i = 0; i < parseInt(bin.length / 8); i++) {
    // Determining the substring.
    var substring = bin.substr(i*8, 8)
    // Determining the hexValue of this binary substring.
    var hexValue = parseInt(substring, 2).toString(16);
    // Not all binary values produce two hex numbers. For example:
    // '00000011' gives just a '3' while what we wand would be '03'. So we add a 0 in front.
    if(hexValue.length == 1) hexValue = '0'+hexValue;
    // Adding this hexValue to the end string which we will return.
    returnValue += hexValue;

  // Compressing the hex string even further.
  // If there's any double hex chars in the string it will take those and compress those into 1 char.
  // Then if we have multiple of those chars these are compressed into 1 char again.
  // For example: the hex string "ff will result in a "v" and "ffff" will result in a "V".
  // Also: "11" will result in a "h" and "1111" will result in a "H"
  // For the 0s this process is repeated a few times.
  // (string with 4096 0s) (this would represent a 64*64 EMPTY grid)
  // will result in a "Z".
  var returnValue = returnValue.replace(/00/g, 'g')
                               .replace(/gg/g, 'G')
                              // Since 0s are probably more likely to exist in our binary and hex, we go a step further compressing them like this:
                               .replace(/GG/g, 'w')
                               .replace(/ww/g, 'W')
                               .replace(/WW/g, 'x')
                               .replace(/xx/g, 'X')
                               .replace(/XX/g, 'y')
                               .replace(/yy/g, 'Y')
                               .replace(/YY/g, 'z')
                               .replace(/zz/g, 'Z')
                               //Rest of the chars...
                               .replace(/11/g, 'h')
                               .replace(/hh/g, 'H')
                               .replace(/22/g, 'i')
                               .replace(/ii/g, 'I')
                               .replace(/33/g, 'j')
                               .replace(/jj/g, 'J')
                               .replace(/44/g, 'k')
                               .replace(/kk/g, 'K')
                               .replace(/55/g, 'l')
                               .replace(/ll/g, 'L')
                               .replace(/66/g, 'm')
                               .replace(/mm/g, 'M')
                               .replace(/77/g, 'n')
                               .replace(/nn/g, 'N')
                               .replace(/88/g, 'o')
                               .replace(/oo/g, 'O')
                               .replace(/99/g, 'p')
                               .replace(/pp/g, 'P')
                               .replace(/aa/g, 'q')
                               .replace(/qq/g, 'Q')
                               .replace(/bb/g, 'r')
                               .replace(/rr/g, 'R')
                               .replace(/cc/g, 's')
                               .replace(/ss/g, 'S')
                               .replace(/dd/g, 't')
                               .replace(/tt/g, 'T')
                               .replace(/ee/g, 'u')
                               .replace(/uu/g, 'U')
                               .replace(/ff/g, 'v')
                               .replace(/vv/g, 'V');

  // Adding the number of leading 0s that need to be ignored when decompressing to the string.
  returnValue = padding+'-'+returnValue;

  // Returning the compressed string.
  return returnValue;

The function I use to decompress:

 * Decompresses the compressed string back into a binary string.
 * Returns the decompressed string.
Codes.decompress = function(compressed) {
  var returnValue = ''; // Empty string to add our data to later on.

  // Splitting the input on '-' to seperate the number of paddin 0s and the actual hex code.
  var compressedArr = compressed.split('-');
  var paddingAmount = compressedArr[0]; // Setting a variable equal to the amount of leading 0s used while compressing.
  compressed = compressedArr[1]; // Setting the compressed variable to the actual hex code.

  // Decompressing further compressed characters.
  compressed = compressed// Decompressing the further compressed 0s. (even further then the rest of the chars.)
                         .replace(/Z/g, 'zz')
                         .replace(/z/g, 'YY')
                         .replace(/Y/g, 'yy')
                         .replace(/y/g, 'XX')
                         .replace(/X/g, 'xx')
                         .replace(/x/g, 'WW')
                         .replace(/W/g, 'ww')
                         .replace(/w/g, 'GG')
                         .replace(/G/g, 'gg')
                         .replace(/g/g, '00')
                         // Rest of chars...
                         .replace(/H/g, 'hh')
                         .replace(/h/g, '11')
                         .replace(/I/g, 'ii')
                         .replace(/i/g, '22')
                         .replace(/J/g, 'jj')
                         .replace(/j/g, '33')
                         .replace(/K/g, 'kk')
                         .replace(/k/g, '44')
                         .replace(/L/g, 'll')
                         .replace(/l/g, '55')
                         .replace(/M/g, 'mm')
                         .replace(/m/g, '66')
                         .replace(/N/g, 'nn')
                         .replace(/n/g, '77')
                         .replace(/O/g, 'oo')
                         .replace(/o/g, '88')
                         .replace(/P/g, 'pp')
                         .replace(/p/g, '99')
                         .replace(/Q/g, 'qq')
                         .replace(/q/g, 'aa')
                         .replace(/R/g, 'rr')
                         .replace(/r/g, 'bb')
                         .replace(/S/g, 'ss')
                         .replace(/s/g, 'cc')
                         .replace(/T/g, 'tt')
                         .replace(/t/g, 'dd')
                         .replace(/U/g, 'uu')
                         .replace(/u/g, 'ee')
                         .replace(/V/g, 'vv')
                         .replace(/v/g, 'ff');

  for (var i = 0; i < parseInt(compressed.length / 2); i++) {
    // Determining the substring.
    var substring = compressed.substr(i*2, 2);
    // Determining the binValue of this hex substring.
    var binValue = parseInt(substring, 16).toString(2);

    // If the length of the binary value is not equal to 8 we add leading 0s (js deletes the leading 0s)
    // For instance the binary number 00011110 is equal to the hex number 1e,
    // but simply running the code above will return 11110. So we have to add the leading 0s back.
    if (binValue.length != 8) {
      // Determining how many 0s to add:
      var diffrence = 8 - binValue.length;

      // Adding the 0s:
      for (var j = 0; j < diffrence; j++) {
        binValue = '0'+binValue;

    // Adding the binValue to the end string which we will return.
    returnValue += binValue

  var decompressedArr = returnValue.split('');
  returnValue = ''; // Emptying the return variable.

  // Deleting the not needed leading 0s used as padding.
  for (var i = paddingAmount; i < decompressedArr.length; i++) {
    returnValue += decompressedArr[i];

  // Returning the decompressed string.
  return returnValue;

URL shortener

I still found the "compressed" strings a little long for sharing / pasting around. So i used a simple URL shortener (view here) to make this process a little easier for the user.

Now you might ask, then why did you need to compress this string anyway?

Here's why:

First of all, my project is hosted on github pages (gh-pages). The info page of gh-pages tells us that the url can't be any longer than 2000 chars. This would mean that the max grid size would be the square root of 2000 - length of the base url, which isn't that big. By using this "compression" we are able to share much larger grids.

Now the second reason why is that, it's a challange. I find dealing with problems like these fun and also helpfull since you learn a lot.


You can view the live version of my project here. and/or find the github repository here.


I want to thank everyone who helped me with this problem. Especially Corstian and Arnauld, since i ended up using their answers to reach my final functions.

Sooooo.... thanks guys! apriciate it!

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download