Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 17.12.2014, 00:48
Аватар для Vlasenko Fedor
Профессор
Отправить личное сообщение для Vlasenko Fedor Посмотреть профиль Найти все сообщения от Vlasenko Fedor
 
Регистрация: 13.03.2013
Сообщений: 1,572

Быки и коровы
Как то мне попалось ниже приведенное тестовое задание.
Мой вариант решения здесь http://learn.javascript.ru/play/4WDZG

"Реализовать алгоритмы игры «Быки и коровы» для варианта неповторяющихся цифр:
https://ru.wikipedia.org/wiki/%D0%91...BE%D0%B2%D1%8B
для отгадывания числа человеком и компьютером. Усложненный вариант – реализовать стратегию игры компьютера при которой даются непротиворечивые ответы, максимизирующие число ходов соперника.
Реализовать интерфейс игры."

Вопрос. Кто сталкивался с данной задачей интересует реализация алгоритма нахождения "быстрого ответа". Математика и анализ следующего хода. Интересует исключительно для саморазвития. Google знаю, английский читаю, а вот примеры вашего кода на Js, будет то, что надо

Последний раз редактировалось Vlasenko Fedor, 17.12.2014 в 00:54.
Ответить с цитированием
  #2 (permalink)  
Старый 17.12.2014, 21:16
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 33,108

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
если есть быки по маске не удалять
Ответить с цитированием
  #3 (permalink)  
Старый 17.12.2014, 21:34
Профессор
Посмотреть профиль Найти все сообщения от krutoy
 
Регистрация: 09.11.2014
Сообщений: 610

Сообщение от рони
убрать все числа в которых нет 1 или 2 или 3 или 4
Твой алгоритм на этот момент не знает, какие числа введены. В твоем решении парадокс. Он на первом шаге знает, что комбинация может содержать 1||2||3||4 (-- а это коровы, их предстоит еще получить), чего на самом деле нет. Он должен рандомно сгенерить комбинацию 4-х [0-9], после этого он узнает коров и быков этой комбинации, если таковые есть, и так далее.

Последний раз редактировалось krutoy, 17.12.2014 в 21:39.
Ответить с цитированием
  #4 (permalink)  
Старый 17.12.2014, 22:18
Аватар для Vlasenko Fedor
Профессор
Отправить личное сообщение для Vlasenko Fedor Посмотреть профиль Найти все сообщения от Vlasenko Fedor
 
Регистрация: 13.03.2013
Сообщений: 1,572

Спасибо откликнувшимся.
Игра то работает, решето отрабатывает все условия. Может вы меня неправильно поняли. Объясню подробнее.
На начальном этапе я генерирую все 4536 вариантов ответов
Вопрос? Есть ли математический подход, выбор правильного первого хода, второго хода и т. д.
Потому как к примеру http://slovesnov.narod.ru/articles/bullcow.pdf первый ход находится методом перебора всех действительных вариантов ответов. Или примеры с описаниями матрицы готовых ходов.
Меня интересует функция куда бы я передавал массив решений а в ответ она мне оптимальный ответ(ход). Алгоритм самой этой функции. Думаю, что кроме тупого перебора подобное должно быть.
Может у кого на досуге появится желание поиграть в игру и найти алгоритм хода
Ответить с цитированием
  #5 (permalink)  
Старый 17.12.2014, 22:26
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 33,108

без фильтра коровы быки и без маски ... условно отгадываем 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>

Последний раз редактировалось рони, 18.12.2014 в 11:25.
Ответить с цитированием
  #6 (permalink)  
Старый 17.12.2014, 22:37
Аватар для Vlasenko Fedor
Профессор
Отправить личное сообщение для Vlasenko Fedor Посмотреть профиль Найти все сообщения от Vlasenko Fedor
 
Регистрация: 13.03.2013
Сообщений: 1,572

рони,
getNum(arr); - вот это слабое звено. Вместо рандомных вариантов, должна функция возвращать лучший, то есть после которого число оставшихся будет минимальным, срез вариантов максимальным
Ответить с цитированием
  #7 (permalink)  
Старый 17.12.2014, 22:43
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 33,108

Сообщение от Poznakomlus
getNum(arr); - вот это слабое звено.
попробуй выбрать наилучший результат из оставшихся ... случайно угадали 4 числа )))
<!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>

Последний раз редактировалось рони, 18.12.2014 в 11:25.
Ответить с цитированием
  #8 (permalink)  
Старый 17.12.2014, 23:09
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 33,108

добавил маску ... вариант угадали 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>

Последний раз редактировалось рони, 18.12.2014 в 11:26.
Ответить с цитированием
  #9 (permalink)  
Старый 17.12.2014, 23:40
Аватар для Vlasenko Fedor
Профессор
Отправить личное сообщение для Vlasenko Fedor Посмотреть профиль Найти все сообщения от Vlasenko Fedor
 
Регистрация: 13.03.2013
Сообщений: 1,572

рони,
чуточку не понимаю ход твоих мыслей. В решении задачи приведенной выше все то что ты показываешь уже есть. Стоит указать ответ 4 коровы и посмотреть размерность массива. Кроме того у тебя не учитывается бык(число совпало и находится в той же позиции) это или корова(число есть но находится в другой позиции). Так как это сразу уменьшает количество ответов. И вопрос в том каков должен быть первый ход, следующий и т.д. Функция нахождения ходов
Ответить с цитированием
  #10 (permalink)  
Старый 18.12.2014, 00:13
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 33,108

Poznakomlus,
добавил проверку быков -- пост 8 -- думаю что случайный выбор из оставшихся самый правильный.
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск