Триплетным называется число (или цифровая строка), которое можно полностью свернуть до пустой строки путем последовательного удаления троек соседних одинаковых цифр. Например, последовательность 125577752211 преобразуется следующим образом: 125577752211 -> 125552211 -> 122211 -> 111 -> "". Рассмотрим, как эффективно решить эту задачу на платформе 1С:Предприятие при работе с последовательностями произвольной длины.
Прежде чем приступать к полному обходу строки, выясним особенности платформы 1С и базовые свойства задачи, позволяющие отсечь заведомо невалидные варианты:
Число имеет максимальную разрядность 38 знаков. Математические операции деления (/ 10) и взятия остатка (% 10) неприменимы для длинных последовательностей (сотни и тысячи знаков), поэтому входные данные необходимо обрабатывать как тип Строка.СтрДлина(ВходнаяСтрока) % 3 <> 0, строка гарантированно не является триплетом.Разберем самый декларативный способ решения — использование встроенного механизма регулярных выражений 1С (функция СтрНайтиВсеПоРегулярномуВыражению). Идея заключается в циклическом поиске и удалении подстроки вида (\d)\1\1, пока вхождения не перестанут находиться.
Посмотрим на пример кода:
&НаСервере
Функция ЧислоТриподРегулярка(Знач ВходнаяСтрока) Экспорт
Если СтрДлина(ВходнаяСтрока) % 3 <> 0 Тогда
Возврат Ложь;
КонецЕсли;
ШаблонПоиска = "(\d)\1\1";
Пока Истина Цикл
Вхождения = СтрНайтиВсеПоРегулярномуВыражению(ВходнаяСтрока, ШаблонПоиска, Истина);
Если Вхождения.Количество() = 0 Тогда
Прервать;
КонецЕсли;
Для Каждого Запись Из Вхождения Цикл
ВходнаяСтрока = СтрЗаменить(ВходнаяСтрока, Запись.Значение, "");
КонецЦикла;
КонецЦикла;
Возврат ПустаяСтрока(ВходнаяСтрока);
КонецФункции
Оценка метода: Способ компактен и нагляден, однако на больших строках (от 10 000 символов) показывает крайне низкую производительность из-за повторных полных проходов регулярного выражения и частых операций перевыделения памяти при вызове СтрЗаменить.
Проанализируем алгоритм прямого прохода по строке. Мы перемещаемся слева направо. Как только обнаружены три одинаковых символа подряд, мы удаляем их и смещаем текущий указатель позиции на два шага назад. Это необходимо, так как схлопывание тройки могло объединить ранее разделенные одинаковые цифры.
Рассмотрим реализацию данного подхода:
&НаСервере
Функция ПроверитьСдвигомНазад(ЧислоСтрокой) Экспорт
Если СтрДлина(ЧислоСтрокой) % 3 <> 0 Тогда
Возврат Ложь;
КонецЕсли;
КопияЧисла = ЧислоСтрокой;
Поз = 1;
Пока Истина Цикл
ДлинаОстатка = СтрДлина(КопияЧисла);
Если ДлинаОстатка = 0 Тогда
Возврат Истина;
КонецЕсли;
Если Поз > ДлинаОстатка - 2 Тогда
Возврат Ложь;
КонецЕсли;
Символ1 = Сред(КопияЧисла, Поз, 1);
Символ2 = Сред(КопияЧисла, Поз + 1, 1);
Символ3 = Сред(КопияЧисла, Поз + 2, 1);
Если Символ1 = Символ2 И Символ1 = Символ3 Тогда
КопияЧисла = Лев(КопияЧисла, Поз - 1) + Сред(КопияЧисла, Поз + 3);
Поз = Поз - 2;
Если Поз < 1 Тогда
Поз = 1;
КонецЕсли;
Иначе
Поз = Поз + 1;
КонецЕсли;
КонецЦикла;
КонецФункции
Посмотрим на более быстрый алгоритм, работающий по принципу стека, сформированного в обычной строковой переменной Приемник. По мере чтения символов проверяется переменная Хвост, хранящая два последних добавленных знака. Если текущий символ совпадает с ними, хвост отсекается (происходит схлопывание), иначе символ добавляется в конец.
Разберем код реализации:
&НаСервере
Функция ПроверитьСтроковымСтеком(СтрокаЧисла) Экспорт
Если СтрДлина(СтрокаЧисла) % 3 <> 0 Тогда
Возврат Ложь;
КонецЕсли;
Приемник = "";
Хвост = "";
ДлинаПриемника = 0;
Для Поз = 1 По СтрДлина(СтрокаЧисла) Цикл
Символ = Сред(СтрокаЧисла, Поз, 1);
Если Хвост = Символ + Символ Тогда
Приемник = Лев(Приемник, ДлинаПриемника - 2);
Хвост = Прав(Приемник, 2);
ДлинаПриемника = ДлинаПриемника - 2;
Иначе
Приемник = Приемник + Символ;
Хвост = Прав(Хвост, 1) + Символ;
ДлинаПриемника = ДлинаПриемника + 1;
КонецЕсли;
КонецЦикла;
Возврат (Приемник = "");
КонецФункции
Выясним, какой способ является самым производительным в 1С. Поскольку строки в платформе 1С неизменяемы (immutable) и любая конкатенация или вызов Лев() выделяет новый блок памяти, строковые стеки замедляются на больших объемах. Наилучшую скорость дает классический стек на базе объекта Массив с предварительно добавленными заглушками, исключающими постоянную проверку границ коллекции.
Рассмотрим по шагам реализацию самого быстрого алгоритма:
&НаСервере
Функция ПроверитьТриплетМассивом(СтрокаЧисла) Экспорт
Если СтрДлина(СтрокаЧисла) % 3 <> 0 Тогда
Возврат Ложь;
КонецЕсли;
Стек = Новый Массив;
// Добавляем две служебные заглушки для безопасного обращения по индексам (Размер - 1)
Стек.Добавить("");
Стек.Добавить("");
Размер = 1; // Указывает на верхний значимый элемент в стеке
Для Поз = 1 По СтрДлина(СтрокаЧисла) Цикл
Символ = Сред(СтрокаЧисла, Поз, 1);
Если Стек[Размер] = Символ И Стек[Размер - 1] = Символ Тогда
// Найдена тройка: удаляем два предыдущих символа с вершины стека
Стек.Удалить(Размер);
Стек.Удалить(Размер - 1);
Размер = Размер - 2;
Иначе
// Тройки нет: помещаем текущий символ в стек
Стек.Добавить(Символ);
Размер = Размер + 1;
КонецЕсли;
КонецЦикла;
// Если в стеке остались только две начальные заглушки, число полностью схлопнулось
Возврат (Стек.Количество() = 2);
КонецФункции
Для замера скорости и проверки корректности алгоритмов построим генератор триплетных строк заданной длины:
&НаСервере
Функция СгенерироватьТестовыйТриплет(КоличествоТроек) Экспорт
ГСЧ = Новый ГенераторСлучайныхЧисел;
НачалоСтроки = "";
КонецСтроки = "";
Для Итератор = 1 По КоличествоТроек Цикл
СлучайнаяЦифра = Строка(ГСЧ.СлучайноеЧисло(0, 9));
СчетчикСлева = ГСЧ.СлучайноеЧисло(1, 3);
Для Шаг = 1 По СчетчикСлева Цикл
НачалоСтроки = НачалоСтроки + СлучайнаяЦифра;
КонецЦикла;
Для Шаг = 1 По (3 - СчетчикСлева) Цикл
КонецСтроки = СлучайнаяЦифра + КонецСтроки;
КонецЦикла;
КонецЦикла;
Возврат НачалоСтроки + КонецСтроки;
КонецФункции
Итог: Для небольших чисел подходят строковые методы, однако при обработке длинных последовательностей (от десятков тысяч знаков) рекомендуется использовать Вариант 4 (Стек на базе массива) с предварительной проверкой кратности длины строки.