Принудительный выход из рекурсии в случае, если ответ уже найден - Алгоритмы

Опять я со своими нескончаемыми дилетантскими вопросами...

Простенькая задача: Merged String Checker | Codewars

Мое решение на JavaScript

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;
    }

Наверное, любой бывалый программист скажет, что подобные фрагменты в подавляющем большинстве случаев лишь засоряют код (поправьте, если это не так). Однако, как мне кажется, в некоторых (редких?) случаях они могут быть полезны.

Немного модифицированное решение

function isMerge(s, part1, part2) {
  console.log("s =", s)
  console.log("part1 =", part1)
  console.log("part2 =", part2)
  
  if (s.length !== part1.length + part2.length) {
    return false;    
  }
  
  const last = s.length - 1;
  let mergeConfirmed = false;
  
  const tryMerge = (pos1=0, pos2=0) => {
    console.log("pos1, pos2, mergeConfirmed =", pos1, pos2, mergeConfirmed)
    
    if (mergeConfirmed) {
      // return;
      console.log("PREVENTIVE EXIT COULD BE HERE!")
    }
    
    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();
  console.log("mergeConfirmed =", mergeConfirmed)
  
  return mergeConfirmed;
}

Один из логов модифицированного решения

s = <!qTG<<!qoi3ndI
part1 = <!qoi
part2 = <!qTG<3ndI
pos1, pos2, mergeConfirmed = 0 0 false
pos1, pos2, mergeConfirmed = 1 0 false
pos1, pos2, mergeConfirmed = 2 0 false
pos1, pos2, mergeConfirmed = 3 0 false
pos1, pos2, mergeConfirmed = 0 1 false
pos1, pos2, mergeConfirmed = 0 2 false
pos1, pos2, mergeConfirmed = 0 3 false
pos1, pos2, mergeConfirmed = 0 4 false
pos1, pos2, mergeConfirmed = 0 5 false
pos1, pos2, mergeConfirmed = 1 5 false
pos1, pos2, mergeConfirmed = 1 6 false
pos1, pos2, mergeConfirmed = 2 6 false
pos1, pos2, mergeConfirmed = 3 6 false
pos1, pos2, mergeConfirmed = 4 6 false
pos1, pos2, mergeConfirmed = 5 6 false
pos1, pos2, mergeConfirmed = 5 7 false
pos1, pos2, mergeConfirmed = 5 8 false
pos1, pos2, mergeConfirmed = 5 9 false
pos1, pos2, mergeConfirmed = 5 10 false
pos1, pos2, mergeConfirmed = 0 6 true
PREVENTIVE EXIT COULD BE HERE!
pos1, pos2, mergeConfirmed = 1 6 true
PREVENTIVE EXIT COULD BE HERE!
pos1, pos2, mergeConfirmed = 2 6 true
PREVENTIVE EXIT COULD BE HERE!
pos1, pos2, mergeConfirmed = 3 6 true
PREVENTIVE EXIT COULD BE HERE!
pos1, pos2, mergeConfirmed = 4 6 true
PREVENTIVE EXIT COULD BE HERE!
pos1, pos2, mergeConfirmed = 5 6 true
PREVENTIVE EXIT COULD BE HERE!
pos1, pos2, mergeConfirmed = 5 7 true
PREVENTIVE EXIT COULD BE HERE!
pos1, pos2, mergeConfirmed = 5 8 true
PREVENTIVE EXIT COULD BE HERE!
pos1, pos2, mergeConfirmed = 5 9 true
PREVENTIVE EXIT COULD BE HERE!
pos1, pos2, mergeConfirmed = 5 10 true
PREVENTIVE EXIT COULD BE HERE!
mergeConfirmed = true

Что скажете, имеет ли такой подход с превентивным выходом из рекурсии право на существование? Оговорюсь, что вышеприведенный лог относится к единственному подвернувшемуся мне тестовому случаю, в котором этот подход мог быть мало-мальски полезен. Вполне возможно, что я чего-то недопонимаю...

Здравствуйте, Lazytech, Вы писали:

L>Вполне возможно, что я чего-то недопонимаю...
А зачем понадобилась рекурсия?

Здравствуйте, kov_serg, Вы писали:

_>А зачем понадобилась рекурсия?

А как иначе решать такие задачи? Из альтернативных подходов могу назвать только лишь динамическое программирование, но рекурсивное решение в данном случае вроде проще.

Здравствуйте, Lazytech, Вы писали:

_>>А зачем понадобилась рекурсия?

L>А как иначе решать такие задачи? Из альтернативных подходов могу назвать только лишь динамическое программирование, но рекурсивное решение в данном случае вроде проще.

На первый взгляд задача очень похожа на сортировку слиянием — два линейных прохода по двум массивам.

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>На первый взгляд задача очень похожа на сортировку слиянием — два линейных прохода по двум массивам.

Сначала я примерно так и сделал, только вот это решение заваливало некоторые тестовые случаи. Проблема в том, что между part1 и part2 возможны «ложные перекрытия» (см. пример ниже).

Еще один лог модифицированного решения

s = Bananas from Bahamas
part1 = Bahas
part2 = Bananas from am
pos1, pos2, mergeConfirmed = 0 0 false
pos1, pos2, mergeConfirmed = 1 0 false
pos1, pos2, mergeConfirmed = 2 0 false
pos1, pos2, mergeConfirmed = 0 1 false
pos1, pos2, mergeConfirmed = 0 2 false
pos1, pos2, mergeConfirmed = 0 3 false
pos1, pos2, mergeConfirmed = 0 4 false
pos1, pos2, mergeConfirmed = 0 5 false
pos1, pos2, mergeConfirmed = 0 6 false
pos1, pos2, mergeConfirmed = 0 7 false
pos1, pos2, mergeConfirmed = 0 8 false
pos1, pos2, mergeConfirmed = 0 9 false
pos1, pos2, mergeConfirmed = 0 10 false
pos1, pos2, mergeConfirmed = 0 11 false
pos1, pos2, mergeConfirmed = 0 12 false
pos1, pos2, mergeConfirmed = 0 13 false
pos1, pos2, mergeConfirmed = 1 13 false
pos1, pos2, mergeConfirmed = 2 13 false
pos1, pos2, mergeConfirmed = 3 13 false
pos1, pos2, mergeConfirmed = 4 13 false
pos1, pos2, mergeConfirmed = 3 14 false
pos1, pos2, mergeConfirmed = 3 15 false
pos1, pos2, mergeConfirmed = 4 15 false
pos1, pos2, mergeConfirmed = 5 15 false
pos1, pos2, mergeConfirmed = 1 14 true
PREVENTIVE EXIT COULD BE HERE!
mergeConfirmed = true

P.S. Если я правильно понял, имелось в виду нечто вроде этого:

Не вполне рабочее решение

function isMerge(s, part1, part2) {
  if (s.length !== part1.length + part2.length) {
    return false;    
  }

  const len = s.length;
  let pos1 = 0,
      pos2 = 0;
      
  for (let i = 0; i < len; i++) {
    if (part1[pos1] === s[i]) {
      pos1++;
    } else if (part2[pos2] === s[i]) {
      pos2++
    } else {
      return false;
    }
  }
  
  return true;
}

Такое решение заваливает некоторые тесты по вышеуказанной причине. Если я что-то сделал не так, прошу указать на ошибку.

P.P.S. Нашел еще один подход, в котором используется стек:
https://stackoverflow.com/questions/49960458/codewars-merged-string-checker

Здравствуйте, 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, а иначе выходишь из цикла.

Если дошел на выходе из цикла ты дошел до конца выходной строки и полностью сожрал обе входные, то ответ "да", иначе — "нет".

Здравствуйте, Pzz, Вы писали:

Pzz>Идешь по выходной строке по символам, по порядку, и смотришь, если очередной символ является началом строки s1, откусываешь его от начала строки s1, если началом строки s2, то откусываешь от начала строки s2, а иначе выходишь из цикла.

А если буквы одинаковые в s1 и s2, то какую из строк откусывать?

Здравствуйте, Буравчик, Вы писали:

Pzz>>Идешь по выходной строке по символам, по порядку, и смотришь, если очередной символ является началом строки s1, откусываешь его от начала строки s1, если началом строки s2, то откусываешь от начала строки s2, а иначе выходишь из цикла.

Б>А если буквы одинаковые в s1 и s2, то какую из строк откусывать?

Вроде как не важно, но математическое доказательство изобретать лениво

Здравствуйте, Pzz, Вы писали:

Pzz>Вроде как не важно, но математическое доказательство изобретать лениво

Важно.

Пример:

s = aman
s1 = am
s2 = an

Если откусишь s2 вместо s1, то ошибешься

Здравствуйте, Буравчик, Вы писали:

Pzz>>Вроде как не важно, но математическое доказательство изобретать лениво

Б>Важно.

Да, пожалуй. Но все равно должен быть линейный, от суммы длинн, алгоритм. Это ж сводится к регулярному автомату, причем построение такого автомата тоже должно быть несложным.

Здравствуйте, Буравчик, Вы писали:

Б>Если откусишь s2 вместо s1, то ошибешься

ОК, тогда вот так.

Если обе подходят, откусываем от обеих, и считаем, сколько раз мы откусили от обеих. Когда доходим до того места, когда начинает подходить только одна, откусываем от нее, а другую проматываем назад на столько, сколько мы насчитали, пока откусывали от обеих.

Здравствуйте, 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

Здравствуйте, Lazytech, Вы писали:

L>Что скажете, имеет ли такой подход с превентивным выходом из рекурсии право на существование?

Да может, почему нет.

Но вот я не понял, зачем так сложно? Насколько я понимаю, должно хватить цикла по merged строке, и проверкой каждого символа на нахождение в начале одной из проверяемых строк (если найден, то указатель/индекс по той строке увеличиваем).

Здравствуйте, Stanislav V. Zudin, Вы писали:

_>>>А зачем понадобилась рекурсия?

L>>А как иначе решать такие задачи? Из альтернативных подходов могу назвать только лишь динамическое программирование, но рекурсивное решение в данном случае вроде проще.

SVZ>На первый взгляд задача очень похожа на сортировку слиянием — два линейных прохода по двум массивам.

Почему два и два?

Здравствуйте, Marty, Вы писали:

L>>Что скажете, имеет ли такой подход с превентивным выходом из рекурсии право на существование?
M>Да может, почему нет.

Я подозревал, что в данном случае модификация внешней переменной вместо явного возврата результата — это bad practice. Похоже, так и есть.

M>Но вот я не понял, зачем так сложно? Насколько я понимаю, должно хватить цикла по merged строке, и проверкой каждого символа на нахождение в начале одной из проверяемых строк (если найден, то указатель/индекс по той строке увеличиваем).

Выше объяснили, почему такой подход не работает.

Здравствуйте, Marty, Вы писали:

SVZ>>На первый взгляд задача очень похожа на сортировку слиянием — два линейных прохода по двум массивам.

M>Почему два и два?

Неточно выразился. Ессно, имелось в виду одновременно обойти два массива.
Но коллеги уже предложили контрпримеры, на котором это работать не будет.

Можно попробовать применить жадный алгоритм — при совпадении символов выбирать самую длинную последовательность, а не единственный символ. Этот вариант надо проверять.
Но в любом случае мне кажется рекурсия тут лишняя.

Здравствуйте, Lazytech, Вы писали:

L>>>Что скажете, имеет ли такой подход с превентивным выходом из рекурсии право на существование?
M>>Да может, почему нет.

L>Я подозревал, что в данном случае модификация внешней переменной вместо явного возврата результата — это bad practice. Похоже, так и есть.

Всё равно же переменная локальная, она внешняя только для лямбды. Имхо корявенько как-то, но не ужас-ужас

M>>Но вот я не понял, зачем так сложно? Насколько я понимаю, должно хватить цикла по merged строке, и проверкой каждого символа на нахождение в начале одной из проверяемых строк (если найден, то указатель/индекс по той строке увеличиваем).

L>Выше объяснили, почему такой подход не работает.

Да, согласен, не слишком долго думал. Но, думаю, линейный вариант можно сделать. Хотя, конечно, рекурсию налабать обычно проще

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>>>На первый взгляд задача очень похожа на сортировку слиянием — два линейных прохода по двум массивам.

M>>Почему два и два?

SVZ>Неточно выразился. Ессно, имелось в виду одновременно обойти два массива.

Ну, я бы сказал: а) обойти один массив — полную строку (кандидатов не учитываем), либо б) обойти три массива — полная строка и два кандидата

SVZ>Но коллеги уже предложили контрпримеры, на котором это работать не будет.

SVZ>Можно попробовать применить жадный алгоритм — при совпадении символов выбирать самую длинную последовательность, а не единственный символ. Этот вариант надо проверять.
SVZ>Но в любом случае мне кажется рекурсия тут лишняя.

Да, я тоже лажанул на скорую руку. И да, имхо рекурсия не нужна. Но с ней часто проще что-то налабать — вместо явного стека использовать неявный

	От:	Lazytech
	Дата:	20.11.20 14:21
	Оценка:

	От:	kov_serg
	Дата:	20.11.20 15:16
	Оценка:

	От:	Lazytech
	Дата:	20.11.20 15:18
	Оценка:	+1

	От:	Stanislav V. Zudin
	Дата:	20.11.20 15:23
	Оценка:	+1

	От:	Lazytech
	Дата:	20.11.20 15:27
	Оценка:

	От:	Буравчик
	Дата:	20.11.20 17:36
	Оценка:	19 (2)

От:	Pzz	https://github.com/alexpevzner
Дата:	20.11.20 18:12
Оценка:

От:	Marty	https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата:	21.11.20 17:26
Оценка: