Найти наибольшую арифметически корректную подстроку равную нулю

Не могу правильно решить задачу из ЕГЭ по информатике. Объясните, пожалуйста, в чём я ошибся.

Задача с 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 шт):

Автор решения: Stanislav Volodarskiy

Я вызвал ваше решение с выражением 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 – истина, если последнее слагаемое в формуле содержит нулевой множитель.

На каждой итерации хранятся максимум три выражения-корректных префикса:

  1. самая длинная формула, у которой последний множитель не ноль (но которая имеет шанс стать нулевой в будущем);
  2. самая длинная формула, у которой последний множитель ноль (она обновляет текущий максимум);
  3. формула из одного последнего символа.

Алгоритм работает за линейное время и избегает, как мне кажется, описания большого количества тонких мест.

Я переделал программу, чтобы её можно было тестировать с разными текстами. Для исходного текста её надо запускать так: 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()
→ Ссылка
Автор решения: Intelligent Shade of Blue

Вещи держать в уме:

  • Нулевая последовательность может быть под-последовательностью ненулевой последовательности.

  • Можно "украсть" конечный ноль у ненулевого число. Например, в последовательности 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)))
→ Ссылка
Автор решения: Vitalizzare

В подобных ситуациях помогает разработка через тестирование (т.е. 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', в которых функция, работающая на уровне арифметики может сломаться, не увидев ноль как подстроку.

→ Ссылка
Автор решения: Qwertiy

tio.run

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.

→ Ссылка
Автор решения: Intelligent Shade of Blue

Это 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
→ Ссылка
Автор решения: puffleeck

как насчет того чтобы вжухнуть задачку одной регуляркой? :)

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)
→ Ссылка