В чем ошибка моего решения?

Question

[Vova135798]

Нужно решить задачу: Текстовый файл состоит не более чем из 106 символов X, Y и Z. Определите максимальную длину цепочки вида XYZXYZXYZ... (составленной из фрагментов XYZ, последний фрагмент может быть неполным). Для выполнения этого задания следует написать программу. Ниже приведён файл, который необходимо обработать с помощью данного алгоритма. Ссылка на файл:https://inf-ege.sdamgia.ru/doc/inf/zadanie24/24_de...

Почему-то мое решение выдает неправильный ответ

with open("text.txt", "r") as file:
    s = file.readline()
    k = 1
    kmax = 1
    for i in range(1, len(s)):
        if s[i] != s[i-1]:
            k = k + 1

            if k > kmax :
                kmax = k

        else:
            k = 1

print(kmax)

правильный ответ 13

Answer 1

[MinTnt]

with open('text.txt', 'r') as f:
	import re
	print(max([len(i[0]) for i in re.findall('((XYZ)+(X|XY)?)', f.read())]))

Это с учётом условия

"последний фрагмент может быть неполным"

т.е. я понял он может быть просто как 'XY, 'X'. По итогу вышло, что максимальная длина цепочки 13. Значит она будет иметь примерный вид как "XYZXYZXYZXYZX".

Только мне чуть кажется, что я точно что-то не правильно задал в условии для поиска, ну.. если что призову всезнающего.

Update: Хах, я ток ща перечитывая условие, заметил заметку "правильный ответ 13"

Comments

[Алан Гибизов]

Я, конечно, тоже накропал свой брутфорс этой задачки.
Он получился в 2.5 раза медленнее этого варианта. Поэтому публиковать его как ответ не буду, тут прилеплю для истории… пусть люди узнают, как можно, но не надо делать :)))

spoiler

pattern = ['X', 'Y', 'Z']
counter = 0
next_string = ''
sizes = []
filepath = r'text.txt'

with open(filepath, 'r') as file:
    file = file.read()
    for element in file:
        if element == pattern[counter]:
             if counter < 2:
                 counter += 1
             else:
                 counter = 0
             next_string += element
             
        else:
            sizes.append(len(next_string))
            next_string = ''
            counter = 0
            
print(max(sizes))

По времени получается мой вариант 0.25 сек, а в ответе ~0.1 сек.

[MinTnt]

Алан Гибизов, выглядит загадочно (т.к. много переменных)

а в ответе ~0.1 сек.

Вроде нигде не уточнялось про время затребуемое для задачи.

А вообще, просто когда сел за неё, глянул, и решил, что здесь нужно использовать import re, по привычке.

P.s. поздравляю с получением "Куратор раздела"

[MinTnt]

Алан Гибизов, я пока посмотрел почему код медленнее. Методы работы похожи:
Создание списка со значениями длины цепочек. Просто у тебя оно по этапно каждый раз добавляет по 1 символу в строку пока идёт цикл. У меня благодаря функции re.findall() оно сразу ищет конструкции. Т.е. не добавляет по одному символы, а поиск идёт сразу с трёх XYZ (и более) и оканчиваясь X XY

[Алан Гибизов]

MinTnt, у меня была странная мысль - сделать split по XYZ и считать полученные пустые элементы списка - это и есть ведь XYZ. Но не дотянул мысль…

[MinTnt]

Алан Гибизов, вообще, я тоже думал что-то этом направлении. Но вот сейчас решил задуматься с реализацией через split(), со всеми исходящими от этого минусами, в принципе можно, но из-за моего желания минимализма - уместить всё в одну строчку сложно

[longclaps]

Алан Гибизов, MinTnt,

with open('text.txt', 'r') as f:
    print(max(map(len, f.read().replace('Y', 'Z').split('Z'))))

Хех, однострочечники )

[MinTnt]

longclaps, А погодите-ка.. Это же вроде выгодит совсем не то. К примеру расскладываем поэтапно.
f.read() ==
XXXYYXXYZXXYXZYXXXYYXXXXXXXXYZ
f.read().replace('Y', 'Z') ==
XXXZZXXZZXXZXZZXXXZZXXXXXXXXZZ
f.read.replace('Y', 'Z').split('Z')

['XXX', '', 'XX', '', 'XX', 'X', '', 'XXX', '', 'XXXXXXXX', '', '']

Итог: По итогу мы получаем лишь самую длинную цепочку повторений "X". Что не соотвествует задачи -

Найти цепочки которые выглядят по типу XYZ и заканчиваются не полностью.

[longclaps]

MinTnt, да, я перешел по ссылке из сегодняшнего вопроса и не читал этот. Бывает. Сейчас напишу решение к этому.

[MinTnt]

longclaps, Жду. Я про это задание вообще и забыл за это время. Ну точнее я про то, что сейчас вижу некоторые пути оптимизации и тд

[longclaps]

MinTnt, вот императивочка

s = 'XXXYYXXYZXXYXZYXXXYYXXXXXXXXYZ'
a, best, cnt = 88, 0, 0
for i,b in enumerate(map(ord, s)):
    if (b - a) % 3 == 1:
        cnt += 1
        a = b
    else:
        if best < cnt:
            best = cnt
        print(f'{s[:i-cnt]} "{s[i-cnt:i]}" {s[i:]} {cnt}')
        a, cnt = 88, int(b==88)
if best < cnt:
    best = cnt
print(best)

[MinTnt]

longclaps, о, интересно, ща ещё закомпилирую в одностоойный код

[MinTnt]

MinTnt, но всё же на обработку оно занимает больше времени -
0.5650322437286377

[longclaps]

MinTnt, ну да. Поправил баг, сделал визуализацию.

Answer 2

[Rsa97]

Вам надо искать цепочки XYZXYZ, а вы ищете цепочки, где следующий символ не совпадает с предыдущим. То есть цепочка XYXY вашей программой тоже будет найдена.

Comments

[Vova135798]

А как это сделать?

Answer 3

[Николай]

Может быть как-то так

with open("text.txt", "r") as file:
    s = file.readline()
    k = 0
    kmax = 0
    for i in range(1, len(s)-3):
        if s[i:i+3] == 'XYZ':
            k = k + 1
            i+=2

            if k > kmax :
                kmax = k

        else:
            k = 0

print(kmax)

Comments

[Алан Гибизов]

Это у меня не сработало. Не разбирался, почему.

[Николай]

Алан Гибизов, это точно работает

with open("text.txt", "r") as file:
    s = file.readline()
    i=0
    k = 0
    kmax = 0
    while i< (len(s)-1):
        if s[i:i+3] == 'XYZ':
            k = k + 1
            i+=2

            if k > kmax :
                kmax = k

        else:
            k = 0
        i+=1

print(kmax)

[Алан Гибизов]

Николай, у меня возвращает 4 вместо 13. Может, я что-то не так делаю?