Python: Duplicate Encoder — решение задачки с Codewars

Автор: | 05/03/2018
Нет комментариев
 

PythonЗадача

Ссылка на задачу

Оригинал:

The goal of this exercise is to convert a string to a new string where each character in the new string is ‘(‘ if that character appears only once in the original string, or ‘)’ if that character appears more than once in the original string. Ignore capitalization when determining if a character is a duplicate.

Examples:

«din» => «(((»

«recede» => «()()()»

«Success» => «)())())»

«(( @» => «))((«

Вольный перевод:

Цель задачи — сконвертировать переданную в функцию строку в новую строку, где каждый символ новой строки будет являться «(«, если символ в старой строке встречается только один раз, и «)» — если символ в старой строке встречается два и более раз. Символы должны быть регистронезависимы.

Решение

Создадим тестовый скрипт:

#!/usr/bin/env python


def duplicate_encode(word):

    iter = str(word)
    print(iter)     

duplicate_encode('test')

Запускаем, проверяем:

[simterm]

$ ./duplicate_encode.py 
test

[/simterm]

ОК, теперь можно придумывать решение.

Решение не претендует на оригинальность и уж тем более на идеальность или красоту подхода, но раз кодить на Python приходиться редко — то хотя бы такая разминка для мозгов.

На каком-то собеседовании я встречал похожую задачу, идея решения достаточно простая:

  1. создаём пустой список
  2. запускаем цикл, в котором проверяем каждый элемент переданного в аргументе функции слова
  3. каждый элемент проверяем с циклом: если элемента в списке нет — ставим «(«, если есть — ставим «)»

ОК, пробуем:

#!/usr/bin/env python

def duplicate_encode(word):

    # will conatin word from function's argument
    iter_word = str(word)
    # will container already checked items to compare with
    check_list = []
    # will contain brackets
    formatted_list = []

    print('Checking word: {}'.format(iter_word))

    for i in iter_word:
        print('Checking item: {}'.format(i))
        if i not in check_list:
            print('{} not found in the list[], so using ")" symbol'.format(i))
            check_list.append(i)
            i = '('
            formatted_list.append(i)
        else:
            print('{} found in the list[], so using "(" symbol'.format(i))
            check_list.append(i)
            i = ')'
            formatted_list.append(i)

    print('Result: {}'.format(''.join(map(str, formatted_list))))

duplicate_encode('test')

Рассмотрим код построчно:

  1. iter_word = str(word) — приводим input к типу str, сохраняем в переменную iter_word
  2. check_list = [] — создаём пустой список, в который будем сохранять элементы, которые уже проверены и которым будем сверяться дальше в цикле
  3. formatted_list = [] — пустой сисок, который будет содержать символы «(» и «)»
  4. for i in iter_word: — запускаем цикл и проверяем каждый элемент из переменной iter_word
  5. if i not in check_list — в самом начале список check_list у нас пустой, дальше на каждой итерации ищем в нём очередной элемент i
  6. check_list.append(i) — независимо от результата — добавляем уже проверенный элемент в список check_list
  7. i = '(' — раз i не найден в списке check_list — то сохраняем его в formatted_list как «(«
  8. else: i = ')' — если i найден в списке, то сохраняем его в formatted_list как «)»
  9. print('Result: {}'.format(''.join(map(str, formatted_list)))) — и в конце выводим получившийся список formatted_list в виде обычного слова

Проверяем:

[simterm]

$ ./duplicate_encode.py 
Checking word: test
Checking item: t
t not found in the list[], so using ")" symbol
Checking item: e
e not found in the list[], so using ")" symbol
Checking item: s
s not found in the list[], so using ")" symbol
Checking item: t
t found in the list[], so using "(" symbol
Result: )))(

[/simterm]

ОК — работает.

Но вернёмся к задаче.

Во-первых: «Ignore capitalization when determining if a character is a duplicate» — ОК, добавим строковый метод lower():

...
for i in iter_word.lower():
...
duplicate_encode('Test')

Проверяем:

[simterm]

$ ./duplicate_encode.py 
Checking word: Test
Checking item: t
t not found in the list[], so using ")" symbol
Checking item: e
e not found in the list[], so using ")" symbol
Checking item: s
s not found in the list[], so using ")" symbol
Checking item: t
t found in the list[], so using "(" symbol
Result: )))(

[/simterm]

Но тесты в Codewars снова вернут ошибку:

Почему?

Потому что во втором тесте:

...
Test.assert_equals(duplicate_encode("recede"),"()()()")
...

Мы проверяем букву r, её нет, задаём её как «(«, затем проверяем вторую букву — e, не находим её  и тоже сохраняем как «(» — хотя дальше в слове она есть.

Сначала изменим проверочное слово, на котором падает тест, в самом скрипте со слова Test на recede, весь код сейчас выглядит так

#!/usr/bin/env python


def duplicate_encode(word):

    # will conatin word from function's argument
    iter_word = str(word)
    # will container already checked items to compare with
    check_list = []
    # will contain brackets
    formatted_list = []

    print('Checking word: {}'.format(iter_word))

    for i in iter_word.lower():

        print('Checking item: {}'.format(i))
        if i not in check_list:
            print('{} not found in the list[], so using ")" symbol'.format(i))
            check_list.append(i)
            i = '('
            formatted_list.append(i)
        else:
            print('{} found in the list[], so using "(" symbol'.format(i))
            check_list.append(i)
            i = ')'
            formatted_list.append(i)

    print('Result: {}'.format(''.join(map(str, formatted_list))))

    return ''.join(map(str, formatted_list))    
    

duplicate_encode('recede')

Проверяем:

[simterm]

$ ./duplicate_encode.py 
Checking word: recede
Checking item: r
r not found in the list[], so using ")" symbol
Checking item: e
e not found in the list[], so using ")" symbol
Checking item: c
c not found in the list[], so using ")" symbol
Checking item: e
e found in the list[], so using "(" symbol
Checking item: d
d not found in the list[], so using ")" symbol
Checking item: e
e found in the list[], so using "(" symbol
Result: ((()()

[/simterm]

ОК — ошибку воспроизвели: Result: ((()().

Как решить эту проблему? Попробуем использовать слайсинг.

В первом if будем проверять не только наличие значения из переменной i в списке check_list, но и дальше во всём слове, начиная с текущей позиции.

Для этого — добавим пермеменную position:

...
    # count current position in checked word
    position = 0
...

Далее уже в теле цикла — добавляем инкремент на 1:

...
    for i in iter_word.lower():

        position += 1
...

И в первом if добавляем вторую проверку — ... and i not in (iter_word[position:]):

...
        print('Checking item: {}'.format(i))
        if i not in check_list and i not in (iter_word[position:]):
...

Получается следующий код:

#!/usr/bin/env python


def duplicate_encode(word):

    # will conatin word from function's argument
    iter_word = str(word)
    # will container already checked items to compare with
    check_list = []
    # will contain brackets
    formatted_list = []
    # count current position in checked word
    position = 0

    print('Checking word: {}'.format(iter_word))

    for i in iter_word.lower():

        position += 1
        
        print('Checking item: {}'.format(i))
        if i not in check_list and i not in (iter_word[position:]):
            print('{} not found in the list[], so using ")" symbol'.format(i))
            check_list.append(i)
            i = '('
            formatted_list.append(i)
        else:
            print('{} found in the list[], so using "(" symbol'.format(i))
            check_list.append(i)
            i = ')'
            formatted_list.append(i)

    print('Result: {}'.format(''.join(map(str, formatted_list))))

    return ''.join(map(str, formatted_list))    
    

duplicate_encode('recede')

Запускаем, проверяем:

[simterm]

$ ./duplicate_encode.py 
Checking word: recede
Checking item: r
r not found in the list[], so using ")" symbol
Checking item: e
e found in the list[], so using "(" symbol
Checking item: c
c not found in the list[], so using ")" symbol
Checking item: e
e found in the list[], so using "(" symbol
Checking item: d
d not found in the list[], so using ")" symbol
Checking item: e
e found in the list[], so using "(" symbol
Result: ()()()

[/simterm]

ОК!

Пробуем на Codewars:

Без print(), для более полной картины:

Готово — все 4 теста пройдены.

Но! 🙂

Запускаем Attemp — и получаем ошибку при генерировании рандомной строки:

Testing for word: @SSJGkxxacRvQwHOzHvPb
It Should encode ‘())((())((()(()(())((‘: ‘(()((())((()((((())((‘ should equal ‘())((())((()(()(())((‘

Тут она возникает потому что в условии:

...
if i not in check_list and i not in (iter_word[position:]):
...

проверяется iter_word не приведённая к lower().

Изменим в самом начале задание переменной iter_word — приведём всё слово word к lower(), и дальше уже будем оперерировать только символами в нижнем регистре:

def duplicate_encode(word):

    # will conatin word from function's argument
    iter_word = str(word.lower())
    ...

    for i in iter_word: 
 
        position += 1
    ...

Проверяем:

Готово.