- ВКонтакте
- РћРТвЂВВВВВВВВнокласснРСвЂВВВВВВВВРєРСвЂВВВВВВВВ
- РњРѕР№ Р В Р’В Р РЋРЎв„ўР В Р’В Р РЋРІР‚ВВВВВВВВРЎР‚
- Viber
- Skype
- Telegram
Найти наибольшую арифметически корректную подстроку равную нулю
Не могу правильно решить задачу из ЕГЭ по информатике. Объясните, пожалуйста, в чём я ошибся.
Задача с KompEGE:
№ 17685 Пересдача 04.07.24 (Уровень: Гроб)
Текстовый файл состоит из десятичных цифр, знаков «+» и «*» (сложения и умножения). Определите максимальное количество символов в непрерывной последовательности, являющейся корректным арифметическим выражением с целыми неотрицательными числами (без знака), значение которого равно нулю. В этом выражении никакие два знака арифметических операций не стоят рядом, порядок действий определяется по правилам математики. В записи чисел отсутствуют незначащие (ведущие) нули. В ответе укажите количество символов.
Ответ: 169
Мой код:
s = open("24_17641.txt").read()
while "**" in s or "++" in s or "*+" in s or "+*" in s:
if "**" in s:
s = s.replace("**", "* *")
if "++" in s:
s = s.replace("++", "+ +")
if "*+" in s:
s = s.replace("*+", "* +")
if "+*" in s:
s = s.replace("+*", "+ *")
s = s.split()
print(s)
a = [i[1:-1] for i in s if i != "+" and i != "*"]
a = a[1:-1]
mx = 0
for i in a:
if eval(i) == 0:
mx = max(mx, len(i))
print(mx)
Ответы (6 шт):
Я вызвал ваше решение с выражением 0*0+1*1
, получил ответ 0. А правильный ответ 3 для выражения 0*0
. Ошибка в алгоритме.
NB Это вторая попытка. Первая строилась на анализе выражений "сверху вниз" и ломалась на 10+1
и 10*1
. Если обработку 10+1
можно было починить, глядя на предыдущее слагаемое, то 10*1
куда хуже. Оно не чинится, если мы разбили выражение на слагаемые и коэффициенты. Я бросил этот подход и сделал по другому.
Класс Expr
принимает последовательные символы (e.update(с)
) и содержит следующие поля:
e.length
– длина текста, пока он синтаксически правильный;e.valid_prefix
– истина, если текст может быть продолжен до правильной формулы с нулевым значением;e.valid_zero
– истина, если текст прямо сейчас представляет правильную формулу с нулевым значением;e.last_term_is_zero
– истина, если последнее слагаемое в формуле содержит нулевой множитель.
На каждой итерации хранятся максимум три выражения-корректных префикса:
- самая длинная формула, у которой последний множитель не ноль (но которая имеет шанс стать нулевой в будущем);
- самая длинная формула, у которой последний множитель ноль (она обновляет текущий максимум);
- формула из одного последнего символа.
Алгоритм работает за линейное время и избегает, как мне кажется, описания большого количества тонких мест.
Я переделал программу, чтобы её можно было тестировать с разными текстами. Для исходного текста её надо запускать так: cat 24_17641.txt | python zero-expr.py
.
class Expr:
def __init__(self):
self.length = 0
self.valid_prefix = True
self.valid_zero = False
self.last_term_is_zero = False
self._last_factor = '' # '' for empty last factor
# '0' for zero last factor
# '1' for nonzero last factor
def update(self, char):
if self.valid_prefix and self._update(char):
self.length += 1
self.valid_zero = self.last_term_is_zero and self._last_factor != ''
else:
self.valid_prefix = False
self.valid_zero = False
def _update(self, char):
if char == '+':
if self._last_factor == '':
return False # no digit before `+` sign
if not self.last_term_is_zero:
return False # whole expression is above zero
self.last_term_is_zero = False
self._last_factor = '' # start new factor
return True
if char == '*':
if self._last_factor == '':
return False # no digit before `*` sign
self._last_factor = '' # start new factor
return True
if char == '0':
if self._last_factor == '':
self._last_factor = '0'
self.last_term_is_zero = True
return True
return self._last_factor != '0' # leading zero before digit
if '1' <= char <= '9':
if self._last_factor == '':
self._last_factor = '1' # nonzero last factor
return True
return self._last_factor != '0' # leading zero before digit
return False # unknown character
def main():
with open(0) as f:
text = f.read()
max_length = 0
exprs = []
for c in text:
exprs.append(Expr())
for e in exprs:
e.update(c)
if e.valid_prefix and e.valid_zero:
max_length = max(max_length, e.length)
new_exprs = []
for e in exprs:
if e.valid_prefix:
new_exprs.append(e)
break
for e in exprs:
if e.valid_prefix and e.last_term_is_zero and e not in new_exprs:
new_exprs.append(e)
break
exprs = new_exprs
print(max_length)
main()
Вещи держать в уме:
Нулевая последовательность может быть под-последовательностью ненулевой последовательности.
Можно "украсть" конечный ноль у ненулевого число. Например, в последовательности
12340+567*0
макс нулевая последовательность это0+567*0
.Если нет ненулевых выражений, но есть цифра "0" в тексте, то это и есть макс последовательность.
Спасибо @Vitalizzare за находку ошибок в моем коде.
Итак, исправленный код будет:
import re
def find_longest_zero_expr(text):
longest = "0" if "0" in text else ""
for expr in re.split("[*+]{2,}", text.strip("*+")):
if len(expr) < len(longest): continue
zeros = []
for prod in expr.split('+'):
if "*0*" not in '*' + prod + '*':
parsed = "+".join(zeros)
if len(parsed) > len(longest): longest = parsed
pos = prod.find("0*")
if pos > 0:
# take "0*..." sub-sequence from non-zero product
zeros = [prod[pos:]]
elif prod.endswith('0'):
# take trailing '0' from non-zero product
zeros = ["0"]
else: zeros = []
else: zeros += [prod]
parsed = "+".join(zeros)
if len(parsed) > len(longest): longest = parsed
return longest
text = open("9rWpROaef.txt").read()
print(len(find_longest_zero_expr(text)))
В подобных ситуациях помогает разработка через тестирование (т.е. Test-Driven Development, TDD). Это дает возможность изучить объект, с которым вы работаете, задавая себе вопросы: Что в принципе возможно? Какой должен быть результат? Какие пограничные случаи? и т.п. Составим, для примера, таблицу возможных случаев:
test_cases = [
# [given, expected]
['', ''],
['+', ''],
['*', ''],
['1', ''],
['0', '0'],
['0*', '0'],
['*0', '0'],
['*0*', '0'],
['0+1', '0'],
['0+0', '0+0'],
['0*0', '0*0'],
['10', '0'],
['101', '0'],
['10+0', '0+0'],
['10*1+0', '0*1+0'],
]
В каком виде и со скольких кейсов начать - решаем по ситуации. Здесь я оставил то, что мне показалось интересным, а для самоконтроля оставил в качестве результата искомую подстроку вместо её длины. Начать можно с первых пары строк, дополняя таблицу по мере разработки с целью "сломать" функцию при тестировании (т.е. найти такой случай, когда функция ошибается):
def test_func(func: Callable[[str], int], cases: list[list[str]], show_ok: bool = False):
for count, (given, expected) in enumerate(cases, start=1):
correct_len = len(expected)
result_len = func(given)
if correct_len != result_len:
print(f'FAILED in case {count}: {text!r}')
elif show_ok:
print(f'OK in case {count}: {text!r}')
Почему это хорошо? Потому что в ситуации, когда мы работаем одновременно на двух уровнях, - извлечение арифметических выражений против извлечения подстрок, - легко соскользнуть в один из них, который понятен и алгоритмически привлекателен (арифметика), забыв о втором (извлечение подстрок). И как результат, можем упустить какой-то нюанс. Например, искомая подстрока в заданном файле выглядит так:
substring = '0+32373*0*60611+0*0*29472+0+49966*47103*0*0*0+0+0+0+0*54026*0+22544*0*0*0+0+0+0*0*0*0*0*0+0+0+0*0*29624+0+0+60153*0+0+0*52823*0*0*0*0*0*0*0+0+0*0+0+0+0*17505+0+0*0*0*0+0'
assert len(substring) == 169
assert eval(substring) == 0
Но она является частью большей арифметически корректной строки:
big_substring = '630+32373*0*60611+0*0*29472+0+49966*47103*0*0*0+0+0+0+0*54026*0+22544*0*0*0+0+0+0*0*0*0*0*0+0+0+0*0*29624+0+0+60153*0+0+0*52823*0*0*0*0*0*0*0+0+0*0+0+0+0*17505+0+0*0*0*0+0'
Обратите внимание на первое слагаемое, благодаря которому третья снизу строка вашего кода if eval(bit_substring) == 0: ...
отбракует всю строку как неподходящую.
Но ситуация там гораздо хуже. Запишем ваш код в виде функции и проверим её на простых кейсах:
def get_length_of_biggest_zero_string(s: str) -> int:
while "**" in s or "++" in s or "*+" in s or "+*" in s:
if "**" in s:
s = s.replace("**", "* *")
if "++" in s:
s = s.replace("++", "+ +")
if "*+" in s:
s = s.replace("*+", "* +")
if "+*" in s:
s = s.replace("+*", "+ *")
s = s.split()
a = [i[1:-1] for i in s if i != "+" and i != "*"]
a = a[1:-1]
mx = 0
for i in a:
if eval(i) == 0:
mx = max(mx, len(i))
return mx
test_func(get_length_of_biggest_zero_string, test_cases)
# FAILED on case 5: '0'
# FAILED on case 6: '0*'
# FAILED on case 7: '*0'
# FAILED on case 8: '*0*'
# FAILED on case 9: '0+1'
# FAILED on case 10: '0+0'
# FAILED on case 11: '0*0'
# FAILED on case 12: '10'
# FAILED on case 13: '101'
# FAILED on case 14: '10+0'
# FAILED on case 15: '10*1+0'
Как видим, ваш алгоритм удалось сломать на простых случаях, начиная со строки '0'
. Предположу, что серьёзные проблемы начинаются с определения списка a
, где, как мне кажется, вы хотите собрать арифметически корректные выражения после чистки идущих подряд арифметических знаков. После тестов, вы могли бы продолжить работу с этого места, например, заменив сомнительное i[1:-1]
на i.strip('+*')
и заменив попытку отбросить возможные пустые строки a = a[1:-1]
каким-то фильтром:
a = [stripped_item for i in s if (stripped_item:=i.strip('+*'))]
После такой замены, функция будет ошибаться реже. Но вы увидите эти ошибки, если, наполняя кейсы, думали на уровне подстрок, а не арифметических операций:
FAILED on case 9: '0+1'
FAILED on case 12: '10'
FAILED on case 13: '101'
FAILED on case 14: '10+0'
FAILED on case 15: '10*1+0'
Здесь я позволю себе остановится и переадресовать к ранее опубликованным ответам. Рекомендую читать не конечный результат, а историю изменений, чтобы на живом примере увидеть важность и пользу разработки через тестирование:
P.S. Пример, как мы можем составлять кейсы через вопросы, продвигаясь от обратного: допустим, что у нас хорошая строка (арифметически корректная), применив к которой функцию eval
мы получим ноль. Какой у неё самый простой вид? С чего она может начинаться? Чем может заканчиваться? Что может стоять перед ней и после неё? Будет ли она хорошей после дополнения чем-то в начале или конце? А изменится ли её результат как арифметического выражения?
Задавая себе такие вопросы, мы видим простейший случай '0'
и производные от него - '10'
, '101'
, '10+1'
, '10*1'
, в которых функция, работающая на уровне арифметики может сломаться, не увидев ноль как подстроку.
import re
print(
max((len(m.group()) for m in re.finditer(
r'0[+0]*(?<!\+)',
re.sub(
r'[*\d]+',
lambda m:
'0' * len(m.group()) if re.search(r'\*0|\b0\*|^0$', m.group())
else 'X' + m.group()[-1],
re.sub(
r'[+*]{2,}(?:0*(?=\d)|$)|(?<=\b0)(?:0+(?=\d)|$)',
' ',
re.sub(r'\b00*(?=\d)', '0 ', input())
)
)
)), default=0)
)
На приведённом входном файле получается 169.
Это c++ версия, которая работает на той же основе как моя питон версия.
zero.cpp
#include <algorithm>
#include <fstream>
#include <iostream>
#include <regex>
#include <sstream>
#include <string>
auto find_longest_zero_expr(std::string text)
{
text.erase(0, text.find_first_not_of("*+"));
text.erase(text.find_last_not_of("*+") + 1);
int max_len = text.contains("0");
std::regex re{ "[*+]{2,}" };
std::sregex_token_iterator it{ text.begin(), text.end(), re, -1 }, end;
for (; it != end; ++it)
{
if (auto expr = it->str(); expr.size() > max_len)
{
int new_len = 0;
std::stringstream ss{ expr };
for (std::string prod; std::getline(ss, prod, '+');)
{
if (('*'+prod+'*').find("*0*") == prod.npos)
{
max_len = std::max(max_len, new_len);
if (auto pos = prod.find("0*"); pos != prod.npos)
new_len = prod.size() - pos; // take "0*..." sub-seq from non-zero product
else new_len = prod.ends_with('0'); // take trailing '0' from non-zero product
}
else new_len += prod.size() + !!new_len; // !!new_len for the '+' sign
}
max_len = std::max(max_len, new_len);
}
}
return max_len;
}
int main()
{
std::string text;
std::getline(std::ifstream{"./9rWpROaef.txt"}, text, '\0');
std::cout << find_longest_zero_expr(text) << std::endl;
return 0;
}
Компилируется с:
g++ -O3 -std=c++23 zero.cpp -o zero
как насчет того чтобы вжухнуть задачку одной регуляркой? :)
RegEx:
/(?:
(?: (?# первый "нулевой мультик" - группа множителей с как минимум 1м нулём )
(?:[0-9]+\*)*
(?<![0-9]) (?# без хвоста)
0+
(?![0-9]) (?# и без ведущего)
(?:\*[0-9]+)*
)
(?: (?# все остальные мульты )
\+
(?:[0-9]+\*)*
0+
(?![0-9]) (?# и без прочих ведущих )
(?:\*[0-9]+)*
)*
)/gx (?# флаги - Global, eXtended )
JavaScript:
let s = `999***0*123*0*2*4*8*0****630+32373*0*60611+0*0*29472+0+49966*47103*0*0*0+0+0+0+0*54026*0+22544*0*0*0+0+0+0*0*0*0*0*0+0+0+0*0*29624+0+0+60153*0+0+0*52823*0*0*0*0*0*0*0+0+0*0+0+0+0*17505+0+0*0*0*0+0
['*100000*1+0*', '0*1+0'],
['1000001', '0'],
['10+00002', '0+0'], # can be skipped, no leading zero expected
'1*0+00002'
['0', '0'],
['0*', '0'],
['*0', '0'],
['*0*', '0'],
['0+1', '0'],
['0+0', '0+0'],
['0*0', '0*0'],
['10', '0'],
['101', '0'],
['10+0', '0+0'],
['10*1+0', '0*1+0'],`;
let p = /(?:(?:(?:[0-9]+\*)*(?<![0-9])0+(?![0-9])(?:\*[0-9]+)*)(?:\+(?:[0-9]+\*)*0+(?![0-9])(?:\*[0-9]+)*)*)/g;
for(e of s.match(p))
{
console.log(e.length + ' < ' + e)
}
и наконец Python:
import re
s = '999***0*123*0*2*4*8*0****630+32373*0*60611+0*0*29472+0+49966*47103*0*0*0+0+0+0+0*54026*0+22544*0*0*0+0+0+0*0*0*0*0*0+0+0+0*0*29624+0+0+60153*0+0+0*52823*0*0*0*0*0*0*0+0+0*0+0+0+0*17505+0+0*0*0*0+0';
p = "(?:(?:(?:[0-9]+\*)*(?<![0-9])0+(?![0-9])(?:\*[0-9]+)*)(?:\+(?:[0-9]+\*)*0+(?![0-9])(?:\*[0-9]+)*)*)";
for e in re.findall(p, s):
print(len(e), ' < ', e)