Быки и коровы
Как то мне попалось ниже приведенное тестовое задание.
Мой вариант решения здесь http://learn.javascript.ru/play/4WDZG "Реализовать алгоритмы игры «Быки и коровы» для варианта неповторяющихся цифр: https://ru.wikipedia.org/wiki/%D0%91...BE%D0%B2%D1%8B для отгадывания числа человеком и компьютером. Усложненный вариант – реализовать стратегию игры компьютера при которой даются непротиворечивые ответы, максимизирующие число ходов соперника. Реализовать интерфейс игры." Вопрос. Кто сталкивался с данной задачей интересует реализация алгоритма нахождения "быстрого ответа". Математика и анализ следующего хода. Интересует исключительно для саморазвития. Google знаю, английский читаю, а вот примеры вашего кода на Js, будет то, что надо |
Poznakomlus,
мысли вслух 1234 некое число угаданных удалить в которых нет комбинаций некого числа из 4 1 убрать все числа в которых нет 1 или 2 или 3 или 4 + убрать по маске 1ххх х2хх и т.д. 2 число убрать все числа в которых нет 1 и 2 или 1 и 3 или 1 и 4 или и тд + убрать по маске 12хх 1х3х 1хх4 и т.д. 3 числа также 1и 2и3 или т.д. + маска 123х 12х4 1х23 х234 4 числа удалить все в которых нет комбинаций 4 из 4 если есть быки по маске не удалять |
Цитата:
|
Спасибо откликнувшимся.
Игра то работает, решето отрабатывает все условия. Может вы меня неправильно поняли. Объясню подробнее. На начальном этапе я генерирую все 4536 вариантов ответов Вопрос? Есть ли математический подход, выбор правильного первого хода, второго хода и т. д. Потому как к примеру http://slovesnov.narod.ru/articles/bullcow.pdf первый ход находится методом перебора всех действительных вариантов ответов. Или примеры с описаниями матрицы готовых ходов. Меня интересует функция куда бы я передавал массив решений а в ответ она мне оптимальный ответ(ход). Алгоритм самой этой функции. Думаю, что кроме тупого перебора подобное должно быть. Может у кого на досуге появится желание поиграть в игру и найти алгоритм хода |
:write: без фильтра коровы быки и без маски ... условно отгадываем 2 числа неважно коровы или быки
<!DOCTYPE HTML>
<html>
<head>
<title>Untitled</title>
<meta charset="utf-8">
</head>
<body>
<script>
function buildAnswers() {
var all_res = [];
for (var i = 1; i < 10; ++i) {
for (var j = 0; j < 10; ++j) {
if (j == i) continue;
for (var k = 0; k < 10; ++k) {
if (k == j || k == i) continue;
for (var l = 0; l < 10; ++l) {
if (l == k || l == j || l == i) continue;
all_res.push([i, j, k, l]);
}
}
}
}
return all_res;
}
var arr = buildAnswers();
function getNum(arr) {
return arr[Math.floor(Math.random() * arr.length)]
}
function test(arr, n) {
return function(a) {
var k = 0,
s;
for (var i = 0; i < 4; i++) {
s = (arr[0] - a[i]) * (arr[1] - a[i]) * (arr[2] - a[i]) * (arr[3] - a[i])
if (!s) k++
}
return k >= n
}
}
var filter = test(num, 1);
function filterAnswers(arr, filter) {
for (var i = arr.length - 1; i > -1; i--) {
if (!filter(arr[i])) arr.splice(i, 1);
}
}
for (var i = 0; i < 5; i++) {
var num = getNum(arr); //выбрали любое число из массива
document.write(num + " количество вариантов " + arr.length + "<br>");
var filter = test(num, 2); //условно 5 раз угадали по 2 числа
filterAnswers(arr, filter)
}
document.write("осталось вариантов " + arr.length + "<br>"); // осталось вариантов
</script>
</body>
</html>
|
рони,
getNum(arr); - вот это слабое звено. Вместо рандомных вариантов, должна функция возвращать лучший, то есть после которого число оставшихся будет минимальным, срез вариантов максимальным |
Цитата:
<!DOCTYPE HTML>
<html>
<head>
<title>Untitled</title>
<meta charset="utf-8">
</head>
<body>
<script>
function buildAnswers() {
var all_res = [];
for (var i = 1; i < 10; ++i) {
for (var j = 0; j < 10; ++j) {
if (j == i) continue;
for (var k = 0; k < 10; ++k) {
if (k == j || k == i) continue;
for (var l = 0; l < 10; ++l) {
if (l == k || l == j || l == i) continue;
all_res.push([i, j, k, l]);
}
}
}
}
return all_res;
}
var arr = buildAnswers();
function getNum(arr) {
return arr[Math.floor(Math.random() * arr.length)]
}
function test(arr, n) {
return function(a) {
var k = 0,
s;
for (var i = 0; i < 4; i++) {
s = (arr[0] - a[i]) * (arr[1] - a[i]) * (arr[2] - a[i]) * (arr[3] - a[i])
if (!s) k++
}
return k >= n
}
}
var filter = test(num, 1);
function filterAnswers(arr, filter) {
for (var i = arr.length - 1; i > -1; i--) {
if (!filter(arr[i])) arr.splice(i, 1);
}
}
var num = getNum(arr); //выбрали любое число из массива
document.write(num + " количество вариантов " + arr.length + "<br>");
var filter = test(num, 4); //условно угадали 4 числа
filterAnswers(arr, filter)
document.write("осталось вариантов " + arr.length + "<br>" + arr.join("<br>")); // осталось вариантов
</script>
</body>
</html>
|
:write: добавил маску ... вариант угадали 4 числа из них 2 быка, затем 4 числа 0 быков
<!DOCTYPE HTML>
<html>
<head>
<title>Untitled</title>
<meta charset="utf-8">
</head>
<body>
<script>
function buildAnswers() {
var all_res = [];
for (var i = 1; i < 10; ++i) {
for (var j = 0; j < 10; ++j) {
if (j == i) continue;
for (var k = 0; k < 10; ++k) {
if (k == j || k == i) continue;
for (var l = 0; l < 10; ++l) {
if (l == k || l == j || l == i) continue;
all_res.push([i, j, k, l]);
}
}
}
}
return all_res;
}
var arr = buildAnswers();
function getNum(arr) {
return arr[Math.floor(Math.random() * arr.length)]
}
function test(arr, n, bull) {
return function(a) {
var k = 0, t = 0,
s;
for (var i = 0; i < 4; i++) {
if(arr[i] == a[i] ) t++;
s = (arr[0] - a[i]) * (arr[1] - a[i]) * (arr[2] - a[i]) * (arr[3] - a[i])
if (!s) k++
}
if(t != bull) return false;
return k >= n
}
}
var filter = test(num, 1);
function filterAnswers(arr, filter) {
for (var i = arr.length - 1; i > -1; i--) {
if (!filter(arr[i])) arr.splice(i, 1);
}
}
var num = getNum(arr); //выбрали любое число из массива
document.write(num + " количество вариантов " + arr.length + "<br>");
var filter = test(num, 4, 2); //условно угадали 4 числа -- 2 быка
filterAnswers(arr, filter)
var num = getNum(arr); //выбрали любое число из массива
document.write("осталось вариантов " + arr.length + "<br>" + arr.join("<br>"));
var filter = test(num, 4, 0); //условно угадали 4 числа -- 0 быков
filterAnswers(arr, filter)
document.write("<br>осталось вариантов " + arr.length + "<br>" + arr.join("<br>")); // осталось вариантов
</script>
</body>
</html>
|
рони,
чуточку не понимаю ход твоих мыслей. В решении задачи приведенной выше все то что ты показываешь уже есть. Стоит указать ответ 4 коровы и посмотреть размерность массива. Кроме того у тебя не учитывается бык(число совпало и находится в той же позиции) это или корова(число есть но находится в другой позиции). Так как это сразу уменьшает количество ответов. И вопрос в том каков должен быть первый ход, следующий и т.д. Функция нахождения ходов |
Poznakomlus,
добавил проверку быков -- пост 8 -- думаю что случайный выбор из оставшихся самый правильный. |
Цитата:
|
:write:
вариант поиграть с подсчётом шагов первая цифра всего угадано пробел быков (на своём месте) пример 3 1 -- 3 угадано 1 на своём месте 2 0 две угадано на своём месте нет .
<!DOCTYPE HTML>
<html>
<head>
<title>Untitled</title>
<meta charset="utf-8">
</head>
<body>
<script>
function buildAnswers() {
var all_res = [];
for (var i = 1; i < 10; ++i) {
for (var j = 0; j < 10; ++j) {
if (j == i) continue;
for (var k = 0; k < 10; ++k) {
if (k == j || k == i) continue;
for (var l = 0; l < 10; ++l) {
if (l == k || l == j || l == i) continue;
all_res.push([i, j, k, l]);
}
}
}
}
return all_res;
}
var arr = buildAnswers();
function getNum(arr) {
return arr[Math.floor(Math.random() * arr.length)]
}
function test(arr, n, bull) {
return function(a) {
var k = 0, t = 0,
s;
for (var i = 0; i < 4; i++) {
if(arr[i] == a[i] ) t++;
s = (arr[0] - a[i]) * (arr[1] - a[i]) * (arr[2] - a[i]) * (arr[3] - a[i])
if (!s) k++
}
if(t != bull) return false;
return k >= n
}
}
var filter = test(num, 1);
function filterAnswers(arr, filter) {
for (var i = arr.length - 1; i > -1; i--) {
if (!filter(arr[i])) arr.splice(i, 1);
}
}
var num = getNum(arr);
for (var i=1; arr.length > 1; i++) {
var data = prompt("всего запятая быков в числе "+ num, "").split(/\D+/) ;
var filter = test(num, data[0], data[1]);
filterAnswers(arr, filter)
document.write(num + " " + data +" осталось вариантов " + arr.length + " шаг "+i+"<br>");
num = arr[Math.floor(.5 * arr.length)]
}
document.write("<br>осталось вариантов " + arr.length + "<br>" + arr.join("<br>"));
</script>
</body>
</html>
|
Poznakomlus,
да пожалуй случайное не самое оптимальное -- но работает. Цитата:
Цитата:
|
Не могу плюсануть. Вижу игра понравилась :)
|
Poznakomlus,
очередная версия ))) проверьте будет ли у вас больше 7 ходов Цитата:
<!DOCTYPE HTML>
<html>
<head>
<title>Untitled</title>
<meta charset="utf-8">
</head>
<body>
<script>
function buildAnswers() {
for (var a = [], d = 1; 10 > d; ++d)
for (var b = 0; 10 > b; ++b)
if (b != d)
for (var c = 0; 10 > c; ++c)
if (c != b && c != d)
for (var e = 0; 10 > e; ++e) e != c && e != b && e != d && a.push([d, b, c, e]);
return a
}
var arr = buildAnswers(),
z = [1, 2, 3, 4, 5, 6, 7, 8, 9].sort(function() {
return Math.random() - .5
});
z.push(z[Math.floor(Math.random()*4)],z[Math.floor(Math.random()*4)+4],0);
function getNum(a) {
return z.length && a.length > 10 ? z.splice(0, 4) : a[Math.floor(Math.random() * a.length)]
}
function test(a, d, b) {
return function(c) {
for (var e = 0, g = 0, h, f = 0; 4 > f; f++) a[f] == c[f] && g++, (h = (a[0] - c[f]) * (a[1] - c[f]) * (a[2] - c[f]) * (a[3] - c[f])) || e++;
return g != b ? !1 : e >= d
}
}
function filterAnswers(a, d) {
for (var b = a.length - 1; - 1 < b; b--) d(a[b]) || a.splice(b, 1)
};
for (var i = 1; arr.length > 1; i++) {
var num = getNum(arr),
data = prompt("всего запятая быков в числе " + num, "").split(/\D+/)
filter = test(num, data[0], data[1]);
filterAnswers(arr, filter)
document.write(num + " " + data + " осталось вариантов " + arr.length + " шаг " + i + "<br>");
}
document.write("<br>осталось вариантов " + arr.length + "<br>" + arr.join("<br>"));
</script>
</body>
</html>
|
2,1,3,5 1,0 осталось вариантов 2677 шаг 1
6,4,9,8 1,0 осталось вариантов 1602 шаг 2 7,2,9,0 1,1 осталось вариантов 439 шаг 3 7,0,5,6 0,3 осталось вариантов 7 шаг 4 7,0,5,9 1,2 осталось вариантов 5 шаг 5 7,0,1,6 0,2 осталось вариантов 3 шаг 6 7,8,5,6 0,3 осталось вариантов 2 шаг 7 7,9,5,6 0,4 осталось вариантов 1 шаг 8 осталось вариантов 1 7,9,5,6 :) 8 ходов |
Цитата:
защиты от дурака нет, поэтому просьба играть по правилам быков вторая цифра не может быть больше общего числа угаданных |
| Часовой пояс GMT +3, время: 17:21. |