Сложилось, что разбирал со студентами LINQ, а со школьниками преобразование между римской и арабской системой счисления. В итоге, мысли заплелись и получился интересный код конвертора, который жалко схоронить в локальных архивах. Пример сгодится в качестве упражнения для понимания LINQ.
Итак, нам понадобится словарь, сопоставляющий элементы римских чисел с арабскими.
Используя этот словарь можно написать конверторы из римской в арабскую нотацию и обратно. Для краткости и красоты мы не будем обрабатывать предусловия. Для арабских цифр допустимый диапазон определен как [1,4000). А римские цифры должны быть корректными и преобразованы к верхнему регистру.
Разбор числа начинаем с больших чисел. Ключи в словаре упорядочены в порядке убывания. Просматривая их в заданном порядке находим первый ключ со значением не более конвертируемого числа (оператор Where). В словаре этому числу сопоставлено буквенное сочетание из римской системы счисления. Склеиваем найденное буквенное сочетание с рекурсивно конвертированным остатком числа (оператор Select). Первый результат и будет искомым представлением числа в римской нотации (оператор FirstOrDefault).
Разбор римского числа происходит слева направо. Просматриваем все буквенные сочетания из словаря на вхождение в начало преобразуемой строки number.StartsWith(d.Value). При совпадении поле ключа будет содержать числовое значение, соответствующее буквенному сочетанию. Полученное значение суммируется с рекурсивно обработанной оставшейся строкой.
На этом можно было бы остановиться. Но оказывается, что число 499 можно записать пятью способами: CDXCIX, LDVLIV, XDIX, VDIV или ID. Для краткой записи могут использоваться не заданные в словаре сочетания. Можно расширить словарь, а можно отталкиваться только от исходных букв IVXLCDM, которым соответствуют числа (1,5,10,50,100,500,1000).
В целях прокачки навыков .Net мага VC-уровня (VC == 95), словарь сгенерируем автоматически. А полученный код можно использовать для проверки навыков чтения чужого кода на вступительных испытаниях в школу .Net магов IC-уровня.
Для генерации словаря пришлось воспользоваться внешней переменной. Далее код без комментариев.
А вот для перевода в римскую систему для краткости потребовалась пара вспомогательных функций. Можно их включить в саму функцию, но получится нагромождение.
Эти примеры далеко не оптимальны по скорости работы, но их можно использовать. И прежде всего, в обучении основам LINQ.
Итак, нам понадобится словарь, сопоставляющий элементы римских чисел с арабскими.
Dictionary<int, string> ra = new Dictionary<int, string>
{ { 1000, "M" }, { 900, "CM" }, { 500, "D" }, { 400, "CD" }, { 100, "C" },
{ 90 , "XC" }, { 50 , "L" }, { 40 , "XL" }, { 10 , "X" },
{ 9 , "IX" }, { 5 , "V" }, { 4 , "IV" }, { 1 , "I" } };
Используя этот словарь можно написать конверторы из римской в арабскую нотацию и обратно. Для краткости и красоты мы не будем обрабатывать предусловия. Для арабских цифр допустимый диапазон определен как [1,4000). А римские цифры должны быть корректными и преобразованы к верхнему регистру.
Конвертер из арабских в римские
Разбор числа начинаем с больших чисел. Ключи в словаре упорядочены в порядке убывания. Просматривая их в заданном порядке находим первый ключ со значением не более конвертируемого числа (оператор Where). В словаре этому числу сопоставлено буквенное сочетание из римской системы счисления. Склеиваем найденное буквенное сочетание с рекурсивно конвертированным остатком числа (оператор Select). Первый результат и будет искомым представлением числа в римской нотации (оператор FirstOrDefault).
string ToRoman(int number) => ra
.Where(d => number >= d.Key)
.Select(d => d.Value + ToRoman(number - d.Key))
.FirstOrDefault();
Конвертер из римских в арабские
Разбор римского числа происходит слева направо. Просматриваем все буквенные сочетания из словаря на вхождение в начало преобразуемой строки number.StartsWith(d.Value). При совпадении поле ключа будет содержать числовое значение, соответствующее буквенному сочетанию. Полученное значение суммируется с рекурсивно обработанной оставшейся строкой.
int ToArabic(string number) => number.Length == 0 ? 0 : ra
.Where(d => number.StartsWith(d.Value))
.Select(d => d.Key + ToArabic(number.Substring(d.Value.Length)))
.FirstOrDefault();
Готовый класс для копипастинга v1
static class RomanNum
{
// (c) 2015, Alexey Danov | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY ...
static Dictionary<int, string> ra = new Dictionary<int, string>
{ { 1000, "M" }, { 900, "CM" }, { 500, "D" }, { 400, "CD" }, { 100, "C" },
{ 90 , "XC" }, { 50 , "L" }, { 40 , "XL" }, { 10 , "X" },
{ 9 , "IX" }, { 5 , "V" }, { 4 , "IV" }, { 1 , "I" } };
public static string ToRoman(int number) => ra
.Where(d => number >= d.Key)
.Select(d => d.Value + ToRoman(number - d.Key))
.FirstOrDefault();
public static int ToArabic(string number) => number.Length == 0 ? 0 : ra
.Where(d => number.StartsWith(d.Value))
.Select(d => d.Key + ToArabic(number.Substring(d.Value.Length)))
.First();
}
На этом можно было бы остановиться. Но оказывается, что число 499 можно записать пятью способами: CDXCIX, LDVLIV, XDIX, VDIV или ID. Для краткой записи могут использоваться не заданные в словаре сочетания. Можно расширить словарь, а можно отталкиваться только от исходных букв IVXLCDM, которым соответствуют числа (1,5,10,50,100,500,1000).
В целях прокачки навыков .Net мага VC-уровня (VC == 95), словарь сгенерируем автоматически. А полученный код можно использовать для проверки навыков чтения чужого кода на вступительных испытаниях в школу .Net магов IC-уровня.
Конвертер из римских в арабские с обвязкой
Для генерации словаря пришлось воспользоваться внешней переменной. Далее код без комментариев.
int o = 1;
string w = "IVXLCDM";
Dictionary<char, int> ra = w.ToDictionary(ch => ch, ch => (o = ("" + o)[0] == '1' ? o * 2 : o * 5) / 2);
int ToArabic(string num) =>
num.Select((c, i) => ++i < num.Length && ra[c] < ra[num[i]] ? -ra[c] : ra[c]).Sum();
Конвертер из арабских в римские с обвязкой
А вот для перевода в римскую систему для краткости потребовалась пара вспомогательных функций. Можно их включить в саму функцию, но получится нагромождение.
string W(int k, int l = 1) => w.Substring(k, l);
string R(char m, int k) =>
m == '9' ? W(k-2)+W(k) : m == '5' ? W(k-1) : m == '4' ? W(k-2, 2) : W(k-2);
string ToRoman(int num) => num < 1 ? "" :
(from z in "000100101".Split('1') from m in "9541" select m + z)
.Where(z => num >= (o = int.Parse(z)))
.Select(z => R(z[0], z.Length * 2)).First() + ToRoman(num - o);
Готовый класс для копипастинга v2
static class RomanNumEx
{
// (c) 2015, Alexey Danov | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY ...
static int o = 1;
static string w = "IVXLCDM";
static Dictionary<char, int> ra = w.ToDictionary(ch => ch, ch => (o = ("" + o)[0] == '1' ? o * 2 : o * 5) / 2);
public static int ToArabic(string num) => num
.Select((c, i) => ++i < num.Length && ra[c] < ra[num[i]] ? -ra[c] : ra[c]).Sum();
static string W(int k, int l = 1) => w.Substring(k, l);
static string R(char m, int k) => m == '9' ? W(k-2)+W(k) : m == '5' ? W(k-1) : m == '4' ? W(k-2, 2) : W(k-2);
public static string ToRoman(int num) => num < 1 ? "" :
(from z in "000100101".Split('1') from m in "9541" select m + z)
.Where(z => num >= (o = int.Parse(z)))
.Select(z => R(z[0], z.Length * 2)).First() + ToRoman(num - o);
}
Эти примеры далеко не оптимальны по скорости работы, но их можно использовать. И прежде всего, в обучении основам LINQ.
Комментарии (13)
Sane
17.11.2015 14:36+6И еще пару слов про код — очень плохая практика использовать в методах, которые вызываются в linq сайд эффекты — присваивание переменных и подобное:
Dictionary<char, int> ra = w.ToDictionary(ch => ch, ch => (o = ("" + o)[0] == '1' ? o * 2 : o * 5) / 2);
Если вам нужны локальные переменные — используйтеlet. Плюс странная констркуция ("" + o)[0] — это первый символ числа? Тогда пишите явно o.ToString()[0]. Но все равно присовение внутри linq функций — это плохо. Тоже самое и здесь
num.Select((c, i) => ++i < num.Length && ra[c] < ra[num[i]] ? -ra[c] : ra[c])
++i лучше заменить на i+1.
И во втором ToRoman.
Также нежелательно смешивать linq синтаксис и вызовы extension методов. Понятно, что во втором ToRoman нужен последний First(), но тогда либо весь предыдущий запрос писать в linq синтаксисе, либо весь в цепочку вызовов.
Danov
17.11.2015 21:32-1очень плохая практика использовать в методах, которые вызываются в linq сайд эффекты — присваивание переменных и подобное
Это утверждение верное, но не надо его возводить в ранг мантры. Аналогичный баг находится у студентов с оператором GOTO. Половина знает о его существовании, но все утверждают, что им пользоваться нельзя. И громоздят в коде флаги, дополнительные переменные для выхода из вложенных циклов.
Конкретно в этом фрагменте кода локальная статическая переменная используется только раз при первом обращении к классу. Единственный вред от нее — занимает 4 байта памяти. Даже многопоточность не может привести к конфликту в коде генерации словоря. Во втором случае использования переменной будут конфликты потоков.
Также нежелательно смешивать linq синтаксис и вызовы extension методов
Согласен, что «нежелательно». С другой стороны, декартово произведение проще получить в linq синтаксисе. Аналог оператора let через вызовы extension методов мне неизвестен.
PS: Позже сделаю еще одну LINQ-версию, исправленную.Sane
18.11.2015 10:35+1Ну уж нет, именно в ранг мантры. Такой код сложно читать, практически невозможно рефакторить. То же самое касается goto. Такой код в продакшене — повод поговорить про профнепригодность.
Аналог let — это Select с анонимным типом внутри.
А вы действительно учите этому студентов?Danov
18.11.2015 15:04Аналог let — это Select с анонимным типом внутри.
Невозможно переписать значение переменной объявленной оператором let и поля анонимного класса тоже ReadOnly. Почему у вас такое отторжение к механизму замыкания переменных?
А вы действительно учите этому студентов?
Учу много чему и с очень давних времен. Есть чем гордиться. Сейчас только один предмет веду близкий по содержанию к Data Mining. А LINQ студентам рассказал, чтобы они не городили мне горы циклов. (про уход от темы и ваш вариант ниже).Sane
18.11.2015 16:35Я совершенно не против замыканий. Я против использования нечистых функций в linq в частности и в функциональных подходах (linq, как ни крути, это кусочек функционального мира в императивном C#) в общем. Все ваши примеры можно переписать с использованием чистых функций, и, отвечая на ваш вопрос ниже, они вполне подходят для обучения студентов. Горы циклов, это, конечно, не очень, но такое использование linq, на мой взгляд, усложняет его понимание и уводит несколько в сторону от его базовых понятий — комбинации функций, ленивые вычисления и так далее.
omikad
19.11.2015 05:41Также нежелательно смешивать linq синтаксис и вызовы extension методов
Чем смешивать плохо, какие аргументы?
Я имею в виду такое, допустим код вида
(from b in a where .... select ...).ToArray(...).Where(...) ...
То ее если ее переписать в длинную цепочку как
a.Where(...).Select(...).ToArray(...).Where(...) ...
То дебажить и исследовать их одинаково тяжело, а вот читать первую мне больше нравится. Особенно, если в выражении есть group by и join, которые в extension методах смотрятся очень плохо.
Было бы здорово услышать аргументы против
impwx
17.11.2015 16:29Однобуквенные переменные, магия со строками, присвоение в статическую переменную из LINQ-запроса… Это заявка на участие в конкурсе обфусцированных программ?
Danov
17.11.2015 21:36-2Код v2 предлагается использовать для анализа и для проверки способностей кандидатов. Один кандидат опишет алгоритм работы и все недостатки с обоснованием. А другой может эмоционально ругаться и отказываться вникать в код. Вы которого на работу возьмете?
Sane
18.11.2015 10:37+1Второго. Если б я увидел такой код на собеседовании — я бы усомнился в адекватности собеседующих и задумался о вакансии в принципе. Мне придется разбираться с таким кодом на работе? Вы реально так пишите? Какие мои навыки вы проверяете?
Danov
18.11.2015 14:53Какие мои навыки вы проверяете?
Мышление и способность видеть алгоритм за набором символов. Знание базового синтаксиса C#Вы реально так пишите?
Для своего проекта могу написать подобный код. Например, парсер. Без генераторов. Ведь никого не смущает переменные и константы из алгебры a,b,c,d,x. Кроме того, такой код использую только для вещей, где говорящие названия только захламят текст программы, разнесут его на несколько абзацев то, что укладывается в одну строчку. Нет смысла использовать вместо X имя переменной Abscissa, а вместо Y — Ordinate.
Вы от сути тему уводите и переходите на личности. Можете предложить свой вариант решаемой задачи с помощью LINQ?Sane
18.11.2015 15:51Я, наверное, неправильно выразился — на личности переходить не хотелось, коненчо. Вопросы сверху — это те вопросы, которые я бы задал на собеседовании в ответ на такое задание.
На мой взгляд, такое задание наоборот, помешает мне увидеть алгоритм — это набор триков, который действительно выглядит как обфускация. Проверить этим мышление — наверное, да, получится. Но эта задачка (надеюсь) все-таки слишком далека от реального кода.
Например, мы на собеседовании даем вот такой вот код «на-объяснить»:
var groupToDictionary = function(arr, keyFunction) { var objToReturn = {}; arr.forEach(function(item) { var key = keyFunction(item); if (!objToReturn.hasOwnProperty(key)){ objToReturn[key] = []; objToReturn[key].getKey = function() { return key; }; } objToReturn[key].push(item); }); return objToReturn; };
Банальная функция, на которой, к сожалению, многие отваливаются. Но функция реальная, без подвохов.
Sane
К сожалению, Dictionary<,> в общем случае не сохраняет порядок добавления ключей. Если я не ошибаюсь, порядок теряется при перебалансировке. В вашем случае лучше подойдет просто список пар (ну или Tuple-ов).
Danov
Да, это верно для v1. Вариант v2 использует Dictionary как ассоциативный массив.