Ruby (549)(549) binary chars
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 replace "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,256128).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<<=8;m+=x|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})")}
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.
Note that althoughIf you run the compressedcurrent code-packer program on the above short solution, you get an expansion to 627 bytes. The packed string itself is over 100about 50 bytes shorter than the original program, most ofbut the savings is takendecompression code blows up by the decompressionoverall 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.