Como atravessar 4 vacas por uma ponte com apenas um cabeçote para duas?

Question

Exercício 6.31 do livro Data Structures and Algorithms in Python (Michael T. Goodrich, Roberto Tamassia e Michael H. Goldwasser):

-Suppose Bob has four cows that he wants to take across a bridge, but only one yoke, which can hold up to two cows, side by side, tied to the yoke. The yoke is too heavy for him to carry across the bridge, but he can tie (and untie) cows to it in no time at all. Of his four cows, Mazie can cross the bridge in 2 minutes, Daisy can cross it in 4 minutes, Crazy can cross it in 10 minutes, and Lazy can cross it in 20 minutes. Of course, when two cows are tied to the yoke, they must go at the speed of the slower cow. Describe how Bob can get all his cows across the bridge in 34 minutes.

Answer 1

Para responder essa questão, devemos analisar como podemos combinar as 4 vacas aos pares para ir no cabeçote, e com o resultado, obter as formas que são possíveis de fazer a travessia em 34 minutos:

import numpy as np
import pandas as pd
import itertools

cows = [2, 4, 10, 20]
cownames = ['Mazie', 'Daisy', 'Crazy', 'Lazy']

#Fazendo Combinações aos pares da velocidade das vacas.
cj = list()
for subset in itertools.combinations(cows, 2):
        cj.append(subset)

cjn = list()
for subset in itertools.combinations(cownames, 2):
        cjn.append(subset)

Como no cabeçote as vacas devem ir na velocidade da mais devagar, devemos obter, entre as possíveis duplas no cabeçote, a velocidade da que faz a travessia em mais tempo, e somá-la com a das demais:

#Obtendo a duração da travessia para cada combinação de vacas na jangada.
cjr = list()
for i in range(0, len(cj)):
    x = max(cj[i]) + np.sum(cows) - np.sum(cj[i])
    cjr.append(x)

Tab = np.hstack((cjn, np.transpose([cjr])))
Tab = pd.DataFrame(Tab, 
                   columns=['Vaca 1 no Cabeçote', 'Vaca 2 no Cabeçote', 'Duração'], 
                   index=['Comb. 1', 'Comb. 2', 'Comb. 3', 'Comb. 4', 'Comb. 5', 'Comb. 6'])
print(Tab)

        Vaca 1 no Cabeçote Vaca 2 no Cabeçote Duração
Comb. 1              Mazie              Daisy      34
Comb. 2              Mazie              Crazy      34
Comb. 3              Mazie               Lazy      34
Comb. 4              Daisy              Crazy      32
Comb. 5              Daisy               Lazy      32
Comb. 6              Crazy               Lazy      26

Logo, notamos que as combinações que são possíveis para atravessar as vacas em 34 minutos são as que levam no cabeçote 'Mazie e Daisy', 'Mazie e Crazy' ou 'Mazie e Lazy' e fazem a travessia com as restantes isoladamente.

Comments

Ótima solução, consegui replicar o código perfeitamente aqui. Um comentário é que poderia fazer um função que retornasse os valores para primeira e segunda coluna que era igual a 34. Isso não altera em nada o resultado, mas se fosse uma tabela maior, seria mais difícil analisar apenas 'no olho'.