nav.py

"""Поиск оптимальной цепочки городов.

Пример входных данных:
    ABCD

    Сегменты:
    1. AB
    2. BC
    3. BCD
    4. DE
    5. XAB
    6. CDF
    7. ZCDF

Варианты решений:
           ┌─3 = AB + BCD => 5 узлов - оптимальное решение
       ┌─1─┼─6 = AB + CDF => 5 узлов - оптимальное решение
       │   └─7 = AB + ZCDF => 6 узлов
Старт ─┤
       │   ┌─3 = XAB + BCD => 6 узлов
       └─5─┼─6 = XAB + CDF => 6 узлов
           └─7 = XAB + ZCDF => 7 узлов

Узлы в исходной строке уникальны.
Сегменты в одном решении могут повторяться.
Из одиночных городов маршрут не собираем.
"""
from collections import defaultdict


def read_chains():
    return [
        ['R', 'T', 'C', 'A', 'O'],  # потеряли хвост
        ['M', 'T', 'I', 'D', 'S'],  # ok
        ['C', 'H', 'N', 'A'],  # ok
        ['P', 'N', 'M', 'P', 'A'],  # ok
        ['E', 'I', 'J', 'B'],  # ok
        ['P', 'I', 'Q', 'T', 'M'],  # нет решений
        ['I', 'C', 'H', 'T', 'S'],  # нет решений
        ['D', 'R', 'C', 'T', 'M'],  # потеряли хвост
        ['K', 'A', 'S', 'B'],  # ok
        ['S', 'C', 'N', 'T'],  # ok
        ['H', 'P', 'Q', 'N', 'R'],  # ok
        ['T', 'J', 'H', 'E', 'F'],  # потеряли хвост
    ]


def read_segments():
    raw = [
        ['R', 'T'],
        ['M', 'T'],
        ['C', 'H'],
        ['P', 'N'],
        ['F', 'A'],
        ['U', 'J'],
        ['T', 'B', 'M'],
        ['F', 'R', 'L'],
        ['E', 'I'],
        ['N', 'I'],
        ['P', 'I', 'Q'],
        ['H', 'I'],
        ['I', 'C', 'H'],
        ['D', 'R'],
        ['E', 'A', 'A'],
        ['K', 'A', 'S'],
        ['S', 'C'],
        ['H', 'P'],
        ['E', 'C'],
        ['T', 'J'],
        ['P', 'B'],
        ['C', 'A'],
        ['I', 'D', 'S'],
        ['H', 'N'],
        ['M', 'P', 'A'],
        ['C', 'N', 'F'],
        ['F', 'F', 'O'],
        ['B', 'P'],
        ['L', 'R'],
        ['I', 'J', 'B'],
        ['I', 'N', 'B'],
        ['T', 'M'],
        ['Q', 'Q'],
        ['T', 'S'],
        ['C', 'T'],
        ['A', 'Q'],
        ['S', 'B'],
        ['C', 'N', 'T'],
        ['Q', 'N', 'R'],
        ['I', 'C', 'J'],
        ['H', 'E'],
        ['N', 'P'],
        ['A', 'O'],
        ['N', 'A'],
        ['Q', 'D'],
        ['E', 'F'],
        ['P', 'F'],
    ]

    return {
        number: segment
        for number, segment in enumerate(raw, start=1)
    }


def pairwise(iterable):
    return [
        [iterable[i], iterable[i + 1]]
        for i in range(len(iterable) - 1)
    ]


def build_edges(segments):
    edges = defaultdict(list)
    for number, segment in segments.items():
        for first, second in pairwise(segment):
            edges[(first, second)].append(number)
    return dict(edges)


def solve(chain, edges, solution, path):
    """Есть проблема хвоста.

    Если мы откусили всю голову и у нас в итоге остался один узел,
    его некуда прицепить.
    """
    if len(chain) < 2:
        solution.append(path)
        if chain:
            print(f'\tНекуда прицепить {chain[0]}')
        return

    first, second, *rest = chain
    valid_edges = edges.get((first, second))
    if valid_edges is None:
        path.clear()
        return

    for valid_edge in valid_edges:
        solve(rest, edges, solution, path + [valid_edge])


def weight(variant):
    return sum(len(segment) for segment in variant)


def join(array):
    return ' '.join(array)


def main():
    chains = read_chains()
    segments = read_segments()

    min_len = 2
    max_len = 5
    max_variants = 3

    edges = build_edges(segments)

    for chain in chains:
        solution = []
        print(f'Путь: {join(chain)}')
        solve(chain, edges, solution, [])

        if len(set(chain)) != len(chain):
            print('\tДубликаты в исходных данных\n')
            continue

        valid_paths = []
        for each in solution:
            variant = [segments[x] for x in each]

            if min_len <= len(variant) <= max_len:
                valid_paths.append(variant)

        valid_paths.sort(key=weight)
        valid_paths = valid_paths[:max_variants]

        if not valid_paths:
            print('\tРешений не найдено')

        for path in valid_paths:
            w = weight(path)
            total = len(path)
            string = ' + '.join(f'({join(x)})' for x in path)
            print(f'\t{total} сегментов, {w} точек: {string}')

        print()


if __name__ == '__main__':
    main()