21
\$\begingroup\$

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 , so shortest answer wins.

\$\endgroup\$
4
  • \$\begingroup\$ Suggested tag: fizzbuzz /hj \$\endgroup\$ Commented Jul 16, 2023 at 1:38
  • \$\begingroup\$ If the light bounces off a corner, is that one reflection or two? \$\endgroup\$
    – xnor
    Commented Jul 16, 2023 at 2:10
  • \$\begingroup\$ @xnor It counts as one reflection. \$\endgroup\$ Commented Jul 16, 2023 at 13:15
  • 1
    \$\begingroup\$ Related \$\endgroup\$
    – c--
    Commented Jul 16, 2023 at 20:57

16 Answers 16

19
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ This is creative, another nice one from Albert.Lang \$\endgroup\$
    – justhalf
    Commented Jul 17, 2023 at 8:35
9
\$\begingroup\$

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\$

\$\endgroup\$
7
\$\begingroup\$

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
\$\endgroup\$
1
6
\$\begingroup\$

Python 3, 50 bytes

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

Try it online!

\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$
0
5
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ Another 6-byter that might inspire something: ×þFQ<S \$\endgroup\$ Commented Jul 16, 2023 at 3:07
  • 1
    \$\begingroup\$ ḍⱮṖṀƇL is also 6 bytes. \$\endgroup\$
    – Neil
    Commented Jul 16, 2023 at 7:06
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Perfect use of gerund +`- \$\endgroup\$
    – Jonah
    Commented Jul 16, 2023 at 5:04
  • 1
    \$\begingroup\$ Thanks! Means a lot coming from someone so experienced lol \$\endgroup\$
    – south
    Commented Jul 16, 2023 at 5:43
4
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Looks good to me, @LuisMendo \$\endgroup\$
    – loopy walt
    Commented Jul 19, 2023 at 1:34
3
\$\begingroup\$

JavaScript (Node.js), 46 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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))
    }
  }
}

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 15 bytes

≔…¹NθI№×﹪θN﹪θN⁰

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

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

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!

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.