алгоритм?

Боян, что-то такое было на тестировании для поступления на работу в одной конторе.

ну то есть мыслей нет?

ты не сформулировал задачу толком. Если речь о нахождении просто хоть какого-то набора префиксов, то это как бы в лоб решается. Другое дело если ты хочешь оптимизировать таблицу -- то есть "вытаскивать наверх" какие-то АТС -- сокращать им префикс. Но тогда ты не сформулировал по какому критерию ты эту таблицу хочешь оптимизировать.

ммм... тут вроде никакой оптимизации не нужно -- надо для списка диапазонов номеров сгенерить список префиксов для однозначного включения произвольного номера в диапазон, сравнив только префиксы. при этом, если существуют несколько префиксов, под которые этот номер подпадает, использовать для идентификации АТС более длинный префикс из подходящих (два одинаковых префикса быть не может, т.е. могут быть префиксы "37" (АТС 37) + "374" (АТС ООО R&K) + "3742" (АТС УО ПК МСТИ), но не может быть "33" (АТС 33) + "3345" (АТС СА КП) + "3345" (АТС ОПМ)).

я застрял на том, что диапазон может начинаться с произвольной цифры, в т.ч. с последней -- 31-00-00..31-09-99, 31-10-00..31-19-99, *31-23-46..31-28-45*.

мощность диапазона я нахожу (1/10/100/1000/... номеров), если нумерация начинается на границе мощности -- всё легко, а вот если она начинается с левого номера -- тут надо расписывать префиксы по возрастающей, и у меня пока не получается это алгоритмизовать. в приведённом выше списке последний диапазон надо расписать как "312346 312347 312348 312349 31235 31236 31237 31238 31239 3124 3125 3126 3127 31280 31281 31282 31283 312840 312841 312842 312843 312844 312845". так вот *как*?

ну вот на шелле:

dump_table()
{
    (
        if test -z "$1"; then
            return
        fi
        A=${1%[0-9]}
        B=${2%[0-9]}
        if test $A = $B; then
            if expr "$1" : "[0-9]*0$" > /dev/null && expr "$2" : "[0-9]*9$" > /dev/null; then
                echo $A
            else
                seq $1 $2
            fi
            return
        fi
        if expr "$1" : "[0-9]*0$" > /dev/null; then
            dump_table $A $((B-1))
            dump_table ${B}0 $2
        else
            seq $1 ${A}9
            dump_table $((A+1))0 $2
        fi
    )
}




$ dump_table 312346 312845
312346
312347
312348
312349
31235
31236
31237
31238
31239
3124
3125
3126
3127
31280
31281
31282
31283
312840
312841
312842
312843
312844
312845

только она не работает если первая цифра 0. -- можно как воркэраунд добавлять всегда 1 в начало

зачёт! я что-то смутно вроде этого думал, но мозги ничего внятного не выдавали -- надо в отпуск.

так лучше:

dump_table()
{
    (
        if test -z "$1"; then
            return
        fi
        A=${1%[0-9]}
        B=${2%[0-9]}
        if test $A = $B; then
            if expr "$1" : "[0-9]*0$" > /dev/null && expr "$2" : "[0-9]*9$" > /dev/null; then
                echo $A
            else
                seq $1 $2
            fi
            return
        fi
        if expr "$1" : "[0-9]*0$" > /dev/null; then
            if expr "$2" : "[0-9]*9$" > /dev/null; then
                dump_table $A $B
            else
                dump_table $A $((B-1))
                dump_table ${B}0 $2
            fi
        else
            seq $1 ${A}9
            dump_table $((A+1))0 $2
        fi
    )
}