Author |
Topic: How far can a truck go carrying it own fuel? (Read 12329 times) |
|
Hippo
Uberpuzzler
Gender: 
Posts: 919
|
 |
Re: How far can a truck go carrying it own fuel?  truck2.pdf
« Reply #50 on: Oct 16th, 2008, 2:00pm » |
 Quote  Modify
|
Finaly I have looked for ps -> pdf conversion (actualy inherited in gsview) ... I usually generate PDF files using PDFTeX, but I have had problems now ... this much smaller attachment contains optimalised paths ... nonnecessary tanking reduced.
Actually METAPOST main memory is not sufficient even for optimised paths for 100 additional tanks (now having only 4082 vertices improving the original 6753). So the last path I have included is for 80 additional tanks (capacity does not allow to draw both paths on one picture).
... Actually even when the order of first trips can be choosen arbitrary for given fixed number of tanks, it was choosen such that this can be extended for higher number of tanks.
Here is the code ... not very nice, but works 
------ TeX ------
\nopagenumbers
\input epsf
\def\truck#1{
\count0=#1\vbox to 0pt{\kern 11cm\hbox to 0pt{\kern 7cm \hbox to 0cm{\hss\bf #1\hss}\hss}\vss}\epsfbox{truck.#1}\vfil\eject}
------- METAPOST --------
def truck(expr tanks)=
%tanks > 3
begingroup
save e,ii,i,et,el,ee,f,dx,xx,sx,eb,n,tl,p,fb;
xx[0]=sx[0]=eb[0]=0;
dx[1]=2MAG;dx[2]=2MAG/3;
for i=1,2:
fb[i]:=-MAG;xx[i]=xx[i-1]+dx[i];sx[i]=sx[i-1]+xx[i];eb[i]=i;n[i]=0;tl[i]=(1+2i)*xx[i]-2*sx[i];
endfor;
i:=2;e=2;show(MAG*(tanks+1));
forever:
if (MAG*(tanks+1)>=tl[i]): ii:=i+1; fi
exitif (e>=ii);i:=i+1;fb[i]:=-MAG;
n[i]=0;
forever:
n[i]:=n[i]+1;et:=1+(n[i-1]-n[i]);ee:=et*(MAG-2xx[i-1])+2(sx[i-1-n[i]]-sx[i-2-n[i-1]]);
dx[i]:=(MAG+ee)/(2i-1-2n[i]);xx[i]:=xx[i-1]+dx[i];el:=2(et*xx[i]-(sx[i-1-n[i]]-sx[i-2-n[i-1]]));
exitif (el>=MAG*et);
endfor
sx[i]=sx[i-1]+xx[i];tl[i]=(1+2i)*xx[i]-2sx[i];
forever:exitif(e+n[i]>=i);
e:=e+1;eb[e]:=i;
endfor
endfor
ee:=(tanks+1)*MAG-tl[ii-1];
dx[ii]:=ee/(2ii-1);xx[ii]:=xx[ii-1]+dx[ii];sx[ii]:=sx[ii-1]+xx[ii];tl[ii]:=(1+2ii)*xx[ii]-2sx[ii];
show('F');show(ee);show(ii);show(e);show(dx[ii]);show(xx[ii]);show(sx[ii]);show(tl[ii]);
i:=-INCR;f:=MAG*(tanks+1); %global addressing in trip!
e:=ii-1;
forever:exitif(e=0);
ee:=e; forever:exitif(eb[ee]<eb[ee+1]);ee:=ee-1;endfor
et:=ee; forever:exitif(ee>e);trip(ee);ee:=ee+1;endfor
e:=et-1;
endfor
lasttrip;
len:=i;
endgroup
enddef;
def trip(expr b)=
show('Trip[b]');
begingroup
save c,t,pb,bb,si,sf;
si:=i;sf:=f;c:=0;
pb:=t:=ii;
trace;
c:=2MAG;f:=f-c;
if (f<eps): show('fuel problems at the base'); fi
trace;
forever:
t:=t-1;
exitif (t=b);
bb[t]:=0;
if (fb[t]>-MAG): %base exists already
c:=c-(xx[pb]-xx[t]);trace;
bb[t]:=bb[t]+c-2MAG;
fb[pb]:=fb[pb]+c-2MAG;c:=2MAG;trace;
if (fb[pb]<-eps) or (fb[pb]>MAG+eps): show('problems at base'+pb);show(fb[pb]);fi
fi
endfor
c:=c-(xx[pb]-xx[t]);trace;
bb[pb]:=MAG;
fb[pb]:=MAG;c:=c-MAG;trace;
if (2dx[pb+1]>MAG):
c:=c+2dx[pb+1]-MAG;
bb[pb]:=bb[pb]+MAG-2dx[pb+1];
fb[pb]:=fb[pb]+MAG-2dx[pb+1];trace;
fi
forever:
t:=t+1;
exitif (t=ii);
if (fb[t]>-MAG):
c:=c-(xx[t]-xx[pb]);trace;
if (c<dx[pb+1]):
bb[pb]:=bb[pb]+c-dx[pb+1];
fb[pb]:=fb[pb]+c-dx[pb+1];c:=dx[pb+1];trace;
else:
if (c>dx[pb+1]):
if (fb[pb]+c-dx[pb+1]>MAG):
bb[pb]:=bb[pb]+MAG-fb[pb];
c:=c+fb[pb]-MAG;fb[pb]:=MAG;trace;
else:
bb[pb]:=bb[pb]+c-dx[pb+1];
fb[pb]:=fb[pb]+c-dx[pb+1];c:=dx[pb+1];trace;
fi
fi
fi
fi
endfor
c:=c-(xx[t]-xx[pb]);trace;
f:=f+c;c:=0;trace;
i:=si;f:=sf;c:=0;
pb:=t:=ii;trace;
c:=2MAG;f:=f-c;trace;
forever:
t:=t-1;
exitif (t=b);
if (abs(bb[t])>eps): % filling necessary at the base
fb[t]:=fb[t]-bb[t]; % original amount
if (bb[t]<0): % base -> car
c:=c-(xx[pb]-xx[t]);trace;
if (c-bb[pb] < 2MAG):
fb[pb]:=fb[pb]+bb[pb];c:=c-bb[pb];bb[pb]:=0;trace;
else:
fb[pb]:=fb[pb]+c-2MAG;bb[pb]:=bb[pb]-c+2MAG;c:=2MAG;trace;
fi
if (fb[pb]<-eps) or (fb[pb]>MAG+eps): show('problems at base'+pb);show(fb[pb]);fi
fi
fi
endfor
c:=c-(xx[pb]-xx[t]);trace;
fb[pb]:=MAG;c:=c-MAG;trace;
if (2dx[pb+1]>MAG):
c:=c+2dx[pb+1]-MAG;
fb[pb]:=fb[pb]+MAG-2dx[pb+1];trace;
fi
forever:
t:=t+1;
exitif (t=ii);
if (abs(bb[t])>eps): % remaining change
c:=c-(xx[t]-xx[pb]);trace;
fb[pb]:=fb[pb]+bb[pb];c:=c-bb[pb];bb[pb]:=0;trace;
fi
endfor
c:=c-(xx[t]-xx[pb]);trace;
f:=f+c;c:=0;trace;
endgroup
enddef;
def lasttrip=
show('L');
begingroup
save t,pb;
c:=f;f:=0;
pb=t=ii;
trace;
forever:
t:=t-1;
c:=c-(xx[pb]-xx[t]);trace;
exitif (t=0);
c:=c+fb[pb];trace;
endfor
if (abs(c)>eps): show('final fuel problems'+abs(c)); fi
endgroup
enddef;
def trace=
pb:=t;x[INC]t:=xx[pb];y[i]t:=f+c;x[i]b:=xx[pb];y[i]b:=2f+c;
if (abs(c-MAG)>MAG+eps):show('fuel problems'+c); fi
enddef;
vardef INC=
i:=i+INCR;i
enddef;
INCR:=1/256*1/256;MAG:=100;
beginfig(4)
truck(4);
pickup pencircle scaled 0.4pt;
transform t;
z[0]t transformed t = (0,22cm);
z[len]t transformed t = (14cm,0);
(x[0]t,y[len]t) transformed t = (0,0);
i:=0;draw (z[i]b forever: --z[INC]b exitif(i>=len); endfor) transformed t;
transform t;
z[0]b transformed t = (14cm,0);
z[len]b transformed t = (0,22cm);
(x[len]b,y[0]b) transformed t = (0,0);
i:=0;draw (z[i]b forever: --z[INC]b exitif(i>=len); endfor) transformed t;
endfig;
% same for other number of tanks, but changing MAG as the sx exceeds 4098 ... smaller pen for higher tanks
bye.
|
| « Last Edit: Oct 16th, 2008, 2:37pm by Hippo » |
 IP Logged |
|
|
|
Vashist
Newbie
Posts: 1
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #51 on: Nov 20th, 2008, 8:07pm » |
Quote Modify
|
According to Physics, Gases occupy 10% more place than the same volume of water, So it there is a full tank of Petrol, it will become 10% more Gas. And the Lorry, would travel more than 500 miles.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #52 on: Nov 20th, 2008, 11:52pm » |
Quote Modify
|
on Nov 20th, 2008, 8:07pm, Vashist wrote:| According to Physics, Gases occupy 10% more place than the same volume of water, So it there is a full tank of Petrol, it will become 10% more Gas. |
|
That sentence makes no sense. The volume is the amount of space it occupies. So you're saying gases occupy 10% more space than they occupy; which implies they either don't take any space, or all space.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
brac37
Newbie
Gender:
Posts: 23
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #53 on: Apr 9th, 2009, 2:29pm » |
Quote Modify
|
The original problem is Dewdney's jeep problem, except that the jeep has initial fuel in its tank, but that can be solved by using 101 drums. The extra drum is not needed for depots, because about half of the drums does not leave the starting point in the solution of Dewdney's jeep problem in the link below. Actually, it is solved with drums of five tankloads instead of one, but the solution with drums of another amount of fuel is similar. Furthermore, you cannot get further if you have smaller drums and you can carry one (or five) tankloads by way of drums.
The problem with n empty drums and infinitely much fuel is Maddex' jeep problem, and the solution for that problem is that you can get exactly as far as a jeep that can carry n full drums. You have to set up full drums in the desert instead of riding out from the fuel station with all of them.
A solution to Dewdney's jeep problem (1995)
by B Jackson, J Mitchem, E Schmeichel
in: Graph Theory, Combinatorics, and Applications: Proc. 7th Quadrenn. Int. Conf. Theory Appl. Graphs, Kalamazoo
PS: I believe the answer is 560.755540. At least, that is what the following program outputs. 58 of the 100 drums are moved.
Code:#include <stdio.h>
double jeep[100], jeepload[100][100], jeepdist[100], jeepdist2[100], jeepdrum[100];
double load;
double fuel = 101;
double drum = 1;
double distunit = 100;
main ()
{
double distance = distunit * (drum + 1);
int count = 1;
double remain = fuel;
fuel -= drum + 1;
jeepdist[0] = -distunit;
jeepdist[1] = -distance;
while (fuel > 0.0000000001) {
load = drum;
jeep[count] = 1;
count++;
int i;
for (i=1; i<count; i++) {
if (load / (2*i-1) < jeep[i] / 2) break;
load += jeep[i];
jeep[i] = 0;
}
load /= 2*i-1;
distance += load * distunit;
jeepdist[count] = -distance;
fuel -= load * (2*count-1);
for (; i<count; i++) {
jeep[i] -= 2 * load;
}
}
distance += distunit * fuel / (2*count-1);
fuel = 0;
int i, j, k;
jeepdist[count] = 0;
jeepdrum[count] = remain - count*drum;
for (i=count-1; i>=1; i--) {
jeepdist[i] += distance;
jeepdist2[i] = jeepdist[i];
jeepdrum[i] = drum;
double tank = 0.5 - (jeepdist[i] - jeepdist[i+1]) / distunit;
if (tank < -0.0000000001) {
tank = 0;
jeepdist2[i] = jeepdist[i+1] + 0.5 * distunit;
}
for (j=i+1; j<count; j++) {
tank -= (jeepdist[j] - jeepdist[j+1]) / distunit;
if (tank < 0) {
jeepload[i][j] = -tank;
jeepdrum[j] += 2*tank;
tank = 0;
}
}
jeepload[i][j] = 1-2*tank;
jeepdrum[j] -= 1-2*tank;
}
jeepload[i][i] = 1;
jeepdist[i] += distance;
jeepdist2[i] = jeepdist[i];
for (j=i+1; j<=count; j++) {
jeepload[i][j] = jeepdrum[j];
}
printf ("Leave %d drums closed. ", count);
printf ("Open the other drums on position 0.\n");
jeepdrum[count] = remain - count*drum;
printf ("So we start with %f tankloads of opened drums on position 0.\n\n", jeepdrum[count]);
for (i=count-1; i>=0; i--) {
jeepdrum[i] = drum;
for (j=i+1; j<count; j++) {
if (jeepload[i][j] > 0) break;
}
printf ("Pick one drum on position %d.\n", 0.0);
double tank = 0;
for (k=count; k>=j; k--) {
tank += jeepload[i][k];
if (tank > 1.0000000001) {
printf (" %f tankloads of tank fuel remains.\n", tank-jeepload[i][k]);
printf ("Dump drum and ride back to %f\n", jeepdist2[k]);
printf ("Take drum with %f tankloads and ride to %f\n", jeepload[i][k], jeepdist[k]);
tank -= 2*(jeepdist[k]-jeepdist2[k]) / distunit;
}
printf (" Take %f tankloads from position %f.\n", jeepload[i][k], jeepdist[k]);
printf ("Increase tank fuel from %f to %f tankloads.\n", tank-jeepload[i][k], tank);
jeepdrum[k] -= jeepload[i][k];
printf ("%f tankloads remain on position %f.\n", jeepdrum[k], jeepdist[k]);
if (k == j) {
printf ("Ride to position %f and dump drum.\n", jeepdist2[i]);
tank -= (jeepdist2[i]-jeepdist[k]) / distunit;
} else {
printf ("Ride to position %f.\n", jeepdist[k-1]);
tank -= (jeepdist[k-1]-jeepdist[k]) / distunit;
}
}
if (i == 0) {
printf (" Take %f tankloads from position %f.\n", jeepload[i][i], jeepdist[i]);
printf ("Increase tank fuel from %f to %f tankloads.\n", tank, tank+jeepload[i][i]);
jeepdrum[i] -= jeepload[i][i];
printf ("%f tankloads remain on position %f.\n", jeepdrum[i], jeepdist[k]);
printf ("Ride to %f.\n", distance);
break;
}
for (k=j; k<count; k++) {
printf (" Ride to position %f.\n", jeepdist[k]);
if (k == j) {
tank -= (jeepdist2[i]-jeepdist[k]) / distunit;
} else {
tank -= (jeepdist[k-1]-jeepdist[k]) / distunit;
}
printf ("Take %f tankloads from position %f.\n", jeepload[i][k], jeepdist[k]);
printf ("Increase tank fuel from %f to %f tankloads.\n", tank, tank+jeepload[i][k]);
tank += jeepload[i][k];
jeepdrum[k] -= jeepload[i][k];
printf ("%f tankloads remain on position %f.\n", jeepdrum[k], jeepdist[k]);
}
printf (" Ride to position %f.\n\n", jeepdist[k]);
}
}
|
|
|
| « Last Edit: Apr 10th, 2009, 10:14am by brac37 » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #54 on: Apr 10th, 2009, 7:44am » |
Quote Modify
|
on Apr 9th, 2009, 2:29pm, brac37 wrote:The original problem is Dewdney's jeep problem, except that the jeep has initial fuel in its tank, but that can be solved by using 101 drums. The extra drum is not needed for depots, because about half of the drums does not leave the starting point in the solution of Dewdney's jeep problem in the link below. Actually, it is solved with drums of five tankloads instead of one, but the solution with drums of another amount of fuel is similar. Furthermore, you cannot get further if you have smaller drums and you can carry one (or five) tankloads by way of drums.
The problem with n empty drums and infinitely much fuel is Maddex' jeep problem, and the solution for that problem is that you can get exactly as far as a jeep that can carry n full drums. You have to set up full drums in the desert instead of riding out from the fuel station with all of them.
A solution to Dewdney's jeep problem (1995)
by B Jackson, J Mitchem, E Schmeichel
in: Graph Theory, Combinatorics, and Applications: Proc. 7th Quadrenn. Int. Conf. Theory Appl. Graphs, Kalamazoo |
|
I have find this link, page 23, I should compare it with my results (at least the path is different).
There seems to be nonoptimality in the link. In my solution I went distance from start to base 1 23 times to base 2 21 times to base 3 19 times, but in the link they went to base 2 23 times, ... they got 5417/1344 4.030506. I should check my resulting distance.... by the metapost code given above 4.6435532. May be I have to write some article about it (or if there is a volunteer, I can share ... to be coautor would be sufficient).
I should install ghostview to convert the .ps file for 22 tanks to .pdf ...
|
| « Last Edit: Apr 10th, 2009, 9:29am by Hippo » |
IP Logged |
|
|
|
brac37
Newbie
Gender:
Posts: 23
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #55 on: Apr 10th, 2009, 10:39am » |
Quote Modify
|
on Apr 10th, 2009, 7:44am, Hippo wrote:
I have find this link, page 23, I should compare it with my results (at least the path is different).
There seems to be nonoptimality in the link. |
|
There is non-optimality in that link, because it solves the camel-banana-problem. With the camel-banana-problem, you must empty each opened can immediately entirely in the jeep's fuel tank. This restriction has a price. 515.5598958 miles is the optimum instead of 560.755540.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #56 on: Apr 10th, 2009, 12:00pm » |
Quote Modify
|
on Apr 10th, 2009, 10:39am, brac37 wrote:
There is non-optimality in that link, because it solves the camel-banana-problem. With the camel-banana-problem, you must empty each opened can immediately entirely in the jeep's fuel tank. This restriction has a price. 515.5598958 miles is the optimum instead of 560.755540. |
|
Oh, I see now, they have the 4th constrain ... they can fill the truck only when it is out of gas.
on Apr 9th, 2009, 2:29pm, brac37 wrote:
PS: I believe the answer is 560.755540. At least, that is what the following program outputs. 58 of the 100 drums are moved.
|
|
on Jan 6th, 2003, 12:08pm, James Fingas wrote:| After doing some serious spreadsheeting, I have come up with a method for moving 560.754 miles from the beginning. |
|
So you have beaten James bound.
I have got 561.1 see this post and immediately preceeding ones.
|
| « Last Edit: Apr 10th, 2009, 12:29pm by Hippo » |
IP Logged |
|
|
|
brac37
Newbie
Gender:
Posts: 23
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #57 on: Apr 10th, 2009, 2:36pm » |
Quote Modify
|
The solution in the link is optimal, so I must have misremembered the solution. It is a while ago that I studied the problem. I will try to remember the right solution another time.
Now I remember that not moving drums any more after opening them has a prize. It that is true, then that is a reason that my solution is not optimal. My solution might be the optimal solution for not moving drums any more after opening them.
It's long ago. I might be wrong about that this problem is Dewdney's jeep problem: I do not remember any more if transferring tank fuel into drums is allowed. That can also be the reason for non-optimality, although not remembering it can also be a sign for that is does not matter.
|
| « Last Edit: Apr 10th, 2009, 3:39pm by brac37 » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #58 on: Apr 11th, 2009, 12:59am » |
Quote Modify
|
on Apr 10th, 2009, 2:36pm, brac37 wrote:
Now I remember that not moving drums any more after opening them has a prize. It that is true, then that is a reason that my solution is not optimal. My solution might be the optimal solution for not moving drums any more after opening them.
|
|
It seems to me this constrain is not important ... I always move full tanks
(but I can tank any exact portion from a tank in "an arbitrary" situation, I hope as well as you).
|
|
IP Logged |
|
|
|
brac37
Newbie
Gender:
Posts: 23
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #59 on: Apr 16th, 2009, 3:59pm » |
Quote Modify
|
On easter holidays, I have though about my algorithm. I convinced myself it is optimal when you do not allow returning tank fuel to drums, and that Hippo returns tank fuel to drums in his algorithm.
But it does not seem that Hippo returns tank fuel to drums in his algorithm. But I still think doing so in the right way will lead to a better algorithm.
So I have compared my table and Hippo's table. They start to get different at the exact position that the denominator does not fit any more in three digits. So my guess is that James, Hippo and I all have the same algorithm. Prove me I am wrong!
This is my table after getting a library for exact rational computation here:
Fuel = 101+0/1
2+0/1 + 0+2/3 = 2+2/3
2+2/3 + 0+1/3 = 3+0/1
3+0/1 + 0+4/15 = 3+4/15
3+4/15 + 0+1/5 = 3+7/15
3+7/15 + 0+16/105 = 3+13/21
3+13/21 + 0+1/7 = 3+16/21
3+16/21 + 0+106/945 = 3+118/135
3+118/135 + 0+32/297 = 3+54/55
3+54/55 + 0+1/11 = 4+4/55
4+4/55 + 0+1262/15015 = 4+214/1365
4+214/1365 + 0+1/13 = 4+319/1365
4+319/1365 + 0+206/2925 = 4+479/1575
4+479/1575 + 0+1/15 = 4+584/1575
4+584/1575 + 0+4756/80325 = 4+6908/16065
4+6908/16065 + 0+195028/3357585 = 4+19280/39501
4+19280/39501 + 0+1/19 = 4+21359/39501
4+21359/39501 + 0+210148/4147605 = 4+129097/218295
4+129097/218295 + 0+1/21 = 4+139492/218295
4+139492/218295 + 0+587738/13054041 = 4+2126038/3108105
4+2126038/3108105 + 0+1/23 = 4+2261173/3108105
4+2261173/3108105 + 0+629318/15540525 = 4+39917/51975
4+39917/51975 + 0+11146/280665 = 4+161927/200475
4+161927/200475 + 0+1/27 = 4+169352/200475
4+169352/200475 + 0+295282/8139285 = 4+1327958/1507275
4+1327958/1507275 + 0+1/29 = 4+1379933/1507275
4+1379933/1507275 + 0+976524/29419775 = 4+25985891/27390825
4+25985891/27390825 + 0+1/31 = 4+26869466/27390825
4+26869466/27390825 + 0+47985422/1561277025 = 5+589289/50363775
5+589289/50363775 + 0+53286872/1762732125 = 5+2737481/65286375
5+2737481/65286375 + 0+1/35 = 5+4602806/65286375
5+4602806/65286375 + 0+1836365026/65221088625 = 5+1286913644/13044217725
5+1286913644/13044217725 + 0+1/37 = 5+1639460069/13044217725
5+1639460069/13044217725 + 0+1913109826/72674927325 = 5+2090019229/13749310575
5+2090019229/13749310575 + 0+1/39 = 5+2442565654/13749310575
5+2442565654/13749310575 + 0+29115404776/1178690897475 = 5+874536288086/4321866624075
5+874536288086/4321866624075 + 0+1/41 = 5+979947669161/4321866624075
5+979947669161/4321866624075 + 0+30269193076/1299582271575 = 5+1133323033751/4532689386225
5+1133323033751/4532689386225 + 0+4695599713352/203971022380125 = 5+1295235726329/4743512148375
5+1295235726329/4743512148375 + 0+1/45 = 5+1400647107404/4743512148375
5+1400647107404/4743512148375 + 0+4861533485902/222945070973625 = 5+14138389506778/44589014194725
5+14138389506778/44589014194725 + 0+1/47 = 5+15087091936453/44589014194725
5+15087091936453/44589014194725 + 0+5017698494902/242762410615725 = 5+3337986346129/9297283810815
5+3337986346129/9297283810815 + 0+1/49 = 5+3527726832064/9297283810815
5+3527726832064/9297283810815 + 0+1352409418767292/68753413780976925 = 5+559998966160828/1403130893489325
5+559998966160828/1403130893489325 + 0+1449177066594142/74365937354934225 = 5+610374946531726/1458155634410475
5+610374946531726/1458155634410475 + 0+1/53 = 5+637887316992301/1458155634410475
5+637887316992301/1458155634410475 + 0+46219536558573544/2486155356669859875 = 5+21392781359065033/46908591635280375
5+21392781359065033/46908591635280375 + 0+1/55 = 5+22245664843342858/46908591635280375
5+22245664843342858/46908591635280375 + 0+47540130340681144/2673789723210981375 = 5+4783792823313542/9722871720767205
5+4783792823313542/9722871720767205 + 0+1/57 = 5+4954369520169107/9722871720767205
5+4954369520169107/9722871720767205 + 0+2871921257729234/168720421036842675 = 5+1394609113417621/2648427661704825
5+1394609113417621/2648427661704825 + 0+37046418912178022/2192519757082780125 = 5+141374317705768811/260129462704736625
5+141374317705768811/260129462704736625 + 0+1/61 = 5+145638735127157936/260129462704736625
5+145638735127157936/260129462704736625 + 0+37951519752636122/2341165164342629625 = 5+22109838293394386/38379756792502125
5+22109838293394386/38379756792502125 + 0+1/63 = 5+22719040782164261/38379756792502125
5+22719040782164261/38379756792502125 + 0+1439091161045885576/92303315085967610625 = 5+6230931582461214809/10255923898440845625
5+6230931582461214809/10255923898440845625 + 0+1/65 = 5+6388715027052612434/10255923898440845625
5+6388715027052612434/10255923898440845625 - 0+449052542624931547357037189551336682/292088402466833103571021241038410 28125 = 5+17745988533599676346381190694635102128/2920884024668331035710212410384 1028125
With 100 digits accuracy (moved the point two spots to the right): 560.75553970553400879818000925876880936180908640905053874901288682215319 03614211532617991533191874618
|
| « Last Edit: Apr 16th, 2009, 4:19pm by brac37 » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #60 on: Apr 16th, 2009, 11:12pm » |
Quote Modify
|
I have noted that table contains fractions that are approximations to the correct values ... it's how excell writes them. But the difference is too big to be rounding problems. Did you optimise the order the trips?
|
|
IP Logged |
|
|
|
brac37
Newbie
Gender:
Posts: 23
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #61 on: Apr 17th, 2009, 4:42am » |
Quote Modify
|
on Apr 16th, 2009, 11:12pm, Hippo wrote:| I have noted that table contains fractions that are approximations to the correct values ... it's how excell writes them. But the difference is too big to be rounding problems. Did you optimise the order the trips? |
|
No, but I do not return tank fuel to the drums either. I see how out of order transportation of drums can be useful, but only if you allow returning tank fuel to the drums. See my previous post. If you do not refill drums with tank fuel, then your algorithm is a counterexample to what I believe. But your pictures show that you do refill drums.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Truck with Removable Gas Tanks
« Reply #62 on: Apr 17th, 2009, 6:18am » |
Quote Modify
|
I had no time to edit the previous post after thinking about it ...
on Sep 19th, 2008, 4:16pm, Hippo wrote:
3) t1,p1,f4/15,t4/15,f1/3,d1,r1/3,t4/15,t(-1/3),r4/15
base 0 ... initialised with d1, t4/(3*5) used 5 times, but t(-1/3) after the 2nd, so 4/3 in and out.
|
|
Yes, I am taking fuel from the truck (I am not sure James does this as well).
And this is why optimisation of order of trips is important in my solution.
Oops, not realy, see the PDF in the first link on this page, this t(-1/3) was only for easines of describtion.
I can as well tank less during the trip ...
3) t1,p1,f4/15,t3/15,f1/3,d1,r1/3,r4/15
Oops, Oops ... see "pages" 9,10 ... there it is required.
|
| « Last Edit: Apr 17th, 2009, 6:56am by Hippo » |
IP Logged |
|
|
|
brac37
Newbie
Gender:
Posts: 23
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #63 on: Apr 17th, 2009, 7:39am » |
Quote Modify
|
Cool that that out of order transportation leads to a better algorithm. But refilling makes proving optimality much harder. One way to prove optimality is to prove that some program finds the optimal algorithm and to run that program. 
|
|
IP Logged |
|
|
|
brac37
Newbie
Gender:
Posts: 23
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #64 on: Apr 21st, 2009, 3:21pm » |
Quote Modify
|
It seems hard to find an optimal algorithm. I got as far as
5 110210046720786239934976/168036215348370240246375 = 5.655871
thus far by reusing drum depots. The second time a drum depot is used, the jeep can "vomit" its tankfuel into the already used drum. If the first drum is not empty yet, then the jeep can use all its fuel for riding if the "vomit" trip is chosen on the right moment.
I have tested the algorithm with a simulation. Hippo seems to use a different approach, and I think that combining both approaches might lead to an even better algorithm.
Here are the drum depot positions in arbitrary order.
4.655871 3.655871 2.989204 2.655871 2.389204
1.583144 2.189204 2.036823 1.378967 1.893966
1.226856 1.781797 1.102632 1.102632 1.674053
0.940084 0.940084 1.583144 0.801645 0.801645
1.378967 0.681888 0.681888 0.681888 1.226856
0.541525 0.541525 0.541525 0.541525 1.102632
0.390658 0.390658 0.390658 0.390658 0.940084
0.261390 0.261390 0.261390 0.261390 0.801645
0.148316 0.148316 0.148316 0.067856 0.681888
0.034310 0.541525 0.390658 0.261390 0.148316
0.067856 0.034310 0.002052
|
|
IP Logged |
|
|
|
brac37
Newbie
Gender:
Posts: 23
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #65 on: Apr 22nd, 2009, 6:24am » |
Quote Modify
|
An improvement of the above is the following. Assume the jeep has dumped his full drum and is about to vomit its tankload. Before doing so, ride back a little with the empty drum. The dumped drum will be emptied during the last outward trip, so only small amounts of fuel can be taken from the dumped drum. But it gives some room to ride back with the empty drum.
After riding back a little, dump the empty drum and vomit. It seems somewhat illogical to vomit on a smaller position than you reach in a trip. But it does not cost anything and even saves fuel in case of multiple vomit positions: the drum to vomit into will be closer. The third time a drum is used to vomit into, the drum will be even more closer, etc. In the above algorithm, the multiplicities of the vomits are: 5 x 1, 3 x 2, 2 x 3, 3 x 4.
I currently do not have time any more to make further computations, so here are my files.
EDIT: Wait, it can be done better. The above algorithm does not only seem illogical, but is illogical: vomiting must be done on the same position as dumping. The drum is not carried backward on the vomit trip, but on the last trip that its fuel is used. This way, the fuel of dumped drums can be saved for a while, giving more room to carry back empty drums.
|
| « Last Edit: Apr 22nd, 2009, 6:49am by brac37 » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #66 on: Apr 22nd, 2009, 2:17pm » |
Quote Modify
|
I didn't checked the results ... can you find minimal number of drums for which your algorithm gives better results than mine.
|
| « Last Edit: Apr 22nd, 2009, 2:17pm by Hippo » |
IP Logged |
|
|
|
brac37
Newbie
Gender:
Posts: 23
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #67 on: Apr 23rd, 2009, 12:55pm » |
Quote Modify
|
on Apr 22nd, 2009, 2:17pm, Hippo wrote:| I didn't checked the results ... can you find minimal number of drums for which your algorithm gives better results than mine. |
|
My algorithm starts deviating from the Dewdney jeep algorithm at 24 tankloads (23 drums). But your algorithm is better at that point. So you have a better start, but I overtake you later. The conclusion is that our ideas should be combined. But haven't I said that already? So there is a lot of room for improvement, see also my previous post.
The precise deviation point is 23.810. It does not take very long before I overtake you:
23 116/271:
Me 4.305052 
You 4.308641
25 210/937:
Me 4.372006
You 4.375163
26 93/100
Me 4.431824
You 4.433987
28 577/804
Me 4.491351 
You 4.491654 
30 5/11
Me 4.545729
You 4.544286
|
| « Last Edit: Apr 23rd, 2009, 1:34pm by brac37 » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #68 on: Apr 24th, 2009, 10:24pm » |
Quote Modify
|
on Apr 23rd, 2009, 12:55pm, brac37 wrote:
My algorithm starts deviating from the Dewdney jeep algorithm at 24 tankloads (23 drums). But your algorithm is better at that point. So you have a better start, but I overtake you later. The conclusion is that our ideas should be combined. But haven't I said that already? So there is a lot of room for improvement, see also my previous post.
30 5/11
Me 4.545729
You 4.544286 |
|
Can you write describtion of you jurney with 30 drums (preferable format is with distances to the target rather from the start).
Thanks
|
|
IP Logged |
|
|
|
brac37
Newbie
Gender:
Posts: 23
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #69 on: Apr 25th, 2009, 8:25am » |
Quote Modify
|
The below solution is with 29 drums and a full tank. So its target is lower than that of 30 5/11 tankloads. The drum positions are:
3.531780 2.531780 1.865113 1.531780 1.265113
0.549962 1.065113 0.331664 0.912732 0.167265
0.769875 0.657706 0.549962 0.331664 0.167265
0.037116
The journey is in the same format as you use, so no distances form start or target.
p1 f0.037116 d1 r0.037116
p1 f0.167265 d1 r0.167265
p1 t0.240428 f0.331664 d1 r0.331664 t0.331664
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.012845 f0.382696 d1 r0.382696 t0.012845 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.120589 f0.490440 d1 r0.490440 t0.120589 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.130149 f0.164399 t0.102610 f0.438211 d1 r0.438211 t0.102610 r0.164399 t0.130149 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.130149 f0.164399 t0.164399 f0.218297 t0.081068 f0.362771 d1 r0.362771 t0.081068 r0.218297 t0.164399 r0.164399 t0.130149 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 d1 t(-0.739702) r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.130149 f0.164399 t0.164399 f0.218297 t0.218297 f0.107744 t0.015152 f0.407407 d1 r0.407407 t0.015152 r0.107744 t0.218297 r0.218297 t0.164399 r0.164399 t0.130149 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.130149 f0.164399 d1 t(-0.671202) r0.164399 t0.130149 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.130149 f0.164399 t0.164399 f0.218297 d1 t(-0.563405) r0.218297 t0.164399 r0.164399 t0.130149 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.130149 f0.164399 t0.164399 f0.218297 t0.218297 f0.107744 t0.107744 f0.112169 t0.107407 f0.495238 d1 r0.495238 t0.107407 r0.112169 t0.107744 r0.107744 t0.218297 r0.218297 t0.164399 r0.164399 t0.130149 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.130149 f0.164399 t0.164399 f0.218297 t0.218297 f0.107744 t0.107744 f0.112169 t0.112169 f0.142857 t0.142857 f0.152381 t0.119048 f0.466667 d1 r0.466667 t0.119048 r0.152381 t0.142857 r0.142857 t0.112169 r0.112169 t0.107744 r0.107744 t0.218297 r0.218297 t0.164399 r0.164399 t0.130149 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.130149 f0.164399 t0.164399 f0.218297 t0.218297 f0.107744 t0.107744 f0.112169 t0.112169 f0.142857 t0.142857 f0.152381 t0.152381 f0.200000 t0.200000 f0.266667 t0.100000 f0.333333 d1 r0.333333 t0.100000 r0.266667 t0.200000 r0.200000 t0.152381 r0.152381 t0.142857 r0.142857 t0.112169 r0.112169 t0.107744 r0.107744 t0.218297 r0.218297 t0.164399 r0.164399 t0.130149 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.130149 f0.164399 t0.164399 f0.218297 t0.218297 f0.107744 t0.107744 f0.112169 t0.112169 f0.142857 t0.142857 f0.152381 t0.152381 f0.200000 t0.200000 f0.266667 t0.266667 f0.333333 t0.333333 f0.666667 d1 t0.333333 r0.666667 t0.333333 r0.333333 t0.266667 r0.266667 t0.200000 r0.200000 t0.152381 r0.152381 t0.142857 r0.142857 t0.112169 r0.112169 t0.107744 r0.107744 t0.218297 r0.218297 t0.164399 r0.164399 t0.130149 r0.130149 t0.040000 r0.037116 t0.497116
p1 t0.497116 f0.037116 t0.040000 f0.130149 t0.130149 f0.164399 t0.164399 f0.218297 t0.218297 f0.107744 t0.107744 f0.112169 t0.112169 f0.142857 t0.142857 f0.152381 t0.152381 f0.200000 t0.200000 f0.266667 t0.266667 f0.333333 t0.333333 f0.666667 t0.666667 f1.000000 d1 t1.000000 f1.000000
4 45220886/85036875 = 4.531780
|
| « Last Edit: Apr 25th, 2009, 8:30am by brac37 » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #70 on: Apr 25th, 2009, 11:50pm » |
Quote Modify
|
Seems, I get the diference ... you better use truck for transporting fuel inside it's tank. Good job.
I will think later about the problem again ...
|
|
IP Logged |
|
|
|
brac37
Newbie
Gender:
Posts: 23
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #71 on: Feb 1st, 2010, 6:25am » |
Quote Modify
|
A solution to Dewdneys jeep problem that is easier to get is the following article in the Mathematical Gazette.
http://www.jstor.org/stable/3618853
But it is harder to find since it is not indexed in the MathSciNet database.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #72 on: Feb 4th, 2010, 1:49am » |
Quote Modify
|
I still have this problem on to think about later list
|
|
IP Logged |
|
|
|
brac37
Newbie
Gender:
Posts: 23
|
|
Re: How far can a truck go carrying it own fuel?
« Reply #73 on: Apr 19th, 2010, 8:03am » |
Quote Modify
|
Jeep problems are interesting on its own, especially when they are unsolved, like this one. But does anyone know real life applications of such problems?
I think about (ant)arctic expeditions, cage diving and spatial traveling. But there might be applications that did not cross my mind.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print