вторник, 10 мая 2011 г.

Решаем Google CodeJam по другому.

Здравствуйте читатели.

Сегодня хотел поговорить на тему различия в написании программ на олимпиадах и на проектах, или как я их называю: "Олимпиадный" и "Корпоративный" стили. У каждого из них есть как свои плюсы так и минусы. Я не говорю, что я владею ими достаточно глубоко, но различия постараюсь продемонстрировать ниже, а заодно и рассказать о том, как понять некоторые паттерны проектирования на простых задачах. Очень редко появляется возможность найти неплохой пример для демонстрации того или иного подхода.


Немного конкретики.

Задача: Magicka.

Для тех кому лень переводить: есть последовательность символов (элементов), и есть несколько преобразований при добавлении очередного символа. Существует два преобразования: 1) если новый и предыдущий символ описаны как преобразуемые, то они удаляются и вместо них ставиться определенный; 2) если новый символ не сопоставим с любым из последовательности - вся последовательность, включая новый символ, уничтожается. Нужно найти конечное состояние последовательности если известны наборы преобразований, уничтожений и последовательность добавления символов.

Решение: симуляция.

А теперь почему я выбрал именно эту задачу. Если мы посмотрим на любое бизнес приложение, то это почти полная симуляция (автоматизация) какого-либо набора действий. Чем наша задача не набор действий?

Вариант решения Олимпиадный:

private void Solve()
{
    string res = string.Empty;
    var e = new Dictionary();

    int i = 0;
    char last = '#';
    while (i<_query.Length)
    {
        char next = _query[i];
        if (last != '#')
        {
            if (_combine.ContainsKey(next)
                && _combine[next].ContainsKey(last))
            {
                next = _combine[next][last];
                res = res.Remove(res.Length - 1);

                e[last]--;
                if (e[last] == 0)
                    e.Remove(last);
            }

            bool doClear = false;
            var t = e.Keys.ToArray();
            for (int j = 0; j < t.Length; j++)
            {
                if (_opposed.ContainsKey(next)
                    && _opposed[next].Contains(t[j]))
                {
                    doClear = true;
                    break;
                }
            }

            if (doClear)
            {
                res = string.Empty;
                e.Clear();
                next = '#';
                last = next;
                i++;
                continue;
            }
        }

        res += next;
        if (!e.ContainsKey(next))
            e[next] = 1;
        else
            e[next]++;

        last = next;
        i++;
    }

    _result[_num] = res;
}

Что же тут хорошего: Во первых не много текста, все рядом, да и вообще если смотреть на это чудо минут 10-15 то, примерно, понимаешь как оно работает.
Что тут плохого: Данный стиль, лично мне, напоминает язык perl: write only, написал, а через пару дней уже не понимаешь как ты к этому пришел и как сюда внести изменения.

Из вышеизложенных пунктов можно понять, почему некоторые компании с недоверием смотрят в сторону олимпиадников.

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

Сущности.

В задаче присутствуют такие понятия как:

  • Стэк/очередь/список/массив символов: 
    • Добавляем новый символ
    • Достаем последний символ
    • Достаем два последних символа
    • Множество уникальных символов
    • Количество каждого символа в стеке
    • Очистка результата
  • Волшебная очередь:
    • Добавляем новый символ
    • Проверки
      • Трансформация двух последних в один новый
      • Несовместимые символы и очистка результата
  • Конфигурация очереди
    • Добавление комбинаций и условия уничтожения
    • Проверка комбинаций
    • Проверка условия уничтожения
    • Колдун
      • Получает строку и посимвольно вызывает элементы.

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

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

    internal interface IMagicQueue
    {
        void AddElement(char c);
    }
    
    internal interface IMagicMan
    {
        void InvokeElements(string items);
    }
    
    internal class MagicMan : IMagicMan
    {
        private readonly IMagicQueue _q;
    
        public MagicMan(IMagicQueue q)
        {
            _q = q;
        }
    
        public void InvokeElements(string items)
        {
            foreach (var c in items)
            {
                _q.AddElement(c);
            }
        }
    }
    

    Ничего сложного. Имеем интерфейс магической очереди, интерфейс колдуна. Через конструктор передаем колдуну, с чем ему работать. А в методе InvokeElements передаем последовательность элементов которые этот колдун и вызывает.

    Продолжим.

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

    Например: нужно сформировать отчет в нескольких вариантах: XML, TXT, HTML. Отчет содержит заголовок, данные и нижнюю часть документа (график). Так вот, билдер будет выглядеть следующим образом:

    using System;
    using System.Collections.Generic;
    using System.Text;
    
    /// <summary>
    /// Данные для отчета
    /// </summary>
    internal interface IReportData
    {
        /// <summary>
        /// Отчетный период
        /// </summary>
        int Year { get; }
    
        /// <summary>
        /// Доход компании
        /// </summary>
        decimal Profit { get; }
    }
    
    /// <summary>
    /// Интерфейс построителя
    /// </summary>
    interface IReportBuilder
    {
        void BuildHeader(string companyName);
        void BuildData(List<IReportData> data);
        void BuildChart(List<IReportData> chartData);
        string GetResult();
    }
    
    /// <summary>
    /// Реализация построителя текстового отчета
    /// </summary>
    internal class TextReportBuilder : IReportBuilder
    {
        private readonly StringBuilder _result = new StringBuilder();
    
        public void BuildHeader(string companyName)
        {
            _result.AppendFormat("Report for {0}\n", companyName);
        }
    
        public void BuildData(List<IReportData> data)
        {
            foreach (var reportData in data)
            {
                _result.AppendFormat("Year {0}, profit: ${1}\n", reportData.Year, reportData.Profit);
            }
        }
    
        public void BuildChart(List<IReportData> chartData)
        {
            _result.AppendFormat("Generated time:" + DateTime.Now);
        }
    
        public string GetResult()
        {
            return _result.ToString();
        }
    }
    
    /// <summary>
    /// Директор
    /// </summary>
    class Director
    {
        private readonly IReportBuilder _builder;
    
        /// <summary>
        /// Создание директора на основе построителя
        /// </summary>
        /// <param name="builder">Построитель</param>
        public Director(IReportBuilder builder)
        {
            _builder = builder;
        }
    
        /// <summary>
        /// Постройка отчета
        /// </summary>
        /// <param name="companyName">Имя компании</param>
        /// <param name="data">Данные для отчета</param>
        public void BuildGlobalReport(string companyName, List<IReportData> data)
        {
            // Строим отчет не зависимо от конкретной реализации построителя отчетов.
    
            _builder.BuildHeader(companyName);
            _builder.BuildData(data);
            _builder.BuildChart(data);
        }
    }
    
    class Source
    {
        public void ReportButtonClick()
        {
            // Пользователь кликнул по кнопке генерации отчета.
    
            // Создаем построитель
            IReportBuilder builder = new TextReportBuilder();
    
            // Директора
            Director director = new Director(builder);
    
            // Строим отчет
            director.BuildGlobalReport("KudInc", GetFullReport());
    
            // Получаем отчет.
            string result = builder.GetResult();
        }
    
        private List<IReportData> GetFullReport()
        {
            var result = new List<IReportData>();
    
    
            return result;
        }
    }
    

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

    internal interface ISimpleQueue
    {
        void AddElement(char element);
        void RemoveElement();
        void Clear();
    
        int Length { get; }
        string Result { get; }
    
        char LastItem { get; }
        char[] TwoLatestItems { get; }
        IEnumerable<char> UniqueItems { get; }
    }
    

    Наша простая очередь должна выполнять примитивные действия с элементами: Добавлять элемент в конец, Удалять последний, Очищаться, возвращать количество элементов, Возвращать текущее состояние, Возвращать последний элемент, Возвращать два последних элемента и возвращать все уникальные элементы которые в ней есть. На основании этого мы можем решить нашу задачу вынеся реализацию по объеденению и уничтожению элементов на уровень Магической очереди.

    Реализуем простую очередь:
    internal class SimpleQueue : ISimpleQueue
    {
        /// <summary>
        /// Count of each elements.
        /// </summary>
        private readonly int[] _available;
    
        /// <summary>
        /// Set of unique elements.
        /// </summary>
        private readonly HashSet<char> _history;
    
        /// <summary>
        /// Current queue state.
        /// </summary>
        private readonly StringBuilder _queue;
    
        /// <summary>
        /// Create new instance of SimpleQueue with default values.
        /// </summary>
        public SimpleQueue()
        {
            _available = new int[255];
            _history = new HashSet<char>();
            _queue = new StringBuilder();
        }
    
        /// <summary>
        /// Current queue state.
        /// </summary>
        public string Result
        {
            get { return _queue.ToString(); }
        }
    
        /// <summary>
        /// Current queue length.
        /// </summary>
        public int Length
        {
            get { return _queue.Length; }
        }
    
        /// <summary>
        /// Remove last element from the queue.
        /// </summary>
        public void RemoveElement()
        {
            var l = _queue.Length;
            var c = _queue[l - 1];
            _queue.Remove(l - 1, 1);
            _available[c]--;
            if (_available[c] == 0)
                _history.Remove(c);
        }
    
        /// <summary>
        /// Add new element to the end of the queue.
        /// </summary>
        /// <param name="element">Element that should be added.</param>
        public void AddElement(char element)
        {
            // append element to end of queue
            _queue.Append(element);
    
            // increase count of elements
            _available[element]++;
    
            // add element to unique set of elements
            if (_available[element] == 1)
                _history.Add(element);
        }
    
        /// <summary>
        /// Clear current queue state.
        /// </summary>
        public void Clear()
        {
            // clear queue.
            _queue.Clear();
    
            // clear element counters.
            Array.Clear(_available, 0, _available.Length);
    
            // clear unique elements set.
            _history.Clear();
        }
    
        /// <summary>
        /// Last queue element.
        /// </summary>
        public char LastItem
        {
            get { return _queue[_queue.Length - 1]; }
        }
    
        /// <summary>
        /// Two latest items in the queue.
        /// </summary>
        public char[] TwoLatestItems
        {
            get { return new[] { _queue[_queue.Length - 2], _queue[_queue.Length - 1] }; }
        }
    
        /// <summary>
        /// Unique elements that present in the queue.
        /// </summary>
        public IEnumerable<char> UniqueItems
        {
            get { return _history; }
        }
    
    }
    

    Таким образом, у нас получилась следующая зависимость: Маг зависит от магической очереди, которая зависит от простой очереди.

    Приблизительный алгоритм работы следующий:

    1. Маг колдует новый элемент и отправляет магической очереди на обработку
    2. Магическая очередь добавляет данный элемент в конец просто очереди
    3. Магическая очередь осуществляет проверку с использованием конфигурации на наличие преобразования и уничтожения.

    Так же нужно выделить дополнительную сущность, как конфигурация магической очереди:

    internal interface IMagicQueueConfiguration
    {
        /// <summary>
        /// Checking for opposing.
        /// </summary>
        /// <param name="a">First element.</param>
        /// <param name="b">Second element.</param>
        /// <returns>True when these elements is opposed, or false when not.</returns>
        bool IsOpposed(char a, char b);
    
        /// <summary>
        /// Get combination rule. Zero when no combination is available.
        /// </summary>
        /// <param name="a">First element.</param>
        /// <param name="b">Second element.</param>
        /// <returns>Result of a combination of these elements.</returns>
        char GetCombine(char a, char b);
    }
    
    internal class MagicQueueConfiguration : IMagicQueueConfiguration
    {
        /// <summary>
        /// Combination matrix.
        /// </summary>
        protected readonly char[,] Combine = new char[255, 255];
    
        /// <summary>
        /// Opposed matrix.
        /// </summary>
        protected readonly bool[,] Opposed = new bool[255, 255];
    
        /// <summary>
        /// Create new combination rule.
        /// </summary>
        /// <param name="a">First element.</param>
        /// <param name="b">Second element.</param>
        /// <param name="result">Combination result.</param>
        public void AddCombine(char a, char b, char result)
        {
            Combine[a, b] = result;
            Combine[b, a] = result;
        }
    
        /// <summary>
        /// Create new opposing rule.
        /// </summary>
        /// <param name="a">First element.</param>
        /// <param name="b">Second element.</param>
        public void AddOpposed(char a, char b)
        {
            Opposed[a, b] = true;
            Opposed[b, a] = true;
        }
    
        /// <summary>
        /// Checking for opposing.
        /// </summary>
        /// <param name="a">First element.</param>
        /// <param name="b">Second element.</param>
        /// <returns>True when these elements is opposed, or false when not.</returns>
        public bool IsOpposed(char a, char b)
        {
            return Opposed[a, b];
        }
    
        /// <summary>
        /// Get combination rule. Zero when no combination is available.
        /// </summary>
        /// <param name="a">First element.</param>
        /// <param name="b">Second element.</param>
        /// <returns>Result of a combination of these elements.</returns>
        public char GetCombine(char a, char b)
        {
            return Combine[a, b];
        }
    }
    

    Продолжаем. На данном этапе реализуем базовый процесс добавления элемента в магическую очередь используя "Шаблонный метод":
    /// <summary>
    /// Base magic queue.
    /// </summary>
    internal abstract class BaseMagicQueue : IMagicQueue
    {
        /// <summary>
        /// Result storage.
        /// </summary>
        protected ISimpleQueue Sq;
    
        /// <summary>
        /// Configuration provider.
        /// </summary>
        protected IMagicQueueConfiguration Qc;
    
        /// <summary>
        /// Create new instance nased on result storage and configuration provider.
        /// </summary>
        /// <param name="sq">Storage result.</param>
        /// <param name="qc">Configuration provider.</param>
        protected BaseMagicQueue(ISimpleQueue sq, IMagicQueueConfiguration qc)
        {
            Qc = qc;
            Sq = sq;
        }
            
        #region Abstract methods
    
        public abstract void Oppose();
        public abstract void Combine();
    
        #endregion
    
        /// <summary>
        /// Create new element and process comination and opposing.
        /// </summary>
        /// <param name="c">New element value</param>
        public void AddElement(char c)
        {
            Sq.AddElement(c);
            Combine();
            Oppose();
        }
    }
    

    Далее реализуем сам механизм комбинирования и уничтожения очереди:
    /// <summary>
    /// Magic queue with Oppose and Combine implementation.
    /// </summary>
    internal class MagicQueue : BaseMagicQueue
    {
        /// <summary>
        /// Create new instance nased on result storage and configuration provider.
        /// </summary>
        /// <param name="sq">Storage result.</param>
        /// <param name="qc">Configuration provider.</param>
        public MagicQueue(ISimpleQueue sq, IMagicQueueConfiguration qc) : base(sq, qc)
        {
        }
    
        /// <summary>
        /// Oppose queue.
        /// </summary>
        public override void Oppose()
        {
            if (Sq.Length < 2)
                return;
    
            var c = Sq.LastItem;
            foreach (char item in Sq.UniqueItems)
            {
                if (Qc.IsOpposed(item, c))
                {
                    Sq.Clear();
    
                    return;
                }
            }
        }
    
        /// <summary>
        /// Combine queue.
        /// </summary>
        public override void Combine()
        {
            if (Sq.Length < 2)
                return;
    
            char[] items = Sq.TwoLatestItems;
    
            var t = Qc.GetCombine(items[0], items[1]);
            if (t != 0)
            {
                Sq.RemoveElement();
                Sq.RemoveElement();
                Sq.AddElement(t);
            }
        }
    
    }
    

    Ну и наконец, осталось самое простое: пример использования данного чуда.
    Создаем обычную очередь, создаем конфигурацию, создаем магическую очередь на основе конфигурации и простой очереди, создаем мага на основе магической очереди, настраиваем конфигурацию, даем магу указания, забираем результат из простой очереди.

    class Program
    {
        public static void Main(string[] args)
        {
            // Create simple queue.
            var simpleQueue = new SimpleQueue();
    
            // Create queue configurator.
            var queueConfiguration = new MagicQueueConfiguration();
    
            // Create magic queue mased on configurator and simple queue.
            var queue = new MagicQueue(simpleQueue, queueConfiguration);
    
            // Create new magic man.
            var magicMan = new MagicMan(queue);
    
            // Configure queue.
            // Q+F traslated into T
            queueConfiguration.AddCombine('Q', 'F', 'T');
    
            // Q&F will clear the queue.
            queueConfiguration.AddOpposed('Q', 'F');
    
            // Do magic.
            magicMan.InvokeElements("FAQFDFQ");
    
            // Take result.
            var res = simpleQueue.Result;
    
            Console.WriteLine(res);
        }
    }
    

    И напоследок общая картина как оно работает в виде сиквенс диаграммы (кликабельно):


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

    PS: Назвать стэк очередью была плохой идеей, но надеюсь вы не в обиде. :)

    Спасибо за внимание.

    3 комментария:

    1. Дружище, ты в олимпик солюшене ОДНИМ ридером читаешь файл параллельно в разных потоках без синхронизации вообще? Экстремал ты :) Или операция StreamReader.ReadLine синхронизирована унутре?

      ОтветитьУдалить
    2. Для начала я не читаю много поточно.

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

      for (int i=0;i<n;i++)
      {
      var t = new TaskB(r, i); -- читаю данные

      запускю задачу:
      var task = Task.Factory.StartNew(t.Solve);

      bg[i] = task;
      }

      ОтветитьУдалить