Алгоритм оценки MasterMind в С# с использованием LINQ

Я ищу элегантный способ вычислить оценку догадки в игре MasterMind на С#, предпочтительно используя LINQ.

В MasterMind кодоискатель генерирует секретный код из 4 цифр, используя цифры с 1 по 6. Цифра может использоваться более одного раза. Например, секретный код:

int[] secret = { 1, 2, 3, 1 };

Кодкрамер пытается разбить секретный код, представив предположение. В этом примере предполагается следующее:

int[] guess  = { 1, 1, 2, 2 };

(Оба кода и догадки теперь хранятся в массиве, но другие типы коллекций тоже в порядке).

Кодекейкер затем "оценивает" эту догадку, объявляя количество "черных" и "белых". За каждую цифру присваивается черный цвет, который правилен как по значению, так и по положению. Для каждой правильной цифры помещается белый цвет в неправильном положении. В этом примере оценка 1 черная (для "1" в позиции 1) и 2 белых (для "1" и "2" в позициях 2 и 3).

Вернуться к вопросу: Я ищу элегантный способ вычислить оценку угадывания в С#, предпочтительно используя LINQ. До сих пор я придумал инструкцию, которая вычисляет количество черных:

int blacks = new int[] { 0, 1, 2, 3 }.Count(i => (guess[i] == secret[i]));

Я собирался продолжить по строкам, что количество белых - это общее количество матчей (3) минус количество черных. Поэтому я попробовал:

int whites = guess.Intersect(secret).Count() - blacks;

Но, увы, IEnumerable.Intersect() создает {1, 2} вместо {1, 1, 2}, потому что он смотрит только на отдельные цифры. Поэтому он вычисляет белые = 1 вместо 2.

Я не могу придумать другой способ вычисления "белых", кроме как использовать вложенные петли типа "С". Ты можешь? Предпочтительно использовать LINQ - мне нравится способ, которым алгоритм может быть выражен в коде с использованием LINQ. Скорость выполнения не является проблемой.

Ответы

Ответ 1

var black = guess
        .Zip(secret, (g, s) => g == s)
        .Count(z => z);

var white = guess
        .Intersect(secret)
        .Sum(c =>
            System.Math.Min(
                secret.Count(x => x == c),
                guess.Count(x => x == c))) - black;

Дано:

int[] secret = { 1, 2, 3, 1 };
int[] guess  = { 1, 1, 2, 2 };

Тогда:

black == 1 && white == 2

Ответ 2

Здесь один из способов (если я правильно понял проблему):

  • Найдите черную оценку - это достаточно легко; это просто вопрос застегивания последовательностей вверх и подсчет количества соответствующих элементов, которые соответствуют.

  • Найдите количество "общих элементов" между обеими последовательностями - это должна быть сумма белых и черных баллов.

  • Найдите белый счет - просто разница между 2. и 1.

// There must be a nicer way of doing this bit
int blackPlusWhite = secret.GroupBy(sNum => sNum)
                           .Join(guess.GroupBy(gNum => gNum),
                                 g => g.Key,
                                 g => g.Key,
                                (g1, g2) => Math.Min(g1.Count(), g2.Count()))
                           .Sum();   

int black = guess.Zip(secret, (gNum, sNum) => gNum == sNum)
                 .Count(correct => correct); 

int white = blackPlusWhite - black;

EDIT: смешанный черный и белый.

EDIT: (OP не входит в .NET 4). В .NET 3.5 вы можете вычислить черный цвет с помощью:

int black = Enumerable.Range(0, secret.Count)
                      .Count(i => secret[i] == guess[i]);

Ответ 3

Ответ Ани - это хорошо. Здесь более приятный (более ясный) способ сделать эту группировку и присоединение.

ILookup<int, int> guessLookup = guess.ToLookup(i => i);

int blackPlusWhite
(
  from secretNumber in secret.GroupBy(i => i)
  let secretCount = secretNumber.Count()
  let guessCount = guessLookup[secretNumber.Key].Count()
  select Math.Min(secretCount, guessCount)
).Sum()

int black = Enumerable.Range(0, secret.Count).Count(i => guess[i] == secret[i]);

int white = blackPlusWhite - black;