LINQ и алгоритмические задачи | Кодементор
фото Джей Джей Ин на Скрыть
Некоторое время назад я нашел очень интересный блог интервьюера Google. Алекс Голец. У него есть несколько статей о вопросах для интервью с решениями на Python. И те же задачи я решал на своем любимом C# (не подглядывая, конечно, в ответы!). И во время сравнения своего решения с предоставленными решениями Python я понял, насколько LINQ мой образ мышления и мой способ решения задач программирования.
Позвольте мне показать, что я имею в виду. Вот первая задача, Поиск отношения:
У вас есть набор известных коэффициентов конверсии, таких как:
— 1 рука равна 4 дюймам
— 4 дюйма равны 0,33333 фута
— 0,33333 фута равняется 6,3125e-5 миль
— 6,3125e-5 миль равняется 1,0737e-17 световых летУчитывая такой список, разработайте алгоритм, который принимает два произвольных значения единиц и возвращает коэффициент конверсии между ними.
И вот мое решение задачи:
Скрипка
static (string source, string destination, double coef)[] coeffs = {
("foot", "inch", 12),
("hand", "inch", 4),
("mile", "foot", 5280),
("light year", "km", 9.461e+12),
("km", "mile", 0.621371)
};
static void Main(string[] args)
{
var allCoeffs = Queryable.Union<(string source, string destination, double coef)>(coeffs.AsQueryable(), coeffs.Select(s => (s.destination, s.source, 1 / s.coef))).ToArray();
var unit1 = "hand";
var unit2 = "light year";
var result = SearchConversion(allCoeffs, unit1, unit2);
Console.WriteLine(result);
}
private static double SearchConversion((string source, string destination, double coef)[] allCoeffs, string unit1, string unit2)
{
var result = 0.0;
var conversionAdded = allCoeffs.Where(w => w.source == unit1).Select(s => (destination:s.destination, coef:s.coef)).ToDictionary(k => k.destination, e => e.coef);
bool somethingChanged = true;
while (somethingChanged)
{
somethingChanged = false;
foreach (var existingConversion in conversionAdded.Keys.ToArray())
{
var nextStep = allCoeffs.Where(w => w.source == existingConversion && !conversionAdded.ContainsKey(w.destination));
foreach (var newConversion in nextStep)
{
if (existingConversion == unit1) continue;
var newCoeff = conversionAdded[existingConversion] * newConversion.coef;
conversionAdded.Add(newConversion.destination, newCoeff);
somethingChanged = true;
if (newConversion.destination == unit2)
{
result = newCoeff;
return result;
}
}
}
}
return result;
}
Первое, что следует упомянуть, это то, что операторы LINQ могут предоставлять простые однострочники для шагов решения. Без LINQ для этого потребовались бы отдельные методы или блоки кода. Например, вот добавление обратной конверсии в список конверсий:
var allCoeffs = Queryable.Union<(string source, string destination, double coef)>(
coeffs.AsQueryable(),
coeffs.Select(s => (s.destination, s.source, 1 / s.coef)))
.ToArray();
Следующая хорошая вещь заключается в том, что с LINQ вы используете итеративный подход вместо рекурсии. С помощью этого кода я получаю следующую порцию конверсий (поиск в ширину):
var nextStep = allCoeffs.Where(w => w.source == existingConversion
&& !conversionAdded.ContainsKey(w.destination));
Третье, что нелегко показать, но очень легко заметить, это то, что LINQ позволяет вам манипулировать вашей логикой для отладки и рефакторинга. Вы можете разделить длинное выражение на несколько частей. Вы можете использовать .ToArray() для просмотра результатов вычислений. Вы выполняете холодное преобразование данных для повышения производительности (например, преобразование массива в словарь). Или вы можете даже переписать некоторые части LINQ без LINQ, чтобы получить более понятный и управляемый код. Кстати, я очень доволен именованными кортежами, которые теперь есть в C#. Это действительно упрощает чтение и реализацию кода. И давайте проверим следующее задание интервью, Рыцарь Звонилка:
Вы кладете шахматную фигуру коня на панель набора номера телефона.
1 2 3 4 5 6 7 8 9 0Эта шахматная фигура движется в форме заглавной буквы «L»: два шага по горизонтали, за которыми следует один по вертикали, или один шаг по горизонтали, а затем два по вертикали.
Предположим, вы набираете клавиши на клавиатуре, используя только прыжки, которые может сделать рыцарь. Каждый раз, когда рыцарь приземляется на клавишу, мы набираем эту клавишу и делаем еще один прыжок. Начальная позиция считается набранной.
Сколько различных номеров вы можете набрать за N переходов из определенной начальной позиции?
Действительно сложная задача с учетом проблем с производительностью, но решение выглядит простым:
Скрипка
static (char source, char destination)[] moves = {
('1','6'),
('1','8'),
('2','7'),
('2','9'),
('3','4'),
('3','8'),
('4','3'),
('4','9'),
('4','0'),
('6','1'),
('6','0'),
('6','7'),
('7','6'),
('7','2'),
('8','1'),
('8','3'),
('9','4'),
('9','2'),
('0','4'),
('0','6')
};
static void Main(string[] args)
{
var unsymmetrical = moves.Where(w => !moves.Where(wi => wi.destination == w.source && wi.source == w.destination).Any());
if (unsymmetrical.Any())
{
Console.WriteLine("Incorrect input");
}
int N = 30;
char original="0";
var variantsCounts = new List<(char digit, long count)>();
variantsCounts.Add((original, 1));
for (int i = 0; i < N; i++)
{
var nextRoundUngrouped = variantsCounts
.Join(moves, phone => phone.digit, move => move.source, (phone, move) => (digit: move.destination, count: phone.count)).ToArray();
var nextRoundGrouped = nextRoundUngrouped.GroupBy(g => g.digit).Select(s => (digit: s.Key, count: s.Sum(v=>v.count))).ToList();
variantsCounts = nextRoundGrouped;
}
var sum = variantsCounts.Sum(s => s.count);
Console.WriteLine($"Number of phones: {sum}");
}
И здесь вы можете увидеть те же особенности: легко читаемый и легко отлаживаемый код и итеративный подход. Я разделил одно выражение LINQ, которое создает данные следующего шага, на два:
var nextRoundUngrouped = variantsCounts
.Join(moves, phone => phone.digit, move => move.source, (phone, move) => (digit: move.destination, count: phone.count)).ToArray();
var nextRoundGrouped = nextRoundUngrouped
.GroupBy(g => g.digit)
.Select(s => (digit: s.Key, count: s.Sum(v=>v.count)))
.ToList();
Это позволило мне во время отладки просматривать данные, которые у меня есть на каждом этапе. Но очень легко собрать все вместе, чтобы получить немного больше производительности:
var nextRoundGrouped = variantsCounts
.Join(moves, phone => phone.digit, move => move.source, (phone, move) => (digit: move.destination, count: phone.count))
.GroupBy(g => g.digit)
.Select(s => (digit: s.Key, count: s.Sum(v=>v.count)))
.ToList();
Итак, теперь для меня очевидно, что, несмотря на то, что LINQ был введен в основном для того, чтобы упростить реализацию бизнес-логики для корпоративных приложений, он формирует новый образ мышления при реализации алгоритмов. Во многих случаях это позволяет создавать лучший код. И, конечно же, очень интересно использовать простые соединения вместо вложенных циклов.
