random.js

/**
 * Parses a message and replaces all [a,b,c] structures with a random
 * selection.
 *
 * Supports nested structures and escaping those special characters.
 *
 * The general approach is to make a single pass through the whole message
 * character by character, keeping a stack of lists representing all the choices
 * at the current index. The outer stack tracks the current nesting level while
 * the inner list tracks the choices at the given nesting level.
 *
 * There are two approaches to dealing with the lowest nesting level (zero):
 *  - A special case understood at every operation (operation = processing a special char)
 *  - Treat it just like any other nesting level, except it will only ever have one choice
 *
 * We chose the second approach.
 */
function parse(message) {
  // These characters can be escaped - attempting to escape any other character (eg \a)
  // will simply result in the literal string '\\a'. This behaviour may or may not be
  // wanted and can be easily changed to silently "escape" any character.
  var specialChars = [
    '\\',
    '[',
    ',',
    ']'
  ];

  // Current character index
  var ptr = 0;

  /** 
   * Each nesting level contains a list of the current choices as well as a
   * single boolean indicating whether the latest choice is 'complete'.
   *
   * This is important when you have something like '[pre[a,b],c]' and the string 'pre'
   * needs to be concatenated with the result of '[a,b]' instead of being treated
   * as a seperate choice.
   */
  var stack = [{
    'incomplete': false,
    'choices': []
  }];

  // Temporary 'register' of sorts for the current string until a control character is reached
  var curString = '';

  // Whether we've hit an escaping backslash and the current character should be ignored
  var escaped = false;

  while (ptr < message.length) {
    if (escaped) {
      if (specialChars.indexOf(message[ptr]) !== -1) {
        curString += message[ptr];
      } else {
        curString += '\\' + message[ptr];
      }

      escaped = false;
      ptr++;
      continue;
    }

    if (message[ptr] === '\\') {
      escaped = true;
    } else if (message[ptr] === '[') {
      // Store the current partial string as an incomplete choice
      addToStack(stack, curString);
      stack[0].incomplete = true;

      // New nesting level
      stack.unshift({
        'incomplete': false,
        'choices': []
      });

      curString = '';
    } else if (message[ptr] === ',') {
      // Store the current string as a complete choice
      addToStack(stack, curString);
      stack[0].incomplete = false;

      curString = '';
    } else if (message[ptr] === ']') {
      if (stack.length <= 1) {
        // Ignore any ] that don't have a matching [
        // Lowest nesting level is a special case that doesn't truly have a [
        curString += message[ptr];
      } else {
        // Store the current string as a complete choice
        addToStack(stack, curString);
        stack[0].incomplete = false;

        // After picking a random choice from the current completed nesting level,
        // remove this level and add the string to the underlying nesting level
        curString = selectRand(stack[0].choices);
        stack.shift();
        addToStack(stack, curString);

        curString = '';
      }
    } else {
      curString += message[ptr];
    }
    
    ptr++;
  }

  // Commit any straggling partial string
  addToStack(stack, curString);

  /**
   * Collapse any unfinished stacks - improperly formed syntax resulted
   * in [ without closing ] so they will be reconstructed into the original string
   */
  while (stack.length > 0) {
    if (stack.length === 1) {
      // Special case for the lowest nesting level which didn't really start with a [
      curString = '';
    } else {
      curString = '[';
    }

    // Gotta reverse because we stored the list in reverse
    stack[0].choices.reverse();
    curString += stack[0].choices.join(',');
    stack.shift();

    addToStack(stack, curString);
  }

  return curString;
}

/**
 * Pick a random item from an array.
 */
function selectRand(arr) {
  var index = Math.floor(Math.random() * arr.length);
  return arr[index];
}

/**
 * Adds the current partially built string to the list of choices
 * at the current nesting level.
 *
 * Correctly concatenates to the last choice or appends a new choice
 * depending on the 'incomplete' flag.
 */
function addToStack(stack, str) {
  if (stack.length === 0) {
    return;
  }

  if (stack[0].incomplete) {
    stack[0].choices[0] += str;
  } else {
    stack[0].choices.unshift(str);
  }
}

function runTests() {
  var tests = [{
    'input': '',
    'output': ['']
  }, {
    'input': 'hello',
    'output': ['hello']
  }, {
    'input': '[hello',
    'output': ['[hello'],
  }, {
    'input': 'hello]',
    'output': ['hello]'],
  }, {
    'input': 'a [ hello',
    'output': ['a [ hello']
  }, {
    'input': 'hello ] a',
    'output': ['hello ] a']
  }, {
    'input': '[hello]',
    'output': ['hello'],
  }, {
    'input': '[a,b,c]',
    'output': ['a', 'b', 'c']
  }, {
    'input': '[a,[1,2,3],c]',
    'output': ['a', '1', '2', '3', 'c']
  }, {
    'input': '[a,b][c,d]',
    'output': ['ac', 'ad', 'bc', 'bd']
  }, {
    'input': '[[a,b],[1,2]]',
    'output': ['a', 'b', '1', '2']
  }, {
    'input': 'pre[a,b,c]post',
    'output': ['preapost', 'prebpost', 'precpost']
  }, {
    'input': 'a[hi[1,2]ho,ha]b',
    'output': ['ahi1hob', 'ahi2hob', 'ahab']
  }, {
    'input': 'a[b[[[',
    'output': ['a[b[[[']
  }, {
    'input': '[a,b][[',
    'output': ['a[[', 'b[[']
  }, {
    'input': '[a,b]]]',
    'output': ['a]]', 'b]]']
  }, {
    'input': '\\[a,b\\]',
    'output': ['[a,b]']
  }, {
    'input': '\\,\\,,hi,ho\\,ha',
    'output': [',,,hi,ho,ha']
  }, {
    'input': 'a[1\\,\\[2[3,4\\,5],[6,7]',
    'output': ['a[1,[23,6', 'a[1,[23,7', 'a[1,[24,5,6', 'a[1,[24,5,7']
  }, {
    'input': 'a[1\\,,]b',
    'output': ['a1,b', 'ab']
  }];

  for (var i = 0; i < tests.length; i++) {
    var results = [];
    for (var r = 0; r < 1000; r++) {
      addToSet(results, parse(tests[i].input));
    }

    checkEquals(tests[i].output, results, tests[i].input);
  }
}

function addToSet(set, value) {
  if (set.indexOf(value) === -1) {
    set.push(value);
  }
}

function checkEquals(expected, results, input) {
  var unexpected = [];
  var missing = [];

  for (var i = 0; i < results.length; i++) {
    if (expected.indexOf(results[i]) === -1) {
      addToSet(unexpected, results[i]);
    }
  }
  
  for (var i = 0; i < expected.length; i++) {
    if (results.indexOf(expected[i]) === -1) {
      addToSet(missing, expected[i]);
    }
  }

  if (unexpected.length === 0 && missing.length === 0) {
    console.log('Test passed');
  } else {
    console.log('Test failed:', input);
    if (unexpected.length > 0) {
      console.log(' > unexpected:', unexpected);
    }
    if (missing.length > 0) {
      console.log(' > missing:', missing);
    }
  }
}

runTests();