Skip to content

Instantly share code, notes, and snippets.

@ob-ivan
Last active December 10, 2015 00:50
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ob-ivan/fcf7b53a2add0f2cfe3d to your computer and use it in GitHub Desktop.
Save ob-ivan/fcf7b53a2add0f2cfe3d to your computer and use it in GitHub Desktop.
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
</head>
<body>
<script type="text/javascript" src="oxcow.js"></script>
<script>
var game = new Game();
game.init();
</script>
</body>
</html>
var Result = function (ox, cow) {
this.ox = ox;
this.cow = cow;
};
var Assertion = function (word, ox, cow) {
this.word = word;
this.ox = ox;
this.cow = cow;
};
var Range = (function () {
var Range = function (from, to) {
this.from = from;
this.to = to;
};
Range.prototype.getLength = function () {
return this.to - this.from + 1;
};
return Range;
})();
var ElementRemover = (function () {
var ElementRemover = function () {
this.ranges = [];
};
ElementRemover.prototype._initRange = function (position) {
var newRange = new Range(position, position);
this.ranges.push(newRange);
};
ElementRemover.prototype.mark = function (position) {
if (! this.ranges.length) {
this._initRange(position);
return;
}
var lastMarkedPosition = this.ranges[this.ranges.length - 1].to;
if (position === lastMarkedPosition + 1) {
++this.ranges[this.ranges.length - 1].to;
} else if (position > lastMarkedPosition + 1) {
this._initRange(position);
} else {
throw new Error('Please call ElementRemover::mark only with increasing values of position argument');
}
};
/**
* Modify the array to remove elements at marked ranges.
*
* Return number of elements removed.
*
* @param {array} array
* @return {integer}
**/
ElementRemover.prototype.remove = function (array) {
var removed = 0;
for (var i = 0; i < this.ranges.length; ++i) {
var rangeLength = this.ranges[i].getLength();
array.splice(this.ranges[i].from - removed, rangeLength);
removed += rangeLength;
}
return removed;
};
return ElementRemover;
})();
var Utils = {
getRandomElement : function (array) {
return array[Math.floor(Math.random() * array.length)];
}
};
var CompleteWordSource = (function () {
var CompleteWordSource = function (alphabet, length) {
this._alphabet = alphabet;
this._length = length;
};
CompleteWordSource.prototype.getRandomWord = function () {
var chars = [];
for (var i = 0; i < this._length; ++i) {
chars.push(Utils.getRandomElement(this._alphabet));
}
return chars.join('');
};
CompleteWordSource.prototype.hasWordAt = function (position) {
return position <= Math.pow(this._alphabet.length, this._length);
};
CompleteWordSource.prototype.getWordAt = function (position) {
var remainder = position;
var chars = [];
for (var i = 0; i < this._length; ++i) {
var mod = remainder % this._alphabet.length;
remainder = Math.floor(remainder / this._alphabet.length);
chars.push(this._alphabet[mod]);
}
chars.reverse();
return chars.join('');
};
return CompleteWordSource;
})();
var Solver = (function () {
var Solver = function (wordSource, batchSize, calculationTimeoutMs) {
this.wordSource = wordSource;
this.batchSize = batchSize;
this.calculationTimeoutMs = calculationTimeoutMs;
this.assertions = [];
this.words = [];
this.progress = 0;
this.completeCount = 0;
this.spliceFrom = null;
this.spliceTo = null;
this.state = this.STATE_NEW;
};
Solver.prototype.STATE_NEW = 0;
Solver.prototype.STATE_INIT = 1;
Solver.prototype.STATE_READY = 2;
Solver.prototype.STATE_WORKING = 3;
Solver.prototype._deleteChar = function (word, position) {
var chars = word.split('');
chars.splice(position, 1);
return chars.join('');
};
Solver.prototype.compare = function (word, candidate) {
var oxCount = 0;
var cowCount = 0;
var wordOxless = word;
var candidateOxless = candidate;
for (var i = 0; i < word.length && i < candidate.length; ++i) {
if (word[i] === candidate[i]) {
wordOxless = this._deleteChar(wordOxless, i - oxCount);
candidateOxless = this._deleteChar(candidateOxless, i - oxCount);
++oxCount;
}
}
var wordCowless = wordOxless;
for (var i = 0; i < candidateOxless.length; ++i) {
var p = wordCowless.indexOf(candidateOxless[i]);
if (p >= 0) {
++cowCount;
wordCowless = this._deleteChar(wordCowless, p);
}
}
return new Result(oxCount, cowCount);
};
Solver.prototype.getRandomWord = function () {
return this.wordSource.getRandomWord();
};
Solver.prototype.getRandomAttempt = function () {
if (this.state === this.STATE_NEW || this.state === this.STATE_INIT) {
return this.getRandomWord();
}
return Utils.getRandomElement(this.words);
};
Solver.prototype._getDynamicBatchSize = function () {
return this.batchSize;
};
Solver.prototype._init = function () {
console.log(
'init: this.progress', this.progress,
'this.words.length', this.words.length
);
for (var end = this.progress + 10 * this._getDynamicBatchSize();
this.progress < end;
++this.progress
) {
if (! this.wordSource.hasWordAt(this.progress)) {
this.state = this.STATE_READY;
this._startCalculation();
return;
}
var word = this.wordSource.getWordAt(this.progress);
var ok = true;
for (var i = 0; i < this.assertions.length; ++i) {
var assertion = this.assertions[i];
var compareResult = this.compare(assertion.word, word);
if (compareResult.ox !== assertion.ox ||
compareResult.cow !== assertion.cow
) {
ok = false;
break;
}
}
if (ok) {
this.words.push(word);
}
}
window.setTimeout(this._init.bind(this), this.calculationTimeoutMs);
};
Solver.prototype._calculate = function () {
console.log(
'calculate: this.progress', this.progress,
'this.words.length', this.words.length
);
var remover = new ElementRemover();
for (var end = this.progress + this._getDynamicBatchSize();
this.progress < end;
++this.progress
) {
for (var i = 0; i < this.assertions.length; ++i) {
if (this.words.length <= this.progress) {
this.progress -= remover.remove(this.words);
this.completeCount = this.startCount;
this.state = this.STATE_READY;
if (this.completeCount < this.assertions.length) {
this._startCalculation();
}
return;
}
var assertion = this.assertions[i];
var word = this.words[this.progress];
var compareResult = this.compare(assertion.word, word);
if (compareResult.ox !== assertion.ox ||
compareResult.cow !== assertion.cow
) {
remover.mark(this.progress);
break;
}
}
}
this.progress -= remover.remove(this.words);
window.setTimeout(this._calculate.bind(this), this.calculationTimeoutMs);
};
Solver.prototype._startCalculation = function () {
if (this.state != this.STATE_READY) {
return;
}
this.state = this.STATE_WORKING;
this.startCount = this.assertions.length;
this.progress = 0;
this._calculate();
};
Solver.prototype.assert = function (word, oxCount, cowCount) {
var assertion = new Assertion(word, oxCount, cowCount);
this.assertions.push(assertion);
if (this.state === this.STATE_NEW) {
this.state = this.STATE_INIT;
this._init();
}
if (this.state === this.STATE_READY) {
this._startCalculation();
}
return this;
};
Solver.prototype.isUnresolvable = function () {
return this.state !== this.STATE_INIT && this.words.length === 0;
};
Solver.prototype.isSolutionReady = function () {
return this.state !== this.STATE_INIT && this.words.length === 1;
};
Solver.prototype.getSolution = function () {
if (this.isSolutionReady()) {
return this.words[0];
}
};
return Solver;
})();
var Game = (function () {
var Game = function () {
};
Game.prototype._initTable = function (iGoFirst) {
var table = document.createElement('div');
var p = document.createElement('p');
p.appendChild(document.createTextNode('The alphabet is: ' + this._alphabet));
table.appendChild(p);
var p = document.createElement('p');
p.appendChild(document.createTextNode('Word length is: ' + this._length));
table.appendChild(p);
var p = document.createElement('p');
p.appendChild(document.createTextNode((iGoFirst ? 'I' : 'You') + ' go first.'));
table.appendChild(p);
table.className = 'table';
document.body.appendChild(table);
this.table = table;
};
Game.prototype._finish = function (message) {
var p = document.createElement('p');
p.appendChild(document.createTextNode(message));
document.body.appendChild(p);
};
Game.prototype._turn = function () {
var div = document.createElement('div');
div.className = 'yourAttempt';
this.table.appendChild(div);
var attempt = document.createElement('input');
div.appendChild(attempt);
var submit = document.createElement('input');
submit.type = 'button';
submit.value = 'submit';
div.appendChild(submit);
submit.addEventListener('click', function () {
div.removeChild(submit);
var assertion = this._solver.compare(this._word, attempt.value);
if (assertion.ox === this._length) {
this._finish('You win!');
return;
}
var span = document.createElement('span');
span.className = 'ox';
span.appendChild(document.createTextNode(assertion.ox));
div.appendChild(span);
var span = document.createElement('span');
span.className = 'cow';
span.appendChild(document.createTextNode(assertion.cow));
div.appendChild(span);
this._attempt();
}.bind(this));
};
Game.prototype._attempt = function () {
var candidate = Math.random() < 0.99
? this._solver.getRandomAttempt()
: this._solver.getRandomWord();
var div = document.createElement('div');
div.className = 'myAttempt';
this.table.appendChild(div);
var span = document.createElement('span');
span.appendChild(document.createTextNode(candidate));
div.appendChild(span);
var ox = document.createElement('input');
div.appendChild(ox);
var cow = document.createElement('input');
div.appendChild(cow);
var submit = document.createElement('input');
submit.type = 'button';
submit.value = 'submit';
div.appendChild(submit);
submit.addEventListener('click', function () {
div.removeChild(submit);
this._solver.assert(
candidate, parseInt(ox.value) || 0, parseInt(cow.value) || 0
);
ox.disabled = true;
cow.disabled = true;
if (this._solver.isUnresolvable()) {
this._finish('I surrender!');
} else if (this._solver.isSolutionReady()) {
this._finish('The answer is ' + this._solver.getSolution());
} else {
this._turn();
}
}.bind(this));
};
Game.prototype._createSelect = function (id, options) {
var select = document.createElement('select');
select.id = id;
for (var i = 0, l = options.length; i < l; ++i) {
var option = document.createElement('option');
option.value = options[i];
option.innerHTML = options[i];
select.appendChild(option)
}
return select;
};
Game.prototype._makeFirstMove = function () {
var iGoFirst = Math.random() < 0.5;
this._initTable(iGoFirst);
if (iGoFirst) {
this._attempt();
} else {
this._turn();
}
};
Game.prototype._initVariables = function (alphabet, length) {
this._alphabet = alphabet;
this._length = parseInt(length, 10);
var wordSource = new CompleteWordSource(this._alphabet, this._length);
this._solver = new Solver(wordSource, 1000, 1000);
this._word = wordSource.getRandomWord();
};
Game.prototype._getSelectedValue = function (select) {
return select.options[select.selectedIndex].value;
};
Game.prototype._start = function (alphabetSelect, lengthSelect, startButton) {
startButton.disabled = true;
this._initVariables(
this._getSelectedValue(alphabetSelect),
this._getSelectedValue(lengthSelect)
);
this._makeFirstMove();
};
Game.prototype._initControls = function () {
var alphabetSelect = this._createSelect(
'alphabet',
[
'RYGBOV',
'RYGBOVSC',
'0123456789',
'abcdefghijklmnopqrstuvwxyz',
'абвгдеёжзийклмнопрстуфхцчшщъыьэюя',
]
);
document.body.appendChild(alphabetSelect);
var lengthSelect = this._createSelect('length', [4, 5]);
document.body.appendChild(lengthSelect);
var startButton = document.createElement('button');
startButton.innerHTML = 'start';
startButton.addEventListener('click', this._start.bind(this, alphabetSelect, lengthSelect, startButton));
document.body.appendChild(startButton);
};
Game.prototype.init = function () {
this._initControls();
};
return Game;
})();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment