@Treyrem

Необходимо решить задачу для курса и понять в чем ошибка моего кода и мышления?

Понимаю, что различные виды решения этой задачи есть в интернете, но не могу понять почему мой код тупо обрывается на пол пути. И в целом почему мой метод решения не верен и не работает. Изначально хотела написать говно код, который проверяет сначала первый символ на повторение (сравнивает i и i+1) и в случае отсутствия повторения обрывался и продолжал операцию с уже нынешнего i+1 и каким-то образом додумалась до цикла в цикле. В программировании совсем уж новичок, помогите пожалуйста
Мой код:
a=input().lower()

i=-1
j=0
s=len(a)-1

while i<=s:
  i=i+1
  j=j+1
  cnt=1
  while i<s:
    if a[i]==a[j]:
      i+=1
      j+=1
      cnt+=1
    if a[i]==a[s]:
      break
      print(a[i],cnt,sep="",end='')
    if a[i] != a[j]:
      print(a[i],cnt,sep="",end='')
      break


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

Кодирование осуществляется следующим образом:
s = 'aaaabbсaa' преобразуется в 'a4b2с1a2', то есть группы одинаковых символов исходной строки заменяются на этот символ и количество его повторений в этой позиции строки.

Напишите программу, которая считывает строку, кодирует её предложенным алгоритмом и выводит закодированную последовательность на стандартный вывод. Кодирование должно учитывать регистр символов.

Sample Input 1:

aaaabbcaa
Sample Output 1:

a4b2c1a2
Sample Input 2:

abc
Sample Output 2:

a1b1c1
  • Вопрос задан
  • 233 просмотра
Пригласить эксперта
Ответы на вопрос 4
AlexNest
@AlexNest Куратор тега Python
Работаю с Python/Django
Алгоритм следующий:
  1. В новый список (назовем его letters_count) помещаете список вида [<первая буква>, 1];
  2. Удаляете первую букву из строки;
  3. Далее в цикле по строке сравниваете, совпадает ли текущая буква с буквой в последнем списке letters_count;
  4. Если да - увеличиваете значение числа на единицу;
  5. В противном случае - добавляете новый список по аналогии с первым;
  6. преобразуете letters_count в строку

Безусловно, может быть более элегантное решение, но это тоже вполне рабочее.

from random import randint, choice
def encode_dna(dna:str) -> str:
    if not dna:
        return ''
        
    dna_letters_list = list(dna.lower())
    letters_count = []
    
    letters_count.append([dna_letters_list[0],1])
    dna_letters_list.pop(0)

    for letter in dna_letters_list:
        if letter == letters_count[-1][0]:
            letters_count[-1][1] += 1
        else:
            letters_count.append([letter,1])

    for count in enumerate(letters_count, start=0):
        index,count = count
        string = ''.join(map(str,count))
        letters_count[index] = string


    encoded_dna = ''.join(letters_count)        
 

    return encoded_dna




if __name__ == '__main__':
    alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
    for i in range(10):
        dna = [choice(alphabet) for _ in range(randint(1,10))]
        dna_str = ''.join(dna)
        
        print(dna_str,'->',encode_dna(dna_str))

Вывод:
c -> c1
ffdcfbeg -> f2d1c1f1b1e1g1
fgfbebbcbb -> f1g1f1b1e1b2c1b2
ffefaedac -> f2e1f1a1e1d1a1c1
g -> g1
ecbcddf -> e1c1b1c1d2f1
b -> b1
f -> f1
ec -> e1c1
fgcgcg -> f1g1c1g1c1g1
Ответ написан
seven5674
@seven5674
Старый я уже что бы что-то в себе менять
UPD
import re

s = "llldddrrrwwwwttttgggglllleeeeddddddddd"
f = re.findall(r"((\w)+?(?!\2))", s)
d = [w + "" + str(len(l)) for l, w in f]
print(s)
print(''.join(d))


и...
llldddrrrwwwwttttgggglllleeeeddddddddd
l3d3r3w4t4g4l4e4d9


Плохой вариант

s = "llldddrrrwwwwttttgggg"
d = {}

for i in s:
    d.setdefault(i, 0)
    d[i] += 1

g = [''.join(map(lambda i: str(i), item)) for item in d.items()]

print(s)
print(''.join(g))

и...
llldddrrrwwwwttttgggg
l3d3r3w4t4g4

Ответ написан
trapwalker
@trapwalker Куратор тега Python
Программист, энтузиаст
Александр Нестеров привёл решение на псевдокоде, но вопрос под тегом Питон... Дело в том, что питон не поощряет изменение входных строк в решениях такого рода.
Поэтому приведу своё решение перфекциониста=) Если кто укажет как его улучшить, буду рад=)
Возможно новичку применённые там трюки будут сложны в понимании или даже местами вредны, но точно познавательны.

import unittest
import typing

_VARIANTS = []  # Сюда попадут все решения, которые нужно тестировать
# А это декоратор, которым нужно пометить все претенденты на решение
solution = lambda f: _VARIANTS.append(f) or f

EXAMPLES = [
    ('', ''),
    ('a', 'a1'),
    ('abc', 'a1b1c1'),
    ('aaaabbca', 'a4b2c1a1'),
]


@solution
def encode(inp: str) -> str:
    """Самое простое решение
    Минусы: громоздко и многословно 
    (зато прозрачно и понятно, без магии и выкрутасов)
    """
    if not inp:
        return ''
    count = 1
    current = inp[0]
    res = []
    for c in inp[1:]:
        if c == current:
            count += 1
        else:
            res.append(f'{current}{count}')
            count = 1
            current = c
    
    res.append(f'{current}{count}')
    return ''.join(res)       


def encode_stream(inp: typing.TextIO) -> typing.Iterator:
    """Потоковое решение. 
    С помощью него можно без затрат памяти кодировать файлы любого размера
    Минусы: нет, если вам нужно закодировать гигабайты. 
    Ну или готов поспорить на эту тему, если вы не согласны.=)
    """
    current = inp.read(1)
    count = len(current)
    while current:
        c = inp.read(1)
        if c == current:
            count += 1
        else:
            yield f'{current}{count}'
            current = c
            count = len(current)


@solution
def encode_string_by_stream(inp: str) -> str:
    """Обёртка для использования потокового кодирования из строки"""
    import io
    return ''.join(encode_stream(io.StringIO(inp)))


@solution
def encode_elegant(s: str) -> str:
    """Довольно элегантное решение на словаре от @seven5674.
    К сожалению в оригинальном варианте неверное, но я 
    исправил и отрефакторил.
    Минусы: запутанное и непрозрчное, зато короткое"""
    d = {}
    g = 1
    for c in s:
        g = d.get((c, g), 0) and g or g + 1
        d[c, g] = d.get((c, g), 0) + 1

    return ''.join([f'{k[0]}{v}' for k, v in d.items()])


@solution
def encode_by_regexp(s: str) -> str:
    """Решение на регекспах от @seven5674, 
    я лишь чуть отформатировал и отрефакторил.
    Минусы: регексп поведёт себя довольно непредсказуемо на больших данных,
    к тому же регекспы читать умеют не все. 
    Но автор умеет в регекспы лучше, чем в питон, видимо с js пришел.
    """
    import re
    return ''.join(
        f'{w}{len(l)}' 
        for l, w in 
        re.findall(r"((\w)+?(?!\2))", s)
    )
    

#############################################################################
## Дальше идёт инфраструктура для тестирования решений
    
class Test(unittest.TestCase):
    """Автоматический тест решений.
    Претенденты на решение должны быть помечены декоратором @solution
    Примеры берутся из списка EXAMPLES.
    """

    def closure(func, arg, res):
        """Временная функция, которая делает тест.
        Она формирует каждый раз новую функуию-замыкание, которая будет тестировать
        оережной кейс.
        """
        def test(self):
            f"""Тест функции {func.__name__}({arg!r})"""
            self.assertEqual(func(arg), res, msg=f'Func {func.__name__}({arg!r})')
        return test
    
    # Перебираем все варианты реализаций:
    for f in _VARIANTS:
        # Перебираем все предлженные эталонные римеры:
        for case_num, case in enumerate(EXAMPLES):
            # Создаём новую функуию теста и добавляем ее в класс теста как метод.
            locals()[f'test_{f.__name__}__{case_num}'] = closure(f, *case)

    # Удаляем из контекста класса лишние переменные
    del(closure, f, case_num, case)


if __name__ == '__main__':
    unittest.main(verbosity=3)


UPD: Обновил код, включив туда решения seven5674 и valerr007
Кстати, решение valerr007 проваливает тест с "a" на входе. Возвращает пустую строку. Ну и много претензий к коду.
Ответ написан
@valerr007
a = input("Input: ").lower()
def f(a):
    b = []
    count = 1
    for i in range(1,len(a)):

        if i == len(a)-1:
            if a[i]!= a[i-1]:
                b.extend([a[i-1],str(count),a[i],str(1)])
            else:
                count += 1
                b.extend([a[i],str(count)])

        elif a[i-1] == a[i]:
            count += 1
            continue

        elif a[i] != a[i-1]:
            b.extend([a[i-1],str(count)])
            count = 1

    print("".join(b))

f(a)
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы
24 нояб. 2024, в 21:55
200000 руб./за проект
24 нояб. 2024, в 21:41
1000 руб./за проект
24 нояб. 2024, в 21:19
35000 руб./за проект