5

Система проверки сайта не принимает решение, пожалуйста подскажите где ошибка.

Собственно задача:

1002.Телефонные номера

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ

В современном мире вы встречаетесь с огромным количеством телефонных номеров, которые со временем становятся всё длиннее и длиннее. И вам приходится запоминать эти номера. Одним из простых способов запоминания является сопоставление букв каждой цифре, как показано на следующем рисунке:

1 ij    2 abc   3 def
4 gh    5 kl    6 mn
7 prs   8 tuv   9 wxy
        0 oqz

Таким образом, каждому слову или группе слов может быть сопоставлен уникальный номер, так что можно запоминать слова вместо телефонных номеров. Очевидно, есть особый шарм в том, чтобы найти простую взаимосвязь между словом, используемым для запоминания телефонного номера, и владельцем этого номера. Так, телефонный номер 941837296 вашего друга, играющего в шахматы, может быть прочитан как WHITEPAWN (белая пешка), а номер 2855304 Вашего любимого учителя может быть прочитан как BULLDOG (бульдог).

Напишите программу, находящую самую короткую последовательность слов (имеющую наименьшее количество слов), которая соответствует заданному номеру телефона и заданному списку слов. Соответствие описано на рисунке выше.

Исходные данные

Ввод состоит из набора тестов. Первая строка каждого теста содержит номер телефона, к которому нужно подобрать мнемонику. Номер состоит не более чем из 100 цифр. Вторая строка содержит общее количество слов в словаре (максимум 50 000). Каждая из оставшихся строк содержит одно слово, состоящее не более чем из 50 строчных латинских букв. Общий размер ввода не превосходит 300 килобайт. Последняя строка ввода содержит число −1.

Результат

Каждая строка вывода должна содержать кратчайшую последовательность слов, найденную вашей программой. Слова должны быть разделены одиночными пробелами. Если для входных данных нет решения, соответствующая строка вывода должна содержать текст No solution.. Если существует несколько решений, имеющих одинаковое количество слов, можете выбрать любое из них.


Ввод и вывод данные авторами для примера:

7325189087
5
it
your
reality
real
our
4294967296
5
it
your
reality
real
our
-1
# Ожидаемый результат  
reality our
No solution.

Мои вводные для теста:

2272583262772
11
ba
ra
ku
k
ss
u
ma
da
m
a
ssa
-1

По логике ответ должен быть

ba ra ku da ma ssa

Но это решение почему-то в список возможных не попадает.
Причем если ma расположить после da то это решение находится.
Вот список решений из которых идет выбор оптимального:

['ba', 'ra', 'ku', 'da', 'm', 'a', 'ss', 'a']
['a', 'a', 'ra', 'ku', 'da', 'm', 'a', 'ss', 'a']

И соответственно оптимальным код считает:

ba ra ku da m a ss a

Ну и соответственно валидатор не принимает это решение.
Подскажите пожалуйста где косяк

Мое решение:

keyboard = {'1': 'ij', '2': 'abc', '3': 'def',
            '4': 'gh', '5': 'kl', '6': 'mn',
            '7': 'prs', '8': 'tuv', '9': 'wxy',
            '0': 'oqz'}

while True:
    phone_num = input()
    solutions = []
    if phone_num == '-1':
        break
    phone_len = len(phone_num)
    words = [input() for _ in range(int(input()))]
    collector = []
    for word in words:
        if len(word) > phone_len:
            continue

        solution = []
        for i in range(len(word)):
            if word[i] not in keyboard[phone_num[i]]:
                break

        else:
            solution.append(word)
            test_solution = []

            while test_solution != solution:
                test_solution = solution.copy()
                raw_solution = ''.join(solution)
                len_solution = len(raw_solution)
                new_words = [item for item in words if len(item) <= phone_len - len_solution]
                if new_words:
                    for item in new_words:
                        raw_solution = ''.join(solution)
                        len_solution = len(raw_solution)
                        test_string = raw_solution + item
                        len_test_string = len(test_string)
                        if len_test_string > phone_len:
                            continue
                        for s in range(len_solution, len_test_string):
                            if test_string[s] not in keyboard[phone_num[s]]:
                                break
                        else:
                            solution.append(item)

            solutions.append(solution)

    if solutions:
        solutions.sort(key=lambda g: len(g))
        print(*solutions[0])
    else:
        print('No solution.')
13
  • Если я правильно понимаю, то данный код фиксирует только первое слово в каждом потенциальном решении, а для оставшейся части номера словарь перебирается по порядку. Но таким образом можно упустить лучшее решение.
    – MBo
    2 окт 2018 в 9:36
  • Немного не так, там получается перебор всех слов с каждым словом (там вложенный цикл) и фиксируется (в этом видимо и косяк) сочетание из 2х слов. Впринципе, здесь скорее проблема с алгоритмом нежели с кодом. Никак не могу дотумкать как заставить программу проверить все возможные варианты решения при этом не словив исключение. 2 окт 2018 в 9:40
  • Пусть словарь - буквы. Тогда для номера 145 верхний уровень даст начальный список i, второй цикл найдёт ig, потом igk и уже не будет проверять ih, igl и т.п.
    – MBo
    2 окт 2018 в 9:52
  • вот на таких вводных ` 12345 5 iad i adgk g k -1` он выдает i adgk но боюсь что, если-бы оптимальное решение было длиннее то оно не попало-бы туда 2 окт 2018 в 9:54
  • 1
    У вас в скрипте есть еще одна ошибка. Если слова например, будут ['reality', 'ityour', 'your', 'real', 'ouq', 'it'], то правильной комбинацией будут real ityour, у вас же он выдаст только reality как правильный ответ
    – Axenow
    6 окт 2018 в 2:35

2 ответа 2

4
+100

Общий принцип решения:

Пусть N – длина телефонного номера.

Словарь представим как список из M слов.

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

Затем создаём квадратную матрицу размерности N+1 x N+1 (Я предполагаю, что индексы везде начинаются с 0).

Каждая ячейка (i,j) = k матрицы означает, что у нас есть слово под номером k из словаря такое, что оно совпадает с частью i .. j-1 цифр телефона.

Заполним все её ячейки значением -1. Это будет обозначать, что у нас нет такого слова.

Затем в цикле по всем словам проверяем, к какой части телефонного номера они подходят и заполняем матрицу.

Затем поиском в ширину находим путь в нашей матрице из 0 в N.

Если путь найден, слова из словаря под значениями ячеек пути будут решением задачи, иначе "No solution."

Время заполнения матрицы O(NxM). Время поиска в ширину O(NxN).

Не самый оптимальный способ:

n = len(phone_num)
m = int(input())
words = [input() for _ in range(m)]

# Создаём матрицу (n+1) x (n+1)
a = [[-1] * (n+1) for i in range(n+1)]


wordNumbers = [convertToNumber(words[i]) for i in range(m)]

# Заполняем матрицу переходов
# перебираем слова и проверяем, что они совпадают с частью номера телефона
for i in range(n):
    for k in range(m):
        number = wordNumbers[k]
        number_length = len(number)

        if (phone_num[i:i+number_length] == number):
            a[i][i+number_length]=k


#Поиск в ширину

# Сюда будем записывать вершины пути 
# (вес, откуда пришли, куда идём)
# По вершине на каждую цифру номера
vertex = [(10000000,-1,-1)] * (n+1)

stack = []
stack.append(0)
vertex[0]=(0, 0, 0)

while(stack):
    top = stack.pop()
    ver = vertex[top]
    new_weight = ver[0] + 1
    for j in range(top+1, n+1):
        k = a[top][j]
        if k > -1:
            v = vertex[j]
            if v[0]>new_weight:
                if v[1] == -1:
                    stack.append(j)
                vertex[j] = (new_weight, top, k)


# Извлечение пути

rver = vertex[n]
if rver[1] == -1: #Мы не достигли конца
    print('No solution.')
else:
    way = []
    pos = n
    while pos != 0:
        v = vertex[pos]
        way.insert(0,words[v[2]])
        pos = v[1]
    print(' '.join(way))

Остальное вам, наверное, понятно.

2
  • Суть идеи уловил, что называется "за хвостик" (ввиду небольшого опыта в программировании вообще и знакомства с ДП на уровне ознакомления с принципами). Если Вас не затруднит, хотя-бы намекните на варианты реализации описанного Вами алгоритма. (На объяснение что такое "О" время тратить не стоит, это я уже осилил ))). Заранее спасибо. 9 окт 2018 в 17:34
  • Спасибо огромное. Пошел курить графы. 11 окт 2018 в 6:06
2

Еще одно решение. Проходит все тесты.

# Класс, описывающий структуру вершин графа
class Vertex(object):
    def __init__(self, value, predecessor):
        # Слово
        self.value = value
        # Список вершин-наследников = вершина предка + длина слова
        self.successor = predecessor + len(value)
        # Метка посещения вершины
        self.is_explored = False

    def __eq__(self, other):
        return self.successor == other.successor


# Функция перевода слова в его цифровое представление
def get_number(value):
    letters = {
        'i': '1', 'j': '1', 'a': '2', 'b': '2', 'c': '2', 'd': '3', 'e': '3', 'f': '3', 'g': '4', 'h': '4', 'k': '5',
        'l': '5', 'm': '6', 'n': '6', 'p': '7', 'r': '7', 's': '7', 't': '8', 'u': '8', 'v': '8', 'w': '9', 'x': '9',
        'y': '9', 'o': '0', 'q': '0', 'z': '0'
    }
    return ''.join([letters[ch] for ch in value])


# Возвращает список всех возможных вершин слова
def get_vertex(edge, path):
    start = 0
    while True:
        try:
            vertex = path.index(edge, start)
            yield (vertex)
            start = vertex + 1
        except ValueError:
            break


# Функция нахождения кратчайшего пути методом поиска в глубину (BFS)
def bfs_shortest_path(graph, start, goal):
    queue = [[vertex] for vertex in graph[start]]

    while queue:
        path = queue.pop(0)
        node = path[-1]
        if node.is_explored:
            continue
        try:
            neighbours = graph[node.successor]
            for neighbour in neighbours:
                new_path = list(path)
                new_path.append(neighbour)
                queue.append(new_path)
                if neighbour.successor == goal:
                    return new_path
        except KeyError:
            pass

        node.is_explored = True

    return None


if __name__ == '__main__':
    while True:
        phone = input()
        if phone == '-1':
            break

        # Метка существования слова, с которого начинается номер
        is_start = False
        # Метка существования возможного результата
        is_result = False
        result = ''
        # Граф
        dictionary = {}

        for _ in range(int(input())):
            word = input()
            if is_result:
                continue
            number = get_number(word)
            if number == phone:
                is_result = True
                result = word
            else:
                for position in get_vertex(number, phone):
                    if position == 0:
                        is_start = True
                    vertex_word = Vertex(word, position)
                    try:
                        if any(map(lambda w: w == vertex_word, dictionary[position])):
                            continue
                        dictionary[position] += [vertex_word]
                    except KeyError:
                        dictionary[position] = [vertex_word]

        if is_result:
            print(result)
            continue
        if is_start:
            result = bfs_shortest_path(dictionary, 0, len(phone))
            if result:
                print(' '.join([word.value for word in result]))
                continue
            print('No solution.')
        else:
            print('No solution.')

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.