Есть ли алгоритмический трюк для решения перестановок размещения скобок в логических выражениях?
Проблема (оригинал найден здесь) заключается в том, чтобы получить случайную строку t и f (обозначающих логическое значение true/false), разделенных одним из & | ^ например "T&F|F^T&T^F" и напишите функцию, возвращающую количество уникальных размещений скобок (где общее количество пар скобок = количество t/f - 1), для которых общее выражение будет иметь значение true. (T&((F^T)|(T&F))) верно. Мой код возвращает правильный ответ, но не за отведенное время (для очень длинных входных строк). Я ищу подсказку относительно того, нужно ли мне понять трюк алгоритма, который резко сокращает количество итераций/рекурсий, или мой код просто недостаточно эффективен.
Мой алгоритм, по сути, перебирает каждую пару, но после сокращения любой данной пары tf до одного нового значения он проверяет полученную строку размещения символов/скобок по справочной таблице, чтобы увидеть, был ли этот шаблон достигнут ранее, и продолжает без рекурсии, если в нем есть.
Например, если входные данные — T T F T F F T: Если мы находимся на перестановке, где первая пара — (TT)F T F F T, а вторая пара — (TT)F T(F F)T, что ж, в конечном итоге у нас будет перестановка, первая пара которой пара — T T F T(F F)T, а вторая — (T T)F T(F F)T, после чего таблица покажет, что этот путь уже пройден, и перейдет к следующей перестановке.
Я также выполняю проверку каждый раз, когда строка tf уменьшается, например. (T&F)^F|T&T --> F^F|T&T, чтобы убедиться, что остался хотя бы один T, поскольку F^F|F&F больше не нуждается в рекурсии.
Я чувствую, что должен быть способ уменьшить количество обходов по сравнению с тем, что я сделал. (обсуждение CodeWars здесь)
// C++. The input will be given as two strings, e.g. "ttfftf","&&^|^"
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <iostream>
using namespace std;
using pairVec = vector<pair<string,char>>;
unordered_map<string, bool> usedPatMap{};
inline char tOrF(char c1, char c2, char op){
if (c1=='f') {
if (c2=='f') return 'f';
else { // c2=='t'
if (op=='&') return 'f';
return 't';
}
}
else { //c1=='t'
if (c2=='f') {
if (op=='&') return 'f';
return 't';
}
else { // c2=='t'
if (op=='^') return 'f';
return 't';
}
}
}
void traverse(pairVec& tfs, string ops, int64_t& ct) {
for(int i = 0; i + 1 < tfs.size(); ++i) {
char tf = tOrF(tfs[i].second, tfs[i+1].second, ops[i]);
string newBracePat = "(" + tfs[i].first + tfs[i+1].first + ")";
pairVec tfs2 = tfs;
string ops2 = ops;
auto p = tfs2.erase(tfs2.begin() + i, tfs2.begin() + 2 + i);
tfs2.insert(p,make_pair(newBracePat,tf));
if (find_if (tfs2.begin(), tfs2.end(),
[](auto x){ return x.second=='t';})==tfs2.end()) continue;
string checkStr;
for(auto pr:tfs2) checkStr.append(pr.first);
if (!usedPatMap[checkStr]) usedPatMap[checkStr] = true;
else continue;
ops2.erase(ops2.begin()+i);
if (ops2.empty()) {
if (tfs2[0].second=='t') ++ct;
return; }
traverse(tfs2, ops2, ct);
}
}
int64_t solve(const string &s, const string &ops) {
if (s.length() < 2 || ops.length()!=s.length() - 1) return 0;
int64_t ct = 0;
string s2 = s, ops2 = ops;
pairVec v(s2.length(),{"x",'t'});
for(int i = 0; i < s2.length(); ++i) if (s2[i]=='f') v[i].second = 'f';
traverse(v, ops2, ct);
return ct;
}
int main(int argc, char **argv) {
cout<<solve("ttftfftftf","|&^&&||^&");
}
Обратите внимание, что в приведенном коде отсутствует функция main и необходимые заголовки. Это не поиск ошибок, поэтому минимальный воспроизводимый пример не является обязательным, но обычно они помогают, и вы настолько близки к его получению, что можете с таким же успехом закончить работу.
Кстати, ваш код не проходит базовые тесты: godbolt.org/z/KPExMvfha поэтому нет смысла рассматривать производительность (глобальное состояние может быть частью проблемы).
После исправления незначительной проблемы в вашем коде: godbolt.org/z/99Mf8o8E9 он не работает в одном простом тестовом примере.
@ user4581301, код взят из CodeWars; все заголовки предоставляются, и сайт вызывает функцию пользователя, поэтому с моей стороны не задействована функция main().
@MarekR, я не знаю, как это может быть: мой код проходит тесты CodeWars на шаблоны, которые дают сотни или тысячи истинных ответов. Для более длинных строк время истекает... Изменение кода для обработки "t" в качестве входных данных не устраняет проблему тайм-аута...
@MarekR, я добавил простую строку, чтобы «t» давало 1, и теперь все тесты Godbolt прошли. Но это не решает проблему CodeWars, поскольку я думаю, что проблема всегда передает строку, содержащую как минимум два символа, с оператором между ними.
Обычно это не имеет значения, поскольку вы сейчас находитесь здесь, и людям здесь может потребоваться запустить ваш код, чтобы поэкспериментировать с ним и протестировать его. Собираетесь ли вы принимать ответы от людей, которые не проверили то, что они написали? Если ваш ответ «да», все, что я могу сказать, это «ТЫ ДУРАК!»
Я добавил в код main() и заголовки. Однако я знаю, что мой алгоритм работает... Я ищу кого-нибудь, кто может сказать мне, есть ли более умный алгоритм для сокращения итераций, потому что моему коду требуется ≈10 секунд для обработки строки из 14 t/f, отведенного время составляет 12 секунд, и я уверен, что сайт передает строки длиной более 14.
Алгоритм работает, но вы думаете, что он может работать лучше. Это похоже на потенциального кандидата на Code Review. Лучше всего убедиться в этом, прочитав их страницы помощи по заданию вопросов, в частности, о каких темах я могу здесь задавать вопросы?
Вы задавали этот вопрос на форумах CodeWars?
Каждая строка с «уникальным размещением скобок» соответствует двоичному дереву. Каждая выбранная вами корневая операция делит входную строку на две части, которые снова можно собрать в дерево. Самое приятное то, что вы можете рассчитать счетчики для обоих поддеревьев отдельно, а затем объединить результаты обеих частей.
@MarekR, спасибо. Я пока не собираюсь просматривать ваш код и посмотреть, смогу ли я сначала понять, что вы подразумеваете под умным кэшированием. Я предполагал, что что-то подобное происходит, но пока не могу понять, как это работает.
@Botje, спасибо, я посмотрю, смогу ли я осознать то, что ты говоришь. Я занимался программированием лишь время от времени в качестве хобби около 4 лет, поэтому многие концепции все еще для меня новы.
И, конечно же, в самом абстрактном смысле вам вообще не нужно строить деревья, вы можете просто говорить о количестве результатов для данного сегмента входных данных.
«Проблема (нажмите, чтобы увидеть)» — Нет. Не «нажмите, чтобы увидеть», ТАК вопросы должны быть полностью самостоятельными. Вопрос должен включать «проблему» (какой бы она ни была), а не прятать ее за ссылкой на внешний сайт (которая может сгнить в будущем).
@Элджей Да, но никто не отвечал, и мне уже не хотелось прогрессировать!
@JesperJuhl Проблема описана в моем сообщении, но кто-то посоветовал мне включить ссылку на оригинал.
Отличный! Пожалуйста, обновите вопрос, добавив ссылку на обсуждение на форуме, чтобы мы также могли увидеть этот разговор.
Ну, я думал, что нашел способ проверить общее количество поддеревьев и просто вернуть счетчик вместо обхода поддерева, но даже в этом случае мой код работает очень медленно. Итак, @MarekR, я все-таки посмотрел твой код. Можете ли вы объяснить мне, что происходит в методе mergeOps()? Я не знаю, как я мог придумать, как выполнять умножение и сложение положительных/отрицательных чисел, которые там происходят...
@MarekR, мне удалось понять, что происходит в твоем коде. Очень поучительная проблема для меня, поэтому спасибо за вашу помощь.
Ответы 1
При беглом взгляде на ваш код я заметил, что вы фактически создаете строки со скобками, вставленными в разные места. Это, безусловно, представляет собой множество манипуляций, в которых на самом деле нет необходимости.
Никаких манипуляций со строками не требуется. Этого должно быть достаточно, чтобы вычислить результаты для подстрок вашего ввода и собрать для каждого количество ложных результатов и количество истинных результатов. Если вы начнете с самых маленьких подстрок, имеющих только одно значение f или t, то это тривиально. Затем вы можете положиться на эти результаты для вычисления количества подстрок, имеющих два операнда и один оператор. Это дает новый пласт результатов. Для следующих слоев вам также необходимо учитывать выбор оператора, который будет располагаться вверху (с левым и правым операндом меньшего размера, для которого у вас уже есть счетчики).
Это описание решения восходящего динамического программирования.
Я привожу здесь код в стиле C, используя простые массивы. Для C++ было бы хорошо использовать векторы, как вы это делали:
int64_t solve(const std::string &s, const std::string &ops)
{
size_t n = s.length();
int64_t dp[n][n][2]; // Dynamic programming tabulation
for (size_t i = 0; i < n; i++) {
int64_t isTrue = (s[i] == 't');
dp[0][i][0] = 1 - isTrue;
dp[0][i][1] = isTrue;
}
int64_t *counters = dp[0][0];
for (size_t opCount = 1; opCount < n; opCount++) {
for (size_t start = 0; start + opCount < n; start++) {
counters = dp[opCount][start];
counters[0] = counters[1] = 0;
for (size_t leftOpCount = 0; leftOpCount < opCount; leftOpCount++) {
int64_t *left = dp[leftOpCount][start];
int64_t *right = dp[opCount - 1 - leftOpCount][start + leftOpCount + 1];
int64_t ff = left[0] * right[0];
int64_t ft = left[0] * right[1] + left[1] * right[0];
int64_t tt = left[1] * right[1];
char op = ops[start + leftOpCount];
if (op == '&') {
counters[0] += ff + ft;
counters[1] += tt;
} else if (op == '|') {
counters[0] += ff;
counters[1] += tt + ft;
} else {
counters[0] += ff + tt;
counters[1] += ft;
}
}
}
}
return counters[1];
}
Первое измерение dp представляет количество операторов в рассматриваемом выражении. Второе измерение имеет начальный индекс s, где начинается это подвыражение. В третьем измерении всего две записи: одна для ложных подсчетов и одна для истинных подсчетов.
Спасибо вам за разъяснение! Как я уже сказал Мареку Р. ранее, я пока не собираюсь просматривать предоставленный вами код. Я собираюсь посмотреть, смогу ли я усвоить концепции, о которых вы говорите, и сам воплотить их в коде. Если я все еще застряну, я ссылаюсь на ваш код для спасения. Спасибо! Джон
Как бы то ни было, я знал, что конкатенация строк требует много работы, но на тот момент моего путешествия я не мог придумать другого способа проверить, посещал ли я определенную перестановку раньше, без сохранения ее визуального представления.
Большой! Второе предложение в описании проблемы немного прояснило ситуацию. Возможно, вам стоило включить его? «
t,fбудет означатьtrue,falseи ...»