I've implemented a simple Shape Up Editor on my Flutter page, that passes data back to my site without any backend, passing all of the data for a Shape Up component. But the size of my component can be pretty wordy.
For example, the url to load this bumble bee is:
/shapeup/27,48,0,0,0,0,31,0,0,0,0,0,127,128,0,0,0,1,255,248,0,0,0,7,255,254,0,0,0,31,255,255,0,0,0,127,255,255,0,0,0,255,255,255,0,0,127,255,255,255,0,0,255,255,255,254,0,1,255,255,255,252,12,3,255,255,255,224,19,127,255,255,252,0,33,255,255,255,254,0,65,255,255,255,254,0,129,255,255,255,254,0,15,255,255,255,254,0,8,127,255,255,255,0,16,127,255,255,255,0,16,62,127,255,255,0,32,29,191,255,254,128,32,9,111,128,204,64,0,1,107,0,102,0,0,2,98,0,35,0,0,4,70,0,33,0,0,0,132,0,16,128,0,1,8,0,0,128,0,0,8,0,0,64The data payload is 497 characters long. Surely this can be made smaller!
So how do we make it smaller? Introduce a larger variety of characters! Right now I'm only taking advantage of 0-9 and the comma.
Since I'm trying to use this data in a url param, I've picked a very standard set of common url friendly characters to add to my arsenal (a-z A-Z ! $) introducing 54 additional characters to our 0-9, bringing the count up to 64.
I chose 64 because Math.pow(64,4) == 256<<16. This translates to "I can have a base64 value with 4 characters that can hold the data for 3 blocks of values within 1 and 255." 255,255,255 becomes $$$$.
I can skip on the comma by guaranteeing that all 4 characters are always present instead of truncating any 0s on the left hand side so 255,255,255,255,255,255 is still only $$$$$$$$, 23 characters become 8.
Our bumble bee's url becomes:
/shapeup/030r0000000v0000081$0g000fz$1M000fX$7M000f$$vM000f$$$M000f$$$TY00f$$$$Y00fX$$$Y13fP$$$Y34!3$$$Z$8g3Y$$$$gg3!$$$$wg3!$$$$3M3!$$$$203!$$Z$403$$$Z$403$$TY!803$$XYt883!w6Y9043c06I1001C0682000z04o4000x08g0080g00w1080000w00400Our payload is down to 220 characters, now 2.26x smaller than the original. That's great!
But $$$$$$$$ can be optimized further. To reduce repeating sets of values, I am going to introduce an additional 6 characters (^*-_~`) to represent counts. $$$$$$$$ becomes $`.
Since there wouldn't be any savings for counting occurences less than 3, it only requires 6 characters to support x3-8.
$$ $$
$$$ $^
$$$$ $*
$$$$$ $-
$$$$$$ $_
$$$$$$$ $~
$$$$$$$$ $`
Our url becomes:
/shapeup/030r0~v0-81$0g0^fz$1M0^fX$7M0^f$$vM0^f$^M0^f$^TY00f$*Y00fX$^Y13fP$^Y34!3$^Z$8g3Y$*gg3!$*wg3!$*3M3!$*203!$$Z$403$^Z$403$$TY!803$$XYt883!w6Y9043c06I1001C06820^z04o40^x08g0080g00w1080*w00400The result is 187 characters long, 1.18x smaller than the version without counts and 2.54x smaller than the original.
The next thing I did was optimize every level I have, and look for common pairs that I can also replace with special characters.
00: 183 $$: 123 0f: 97 Y0: 96 M0: 94 3$: 92 0^: 86 f$: 82 01: 80 03: 77
There are two clear winners, 00 and $$. I will replace both of these with two new characters, @ and =, bringing the total to 72.
176 characters long! 1.06x smaller and 2.82x smaller than the original.
/shapeup/030r0~v0-81$0g0^fz$1M0^fX$7M0^f=vM0^f$^M0^f$^TY@f$*Y@fX$^Y13fP$^Y34!3$^Z$8g3Y$*gg3!$*wg3!$*3M3!$*203!=Z$403$^Z$403=TY!803=XYt883!w6Y9043c06I1@1C06820^z04o40^x08g@80g@w1080*w@4@If we check for common occurences again, a lot of the runners up were knocked off of the list because they shared a 0 or a $. The new winner, is 0^. So I'm introducing a 73rd character, ', to replace this pattern.
0^: 86 Y0: 81 0f: 80 3$: 78 M0: 76 01: 69 0$: 61 f$: 57 $0: 52 $M: 52
169 characters long. 1.04x smaller and 2.94x smaller than the original.
/shapeup/030r0~v0-81$0g'fz$1M'fX$7M'f=vM'f$^M'f$^TY@f$*Y@fX$^Y13fP$^Y34!3$^Z$8g3Y$*gg3!$*wg3!$*3M3!$*203!=Z$403$^Z$403=TY!803=XYt883!w6Y9043c06I1@1C0682'z04o4'x08g@80g@w1080*w@4@Why stop there though? I'm introducting a 74th character, ", that always has a trailing character to represent a common pattern's index. I've identified 46 patterns with a length of 3 that occur more than 5 times across my library of puzzles.
3$0, Y0$, M0*, !f$, @20, 080, 0Y0, 0f0, $`$, 3w0, fYf, 0fU, "23, c01, Y07, 0fY, !3$, 020, 3M3, Y@f, 0fM, $"3, $^Y, 640, 030, 1Y0, 1M0, Yf=, @3w, 0c0, "22, 0M0, $3$, !$^, 3$v, 0g0, o'o, M3", "1M, f$^, M3M, 0s0, 0v0, @80, $*", 03"
156 characters long. 1.08x smaller and 3.19x smaller than the original.
/shapeup/"or0~v0-81$0g'fz$1M'fX$7M'f=vM'"DM'"DT"j"IjX"m13fP"m34"g^Z$8g3Y$*gg3!$*wg3!"Ii!$*203!=Z$403$^Z$403=TY!803=XYt883!w6Y9043c06I1@1C0682'z04o4'x08g"Hg@w1"5*w@4@46 patterns doesn't totally cover every possible index, so I decided to look for new types of patterns, not just *** but patterns like * * *, ** *, * **, and so on. After adding 26 additional patterns, my string is 154 characters long. 1.01x smaller and 3.23x smaller than the original.
$ $ $, " " ", $M $, 01 0, = $ $, 01 ', M f 0, 0 " 0, 0 " ", 0 " 0, M " M, 3 0 ", M 0 ", m q G, $ $ f, Y $ Y, " f ", 1w0, 0 " ", $^ $, 1 "V, 1" Y, " " M, $M $, 0 " ", " fw
/shapeup/"or0~v0-81$0g'fz$1M'fX$7M'f=v"U'D'"DT"j"IjX"m13fP"m34"g^Z$8g3Y$*gg3!$*wg3!"Ii!$*203!=Z$403"*Z403=TY!803=XYt883!w6Y9043c06I1@1C0682'z04o4'x08g"Hg@w1"5*w@4@Not a huge gain, but every little bit counts. We're still down 2 characters and we didn't have to introduce any new characters.
I'm not out of ideas yet. I want to implement another new character to introduce another new technique that isn't about identifying common patterns across all puzzles, but one that specifically looks for common patterns in our current puzzle. If I put our new character, ;, before the first occurence of this 2 character pattern, I can replace all future occurences with our new character. As an example, 0130101401 would become ;013;;4;
For our bumble bee the pattern 3! appears 4 times. If we can designate one character to replace these 4 patterns, we'll cut off 2 characters. And if we target another common pattern, 'f with another new character, :, we can cut off 1 more. If no pattern appears more than twice, we can avoid this technique altogether as it doesn't help us at all.
151 characters long. 1.02x smaller and 3.29x smaller than the original.
/shapeup/"or0~v0-81$0g:'fz$1M:X$7M:=v"U'D'"DT"j"IjX"m13fP"m34"g^Z$8g3Y$*gg;3!$*wg;"Ii!$*20;=Z$403"*Z403=TY!803=XYt88;w6Y9043c06I1@1C0682'z04o4'x08g"Hg@w1"5*w@4@Next I can't help but notice that my bumble bee still has the pattern 403 repeating twice. I also see 043, which is so close as well. I'm introducting 6 new characters, <>()[], to handle all of the permutations of a 3 character pattern.
A 3 character pattern, at most, has 6 permutations, hence the 6 new characters. The permutations for 403 are: 403 034 340 043 430 304.
148 characters long. 1.02x smaller and 3.36x smaller than the original.
/shapeup/"or0~v0-81$0g:'fz$1M:X$7M:=v"U'D'"DT"j"IjX"m13fP"m34"g^Z$8g3Y$*gg;3!$*wg;"Ii!$*20;=Z$<403"*Z<=TY!803=XYt88;w6Y9)c06I1@1C0682'z04o4'x08g"Hg@w1"5*w@4@We may as well add in {} to replace the most active 2 character patterns and their one other permutation (the only thing you can do with the 2 characters is flip them). But just matching for one other permutation doesn't cast a really big net, so I'm introducing 2 more characters, + and |, to replace instances where this pattern appears with another character in between the two. For instance, in this puzzle, 0-8, 80, 068, and 08 all appear. Minimized, 0-8 80 068 08 becomes +0-8 } +6 {, down 2 characters.
146 characters long. Our final result is 1.01x smaller and 3.4x smaller than the original.
/shapeup/"or0~v+0-81$0g:'fz$1M:X$7M:=v"U'D'"DT"j"IjX"m13fP"m34"g^Z$8g3Y$*gg;3!$*wg;"Ii!$*20;=Z$<403"*Z<=TY!}3=XYt88;w6Y9)c06I1@1C+62'z04o4'x{g"Hg@w1"5*w@4@Sure, the url is still pretty big, but we're storing every piece of data required for our entire bumble bee! I've reached my target goal: get the payload to 150(146) characters, achieve a compression ratio of under 30(29.38)%.
By the way, I've made this minimization technique into a standalone package available on github. I also found a better way to describe this data in