Can't solve this problem from my university

[chocho.boss]

Hi.

From university I got this problem below, which I can't solve. They want it written in C# in which I have no knowledge of. I was hoping if someone here can help me with it.

Here is the problem:

We have 3 barrels with 100L fuel each.
Also a truck with 20L fuel tank and it can carry 1 barrel.
The truck consumes 10L per 100km (10L / 100km).

With this we have to figure out how to move the barrels and consume the fuel inside them in the most efficient way so that we can travel the most distance in a straight line. The truck can move, and refill from, which ever barrel he wants.

The truck can travel 3000km with all the fuel in the barrels. In a straight line I believe the truck can travel 1500km. That's the most optimal I got on paper but for the love of god I can't translate it to code.

I got that answer by refilling from a barrel, getting a full barrel for 100km drop it and with the rest go back for the next full barrel and refilling from the same barrel, then going back for the not full one. And that left me with 2 100l barrels and one with 40l left. (100km straight and 500km overall). Repeat that again and we're left with 2 100l barrels, 1 0l and an empty fuel tank. After that we do that again with the 2 barrels until the barrel we refill from is left at 40l, then we move the emptier barrel first and refill once from the full barrel so we don't redundant paths. After that we empty the barrels and 1500km straight/3000km overall is achieved.

I guess I should say that I have to do it till December 1.

Thank you in advance for all the help provided.

 

[WhiteCube]

Hi.

From university I got this problem below, which I can't solve. They want it written in C# in which I have no knowledge of. I was hoping if someone here can help me with it.

Here is the problem:

We have 3 barrels with 100L fuel each.
Also a truck with 20L fuel tank and it can carry 1 barrel.
The truck consumes 10L per 100km (10L / 100km).

With this we have to figure out how to move the barrels and consume the fuel inside them in the most efficient way so that we can travel the most distance in a straight line. The truck can move, and refill from, which ever barrel he wants.

The truck can travel 3000km with all the fuel in the barrels. In a straight line I believe the truck can travel 1500km. That's the most optimal I got on paper but for the love of god I can't translate it to code.

I got that answer by refilling from a barrel, getting a full barrel for 100km drop it and with the rest go back for the next full barrel and refilling from the same barrel, then going back for the not full one. And that left me with 2 100l barrels and one with 40l left. (100km straight and 500km overall). Repeat that again and we're left with 2 100l barrels, 1 0l and an empty fuel tank. After that we do that again with the 2 barrels until the barrel we refill from is left at 40l, then we move the emptier barrel first and refill once from the full barrel so we don't redundant paths. After that we empty the barrels and 1500km straight/3000km overall is achieved.

I guess I should say that I have to do it till December 1.

Thank you in advance for all the help provided.

Approach 1, The driver has choices.

A program could test every possible sequence of choices, then output the best sequence.

Can the driver's choices be reduced to a few simple rules?

1700 km is possible.

Approach 2, what is the most efficient way to use 300 litres?

The best ending is to have a full tank and a full barrel. 120 litres.

The problem is now reduced to, what is the most efficient way to use 180 litres?

Does the problem have a recursive nature? In other words, if the most efficient way to use x litres has been calculated, is that number useful when calculating larger values?

1700 km demonstration.

a(f,d)
  load f litres
  go forward d km
  unload, keep just enough to get back
  go backwards d km

b(f,d)
  load f litres
  go forward d km

{location:fuel(barrels)}

begin {0:300(3)}

a(100,150) {0:200(2),150:70(1)}
a(100,150) {0:100(1),150:140(2)}
b(100,150) {150:225(3)}

a(105,150) {150:120(2),300:75(1)}
b(120,150) {300:180(2)}

a(80,100) {300:100(1),400:60(1)}
b(100,100) {400:150(2)}

a(50,100) {400:100(1),500:30(1)}
b(100,100) {500:120(2)}

b(120,1200) {1700:0(1)}

 

[chocho.boss]

Approach 1, The driver has choices.

A program could test every possible sequence of choices, then output the best sequence.

Can the driver's choices be reduced to a few simple rules?

1700 km is possible.

Approach 2, what is the most efficient way to use 300 litres?

The best ending is to have a full tank and a full barrel. 120 litres.

The problem is now reduced to, what is the most efficient way to use 180 litres?

Does the problem have a recursive nature? In other words, if the most efficient way to use x litres has been calculated, is that number useful when calculating larger values?

1700 km demonstration.

a(f,d)
  load f litres
  go forward d km
  unload, keep just enough to get back
  go backwards d km

b(f,d)
  load f litres
  go forward d km

{location:fuel(barrels)}

begin {0:300(3)}

a(100,150) {0:200(2),150:70(1)}
a(100,150) {0:100(1),150:140(2)}
b(100,150) {150:225(3)}

a(105,150) {150:120(2),300:75(1)}
b(120,150) {300:180(2)}

a(80,100) {300:100(1),400:60(1)}
b(100,100) {400:150(2)}

a(50,100) {400:100(1),500:30(1)}
b(100,100) {500:120(2)}

b(120,1200) {1700:0(1)}

Hi thanks for giving me some of your time.

For the first approach i'd say yes the driver choices can be reduced to simple rules.
As for the second approach, yes the problem has a recursive nature.

Thank you again for the effort.

 

[AngleWyrm]

The Adventures of Jim the truck driver
Day 1: Jim fills up from barrel1 (80/100), ships it out to the 100km marker, and returns.
He refills from barrel2 (80/100), ships it to 100km and returns.
Then he refills from barrel3 (80/100) and takes it to the 100km marker.

Day 2 begins with all three barrels at 80/100, and 1/2 a tank of gas in the truck.
Jim tops off from barrel1 (70/100), ships it out to 200km and returns.
He refills from barrel2 (60/100), ships it out to 200km and returns.
Then he refills from barrel3 (60/100) and takes it to the 200km marker.

Day 3 begins with 1/2 a tank of gas, barrel1 at 70/100, and the other two at 60/100
Jim tops off from barrel1 (60/100) transports it to 300km, and returns.
He refills from barrel2 (40/100) takes it to 300km and returns.
And finally he refills from barrel3 (40/100) and takes it to the 300km marker.

Day 4 begins with 1/2 a tank of gas, barrel1 at 60/100 and the other two at 40/100
Jim tops off from barrel1 (50/100) transports it to 400km and returns.
He refills from barrel2 (20/100) takes it to 400km and returns.
And he ends the day refilling from barrel2 (20/100) and taking it to 400km

Day 5 begins at 400km marker with 1/2 a tank of gas, barrel1 at 50/100 and the other two at 20/100
Jim tops off from barrel1 (40/100), ships barrel2 to 500km and returns
He refills from barrel3, (0/100) discarding it at the 400km marker and takes barrel1 to 500km

Day 6 begins at 500km with 1/2 a tank of gas, barrel1 at 40/100, and barrel2 at 20/100
Jim tops off from barrel1 (30/100) ships barrel2 to 600km and returns.
He refills from barrel1 (10/100) and takes it to 600km

Day 7 begins at 600km with 1/2 a tank of gas, barrel1 at 10/100 and barrel2 at 20/100
Jim tops off from barrel1 (0/100) discarding it at the 600km marker and travels 200km with barrel2 to 800km
He refills with the remaining 20/100 from barrel2, discarding it at 800km and travels an additional 200km to 1000km from start.

Jim has used all the gas.

 

[WhiteCube]

This is like the classic problem of the camel crossing the desert with 3000 bananas.

The 20 litre fuel tank does make things more interesting.

To move n barrels, one at a time, from depot A to depot B, costs 1 barrel, when the distance from A to B is 1000/(n+n-1) km.

n+n-1 trips

On the other hand, using the idea of a way station, if the first barrel is dropped half way between A and B, and the truck refuels with it every trip, then the depots can be slightly further away.

1000/(n+n-2) km

n+n-2 trips

Driver's choice 1, use the waystation method to move 250 km.

2 barrels left.

Driver's choice 2, use 80 litres to move 800/3 km.

1.2 barrels left.

Driver's choice 3, use everything to move 1200 km.

total: 1716 + 2/3 km.

Choice 1 is not the best way to use 1 of 3 barrels, another way to save a trip is to use the tank, leaving an empty barrel at depot A.

Driver's choice 1a, use 60 litres to move 600/5 km (5 trips), then use 40 litres to move 400/3 km (3 trips).

253 + 1/3 km.

total: 1720 km.

 

[WhiteCube]

Proof the maximum distance is 1720 km. Instead of thinking about the truck's movement and fuel tank, consider the barrels' movements.

If the following is correct then the program does not need to search for a solution.

It costs fuel to move a barrel forwards, but one barrel is special, the last barrel, the truck does not go backwards after moving the last barrel.

Say there are two red barrels and one green barrel.

For every km a red barrel moves forward, the truck goes backward the same distance. (conjecture, but looks right)

Therefore the cost of forward movement is
red : 0.2 l/km = 5 km/l
green : 0.1 l/km = 10 km/l

The reds are costing a lot, so Jim needs to get rid of one red barrel as soon as possible. The first red barrel can stop moving forward when it contains 40 litres and is in the same location as the other barrels.

So Jim needs to use 60 litres.

f3, f2, f1 is the fuel used to move the red, red, and green barrels. x is the distance where they meet.

fuel * km/l = distance

f3 * 5 = x
f2 * 5 = x
f1 * 10 = x

f1 * 5 = 0.5x

5(f3+f2+f1) = x + x + 0.5x
5(60) = 2.5x
300 = 2.5x
120 = x

end of first stage: 120 km forwards, 240 litres left, one red barrel can stop

To get to the ideal ending, Jim uses 120 litres to get the red and green barrel to the same place.

f2 * 5 = x
f1 * 10 = x

5(f2+f1) = x + 0.5x
5(120) = 1.5x
600 = 1.5x
400 = x

end of second stage: 120 + 400 km forwards, 120 litres left, second red barrel can stop

f1 * 10 = x

120 * 10 = x

end of third stage: 120 + 400 + 1200 km forwards

Bonus, it now seems obvious how to solve 4, 5 and 6 barrels.

to move b barrels using f litres:
d assign (10*f)/(b+b-1)
loop b-1 times
  load as much as possible
  drive d
  unload as much as possible
  have enough fuel to get back
  drive -d
end loop
load as much as possible
drive d

to solve n: (n<7)
if n=1 then
  move 1 barrel using 100 litres
else
  t assign 20*(n-1)
  move n barrels using 100-t litres
  move n-1 barrels using t litres
  solve n-1
endif

 

[Reti]

And in conclusion, how this already solved problem looks in C# full and consistent code..?

 

[chocho.boss]

All of this is awesome guys thank you for all the help!

I'm struggling to recreate it in C#.
As @Reti wrote, how would it look in a C# code?

Again thank you all for the help!