Этот билет был брошен на мой стол на четвертой неделе моей работы фронтенд-разработчика «начального уровня». Как увеличить букву/серию букв? Например, преобразовать A -> B, Z -> AA, BZ -> CA и так далее. Использование алгоритма не имеет значения. Важно, однако, то, насколько эта проблема захватила мое любопытство и заставила меня почувствовать себя взволнованным 5-летним мальчиком, собирающим свой первый набор пазлов. Вот как я нашел оптимальное решение, и я проведу вас через весь процесс, давайте начнем!
Шаг 1: Определите проблему
Как и любая проблема, с которой сталкивается инженер-программист, ее решение требует четкого определения, прежде чем мы начнем. Две критически важные части информации, которые нам нужны, — это входные критерии и ожидаемый результат.
Ввод: мы предполагаем, что ввод представляет собой строку латинского алфавита (английский). Поэтому нам не нужно проверять наличие специальных символов, цифр или пробелов. Тем не менее, мы должны учитывать входные данные нижнего/верхнего регистра.
Вывод: мы получим строку латинских алфавитов, увеличенную на 1 в алфавитном порядке. Бывший. A -> B, Z -> AA, BZ -> CA, ZZ -> AAA и т. д.
Шаг 2: Определите сложность
Прежде чем придумать решение, я хотел бы посмотреть, что делает проблему трудноразрешимой. В этом конкретном случае тикет уже прошел через 3 других младших разработчиков, которые не смогли решить его своевременно.
На первый взгляд, этот билет прост. Если у нас есть буква «F», мы пройдемся по алфавиту и найдем следующую букву «G». Проблема усложняется при обработке «случаев переполнения». Как вы объясняете, что «Z» переполняется «AA»? А как насчет «GZ» на «HA»? Более того, учитывая, что строка букв может быть бесконечно длинной, как нам сделать ее масштабируемой?
Шаг 3: Решение(я)
Способ 1 (неправильный):
«просто напиши пару циклов while, чувак»
Это то, что сказал один из моих коллег, когда я попросил его о помощи. Точно так же большинство людей решают вопросы алгоритмов, просто напишите пару циклов while или for и надейтесь на лучшее. Это неправильно, и я покажу вам, почему. Давайте кодировать!
Во-первых, нам нужно сообщить компьютеру, каков алфавитный порядок. Мы можем создать объект, присваивающий числовое значение клавише алфавита. Так:
const alphabeticalOrder = {A: 1, B: 2, C: 3,D: 4, E: 5, F: 6, G: 7, H: 8, I: 9, J: 10, K: 11, L: 12, M: 13, N: 14, O: 15, P: 16, Q: 17, R: 18, S: 19, T: 20, U: 21, V: 22, W: 23, X: 24, Y:25, Z:26}
Используя этот объект, мы можем сопоставить заданную входную букву и найти букву после нее. Например, мы могли бы написать такую функцию:
const alphabetIncrementation = (input) => {
// the toUpperCase() is meant to account for lowercase inputs
const alphabetValue = alphabeticalOrder[input.toUpperCase()]
const nextAlphabet = Object.keys(alphabeticalOrder).find(key => alphabeticalOrder[key] === alphabetValue + 1);
return nextAlphabet;
}
Теперь все, что нам нужно сделать, это вызвать эту функцию (конечно, передав ввод в качестве параметра) и легко! Верно? Еще не совсем. Теперь нам нужно учесть случаи переполнения.
const alphabetIncrementation = (input) => {
// the toUpperCase() is meant to account for lowercase inputs
const alphabetValue = alphabeticalOrder[input.toUpperCase()]
// add a check for cases where input is Z
const nextAlphabet = alphabetValue + 1 > 26 ? "A" : Object.keys(alphabeticalOrder).find(key => alphabeticalOrder[key] === alphabetValue + 1);
return nextAlphabet;
}
Прохладный! Теперь, когда у нас есть функция для увеличения одного алфавита, давайте заставим ее работать с длинной строкой букв. Мы можем добиться этого, зациклившись на массиве входных данных.
// create an array of letters from the input string
const inputArr = input.split("");
// create an empty string as a placeholder for the output
let output = "";
for (let i = inputArr.length - 1; i >= 0; i--) {
output = alphabetIncrementation(input[i]) + output;
// break out of the loop if no overflow happens
if (alphabetIncrementation(input[i]) !== "A") {
output = input.slice(0, i).toUpperCase() + output;
break;
}
// if the last is overflowing, add an A to the start
if (i === 0) {
output = "A" + output;
}
}
И вуаля! Все сделано! Вы можете проверить код в действии здесь, если хотите.
Способ 2 (правильный способ):
Хотя этот код работает, я им не доволен. Это тоже не перфекционизм, с этим решением есть несколько проблем.
- Масштабируемость: чем длиннее входная строка или буквы, требующие увеличения, тем больше должен выполняться цикл for. В этом упрощенном случае это не имеет значения, но, на мой взгляд, неприемлемо для больших кодовых баз.
- Ремонтопригодность и перспектива: что, если нам нужно вернуть не одну строку, а массив строк, каждая из которых увеличивается на 1 букву? бывший. критерии ввода: «YZ» и ожидаемые 3 строки, вывод: [ZA, ZB, ZC]. Петли просто не режут!
Не бойтесь, мы можем использовать математику, чтобы решить эту проблему! Обратите внимание, что в предыдущем методе мы присваивали значения буквам, а приращение — это просто простой процесс добавления 1 к этому значению. Что, если мы расширим эту идею?
Теперь наша цель — преобразовать уникальную строку в уникальное число. На самом деле это проще, чем кажется. Предположим, что каждый алфавит имеет числовое значение, используемое в объекте AlphabeticalOrder выше (например, A = 1, Z = 26). Мы также присваиваем позиции каждого алфавита уникальное числовое значение, умножая его на 26 в степени позиции (от 0 и считая от самой правой позиции). Смущенный? Не будь! Позвольте мне написать это для вас.
То, что мы только что сделали, это кодирование ABC с помощью процесса, называемого шифром с основанием 26: один из основных алгоритмов преобразования! Чтобы обратить этот процесс вспять, нам просто нужно сначала найти наибольшую степень числа 26, которая меньше 731. Это будет 2, мы получим 26². Затем мы делим исходное число 731 на 26², чтобы получить частное (1) и остаток (45), в результате чего получается уравнение 731 = 26² * 1 + 45. Как видите, мы уже получаем нашу ABC обратно, как сейчас знайте, на 3-й позиции буква А! Теперь мы просто берем остаток и повторяем процесс, пока не останется остатка.
Теперь давайте преобразуем эту математику в код JS. Во-первых, шифрование:
// we could keep the alphabeticalOrder object we used before but we could do better by leveraging some array methods and charCode const alphabeticalOrder = Array.from(Array(26)).map((e, i) => i + 65).map((x) => String.fromCharCode(x));
Этот код в основном создает массив заглавных букв алфавита. Array(26) создает массив длиной 26, количество алфавитов, которое нам нужно. Затем мы сопоставляем его, чтобы заполнить массив числами от 65 до 90. Мы можем использовать from Charcord для преобразования этих чисел в заглавные буквы, поскольку они являются значениями charCode.
Сам код шифрования будет выглядеть следующим образом:
const encryption = (input) => {
// make sure to initialize result to 0 so the rest of the code builds upon this integer
let num = 0;
input = input.toUpperCase();
// we're incrementing j and decrementing i
let j = 0;
for (let i = input.length - 1; i > -1; i--) {
// get letters in reverse
let letter = input[i];
// get index in alphabeticalOrder and compensate for 0 based array
let position = alphabeticalOrder.indexOf(letter);
position++;
// the power based in 26
let power = Math.pow(26, j);
console.log(power)
// add the power and index to result
num += power * position;
j++;
}
return num;
}
К этому числу мы можем добавить 1, чтобы получить числовое значение увеличенных букв. Если вы хотите, вы можете делать все, что угодно, с этим номером. Например, + 3, чтобы увеличить буквы на 3, или вы также можете уменьшить буквы. Пока результат математически достижим, нет предела тому, что вы можете сделать!
Теперь давайте вернем наше письмо после того, как мы манипулировали им в свое удовольствие. Код расшифровки в основном обращает ход шифрования вспять, он может выглядеть примерно так:
const decryption = (num) => {
let quotient = num;
let remainder;
let result = '';
// no letters for 0 or less
if (num < 1) {
return result;
}
while (quotient !== 0) {
let decremented = quotient - 1;
// divide by 26
quotient = Math.floor(decremented / 26);
remainder = decremented % 26;
// prepend the letter at index of remainder
result = alphabeticalOrder[remainder] + result;
}
return result;
}
Заключение:
Оглядываясь назад, на самом деле это не было сложной задачей. На самом деле, если бы вы обращали внимание на вводные занятия по информатике, вы бы знали об алгоритмах преобразования базы. Что мне показалось интересным для размышления, так это процесс решения никогда не встречавшейся проблемы. У меня никогда не было степени в области компьютерных наук, но я люблю такие моменты. Благодаря этому опыту я понял, что знания в области математики, структур данных и алгоритмов необходимы для написания масштабируемого и поддерживаемого кода! Спасибо за чтение!
