Не знаю, насколько правильно выглядит сам заголовок, но подробнее опишу здесь.
Итак, суть такова: есть, к примеру, некий диапазон и пара условий:
$start и $end всегда имеют одинаковую символьную длину (хотя это и не столь важно);
И если есть диапазон, включающий в себя элемент 555123456 (длина 9 символов), то нет никакого другого диапазона, который включал бы в себя номер, превосходящий по длине уже имеющийся и начинающийся с 555 - т.е. номер 5551234567 (длина - 10 символов) не существует по определению.
Последние цифры в $start и $end равняются 0 и 9 соответственно, что тоже облегчает задачу.
Т.е. (здесь и далее пишу условно, без привязки к каким-либо языку программирования или стандарту regexp)
555000000 - 555999999 // Т.е. 555*
666000000 - 666999999 // Т.е. 666*
5550000000 - 5559999999 // Не существует в списке диапазонов по определению задачи, игнорируем.
6660000000 - 6669999999 // Не существует в списке диапазонов по определению задачи, игнорируем.
Иными словами: если задан 555000000 - 555999999, то нет 5550000000 - 5559999999
Возьмем, например
555000000 - 555999999
Задача: преобразовать в 555*. С указанным примером разобраться несложно - необходимо отнять $start от $end, чтобы получить некую переменную $result, которая равна 999999. Затем использовать значение результата операции $result.length() по отношению к, скажем, $start, чтобы получить строку 555*
$shortrec = substr($start,0,-strlen($result)) . "*";
Но если диапазон выглядит как
777120000 - 777259999
то разница будет иметь значение 139999. Здесь сложнее, но тоже понятно - помимо отчасти указанного выше, сравниваем позиции 0 и 9 в обеих переменных, "выходим" на 12 и дополнительно обрабатываем 12, наращивая его 13 раз и получая в цикле следующую последовательность:
77712*
77713*
77714*
...
77725*
Но как быть, если есть диапазон,
888125120 - 888959599
(здесь вспомним облегчающее логику условие номер 3, чтобы не оперировать выражением типа [5-9], если бы $start равнялся бы 888125125) для которого необходимо получить
88812512*
8882*
8883*
...
8888*
88890*
88891*
88892*
...
88894*
888950*
888951*
888952*
...
888958*
8889590*
8889591*
8889592*
...
8889595*
Прошу рассудить - следую ли я с самого начала правильной логике или нет?
И есть ли некоторое универсальное решение (алгоритм) для подобных задач?
Как поступили бы вы?
P.S. Язык программирования не важен - важен сам подход и алгоритм. Надеюсь, не сломал читающему мозг, но задача не из учебных, а самая что ни на есть настоящая. Так что если есть идеи, буду весьма признателен.
Ответ
Писать алгоритм генерации будем для частного случая - когда число знаков у нижней и верхней границы одинаковы. Если же число знаков разное, то исходный диапазон будет разбит на 3 диапазона:
от минимальной границы до максимального числа с таким же числом цифр
все полные диапазоны чисел, которые не были затронуты границами
от минимального числа с таким же числом цифр, как у максимальной границы, до максимальной границы
На примере понятнее, что все это обозначает. Исходный диапазон 14-123456 разбиваем на три диапазона 14-99, 100-99999, 100000-123456
Если присутствует второй диапазон, то он задается простым выражением \d{n,m}, первый и второй диапазон нужно генерировать отдельно и в границах этих диапазонов всегда одинаковое количество знаков, а значит применим основной алгоритм генерации, а затем объединим эти 3 диапазона альтернативой.
Основной алгоритм для диапазонов с одинаковым количеством цифр
Попытаемся найти общую часть для верхней и нижней границы. Например в диапазоне 1234-1278 можно вынести 12 как обычные символы.
Начнем просмотр границ слева-направо. Для примера диапазон 1234-5678
Первые цифры нижней и верхней границ 1 и 5, поэтому разделим на 3 диапазона: 1234-1999, 2000-4999, 5000-5678, то есть как бы выделим середину, которую можно представить как [2-4]\d{3}
Оставшиеся два диапазона обработаем по тому же самому алгоритму. Например для 1234-1999 сперва вынесем цифру 1 как общую. Диапазон 234-999 разобьем на 2 диапазона 234-299, 300-999
И так далее для всех диапазонов, которые появятся в ходе разбиения на составные диапазоны.
Кода безумно много, но зато можно запустить и потестировать.
$( document ).ready( function() {
$( "#rangeLeft, #rangeRight" ).keydown( function() {
clearDisplay();
} );
$( "#run" ).click( function() {
clearDisplay();
var rangeLeft = $( "#rangeLeft" ).val();
var rangeRight = $( "#rangeRight" ).val();
if ( ! checkRanges( rangeLeft, rangeRight ) ) return;
$( "#result" ).append( generateFullRegExp(rangeLeft, rangeRight)+"
" );
$( "#test" ).show();
} );
$( "#test" ).click( function() {
var rangeLeft = $( "#rangeLeft" ).val();
var rangeRight = $( "#rangeRight" ).val();
var re = new RegExp( "^"+generateFullRegExp(rangeLeft, rangeRight)+"$" );
for( var i=Math.pow( 10, rangeLeft.length-1 ); i
" );
if ( !re.test( i+"" ) && ( i>parseInt(rangeLeft) && i
" );
} );
} );
function checkRanges( rangeLeft, rangeRight ) {
if ( /\D/.test( rangeLeft ) || /\D/.test( rangeRight ) ) {
$( "#result" ).append( "Введите два числа
" );
return false;
};
rangeLeft = parseInt( rangeLeft );
rangeRight = parseInt( rangeRight );
if ( isNaN( rangeLeft ) || isNaN( rangeRight ) ) $( "#result" ).append( "Не указаны границы диапазонов
" );
if ( rangeLeft < 0 ) $( "#result" ).append( "Левая граница меньше 0
" );
if ( rangeRight < 0 ) $( "#result" ).append( "Правая граница меньше 0
" );
if ( rangeLeft > rangeRight ) $( "#result" ).append( "Левая граница больше правой границы
" );
return( !(
rangeLeft < 0 ||
rangeRight < 0 ||
rangeLeft > rangeRight ||
isNaN( rangeLeft ) ||
isNaN( rangeRight )
) );
};
function maxBeginStr( str1, str2 ) {
var res = /^(.*)[^-]*\-\1/.exec( str1 + "-" + str2 );
return res ? res[1] : "";
};
function midDiap( start, end ){
var st0int = parseInt( start[0] );
var en0int = parseInt( end[0] );
if ( st0int+1 == en0int ) {
var res = end[0];
} else {
if ( st0int == en0int-2 ) {
res=( st0int+1 )+"";
} else {
res="["+( st0int+1 )+"-"+(en0int-1)+"]";
};
};
if ( start.length == 1 ) return res;
return res+"\\d{"+(start.length-1)+"}";
};
function lowDiap( num, pos ) {
var res = num.substr(0, pos);
var highRange = parseInt( num[pos] )-1;
if ( highRange == -1 && pos == num.length-1 ) return num;
if ( highRange == -1 ) return null; // выражение можно не включать
if ( pos == num.length-1 ) highRange++;
res += "[0-"+highRange+"]";
if ( num.length != pos+1 ){
res += "\\d{"+(num.length-pos-1)+"}";
}
return res;
};
function highDiap( num, pos ) {
var res = num.substr(0, pos);
var lowRange = parseInt( num[pos] )+1;
if ( lowRange==10 && pos == num.length-1 ) return num;
if ( lowRange==10 ) return null; // выражение можно не включать
if ( pos == num.length-1 ) lowRange--;
res += "["+lowRange+"-9]";
if ( num.length != pos+1 ){
res += "\\d{"+( num.length -pos-1)+"}";
}
return res;
};
function getRegExp( start, end ) {
if ( start.length != end.length ) return "Invalid input";
var res= maxBeginStr( start, end );
start= start.substr( res.length );
end = end.substr( res.length );
if ( start.length == 0 ) return res;
var st0int = parseInt( start[0] );
var en0int = parseInt( end[0] );
var resArr= Array();
if ( start.length > 1 ) {
if ( st0int != en0int-1 ) {
resArr.push( midDiap( start, end) );
}
for ( var i=1; i
Существующий недочет
Для диапазона 10-29 и.т.п. сгенерируется избыточное выражение (?:2[0-9]|1[0-9])
Комментариев нет:
Отправить комментарий