Challenge #2: Bridge Transport - Printable Version

Challenge #2: Bridge Transport - Printable Version

+- Sinisterly (https://sinister.li)
+-- Forum: Coding (https://sinister.li/Forum-Coding)
+--- Forum: Coding (https://sinister.li/Forum-Coding--71)
+--- Thread: Challenge #2: Bridge Transport (/Thread-Challenge-2-Bridge-Transport)

Challenge #2: Bridge Transport - Shebang - 03-03-2014

These are some old questions I found from last year's CCC, I'll post this year's questions if I can find the package I got from my teacher.

Problem S2: Bridge transport
Problem Description
A train of railway cars attempts to cross a bridge. The length of each car is 10m but their weights
might be different. The bridge is 40m long (thus can hold 4 train cars at one time). The bridge will
crack if the total weight of the cars on it at one time is greater than a certain weight. The cars are
numbered starting at 1, going up to N, and they cross the bridge in that order (i.e., 1 immediately
followed by 2, which is immediately followed by 3, and so on).

What is the largest number T of railway cars such that the train of cars 1...T (in order) can cross
the bridge?

Input Speciﬁcation
The ﬁrst line of input is the maximum weight W (1 <= W <= 100000) that the bridge can hold at
any particular time. The second line of input is the number N (1 <= N <= 100000) which is the
number of railway cars that we wish to move across the bridge. On each of the next N lines of
input, there will be a positive integer wi (1 <= i <= N, 1 <= Wi <= 100000) which represents the
weight of the ith railway car in the sequence.

Output Speciﬁcation
Your output should be a non-negative integer representing the maximum number of railway cars
that can be brought across the bridge in the order speciﬁed.

Sample Input 1
100
6
50
30
10
10
40
50

Output for Sample Input 1
5

Explanation of Output for Sample Input 1
The ﬁrst four railway cars have total weight 50 + 30 + 10 + 10 = 100, which is not greater than
what the bridge can hold. When the ﬁrst railway car leaves, and the next comes on, we have a total
weight of 30 + 10 + 10 + 40 = 90, which is not greater than what the bridge can hold. The last
four cars would cause the bridge to break, since 10 + 10 + 40 + 50 = 110 which is greater than the
bridge can hold. So, only the ﬁrst 5 railway cars can be taken across the bridge.

RE: Challenge #2: Bridge Transport - 0xDEAD10CC - 03-03-2014

Here's my solution:

Code:
#include <iostream>
#include <vector>

typedef std::vector<int>::iterator vector_iter_t;

int max_railway_cars(std::vector<int> &cars, const unsigned max_weight, const int max_cars)
{
  unsigned current_weight = 0;
  vector_iter_t it[] = { cars.begin(), cars.begin() };
  do {
    if (std::distance(it[0], it[1]) == max_cars) {
      current_weight -= *it[0];
      it[0]++;
    }
    current_weight += *it[1];
  } while (++it[1] != cars.end() && current_weight <= max_weight);
  return std::distance(cars.begin(), it[1]) - (current_weight <= max_weight ? 0 : 1);
}

int main()
{
  const unsigned max_cars = 4; // 4 cars can cross at a time
  const unsigned max_weight = 100; // max weight the bridge can withstand
  std::vector<int> cars { 50, 30, 10, 10, 40, 50 };
  std::cout << max_railway_cars(cars, max_weight, max_cars) << std::endl;
}

RE: Challenge #2: Bridge Transport - Shebang - 03-03-2014

I forgot to mention that while the question does provide sample inputs, the online grader has a random set of inputs used to confirm that the code functions, which means that you need to support standard input. Here's a solution in Python that received full marks:

Code:
# CCC 2013 S2: Bridge Transport
#
# This solution is due largely to Nenad Bauk
# (also thanks to Victor Wang of Tecumseh Elementary
# re: what if the last car makes the bridge collapse?
# This is NOT tested in the test data, but is the example given.
# This program passed this test :-), as well as the 13 test cases.)
#
# Generally speaking one wishes to calculate the weight of four cars.
# The weights are stored in an array (list in python).
#
# Nenad's insight is to simplify things by starting the array with 3
# zero weight cars. This way there are no special cases to consider
# wrt the first three cars. There are always four cars to add up:
# the current one and the 3 previous!

# To simplify issues around the last car, I also added a sentinel to
# the end, a car with a weight in excess of the max. 


#input the data
file = open("s2.0.in", 'r')
W = int(file.readline())
N = int(file.readline())
carWeight = [0,0,0]
for i in range(N):
    carWeight.append(int(file.readline()))
carWeight.append (W+1)

# calculate the weight of each group of four cars
# stopping when the max weight is exceeded.
# the senteniel guarantees I'll never fall off the end of the array
# and thus no need to check for that.

carsAcross = 0
i = 3
totalWeight = carWeight[i-3] + carWeight[i-2] + carWeight[i-1] + carWeight[i]
while totalWeight <= W:
    carsAcross = carsAcross + 1
    i = i + 1
    totalWeight = carWeight[i-3] + carWeight[i-2] + carWeight[i-1] + carWeight[i]
print carsAcross

If I find my Java solution, I'll post it.

RE: Challenge #2: Bridge Transport - 0xDEAD10CC - 03-03-2014

I understand that, I've seen others of this format, I just didn't feel it was necessary here since that is irrelevant to the question, and also because I don't know where to grab the input from or what format it is in. I'd assume separated by '\n', and spaces if necessary, as this is what most do.