Problem with dictionaries

Question

Good afternoon! I am training my Skills solving some problems, I am a beginner in the Python language. I’ve been trying to solve the problem below for 2 weeks and can’t find a solution. Can someone help me? You don’t even have to give me a ready answer. Only an orientation would be perfect! Below follows the statement of the problem:

In this great city in China, there are T bus terminals, numbered 1 a T; and L bus lines, numbered from 1 to L. The maps are very confused but we can understand that the buses of a line do circular journeys through a fixed set of terminals. By example, the following table indicates the set of terminals by which the buses of each line pass through, to T=10 and L=5: Terminals 1 {4,3,8,2,1} 2 {5,10,7} 3 {1,5} 4 {6,8,10} 5 {9,4,5} No we are concerned about the path of the line, with the order in which the bus passes through the terminals. Therefore, to go from terminal 2 to the terminal 4, we just need to take a bus from line 1 and wait until it arrive at terminal 4. The system ensures that it is possible to travel between any pair of terminals, but perhaps we need to exchange bus line a few times.

We’re afraid of taking a wrong bus and ending up lost in the city. It’s all very big in China! So we want to exchange bus as few times as possible. For example, you can go from the terminal 2 to terminal 10 first taking line 1 to the terminal 1, then line 3 to terminal 5 and finally line 2 up to terminal 10; changing buses twice, using three lines in total. Only that it can go from terminal 2 to the 10 changing only once: first taking line 1 to terminal 8 and then the line 4 to terminal 10.

In this problem, given the sets of terminals of each row, a terminal origin and a terminal destination, your program must compute the minimum possible number of bus lines to make the trip. Input The first line of the input contains four integers, T, L, O and D, representing respectively the number of terminals, the number of bus lines, the terminal origin and the terminal destination. The latest L input lines each describe the set of terminals by which a bus line passes. The i-th line (of the latter L entrance lines) describes the set of bus line terminals i, in the following format: the first integer in the line, C, indicates the number of terminals in the set. After this integer, the rest of the input line contains C distinct integers representing the terminals.

Output Your program should produce a single line, containing only one whole, the minimum possible number of bus lines to travel from the terminal O to terminal D.

That’s the problem. Now below follows the code I have so far:

T, L, O, D = map(int, input().split())
terminais_por_linha = {}
linhas_por_terminal = {}

for i in range(1, L+1):
    terminais_por_linha[i] =  list(input().split())
    del(terminais_por_linha[i][0])

for i in range(1, T+1):
    linhas_por_terminal[i] = []

for k in range(1, T+1):
    for i in range(len(terminais_por_linha)):
        for j in range(len(terminais_por_linha[i+1])):
            if int(terminais_por_linha[i+1][j]) == k:
                linhas_por_terminal[k].append(i+1)

Note that the code only makes the part of the input, these last 'for' aligned here divide the terminals and create a dictionary that shows which lines each terminal meets. Then my problem comes in, I can’t get out of it. If anyone can help me, I really appreciate it.

Answer 1

this is a complex problem, in the problem model presented in "programming marathons", and online problem servers in the SPOJ model -

The most important thing is, before writing the code, to understand the data you have and how you will model it with the common Python data structure (dictionaries, lists and sets) - and even worth creating a specialized class for any of the abstractions of the problem (terminals, or bus lines).

So you can give better names for variables, because the brain works better with "num_lines" than with "L" - even if it gets 2% easier, it’s a 2% that multiplies in each line of your program. Short variable names are a historical feature of programming problems created in an academic environment, in which the mathematical language is very strong - but they do not help in the way modern tools work.

---

As for the problem itself: we can actually have two dictionaries - one with the bus lines, where each "value" is a set (set) (if you don’t know the set, for this purpose are similar to lists, but more efficient since the order does not matter) - and each entry in the set the key to one of the bus terminals. The second structure that will help is a "reverse" dictionary - where the keys are the terminal identifier, and the values set with the bus line identifiers that pass through there.

Now think about how to solve the problem:

If the largest number of jumps between one terminal and another were always "0" - the bus passes at the desired terminal, the problem would be trivial - just take the chosen terminal to start (0), and take any bus passing at the destination terminal (1).

But then, when none of the terminal buses start passing at the terminal destination? Next: for each terminal where each bus leaving the terminal (0) we have to repeat the analysis - (are we in the trivial case? if yes we arrive, otherwise check all possible terminals from each point where the bus passes) -

it is easy to see that it is a problem that requires a recursive call - "see where each bus from here passes - if it passes at the terminal destination arrived - otherwise see repeat the search from each terminal where each bus leaving from here passes" - to avoid endless ties, here goes the cat jump: as the problem is "solved", the minimum number of bus lines between each pair of terminals is noted in a third dictionary. Hence - the recursive function only needs to be called again for pairs of terminals where it has not yet checked the distance.

So - let’s assume that we go from terminal 0 to 1. There is no direct bus - we analyzed the route of the bus A - it passes in terminals 2, 5, 7 - and then we verify that there is already the distance between terminal "7" and "1" which is the destination, why there is a direct bus - ready the bus number between 0 and 1 is "1" + the distance between "7 and "1" - (and we have already noted this in the dictionary of distances).

Another very cool tool that Python has there, that the author of the problem probably did not even foresee that we would be ready is the frozenset - this is like a "tuple", but without specific order - and it can be used as a key of the dictionary that finds the distances between cities - and it will work both for the key "0, 1" and for the opposite order "1, 0". .

---

Before you write any code with more tips on how to implement this, I’ll take a look at your code and comment on something:

T, L, O, D = map(int, input().split())
terminais_por_linha = {}
linhas_por_terminal = {}

OK - so far, you have the input of data from the first line - and creation of data structures - the same as I indicated that they are necessary.

for i in range(1, L+1):
    terminais_por_linha[i] =  list(input().split())
    del(terminais_por_linha[i][0])

Here, ok - you read each line describing the bus lines, discard the first number not needed in Python - since the lists and sets have a dynamic number. You do not convert the number of each terminal to integer - it makes no difference as long as we remember that they are strings in the whole problem.

for i in range(1, T+1):
    linhas_por_terminal[i] = []

Here you already have a problem -you initialize the second dictionary, but leaves it "blank" - we’ll need the information of which lines pass on each terminal be filled.

for k in range(1, T+1):
    for i in range(len(terminais_por_linha)):
        for j in range(len(terminais_por_linha[i+1])):
            if int(terminais_por_linha[i+1][j]) == k:
                linhas_por_terminal[k].append(i+1)

Ok - here you try to fill in this data structure - of the lines that pass through each terminal - rather inefficiently - and, beware - by mixing the "range" that starts at "0" with the Chavs that are the numbers of the terminals and the lines that start at "1," you start at by these "+ 1" there in the middle - the chance that '+ 1' will miss is almost 100% - even if all the rest of the code is right.

And -- you ran out of code - you don’t even actually try to solve the problem - I believe until that last block works.

So come on

---

Functions! Rule number zero: even if you don’t need it, or think you don’t Always divide your program into roles. Otherwise, it ends up happening what was already contaminating your code: logic data entry slipping and mixing the logic of the program.

From this, let’s get the data input right - and having the two dictionaries filled, implement a function that looks for "data two terminals there is a Direct bus from one to the other?" And then another that does: "for a bus, see in each terminal where it stops, which has zero distance?" (this function will give the distance terminals "1") - hence, making it recursive, we can find any distance between two terminals.

def entrada(terminais_por_linha, linhas_por_terminal):
    T, L, O, D = [int(elemento) for elemento in input().split()]

    for i in range(1, L+1):
        # 'set' em vez de 'list' para as informações permite algumas operações mais eficientes.
        terminais_por_linha[i] =  set(list(int(terminal) for terminal in input().split())[1:])

    for linha, terminais in terminais_por_linha.items():
        for terminal in terminais:
            # o método "setdefault" de dicionários é  o mesmo que
            # "se a chave não existe, crie a chave com o valor passado,
            # e retorne aquele valor, se a chave existe, retorne o seu valor"
            linhas_por_terminal.setdefault(terminal, set()).add(linha)


    # Os dicionários são alterados "in place": isso é - permanecem
    # os mesmos objetos, e são alimentados com os valores da entrada,
    # então não precisam ser retornados
    return T, L, O, D

def saida(resultado):

    # Nunca misturar a entrada e saída em itneração com o usuário
    # com a logica do programa. Desta forma, a mesma lógica
    # do programa pode ser usada se for criado uma versão web
    # ou em um aplicativo em janelas do programa
    print(resultado)


def checa_distancia_um(terminais_por_linha, linhas_por_terminal, t1):
    """retorna um conjunto com todos os terminais a distância "1" do terminal passado"""
    resultados = set()
    for linha in linhas_por_terminal(t1):
        resultados.update(terminais_por_linha[linha])
    return resultados

def checa_distancia(terminais_por_linha, linhas_por_terminal, cache_de_distancias, t1, t2):
        # continua
        chave = frozenset({t1, t2})
        if chave in cache_de_distancias:
            return cache_de_distancias[chave]
        if t1 == t2:
            cache_de_distancias[chave] = 0
        elif t2 in checa_distancia_um(terminais_por_linha, linhas_por_terminal, t1):
            cache_de_distancias[chave] = 1
        else:
            distancias = []
            for linha in linhas_por_terminal[t1]:
                for terminal in terminais_por_linha[linha]:
                    if terminal == t1:
                        continue # não verificar o terminal inicial
                    dist = checa_distancia(terminais_por_linha, linhas_por_terminal, terminal, t2)
                    if dist != None:
                        distancias.append(dist)
            if not distancias:
                # não há conexão entre t1 e t2:
                return None
            # retorna a menos distância encontrada, acrescida de um passo
            # (que são as paradas do onibus saindo de t1)
            cache_de_distancias[chave] = min(distancias) + 1
        return cache_de_distancias[chave]


def principal():
    terminais_por_linha = {}
    linhas_por_terminal = {}
    cache_de_distancias = {}
    numero_terminais, numero_linhas, origem, destino = entrada(terminais_por_linha, linhas_por_terminal)
    resultado = checa_distancia(terminais_por_linha, linhas_por_terminal, cache_de_distancias)
    saida(resultado)

principal()

(I haven’t tested it yet, but here’s the idea - you have some test data set there?)