[Community Puzzle] Mirrors

Puzzles
#5

Here’s some starting insight into how the light moves for the example (two mirrors with 50% reflection):

source            m1                 m2                lost
  1 →
            ← 0.5 | 0.5 →
← 0.5             |           ← 0.25 | 0.25 →
          ← 0.125 | 0.125 →          |                 0.25 →
← 0.125           |         ← 0.0625 | 0.0625 →
...

Then take a look at the test 5 and test 6 scenario’s to understand which portion of light to pass through in each direction, depending on from which direction the beam of light comes from.

6 Likes
#6

I did a simulation of the light, but encountered a timeout during test 4. Can anyone provide advice on what optimizations I can make?

1 Like
#7

Does your simulation trim out small amounts of light?

#8

yes, in test 4 there is 4 mirrors the simulation works if i set the break point for example if light < 0.0001 break, but the result is not accurate whene i do light < EPSILON it runs for longe time

#9

I also ran into timeout issues. My problem was too much focus on the light and not enough focus on the mirrors.

#10

I use Python for my simulation and it works very fast. I use a dictionary, where the keys are (source, destination), and the values are the amounts of light. I initiate a variable “answer” to 0.

I divide my simulation into rounds. In each round, I simulate all the key-value pairs in the dictionary, and store the two results (one reflection and one pass-through) in a new dictionary. Some of the reflection/pass-through results may involve the same (source, destination), and so they are added together. I believe this step makes the data more compact than if I just keep growing the queue. The light which is able to escape back to the initial source is added to the answer. After all the old dictionary items are simulated, I copy the results from the new dictionary to the old one, and begin the next round of simulation. As I trim off results of small values during the process, the dictionary eventually becomes empty and the simulation is all done.

4 Likes
#11
It is irrelevant *when* a certain amount of light passes through a certain mirror.

The reflected and passed amounts remain the same whether you process the light from a single reflected beam or process it together with a beam reflected in the same direction.

#12

Im almost confident Test 4 got the wrong answer. I get 0.9440 instead of 0.9401.
Everything else is correct. Could somebody help me?

1 Like
#13

Please show your calculations, in detail, so that we may have a look at what goes wrong.

#14 
def forwards(x, l):
    if l == 0:
        return
    out = l
    back = 0
    global reflection
    while x < n:
        back = out * r[x]
        out = out * (1- r[x])
        round(out, 4)
        round(back, 4)
        if x == 0:
            reflection += back
        else:
            t = backwards(x, back)
            reflection += t
        x += 1
        if out < 1e-7:
            return
    pass

def backwards(x, l): 
    if l == 0:
        round(l, 4)
        return l
    out = l
    front = 0
    x -= 1
    if out < 1e-7:
        return out
    while x >= 0:
        front = out * r[x]
        out = out * (1- r[x])
        round(front, 4)
        round(out, 4)
        forwards(x + 1, front)
        x -= 1
    return out

added some wierd roundings, so the value might decrease.

#15

I mean calculations, not the code :sweat_smile:

#16

The calculation is happening the same way jeetee is discribing it. What do you mean by showing the calculations? Like post what values are added together? If yes, theres too many number to print out which will make the porgram time out :frowning:

#17

Are you able to show the first few steps of how much light moves from one place to another?

Or are you able to show the total amount of light classified by path (e.g. one total for Mirror 1 to Mirror 2, one total for Mirror 1 to source, etc)?

#18

This one is interesting.
Two points however :

  • for me, “mirrors” have r=1
  • I guess it’s possible to find the formula for the equivalent mirror of two ones. But as I recomputed it, this was clearly not a “simple” one :slight_smile:
#19

I too cannot get test 4 to pass. The closest I get is .9306, and the cutoff point is 0.00000001. The lower I go, the more accurate it gets, but I cannot go any lower than this without it timing out.

I’ve been trying to solve this for 4 days. There has to be an easier way to do this, right?

#20

You may read the earlier discussion above to see if that helps you.

#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.