More compact base builder strings

gistfile1.js

// all buildings with weights,
// be sure to use your own datatypes.
var BUILDINGS = [
    [40, 'No Building'],
    [ 6, 'Harvester Tiberium'],
    [ 6, 'Harvester Crystal'],
    [ 6, 'Power Plant'],
    [ 1, 'Tiberium'],
    [ 1, 'Crystal'],
    [ 3, 'Silo'],
    [ 3, 'Accumulator'],
    [ 3, 'Refinery'],
    [ 1, 'Construction Yard'],
    [ 1, 'Command Center'],
    [ 1, 'Defense HQ'],
    [ 1, 'Factory'],
    [ 1, 'Barracks'],
    [ 1, 'Air Field'],
    [ 1, 'Defense Facility'],
    [ 1, 'Sky Support'],
    [ 1, 'Falcon Support'],
    [ 1, 'Ion Support'],
];

var ALPHABET = 'abcdefghijklmnopqrstuvwxyz'
             + 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
             + '0123456789_-';

Node = function() {}
Node.prototype.processed = false;
Node.prototype.value = null;
Node.prototype.weight = 0;
Node.prototype.parent = null;
Node.prototype.left = null;
Node.prototype.right = null;

Node.prototype.traverse = function (needle, code)
{
    if (code == null) {
        code = new Array();
    }

    // leaf
    if (this.left == null && this.right == null) {
        if (this.value != needle)
            return null;
        else
            return code;
    // node
    } else {
        var val = this.left.traverse(needle, code + [0]);
        if (val != null)
            return val;
        return this.right.traverse(needle, code + [1]);
    }
}

Node.prototype.untraverse = function (code)
{
    // leaf
    if (this.left == null && this.right == null)
        return [this.value, code];

    // nodes
    if (code.shift() == 0) {
        return this.left.untraverse(code);
    } else {
        return this.right.untraverse(code);
    }
}

Node.prototype.show = function(depth, indent)
{
    if (depth == null) {
        depth = 0;
        indent = '    ';
        out = 'ROOT';
    } else {
        out = '';
    }

    // leaf
    if (this.left == null && this.right == null) {
        out += ': ' + this.value + ' (' + this.weight + ')\n';
    // nodes
    } else {
        out += '-0';
        out += this.left.show(depth + 1, indent + ' |');
        out += indent + ' 1';
        out += this.right.show(depth + 1, indent + '  ');
    }

    return out;
}

function create_nodelist(iterable)
{
    var nodes = new Array();

    for (i in iterable) {
        var node = new Node();
        node.weight = BUILDINGS[i][0];
        node.value = BUILDINGS[i][1];
        nodes.push(node);
    }

    return nodes;
}

// find the next unprocessed node with the lowest weight
// and mark it as processed
function find_best(nodes)
{
    var best = null
    var weight = -1;

    for (i in nodes) {
        if (nodes[i].processed)
            continue;

        if (weight == -1 || nodes[i].weight <= weight) {
            weight = nodes[i].weight;
            best = nodes[i];
        }
    }

    best.processed = true;
    return best;
}

function create_tree(nodes)
{
    var i = nodes.length;

    while (--i > 0) {
        var node = new Node();

        node.left = find_best(nodes);
        node.right = find_best(nodes);
        node.weight = node.left.weight + node.right.weight;

        nodes.push(node);
    }

    return nodes;
}

function bit2str(bits)
{
    var out = '';
    var cur = 0;

    for (i in bits) {
        cur |= bits[i] << (i % 6);

        if (i % 6 == 5 && i > 0) {
            out += ALPHABET.charAt(cur);
            cur = 0;
        }
    }

    // padding
    out += ALPHABET.charAt(cur);
    out += ALPHABET.charAt(bits.length % 6);

    return out;
}

function str2bit(str)
{
    var out = new Array();

    var c = 0;
    for (; c < str.length - 2; c++) {
        var val = ALPHABET.indexOf(str[c]);
        for (var i = 0; i < 6; i++) {
            out.push(val >> i & 1);
        }
    }

    // padding
    var padsize = ALPHABET.indexOf(str[c + 1]);
    for (var i = 0; i < padsize; i++) {
        out.push(ALPHABET.indexOf(str[c]) >> i & 1);
    }

    return out;
}

function get_golomb_len(prefix)
{
    return (Math.log(prefix) / Math.log(2)) >> 0;
}

function encode_levels_prefix(levels, prefix)
{
    var out = new Array();

    var n = 8;
    while (n-- > 0)
        out.push(((1 << n) & prefix) != 0 ? 1 : 0);

    // create a new array prepending the length of the levels
    var len_levels = new Array();
    len_levels.push(levels.length);
    for (l in levels)
        len_levels.push(levels[l]);

    for (l in len_levels) {
        var current = len_levels[l];

        // determine delta
        if (l > 1)
            current -= len_levels[l - 1];

        // add signedness
        if (l > 0) {
            out.push(current >= 0 ? 0 : 1);
            // abs(current)
            if (current < 0)
                current *= -1;
        }

        var q = (current / prefix) >> 0;
        while (q-- > 0)
            out.push(1);
        out.push(0);

        var i = get_golomb_len(prefix);
        while (i-- > 0)
            out.push(((1 << i) & current) != 0 ? 1 : 0);
    }

    return out;
}

function encode_levels(levels)
{
    var prefix = 1;

    var encodes = new Array();

    var best = 0;
    // XXX: Yep, this is a brute-force aproach
    // and will be optimized someday ;-)
    while ((prefix <<= 1) <= 128) {
        var current = encode_levels_prefix(levels, prefix);
        var is_best = true;
        for (i in encodes)
            if (current.length > encodes[i].length)
                is_best = false;
        if (is_best)
            best = encodes.length;
        encodes.push(current);
    }

    return encodes[best];
}

function decode_levels(bits)
{
    var out = new Array();

    var prefix = 0, n = 8;
    while (n-- > 0)
        prefix += bits.shift() != 0 ? (1 << n) : 0;

    var level_len = -1;
    var previous_level = 0;

    while (bits.length > 0 && (level_len == -1 || out.length < level_len)) {
        // determine signedness
        var sign = 1;
        if (level_len != -1)
            sign = bits.shift() == 1 ? -1 : 1;

        var q = 0;
        while (bits.shift() == 1) q++;

        var level = 0;

        var i = get_golomb_len(prefix);
        while (i-- > 0)
            level += bits.shift() != 0 ? 1 << i : 0;

        // get length of levels
        if (level_len == -1) {
            level_len = level + q * prefix;
        } else {
            previous_level += (level + q * prefix) * sign;
            out.push(previous_level);
        }
    }

    return [out, bits];
}

function encode(root, data, levels)
{
    var code = new Array();

    var levels = encode_levels(levels);
    for (i in levels)
        code.push(levels[i]);

    for (i in data) {
        var huffcode = root.traverse(data[i]);
        for (h in huffcode)
            code.push(huffcode[h]);
    }

    return bit2str(code);
}

function decode(root, data)
{
    var code = str2bit(data);

    var levels = decode_levels(code);
    code = levels[1];

    var out = new Array();
    while (code.length > 0) {
        var result = root.untraverse(code);
        out.push(result[0]);
        code = result[1];
    }

    return [out, levels[0]];
}

 /**************************\
|*  _____         _         *|
|* |_   _|__  ___| |_ ___   *|
|*   | |/ _ \/ __| __/ __|  *|
|*   | |  __/\__ \ |_\__ \  *|
|*   |_|\___||___/\__|___/  *|
|*                          *|
 \**************************/

// wrap phantom
function trace(msg)
{
    if (typeof(phantom) != 'undefined')
        console.log(msg);
}

// this is to make nicer base tests
var SYMBOL_MAPPING = {
    ' ': 'No Building',
    '.': 'Tiberium',
    ',': 'Crystal',
    'Y': 'Construction Yard',
    ':': 'Harvester Tiberium',
    ';': 'Harvester Crystal',
    'P': 'Power Plant',
    'R': 'Refinery',
    '%': 'Silo',
    '*': 'Accumulator',
    'C': 'Command Center',
    'F': 'Factory',
    'B': 'Barracks',
    'A': 'Air Field',
    'D': 'Defense HQ',
    'd': 'Defense Facility',
    's': 'Sky Support',
    'f': 'Falcon Support',
    'i': 'Ion Support',
};

var TEST_BASES = [
    [ 'A D Y C F'
    + '  :%;P   '
    + 'i  P;;*:d'
    + '  :*PP%  '
    + 'B;; R: ; '
    + '     %   '
    + '    : :  '
    + '         '
    , [ 15,12,12,14,14,12,18,14,15,14,17,20,18,19,13
      , 13,12,20,19,17,20,14,15,12,18,20,15,12,17,18
      ]
    ], // e4XZWWXXiXXZjQijZYYOilQWXZiPWZikrLmFUeRG4hBxeRIUADhMwKgT8d-16-hd
    [ '  DPPY d '
    + '  ;;*;P; '
    + '  P%P*%  '
    + '  :*: :  '
    + '  %      '
    + ' ::    : '
    + '     ;%: '
    + '         '
    , [ 19,19,14,14,12,18,17,17,15,18,14,20,13,20,14
      , 12,19,19,15,17,14,17,19,13,16,20,12
      ]
    ], // eyllZXXijkYlXPWQWXilZlYjkZkOWmP78rViwXL7GBHxTA9H-Q_6Va6-dc
    [ '  d Y D  '
    + '   ;  :  '
    + '  %RPs%  '
    + ' ::: ; : '
    + '     PR: '
    + '   %*P%  '
    + '  ;P;; ; '
    + '         '
    , [ 20,14,12,16,15,14,20,12,13,15,12,18,16,19,15
      , 17,12,13,13,15,16,17,16,19,18,14,14
      ]
    ], // eyRWXiWZPWWYZijiZlYWYYlikilXXnA_KFz9bJJaxvTu-DJ_G1HxCrk-pe
];

function assert_equal(a, b)
{
    if ("x" + a != "x" + b)
        throw "Test failed: " + a + " != " + b;
}

function test_bitencode()
{
    var try_with = function(s) {
        var encoded = bit2str(s);
        trace("Encoded base64: " + encoded);
        assert_equal(str2bit(encoded), s);
    };

    try_with([1,0,1,0,1,0,1,0,1,0,1,0,1,0]);
    try_with([1,1,0,1,0,1]);
    try_with([1,1,0,1,0,1,0,0,0,0,0,0]);
    try_with([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]);
    try_with([]);
}

function test_encode_levels()
{
    var try_with = function(s) {
        var encoded = encode_levels(s);
        trace("Encoded levels: " + encoded);
        var decoded = decode_levels(encoded);
        assert_equal(decoded[0], s);
        assert_equal(decoded[1], []);
    };

    try_with([16,16,14,14,11,15,16,12,12,13,16,11,13,14,15]);
    try_with([12,16,11,13,15,12,15,13,14,15,13,14]);
    try_with([200,1,27,59,2,3,4,5,6,7,8,9,0]);
    try_with([]);
}

function test_encode_sample()
{
    var tree = create_tree(create_nodelist(BUILDINGS));
    var root = tree[tree.length - 1];

    for (b in TEST_BASES) {
        // create list of map items
        var items = new Array();
        var base = TEST_BASES[b][0];

        for (c in base)
            items.push(SYMBOL_MAPPING[base[c]]);

        var levels = TEST_BASES[b][1];

        var encoded = encode(root, items, levels);
        trace("Encoded base: " + encoded);
        var decoded = decode(root, encoded);
        assert_equal(decoded[0], items);
        assert_equal(decoded[1], levels);
    }
}

// don't forget to remove these someday ;-)
test_bitencode();
test_encode_levels();
test_encode_sample();

if (typeof(phantom) != 'undefined')
    phantom.exit();

Oh, sorry, i missed that 😞
And no, my weights are by no means the best ones. I based them on the assumption, that the most frequent "building" in most bases would be no building.
So it would be probably the best to do some statistics and just count the buildings on every base people submit to the base builder and get out average values.

Ok.

So how do you suggest to put the strings for the basebuilder, the leveling, the defense builder, the faction (nod/gdi) and the version information together?

okay, for that i'd need to know how your data structure looks like (classes for buildings, defense units, etc).
encoding the faction is quite easy, as it's just 2 bits (00 -> gdi, 01 -> nod, 10 -> forgotten, 11 -> whatnot).
the leveling is already implemented in the code above but not yet in use by the encode/decode functions, i'll work on it now.
if it comes to the defense builder, another tree will be needed, which of course should have good weighting for real-world defenses.
so i'm going to implement this and add a version flag, so we could gather some data with the current version, get the best tree weighting off real world data and do a version 2 of the balanced tree.

sounds that good to you?