9
\$\begingroup\$

Part of the Code Golf Advent Calendar 2022 event. See the linked meta post for details.


As a Christmas gift, you were given a toy solar system. In this toy, all the orbits are circular and happen in the same plane. Each planet starts at a fixed location, has a fixed circumference orbit, and moves at a fixed speed (all in the same direction). You want to figure out, given these variables, at what time all of the planets will align (relative to the star which they orbit).

For example, if we had three planets with rings of size 4, 8, and 12, and the planets started in positions 2, 1, and 0 respectively, it would look like this:

enter image description here

The challenge

You are given three lists of non-negative integers, which are each \$n>1\$ items long:

  • \$R_x\$, indicating the circumference of orbit for planet \$x\$ (will not be zero)
  • \$P_x\$, indicating the start position of planet \$x\$ (positions are zero-indexed; you can assume \$P_x < R_x\$ for all \$x\$)
  • \$S_x\$, indicating the number of units that planet \$x\$ moves along its orbit

(You may also take these as a collection of 3-tuples \$(R_x, P_x, S_x)\$ or a permutation thereof.)

Starting from \$t=0\$, after each time step, each planet moves \$S_x\$ units around their orbit (i.e. \$P_x \leftarrow (P_x + S_x) \mod R_x\$). Your goal is to find the smallest time \$t\$ where \$P_x / R_x \$ of all the planets are the same, i.e. the smallest \$t\$ such that $$((P_1 + t * S_1) \mod R_1) / R_1 = ((P_2 + t * S_2) \mod R_2) / R_2 = \ldots = ((P_n + t * S_n) \mod R_n) / R_n$$ . You may assume that such a time exists.

Test cases

\$R\$ \$P\$ \$S\$ \$t\$
\$[1,1]\$ \$[0,0]\$ \$[0,0]\$ \$0\$
\$[100,100]\$ \$[1,0]\$ \$[1,0]\$ \$99\$
\$[4,8,12]\$ \$[0,1,0]\$ \$[1,5,3]\$ \$5\$

Standard loopholes are forbidden. Shortest code wins.

\$\endgroup\$
3
  • 5
    \$\begingroup\$ But, you know, Kepler's third law suggests that \$\frac{R_x}{S_x^2}\$ is a constant. \$\endgroup\$
    – tsh
    Dec 26, 2022 at 1:42
  • 6
    \$\begingroup\$ @tsh Unfortunately, this is a cheaply made model which does not conform to the law of universal gravitation. \$\endgroup\$ Dec 26, 2022 at 2:11
  • \$\begingroup\$ Side note: Speed does not include the information of direction. Ignoring the formula at the bottom, it could be the case some planets moved clockwise, others counter-clockwise. Maybe orbital angular velocity would have been a better term? \$\endgroup\$ May 13 at 12:00

15 Answers 15

9
\$\begingroup\$

Vyxal, 11 bytes

?*?+?~%/≈)ṅ

Try it Online!

          ṅ # First integer
---------)  # where...
?*          # Multiply by speeds
  ?+        # Add initial positions
    ?~%     # Modulo by orbit sizes, without popping
       /    # Divide by orbit sizes
        ≈   # Are they all equal?
\$\endgroup\$
2
\$\begingroup\$

Pip, 24 bytes

W$!=:{(b+c*i)%a/a}MUaUii

Try It Online!

Takes inputs as a list of lists/tuples for each planet. Explanation:

W                   # While
 $!=:               # Fold not-equal of
     {(b+c*i)%a/a   # The planet position formula
     }MUa           # Mapped over all input tuples
 Ui                 # Increment i
i                   # Return i once the loop is exited
\$\endgroup\$
2
\$\begingroup\$

Python NumPy, 46 bytes

f=lambda R,P,S:(P/R).ptp()and 1+f(R,(P+S)%R,S)

Attempt This Online!

Expects 3 NumPy arrays. May (will) have floating point issues. Does the test cases ok, though. Assumes time moves in steps (in other words the solution is a nonnegative integer) which OP seems to imply.

How?

Simple brute force. Proceed time step by time step.

\$\endgroup\$
2
  • \$\begingroup\$ does this program even exit? i can’t seems to run it \$\endgroup\$
    – okie
    Dec 26, 2022 at 1:08
  • \$\begingroup\$ @okie It does, demo is at link below code block. \$\endgroup\$ Dec 26, 2022 at 1:40
2
\$\begingroup\$

PARI/GP, 53 bytes

f(r,p,s,i)=if(#Set([p[i++]%x/x|x<-r])>1,1+f(r,p+s,s))

Attempt This Online!

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

Thunno 2, 8 bytes

1Ƙ×+Œ⁶/ạ

Attempt This Online! Takes S then P then R.

Output as a singleton list (allowed by community consensus). Add the h flag if you want output as an integer - Attempt This Online!.

Explanation

1Ƙ×+Œ⁶/ạ  # Implicit input
1Ƙ        # First integer where:
  ×       #  Multiply by the first input
   +      #  Add to the second input
    Π    #  Modulo by the third input
     ⁶/   #  Divide by the third input
       ạ  #  Are they all equal?
          # Implicit output
\$\endgroup\$
1
\$\begingroup\$

Python, 83 bytes

f=lambda R,P,S,t=0:1<len({(p+s*t)%r/r for r,p,s in zip(R,P,S)})and f(R,P,S,t+1)or t

Attempt This Online!

Recursive function, takes input lists \$R\$, \$P\$ and \$S\$.

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

Charcoal, 38 bytes

≔×÷Πθθηη≔×÷ΠθθζζW›⌈η⌊η«UMη﹪⁺κ§ζλΠθ→»Iⅈ

Attempt This Online! Link is to verbose version of code. Explanation:

≔×÷Πθθηη≔×÷Πθθζζ

Scale P and S so that their R value becomes the product of the initial R values.

W›⌈η⌊η«

Until the P values are equal, ...

UMη﹪⁺κ§ζλΠθ

... add the S values to them modulo the R product, and...

... keep track of the time.

»Iⅈ

Output the final time.

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

JavaScript (Node.js), 58 bytes

Z=>g=t=>Z.some(x=v=>x-(x=(v.P+~~t*v.S)%v.R/v.R))&&1+g(-~t)

Try it online!

JavaScript (Node.js), 60 bytes

Z=>(g=t=>Z.some(x=v=>x-(x=(v.P+t*v.S)%v.R/v.R))&&1+g(-~t))``

Try it online!

JavaScript (Node.js), 68 bytes

(R,P,S)=>(g=t=>R.some(x=(v,i)=>x-(x=(P[i]+t*S[i])%v/v))&&1+g(-~t))``

Try it online!

Thank tsh for -2 bytes

No floating issue

\$\endgroup\$
3
  • \$\begingroup\$ Uh, can't the first one be just x=v=>...? \$\endgroup\$
    – emanresu A
    Dec 26, 2022 at 3:29
  • \$\begingroup\$ ((v.P+t*v.S)%v.R)/v.R could be (v.P+t*v.S)%v.R/v.R. And if you don't care about floating point errors, you can use (v.P+t*v.S)/v.R%1 \$\endgroup\$
    – tsh
    Dec 26, 2022 at 3:38
  • \$\begingroup\$ @emanresuA g is called with "" \$\endgroup\$
    – l4m2
    Dec 26, 2022 at 3:48
1
\$\begingroup\$

05AB1E, 13 12 bytes

∞<.Δ*²+¹%¹/Ë

Try it online or verify all test cases.

Explanation:

∞            # Push an infinite list of positive integers: [1,2,3,...]
 <           # Decrease it to a non-negative list: [0,1,2,...]
  .Δ         # Pop and find the first which is truthy for:
    *        #  Multiply the third† (implicit) input-speeds to the value
     ²+      #  Add the second input starting positions
       ¹%    #  Modulo it by the orbit sizes
         ¹/  #  Then divide that by the orbit sizes
           Ë #  Check if all values in the list are the same
             # (after which the found integer is output implicitly as result)

† -1 byte removing the explicit third input builtin ³. This will cause the very first iteration (for \$n=0\$) to multiply by the (implicit) first input orbit-sizes instead of intended third input-speeds, but this is irrelevant since it'll be a list of \$0\$s anyway for \$n=0\$. Every other iteration (\$n>1\$) will multiply by the intended (implicit) third input-speeds.

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

x86 32-bit machine code, 39 bytes

31 C0 48 40 60 92 96 31 FF 31 ED AD 93 AD 52 F7 E2 03 06 F7 F3 92 97 F7 E3 93 95 F7 E7 5A 39 D8 AD E1 E8 61 75 DD C3

Try it online!

Following the fastcall calling convention, this takes an array of triples of 32-bit integers in the order \$R_x,S_x,P_x\$, taking the length in ECX and the address in EDX.


This works by iterating through all values of \$t\$ and checking them.

To do the checking, each planet's fractional position is calculated and cross-multiplied with the previous fraction in order to check if the fractions are equal. The previous fraction is initialised to 0/0, which functions as being equal to anything.


In assembly:

f:
    xor eax, eax    # Set EAX to 0. EAX will hold the current time, t.
    dec eax         # Subtract 1 from EAX to cancel out the next instruction.
nexttime:
    inc eax         # Add 1 to EAX, advancing t.
    pushad          # Save all general-purpose registers' values onto the stack.
    xchg edx, eax   # Switch the array address into EAX and t into EDX.
    xchg esi, eax   # Switch the array address into ESI.
    xor edi, edi    # Set EDI (for the last numerator) to 0.
    xor ebp, ebp    # Set EBP (for the last denominator) to 0.
nextplanet:
    lodsd           # Load R_x into EAX, advancing the pointer.
    xchg ebx, eax   # Switch R_x into EBX.
    lodsd           # Load S_x into EAX, advancing the pointer.
    push edx        # Save the value of EDX (t) onto the stack.
    mul edx         # Multiply EAX by EDX, producing t*S_x.
                    # (Also, the high half of the product goes in EDX;
                    #   we're assuming the values fit in 32 bits, so that's 0.)
    add eax, [esi]  # Add P_x to EAX, producing P_x+t*S_x.
    div ebx         # Divide EDX:EAX by EBX (R_x). The quotient goes in EAX
  #  and the remainder, the numerator of this planet's fractional position, goes in EDX.
    xchg edx, eax   # Switch this numerator into EAX.
    xchg edi, eax   # Switch this numerator into EDI and the last numerator into EAX.
    mul ebx         # Multiply the last numerator by this denominator (into EDX:EAX).
    xchg ebx, eax   # Switch the product into EBX and this denominator into EAX.
    xchg ebp, eax   # Switch this denominator into EBP and the last denominator into EAX.
    mul edi         # Multiply the last denominator by this numerator (into EDX:EAX).
    pop edx         # Restore the value of t from the stack into EDX.
    cmp eax, ebx    # Compare the two products.
    lodsd           # Load P_x into EAX, advancing the pointer.
    loope nextplanet  # Decrease ECX by 1, counting down from the number of planets.
                      #  Jump back if the result is nonzero and the comparison was equal.
    popad           # Restore all general-purpose registers' values from the stack.
    jne nexttime    # Jump if the comparison was not equal.
    ret             # Return. (The time t in EAX is the return value.)
\$\endgroup\$
1
\$\begingroup\$

R, 41 bytes

f=\(r,p,s)sum(if(sd(p%%r/r))1+f(r,p+s,s))

Attempt This Online!

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

Pascal, 345 Bytes

This function requires a processor supporting at least Standard Pascal as defined in ISO standard 7185 (level 1).

type Z=integer;W=0..maxInt;P=record R,P,S: W end;function f(S:array[m..n:Z]of P):W;var t:W;i:Z;function a:Boolean;var i:Z;d:real;function q(i:Z):real;begin q:=S[i].P/S[i].R end;begin d:=0;for i:=m+1 to n do d:=d+abs(q(i)-q(i-1));a:=d=0 end;begin t:=0;while not a do begin t:=t+1;for i:=m to n do begin with S[i]do P:=(P+S)mod R end;end;f:=t end;

Readable/ungolfed version:

program planetaryAlignment(output);
    type
        integerNonNegative = 0..maxInt;
        planet = record
                circumference: integerNonNegative;
                start: integerNonNegative;
                speed: integerNonNegative
            end;
    var
        { test planetary systems }
        A, B: array[1..2] of planet;
        C:    array[1..3] of planet;
    
    { In this subroutine `system[i].start` means “current position.” }
    function planetaryAlignment(
            system: array[minimum..maximum: integer] of planet
        ): integerNonNegative;
        var
            { discrete time step }
            t: integerNonNegative;
        { checks whether all planets are aligned on a line }
        function aligned: Boolean;
            var
                i: integer;
                { accumulates differences in positions }
                delta: real;
            { planetary position expressed as cycles }
            function position(i: integer): real;
                begin
                    with system[i] do
                    begin
                        position := start / circumference
                    end
                end;
            begin
                delta := 0.0;
                
                for i := minimum + 1 to maximum do
                begin
                    delta := delta + abs(position(i) - position(i - 1))
                end;
                
                aligned := delta = 0.0
            end;
        { advance planetary system by a simulation step }
        procedure simulate;
            var
                i: integer;
            begin
                t := t + 1;
                
                for i := minimum to maximum do
                begin
                    with system[i] do
                    begin
                        start := (start + speed) mod circumference
                    end
                end
            end;
        { simulation loop until alignment condition is met }
        begin
            t := 0;
            
            while not aligned do
            begin
                simulate
            end;
            
            planetaryAlignment := t
        end;
    
    { ─── MAIN ──────────────────────────────────────────────────────────── }
    begin
        A[1].circumference :=   1; A[1].start :=   0; A[1].speed :=   0;
        A[2].circumference :=   1; A[2].start :=   0; A[2].speed :=   0;
        writeLn(planetaryAlignment(A));
        
        B[1].circumference := 100; B[1].start :=   1; B[1].speed :=   1;
        B[2].circumference := 100; B[2].start :=   0; B[2].speed :=   0;
        writeLn(planetaryAlignment(B));
        
        C[1].circumference :=   4; C[1].start :=   0; C[1].speed :=   1;
        C[2].circumference :=   8; C[2].start :=   1; C[2].speed :=   5;
        C[3].circumference :=  12; C[3].start :=   0; C[3].speed :=   3;
        writeLn(planetaryAlignment(C));
    end.
\$\endgroup\$
0
\$\begingroup\$

Japt v2.0a0, 21 bytes

Takes input in the order P, S, R.

@í+Vm*X)íuW í÷W äÎd}f

Try it

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

Scala, 158 bytes

\$ \color{red}{\text{Failed on the last case, I have no idea how to correct it.}} \$


Golfed version. Try it online!

def f(r:Seq[Int],p:Seq[Int],s:Seq[Int],i:Int):Int={if(r.indices.exists(index=>p(i%p.length)%r(index)!=0)){1+f(r,p.zip(s).map{case (pi,si)=>pi+si},s,0)}else 0}

Ungolfed version. Try it online!

object Main {
  def main(args: Array[String]): Unit = {
    val data = List(
      (List(1,1), List(0,0), List(0,0))
      ,(List(100, 100), List(1,0), List(1,0))
      //,(List(4,8,12), List(0,1,0), List(1,5,3))
    )

    data.foreach { case (r, p, s) =>
      println(s"$r, $p, $s -> ${f(r, p, s, 0)}")
    }
  }

  def f(r: List[Int], p: List[Int], s: List[Int], i: Int): Int = {
    if (r.indices.exists(index => p(i % p.length) % r(index) != 0)) {
      1 + f(r, p.zip(s).map { case (pi, si) => pi + si }, s, 0)
    } else {
      0
    }
  }
}
\$\endgroup\$
0
\$\begingroup\$

Haskell, 121 bytes

import Data.List
import Data.Ratio
z=zipWith.flip
t r p s=length$fst$break(null.tail.group.z(%)r)$iterate(z mod r.z(+)s)p

Try it online!

Haskell, 135 bytes

import Data.List
import Data.Ratio
t r p s=length$fst$break(null.tail.group.zipWith(flip(%))r)$iterate(zipWith(flip mod)r.zipWith(+)s)p

Try it online!

\$\endgroup\$

Your Answer

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

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