Helpful things for codingame.com (in js)

codingame.md

useful stuff for working in js for codingame.com

priority-queue.js

const PriorityQueue = (function() {
const top = 0;
const parent = i => ((i + 1) >>> 1) - 1;
const left = i => (i << 1) + 1;
const right = i => (i + 1) << 1;
class PriorityQueue {
  constructor(comparator = (a, b) => a > b) {
    this._heap = [];
    this._comparator = comparator;
  }
  size() {
    return this._heap.length;
  }
  isEmpty() {
    return this.size() == 0;
  }
  peek() {
    return this._heap[top];
  }
  push(...values) {
    values.forEach(value => {
      this._heap.push(value);
      this._siftUp();
    });
    return this.size();
  }
  get(detector) {
      for (const val of this._heap) {
          if (detector(val)) {
              return val;
          }
      }
  }
  pop() {
    const poppedValue = this.peek();
    const bottom = this.size() - 1;
    if (bottom > top) {
      this._swap(top, bottom);
    }
    this._heap.pop();
    this._siftDown();
    return poppedValue;
  }
  replace(value) {
    const replacedValue = this.peek();
    this._heap[top] = value;
    this._siftDown();
    return replacedValue;
  }
  updateKey(element) {
    // key can only get bigger
    const index = this._heap.indexOf(element);
    if (index < 0) {
        console.error("ERROR: UpdateKey not-found element!");
        return;
    }
    this._siftUp(index);
  }
  _greater(i, j) {
    return this._comparator(this._heap[i], this._heap[j]);
  }
  _swap(i, j) {
    [this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]];
  }
  _siftUp(node = this.size() - 1) {
    while (node > top && this._greater(node, parent(node))) {
      this._swap(node, parent(node));
      node = parent(node);
    }
  }
  _siftDown() {
    let node = top;
    while (
      (left(node) < this.size() && this._greater(left(node), node)) ||
      (right(node) < this.size() && this._greater(right(node), node))
    ) {
      let maxChild = (right(node) < this.size() && this._greater(right(node), left(node))) ? right(node) : left(node);
      this._swap(node, maxChild);
      node = maxChild;
    }
  }
}
return PriorityQueue;
})();

profiler.js

const PROFILER_FLAT_MODE = true;
const PROFILER_LOG_TOTAL = true;
const PROFILER_DISABLED = true;
function barString(progress, maxLength) {
    return "|" + '#'.repeat(progress * maxLength) + '-'.repeat((1 - progress) * maxLength) + '|';
}
class Profiler {
    constructor() {
        this.clear();
        this.allData = undefined;
        this.turnCount = 0;
    }
    clear() {
        this.firstEnterTime = Date.now();
        this.topLevelBlock = this._newBlock("Everything");
        this.currentBlock = this.topLevelBlock;
    }
    enter(name) {
        if (PROFILER_DISABLED) return;
        this.currentBlock = this._newBlock(name, this.currentBlock);
    }
    next(name) {
        if (PROFILER_DISABLED) return;
        this.leave();
        this.enter(name);
    }
    leave() {
        if (PROFILER_DISABLED) return;
        if (this.currentBlock === this.topLevelBlock) return;
        
        this.currentBlock.leaveTime = Date.now();
        this.currentBlock = this.currentBlock.parent;
    }
    _newBlock(name, parent) {
        const newBlock = {
            name, parent,
            children: [],
            enterTime: Date.now(),
            leaveTime: undefined
        };
        if (parent) {
            parent.children.push(newBlock);
        }
        return newBlock;
    }
    _saveTotalResults() {
        this.turnCount++;
        if (!this.allData) {
            this.allData = this.topLevelBlock;
        } else {
            this._mergeBlock(this.allData, this.topLevelBlock);
        }
    }
    getTimeSinceStart() {
        return Date.now() - this.firstEnterTime;
    }
    getSummary() {
        this.topLevelBlock.enterTime = this.firstEnterTime;
        this.topLevelBlock.leaveTime = Date.now();
        this._analyze(this.topLevelBlock);
        this._collapse(this.topLevelBlock);
        this._saveTotalResults();
        const blockToPrint = PROFILER_LOG_TOTAL ? this.allData : this.topLevelBlock;
        if (!PROFILER_LOG_TOTAL) this.turnCount = 1;
        if (blockToPrint.total < 5) {
            return "";
        }
        return "Profiling summary: (" + this.topLevelBlock.total + "ms this turn) \n" + this._getSummaryFor(blockToPrint, blockToPrint, "");
    }
    _getSummaryFor(block, topLevelBlock, indent) {
        let out = indent + block.name + ": " + (block.total / this.turnCount).toFixed(1) + "ms";
        if (block.parent) {
            const relative = block.total / topLevelBlock.total;
            out += ", " + (relative*100).toFixed(1) + "%:   " + barString(relative, 30);
        }
        out += "\n";
        for (const child of block.children) {
            out += this._getSummaryFor(child, topLevelBlock, indent + "  ");
        }
        return out;
    }
    _analyze(block) {
        block.total = block.leaveTime - block.enterTime;
        for (const child of block.children) {
            this._analyze(child);
        }
    }
    _collapse(block) {
        for (const c of block.children) {
            this._collapse(c);
        }
        if (PROFILER_FLAT_MODE) {
            for (const c of [...block.children]) {
                block.children.push(...c.children);
                c.children = [];
            }
        }
        for (let i = 0; i < block.children.length; i++) {
            for (let o = 0; o < i; o++) {
                if (block.children[i].name === block.children[o].name) {
                    block.children[o].total += block.children[i].total;
                    block.children[o].relative += block.children[i].relative;
                    block.children.splice(i, 1);
                    i--;
                }
            }
        }
    }
    _mergeBlock(existing, toBeMerged) {
        existing.total += toBeMerged.total;
        existing.relative += toBeMerged.relative;
        for (const c of toBeMerged.children) {
            let handled = false;
            for (const ec of existing.children) {
                if (ec.name === c.name) {
                    this._mergeBlock(ec, c);
                    handled = true;
                    break;
                }
            }
            if (!handled) {
                existing.children.push(c);
            }
        }
    }
}
let profiler = new Profiler();

function fn() {
    profiler.enter("fn");
    const result = 42; // work
    profiler.leave();
    return result;
}
while(true) {
    profiler.clear();
    profiler.enter("Step 1");
    // ...
    profiler.next("Step 2");
    // ...
    profiler.leave();
    console.error(profiler.getSummary());
}

seedable-random.js

const mask = 0xffffffff;
const {seed_random, random} = (function() {
    var m_w = 123456789;
    var m_z = 987654321;
    function seed_random(i) {
        console.error("Random map seed: " + i);
        m_w = (123456789 + i) & mask;
        m_z = (987654321 - i) & mask;
    }
    function random() {
        m_z = (36969 * (m_z & 65535) + (m_z >> 16)) & mask;
        m_w = (18000 * (m_w & 65535) + (m_w >> 16)) & mask;
        var result = ((m_z << 16) + (m_w & 65535)) >>> 0;
        result /= 4294967296;
        return result;
    }
    return {seed_random, random};
})();
Array.prototype.getRandom = function() {
    return this[floor(random() * this.length, this.length - 1)];
};

vector-math-utils.js

const {pow, abs, sqrt, min, max, round, hypot, PI, sin, cos, atan2, floor} = Math;
Set.prototype.eq = function(other) {
    if (this.size !== other.size) return false;
    for (const elem of this) if (!other.has(elem)) return false;
    return true;
};
Set.prototype.intersect = function(other) {
    return new Set([...this].filter(e => other.has(e)));
};
Array.prototype.getMin = function(attrib) {
    return (this.length && this.reduce(function(prev, curr) {
        return attrib(prev) < attrib(curr) ? prev : curr;
    })) || null;
};
Array.prototype.getMax = function(attrib) {
    return (this.length && this.reduce(function(prev, curr) {
        return attrib(prev) > attrib(curr) ? prev : curr;
    })) || null;
};
Array.prototype.last = function() {
    return this[this.length - 1];
};
Array.prototype.sum = function() {
    let result = 0;
    for (const v of this) {
        result += v;
    }
    return result;
};
// add: T, T -> T
// scale: T, int -> T
Array.prototype.average = function(add, scale) {
    if (this.length === 0) {
        return undefined;
    } else {
        return scale(this.reduce(add), this.length)
    }
};
function floatEq(a, b) {
    return abs(a - b) < 0.001;
}
Object.prototype.vEq = function(other) {
    return floatEq(this.x, other.x) && floatEq(this.y, other.y);
};
Object.prototype.vAdd = function(other) {
    return {x: this.x + other.x, y: this.y + other.y};
};
Object.prototype.vSub = function(other) {
    return {x: this.x - other.x, y: this.y - other.y};
};
Object.prototype.vRound = function() {
    return {x: round(this.x), y: round(this.y)};
};
Object.prototype.vScale = function(scale) {
    return {x: this.x * scale, y: this.y * scale};
};
Object.prototype.vLength = function() {
    return hypot(this.x, this.y);
};
Object.prototype.vDist = function(other) {
    return hypot(this.x - other.x, this.y - other.y);
};
Object.prototype.vSqDist = function(other) {
    const x = this.x - other.x;
    const y = this.y - other.y;
    return x * x + y * y;
};
Object.prototype.vManhattanDist = function(other) {
    return abs(this.x - other.x) + abs(this.y - other.y);
};
Object.prototype.vNormalize = function() {
    return this.vScale(1 / this.vLength());
};
Object.prototype.vInvert = function() {
    return this.vScale(-1);
};
Object.prototype.vPrint = function() {
    return round(this.x) + " " + round(this.y);
};
Object.prototype.vPrintDir = function() {
    if (this.x === 0 && this.y === -1) return 'UP';
    if (this.x === 0 && this.y === 1) return 'DOWN';
    if (this.x === 1 && this.y === 0) return 'RIGHT';
    if (this.x === -1 && this.y === 0) return 'LEFT';
    console.error("Cannot parse " + JSON.stringify(this) + " to a direction");
    return 'NOWHERE';
};
String.prototype.vParse = function() {
    if (this == 'UP') return {x: 0, y: -1};
    if (this == 'DOWN') return {x: 0, y: 1};
    if (this == 'LEFT') return {x: 1, y: 0};
    if (this == 'RIGHT') return {x: -1, y: 0};
    const data = this.split(' ');
    if (data.length !== 2) {
        console.error("Failed to parse String to vector!");
        console.trace();
    }
    return {x: parseInt(data[0]), y: parseInt(data[1])};
};
const DIRECTION_VECTORS = [
    {x: 1, y: 0},
    {x: -1, y: 0},
    {x: 0, y: 1},
    {x: 0, y: -1}
];
Object.prototype.v4Neighbours = function() {
    return DIRECTION_VECTORS.map(p => p.vAdd(this));
};
Array.prototype.vMoveToStart = function(start) {
    // first, remove it
    for (let i = 0; i < this.length; i++) {
        if (this[i].vEq(start)) {
            this.splice(i, 1);
            break;
        }
    }
    // add it back at the start
    this.unshift(start);
}
Object.prototype.vLeft = function() {
    return this.vAdd({x: -1, y: 0});
};
Object.prototype.vRight = function() {
    return this.vAdd({x: 1, y: 0});
};
Object.prototype.vUp = function() {
    return this.vAdd({x: 0, y: -1});
};
Object.prototype.vDown = function() {
    return this.vAdd({x: 0, y: 1});
};