Re: Math Challenge, 2 N panes solutions. Message #24 Posted by Egan Ford on 26 July 2007, 7:18 p.m., in response to message #1 by Chuck
Quote:
Three panes of glass are arranged parallel to each other. Each pane allows 70% light through, reflects 20%, and absorbs 10%. What percentage of light will pass entirely through all panes of glass? Assume a beam of light is emitted to the left of the three panes and exits to the far right; how much emits out to the right? Careful.
Hello Chuck,
Since others already provided a solution for three panes, I worked on two N panes solutions. The first is calculated (quick, but needs RAM) and the other is simulated (low RAM, but needs time).
Calculated solution:
The following 71B program builds a 2*N-1 order sparse matrix to find the exact answer for any N (as long as you have enough RAM). The code should be easy to port to any other HP model with matrix support (sorry no 35S).
10 STD @ DESTROY ALL @ OPTION BASE 1
20 T=.7 @ R=.2
30 M=INT(SQR(MEM/2/8)) @ M=INT((M+1)/2)-1
40 INPUT "MAX N=",STR$(M);N0
50 FOR N=1 TO N0
60 DESTROY A,B,X
70 M=2*N-1
80 M0=MEM @ REAL A(M,M),B(M,1),X(M,1) @ M1=MEM
90 FOR I=1 TO M @ A(I,I)=-1 @ NEXT I
100 FOR I=N+1 TO M @ A(I-N,I)=R @ A(I,I-N)=R @ NEXT I
110 FOR I=1 TO N-1 @ A(I+1,I)=T @ NEXT I
120 FOR I=N+1 TO M-1 @ A(I,I+1)=T @ NEXT I
130 B(1,1)=-T
140 MAT X=SYS(A,B)
150 IMAGE "P(",2D,")= ",2D.10D,"% ",6D," ppm using",6D," bytes"
160 DISP USING 150;N,X(N,1)*100,X(N,1)*1000000,M0-M1
170 NEXT N
180 DESTROY ALL
Lines 10-40 setup the environment and prompts for the MAX N to calculate. The 71B, 48/49/50 matrix solver requires 2x the RAM used by the matrix. I assume that this is to preserve the original matrix. My 71B has ~64K free, so I am limited to ~32K for my matrix, or N=32.
Lines 90-120 setup the matrix, 140 solves.
Output:
P( 1)= 70.0000000000% 700000 ppm using 62 bytes
P( 2)= 51.0416666667% 510417 ppm using 148 bytes
P( 3)= 38.0266075388% 380266 ppm using 308 bytes
P( 4)= 28.6686567164% 286687 ppm using 532 bytes
P( 5)= 21.7595919186% 217596 ppm using 820 bytes
P( 6)= 16.5796748933% 165797 ppm using 1172 bytes
P( 7)= 12.6612595201% 126613 ppm using 1588 bytes
P( 8)= 9.6815861690% 96816 ppm using 2068 bytes
P( 9)= 7.4088116685% 74088 ppm using 2612 bytes
P(10)= 5.6721177756% 56721 ppm using 3220 bytes
P(11)= 4.3436617759% 43437 ppm using 3892 bytes
P(12)= 3.3268533494% 33269 ppm using 4628 bytes
P(13)= 2.5482999981% 25483 ppm using 5428 bytes
P(14)= 1.9520479145% 19520 ppm using 6292 bytes
P(15)= 1.4953536068% 14954 ppm using 7220 bytes
P(16)= 1.1455268133% 11455 ppm using 8212 bytes
P(17)= .8775487825% 8775 ppm using 9268 bytes
P(18)= .6722642349% 6723 ppm using 10388 bytes
P(19)= .5150036989% 5150 ppm using 11572 bytes
P(20)= .3945314511% 3945 ppm using 12820 bytes
P(21)= .3022410597% 3022 ppm using 14132 bytes
P(22)= .2315397822% 2315 ppm using 15508 bytes
P(23)= .1773772706% 1774 ppm using 16948 bytes
P(24)= .1358846583% 1359 ppm using 18452 bytes
P(25)= .1040981355% 1041 ppm using 20020 bytes
P(26)= .0797472129% 797 ppm using 21652 bytes
P(27)= .0610925284% 611 ppm using 23348 bytes
P(28)= .0468015997% 468 ppm using 25108 bytes
P(29)= .0358536442% 359 ppm using 26932 bytes
P(30)= .0274666640% 275 ppm using 28820 bytes
P(31)= .0210415888% 210 ppm using 30772 bytes
P(32)= .0161194843% 161 ppm using 32788 bytes
The first numeric column is the number of panes, the 2nd is the percentage of photons expected to make it through, the 3rd is the number of photons/million expected to complete the journey, and the 4th is the amount of RAM required for the matrix.
Simulated (fun) solution:
10 DESTROY ALL @ RANDOMIZE PI @ OPTION BASE 1
20 FOR P=1 TO 5
30 T0=TIME @ L0=0 @ P0=0 @ DIM P0$[1000],P$[1000]
40 N=1000000 @ A=.1 @ R=.2+A @ C=0
60 FOR J=1 TO LOG10(N)
70 FOR I=10^(J-1) TO 10^J-1
80 T=0 @ D=1 @ L=0 @ P$=""
90 'A': IF D=1 THEN P$=P$&">" ELSE P$=P$&"<"
100 CALL PHOTON(D,T,A,R) @ L=L+1
110 IF T=P THEN C=C+1
120 IF T<P AND T>=0 THEN 'A'
130 IF T=P AND L>L0 THEN L0=L @ P0=I @ P0$=P$
140 NEXT I
150 IMAGE 2D,8D,8D,4D.2D,"% in ",5D.2D," sec LP:"
160 DISP USING 150;P,I,C,C/I*100,TIME-T0,L0
170 NEXT J
180 DISP "Longest Path:";L0;"Photon:";P0
190 T=0 @ D=1
200 FOR I=1 TO L0
210 T$=STR$(T)
220 IF T<10 THEN DISP " ";
230 IF P0$[I,I]=">" THEN DISP P0$[I,I];T$; ELSE DISP T$;P0$[I,I];
240 DISP " ";
250 IF MOD(I,18)=0 THEN DISP
260 IF P0$[I+1,I+1]=">" THEN D=1 ELSE D=-1
270 T=T+D
280 NEXT I
290 DISP @ DISP
300 NEXT P
310 END
320 SUB PHOTON(D,T,A,R)
330 X=RND
340 IF X<A THEN T=-1 @ GOTO 380
350 IF X>R THEN 370
360 IF D=1 THEN D=-1 ELSE D=1
370 T=T+D
380 END SUB
This is a lot longer that it needs to be because I wanted to track and display the longest path. The real work is done by lines 100-120 and 320-380. Lines 320-380 take the current direction and target and randomly determine the next target and direction. Lines 100-120 call PHOTON repeatedly until the target (0,1,2,...N-1) is -1 (i.e. right back at you or absorbed) or N (exited on the other side).
Output:
1 10 4 40.00% in .06 sec LP: 1
1 100 76 76.00% in .22 sec LP: 1
1 1000 714 71.40% in 1.54 sec LP: 1
1 10000 7040 70.40% in 14.82 sec LP: 1
1 100000 70036 70.04% in 144.43 sec LP: 1
1 1000000 700309 70.03% in 1441.46 sec LP: 1
Longest Path: 1 Photon: 1
>0
2 10 3 30.00% in .06 sec LP: 2
2 100 60 60.00% in .33 sec LP: 2
2 1000 554 55.40% in 2.74 sec LP: 4
2 10000 5213 52.13% in 25.60 sec LP: 6
2 100000 50960 50.96% in 254.35 sec LP: 8
2 1000000 510826 51.08% in 2546.96 sec LP: 8
Longest Path: 8 Photon: 27392
>0 >1 0< >1 0< >1 0< >1
3 10 3 30.00% in .05 sec LP: 3
3 100 29 29.00% in .38 sec LP: 5
3 1000 355 35.50% in 3.66 sec LP: 9
3 10000 3714 37.14% in 35.11 sec LP:13
3 100000 37656 37.66% in 348.25 sec LP:13
3 1000000 380791 38.08% in 3485.29 sec LP:17
Longest Path: 17 Photon: 100498
>0 >1 >2 1< 0< >1 0< >1 >2 1< >2 1< 0< >1 >2 1< >2
4 10 1 10.00% in .06 sec LP: 4
4 100 34 34.00% in .49 sec LP:10
4 1000 295 29.50% in 4.32 sec LP:14
4 10000 2894 28.94% in 42.99 sec LP:16
4 100000 28728 28.73% in 428.70 sec LP:22
4 1000000 286649 28.66% in 4272.79 sec LP:24
Longest Path: 24 Photon: 228237
>0 >1 >2 1< 0< >1 >2 >3 2< 1< 0< >1 >2 >3 2< >3 2< 1<
0< >1 >2 1< >2 >3
5 10 3 30.00% in .11 sec LP: 9
5 100 14 14.00% in .61 sec LP:13
5 1000 224 22.40% in 5.31 sec LP:15
5 10000 2147 21.47% in 48.95 sec LP:21
5 100000 21485 21.49% in 490.99 sec LP:25
5 1000000 216278 21.63% in 4916.19 sec LP:37
Longest Path: 37 Photon: 743909
>0 >1 >2 >3 2< 1< 0< >1 >2 >3 >4 3< 2< 1< 0< >1 >2 >3
2< >3 >4 3< 2< 1< >2 >3 2< 1< 0< >1 >2 >3 2< 1< >2 >3
>4
10 10 1 10.00% in .11 sec LP:10
10 100 5 5.00% in .71 sec LP:12
10 1000 70 7.00% in 6.62 sec LP:26
10 10000 573 5.73% in 66.77 sec LP:44
10 100000 5638 5.64% in 662.65 sec LP:54
10 1000000 56891 5.69% in 6629.49 sec LP:60
Longest Path: 60 Photon: 146690
>0 >1 0< >1 >2 >3 2< >3 >4 3< 2< 1< >2 >3 >4 >5 4< >5
>6 5< >6 >7 6< 5< 4< 3< 2< >3 >4 >5 4< 3< >4 >5 >6 >7
6< >7 >8 >9 8< 7< 6< 5< >6 >7 6< 5< >6 >7 >8 >9 8< 7<
6< >7 >8 7< >8 >9
32 10 0 0.00% in .11 sec LP: 0
32 100 0 0.00% in .76 sec LP: 0
32 1000 1 .10% in 7.33 sec LP:44
32 10000 1 .01% in 73.61 sec LP:44
32 100000 19 .02% in 732.32 sec LP:60
32 1000000 162 .02% in 7337.15 sec LP:82
Longest Path: 82 Photon: 698717
>0 >1 >2 >3 >4 >5 >6 >7 >8 >9 >10 9< 8< 7< >8 >9 8< 7<
6< >7 >8 7< 6< 5< >6 5< 4< 3< 2< 1< >2 >3 >4 >5 >6 >7
6< 5< >6 >7 >8 >9 8< 7< >8 >9 >10 >11 >12 >13 >14 >15 >16 >17
>18 >19 >20 >21 >22 21< 20< 19< 18< 17< >18 >19 >20 >21 >22 >23 >24 >25
>26 >27 >28 >29 >30 >31 30< 29< >30 >31
The output is formated number of panes, number of transmitted photons, number of photons that made it out the other side, percentage of escaped photons, simulation time, and the current longest path.
The funny output below chronicles the journey of the photon that took the longest path (in the output directly above that would be photon 698717). The > indicates forward (< backwards) movement and the number is the target. Above photon 698717 breezed though panes 0-9, bounced on 10 back through 9 and 8, bounced around the high single digit numbers and eventually make a break for the low 20s, then the low 30s, and eventually emerged a bit wiser (or a wiser bit).
Comparison of calculated to simulated:
N Calculated Simulated
-- ---------- ---------
1 700000 700309
2 510417 510826
3 380266 380791
4 286687 286649
5 217596 216278
10 56721 56891
32 161 162
Thanks for the challenge.
|