We're no strangers to code golf, you know the rules, and so do I
Ruby 576 557 556 (552) chars && PHP 543 chars
Another search-and-replace solution. Note that this form of solution is essentially a Grammar-based Compression Code http://en.wikipedia.org/wiki/Grammar-based_code Check out http://www.cs.washington.edu/education/courses/csep590a/07au/lectures/lecture05small.pdf for a simple to understand compression example.
I've written the substitution rules so that the starting character for each substitution is computed (they are in sequential ASCII order); it need not be present in the transition data.
i=44
s="We; n7trangMsL8loT63Ke rules5s8d8I
AJull commit4nt'sChatFKink: of6CHldn'tRetKisJrom<ny@Ruy-/A= if?<sk 42DS'tLE 4?;Lo8bli=L7ee..
O,R1)O,R001)/-.."
"
I justCannaLE?2Gotta >u=Msta=.|
Ng1Nlet? downNrun<rH=5desMt?N>cryNsayRoodbyeNtE< lie5hurt?|
We'T3n each@Jor s8lSg6r hear9<ch: but6;Lo7hyL7BInsideCe both3Cha9Ro: S
We3KeRa45we;QplB|1)O)NgiT, nPgiT
(G|iT? up| howFJeel:
| know|me|<= |
YH|8s|o |t's been|ing|'re| a|nd|make? | yH| othM|A|ay it
| w|D|ell| I'm|G|ou|I| f|Lh| t|er|
NP|
(Ooh|eTrQ|RSna | g|on|ve".scan(/[^|]+/){s.gsub!((i+=1).chr,$&)}
puts s
implementation notes
- The above solution is 556 chars long, but scores 552 with the removal of newlines from source code. It is slightly better scoring than the original 556 char solution I had that scored 554.
- I use "known" instead of "know"; this makes the verse repetition identical and should make the compression better
- I originally optimized the rules by repeatedly searching for the substitution that would yield the most decrease in current code size. However, I found that RiderOfGiraffe's substitution rules were (slightly) better than mine, so I'm now using a modified version of his rules.
- I spent time reordering the rules so that a single substitution pass can decompress everything.
- Due to the computed initial character in the substitution rules, my rule list has a rule for every character in a contiguous ASCII range. I found that having some "dummy" substitution rules was better for code size than having all real rules and coding a final text fixup substitution.
- This example is small enough that you probably could successfully write a program to find the optimal (least total cost) set of rules. I would not expect doing this would yield size reductions of more than a few bytes.
older implementation
This older implementation has 576 characters and started with substitution rules from ugoren's bash/sed implementation. Ignoring the substitution variable renaming, my first 28 substitutions are exactly the same as those performed in ugoren's program. I added a few more to lower the overall byte count. This is possible because my rules are more efficiently represented than those in ugoren's implementation.
i=44
puts"WeM noHtraLersB loJ;6 C rules=so do $
& full commitment'sGhat<thinkDof;Gouldn'tKet this fromFny oCrKuy.
-&E if9ask me1~on't @ me:MBo bliEBHee//
3300-.//|
We'J6n each oCr forHo loL;r hear2FchDbut;MBoHhyBH7$nsideGe both6Gha2ADon
We6 CKame=weM>pl7|
$ justGanna @:1#otta 8uEerstaE/|
5?9up5let9down5runFrouE=desert:58cry5sayAodbye5@F lie=hurt:|(Ooh)5?, nI>?
(#4| how<feeliL
|t's been|(Ooh,K4|iJ9up)
|
NI>| know|ay it
|make9|: | you|
You| $'m |FE |Anna |giJ|tell|Ko| to|the|iL |nd| a| w| s|eJr|ve| g|ng|'re".split("|").inject{|m,o|m.gsub((i+=1).chr,o)}.tr('&~#$',"ADGI")
I did not try optimizing the substitution rules in this one.
contest notes
The search-and-replace decompression scheme works well for this contest because most languages have pre-built routines that can do this. With such a small amount of text to be generated, complex decompression schemes do not seem to be feasible winners.
I've used only ASCII text and also avoided using unprintable ASCII characters. With these restrictions, each character in your code can only represent up to a maximum of 6.6 bits of information; this is very different than to real compression techniques where you use all 8 bits. In some sense, it is not "fair" to compare to gzip/bzip2 code size because those algorithms will use all 8 bits. A fancier decompression algorithm may be possible if you can include traditionally unprintable ASCII in your strings AND each unprintable character is still written in your code as a single byte.
PHP Solution
<?=str_replace(range('-',T),split(q,"
I justCannaLE?2Gotta >u=Msta=.q
Ng1Nlet? downNrun<rH=5desMt?N>cryNsayRoodbyeNtE< lie5hurt?q
We'T3n each@Jor s8lSg6r hear9<ch: but6;Lo7hyL7BInsideCe both3Cha9Ro: S
We3KeRa45we;QplBq1)O)NgiT, nPgiT
(GqiT? upq howFJeel:
q knowqmeq<= q
YHq8sqo qt's beenqingq'req aqndqmake? q yHq othMqAqay it
q wqDqellq I'mqGqouqIq fqLhq tqerq
NPq
(OohqeTrQqRSna q gqonqve"),"We; n7trangMsL8loT63Ke rules5s8d8I
AJull commit4nt'sChatFKink: of6CHldn'tRetKisJrom<ny@Ruy-/A= if?<sk 42DS'tLE 4?;Lo8bli=L7ee..
O,R1)O,R001)/-..");
The above solution takes the PHP from "a sad dude" and combines it with my substitution rules. The PHP answer turns out to have the shortest decompression code. See http://ideone.com/XoW5t
Whitespace - 33115 characters
StackExchange chomped my answer, here is the source: https://gist.github.com/lucaspiller/2852385
Not great... I think I may be able to shrink it down a bit though.
(If you don't know what Whitespace is: http://en.wikipedia.org/wiki/Whitespace_(programming_language))
Bash / Sed, 705 650 588 582 chars
Logic:
The basic idea is simple replacement. Instead of writing, for example, Never gonna give you up\nNever gonna let you down, I write Xgive you up\nXlet you down and replace all X with Never gonna.
This is achieved by running sed with a set of rules, in the form s/X/Never gonna /g.
Replacements can be nested. For example, Never gonna is common, but so is gonna in other contexts. So I can use two rules: s/Y/ gonna/g and s/X/NeverY/g.
When adding rules, parts of the song texts are replaced by single characters, so it gets shorter. The rules become longer, but if the string replaced is long and frequent, it's worth it.
The next step is to remove repetition from the sed commands themselves. The sequence s/X/something/g is quite repetitive.
To make it shorter, I change sed commands to look like Xsomething. Then I use sed to convert this into a normal sed command. The code sed 's#.#s/&/#;s#$#/g;# does it.
The final result is a sed command, whose arguments are generated by another sed command, in back-quotes.
You can find a more detailed explanation in this link.
Code:
sed "`sed 's#.#s/&/#;s#$#/g#'<<Q
LMWe'veKn each o!r for-o longPr hearHzchJbutP're2o-hy2-@Insidexe bothKxhaHCJonMWeK ! game+we'reZpl@
TMI justxanna _UFGotta QuXerstaXR
RM~Squp~letqdown~runzrouX+desertU~Qcry~sayCodbye~_z lie+hurtU
E(Ooh)~S, neverZSM(GV
F how=feelingM
Ht's been
%(Ooh, gV
Vivequp)M
~MNeverZ
K know
@ay itM
Qmakeq
qU
U you
PMYou
= I'm
+zX
ZCnna
Sgive
_tell
C go
2 to
!the
Jing
Xnd
z a
x w
- s
M\n`"<<_
We're no-trangers2 lovePK ! rules+so do I
A full commitment'sxhat=thinkJofPxouldn't get this fromzny o!r guyT
LAX ifqask meFDon't _ meU're2o bliX2-eeRRMM%%EELTRR
Notes:
The decompression engine is just 40 characters long. The other 543 are the translation table and compressed text. bzip2 compresses the song to 500 bytes (without the engine, of course), so there must be room for improvement (though I don't see how I'd add Huffman encoding or something like this cheap enough).
<<Q (or <<_) is used to read until a given character. But the end of script (or backquote expression) is good enough. This sometimes causes a warning.
Older and simpler solution, 666 chars:
sed "
s/L/ MWe'veKn each other for so longMYour heart's been aching butMYou're too shy to say itMInside we bothK what's been going onMWeK the game+we'reZplay itM/;
s/T/MI just wanna tellU how I'm feelingMGotta makeU understandR/;
s/R/M ~giveU up~letU down~run around+desertU~makeU cry~say goodbye~tell a lie+hurtU/g;
s/E/(Ooh)~give, neverZgiveM(GV/g;
s/V/iveU up)M/g;
s/U/ you/g;
s/+/ and /g;
s/K/ know/g;
s/~/MNeverZ/g;
s/Z/ gonna /g;
s/M/\n/g
"<<Q
We're no strangers to love
YouK the rules+so do I
A full commitment's what I'm thinking of
You wouldn't get this from any other guyT
LAnd ifU ask me how I'm feeling
Don't tell meU're too blind to seeRRM M(Ooh, gV(Ooh, gVEEL TRR