-
Notifications
You must be signed in to change notification settings - Fork 10
/
Copy pathindex.html
141 lines (131 loc) · 5.52 KB
/
index.html
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title></title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link href="css/main.css" rel="stylesheet">
</head>
<body>
<div id=page>
<header>
<h1>
Code Golf Experiment
</h1>
<em>by <a href="http://eike.se/nd">Eike Send</a></em>
</header>
<p>
I love to code.
</p>
<p>
So when I stumbled upon <a href="http://codegolf.stackexchange.com/questions/6043/were-no-strangers-to-code-golf-you-know-the-rules-and-so-do-i">a code golf stack exchange</a> I was intrigued. The question was to compress the RickRolling lyrics and provide code which would decompress it without using external libraries.
</p>
<p>
I found the most popular <a href="http://codegolf.stackexchange.com/questions/6043/were-no-strangers-to-code-golf-you-know-the-rules-and-so-do-i#6129">JavaScript answer</a> very interesting, so I started reverse engineering it.
</p>
<p>
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:
</p>
<pre>
Somewhere Sometime Someplace
</pre>
<p>would become</p>
<pre>
#where #time #place#Some
</pre>
<p>Now repeat until no sensible replacement is possible.</p>
<p>I wanted like to create a solution like that myself.</p>
<h2>The suffix tree</h2>
<p>
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.
</p>
<p>
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 <a href="https://www.google.com/search?q=longest+repeated+substring+problem">longest repeated substring problem</a> 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!
</p>
<p>
I looked around for a suffix tree implementation in JavaScript, and <a href="http://www.allisons.org/ll/AlgDS/Tree/Suffix/">I found one</a>, but I didn't like it. So I rolled my own <a href="https://github.com/eikes/suffixtree/blob/master/js/suffixtree.js">JavaScript suffix tree implementation</a>, 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.
</p>
<p>
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.
</p>
<p>
Check out the demo below or on <a href="http://jsfiddle.net/eikes/Sws4g/1/">jsfiddle</a> or the <a href="demo.html">super plain demo</a> and <a href="http://codegolf.stackexchange.com/questions/6043/were-no-strangers-to-code-golf-you-know-the-rules-and-so-do-i/6277#6277">upboat my answer on codegolf.stackexchange.com</a>.
<textarea id=lyrics>
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
</textarea>
<button id=newcode>Create new code</button>
<h2>Code</h2>
<p>This code is created using the lyrics above</p>
<pre id=code></pre>
<p>Length: <span id=length></span></p>
<p><button id=eval>Eval this code</button>
(You can also copy and paste it into the console of your browser)</p>
<pre><code id=uncompressed></pre>
</div>
<script src="js/suffixtree.js"></script>
<script src="js/main.js"></script>
</body>
</html>