Ruby (549) binary chars
I recently found that you can enter arbitrary binary characters (including those with value between 128 and 255) in ruby strings, as long as you follow some simple ruby escaping rules. Packing information into binary enables more efficient compression. Unfortunately, display of the "code", when written in binary, is problematic; thus, I created a generic program that reads in an existing ruby text program (assumed to not use chars with value > 127), and creates a secondary ruby source code that does exactly the same thing. This secondary code uses one long string with binary characters in it, and can be shorter than the original, in terms of number of bytes.
Here is the source "code-packer.rb"; it transforms input ruby source code into equivalent "compressed" output ruby source code. All it really does is binary packing of the original source code string, along with printing code for binary unpacking of the binary string.
Addendum: It appears that the original code-packer produces code that does not represent valid UTF-8 encoded binary strings, and thus is technically invalid according to the rules. To make it valid, we must use only character values up to 128. I recently read the UTF-8 encoding rules, and trying to use all 8 bits and generate UTF-encoded strings is not fruitful because most binary strings (over half of all possibly binary strings of any given length) will not represent valid UTF-8 encodings. So using straight up 7-bit ascii code is more efficient. I've modified the code-packer code below to produce only unreadable 7-bit ascii strings by replacing "256" with "128" and "<<8" with "<<7". This makes the packing compression idea not worthwhile for small programs (< 700 or so bytes), although it does still reduce Actven's 1000+ byte solution down to 937 bytes.
#!/usr/bin/env ruby
# This program takes a ruby file as input
# and outputs an equivalent ruby file as output that
# is functionally equivalent, but "compressed".
# Compression is done by creating a string representing the original program
# which contains unprintable characters (including chars with value between 128 and 255)
# The string is just a binary packed version of the input program text.
#
# the "decompression" algorithm for the string is written in ruby as part of the output,
# along with an eval on the decompressed string.
# NOTE: assumes input file doesn't contain any unprintable chars with value > 126, otherwise this will fail.
DEBUG=false # turn on debug to produce larger code that uses code sequences for the unprintable characters,
# and prints debugging information, and ruby code instead of executing it.
#DEBUG=true
# returns array of frequency counts for str
def frequency_count(str)
freq= Array.new(127,0)
str.bytes {|b| freq[b]+=1}
freq
end
# figure out an appropriate contiguous
# range of characters (via ASCII) to use for representing str.
# returns
# 1) forward hash of chars, when applied to str, give only chars in the range
# 2) backward hash of chars for undoing #1
# 3) start character of range
# 4) length of range
def translate_range(str)
freq = frequency_count(str)
forward_hash = {}
backward_hash = {}
left_index = 0
right_index = 126
# ignore unused top range
while right_index > 0 && freq[right_index] == 0
right_index -= 1
end
if right_index == -1
raise "Error: empty input string"
end
last_char_index = right_index
# figure out chars to swap to get contiguous range
# we want to minimize number of swaps, so this
# naive approach won't always yield the best results.
while left_index < right_index do
if freq[left_index] == 0
left_index += 1
next
end
if freq[right_index] > 0
right_index -= 1
next
end
# found char on left that can move to empty spot on right
forward_hash[left_index] = right_index
backward_hash[right_index] = left_index
freq[right_index] = 1 # mark it as filled.
left_index +=1
right_index -=1
end
while freq[left_index]== 0
left_index +=1
end
[forward_hash, backward_hash, left_index, last_char_index - left_index + 1]
end
# translates text into big num of given base, assuming all chars in string
# are in range start_char..(start_char+base-1)
def text_to_num (str, start_char, base)
num = 0
if (str[0] == start_char)
raise "Sorry.. I can't handle strings that start with #{start_char.chr}"
end
str.reverse.bytes {|x| num = num * base + (x - start_char)}
num
end
# translates back from num to text.
def num_to_text (num, start_char, base)
text = ""
while num > 0 do
text += (num % base + start_char).chr
num /= base
end
text
end
# translates from packed num string to original string, without translation part
# will be output into code.. present here for testing.
def packed_num_decode(str, start_char, base)
m=0;str.bytes{|x|m=(m<<8)+x}
t=""
while m>0 ; t+=(m%base+start_char).chr;m/=base end
t
end
# takes a string used for input into translate, and escapes
# chars with special meaning (^ at beginning, '-' between two chars, backslash)
def tr_escapes(str)
str.sub("\\","\\\\\\\\").sub(/^\^/,"\\^").sub(/(.)-(.)/m, "\\1\\-\\2")
end
# takes a binary string, and escapes out characters problematic
# when writing the string within single quotes.
# this includes ' and \.
def packed_string_escapes(str)
chars_to_escape = "\\\'"
escaped_str = ""
str.bytes {|b| if chars_to_escape.include?(b.chr)
then
escaped_str += "\\" + b.chr
else
escaped_str += b.chr
end
}
escaped_str
end
#======== Main program ========
if (ARGV.length != 2)
puts "Usage: #{__FILE__} <input program> <output program>"
end
inputfile = ARGV[0]
outputfile = ARGV[1]
inputtext = File.read(inputfile)
input_info = translate_range(inputtext)
from = ""
to = ""
input_info[0].each_pair {|x,y| from += x.chr ; to += y.chr }
input_mod = inputtext.tr(tr_escapes(from), tr_escapes(to))
input_num = text_to_num(input_mod, input_info[2], input_info[3])
packed_num = num_to_text(input_num,0,128).reverse # do reverse so decompression code doesn't have to do it.
if (DEBUG) then
pretext="input_mod=#{input_mod.inspect}\nfrom=#{from.inspect}\nto=#{to.inspect}\n"
packed_num_with_quotes = packed_num.inspect
operation = "puts \"t=\#\{t.inspect\}\";puts"
else
pretext=""
packed_num_with_quotes = "'" + packed_string_escapes(packed_num) + "'"
operation = "eval"
end
start_char = input_info[2]
base = input_info[3]
from = ""
to = ""
input_info[1].each_pair {|x,y| from += x.chr ; to += y.chr }
from_str = tr_escapes(from).inspect
to_str = tr_escapes(to).inspect
File.open(outputfile, "w+") {|f|f.puts("#{pretext}m=0;#{packed_num_with_quotes}.bytes{|x|m<<=7;m+=x};" +
"t=\"\";while m>0;t+=(m%#{base}+#{start_char}).chr;m/=#{base} end;" +
"#{operation} t.tr(#{from_str},#{to_str})")}
Although the above can be applied to any ruby code (and could be modified to work with other languages), I've applied it to the following short 556 char solution:
i=47
puts"W> n:trangMsL;loT96Ke rules8s;d;I
AJull commit7nt'sHhatVKink= of9HXldn'tRetKisJrom?nyERuy02A@ ifC?sk 75DS'tLU 7C>Lo;bli@L:ee11
O,R4)O,R334)2011|
I justHannaLUC5Gotta Bu@Msta@1|
Ng4NletC downNrun?rX@8desMtCNBcryNsayRoodbyeNtU? lie8hurtC|
W'T6n eachEJor s;lSg9r hear<?ch= but9>Lo:hyL:FInsideHe both6Hha<Ro= S
W6KeRa78we>QplF|4)O)NgiT, nPgiT
(G|iTC up| howVJeel=
| know|me|?@ |
YX|;s|o |t's been|ing|'re| a|nd|A|makeC | yX|D| othM|ay it
|G| w|I| f|Lh| t|er|
NP|
(Ooh|eTrQ|RSna | g|on|ve|ell| I'm|We|ou".split("|").inject{|m,o|m.gsub((i+=1).chr,o)}
The short 556 character solution above is essentially my previous solution, with substitution characters changed, so that the binary packing works better.
If you run the original code-packer program on the above short solution, it will generate a solution that is valid ruby source code that is 549 bytes long. Running this generated ruby source code will print out the required lyrics.
Note that although the compressed string is over 100 bytes shorter than the original program, most of the savings is taken up by the decompression code.
If you run the current code-packer program on the above short solution, you get an expansion to 627 bytes. The packed string itself is about 50 bytes shorter, but adding the decompression code blows up the overall size.
Thanks to the commenters for pointing out the technicalities of UTF-8 encoding. To me, the "valid UTF-8" restriction seems rather arbitrary-- if you're going to allow unprintable ascii characters in valid code, why shouldn't you also allow "invalidly coded UTF-8 characters?" The original code-packer still does generate valid ruby source code that really takes up only 549 bytes of storage when run on the 556-byte solution presented above.
