Угадай алгоритм

[green_fr]

Продолжая тему памяти и документации.
У нас на работе используются идентификаторы из 6 цифр и одной буквы. Цифры выдаются системой по порядку, а буква избыточная, для контроля ошибок. Она генерится специальным алгоритмом так, чтобы у «соседних» номеров буквы были разными — соседними мы называем номера, отличающиеся от исходного одной (любой) цифрой, либо (не 100% достоверная информация) перестановкой двух любых (возможно, соседних) цифр. То есть такая вот минимальная защита от классических описок/опечаток.

Ну а дальше классика — дошли до 999999, подняли алгоритм генерации букв, в нём комментариев ноль, документации ноль, написавший его человек ушёл на пенсию настолько давно что никто не помнит даже его имени. Ходят какие-то слухи, что он не сам придумал алгоритм, а содрал его у более продвинутых товарищей (цитируются американские военные), и это внушает надежду, что кто-то опознает алгоритм.

Вот его причёсанная java-версия (изначально, конечно же, написан на Cobol’е), вам что-нибудь говорят эти цифры?

private int AACUM;
private String AAMEF;
private String [] AAVALNUM = 
   {"0003", "0004", "0100", "0104", "0001", "0005", "0101", "0105", "0002", "0006", 
    "0101", "0002", "0004", "0006", "0100", "0102", "0104", "0106", "0001", "0003", 
    "0104", "0001", "0002", "0003", "0004", "0005", "0006", "0007", "0100", "0101"};
private String [] AALET = {"A","B","C","D","E","F","G","H","J","K","L","M","N","P","Q","R","S","T","U","V","W","X","Y","Z"};
private String bis(String AAZCIN) {
    AACUM = 0;
    AAMEF = "90" + AAZCIN.substring(0,2) + "0" + AAZCIN.substring(2,6) ;//+ "0";
    for (int j=0; j <3; j++) {
        for (int i = 0; i < 3; i++) {
            AACUM  += Integer.parseInt(AAVALNUM[10*i + Integer.parseInt(AAMEF.substring(j*3 +i, j*3 +i+1))]);
        }
    }
    return  AALET[((AACUM % 100) % 8) + (8*((AACUM/100) % 3))];
}

Или хотя бы общие соображения о том, как он работает, и как его расширить до 7 цифр :-)

Comments

[max-first.livejournal.com]

Он очевидно, на 9 значные номера расчитан изначально.
Так что замена
AAMEF = "90" + AAZCIN.substring(0,2) + "0" + AAZCIN.substring(2,6) ;//+ "0";
на
AAMEF = "9" + AAZCIN.substring(0,3) + "0" + AAZCIN.substring(3,7);
должна помочь

[green-fr.livejournal.com]

А можешь немного мысль развить? А то я как-то в упор не вижу, ни почему алгоритм на 9 знаков, ни почему твоё изменение сработает. Я даже не уверен, преднамеренно ли ты заменил 90 на 9, или это опечатка...

[max-first.livejournal.com]

Вот этот цикл
for (int j=0; j <3; j++) {
for (int i = 0; i < 3; i++) {
ходит по строчке как по квадрату 3х3, то есть надо 9 символов
У нас изначально 6 - добавляем еще 3 вот так 90хх0хххх
Чтоб расширить до 7 - добавляем только два: 9ххх0хххх - что я и написал.

[green-fr.livejournal.com]

Ну да, ты исходишь из того, что алгоритм работает с любыми строками, и мы тупо добавили 90 и 0, а могли бы что-то другое, и оно всё равно бы работало. Мне это не очевидно. Хотелось бы понять, как работает этот алгоритм, чтобы быть уверенным.

Можно, конечно, предположить правильность твоего постулата и тупо прогнать тест на 10000000 значений с проверками, но это же не спортивно!

[green-fr.livejournal.com]

Или ты о том, что внутренняя сумма проходит 9 раз, и что для этого мы добавляем «левые» цифры? Но кто нам говорит, что они действительно левые, и что с другими цифрами алгоритм сработает?

[aaalex.livejournal.com]

Интересно. Напоминает разные алго для хешей.
Жаль нет времини прямо сейчас.

Обрати внимание, что
1. j - номер тройки, i-номер цифры в тройке. Каждая линия в матрице соответсвует цифре в тройке.
2. на самом деле AACUM - это 2 назависимых числа. 2 независимых суммы. Их впихнули зачем-то в одно, сдвинув на 2 десятичных разряда. В первую сумму цифра добавляет 1 или не добавляет. Во вторую - добавляет от 0 до 7.
3. Первая сумма - номер восьмерки букв, вторая сумма - номер внутри восьмерки.

Остается вопрос заполнения матрицы

[green-fr.livejournal.com]

О, спасибо!
Задним умом всё очевидно, но я как-то не допёр рассматривать это как две независимые суммы, с ними всё становится очевидно. И последняя строчка с «по модулю 100» и «целое от деления на 100» — это же именно что возврат к двум составляющим суммы.
Спасибо, раскололи, хотя названия алгоритма и не нашли :-)

[grave--digger.livejournal.com]

А у меня вопрос по существу: тебе именно этот алгоритм надо расширить или просто расширить диапазон нумерации? :) Ну, в смысле, тебе просто интересно, как это работает, или вы действительно решили пойти сложным путём при расширении диапазона номеров, расширяя алгоритм вместо того, чтобы дописать к получаемому номеру пару цифр?

[green-fr.livejournal.com]

Просто так дописать пару цифр — сломается система защиты от опечаток (добавленные цифры не участвуют в рассчёте буквенного ключа, опечатка в них не приводит к смене буквы), а её хотелось бы оставить.

[grave--digger.livejournal.com]

Хм, то есть, автоматическая проверка буквы идёт не только при генерации ключа, но и при любом его вводе?
Хотя в любом случае просто в начало ключа дописать, например, две последние цифры года, остальную часть использовать как и раньше. И можно пользоваться долго и счастливо, меняя каждый год две первые цифры. Просто придётся быть чуточку внимательней и контролировать совпадение этих цифр и года. Зато для отчётности удобнее. :)

[avva.livejournal.com]

Расширить до 7 цифр легко: замените "0" + AAZCIN.substring(2,6) на AAZCIN.substring(2,7) и все. Собственно, алгоритм расчитан на 9 цифр, поэтому "90" и еще один "0" дальше добавлены в виде padding.

Как работает в целом понятно, до какой степени дотошности вам объяснить? Числа в AAVALNUM следует воспринимать как пары чисел, первые две цифры и последние две цифры отдельно, потому что в таком виде они потом реально играют роль в последней строке. Т.е. на самом деле это массив пар такого вида:

(0,3), (0,4), (1,0)...
(1,1), (0,2), (0,4)...
(1,4), (0,1), (0,2)...

из 30 пар, которые делятся на три строки по десять пар в каждой. Или три массива по 10 значений в каждом, так даже проще.

Далее алгоритм смотрит на каждую цифры 9-цифрового исходного числа, и прибавляет к двум аккумуляторам (которые в коде объединены в один AACUM)
значения пары, которая стоит на этом месте в одном из трех массивов: в каком - зависит от позиции данной цифры mod 3.
Обозначим аккумуляторы ACUM1 и ACUM2, тогда, например, если на 4-м месте в числе стоит цифра 1, то мы смотрим на второй массив (массив номер 1=4%3, считая от 0),
позицию номер 1 (опять-таки считая от 0), и видим там пару (0,2), см. выше, и добавляем ACUM1+=0, ACUM2+=2. Следующая цифра на 5-й позиции, поэтому для нее мы возьмем пару из третьего массива, и так далее.

В конце мы берем получившееся значение ACUM1 по модулю 3, получившееся значениe ACUM2 по модулю 8, и смотрим на них вместе как две цифры восьмеричного числа, которое определяет индекс буквы в массиве AALET. Таким образом наибольшее значение индекса будет 027 в восьмеричной системе (2 максимальное значение ACUM1, по модулю 3, 7 максимальное ACUM2 по модулю 8), что равно 23. Всего в массиве 24 буквы, т.к. пропущены I и O, так что это как раз сходится.

[avva.livejournal.com]

Пары в трех массивах по 10 пар в каждом подобраны так, что:

1) в одном массиве никогда нет двух одинаковых пар. Это значит, что если одну цифру в исходном числе заменить на другую, алгоритм использует другую пару из того же массива, и это изменит конечный индекс (строго говоря, это изменит конечное значение хотя бы одного из ACUM1, ACUM2, а они берутся в конце по модулю 3 и 8 соответственно, но изменение одной пары не может увеличить/уменьшить их ровно на 3 или ровно на 8, потому что значения в парах меньше этих границ).

2) что происходит, если вы поменяете местами две цифры в соседних позициях? Например, это цифры i,j в позициях 1 и 2, так что пары для них идут из второго и третьего массивов. Теперь пара для i будет браться из третьего массива, а для j из второго, а раньше было наоборот. Поэтому общий вклад в (ACUM1, ACUM2) изменится на величину (пара номер i из третьего - пара номер i из второго) + (пара номер j из второго - пара номер j из третьего). Для того, чтобы этот общий вклад не был нулевым в обоих координатах, нужно гарантировать, что в массиве разностей между вторым и третьим массивом не было идентичных пар. И дейсвительно, если вы вычтете третий массив из второго, то получите:

(0,-3), (0,1), (0, 2), (0,3), (1,-3), (1,-2), (1, -1), (-1,1), (-1,2)

все пары разные. То же увидите, если вычтете третий массив из первого или первый из второго[1]. Таким образом достигается указанное вами свойство.


[1] С одним исключением: две пары при вычитании 1-го массива из 3-го совпадают. Значит, есть какая-то доля чисел, в которых перемена соседних двух цифр приведет к той же букве. Возможно, кто-то допустил ошибку в создании массивов, или может быть это неизбежно в данном случае.

[a_p]

кстати, в промышленности (например, в баркодах, например, в стандарте code128) есть довольно старнадртный подход к вычислению подобных контрольных величин: суммируются величины букв/цифр, умноженные на позицию в строке (и потом берётся остаток от деления этого дела на что-нибудь). Оба ваших требования (ловить опечатки в одной цифре и перестановку пары соседних) при этом удовлетворяются.