маска числовой последовательности

[Mayor]

есть ряд диапазонов телефоных номеров, все их нужно превратить в маски, разбиенем на базовые поддиапазоны и простым удалением поддиапазонов 0*-9* от 0 до 10**(к+1) где к число разрядов

пример:

вход:

2030000 2039999
2290000 2293099
2293300 2297699
2297800 2297899
2298000 2298999
2299300 2299399
2299700 2299999
2510000 2514999
2516000 2516999
2517900 2517999
2518200 2519099

выход:

2030000 2039999
2030 ;
2290000 2293099
2290 ; 2291 ; 2292 ; 22930 ;
2293300 2297699
22933 ; 22934 ; 22935 ; 22936 ; 22937 ; 22938 ; 22939 ; 2294 ; 2295 ; 2296 ; 22976 ; 22975 ; 22974 ; 22973 ; 22972 ; 22971 ; 22970 ;
2297800 2297899
229780 ;
2298000 2298999
22980 ;
2299300 2299399
229930 ;
2299700 2299999

вот первая глючная версия кода не поддающаяся дальнейшей отладке -- написаная в императивном стиле

Код:

#!/bin/awk

BEGIN {
	FS="";
	num=7 # number of digit;
	dsize=1 # delimiter size;
	msep=" ; " #mask separator;
}

{
print " \n" $0;
	for (i=1 ; i<=num ; i++ ) { # const digit
		if ( $i != $(i+num+dsize) ) break ;}

	o=num # begin digit;

# print lower 
	while ( o>i ) {
		while ( $o%10  ) {
			for ( t=1; t<=o ; t++) printf "%s",$t; 
			printf "%s",msep;
			$o++;
		}
		if ($o=="10") {
			$o="0";
			o--;
			$o++;
		}
		else o--;
		
	}
#print highter digit

	xx=0;
	for ( x=num ; x>=i; x--) {
		if ( $x != "0" || $(x+num+dsize) !=9 ) {
			xx=1;
			break;
		}
	}
	if ( xx != 0 )
	{
	while ($o < $(o+num+dsize)) {
		for ( t=1; t<=o ; t++) {
		       	printf "%s",$t ; }
		printf "%s",msep ;
		$o++;
	} }
	else {
		for (t=1;t<=o; t++) {
			printf "%s",$t;}
		printf "%s",msep;
	}
#print last
	o=num+num+dsize;
	i=i+num+dsize;
	while ( o>i ) {
		if ( $o==-1 ) {
			o--;
			$o--;
			continue;
		}
		if ( $o==9 ) {
			o--;
		       	continue ;
		}
		for ( t=num+2; t<=o ; t++) {
		       	printf "%s",$t ; }
		printf "%s",msep ;
		$o--;
	}
	if ( $i == $(i-num-1) ){
		for (t=num+2;t <=o ; t++) {
			printf "%s",$t ; }
	}
}

вот вторая версия кода, не потребововшая отладки -- написанная в event-driven стиле:

Код:

#!/bin/awk -f

BEGIN {
	bold = 0;
	FS="-"
	msep = ","
}
#next rule
/^=/ {
	printf "\n" $1 "   "
	bold=0
	next
}

#constraits

length($1) != length($2) { 
	printf " length mismatch at : " NR  ;
	exit 1;
}

$1 !~ /^[0-9]+$/ || $2 !~ /^[0-9]+$/ {

       print " not number at : " NR ;
       exit 1;
}

$1 > $2 || bold > $1 {
	printf " wrong number at : " NR ;
	exit 1;
}

#initialisation
{
	#bold=$2
	delete t1
	delete t2
	split($1,t1,"")
	split($2,t2,"")
	i=0
	while ( t1[i+1] == t2[i+1] && i<length($1) ) i++;
	teq=substr($1,1,i) # number of equal digits
	i++
	$1=substr($1,i) 
	$2=substr($2,i)
	$1=gensub(/0*$/,""," ",$1)
	$2=gensub(/9*$/,""," ",$2)
	if ( $1 == $2 ) {
		printf "%s%s",teq,msep
		next
	}
	thh=substr($2,1,1) # stop number
	if ( thh == "" ) thh=9


}
$1 == "" { $1 = "0" }

#low path
{
	while ( $1 != thh ) {
		printf "%s%s%s",teq,$1,msep
		$1++ ;
		$1=gensub(/0*$/,""," ",$1)
	}
}
#high path
$2 == "" {
	printf "%s%s%s",teq,"9",msep
	next
}

{
	thh--
	while ( $2 > thh ) {
		printf "%s%s%s",teq,$2,msep
		$2=gensub(/0*$/,""," ",$2)
		$2-- ;
	}
}
#test

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

на каком бы языке предпочли писать код и почему?

какой алгоритм лучше использовать для решения?

какое представление данных проще реализовать? символьное или целое?

[Алексей++]

ответы, по порядку:

1) предпочёл бы хороший стиль
2) с++ (потому что пишу только на нём)
3) хм... работающий алгоритм ))
4) вопрос не совсем понятен...

[RXL]

Алексей1153++, задача проста:
есть диапазоны телефонных номеров (не чисел, а последовательностей цифр!). Нужно найти префиксы.

Пример: есть диапазон 100..109.
В телефонии он записывается так: 100, 101, 102, 103, 104, 105, 106, 107, 108, 109.
Более удобная префиксная запись: 10.

Пример: диапазон 100..139.
Списое полностью не привожу - и так понятно
Префиксы: 10, 11, 12, 13.

И более сложный случай: 100...127.
Префиксы: 10, 11, 12, 120, 121, 122, 123, 124, 125, 126, 127.

Объем списка сокращается, а информация не теряется.

[Алексей++]

ааа, так это я только что реализовывал ) Называется алгоритм архивации Лемпеля-Зива

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

[RXL]

На подручном PHP:

Код:

<?php

function find_prefixes($n1, $n2)
{
	$list = array();

	// Удалить последние цифры, если в первом числе это 0, а во втором 9.
	for ($i = strlen($n1) - 1; $i >= 0; $i--)
	{
		if (substr($n1, $i, 1) != &#39;0&#39; || substr($n2, $i, 1) != &#39;9&#39;)
			break;
	}

	$n1 = substr($n1, 0, $i + 1);
	$n2 = substr($n2, 0, $i + 1);

	// Найти постоянный префикс, общий для двух номеров. Его тоже отрезаем.
	for ($i = 0; $i < strlen($n1); $i++)
	{
		if (substr($n1, $i, 1) != substr($n2, $i, 1))
			break;
	}

	$prefix = substr($n1, 0, $i);
	$n1 = substr($n1, $i);
	$n2 = substr($n2, $i);

	$delta = $n2 - $n1;
	$temp = $n1;

	while ($delta != &#39;&#39;)
	{
		$beg = substr($temp, 0, 1);
		$end = substr($delta, 0, 1) + $beg;

		for ($digit = $beg; $digit <= $end; $digit++)
		{
			$list[] = $prefix . $digit;
		}

		$prefix = $prefix . $end;

		$delta = substr($delta, 1);
		$temp = substr($temp, 1);
	}

	$list[] = $prefix;

	return $list;
}

print join("\n", find_prefixes(&#39;2030000&#39;, &#39;2046799&#39;)) . "\n";

?>

Результат теста:

203
2040
2041
2042
2043
2044
2045
20460
20461
20462
20463
20464
20465
20466
20467


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

[Mayor]

хорошо нада пхп немного почитать ...

[RXL]

Не - у меня много ошибок - позже переделаю.

[Mayor]

Не - у меня много ошибок - позже переделаю.

да мне лишь бы алгоритм понять и сравнить эфективность написания на пхп и авк

[Dimka]

Странно, почему действия событийно-управляемого кода на AWK не получилось эффективно привести к алгоритмическому виду...

Код:

// Язык                : Windows Script Host, JScript
// Пример использования: "cscript /Nologo phones.js < phones.txt > mask.txt"

var maskSeparator = " ; ";

// Функция поиска масок.
// Параметры:
//   begin - начало диапазона номеров
//   end   - конец диапазона номеров
// Результат: отсутствует
function findMask(begin, end)
{    
    for(;;)
    {
        begin = String(begin);
        end = String(end);    
        if(begin == "" || end == "")
        {
            return;
        }
        if(begin == end)
        {
            WScript.StdOut.Write(begin + maskSeparator);
            break;
        }
        // Обрабатываем номера с конца.
        var lastBegin = Number(begin.charAt(begin.length - 1));
        var lastEnd = Number(end.charAt(end.length - 1));       
        if(lastBegin == "0" && lastEnd == "9")
        {
            // Отбрасываем последнюю цифру.
            begin = begin.substr(0, begin.length - 1);
            end = end.substr(0, end.length - 1);
        }
        else
        {
            // Стараемся привести номера к виду, при котором конечные цифры
            // составят полный диапазон номеров от 0 до 9 и смогут быть
            // отброшены (см. выше)
            begin = Number(begin);
            end = Number(end);
            while(begin % 10 > 0 && begin < end)
            { 
                WScript.StdOut.Write(begin + maskSeparator);
                begin++;
            };
            while(end % 10 < 9 && begin < end)
            {
                WScript.StdOut.Write(end + maskSeparator);
                end--;
            };
        };
    };
    WScript.StdOut.WriteLine();
};

// Основная программа.
while(!WScript.StdIn.AtEndOfStream)
{
    var line = WScript.StdIn.ReadLine();
    WScript.StdOut.WriteLine(line);    
    var numbers = line.split(new RegExp("(\ |\t)"));        
    findMask(numbers[0], numbers[1]);
};

Вывод:

Код:

2030000 2039999
203 ; 
2290000 2293099
22930 ; 2292 ; 2291 ; 2290 ; 
2293300 2297699
22933 ; 22934 ; 22935 ; 22936 ; 22937 ; 22938 ; 22939 ; 22976 ; 22975 ; 22974 ; 22973 ; 22972 ; 22971 ; 22970 ; 2294 ; 2295 ; 2296 ; 
2297800 2297899
22978 ; 
2298000 2298999
2298 ; 
2299300 2299399
22993 ; 
2299700 2299999
22997 ; 22998 ; 22999 ; 
2510000 2514999
2514 ; 2513 ; 2512 ; 2511 ; 2510 ; 
2516000 2516999
2516 ; 
2517900 2517999
25179 ; 
2518200 2519099
25182 ; 25183 ; 25184 ; 25185 ; 25186 ; 25187 ; 25188 ; 25189 ; 25190 ; 

Единственный недостаток - это несоблюдение лексикографического порядка масок. Но эта проблема тривиальна и решается простой записью в массив с последующей сортировкой.

[Mayor]

Странно, почему действия событийно-управляемого кода на AWK не получилось эффективно привести к алгоритмическому виду...

Единственный недостаток - это несоблюдение лексикографического порядка масок. Но эта проблема тривиальна и решается простой записью в массив с последующей сортировкой.

прикольный алгоритм, мне просто не пришло в голову создать цикл или рекурсию,

по скорости авк немного превосходит js, но это не имеет значение пока мало цифр в номере...

где js учился?
долго алгоритм разрабатывал?
сколько на написание потратил?

[Mayor]

а вата в моем коде косяк: из за слабых типов теряются 0 в начале строки

1204 1249

1204,121 ...


dimka, твой код похоже работает без ошибок
зы типа опыт против поспешности

что бы с этим сделать?

есть парсены со строгими типами?

или как-то можно неявное приведение строки начинающейся с 0 в число с потерей первых нулей обойти?

[Mayor]

зы типа опыт рулит ...

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

Код:

// Язык                : Windows Script Host, JScript
// Пример использования: "cscript /Nologo phones.js < phones.txt > mask.txt"

var maskSeparator = ",";

// Функция поиска масок.
// Параметры:
//   begin - начало диапазона номеров
//   end   - конец диапазона номеров
// Результат: отсутствует
function findMask(begin, end)
{    
    for(;;)
    {
        begin = String(begin);
        end = String(end);    
        if(begin == "" || end == "")
        {
            return;
        }
        if(begin == end)
        {
            WScript.StdOut.Write(begin + maskSeparator);
            break;
        }
        // Обрабатываем номера с конца.
        var lastBegin = Number(begin.charAt(begin.length - 1));
        var lastEnd = Number(end.charAt(end.length - 1));       
        if(lastBegin == "0" && lastEnd == "9")
        {
            // Отбрасываем последнюю цифру.
            begin = begin.substr(0, begin.length - 1);
            end = end.substr(0, end.length - 1);
        }
        else
        {
            // Стараемся привести номера к виду, при котором конечные цифры
            // составят полный диапазон номеров от 0 до 9 и смогут быть
            // отброшены (см. выше)
            begin = Number(begin);
            end = Number(end);
            while(begin % 10 > 0 && begin < end)
            { 
                WScript.StdOut.Write(begin + maskSeparator);
                begin++;
            };
            while(end % 10 < 9 && begin < end)
            {
                WScript.StdOut.Write(end + maskSeparator);
                end--;
            };
        };
    };
    WScript.StdOut.WriteLine();
};

// Основная программа.
while(!WScript.StdIn.AtEndOfStream)
{
    var line = WScript.StdIn.ReadLine();
//	WScript.StdOut.Write(line.substr(0,1));

   if(line.substr(0,1) == "=") {
    WScript.StdOut.WriteLine(line+"   ");    
   }
   else
   {
    var numbers = line.split(new RegExp("(\-|\t)"));        
    findMask(numbers[0], numbers[1]);
   }
};

как кстати отменить вставку конца строки после WriteLine?

вот место моего бага:

#low path
      $1++ ;

строка вида 002, после инкремента превращается в 3, что рушит алгоритм

как править без понятия ... наверное проще димкин алгоритм на авк реализовать чем мой править ...

[Sla]

Mayor1, ты вроде с паскалем знаком
writeline тебе что нибудь напоминает?

[Mayor]

Mayor1, ты вроде с паскалем знаком
writeline тебе что нибудь напоминает?

а те наверное есть, что то типа :

WScript.StdOut.Write()

прикольно, щас заценю