CodeStars. Track 04. Математика

Задача.
Чтобы узнать, сколько комментариев у тебя будет на GitHub, реши следующую задачу:На международном музыкальном фестивале участники говорят на множестве разных языков. Чтобы все могли понимать друг друга, организаторы предложили использовать автоматические переводчики, но переводчики есть не для всех пар языков. В текстовом файле в каждой строке содержится (через пробел) имя переводчика, с какого языка и на какой он может переводить. Какое минимальное количество переводчиков необходимо, чтобы переводить с Исландского на Албанский?

Предисловие.
Ох лол... у меня не будет комментариев на GitHub, потому что у меня нет аккаунта на GitHub. Но задача есть задача. Классическая задача на графы, каждый язык - вершина графа, а переводчик - ребро графа, связывающее языки. И надо найти кратчайший путь в графе. Структура данных проста: есть язык, точки входа и точки выхода. Алгоритм известен... что означает, мы с легкостью можем его загуглить, например здесь (Задача о кратчайшем пути в Википедии). Наученная прошлым опытом и вооруженная ленью, я предполагаю, что библиотеки работы с графами для C# уже есть. Есть три аспекта работы с графами: создание структуры данных, алгоритмы и отображение. Почти все библиотеки поддерживают создание структур и их отображение. Различия в основном лежат в алгоритмах визуализации, различных параметрах визуализации, механизмах выгрузки картинок (например в pdf), способа ввода данных и возможностях автоматической генерации графа. А вот математические алгоритмы реализует только QuickGraph. Может быть и не только он.. но остальных мне найти не удалось. )) 

1. Microsoft Automatic Graph Layout (MSAGL) она же Glee - собственно была библиотека Glee, теперь она же перекуплена MS, доработана и называется страшной аббревиатурой MSAGL. Также иногда в инетиках именуется Microsoft Glee. Что не совсем корректно, по ссылке есть раздел отличий.
2. Graphviz но в нем мне не устанавливая разобраться не удалось. Хотя в этом формате вот здесь есть пример: QuickGraph + Graphiz  . Если верить документации на сайте очень развитые варианты  вывода и настроек отображения.
3. Graph# - по факту WPF контроллер для отображения графов. Содержит несколько алгоритмов визуализации. 
4. NodeXL - вроде работает только с графами заданными через Excel.
5. QuickGraph - библиотека обеспечивающая мат. алгоритмы работы с графами. А также позволяет выводить графы через Glee, Graphiz. 

Решение.

Сначала разберемся с математикой. 

1. Добавляем QuickGraph в ссылки и включаем использование:
   
   using QuickGraph;
   using QuickGraph.Algorithms.ShortestPath;
   
2. Создаем граф. Так как переводчик единица универсальная - в том смысле, что, вообще говоря, переводить может в обоих направлениях, то создаем ненаправленный граф.
   
    UndirectedGraph<string, Edge<string>> languageGraph = null;
   
3. Пишем метод, для заполнения этого графа из файла. Предположим FillGraph();
4. Думаем над тем, какой нам нужен алгоритм. Мне нравится Дейкстра. Это ничем не обосновано, на самом деле.
   
   var a = new UndirectedDijkstraShortestPathAlgorithm<string, Edge<string>>(languageGraph, edgeCost);
   
5. Используем алгоритм:
   -  Назначаем ключевую вершину:
   
    a.SetRootVertex("Исландский");
   
   - Делаем расчет алгоритма: a.Compute(); Это по факту запускает алгоритм с заданным графом и настройками.
   - Получаем искомое: 
   
   if (a.TryGetDistance("Албанский", out path_length))               MessageBox.Show(path_length.ToString());
   else     
      MessageBox.Show("Что-то не так.");
   
6. Получаем правильный ответ. 

Визуализация  : to be continued. 

Сегодня ко мне пришел прекрасный человек проконсультироваться по базе данных.

Прекрасный человек оглядел рабочий монитор, тяжело вздохнул при виде моей RAD Studio 2010 и выдал установщик CnWizard.

Теперь мой делфи код не страшно открывать и можно читать. В нем теперь видно связки begin - end, легко смотреть где что и как используется...  а кнопочки в формах просто выравнивать.

Как солнцем осветили.

Informix, Logical Logs и onlog или как узнать кто испортил наши данные

Как бы ни было клево решать простые задачки из курса дискретной математики... Иногда надо работать.

3 вещи которые я узнала за сегодня:
1.  Информикс умеет (и ведет по умолчанию и, по ходу, помешать этому нельзя) вести логи транзакций. Называется эта штука Logical Logs.
Посмотреть их можно командой onlog. Главное - не пугаться вывода.
Вывод этой команды разнообразен и прекрасен. Поэтому: как интерпретировать записи логического журнала Informix. Там вообще рядом много всего интересного. Возможно позже напишу пример.
По умолчанию эти логи бекапятся вместе с базой.

2. Для ведения контролируемых логов изменения могут оказаться полезными ключевые SQL слова "CURRENT" и "USER". Первое вернет текущую дату-время, второе - юзера от которого был запрос.

Пример: INSERT INTO test (dt, username) VALUES (CURRENT, USER);

3. Интересное про аудит (т.е. учет) изменений данных и стуктуры БД: http://rsdn.ru/article/db/db_audit.xml.

Codestars. Track 03.

Задача

Немногие знают, что музы существуют на самом деле. Физики-музыковеды выяснили, что музы, как и люди, говорят на разных языках, но это не мешает им общаться. Так, в Секретном институте прикладного музыковедения ученые в ходе наблюдений получили текстовый файл, который в каждой строчке содержит два номера муз (разделенных пробелом), которые общаются друг с другом. Предполагается, что общаются друг с другом только те музы, которые говорят на одном языке, и что для каждой музы в файле есть запись (т.е. муз, которые ни с кем не общаются, не существует).

Узнай, сколько всего языков существует у муз.

Лирическое отступление.

Первый вопрос, который бросился в глаза и ввел меня в недоумение: "А одна муза может говорить только на одном языке? Или они полиглоты?.."
Для начала, предположу, что каждая муза говорит только на одном языке. Просто потому, что я понятия не имею как решать эту задачу в обратном случае.
Тогда, внутри каждого языка существует множество общающихся друг с другом муз. И нам надо найти, всего лишь, количество этих множеств.
Из предположения 1 муза - 1 язык есть два любопытных следствия:

1. Очевидное: множества общающихся муз между языками не пересекаются.
2. Общение понятие транзитивное, т.е. если муза 1 общается с музой 2, но ничего не сказано про общение 1 и 3, но известно, что муза 2 общается с музой 3, то и общение муз 1 и 3 теоретически возможно.

Бонус. Для простоты работы с множествами я буду считать, что общение - штука еще и рефлексивная. Т.е. для каждой музы справедливо, что она общается сама с собой. Ну или просто, что она личность творческая и хранит на первой строчке своей записной книжки свой собственный номер.

Решение.

Для начала я составлю список муз и их контактов.
Муза у нас уникальная и обозначается номером. Так как мне лень каждый раз при сравнении делать Convert.ToInt32() (а еще потому, что называть муз числами как-то грустно, и это могли бы быть имена...) то моя структура для хранения записных книжек муз выглядит так:

Dictionary<string, List<string>> Muses = new Dictionary<string, List<string>>();

В этом словаре ключом выступает имя музы, а в словарь я записываю ее контакты. Начиная с ее собственного.

Теперь у нас для каждой музы есть ее записная книжка. Чтобы узнать количество языков, надо сгруппировать муз, т.е. переписать муз одного языка в одну книжку. Пусть это будет книжка первый встреченной музы данной группы. Искать мы их будем транзитивно - по принципу того, что контакты моего контакта - мои контакты. Берем первую музу и ее контакты (множество М1), для каждого контакта с его контактами (Mi) добавляем различающиеся элементы M1 и Mi.

Как водится у меня есть велосипед (которые мне почему-то очень хочется писать) и адекватный (более менее, наверное) вариант работы с множествами в C#.

Велосипед выглядел как-то так:

for (int i = 0; i < Muses.Keys.Count; i++)
{
    string current_muse = Muses.Keys.ElementAt(i);

    for (int j = 1; j < Muses[current_muse].Count; j++)
    {
string contact_muse = Muses[current_muse][j];
        if (Muses.Keys.Contains(contact_muse))
{
           List<string> except_muses = new List<string>();

            foreach (string transit_muse in Muses[contact_muse])
           {
if (!Muses[current_muse].Contains(transit_muse))
                  Muses[current_muse].Add(transit_muse);  
           }

            Muses.Remove(contact_muse);
}
    }
}

Но где-то здесь надо остановиться. Все что нам на самом деле надо сделать описывается псевдокодом как-то так:

foreach (M1 in M)
{
    foreach (mi in M1)
    {
M1 = M1 + mi; //где "+" - это операция объединения множеств.
M.Remove(mi);
    }
}

Благодаря пространству имен System.Linq любая коллекция в C# поддерживает интерфейс IEnumarable<T>. А он вполне себе множество и имеет такие классные методы как Union, Intersect, Except, where... В общем позволяет вспомнить курс дискретной математики и применить его на практике. Так что мой псевдокод в итоге выглядит так:

for (int i = 0; i < Muses.Keys.Count; i++ )
{
    string current_muse = Muses.Keys.ElementAt(i);

    for (int j = 1; j < Muses[current_muse].Count; j++)
    {
string contact_muse = Muses[current_muse][j];
if (Muses.Keys.Contains(contact_muse))
{
          Muses[current_muse] = Muses[current_muse].Union(Muses[contact_muse]).ToList();
          Muses.Remove(contact_muse);
}
    }
}

Для самых внимательных: итератор foreach не позволяет изменять коллекцию в теле цикла. А мне нужно. Поэтому for.

Проверка на существование contact_muse нужна на случай, если мы записуню книжку этой музы уже обработали.

Вот собственно и все.
Картинка, музычка и проект. )

03_MuseLanguages

Download Muse Starlight for free from pleer.com

CodeStars. Track 02.

Задача

Случайно к тебе попало письмо с текстом будущего хита от твоего главного соперника за первое место в хит-парадах! Но, к сожалению, все сообщение оказалось закодированным. Твои помощники определили, что в песне используется два смысловых слова — Yo и Nice — причем, Nice означает конец очередной буквы, а количество предшествующих слов Yo определяет порядковый номер буквы в алфавите. Два подряд идущих слова Nice обозначают конец слова. В приведенном файле также содержатся другие слова-паразиты, которые не несут смысловой нагрузки, и бессмысленные знаки препинания (которые тем не менее используются для разделения слов). Расшифруй текст песни, содержащийся в файле. Если ты сделаешь все правильно, ты получишь текст только из букв и пробелов, без лишних пробелов и знаков препинания.

Решение

Что описывать в решении я не знаю... все очень просто. Но я попытаюсь.

У нас есть файл с кучей всяких слов. Которые нас не волнуют. Нас волнуют только две вещи:

• слово, которое встречаясь увеличивает порядковый код буквы в слове на единицу. Yo.
• слово "пробел" - разделитель слов. Nice. Когда оно встречается счетчик наших Yo обнуляется. 

Наша задача получить символы из которых состоит файл. Эти символы буквы (латинские) и пробелы (так сказано в задании). Каждому символу соответствует число Yo. Для пробела между словами число Yo будет равно нулю (ровно столько Yo мы насчитаем между двумя идущими подряд разделительями Nice). Если заглянуть в ASCII табличку то мы это и увидим. Сначала пробел, а потом маленькие латинские буковки от 'a' до 'z'. Значит значение аски-кода символа связано со значением счетчика с неким постоянным смещением (96 - можно вычислить по таблице). Значит, для вычисления буковки мы берем полученный счетчик и прибавляем к нему 96. И делаем Convert.ToChar(Counter);

Значит нам нужно два вложенный цикла.

Внешний ползет по нашему мусору от обеда до следующего Nice. Доползя запоминает позицию откуда начал и где остановился и передает их во внутренний цикл.

Внутренний цикл ползет по тексту между этими позициями и считает Yo. Доползает до конца, вычисляет буковку, добавляет ее в результат.

Все.

Картинка. Проект. И бонусная песня, которую мы "слямзили" своими нечеловеческими усилиями.

Cкачать I Don't Want To Miss A Thing бесплатно на pleer.com

02 CodeStars SongDecode Project

CodeStars. Track 01

http://contests.techdays.ru/codestars/

Задача. 
Твой первый клип не попадет в ротацию MTV, если ты не решишь эту задачу.

На съемках твоего первого клипа не обойтись без массовки — 106 симпатичных девушек разного роста, одетых в разноцветные костюмы. Но как их лучше разместить в кадре? Чтобы найти удачный ракурс, тебе придется попробовать все возможные расстановки для героинь твоего видео. Сколько часов потребуется на просмотр всех расстановок, если на просмотр одной расстановки требуется 10 секунд?

Предисловие.
Нам нужно количество перестановок в кадре различных девиц - значит, факториал. И умножить это значение на 10 - чтобы узнать общее время.
Поскольку 106! - это очень и очень много, надо сразу учесть, что в int и даже в longint это богатство не влезет. Поэтому нам нужно использовать длинную арифметику.

Ларчик открывался, на самом деле, невероятно просто. Примерно за 30 минут. Без извращений и попыток убить себя об стену.

Но я старый (как оказалось - ужасно) кодер и не знаю слов использования (using), поэтому вместо того, чтобы использовать гугл, я попробовала реализовать класс LongLongInt с нуля. Велосипед получился несовершенный, но ездил вполне исправно.

Однако, желание оттестировать его и сделать аккуратным и законченным привели меня к такой горе работы, что я испугалась... и... и правильно, стерла все нафиг. И пошла интересоваться у поисковиков как подобные, вполне типичные же, задачи, решали люди до меня.

Решение.

Если опустить мои четырехдневные мытарства с написанием собственного класса, то задача в рамках C# решается при помощи 10 строк с использованием пространства имен System.Numerics и  его типов BigInteger и Complex. Даже только при помощи первого.

Но чтобы за потраченное время было не так обидно, я расскажу про кнопочку.  Раз уж я теперь звезда электрокода, то надо раскрасить свой проект, так что пусть будет WPF: с кислотно-розовой рамочкой и с большой желтой кнопкой.

Для создания шаблона большой желтой кнопки были совмещены вот эти два источника:

1. http://www.codeproject.com/Articles/29733/PolyStar-WPF-Polygons-and-Stars
2. http://learnwpf.com/post/2009/04/26/Round-Gel-like-button-template-for-WPF.aspx

Предположим, это рабочая ссылка на архив с проектиком (первый раз пытаюсь осознанно использовать гугл-диск:

https://drive.google.com/file/d/0B3glcJhPYpYQX2RNeEw3SGNYLU0/view?usp=sharing

Ну и еще, раз уж такая тема, пусть здесь будет музычка, под которую все началось.

Загадка )

Дано:
string MyNum = "1";

Вопрос:
Convert.ToInt32(MyNum[0]) == ?

Ответ и пояснение под катом. )

Дано:

 - Два поля ввода исходных данных.

 - Кнопка, для осуществления по ним расчета.

 - Три поля вывода результата.

Требуется:

 - Реализовать проверки введенных данных перед расчетами.

Пусть данные на форме перед расчетами проверяются методом ValidateData(). 

У меня есть два быстро приходящих в голову способа реализовать этот метод:

void ValidateData

{

     try

     {

         Convert.ToInt32(this.GirlsCountTB.Text);

     } catch { ... }

     ....

}

Но вообще, try - catch это долго и неэффективно - раз.

Мне в любом случае придется делать эту конвертацию впоследствии, при переходе к расчетам - два. Поэтому второй вариант:

void ValidateData

{

    int girls = 0;

    if (!Int32.TryParse(this.GirlsCountTB.Text, out girls)) { ... }

}

Это уже по-человечески, но куда мне деть результат? Можно вернуть, но у меня здесь два поля, которые надо проверить. А если их будет 10? Можно создать и заполнить словарь. И на этом я бы и остановилась и тогда поста бы не было. Но... Тем временем, коллега на обеде рекомендует мне третий вариант. 

"А как же дзен обработки ввода? Используй событие TextChanged." Идея кажется мне неплохой... 

      -  И... в момент события TextChanged отображение изменения уже произошло. Отменять действие уже поздно.

      -  В списке есть TextInput, но интернет мне услужливо сообщает, что это событие блокируется элементом TextBox. 

      -  Зато есть PreviewTextInput. Оно не блокируется, позволяет отменить ввод...  в общем все прекрасно. Но есть нюанс: это событие не генерируется при нажатии пробела. Пробел нам предлагают обрабатывать дополнительно через KeyDown. 

И в итоге тогда обработка данных происходит в трех местах:

1. PreviewTextInput
2. KeyDown
3. ValidateData (потому что если ни одно из событий не произошло поле остается пустым... и не валидным. И нам надо об этом знать).

В общем идея с событиями мне кажется несостоятельной. Странно?..

Не очень, WPF подразумевает активное, судя по всему даже повсеместное, использование привязок. В этом случае ввод проверяется на уровне объекта, вместе с бизнес-логикой. И все эти события ввода с клавиатуры нам не нужны. 

Но пока у меня в архитектуре нет сформированных объектов, хотя, подозреваю, они еще будут, но пока это будет выглядеть так:

private bool ValidateData()

{

    List<string> errors = new List<string>();

    int girls = 0;

    double timeForOne = 1.0;

    if (this.GirlsCountTB.Text == "")

       errors.Add("Не задан размер массовки.");

                        

    if (!Int32.TryParse(this.GirlsCountTB.Text, out girls))

       errors.Add("Некорректное число массовщиц.");

    if (this.OneVarTimeTB.Text == "")

       errors.Add("Не задано время на проработку одного варианта.");

    if (!Double.TryParse(this.OneVarTimeTB.Text, out timeForOne))

       errors.Add("Некорректное время обработки одного варианта");

    ShowErrorMsg(errors);

    return (errors.Count == 0);

}

Использованные материалы по теме:

http://samorazvitie.net/book/80-osnovy-proektir-interfejsov-s-ispolzovaniem-texnologii-windows-presentation-foundation-shamshev-a/36-55-sobytiya-wpf.html

После прочтения 50 оттенков серого и двух рабочих дней в попытках разобраться и привести в порядок код на Delphi годовой давности, фраза "легкий рефакторинг" - определенно звучит как что-то непристойное и многообещающее.