function isMerge(s, part1, part2) {
if (s.length !== part1.length + part2.length) {
return false;
}
const last = s.length - 1;
let mergeConfirmed = false;
const tryMerge = (pos1=0, pos2=0) => {
if (mergeConfirmed) {
return;
}
const pos = pos1 + pos2;
if (pos > last) {
mergeConfirmed = true;
return;
}
if (part1[pos1] === s[pos]) {
tryMerge(pos1 + 1, pos2);
}
if (part2[pos2] === s[pos]) {
tryMerge(pos1, pos2 + 1);
}
}
tryMerge();
return mergeConfirmed;
}
Обратите внимание на проверку в самом начале рекурсивной функции tryMerge:
if (mergeConfirmed) {
return;
}
Наверное, любой бывалый программист скажет, что подобные фрагменты в подавляющем большинстве случаев лишь засоряют код (поправьте, если это не так). Однако, как мне кажется, в некоторых (редких?) случаях они могут быть полезны.
Что скажете, имеет ли такой подход с превентивным выходом из рекурсии право на существование? Оговорюсь, что вышеприведенный лог относится к единственному подвернувшемуся мне тестовому случаю, в котором этот подход мог быть мало-мальски полезен. Вполне возможно, что я чего-то недопонимаю...
Re: Принудительный выход из рекурсии в случае, если ответ уже найден
Здравствуйте, kov_serg, Вы писали:
_>А зачем понадобилась рекурсия?
А как иначе решать такие задачи? Из альтернативных подходов могу назвать только лишь динамическое программирование, но рекурсивное решение в данном случае вроде проще.
Здравствуйте, Lazytech, Вы писали:
_>>А зачем понадобилась рекурсия?
L>А как иначе решать такие задачи? Из альтернативных подходов могу назвать только лишь динамическое программирование, но рекурсивное решение в данном случае вроде проще.
На первый взгляд задача очень похожа на сортировку слиянием — два линейных прохода по двум массивам.
_____________________
С уважением,
Stanislav V. Zudin
Re[4]: Принудительный выход из рекурсии в случае, если ответ
Здравствуйте, Stanislav V. Zudin, Вы писали: SVZ>На первый взгляд задача очень похожа на сортировку слиянием — два линейных прохода по двум массивам.
Сначала я примерно так и сделал, только вот это решение заваливало некоторые тестовые случаи. Проблема в том, что между part1 и part2 возможны «ложные перекрытия» (см. пример ниже).
Здравствуйте, Lazytech, Вы писали:
L>Что скажете, имеет ли такой подход с превентивным выходом из рекурсии право на существование? Оговорюсь, что вышеприведенный лог относится к единственному подвернувшемуся мне тестовому случаю, в котором этот подход мог быть мало-мальски полезен. Вполне возможно, что я чего-то недопонимаю...
Если понадобится "резко" завершить рекурсивные вызовы — такой подход норм.
Но, думаю, такая необходимость встречается редко. Если проблема появилась, скорее всего неверно спроектирована функция рекурсии.
Питон (без флагов остановки)
def is_merge(s, part1, part2):
if part1 == '':
return s == part2
if part2 == '':
return s == part1
if s == '':
return False
return s[0] == part1[0] and is_merge(s[1:], part1[1:], part2) \
or s[0] == part2[0] and is_merge(s[1:], part1, part2[1:])
Здравствуйте, Lazytech, Вы писали:
L>Наверное, любой бывалый программист скажет, что подобные фрагменты в подавляющем большинстве случаев лишь засоряют код (поправьте, если это не так). Однако, как мне кажется, в некоторых (редких?) случаях они могут быть полезны.
Там не нужна рекурсия.
Идешь по выходной строке по символам, по порядку, и смотришь, если очередной символ является началом строки s1, откусываешь его от начала строки s1, если началом строки s2, то откусываешь от начала строки s2, а иначе выходишь из цикла.
Если дошел на выходе из цикла ты дошел до конца выходной строки и полностью сожрал обе входные, то ответ "да", иначе — "нет".
Re[2]: Принудительный выход из рекурсии в случае, если ответ уже найден
Здравствуйте, Pzz, Вы писали:
Pzz>Идешь по выходной строке по символам, по порядку, и смотришь, если очередной символ является началом строки s1, откусываешь его от начала строки s1, если началом строки s2, то откусываешь от начала строки s2, а иначе выходишь из цикла.
А если буквы одинаковые в s1 и s2, то какую из строк откусывать?
Best regards, Буравчик
Re[3]: Принудительный выход из рекурсии в случае, если ответ уже найден
Здравствуйте, Буравчик, Вы писали:
Pzz>>Идешь по выходной строке по символам, по порядку, и смотришь, если очередной символ является началом строки s1, откусываешь его от начала строки s1, если началом строки s2, то откусываешь от начала строки s2, а иначе выходишь из цикла.
Б>А если буквы одинаковые в s1 и s2, то какую из строк откусывать?
Вроде как не важно, но математическое доказательство изобретать лениво
Re[4]: Принудительный выход из рекурсии в случае, если ответ уже найден
Здравствуйте, Буравчик, Вы писали:
Pzz>>Вроде как не важно, но математическое доказательство изобретать лениво
Б>Важно.
Да, пожалуй. Но все равно должен быть линейный, от суммы длинн, алгоритм. Это ж сводится к регулярному автомату, причем построение такого автомата тоже должно быть несложным.
Re[5]: Принудительный выход из рекурсии в случае, если ответ уже найден
Здравствуйте, Буравчик, Вы писали:
Б>Если откусишь s2 вместо s1, то ошибешься
ОК, тогда вот так.
Если обе подходят, откусываем от обеих, и считаем, сколько раз мы откусили от обеих. Когда доходим до того места, когда начинает подходить только одна, откусываем от нее, а другую проматываем назад на столько, сколько мы насчитали, пока откусывали от обеих.
Re[6]: Принудительный выход из рекурсии в случае, если ответ
Здравствуйте, Pzz, Вы писали:
Pzz>Если обе подходят, откусываем от обеих, и считаем, сколько раз мы откусили от обеих. Когда доходим до того места, когда начинает подходить только одна, откусываем от нее, а другую проматываем назад на столько, сколько мы насчитали, пока откусывали от обеих.
Похоже, снова не верно
Вот такой контрпример:
s = **a*
s1 = *a
s2 = **
Откусываем от обоих:
s = *a*
s1 = a
s2 = *
(держим в уме откусанную от обоих *)
Теперь только s2 подходит, откусываем ее, s1 проматываем назад
s = a*
s1 = *a
s2 =
FAIL
P.S. Гадания без пройденных тестов больше не принимаются
Здравствуйте, Pzz, Вы писали:
Pzz>Там не нужна рекурсия. Pzz>Идешь по выходной строке по символам, по порядку, и смотришь, если очередной символ является началом строки s1, откусываешь его от начала строки s1, если началом строки s2, то откусываешь от начала строки s2, а иначе выходишь из цикла. Pzz>Если дошел на выходе из цикла ты дошел до конца выходной строки и полностью сожрал обе входные, то ответ "да", иначе — "нет".
я привел примерно такое решение (без откусывания строки, но смысл тот же). Также повторяю тестовый случай, который будет завален из-за «ложного перекрытия»:
s = Bananas from Bahamas
part1 = Bahas
part2 = Bananas from am
L>Что скажете, имеет ли такой подход с превентивным выходом из рекурсии право на существование?
Да может, почему нет.
Но вот я не понял, зачем так сложно? Насколько я понимаю, должно хватить цикла по merged строке, и проверкой каждого символа на нахождение в начале одной из проверяемых строк (если найден, то указатель/индекс по той строке увеличиваем).
Здравствуйте, Stanislav V. Zudin, Вы писали:
_>>>А зачем понадобилась рекурсия?
L>>А как иначе решать такие задачи? Из альтернативных подходов могу назвать только лишь динамическое программирование, но рекурсивное решение в данном случае вроде проще.
SVZ>На первый взгляд задача очень похожа на сортировку слиянием — два линейных прохода по двум массивам.
Здравствуйте, Marty, Вы писали:
L>>Что скажете, имеет ли такой подход с превентивным выходом из рекурсии право на существование? M>Да может, почему нет.
Я подозревал, что в данном случае модификация внешней переменной вместо явного возврата результата — это bad practice. Похоже, так и есть.
M>Но вот я не понял, зачем так сложно? Насколько я понимаю, должно хватить цикла по merged строке, и проверкой каждого символа на нахождение в начале одной из проверяемых строк (если найден, то указатель/индекс по той строке увеличиваем).
Выше объяснили, почему такой подход не работает.
Re[5]: Принудительный выход из рекурсии в случае, если ответ
Здравствуйте, Marty, Вы писали:
SVZ>>На первый взгляд задача очень похожа на сортировку слиянием — два линейных прохода по двум массивам.
M>Почему два и два?
Неточно выразился. Ессно, имелось в виду одновременно обойти два массива.
Но коллеги уже предложили контрпримеры, на котором это работать не будет.
Можно попробовать применить жадный алгоритм — при совпадении символов выбирать самую длинную последовательность, а не единственный символ. Этот вариант надо проверять.
Но в любом случае мне кажется рекурсия тут лишняя.
_____________________
С уважением,
Stanislav V. Zudin
Re[3]: Принудительный выход из рекурсии в случае, если ответ уже найден
Здравствуйте, Lazytech, Вы писали:
L>>>Что скажете, имеет ли такой подход с превентивным выходом из рекурсии право на существование? M>>Да может, почему нет.
L>Я подозревал, что в данном случае модификация внешней переменной вместо явного возврата результата — это bad practice. Похоже, так и есть.
Всё равно же переменная локальная, она внешняя только для лямбды. Имхо корявенько как-то, но не ужас-ужас
M>>Но вот я не понял, зачем так сложно? Насколько я понимаю, должно хватить цикла по merged строке, и проверкой каждого символа на нахождение в начале одной из проверяемых строк (если найден, то указатель/индекс по той строке увеличиваем).
L>Выше объяснили, почему такой подход не работает.
Да, согласен, не слишком долго думал. Но, думаю, линейный вариант можно сделать. Хотя, конечно, рекурсию налабать обычно проще
SVZ>>>На первый взгляд задача очень похожа на сортировку слиянием — два линейных прохода по двум массивам.
M>>Почему два и два?
SVZ>Неточно выразился. Ессно, имелось в виду одновременно обойти два массива.
Ну, я бы сказал: а) обойти один массив — полную строку (кандидатов не учитываем), либо б) обойти три массива — полная строка и два кандидата
SVZ>Но коллеги уже предложили контрпримеры, на котором это работать не будет.
SVZ>Можно попробовать применить жадный алгоритм — при совпадении символов выбирать самую длинную последовательность, а не единственный символ. Этот вариант надо проверять. SVZ>Но в любом случае мне кажется рекурсия тут лишняя.
Да, я тоже лажанул на скорую руку. И да, имхо рекурсия не нужна. Но с ней часто проще что-то налабать — вместо явного стека использовать неявный