Paradox of time travel

Question

A man has two devices.

• A time machine - He can control this machine by thinking. It allows him to travel from any point in time to another point in time in the past or future (or even the present point in time) in no time at all. Note that if he travels to the past from B to A, then all normal events (time machines, alternators excluded) from A to B must repeat in the exact same way. Then from point B, he is taken back to point A. Thus, a single time travel creates an infinite loop.
• Alternator - Realising this problem, he creates another machine. He notices that, even though all physical events get repeated in a loop, his thoughts may be different. Hence this machine was designed to be controllable by thought as well. The machine can be used at any time to provide an alternate future (but not past) with respect to the time he used it.

Example

I'll explain all the details using a lengthy example.

1000 T+250 250 T+0 500 T-200 100 T-50 125 A 225 T-400 500 A 100 T-200 150 T-25 100 T+100 50 A 25

• 1000 years pass. It is year 1000 now.
• He travels from 1000 to 1250.
• 250 years pass. It is year 1500 now.
• He travels from 1500 to 1500. This has no effect (and can be ignored).
• 500 years pass. It is now year 2000
• He travels from 2000 to 1800.
• 100 years pass. It is year 1900 now.
• He travels from 1900 to 1850.
• 125 years pass: However, this time, as he is in a loop, things are different. 50 years pass from 1850 to 1900. He loops back to 1850. Another 50 years pass from 1850 to 1900. He loops back again. 25 years pass and it is 1875, thus completing 125 years.
• He uses the alternator. Now there exists an alternate future to the year 1875, which he is now in. The past has not changed.
• 225 years pass. It is now year 2100.
• He travels from 2100 to 1700.
• 500 years pass: 175 years from 1700 to 1875 pass normally. No he encounters the alternator again, which means that now a 3rd future has been created post-1875. 325 years pass normally, making it year 2200.
• Using an alternator now has no effect (and can be ignored) since there exists only one future to 2200 which has not yet been defined.
• 100 years pass. It is now 2300.
• He travels from 2300 to 2100.
• 150 years pass: 100 years from 2100 to 2200 pass normally. A second future gets created from 2200. 50 years pass and it is now year 2250.
• He is supposed to go from 2250 to 2225. However, there now exist two 2225s in two different timelines. Hence this leads to a paradox, since we cannot determine which point in time he will reach. (We will not assume that he goes to the more recent timeline) Hence this terminates our simulation.
• Anything further 100 T+100 50 A 25 is completely ignored since a paradox has occured and our simulation has stopped running.

Hint: If you are struggling to understand the example, imagine time to be like a path you are digging in the earth. If you are time travelling, you are creating a teleporter. If you are using the alternator, you are digging a new path into the wall of an existing path.

Paradox

Assume A, B and C are three points in time (one after another). A paradox is said to have occurred iff:

• you are at a point C, there exists an alternator at a point B, there exists more than one future to point B (and you are in one of them), and you attempt to access any point between B and C via time travel.
• you are at a point A, there exists an alternator at a point B, there exists more than one future to point B, and you try to access a point C (after B) via time travel.

Input

A series of events, similar to the example. (Format is flexible.)

Output

A truthy/falsey value, indicating whether a paradox has occured.

Challenge

Shortest code (in bytes) wins.

Answer 1

Ruby, 510 460 bytes

p=[0];w=[n=x=0]
i=gets.split.map{|s|
if x!=1
if s[0]=="A"
w<<n
else
if s[0..1]=="T+"
t=n
q=s[2..-1].to_i
if w[-1]==t||(w[-1]>t&&w[-1]<n+q)
w<<w[-1]
n+=q
else
n+=(t<p[-1]&&n+q>p[-1])?q%(p[-1]-n):q
end
elsif s[0..1]=="T-"
t=n
p<<n
n-=s[2..-1].to_i
x=(x==0&&w[-1]>0&&t>w[-1]&&n>w[-1])?1:0
else
t=n
q=s.to_i
if w[-1]==t||(w[-1]>t&&w[-1]<n+q)
w<<w[-1]
n+=q
else
n+=(t<p[-1]&&n+q>p[-1])?q%(p[-1]-n):q
end
end
end
else
break
end}
p x

Input

As per example

Output

0 = No Paradox, 1 = Paradox

Sample

The sample input provided: 1000 T+250 250 T+0 500 T-200 100 T-50 125 A 225 T-400 500 A 100 T-200 150 T-25 100 T+100 50 A 25 returns 1, indicating a paradox occurred.

Notes

This is not only the first codegolf exercise I attempt, but it is also the first Ruby program I have written. Hence, it could probably be even shorter.

Brief Explanation

p: Infinite loops
w: Alternate timelines
n: Now (regardless of timeline)
x: Paradox

Infinite loops will only occur while traveling forward in time. I am happy for any feedback - especially if it is pointing out a better way to solve this.

Answer 2

05AB1E, 93 92 86 82 bytes

ðU0V#vyAQiYˆðUëy.ïiYy+DX˜såàiXD€нY@Ïн©θ-®¥OÄ%®θY-YOVëVëYy¦+©¯@àXðʘà*i1q}XY®Ÿª{U®V

Input is in the same format as in the challenge description, except that alternator A is abcdefghijklmnopqrstuvwxyz instead to save a byte.
Outputs 1 if a paradox occurred, or the input itself if not (only 1 is truthy in 05AB1E, everything else is falsey).

Loosely based on my Java 10 answer.

Try it online.

Or try it online with added debug-lines (TODO: Create proper test suite with all test cases at once..):
- Test case with backward time-travel paradox: Try it online.
- Test case with forward time-travel paradox: Try it online.
- Test case without time-travel paradox: Try it online.

Explanation:

ðU                         # Set variable `X` (time-travels) to a space character " "
0V                         # Set variable `Y` (current year) to 0
#                          # Split the (implicit) input by spaces
 v                         # And loop over each event `y`:
  yAQi                     #  If the current event `y` is an alternator ("abcdefghijklmnopqrstuvwxyz"):
      Yˆ                   #   Add the current year `Y` to alternators-list `GB`
      ðU                   #   And reset variable `X` to " "
  ëy.ïi                    #  Else-if the current event `y` is an integer:
       Yy+                 #   Calculate the current year `Y` plus the integer `y`
          D                #   Duplicate `Y+y`
           X˜såài          #   If this `Y+y` is within any of the time-travel ranges:
                 X €н      #    Get the starting positions of each time-travel
                     Y@    #    Check for each starting position if the current year `Y` is >= it
                  D    Ï   #    And only leave the time-travel ranges for which this is truthy
                        н  #    Then pop and push the first one
                         © #    Store this time-travel range in variable `r` (without popping)
                 θ         #    Pop and only leave the time-travel destination
                  -        #    Subtract it from the `Y+y` we duplicated
                       %   #    And modulo it with:
                   ®¥OÄ    #     The absolute distance of the time-travel `r`
                 ®θ        #    Then push the time-travel destination again
                   Y-      #    And subtract the current year `Y`
                 YO        #    Then sum these two and the current year `Y` together
                   V       #    And pop and store it as new year `Y`
       ë                   #   Else (`Y+y` is not within any time-travel ranges)
        V                  #    Simply pop and store the duplicated `Y+y` as new year `Y`
  ë                        #  Else (the current event `y` is a time-travel)
    y¦                     #   Remove the leading "T"
   Y  +                    #   And add the value to the current year `Y`
       ©                   #   Store this value in variable `r`
        ¯@à                #   Check if any alternator in list `GB` is >= this value
           XðÊ˜à           #   Check if there are any time-travels
                *i  }      #   And if both are truhy:
                  1        #    Push a 1
                   q       #    Stop the program
                           #    (after which the top of the stack is output implicitly)
    Y®Ÿ                    #   Create a list in the range [current year `Y`, new year `r`]
   X   ª                   #   Append it to the time-travels `X`
        {                  #   And then sort these time-travels
         U                 #   After which we pop and store it as updated `X`
   ®V                      #   And then set `Y` to the new year `r`
                           # (if we haven't reached `q`, the (implicit) input is output instead)

Answer 3

Java 10, 498 485 478 bytes

import java.util.*;s->{var a=new Stack<Long>();var m=new TreeMap<Long,Long>();long p=0,c=0,t,v,k;o:for(var S:s.split(" "))if((t=S.charAt(0))>65){var b=S.charAt(1)>44;v=new Long(S.substring(2));for(var A:a)p=A>c+(b?-v:v)|m.size()<1?p:1;if(v>0)m.put(c,b?c-v:c+v);c+=b?-v:v;}else if(t>64){a.add(c);m.clear();}else{t=new Long(S);e:for(var e:m.entrySet())if((k=e.getKey())>=c){for(v=c;v<=c+t;)if(a.contains(v++))break e;c=(v=e.getValue())+(c+t-v)%(k-v);continue o;}c+=t;}return p>0;}

Input is (for now) in the same format as in the challenge description.

-13 bytes thanks to @BenjaminUrquhart.
-7 bytes thanks to @ceilingcat.

Try it online or try it online with added debug-lines.

Explanation:

import java.util.*;            // Required import for the List and TreeMap
s->{                           // Method with String parameter and boolean return-type
  var a=new Stack<Long>();     //  Create a List for the alternators
  var m=new TreeMap<Long,Long>();
                               //  Create a sorted Map for the time-travels
  long p=0,                    //  Paradox-flag, initially 0
       c=0,                    //  Current year, initially 0
       t,v,k;                  //  Temp-values, uninitialized
  o:for(var S:s.split(" "))    //  Loop over the input substrings split by space:
    if((t=S.charAt(0))>65){    //   If the first character is a 'T':
      var b=S.charAt(1)>44;    //    Check if the second character is a '-'
      v=new Long(S.substring(2));
                               //    Convert the String-value to a number
      for(long A:a)            //    Loop over the alternators
        p=A>                   //     If an alternator is larger than:
            c+                 //      The current year, plus
              (b?              //      If we travel backwards in time:
                 -v            //       Subtract the value
                :              //      Else (we travel forward in time):
                 v)            //       Add the value
          |m.size()<1?         //     Or if no previous time-travels occurred:
           p                   //      Leave the paradox-flag the same
          :                    //     Else:
           1;                  //      Set the paradox-flag to 1
      if(v>0)                  //     If the value is not 0 (edge-case for "T+0")
        m.put(c,b?c-v:c+v);    //      Add the from-to time-travel to the Map
      c+=b?-v:v;}              //     Increase/decrease the year accordingly
    else if(t>64){             //   Else-if the character is an 'A':
      a.add(c);                //    Add the current year to the alternators-list
      m.clear();}              //    And empty the time-travel Map
    else{                      //   Else (it's a number)
      t=new Long(S);           //    Convert the String to a number
      e:for(var e:m.entrySet())//    Loop over the time-travels:
        if((k=e.getKey())      //     If the time-travel starting point is
                         >=c){ //     larger than or equal to the current year
          for(v=c;v<=c+t;)     //      Loop from the current year to the year+number:
            if(a.contains(v++))//       If the alternator-list contains any of these years
              break e;         //        Stop the time-travel loop
          c=                   //      Set the current year to:
             (v=e.getValue())  //       The time-travel destination
             +                 //       Plus:
              (c+t             //        The current year plus the number
                  -v)          //        minus the time-travel destination
                     %(k-v);   //        Modulo the time-travel from-to distance
          continue o;}         //      And then continue the outer input-loop
      c+=t;}                   //    Increase the current year by the number 
  return p>0;}                 //  Return whether the paradox-flag is 1