I wrote a pentominoes on surfaces game (code) this & last month. When I started the project, I was convinced that finding when pieces are intersecting was going to be the hardest part of the project by far, and that it would be quite difficult.

As it turned out, finding intersections wasn’t all that difficult, but serializing the URL? Yikes.

The task

Here’s an example completed board. It’s an 8x8 grid with 4 pieces of terrain, so there are 60 squares total; this is the correct number, because there are 12 pentominoes each of size 5, and 12 * 5 = 60.

More interestingly, how was I able to permalink this solution? Here’s the string representing the board state:

P88YE00vW05P606nZ20LS23wA26Ub32ii34TL45Xg50zI63f675R11166166

Completely lost? I’ll help you out a bit. Here’s the same URL, but I’ve removed all color data from it:

P88Y400V605P606N120L223W026U332I234T345X050Z063F675R11166166

This one looks a lot clearer. There’s no lowercase letters, and if you’re familiar with these facts about pentominoes (on surfaces):

1. P at the start stands for ProjectivePlane (the surface that I’m solving on here)
2. The names of the tiles are F, I, L, P, N, T, U, V, W, X, Y, Z
3. Each piece can be rotated & reflected, so you need to encode not just the piece name and its coordinates, but also it’s orientation

Then I bet you can make sense of it without too much effort. The first 3 characters are:

• P - ProjectivePlane
• 8 - height
• 8 - width

Then after that is a list of all placed pentominoes, each one taking up four characters:

• Pentomino name (matches [FILPNTUVWXYZ])
• Orientation (matches 0-7)
• x-coordinate (matches 0-7 because we’re on an 8x8 grid, but more on this later)
• y-coordinate (same as x-coordinate)

The terrain is a bit a different; because we expect many of these, after we get to the R tile we stop saying pentomino name and expect that everything else is terrain. (Why don’t we do this for all tiles? (1) Usually people solve with just a single of each tile, and (2) it would be pretty hard to tell where pentominoes start and end - more on this later).

How did we get here?

Version 0: JSONCrush

My first MVP version of Pentominoes¹ used the JSONCrush library. The implementation was very simple:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

export function serializeUrl({ g: grid, h, w }: UrlConfig): string {
  const placedPentominoes: StringifiedPlacedPentomino[] = [];
  grid.map((row, x) =>
    row.map((p, y) => {
      if (p.pentomino !== PENTOMINOES.None)
        placedPentominoes.push({
          p: p.pentomino.name,
          o: p.rotation,
          e: p.reflection,
          x: x,
          y: y,
        });
    })
  );
  const s = JSON.stringify({ g: placedPentominoes, h: h, w: w });
  return encodeURIComponent(JSONCrush.crush(s));
}

export function deserializeUrl(s: string): UrlConfig {
  const j: StringifiedUrlSupportedConfig = JSON.parse(JSONCrush.uncrush(decodeURIComponent(s)));
  const ret = {
    h: j.h,
    w: j.w,
    g: range(j.h).map((x) => range(j.w).map((y) => EMPTY_PENTOMINO(x, y))),
  };
  j.g.map((p) => {
    ret.g[p.x][p.y] = {
      pentomino: PENTOMINOES[p.p],
      rotation: p.o,
      reflection: p.e,
      x: p.x,
      y: p.y,
    };
  });
  return ret;
}

There’s also some boilerplate code in my GameState provider component that updates the URL as needed & pulls the correct config on startup - although you should look at an updated version if you want to copy this implementation, as the original version updated the URL too greedily.

Here’s how an example slug looked:

('g!%5BBVC070*IC076*WD174*TC179*ZE1*FE6*NG-373*XD378*YG-472*PGA475*LGA571*UD578)%5D~h!6~w!10)*)%2CB-~e!0~x!.'~o!7~y!A~e!1~x!B('p!'C.1-D.0-E.2A27G.3%01GEDCBA7.-*_

This was….not great, for a few reasons.

1. There’s a ton of special characters that are valid in URLs, but not in Markdown when trying to link a board behind text (that link takes you to a live version of the original URL; the original won’t work).
2. It’s very hard to copy-paste - in particular you can’t double-click it and highlight the entire thing
3. It’s COMPLETELY unreadable by humans. So if you wanted to edit the URL to change the board, well, good luck with that.
4. As a corollary to 3, if you slightly miscopy something, it’s impossible to verify that you have a mistake, even if you completely understand the encoding.

So okay, new plan needed.

Version 1: A not-so-great manual encoding

All my URLs are backwards compatible to Version 1, so from now on, you can still load any slug I’ll mention. This version turned the same data as in the previous example to this:

6.10V10.0I10.6W01.4T11.9Z62.1F62.6N33.3X03.8Y34.2P74.5L75.1U05.8

Here’s how to read it:

1. First number is the width; then after a dividing .,
2. Second number is the height; then when you reach a character that matches A-Z
3. You start looping through pentominoes:
   1. First character is a letter
   2. Second character encodes the orientation: 0, 1, 2, 3 mean it’s not reflected; 4, 5, 6, 7 mean it’s reflected and then rotated by 0, 1, 2, 3, respectively. Or in other words:
      • reflection = orientation >= 4 ? 1: 0
      • rotation = orientation % 4
   3. Then the x-coordinate starts, until you reach a .
   4. Then the y-coordinate starts, until either you reach a letter (GOTO 1) or the end of the string

It’s not the most straightforward thing to read, and good luck in visualizing the orientation if you see N33.3 vs N53.3, but it’s quite readable once you know what’s going on.

Here’s the code that walks through the URL to decode it. It’s actually pretty bad code IMO, and I’m now using switch/case to make it MUCH more readable. But, well, it worked (and I have a bunch of tests to prove it).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

export function decodeUrl(s: string): StringifiedUrlConfig {
  let h = -1;
  let w = -1;
  const pentominoes: StringifiedPlacedPentomino[] = [];
  let curToken = "";
  let curPos = 0; // ['height', 'width', 'pentominoes']
  let expectRotation = false; // ['name', 'r', 'c']
  s.split("").map((c) => {
    if (c === "." && curPos === 0) {
      h = toInteger(curToken);
      curToken = "";
      curPos += 1;
    } else if (expectRotation === true) {
      pentominoes[pentominoes.length - 1].r = toInteger(c);
      expectRotation = false;
    } else if (c.match(/[\\.0-9]/)) {
      curToken = `${curToken}${c}`;
    } else if (c.match(/[A-Z]/)) {
      if (curPos === 1) {
        // finish width
        w = toInteger(curToken);
        curPos += 1;
      } else {
        // finish last pentomino
        pentominoes[pentominoes.length - 1].c = curToken;
      }
      curToken = "";
      // start a new pentomino
      pentominoes.push({
        p: c,
        r: -1,
        c: "",
      });
      expectRotation = true;
    }
  });
  // resolve the last character
  if (pentominoes.length > 0) {
    pentominoes[pentominoes.length - 1].c = curToken;
  } else {
    w = toInteger(curToken);
  }
  return {
    h: h,
    w: w,
    g: pentominoes,
  };
}

You can view the entire file at the time of that commit if you want. In the snippet above, I removed a few commented-out-anyway console.logs that were left over.

Also, the comment in this line is incorrect:

1

let expectRotation = false; // ['name', 'r', 'c']

Originally this was going to be a second counter for the position within a pentomino, but then I realized I only needed a boolean here so I changed it, but forgot to remove the comment. In later versions, this will go back to being a counter, as the encoding gets more complex.

There’s a few problems still (other than code quality):

1. The . is a problem for double-clicking text still.
2. We’re missing a lot of data that will eventually be added. (That’s because at this point, Pentominoes didn’t support color or surface)
3. It could still be more compact with a bit of extra work.

Version 1.1: Fix problem 1

I really wanted to be able to double-click to copy-paste slugs, so I replaced . with _. So here’s the new URL:

6_10V10_0I10_6W01_4T11_9Z62_1F62_6N33_3X03_8Y34_2P74_5L75_1U05_8

Sadly, in non-monospace fonts it’s actually a bit longer. But the convenience is worth it.

Version 1.5: Add colors

The next hurdle was that I needed to add support for pentominoes having multiple colors. Basically, the difference between this board and this one.

Crucially, actual hex values are independent of the URL. If you set custom colors, that’s stored in your localStorage, and other people’s URLs will look different to you from how they look to the owner. No problem. But the groups of colors are important, as a 3-color board might be intended to demonstrate a solve with a single band of color having properties, such as “none of these touch” or “all of these touch.”

Also, you could use color to demonstrate a property of a solve, such as 2 tiles having a rotational or reflectional symmetry in the final board. Here’s a board with 3 colors demonstrating a (pretty interesting) symmetry.

The naive way to do this would be to encode something like:

_0FILNUVXY1WZ2PT

And then put it at the end of the URL. But we can do better. First of all, there’s no need to display every single tile here; the default is for every tile to be color #0, so why would we encode tiles that are already color #0? Leave them out during encoding, and then keep them 0 during decoding. That gets us this:

1WZ2PT

We could do slightly better than this still, by letting 1 bit of color data correspond to casing of the pentomino name (or even 2 bits if we’re willing to use up some additional letters that don’t correspond to tiles; for example, we can say that A == F, B == I, C == L, D == P, etc, then one bit is lowercase? and another bit is using alternate letter? - but I don’t want to do this because the impact on readability is HUGE & the payout is very tiny, like 3 characters total and only in some circumstances).

But we can do a lot better - if there are tiles placed on the board.

Serializing colors inside the solve

If there are no tiles on the board, it’s true that the string above is needed. And indeed I still have a string like that for an empty board. For example, here’s a current slug for a 6x10 board with no pentominoes placed, but 12 colors assigned:

R6a_0z1Lw2fY3Nt4Iv5uX

Crucially, before I introduced surfaces, there was no real reason to support all tiles having unique color in order to tell them apart. So I figured 6 colors max was fine. Six colors means 2 tiles per color, and that’s sort of the minimum amount you’d ever want to group.

At this point, there was no need to split color data between two different characters, so I placed the entire thing inside of the orientation character, as follows:

• [0-7] means color 0
• [A-H] means color 1
• [I-P] means color 2
• [Q-X] means color 3
• [Y-Za-f] means color 4
• [g-n] means color 5

I even added a unit test to ensure that the total number of colors wasn’t too big:

1
2
3

test("max num colors is small enough", () => {
  expect(LETTERS_IN_ALPHABET * 2 >= (MAX_NUM_COLORS - 1) * NUM_SPATIAL_ORIENTATIONS).toBe(true);
});

In fact this test was a bit stricter than it needed to be, because I could’ve used characters 8 and 9 for something, but at the time I figured it was easier not to.

And then for any tiles that aren’t placed, I’d tack them on at the end of the URL as described above.

This of course required a bit of an update to the decodeUrl function, but the more interesting part is encoding and decoding the orientation character, so I’ll show you that instead:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

export function encodeOrientation(rotation: number, reflection: number, color: number): string {
  const r = reflection === 0 ? rotation : NUM_ROTATIONS + rotation;
  if (color === 0 || color === undefined) return r.toString();

  const n = NUM_SPATIAL_ORIENTATIONS * (color - 1) + UPPERCASE_START_INDEX + r;
  if (n < UPPERCASE_START_INDEX + LETTERS_IN_ALPHABET) return String.fromCharCode(n);

  // use a lowercase letter
  return String.fromCharCode(n + CHAR_GAP_SIZE);
}

export function decodeOrientation(r: string): Orientation {
  const asNumber = toNumber(r);
  if (!isNaN(asNumber)) {
    return {
      rotation: asNumber % NUM_ROTATIONS,
      reflection: asNumber >= NUM_ROTATIONS ? 1 : 0,
      color: 0,
    };
  } else {
    const charCode = r.charCodeAt(0);
    const charValue =
      charCode >= LOWERCASE_START_INDEX
        ? charCode - CHAR_GAP_SIZE - UPPERCASE_START_INDEX
        : charCode - UPPERCASE_START_INDEX;
    const o = charValue % NUM_SPATIAL_ORIENTATIONS;
    return {
      rotation: o % 4,
      reflection: o >= 4 ? 1 : 0,
      // color 0 is a digit not a letter so add 1
      color: Math.floor(charValue / NUM_SPATIAL_ORIENTATIONS) + 1,
    };
  }
}

And here’s the full file at this time.

One last note

Perhaps it goes without saying, but I’m not about to let anything go without saying in this article - I also got rid of the very first underscore by encoding the dimensions the same way as the coordinates.

Here’s a URL encoded at the time of this version:

8_8TA0_1R00_3R00_4R01_3R01_4P11_6FK2_2XA2_5II3_0W33_6V14_1ZC4_4Y65_7NL6_3UA7_1LL7_5

Compare this to the current version of that same board and you can see we still have a bit of a ways to go:

R88TA01P116FK22XA25II30W336V141ZC44Y657NL63UA71LL75R03041314

Version 2: Remove all the underscores

Up until now, I had no restrictions on dimensions of the board, but at this point I realized really large values were completely impractical, so I decided to set a limit on dimension of 99 (later I decreased that to 60, but let’s not get ahead of ourselves).

The important thing here is that if a dimension has max 2 digits, then we can instruct the “compiler” to count 1 or 2 digits of the x-dimension based on the casing of the pentomino letter name. If there’s 1 digit, it’ll be uppercase; if there’s 2 digits it’ll be lowercase. Then we can simply place the 2nd dimension after the 1st with no divider, and keep reading until we reach the next letter (or underscore, marking the start of extra color data, or the end of the URL).

Specifically, we can tell apart these two things:

• P0112 means P tile with orientation 0 at (1, 12)
• p0112 means P tile of orientation 0 and (11, 2)

But……..hold on. I want backwards compatibility. And there’s a big problem here.

The color-pentomino ambiguity

What does the fragment P011_1FN3 refer to?

1. A legacy URL with coordinates (11, 1) followed by the beginning of the F tile, with color 2 and orientation 6
2. A current URL with the coordinates (1, 1) followed by the start of the color section with F and N as color 1 and then some tile as color 3 afterwards

Uh, hm….

Well technically we could figure it out with some regex, something like it’s case 1 IFF the character immediately after the 3 is a digit or underscore. And keep in mind we have to figure this out before we finish decoding 11_1 - ideally before we get done processing the _.

I think it is possible, but…disgusting. I don’t want this.

Fortunately, there’s a very easy solution: Reverse the meanings of uppercase and lowercase. So we will instead ascribe these definitions:

• p0112 means P tile with orientation 0 at (1, 12)
• P0112 means P tile of orientation 0 and (11, 2)

Now there’s no ambiguity. If we see P011_ then we know 100% we’re looking at a legacy URL, because seeing a capital P followed by 2 digits means we’re expecting a digit next, not an underscore. Fantastic! We can tell on time what to do with the string 11.

I don’t think the code implementing this is particularly interesting, but you can check out this PR if you want - I included the notes I wrote out in Notepad while figuring out how to do this as a comment there.

Version 3: Get rid of everything we just did

After all that work, my immediate next step was to discard it all. You see, I decided on that limit of 99 quite naively; it was merely convenient after I thought of encoding the length of the character in the casing. But why do dimensions need to go up to 99? Absolutely no reason at all!

There are 12 pentominoes total, and each one has area 5. This means that there’s 60 squares of area total we can use (assuming we’re not doing something wild like using each tile many times, but I’m not exactly going out of my way to support that).

Therefore, I find it highly unlikely that anyone would ever need a board larger than 60x60. Realistically, there’s probably never a reason to go higher than 30, but maybe you want to do some kind of diagonal thing with a bunch of terrain.

Well, 60 is (barely) less than 10 + 26 + 26 (NUM_DIGITS + NUM_LETTERS_IN_ALPHABET + NUM_LETTERS_IN_ALPHABET). So in fact we could quite easily represent each coordinate as a single digit - no need for any casing shenanigans with the name of the pentomino, and we can free up its casing to refer to something else!

The tradeoff, of course, is human-readability of the resulting slug. And to be honest, I don’t think I would have made this change if I didn’t need that casing bit back.

Requirements to add surfaces

You see, I wanted to add support for solving on multiple surfaces: Pentominoes on Surfaces, not just Pentominoes. For example, here’s a board embedded on a projective plane. (I think this solve is particularly interesting; look at the positioning of the T and P tiles in the corners - they’re equivalent and interchangeable! It’s…a bit weird, but that’s what we get for trying to combine a rigid geometry with a nonorientable surface.)

But, uh, try looking at that same solution without any color. Can you tell anything that’s going on? I certainly can’t.²

There’s a big problem: Up until now, we only supported 6 colors. The reason is that we can’t fit more into the orientation character easily.

That’s fine, though. Remember, we’re getting a bit back from the pentomino name. We can repurpose this as one of the bits of color. So we have not-quite-3 bits of data from the orientation (3 bits would mean 8 colors, and we only have 6) and 1 bit of data from the casing of pentomino name. That’s all we need, as 6 * 2 = 12 = the number of pentominoes that exist.

Backwards compatibility

Making this change backwards compatible with significant code reuse was out of the question. I needed a clear marker somewhere in the URL as to which encoding I should be using. The obvious choice was the new piece of functionality that motivated this change: The surface.

So in deserializeUrl, I added this as the first two lines:

1
2

  const legacy = !!s[0].match(/[0-9]/);
  const config = legacy === true ? decodeSurfacelessUrl(s) : decodeUrl(s);

When I wrote the new decodeUrl function, I also refactored to use switch/case and produce something significantly more readable. Here’s urlConfig.ts after pushing this update, and I’ll also include part of the logic, specifically case 3 for curPos, which is where we look at pentominoes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

      case 3: {
        if (c.match("_")) {
          // no matter what section we're in, terrain or pentominoes
          curPos = 4;
          break;
        }
        switch (pentominoPosition) {
          case 0: {
            // name of pentomino
            if (c.match(PENTOMINOES.R.name)) {
              isTerrain = true;
              pentominoPosition = 2; // skip orientation
              // we'll push the first terrain tile in position 2
            } else {
              config.pentominoes.push({
                p: c,
                r: isTerrain ? "0" : "@", // charCode 64 if it's going to get updated
                c: "",
              });
              pentominoPosition = 1;
            }
            break;
          }
          case 1: {
            // orientation
            config.pentominoes[config.pentominoes.length - 1].r = c;
            pentominoPosition = 2;
            break;
          }
          case 2: {
            if (isTerrain) {
              config.pentominoes.push({
                p: PENTOMINOES.R.name,
                r: isTerrain ? "0" : "@", // charCode 64 if it's going to get updated
                c: "",
              });
            }
            curToken = decodeNumber(c).toString();
            pentominoPosition = 3;
            break;
          }
          case 3: {
            // hook into the original support of decoding coordinates that split on `_`
            // this way we have the same types when decoding legacy formats & also current formats
            config.pentominoes[config.pentominoes.length - 1].c = `${curToken}_${decodeNumber(c)}`;
            pentominoPosition = isTerrain ? 2 : 0;
            break;
          }
        }
        break;
      }

If you actually read that, you might be wondering about this bit:

1
2
3
4
5

            if (c.match(PENTOMINOES.R.name)) {
              isTerrain = true;
              pentominoPosition = 2; // skip orientation
              // we'll push the first terrain tile in position 2
            }

Well…I also made another improvement here. Terrain is the individual square that you can place wherever you want, with the intention that you place it prior to solving & construct a variety of fun puzzles this way (but you can also use it as “training wheels” and place it at the end of your solve in the leftover spaces).

Terrain has no color and no orientation. That means that repeating R0 (terrain with orientation of 0) is a complete waste of characters. If we encode all of our terrain coordinates consecutively at the very end of the pentominoes list, we can swap from not-terrain mode to terrain-mode; when we’re in terrain mode (triggered by noticing that the name of this tile is R), we’ll have only 2 characters per tile: x and y, one character for each.

(Could I do this for all pentominoes? Well…….maybe I could do something with my leftover [8-9o-z] that are invalid orientation values, where if you see one of these characters immediately after a pentomino then you’re expecting the immediate next “number” to be an encoding of the count (n) of pentominoes with this name, and then after that you repeat oxyoxyoxy (orientation-x-y) for each instance of that tile, counting down from n until you expect this tile’s list to be done. Is this practical? I don’t think so. It’s not even in the rules of typical Pentominoes to reuse a tile at all, and even still, you probably have 12 instances of a tile max. So this is maybe saving 10 characters, for an extremely niche edge case, in exchange for quite a bit of added complexity. I’ll pass.

Why would I need that trigger character to say “this tile’s list is gonna be weird”? Well, [0-9a-zA-X] are valid coordinate characters, and [0-8A-Za-n] are valid orientation characters. I need 25 valid characters for pentomino names (12 * 2 + 1 = # of pentominoes * # of color options + 1 terrain). There’s no way to write a one-character-long regex to say definitively “yes this is a _ character, so we must be using _ encoding.”)

Here’s an example slug created with this encoding (no color in the solve):

R88L505U110F412V215Z133I037N040Y246W254X063P766T271R07305274

This is actually the same as we’d currently encode this! Here’s a link to this pattern.

Keep in mind, at this point, I still hadn’t implemented any logic for surfaces. It was basically a state variable that was hard-coded as R with no way to change it. But that R at the start is what said “using version 3 URLs,” so it was vital to include.

3.1: One final improvement to terrain encoding

The reason that encoding is the same as the current one is that there’s no advantage from further serializing terrain. But sometimes, we can do better.

Consider this slug, which makes this empty board:

RbbR0001020304060708090a101112131718191a20212228292a3031393a404a606a7071797a80818288898a909192939798999aa0a1a2a3a4a5a6a7a8a9aa_0y1Iu2Wx3Vz4lT5Pn

In particular let’s look at the tiles in the first row: 0001020304060708090a. Notice anything about this? Every-other digit is 0. Hmm, that sounds like something we can compress. Maybe we could do something like:

• Indicator that this is compressed by x-axis
• (Encoded) number of tiles to expect (n)
• 0 (The x-coordinate)
• List of n y-coordinates

That’s wrong

There’s a critical mistake in that process. I’ll give you a hint: We’ve already made this mistake earlier on.

Another hint: I didn’t figure this out until my unit tests for encoding numbers were failing.

The answer is: If we’re saying “we have n things,” that’s off by one from a coordinate. Specifically, coordinates are 0-indexed, and the count of things is 1-indexed.

In other words, if we anticipate n pieces of terrain, the number that we need to encode in order to have [0-9a-zA-X] correctly correspond to n isn’t actually n, but n-1.

The mistake I previously made is that my dimensions are actually matching [1-9a-zA-Y], while my coordinates are correctly matching [0-9a-zA-X]. This is a really important difference,³ because I need not one but two “trigger” values to come after R to indicate that we have a special encoding:

• Y says “we’re going to keep the y-coordinate constant and show the list of crossing x-coordinates.”
• Z says “we’re going to keep the x-coordinate constant and show the list of crossing y-coordinates.”

Which one we pick can have a huge impact on the length of the resulting URL. Look at this slug (and board) for example:

RbbRZ90012346789a91012346789a

Here we’ve compressed along the x-axis. But if we compressed the other way, we’d instead get:

RY1001110112011301140116011701180119011a01

So to summarize, immediately after the R we have three cases:

1. See a Y, and know we’re going to have a keep-Y-constant encoding
2. See a Z, and know we’re going to have a keep-X-constant encoding
3. See any other character, and know we’re going to have our original encoding

There’s a cost of +1 character + (1 character/distinct (row or column) with terrain in it) for using this encoding, so quite often it will be cheapest to do no special encoding here at all.

One more small optimization

Without loss of generality, I’m going to talk about rows instead of “rows or columns” here.

I just lied to you - the cost is a bit less than 1 character/distinct row with terrain in it. You see, making diagonal lines is very a e s t h e t i c, and I want to improve things when there’s only 1 terrain in a given row. There’s a pretty natural improvement to make if you sort the rows|cols by # of tiles per row descending. Namely, the very last set of tiles will all have n=1 (encoded as n=0 of course).

So, once we get to 0 we’ll go back to displaying coordinates. No added cost of +1 character per row.

What does this look like in practice? Let’s look at this board (designed for the sake of this demo).

Without the optimization:

RZ5956789a5a56789a000011022033044

And with it:

RZ5956789a5a56789a00011223344

A slightly sneaky question

I chose that pattern pretty deliberately because it makes things a bit less confusing. But what if we looked at this board instead?

Here’s the terrain section with the optimization:

RY49012344a0123400a1928374655

Let’s break it up a bit for easier reading:

1

`${'RY'}${'4901234'}${'4a01234'}${'0'}${'0a1928374655'}`

So if we didn’t compress this, it would be the following, right?

1

`${'RY'}${'4901234'}${'4a01234'}${'00a019028037046055'}`

Not so fast. When we compress along the y-axis, we actually reverse the order in which the coordinates show up: We display first the y-coordinate and then a list of x-coordinates. If this list is of length 0, then we effectively are displaying a list of 1 transposed coordinate pair.

But when we go back to “display it normally” mode, we go back to “display it normally” mode. This expects a list of (x, y) and not (y, x).

Of course, if I’d wanted to, I could’ve designed the system so that once you reach 0 when you’re in the y-direction, you keep on going with y-before-x. But it was easier to code this way :)

One thing I am not doing

Consider this board. Its slug is:

RbbRY109a119a129a139a149a159a169a179a189a890123456788a012345678

Hmm, that first part looks kinda bad.

Ideally, we’d write:

RZ890123456788a012345678

Instead of:

RY109a119a129a139a149a159a169a179a189a

Could we…change orientation partway through?

No, this is too complicated. I’m not solving a partitioning problem in my URL encoding code.

Final version

Okay fantastic! Here’s the final code for encoding terrain. I’m doing a bit more string manipulation than I wanted to, but I found it pretty hard to keep everything as an array, and I needed to compare full lengths to determine which version to return.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

function terrainDictToString(dict: CompressedTerrain, direction: TerrainDirection): string {
  const length0: string[] = [];
  const lengthGT0: string[] = [];
  Object.entries(dict).forEach(([d, arr]) => {
    if (arr.length > 1) {
      lengthGT0.push(`${encodeNumber(arr.length - 1)}${d}${arr.join("")}`);
    } else {
      length0.push(`${d}${arr.join("")}`);
    }
  });
  return `${PENTOMINOES.R.name}${directionToLetter[direction]}${lengthGT0.join("")}${
    length0.length > 0 ? "0" : ""
  }${length0.join("")}`;
}

export function serializeTerrain(placedTerrain: StringifiedPlacedPentominoXY[]) {
  if (placedTerrain.length === 0) return "";
  const widthDict: CompressedTerrain = {};
  const heightDict: CompressedTerrain = {};
  placedTerrain.forEach((t) => {
    if (widthDict[t.y] === undefined) widthDict[t.y] = [];
    if (heightDict[t.x] === undefined) heightDict[t.x] = [];
    widthDict[t.y].push(t.x);
    heightDict[t.x].push(t.y);
  });
  const widthString = terrainDictToString(widthDict, TerrainDirection.width);
  const heightString = terrainDictToString(heightDict, TerrainDirection.height);
  const regularArray = placedTerrain.map((p) => `${p.x}${p.y}`);
  const regularString = `${PENTOMINOES.R.name}${regularArray.join("")}`;
  switch (Math.min(regularString.length, widthString.length, heightString.length)) {
    case regularString.length:
      return regularString;
    case widthString.length:
      return widthString;
    case heightString.length:
      return heightString;
  }
}

Decoding it isn’t that different from decoding pentominoes above, although it has significantly more cases. You can check it out if you want.

You can also take a look at my ticket, “make terrain encoding more compact”, where I outlined quite a bit of what I said above, but before I coded it. There were a couple points that took me some time to think about at the time but which in retrospect seem incredibly obvious, so I’ve not brought them up here.

Here’s a before/after of a board with a bunch of terrain (this is the same example posted at the start of the section):

RbbR0001020304060708090a101112131718191a20212228292a3031393a404a606a7071797a80818288898a909192939798999aa0a1a2a3a4a5a6a7a8a9aa_0y1Iu2Wx3Vz4lT5Pn

Gets shortened to:

RbbRZ90012346789a710123789a5201289a33019a140a160a37019a5801289a790123789aaa0123456789a_0y1Iu2Wx3Vz4lT5Pn

Conclusion

I’m pretty sad that I don’t have a good example URL that I copied down at every step of the way to see the % reduction that each step had. I’m sure I’m also missing a few considerations here, because this encoding is quite ridiculous at this point and has gone through so many iterations that I’ve lost track.

Another thing I haven’t mentioned at all is the number of unit tests I have for this code - vitest is telling me that I have 41 tests across 5 files, but many of them have multiple expect statements, so it’s a lot more than that. (There’s a few tests not related to the URL encoding code, but it’s mostly for this.) And I still pushed a few bugs to production, especially at the very last stage, with terrain encoding.

When I started this project, I thought the “hard part” was going to be going from a grid that contains the centers of each tile to a painted grid that knows exactly where any problems are (tiles overlapping, tiles hanging off the edge). Yeah, no. That was surprisingly straightforward, and encoding the URL + tests is close to half my total LOC for the entire project. (Though it’s perhaps unfair to count tests there.)

Anyway, I’m pretty happy where the encoding is now - it’s still human-readable enough that I can modify it directly, you can double-click to highlight the entire slug, and most characters can theoretically use the majority of their 63 allowed values ([0-9A-Za-z_]).

I also have an escape hatch to re-version in the future if I need to - there are only a few possible surfaces (R, S, K, P, T, C, M) (at the time of publication, I still haven’t implemented the sphere, cylinder, or Mobius band). So if I need to, I can lowercase these, or use a completely distinct set of letters to represent these shapes. That should give me another 5000 words worth of room to play with!