Chamber of Reflection

Question

Background

A ray of light is fired from the top left vertex of an MxN Chamber, where M a denotes the width and N denotes the height of the chamber. The ray of light advances one grid space per second. Given that T is the number of seconds to be simulated, calculate the number of reflections in this time frame.

For example, given 5 4 11 (ie. M = 5, N = 4, T = 11):

\/\  [
/\ \ [
\ \ \[
   \/[
-----
There would be 4 reflections, so the output should be 4.

Note that a reflection only counts if the ray of light has already bounced off it, so for example, given 5 4 10:

\/\  [
/\ \ [
  \ \[
   \/[
-----
There would only be 3 reflections, so the output should be 3.

Your Task

• Sample Input: M, the width of the chamber, N, the height of the chamber, and T, the time frame. These are all numbers.

• Output: Return the number of reflections.

Explained Examples

Input => Output
1 1 10 => 9 

Chamber:
\[
-

The ray will be reflected back and forth a total of 9 times. 

Input => Output
5 1 10 => 9 

Chamber:
\/\/\[
-----

The ray will be reflected back and forth a total of 9 times. It will first go left to right, then go backwards right to left.

Input => Output
4 5 16 => 6 

Chamber:
\/\ [
/\ \[
\ \/[
 \/\[
\/\/[
----

The ray will be reflected back and forth a total of 6 times.

Input => Output
100 100 1 => 0 

Chamber:
\ ... [
...    x100
-x100


The ray never touches a wall, and is never reflected, so output 0.

Test Cases

Input => Output
5 4 11 => 4
5 4 10 => 3
1 1 10 => 9
5 1 10 => 9
4 5 16 => 6
100 100 1 => 0

3 2 9 => 5
5 7 5 => 0
3 2 10 => 6
6 3 18 => 5
5 3 16 => 7
1 1 100 => 99
4 4 100 => 24
2398 2308 4 => 0
10000 500 501 => 1
500 10000 502 => 1

Bonus points (not really): Listen to DeMarco's song Chamber of Reflection while solving this.

This is code-golf, so shortest answer wins.

Answer 1

Python, 47 bytes

lambda M,N,T:len({*range(M,T,M),*range(N,T,N)})

Attempt This Online!

How?

Enumerates and counts all bouncing times using the Python set type for deduplication.

Answer 2

C (gcc), 58 bytes

g(a,b){a=b?g(b,a%b):a;}f(M,N,T){T=--T/M+T/N-T*g(M,N)/M/N;}

Try it online!

Uses the formula:

\$ \lfloor \frac{T - 1}{M} \rfloor + \lfloor \frac{T - 1}{N} \rfloor - \lfloor \frac{T - 1}{lcm(M,N)} \rfloor\$

Answer 3

Nekomata, 5 bytes

ᵒ÷u#←

Attempt This Online!

Takes input as [m,n],t.

ᵒ÷u#←
ᵒ÷      Generate a division table of [0,...,t-1] and [m,n]
  u     Uniquify
   #    Length
    ←   Decrement

Answer 4

Python 3, 50 bytes

lambda x,y,t:len({(i//x,i//y)for i in range(t)})-1

Try it online!

Answer 5

Python 3.8 (pre-release), 49 48 bytes

f=lambda M,N,T:(T:=T-1)and(T%M*(T%N)<1)+f(M,N,T)

Try it online!

-1 byte thanks to c--

Answer 6

J, 18 bytes

<:@#@~.@(<.@%/~i.)

Uses the division table method used by others. Expects M N f T.

Attempt This Online!

<:@#@~.@(<.@%/~i.)­⁡​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁢⁡⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁤⁤‏⁠‎⁡⁠⁢⁡⁡‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁤⁢‏⁠‎⁡⁠⁤⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌­
        (        )  NB. ‎⁡Dyadic hook
               i.   NB. ‎⁢0..y-1
             /~     NB. ‎⁣Table with flipped arguments, execute a u b for every a in x and b in y
         <.@%       NB. ‎⁤Divide then floor
<:@#@~.@            NB. ‎⁢⁡Then uniquify, length, and decrement

J, 19 bytes

+`-/@(<.@%[,*./)~<:

Uses the closed form from c--'s answer, so please go upvote!

Expects M N f T, where M N is a list.

The major form is two hooks, an inner and outer hook, (H F)~ G, which is equivalent to (G y) H (F x), with +`-/ tacked on at the end, where x and y are the left and right arguments, respectively.

Attempt This Online!

+`-/@(<.@%[,*./)~<:­⁡​‎⁠⁠‎⁡⁠⁢⁡⁢‏⁠‎⁡⁠⁢⁡⁣‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢⁢‏⁠‎⁡⁠⁤⁤‏⁠‎⁡⁠⁢⁡⁡‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏⁠‎⁡⁠⁤⁢‏⁠‎⁡⁠⁤⁣‏‏​⁡⁠⁡‌⁤​‎⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌­
                 <:  NB. ‎⁡Decrement T
     (         )~    NB. ‎⁢Flip the arguments for the inner hook
          [,*./      NB. ‎⁣Append lcm(M,N) to the list of dimensions
      <.@%           NB. ‎⁤Divide T-1 by each item of the result then floor
+`-/@                NB. ‎⁢⁡Then reduce by both + and -, i.e. +`-/ 6 3 1 = 6 + 3 - 1 = 8

Answer 7

Jelly, 6 bytes

ḍƇⱮṖTL

A dyadic Link that accepts the dimensions on the left and the time on the right and yields the number of completed reflections.

Try it online!

How?

ḍƇⱮṖTL - Link: dimensions = [M, N, ...]; time = T
   Ṗ   - pop {T} -> Seconds=[1,2,3,...,T-1]
  Ɱ    - map {across S in Seconds} with:
 Ƈ     -   keep {dimensions} that:
ḍ      -     divide {S}
    T  - truthy indices
     L - length

---

Lots more sixes such as, TIO:

ṖÆDfƇL - Link: time = T; dimensions = [M, N, ...]
Ṗ      - pop {T}
 ÆD    - divisors
    Ƈ  - keep those for which:
   f   -   filter keep {dimensions}
     L - length

RmFQL’ TIO

ḍẸ¥ⱮṖS TIO

×ⱮFQ<S, ×þFQ<S, ḍⱮṖṀƇL, ḍþṖṀƇL, ḍⱮṖṀ€S, ḍþṖṀ€S, ḍⱮṖẸ€S, ḍþṖẸ€S, ḍⱮṖẸƇL, ḍþṖẸƇL, Ḷ:€QL’, :þSṖṬS, ...

Answer 8

JavaScript (Node.js), 36 bytes

port of user1609012's Python answer

f=(M,N,T)=>--T&&!(T%M&&T%N)+f(M,N,T)

Try it online!

Explanation

Start from the end of the ray \$(t = T)\$, and count the number of times it bounced in it's way, that is, anytime \$t \equiv 1 \pmod M \lor t \equiv 1 \pmod N\$. It's easier to see if you extend the chamber infinitely and have the ray cross the chamber walls.

---

C (gcc), 39 bytes

port to C

f(M,N,T){T=--T?!(T%M&&T%N)+f(M,N,T):0;}

Try it online!

Answer 9

Octave, 33 bytes

@(M,N,T)nnz(union(1:M:T,1:N:T))-1

Try it online!

Thanks to @Luis Mendo for -2.

Octave, 35 bytes

@(M,N,T)numel(union(1:M:T,1:N:T))-1

Try it online!

Port of @Albert.Lang's Python answer.

Answer 10

JavaScript (Node.js), 46 bytes

M=>N=>g=(T,x,y)=>T--?!(x*y)+g(T,-~x%M,-~y%N):T

Try it online!

Answer 11

Scala, 156 bytes

Golfed version. Try it online!

def f(M:Int)(N:Int):(Int,Int,Int)=>Int={def g(T:Int,x:Int=0,y:Int=0):Int=if(T<1)-1 else if(x==0||y==0)1+g(T-1,(x+1)%M,(y+1)%N)else g(T-1,(x+1)%M,(y+1)%N);g}

Ungolfed version. Try it online!

object Main {
  def f(M: Int)(N: Int): (Int, Int, Int) => Int = {
    def g(T: Int, x: Int = 0, y: Int = 0): Int = {
      if (T == 0) T-1
      else if (x == 0 || y == 0) 1 + g(T - 1, (x + 1) % M, (y + 1) % N)
      else g(T - 1, (x + 1) % M, (y + 1) % N)
    }

    g
  }

  def main(args: Array[String]): Unit = {
    val testCases = Array(
      (5, 4, 11),
      (5, 4, 10),
      (1, 1, 10),
      (5, 1, 10),
      (4, 5, 16),
      (100, 100, 1),
      (3, 2, 9),
      (3, 2, 10),
      (6, 3, 18),
      (5, 3, 16),
      (1, 1, 100),
      (4, 4, 100),
      (2398, 2308, 4),
      (10000, 500, 501),
      (500, 10000, 502)
    )

    testCases.foreach { case (a, b, c) =>
      println(f(a)(b)(c, 0, 0))
    }
  }
}

Answer 12

Charcoal, 15 bytes

≔…¹ＮθＩ№×﹪θＮ﹪θＮ⁰

Attempt This Online! Link is to verbose version of code. Takes T as the first parameter. Explanation:

 …              Exclusive range from
  ¹             Literal integer `1` to
   Ｎ            First input as a number
≔   θ           Save in variable
         θ      Saved range
        ﹪       Vectorised modulo
          Ｎ     Second input as a number
       ×        Pairwise multiplied by
            θ   Saved range
           ﹪    Vectorised modulo
             Ｎ  Third input as a number
      №         Count of
              ⁰ Literal integer `0`
     Ｉ          Cast to string
                Implicitly print

Answer 13

Racket, 210 bytes

(define(r M N T[R 0][X 0][Y 0][x 1][y 1])(let*([A(+ X x)][B(+ Y y)][a(or(< A 0)(> A M))][b(or(< B 0)(> B N))])(if(= T 0)R(r M N(- T 1)(if(or a b)(+ R 1)R)(if a(- X x)A)(if b(- Y y)B)(if a(- x)x)(if b(- y)y)))))

Try it online!

---

Explanation

For starters, this will definitely not win. Looking at the other answers, there seems to be a simpler algorithm to solving this. But I don't want to just copy things without having any understanding on how or why they work, so I decided to use a bruteforcing method of actually running the simulation.

Our function receives our three inputs M, N and T. It also receives a predefined state for the recursive loop.

(define (reflect M N T
                 [reflections 0]
                 [x-pos 0] [y-pos 0]
                 [dx 1] [dy 1])
  ...)

We then calculate the next x and y position, and see whether the next position are out-of-bounds (-oob).

  (let* ([next-x-pos (+ x-pos dx)]
         [next-y-pos (+ y-pos dy)]
         [next-x-oob (or (< next-x-pos 0) (> next-x-pos M))]
         [next-y-oob (or (< next-y-pos 0) (> next-y-pos N))])
    ...)

Once those values are calculated, we check whether our simulation time T is equal to zero. If it is, we return the resulting number of reflections. Otherwise we repeat the loop with a new set of configurations:

1. Same M and N sizes.
2. T - 1.
3. If the next X and Y positions are out of bounds, reflections + 1, else reflections.
4. If the next X position is out of bounds, recalculate the next position by flipping dx.
5. If the next Y position is out of bounds, recalculate the next position by flipping dy.
6. If the previously calculated next-x-pos is out of bounds, flip dx.
7. If the previously calculated next-y-pos is out of bounds, flip dy.

(define (reflect M N T
                 [reflections 0]
                 [x-pos 0] [y-pos 0]
                 [dx 1] [dy 1])
  (let* ([next-x-pos (+ x-pos dx)]
         [next-y-pos (+ y-pos dy)]
         [next-x-oob (or (< next-x-pos 0) (> next-x-pos M))]
         [next-y-oob (or (< next-y-pos 0) (> next-y-pos N))])
    (if (= T 0)
        R
        (reflect M N (- T 1)
                 (if (or next-x-oob next-y-oob)
                     (+ reflections 1)
                     reflections)
                 (if next-x-oob
                     (- x-pos dx)
                     next-x-pos)
                 (if next-y-oob
                     (- y-pos dy)
                     next-y-pos)
                 (if next-x-oob
                     (- dx)
                     dx)
                 (if next-y-oob
                     (- dy)
                     dy))))

Have an awesome weekend!

Answer 14

05AB1E, 8 bytes

<Lsδ÷Ùg<

Try it online or verify all test cases.

Explanation:

<L        # Use the first (implicit) input, and push a list in the range [1,input-1]
  s       # Swap to push the second (implicit) input-pair
   δ      # Apply double-vectorized:
    ÷     #  Integer-division
     Ù    # Uniquify this list of pairs
      g   # Pop and push the length
       <  # Decrease it by 1
          # (after which the result is output implicitly)

Answer 15

Thunno 2 L, 6 bytes

ėsȷ÷Uṫ

Try it online!

Port of alephalpha's Nekomata answer.

Explanation

ėsȷ÷Uṫ  # Implicit input
ė       # Push [1..t) to the stack
 s      # Swap so [m,n] is on top
  ȷ     # Outer product over:
   ÷    #  Integer division
    U   # Uniquify the list
     ṫ  # Remove the last item
        # Implicit output of length

Answer 16

Pyth, 7 bytes

tl{/R.Q

Try it online!

Port of @alephalpha's Nekomata answer.

Takes three inputs: time, width, height in that order.

Explanation

tl{/R.QQ    # implicitly add Q
            # implicitly assign Q = eval(input()) and .Q to a list of the remaining input
   /R.QQ    # map division over range(Q) with .Q as the second argument, this automatically vectorizes
  {         # deduplicate
 l          # take the length
t           # subtract 1