[Community Puzzle] Mirrors

Puzzles
#21

It doesn’t help. However, here are some of the first lines from some debugging language I put in. It’s doing test 3, which it accurately guesses.

Standard Output Stream:

Initializing forwards method.

F: i is 0, light is 1

F: initial Through is now 1

F: initial reflected is now 0

F: reflection is: 0.313178

F: through is: 0.686822

F: i = 0, adding 0.313178 to FinalLight. FinalLight is now 0.313178

F: Adding 1 to i. i is now 1

F: reflection is: 0.038074664392

F: through is: 0.648747335608

F: Calling backwards method.

Initializing backwards method. i is 1, r1 is 0.055436, light is 0.038074664392

B: initial reflected is now 0

B: initial through is now 0.038074664392

B: i is now 0. r0 is now 0.313178

B: reflected is now 0.011924147244957776

B: through is now 0.026150517147042224

Calling forwards.

Initializing forwards method.

F: i is 1, light is 0.011924147244957776

F: initial Through is now 0.011924147244957776

F: initial reflected is now 0

F: reflection is: 0.000661027026671479270336

F: through is: 0.011263120218286296729664

F: Calling backwards method.

Initializing backwards method. i is 1, r1 is 0.055436, light is 0.000661027026671479270336

#22

Or if it suits, here is the whole debugging message, though it leaves a lot out in the middle.

Standard Output Stream:

Initializing forwards method.

F: i is 0, light is 1

F: initial Through is now 1

F: initial reflected is now 0

F: reflection is: 0.313178

F: through is: 0.686822

F: i = 0, adding 0.313178 to FinalLight. FinalLight is now 0.313178

F: Adding 1 to i. i is now 1

F: reflection is: 0.038074664392

F: through is: 0.648747335608

F: Calling backwards method.

Initializing backwards method. i is 1, r1 is 0.055436, light is 0.038074664392

B: initial reflected is now 0

B: initial through is now 0.038074664392

B: i is now 0. r0 is now 0.313178

B: reflected is now 0.011924147244957776

B: through is now 0.026150517147042224

Calling forwards.

Initializing forwards method.

F: i is 1, light is 0.011924147244957776

F: initial Through is now 0.011924147244957776

F: initial reflected is now 0

F: reflection is: 0.000661027026671479270336

F: through is: 0.011263120218286296729664

F: Calling backwards method.

Initializing backwards method. i is 1, r1 is 0.055436, light is 0.000661027026671479270336

B: initial reflected is now 0

B: init

…

lLight is now 0.4156138552384287644132847882

B: i is now -1

End of backwards. Returning through, 0.0000553171813153549157533264. FinalLight is now 0.4156138552384287644132847882

F: loop is now 0.0000553171813153549157533264

Adding loop to FinalLight. FinalLight is now0.4156691724197441193290381146

F: Adding 1 to i. i is now 3

end of forwards method, returning 0. FinalLight is now 0.4156691724197441193290381146

B: i is now -1

End of backwards. Returning through, 0.0001982620903990196451116164. FinalLight is now 0.4156691724197441193290381146

F: loop is now 0.0001982620903990196451116164

Adding loop to FinalLight. FinalLight is now0.4158674345101431389741497310

F: Adding 1 to i. i is now 3

end of forwards method, returning 0. FinalLight is now 0.4158674345101431389741497310

B: i is now -1

End of backwards. Returning through, 0.0007105903727324946405495737. FinalLight is now 0.4158674345101431389741497310

F: loop is now 0.0007105903727324946405495737

Adding loop to FinalLight. FinalLight is now0.4165780248828756336146993047

F: Adding 1 to i. i is now 3

end of forwards method, returning 0. FinalLight is now 0.4165780248828756336146993047

B: i is now -1

End of backwards. Returning through, 0.0025468241397226913040963006. FinalLight is now 0.4165780248828756336146993047

F: loop is now 0.0025468241397226913040963006

Adding loop to FinalLight. FinalLight is now0.4191248490225983249187956053

F: Adding 1 to i. i is now 3

end of forwards method, returning 0. FinalLight is now 0.4191248490225983249187956053

B: i is now -1

End of backwards. Returning through, 0.0091280623092765038449048598. FinalLight is now 0.4191248490225983249187956053

F: loop is now 0.0091280623092765038449048598

Adding loop to FinalLight. FinalLight is now0.4282529113318748287637004651

F: Adding 1 to i. i is now 3

end of forwards method, returning 0. FinalLight is now 0.4282529113318748287637004651

B: i is now -1

End of backwards. Returning through, 0.0327158519594944197337793437. FinalLight is now 0.4282529113318748287637004651

F: loop is now 0.0327158519594944197337793437

Adding loop to FinalLight. FinalLight is now0.4609687632913692484974798088

F: Adding 1 to i. i is now 3

end of forwards method, returning 0. FinalLight is now 0.4609687632913692484974798088

B: i is now -1

End of backwards. Returning through, 0.1172567553957012454925750869. FinalLight is now 0.4609687632913692484974798088

F: loop is now 0.1172567553957012454925750869

Adding loop to FinalLight. FinalLight is now0.5782255186870704939900548957

F: Adding 1 to i. i is now 3

end of forwards method, returning 0. FinalLight is now 0.5782255186870704939900548957

B: i is now -1

End of backwards. Returning through, 0.4202594724707205223699281499. FinalLight is now 0.5782255186870704939900548957

F: loop is now 0.4202594724707205223699281499

Adding loop to FinalLight. FinalLight is now0.9984849911577910163599830456

F: Adding 1 to i. i is now 3

end of forwards method, returning 0. FinalLight is now 0.9984849911577910163599830456

0.9985

#23

Not sure if you’ve picked up a point emphasised by both @jeetee and me? Adding up light which will travel in the same way reduces the number of branches in the simulation.

How many loops has your simulation gone through?

My statistics for the test cases are as follows:
Test 1: 19 outer loops or 19 inner loops
Test 2: 0 outer loops or 0 inner loops
Test 3: 46 outer loops or 90 inner loops
Test 4: 172 outer loops or 502 inner loops
Test 5: 9 outer loops or 9 inner loops
Test 6: 10 outer loops or 10 inner loops

My simulation code is structured like this:

while queue:
    for (key, value) in queue.items():

The number of outer loops refers to the total number of while loops the simulation goes through, and the number of inner loops refers to the total number of for loops it goes through.

For your reference, below shows my intermediate answers for my simulation in Test 3:

step  0: 0.0000000000
step  1: 0.3131780000
step  2: 0.3131780000
step  3: 0.3393285171
step  4: 0.3393285171
step  5: 0.7600419975
step  6: 0.7600419975
step  7: 0.7979059475
step  8: 0.7979059475
step  9: 0.9176383878
step 10: 0.9176383878
step 11: 0.9368729593
step 12: 0.9368729593
step 13: 0.9715631563
step 14: 0.9715631563
step 15: 0.9794338663
step 16: 0.9794338663
step 17: 0.9896517833
step 18: 0.9896517833
step 19: 0.9925832403
step 20: 0.9925832403
step 21: 0.9956374907
step 22: 0.9956374907
step 23: 0.9966746748
step 24: 0.9966746748
step 25: 0.9975993275
step 26: 0.9975993275
step 27: 0.9979549534
step 28: 0.9979549534
step 29: 0.9982379123
step 30: 0.9982379123
step 31: 0.9983573697
step 32: 0.9983573697
step 33: 0.9984447327
step 34: 0.9984447327
step 35: 0.9984843005
step 36: 0.9984843005
step 37: 0.9985114690
step 38: 0.9985114690
step 39: 0.9985239747
step 40: 0.9985239747
step 41: 0.9985322472
step 42: 0.9985322472
step 43: 0.9985357364
step 44: 0.9985357364
step 45: 0.9985380446
step 46: 0.9985380446
#24

I think the disconnect is how do you calculate the light that hits the mirror to be reflected in the first place? Sure, I could calculate, like, the mirror getting light that’s reduced by a certain amount every time, then sends it to be reduced again. But that doesn’t account for the light that hits the mirror right next to it, which then bounces back the light and that light then needs to be sent. Then there is light that’s been reflected, goes through, reflected, both a number of times before it even reaches the last mirror to be sent out. How do you get that number?

This is how it’s just melted my brain, knowing what the starting value is that goes back toward the source.

#25

I described my approach here: https://forum.codingame.com/t/community-puzzle-mirrors/201372/10. Basically simulate one queue of light rays (only one reflection and one pass through per light ray, no need to go all the way to the end result), aggregate the results in another queue, discard any insignificant results, and repeat the process with the new queue, until the queue is empty.

#26

I finally got a code that solves all the tests, but it failed validator 6. It doesn’t tell me what the values are in it. What is validator 6? Can I send my code to someone and they can help me determine what went wrong? I do not know why it failed.

#27

I DID it. Finally conquered it!

A note, if anyone is having issues with validator 6, I had to make my numbers floats for it to work. When everything was decimals, it did not work, probably timed out.

#28

My solution (C++) is done by tracking the amount of light on each side of each mirror and then going from front to back and in reverse per loop.
So in each loop I process all the light going from the first mirror into loss and then process all reflections going back to source (and sum them with whatever is there already!).

This loops until the light reflected back by the initial mirror becomes less than epsilon (0.00001).

while (initial mirror reflects enough light to loss side)
    for (mirrors.front -> mirrors.back-1)
        // Move my "loss" side reflection to next mirror as its source
    for (mirrors.back -> mirrors.front+1)
        // Move my "source" side into the previous mirror as reflection

This results in the following outer loop counts (inner loops are outer * 2 * (n_mirrors-1)):
Test 1: 8 loops
Test 2: 0 loops
Test 3: 11 loops
Test 4: 57 loops
Test 5: 1 loop
Test 6: 1 loop

#29

As I said elsewhere, I used a Markov chain (probabilistic graph) and numpy.linalg (I was too lazy to recode by myself a Gauß method).

#30

I have something similar. Yet i need 138 loops to achieve test 4, the worst for me.
Probably the most intuitive simulation method.

(I started by simulating each ray and adding 2 rays each time it reached a mirror, imagine the horror, i had up to 250 000 rays each loop. No spoil here if i said it timed out the big tests. Until i realised i could work with mirrors instead of rays. Best decision so far XD

By the way, there is a mathematic trickery to solve it in one line, but i don’t understand it, if anyone who did it that way can reference me the source, i’ll be interested.

#31

@Razovsky I’m in for the mathematical trickery :

We can use the fact that we can merge (mathematically) two mirrors into a unique mirror that has similar characteristics.

First, existence of such merged mirror. Consider that we have two mirrors m1 and m2 with reflectivity r1 and r2 respectively :

Graphically :

source              m1                              m2                 lost
 1 →                |
               ← r1 | (1-r1) →
                    |                    ← (1-r1)r2 | (1-r1)(1-r2) →
        ← (1-r1)²r2 | (1-r1)r2r1 →                  |                
                    |                 ← (1-r1)r2²r1 | (1-r1)r2r1(1-r2) →
     ← (1-r1)²r2²r1 | (1-r1)r2²r1² →                |              
                    |                ← (1-r1)r2³r1² | (1-r1)r2²r1²(1-r2) →
    ← (1-r1)²r2³r1² | (1-r1)r2³r1³ →                |              
                    |                ← (1-r1)r2⁴r1³ | (1-r1)r2³r1³(1-r2) →
etc...

As the number of steps increase, we can see that the value (1-r1) * r2^n * r1^n which is inside the two mirrors goes to zero. As in every step the sum of what’s out back in the source (sum of all), still between the mirrors (just the last line) and outside lost after m2 (sum of all) is always equal to 1, we can conclude that in the infinite step, the sum of what’s back to the source and the sum of what’s lost after m2 is equal to 1.

We can so create a new mirror, lets call it m12 which represents both mirrors m1 and m2 and with its reflectivity r12 = the sum of whats back ; which converges and is between 0 and 1, which is needed to be considered a proper mirror. What’s lost is by construction of building the steps equal to (1 - r12).

Second, we have to calculate the value of r12 :

By construction we have r12 = r1 + (1-r1)²r2 + (1-r1)²r2²r1 + (1-r1)²r2³r1² + …
We can reconstruct the series as : r12 = r1 + (1-r1)²sum(n = 0…+inf ; r2^(n+1)*r1^n).

We already know that the series converges (it’s in the order of sum(1/2^n)), and we can reformulate it as :
r12 = r1 + (1-r1)²r2sum(n = 0…+inf ; (r2*r1)^n)

We so have a geometric series with ratio r = r1 * r2 with 0<r<1, so we can apply the formula :
sum(n=0…+inf ; (r2 * r1)^n) = 1/(1 - r2 * r1)
See Geometric series - Wikipedia for details.

We can replace it into our formula to get that
r12 = r1 + (1-r1)²r2(1/(1 - r2r1))

Finally, as our new mirror is compatible with all the others, we can apply recursively our approach with all the mirrors until there is only one, knowing that…

The quantity of light back to where it started that passed through a unique mirror of reflectivity r is trivially equal to r.

My first attempt was the one with the simple queue, and it didn’t pass the large tests. I understand nevertheless that the simulation by rounds done by @5DN1L which merges rays that come from every angle of a mirror is enough of a simplification to pass the bulk of calculation that have to be done in those tests.

1 Like
#32

Thanks for the maths. I get it now.
Well i think i made something similar to @5DN1L, it is enough to finish this puzzle.
What we do = merge the rays going into each mirror
What the maths do = merge the mirrors.
The maths certainly win anyway in terms of speed.