I love to code.
So when I stumbled upon a code golf stack exchange I was intrigued. The question was to compress the RickRolling lyrics and provide code which would decompress it without using external libraries.
After inserting a couple of console.log calls I found out, that the author had a string which was repeatedly split by a set of characters that were in a seperate list. The last element of the split was used to join the seperated items again. Sounds complicated, but it isn't. Example:
Somewhere Sometime Someplace
#where #time #place#Some
Now repeat until no sensible replacement is possible.
I wanted like to create a solution like that myself.
It seemed pretty easy. Take the longest substring that occurs at least twice, yank it out and put in a replacement character, append that character and the substring. When repeated often enough, this will lead to a short enough code which could be used for decompression.
The problem was that I didn't know how to find that substring. Some Google-foo led me to the conclusion that this problem is known as the longest repeated substring problem and guess what, it has been solved. I didn't want to get into any details, but it became clear that I needed a suffix tree for that, because the deepest node in a suffix tree represents the longest repeated substring, which is just neat!
After that, it was only a matter of pluging things together and, voila, I was able to take the lyrics, compress them and wrap the compressed text in some code and get a decompressed version that was exactly the same.
This code is created using the lyrics above
(You can also copy and paste it into the console of your browser)