bf_task.js

// https://www.codewars.com/kata/5b84e44d6aa40d1ca5000124/train/bf
const bf = strCode => {
  let orders = ',.[]<>+-'.split('');
  let regex = {
    clean: new RegExp('[^' + escapeRegExp(orders.join('')) + ']', 'g'),
    value: /[\+\-]+/g,
    pointer: /[\<\>]+/g,
    instruction: /[0-9]*./g,
    zero: /\[(\-|\+)\]/g
  };
  
  let config = {
    memorySize: 30000,
    bits: 8, // 8, 16, 32
    maxInstructions: 0 // limit execution to number of instructions, omit if 0
  };
  
  function getInstruction(count, orderLess, orderMore) {
    return ({
      '1': (count > 1) ? count + orderMore : orderMore,
      '0': '',
      '-1': (count < -1) ? (-count) + orderLess : orderLess
    })[Math.sign(count)];
  }
  
  function escapeRegExp(str) {
    return str.replace(/[\-\[\]\/\{\}\(\)\*\+\?\.\\\^\$\|]/g, "\\$&");
  }
  
  function cloneObj(obj) {
    return Object.keys(obj).reduce((res, key) => (res[key] = obj[key], res), {});
  }
  
  function extendObj(obj, ext) {
    return Object.keys(ext || {}).reduce((res, key) => (res[key] = ext[key], res), obj);
  }
  
  const compile = (bfSource, userConfig) => {
    let actualConfig = extendObj(cloneObj(config), userConfig);
    let cleanedSource = (bfSource+'').replace(regex.clean, '');
    let optimized = cleanedSource
      // optimze cell manipulating instructions
      // for example: '+++--' => '+'
      //              '+++++' => '5+'
      .replace(regex.value, (m) => {
        let map = { '+': 1, '-': -1 };
        let n = m.split('').reduce((acc, b) => acc + map[b], 0);
        return getInstruction(n, '-', '+');
      })
      // optimze pointer manipulating instructions
      // for example: '>>><<' => '>'
      //              '>>>>>' => '5>'
      .replace(regex.pointer, (m) => {
        let map = { '>': 1, '<': -1 };
        let n = m.split('').reduce((acc, b) => acc + map[b], 0);
        return getInstruction(n, '<', '>');
      })
      // add (z)ero instruction => it makes reseting cell much faster
      .replace(regex.zero, 'z');
    
    let ordersMap = { // m,p,o,i,l
      ',': () => 'm[p]=i();',
      '.': () => 'o(m[p]);',
      '[': () => 'while(m[p]){',
      ']': () => '}',
      '<': (count) => 'p-='+count+';while(p<0)p+=l;',
      '>': (count) => 'p+='+count+';while(p>=l)p-=l;',
      '+': (count) => 'm[p]+='+count+';',
      '-': (count) => 'm[p]-='+count+';',
      // optimizations:
      'z': () => 'm[p]=0;' // [-] => quick reset memory cell
    };
  
    let createOrder = (order, count) => {
      // if there is a instruction limit, add prefix check-instruction to every instruction
      let prefix = actualConfig.maxInstructions > 0 ? 'if(!--c)return;' : '';
      return [prefix, ordersMap[order](count)].join('');
    };
  
    let definitions = {
      // count
      c: (config) => config.maxInstructions > 0 ? 'let c='+config.maxInstructions+';' : '',
      // length
      l: (config) => ['let l=', config.memorySize, ';'].join(''),
      // memory
      m: (config) => {
        const constr = {'8': 'Uint8Array', '16': 'Uint16Array', '32': 'Uint32Array'};
        return ['let m=new ', constr[config.bits] || constr[8], '(l);'].join('');
      },
      // pointer
      p: () => 'let p=0;',
      // out
      o: () => 'let o=output||(()=>0);',
      // in
      i: () => 'let i=input||(()=>0);'
    };
  
    // create variables definitions
    let code = Object.keys(definitions).map(key => definitions[key](actualConfig));
  
    // create rest code
    (optimized.match(regex.instruction) || []).map((instruction) => {
      let count = +instruction.slice(0, -1) || 1;
      let order = instruction.slice(-1);
      code.push(createOrder(order, count));
    });
  
    let compiled = new Function(['input', 'output'], code.join(''));
    
    return {
      run: (input, output) => {
        let inp, out;
        let res = [];
        if (typeof input === 'string') {
          input = input.split('');
          inp = () => {
            let ch = input.shift();
            return ch ? ch.charCodeAt(0) : 0;
          };
        } else if (typeof input === 'function') {
          inp = input;
        }
        if (typeof output !== 'function') {
          output = () => 0;
        }
        out = (num) => {
          let ch = String.fromCharCode(num);
          output(num, ch);
          res.push(ch);
        };
        compiled(inp, out);
        return res.join('');
      },
      toString: () => compiled.toString()
    };
  };

  return compile(strCode).run();
};

const constr1 = (n, dec = false) => {
  return [
    dec ? '-'.repeat(256 - n) : '+'.repeat(n),
    '.'
  ].join('');
};

const constr2 = (n, a, b) => {
  const diff = n - a * b;
  const prog = [];
  prog.push('+'.repeat(a));
  prog.push(`[->${'+'.repeat(b)}<]`);
  prog.push('>');
  prog.push((diff > 0 ? '+' : '-').repeat(Math.abs(diff)));
  prog.push('.');
  return prog.join('');
};

const solve = n => {
  const sq = n ** 0.5 | 0;
  return [
    constr2(n, sq, Math.ceil(n / sq)),
    constr2(n, sq, Math.floor(n / sq)),
    constr1(n),
    constr1(n, true),
  ].sort((a, b) => a.length - b.length)[0];
};

let sum = 0;
for (let i = 0; i < 256; ++i) {
  const prog = solve(i);
  sum += prog.length;
  console.log(i, solve(i));
}
sum; // 6996