Решаем 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: Назвать стэк очередью была плохой идеей, но надеюсь вы не в обиде. :)

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