# Bridge Crossing - Classic Puzzle

Problem - The classic puzzle of finding the minimum amount of time required to cross a bridge given that only two people can cross the bridge at any one time. Since they have only one flashlight (it's dark and they need the flashlight), the two people move at the speed of the slower one.

Constraints - Upto 6 people (although it should work for a higher number of people)

Input - Number of people (up to 6 tested) & Sorted vector of time required by each person to cross the bridge.

Output - Minimum time possible

int main()
{
vector<int> v; int n; int time;
int items;
int k = 2;
cin>>items;
for (int i = 0; i < items; i++)
{
cin >> n;
v.push_back(n);
}

if (v.size() == 1)
{
cout << v[0];
return 0;
}
int last = v.size() - 1;
time = v[0] + v[1] + v[last] + v[1];

while (last-k >= 2)
{
time += v[0] + v[last - k];
k++;
}
time = time + v[1];

cout << time;
return 0;
}


Note : Code will not work for 2 people, missed a special case.

• Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
– Mast
Dec 9, 2016 at 16:30
• @Mast I assumed the code appeared broken and was difficult to understand as mentioned by forsvarir. Won't edit further Dec 9, 2016 at 16:39
• Given the lack of descriptive variable naming, perhaps you should add a reference to more detailed background info in the question: en.wikipedia.org/wiki/Bridge_and_torch_problem Dec 10, 2016 at 6:43
• Your algorithm is wrong. It outputs 253 for the speeds 1 2 3 80 80 80 80, but I can do it in 175. Dec 10, 2016 at 12:48
• @RolandIllig See the constraints. I've written upto 6 only Dec 10, 2016 at 13:06

The overwhelming first impression I get from your code is that without the text description above, I wouldn't have a clue what it is you're trying to do. A lot of these types of problems have some kind of prompting which helps, however your code doesn't have that, its only output is time after it's finished.

The two main improvements I'd suggest are:

• Put your code in a function that defines an interface.
• Use variable names that have some kind of meaning.

Implementing these two basics would go a long way to making your code easier to follow.

For example, your vector v might be people?!?

You could have a method calculate_minimum_time_to_cross_bridge, which took in a list of people and returned the time.

Whilst your variable names might have meaning to you, they have no meaning a new reader without context.

One final point is that whilst you can do this:

vector<int> v; int n; int time;


It's generally considered bad form. One declaration per line means the declarations are less likely to get lost.

• Thanks for the input. Edited the variables to reflect some meaning. Will implement the method soon. Do you think the code is logically correct? I just formed a conjecture. Worked for upto 6 people Dec 9, 2016 at 16:27
• @borb183 Honestly, I'm not sure, I get a different answer to you, I'd have to see a worked example. By my logic, you basically have two cases. If there is only 1 person, it takes that amount of time. If you have (2 to n) people, then it takes the sum of the times for the n-1 slowest people + the time for the fastest person * n-2, which is the number of times they'd have to walk back. So for 2 people with speeds 2 and 3, the time should be 3 (they walk across together). With your algorithm, I am getting 14, however I'm not sure what order your elements are supposed to be in. Dec 9, 2016 at 17:56

• The biggest problem with this code is variable naming

v should be person or people

items should be count or numPeople

n should be speed

• Create functions to separate workflow

I would create a function that receives user input and another function that computes the minimum crossing time. Both of those functions would be called from main.

• Whenever you the size of a vector beforehand you should either use the constructor, reserve, or resize to prevent reallocations that would occur from naively adding elements. Which one you need depends on the context.

• Use 4-space indentation or tabs (no need to start a religious war over which is better). 2-space indentation is awful for readability imo.

• After the initial step of taking the last and (last-1) person across the bridge, you need to take person 1 to person last-2. The way you wrote your while loop obfuscates this process.

# Suggested Code

struct Person
{
unsigned int walking_speed;
};

std::vector<Person> get_people(unsigned int n)
{
// Create the n people now
std::vector<Person> person(n);
std::cout << "Enter ascending walking speeds for " << n << " people\n";

for (unsigned int i = 0; i < n; ++i)
{
unsigned int speed;

std::cout << "Enter person " << i << " walking speed: ";
std::cin >> speed;

person[i].walking_speed = speed;
}

return person;
}

unsigned int get_minimum_crossing_time(unsigned int n)
{
if (n == 0)
{
return 0;
}

auto person = get_people(n);

if (n < 3)
{
return person.back().walking_speed;
}
else if (n == 3)
{
// Unfortunately the method below does not
// give the minimum time for three people

// Person 0 and 1 cross from A to B
// Person 0 crosses back to A
// Person 0 and 2 cross from A to B
return person[1].walking_speed + person[0].walking_speed + person[2].walking_speed;
}

unsigned int time_taken = 0;

// Person 0 and Person 1 cross from A to B
time_taken += person[1].walking_speed;

// Person 1 crosses back to A
time_taken += person[1].walking_speed;

// Person (n-2) and Person (n-1) cross from A to B
time_taken += person[n-1].walking_speed;

// Person 0 goes back and forth to escort everyone else
for (unsigned int i = 1; i < n-2; ++i)
{
// Person 0 crosses back to A
time_taken += person[0].walking_speed;

// Person 0 and Person i cross from A to B
time_taken += person[i].walking_speed;
}

return time_taken;
}


I am aware person = get_people(n) is a bit confusing, but I prefer addressing people as person[i] in the code rather than people[i].

• Thanks for the suggestions. To point out, I do count the time it takes for v[0] to return. v[last-k] would be the time for v[0] and v[last-k] to cross the bridge (as it is at the speed of the slower one). Then v[0] returns and thus the total time taken is v[0] + v[last-k] Dec 10, 2016 at 8:41
• You are right. That was my fault. I will remove that part. Dec 10, 2016 at 9:31