Code Golf Experiment

by Eike Send

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.

I found the most popular JavaScript answer very interesting, so I started reverse engineering it.

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

would become

#where #time #place#Some

Now repeat until no sensible replacement is possible.

I wanted like to create a solution like that myself.

The suffix tree

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!

I looked around for a suffix tree implementation in JavaScript, and I found one, but I didn't like it. So I rolled my own JavaScript suffix tree implementation, it may not be the fastest, but the source code should be easy to read and implementing a function to find the longest repeated substring was pretty straight forward.

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.

Check out the demo below or on jsfiddle or the super plain demo and upboat my answer on codegolf.stackexchange.com. We're no strangers to love You know the rules and so do I A full commitment's what I'm thinking of You wouldn't get this from any other guy I just wanna tell you how I'm feeling Gotta make you understand Never gonna give you up Never gonna let you down Never gonna run around and desert you Never gonna make you cry Never gonna say goodbye Never gonna tell a lie and hurt you We've known each other for so long Your heart's been aching but You're too shy to say it Inside we both know what's been going on We know the game and we're gonna play it And if you ask me how I'm feeling Don't tell me you're too blind to see Never gonna give you up Never gonna let you down Never gonna run around and desert you Never gonna make you cry Never gonna say goodbye Never gonna tell a lie and hurt you Never gonna give you up Never gonna let you down Never gonna run around and desert you Never gonna make you cry Never gonna say goodbye Never gonna tell a lie and hurt you (Ooh, give you up) (Ooh, give you up) (Ooh) Never gonna give, never gonna give (Give you up) (Ooh) Never gonna give, never gonna give (Give you up) We've know each other for so long Your heart's been aching but You're too shy to say it Inside we both know what's been going on We know the game and we're gonna play it I just wanna tell you how I'm feeling Gotta make you understand Never gonna give you up Never gonna let you down Never gonna run around and desert you Never gonna make you cry Never gonna say goodbye Never gonna tell a lie and hurt you Never gonna give you up Never gonna let you down Never gonna run around and desert you Never gonna make you cry Never gonna say goodbye Never gonna tell a lie and hurt you Never gonna give you up Never gonna let you down Never gonna run around and desert you Never gonna make you cry Never gonna say goodbye Never gonna tell a lie and hurt you Create new code

Code

This code is created using the lyrics above

Length:

Eval this code (You can also copy and paste it into the console of your browser)