1

Один мой друг предложил мне поиграть в игру. Это пошаговая игра и на двух игроков. Вот правила:

  • Оба игрока загадывают четырёхзначное число.
  • Потом они подбрасывают монетку, чтобы решить, кто ходит первым.
  • Первый игрок пытается отгадать число второго игрока.
  • Если у него не получается, второй игрок сообщает первому игроку два числа:

    1. Первое число означает количество угаданных цифр в числе без учёта позиции.
    2. Второе число означает количество правильно угаданных позиций.

      Пример: Первый игрок загадал число 2737 Второй игрок пытается отгадать число. Он говорит 2274 Первый игрок отвечает ему 2, 1

  • Потом они меняются

  • Это продолжается до тех пор, пока один из них не отгадает всё число оппонента.

Я выиграл в этой игре пользуясь следующим алгоритмом:

Представим, что наш оппонент загадал 4856

  1. Сначала мы загадываем 4 случайных цифры.

    1234

    Затем смотрим на ответ. В нашем случае это 1, 0

  2. На следующий ход мы повышаем первую цифру на один от самой большой, присутствующей в числе. В нашем случае это 5.

    5234 #=> [2, 0]

  3. Так как мы обнаружили новую цифру, мы двигаем её вправо на одну позицию, заменяя уже существующую. Также мы снова увеличиваем первую цифру на один.

    6534 #=> [3, 0]

  4. 7654 #=> [3, 1] Мы отгадали первую позицию. Это 5 или 6, так как 7 не увеличила наше первое число в ответе.

  5. 8654 #=> [4, 1] Ура! Мы нашли все цифры. Осталось только найти для них правильные места. Так что мы попробуем попереставлять их, начиная с самой левой.
  6. 6854 #=> [4, 2]
  7. 5864 #=> [4, 1] Тут мы потеряли одну цифру. Это значит, что она была на правильном месте. Вернём её и будет игнорировать в будущем.
  8. 4856 #=> [4, 4] Мы выиграли.

Мы выиграли за 8 ходов. Я пробовал играть в эту игру с другими людьми, используя этот алгоритм, и в большинстве случаем выигрывал. Но всё же мне кажется, что он слишком примитивен. Должен быль способ выиграть эту игру при любом раскладе за наименьшее количество ходов. Есть идеи?

12
  • 2
    Это же "быки и коровы"? для них я когда-то в детстве, когда еще не программировал - вернее, только на калькуляторе - для проверки идеи несколько раз играл так:вариантов не так много, 5040, словом, составлен список. Далее по ответу вычеркиваем все не годящиеся, и составляем такой вопрос, чтобы ответ на него выбрасывал как можно больше вариантов (там я придумывал какие-то эвристики). Выигрывалось очень быстро, но так как тому уже далеко не один десяток лет, детали не помню.
    – Harry
    25 сен 2016 в 12:45
  • Какой ответ подразумевается на 4311, если загадано 1199? 1,0 или 2,0 или 4,0?
    – jfs
    25 сен 2016 в 13:24
  • @jfs в таком случае [2, 0]
    – Viktor
    25 сен 2016 в 13:26
  • А для 4321 было бы 1,0?
    – jfs
    25 сен 2016 в 13:29
  • @jfs всё верно.
    – Viktor
    25 сен 2016 в 13:29

1 ответ 1

2

На качество прошу не смотреть, писалось со скоростью набора на коленке :) В нескольких тестовых партиях угадывало за 5 вопросов. Эвристики никакой :), просто случайным образом берем первый попавшийся вариант из допустимых.

Модифицированные быки-коровы - с разрешенным повторением цифр; первая 0 быть не может.

#include <vector>
#include <string>
#include <iostream>
#include <iomanip>
#include <algorithm>

using namespace std;

vector<int> var;

class Checker
{
public:
    Checker(int val, int tot, int pos):val(val),tot(tot),pos(pos)
    {
        digs[0] = val/1000;
        digs[1] = val/100%10;
        digs[2] = val/10%10;
        digs[3] = val%10;
    };

    bool operator()(int chk) const
    {
        unsigned char cigs[4];
        cigs[0] = chk/1000;
        cigs[1] = (chk/100)%10;
        cigs[2] = (chk/10)%10;
        cigs[3] = chk%10;

        int position = (digs[0]==cigs[0]) + (digs[1]==cigs[1]) + (digs[2]==cigs[2]) + (digs[3]==cigs[3]);
        if (position != pos) return true;

        int tots = 0;
        bool is[4] = { false, false, false, false };
        for(int i = 0; i < 4; ++i)
        {
            for(int j = 0; j < 4; ++j)
            {
                if (is[j]) continue;;
                if (cigs[i] == digs[j])
                {
                    tots++;
                    is[j] = true;
                    break;
                }
            }
        }
        if (tots != tot) return true;

        return false;
    }
private:
    int val, tot, pos;
    unsigned char digs[4];
};

int main(int argc, const char * argv[])
{
    for(int i1 = 1; i1 < 10; ++i1)
        for(int i2 = 0; i2 < 10; ++i2)
            for(int i3 = 0; i3 < 10; ++i3)
                for(int i4 = 0; i4 < 10; ++i4)
                    var.push_back(((i1*10+i2)*10+i3)*10+i4);

    while(var.size() >= 1)
    {
        random_shuffle(var.begin(),var.end());
        cout << "Size = " << setw(4) << var.size() << "  > " << var[0] << "? ";
        int tot, pos;
        cin  >> tot >> pos;
        if (tot == 4 && pos == 4)
        {
            cout << "I won!\n";
            break;
        }
        var.erase(remove_if(var.begin(),var.end(),Checker(var[0],tot,pos)),var.end());
    }

}

Update. Провел эксперимент по отгадыванию всех 9000 чисел. Получилось примерно (прогнал только один цикл по всем числам) такие результаты:

  Попыток  Количество
  -------------------
        2          12
        3          91
        4         614
        5        1865
        6        3138
        7        2329
        8         763
        9         165
       10          23
2
  • Можете добавить пояснения к алгоритму? Не все люди на SO хорошо знают C. Я, например, рубист.
    – Viktor
    23 окт 2016 в 21:03
  • Я писал в комментариях к вопросу: составляю список всех возможных вариантов. Пока варианты есть - перетасовываю список случайным образом, и выдаю запрос из первого элемента. Получаю ответ, выбрасываю все элементы списка, которые не подходят под этот ответ. Повторяю цикл...
    – Harry
    24 окт 2016 в 2:01

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.