1

Boa tarde! Estou treinando minhas skills resolvendo alguns problemas, sou iniciante na linguagem Python. Estou tentando resolver o problema abaixo há 2 semanas e não consigo achar uma solução. Alguém pode me ajudar? Não precisa nem me dar uma resposta pronta. Só uma orientação já estaria perfeito! Abaixo segue o enunciado do problema:

Nessa grande cidade na China, há T terminais de ônibus, numerados de 1 a T; e L linhas de ônibus,numeradas de 1 a L. Os mapas são muito confusos mas conseguimos entender que os ônibus de uma linha fazem viagens circulares passando por um conjunto fixo de terminais. Por exemplo, a tabela seguinte indica o conjunto de terminais por onde passam os ônibus de cada linha, para T=10 e L=5: Linha Conjunto de Terminais 1 {4,3,8,2,1} 2 {5,10,7} 3 {1,5} 4 {6,8,10} 5 {9,4,5} Não estamos preocupados com o trajeto da linha, com a ordem na qual o ônibus passa pelos terminais. Portanto, para ir do terminal 2 para o terminal 4, precisamos apenas tomar um ônibus da linha 1 e esperar até ele chegar no terminal 4. O sistema garante que é possível viajar entre qualquer par de terminais, mas talvez seja preciso trocar de linha de ônibus algumas vezes.

Nós estamos com medo de tomar um ônibus errado e acabar perdidos na cidade. É tudo muito grande na China! Por isso, queremos trocar de ônibus o menor número possível de vezes. Por exemplo, você pode ir do terminal 2 para o terminal 10 primeiro tomando a linha 1 até o terminal 1, depois a linha 3 até o terminal 5 e, por fim, a linha 2 até o terminal 10; trocando de ônibus duas vezes, usando três linhas no total. Só que dá para ir do terminal 2 para o 10 trocando apenas uma vez: primeiro tomando a linha 1 até o terminal 8 e depois a linha 4 até o terminal 10.

Neste problema, dados os conjuntos de terminais de cada linha, um terminal origem e um terminal destino, seu programa deve computar o número mínimo possível de linhas de ônibus para fazer a viagem. Entrada A primeira linha da entrada contém quatro inteiros, T, L, O e D, representando, respectivamente, o número de terminais, o número de linhas de ônibus, o terminal origem e o terminal destino. As últimas L linhas da entrada descrevem, cada uma, o conjunto de terminais pelos quais uma linha de ônibus passa. A i-ésima linha (dessas últimas L linhas da entrada) descreve o conjunto de terminais da linha de ônibus i, no seguinte formato: o primeiro inteiro na linha, C, indica o número de terminais no conjunto. Depois desse inteiro, o restante da linha da entrada contém C inteiros distintos representando os terminais.

Saída Seu programa deve produzir uma única linha, contendo apenas um inteiro, o número mínimo possível de linhas de ônibus para viajar do terminal O para o terminal D.

Esse é o problema. Agora abaixo segue o código que eu tenho até agora:

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)

Vejam que o código só faz a parte da entrada, esses últimos 'for' alinhado aqui dividem os terminais e criam um dicionário que mostra quais as linhas cada terminal atende. Daí entra meu problema, não consigo sair disso. Se alguém puder me ajudar, agradeço grandemente.

1 Resposta 1

2

esse é um problema complexo, no modelo de problemas apresentados em "maratonas de programação", e servidores de problemas on line no modelo do SPOJ -

O mais importante é, antes de escrever o código, entender os dados que você tem e como vai modelar isso com as estrutura de dados comuns do Python (dicionários, listas e conjuntos) - e até se vale a pena criar uma classe especializada para alguma das abstrações do problema (terminais, ou linhas de ônibus).

Daí, pode dar nomes melhores para as variáveis, por que o cérebro funciona melhor com "num_linhas" do que com "L" - mesmo que fique 2% mais fácil, é um 2% que se multiplica em cada linha do seu programa. Os nomes de variáveis curtos são uma característica histórica de problemas de programação criados em um ambiente acadêmico, em que a linguagem matemática é muito forte - mas não ajudam na forma como as ferramentas modernas trabalham.


Quanto ao problema em si: podemos de fato ter dois dicionários - um com as linhas de ônibus, onde cada "valor" é um conjunto (set) (se não conhecer os set, para esse efeito são parecidos com listas, mas mais eficientes já que a ordem não importa) - e cada entrada no set a chave de um dos terminais de ônibus. A segunda estrutura que vai ajudar é um dicionario "ao contrário" - onde as chaves são o identificador dos terminais, e os valores conjuntos com os identificadores das linhas de ônibus que passam por lá.

Agora pensar em como resolver o problema:

Se o maior número de pulos entre um terminal e outro fosse sempre "0" - o ônibus passa no terminal desejado, o problema seria trivial - só pegar o terminal escolhido para início (0), e tomar qualquer ônibus que passe no terminal destino (1).

Mas e aí, quando nenhum dos ônibus terminal de início passa no terminal destino? Seguinte: para cada terminal onde cada ônibus que sai do terminal (0) temos que repetir a análise - (estamos no caso trivial? se sim chegamos, senão, verificar todos os terminais possíveis a partir de cada ponto onde o ônibus passa) -

é fácil ver que é um problema que requer uma chamada recursiva - "veja onde cada ônibus daqui passa - se passa no terminal destino chegou - senão veja repita a busca a partir de cada terminal onde cada ônibus saindo daqui passa" - para evitar laços infinitos, aqui vai o pulo do gato: a medida que o problema é "desvendado", o número mínimo de linhas de onibus entre cada par de terminais vai sendo anotado em um terceiro dicionário. Daí - a função recursiva só precisa ser chamada novamente para pares de terminais onde ainda não verificou a distância.

Assim - vamos supor que vamos do terminal 0 para o 1. Não tem ônibus direto - analisamos a rota do ônibus A - ele passa nos terminais 2, 5, 7 - e aí verificamos que já existe a distância entre o terminal "7" e o "1" que é o destino, por que há um ônibus direto - pronto o número de ônibus entre 0 e 1 é "1" + a distância entre "7 e "1" - (e já anotamos isso no dicionário de distâncias).

Uma outra ferramenta muito bacana que o Python tem aí, que o autor do problema provavelmente nem previu que teriamos pronta é o frozenset - isso é como se fosse uma "tupla", mas sem ordem específica - e pode ser usado como chave do dicionário que acha as distâncias entre as cidades - e vai funcionar tanto para a chave "0, 1" como para a ordem contrária "1, 0". .


Antes de escrever algum código com mais dicas de como implementar isso, vou dar uma olhada no seu código e comentar alguma coisa:

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

OK - até aqui, você tem a entrada de dados da primeira linha - e criação das estruturas de dados - as mesmas que indiquei que são necessárias.

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

Aqui, ok - você lê cada linha descrevendo as linhas de ônibus, descarta o primeiro número que não é necessário em Python - já que as listas e conjuntos tem um número dinâmico. Você não converte o número de cada terminal pra inteiro - não faz diferença desde que lembremos que são strings em todo o problema.

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

Aqui já tem um problema -você inicializa o segundo dicionário, mas deixa ele "em branco" - vamos precisar que a informação de quais linhas passam em cada terminal seja preenchida.

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 - aqui você tenta preencher essa estrutura de dados - das linhas que passam em cada terminal - de forma bastante ineficiente - e, cuidado - ao misturar o "range" que começa em "0" com as chavs que são os números dos terminais e das linhas que começam em "1", você começa a por esses "+ 1" ai no meio - a chance desses '+ 1'se desencontrarem é de quase 100% - mesmo que todo o restante do código esteja certo.

E -- acabou o seu código - você nem chega a tentar resolver de fato o problema - acredito até que esse último bloco funcione.

Então vamos lá


Funções! Regra número zero: mesmo que não vá precisar, ou pense que não vá precisar, sempre divida seu programa em funções. Senão, acaba acontecendo o que já estava contaminando o seu código: a lógica da entrada dos dados vai escorregando e se misturando a lógica do programa.

DIsto isso, vamos acertar a entrada de dados - e tendo os dois dicionários preenchidos, implementar uma função que busque "dados dois terminais há um ônibus direto de um para outro?" E ai uma outra que faça: "para um ônibus, veja em cada terminal onde ele para, quais tem distância zero?" (essa função vai dar os terminais de distância "1") - daí, tornando-a recursiva, podemos achar qualquer distância entre dois terminais.


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()

(Ainda não testei, mas a ideia é essa - você tem algum conjunto de dados de teste aí?)

5
  • Muito obrigado! Eu tenho muita dificuldade com esse tipo de problema e inclusive codei alguns programas que começaram a resolver o problema, mas apenas em casos específicos. Mas obrigado por explicar, isso vai me ajudar muito em problemas futuros!
    – JoaoP_L
    4/06/2020 às 22:48
  • Vou testar, tenho um conjunto de teste. Obrigado!
    – JoaoP_L
    4/06/2020 às 23:00
  • Fui testar e teve o seguinte erro logo depois de terminar a entrada de dados: principal() \n numero_terminais, numero_linhas, origem, destino = entrada(terminais_por_linha, linhas_por_terminal) \n for linha, terminais in terminais_por_linha.items(): \n RuntimeError: dictionary changed size during iteration
    – JoaoP_L
    4/06/2020 às 23:04
  • sim - eu tinha trocado o nome do dicionário a ser atualizado - mais grave - estava faltnado adicionar entradas ao cache de distâncias para os casos de idstancia > 1, e calcular a distancia trivial de um terminal pra ele mesmo.
    – jsbueno
    4/06/2020 às 23:41
  • Uma outra coisa - perceba que as chamadas as funções começam a ficar grandes, por que passamos as estruturas de dados todas para todas as funções. É melhor do que usar as estruturas como variáveis globais - permitiria que o mesmo programa funcionasse num ambiente multi-usuários (com uma interface web, por exemplo) - mas tamem pode ser usada uma 'classe' para resolver o problema . É um porblema de algoritmo que não se beneficia de orientação a objetos em geral - mas manter os dicionários como atributo simplificaria o acesso aos mesmos, sem precisar passar como parametros.
    – jsbueno
    4/06/2020 às 23:45

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .