5
\$\begingroup\$

Challenge

Given a list of integers and a velocity, \$v\$, implement a sorting algorithm which simulates a program sorting the list from smallest to biggest at the given velocity.

Einstein's Theory of Special Relativity

What do I mean? Well assume your program takes a time, \$T\$, to sort a particular list. If you ran the program again at a higher velocity, \$v\$, according to a stationary observer your program would run slower and would take a different time, \$T'\$, to sort the same list.

How do you relate \$T\$ to \$T'\$? You use the equation for time dilation:

$$T' = \frac{T}{\sqrt{1-v^2}}$$

If we use geometrised units where \$v\$ is a fraction of the speed of light, and \$0\leq v \lt 1\$.

So you must change your program's running time by a factor of

$$\frac{1}{\sqrt{1-v^2}}$$

Output

You must output the sorted list

Rules

  • You are allowed an error of \$\pm0.1 \text{ s}\$
  • The length of the list, \$l\$, will be in the range \$1 \leq l \leq 50\$
  • The list will contain only integers
  • The velocity will be given in geometrised units
  • You may sort the list then wait before outputting

Examples

For these examples, assume my program takes a time of \$T = l^2 \text{ s}\$ to run, where \$l\$ is the length of the list, regardless of the contents of the list:

List, Velocity > Sorted list, Time taken
[9,8,7,6,4,3,2,1], 0.5 > [1,2,3,4,5,6,7,8,9], 93.5307
[8,0,0,5,6], 0.1 > [0,0,5,6,8], 25.1259
[7,7,7,7,7,7,7], 0.999 > [7,7,7,7,7,7,7,7], 453.684

Your timings do not need to be as accurate.

Winning

Shortest code wins.

\$\endgroup\$
  • \$\begingroup\$ Suppose your program sorts a list L in time T in the 'normal' rest frame (v=0). Then, if we run with the same list L with v=sqrt(0.5), how long should your program take to run? 2*T or 3*T or some other number? \$\endgroup\$ – Chas Brown Jul 26 '18 at 0:30
  • \$\begingroup\$ Perhaps use the time or restricted-time tags? \$\endgroup\$ – Asone Tuhid Jul 26 '18 at 9:09
  • \$\begingroup\$ @ChasBrown your program should take T/sqrt(1-v**2) to run. For v=sqrt(0.5), then your program should run for sqrt(2)*T \$\endgroup\$ – Beta Decay Jul 26 '18 at 9:17
  • \$\begingroup\$ @ChasBrown If your program runs for a time T, then it should pause for a time of T/sqrt(1-v**2) - T \$\endgroup\$ – Beta Decay Jul 26 '18 at 9:19
  • \$\begingroup\$ @Beta Decay: I agree with your latter comment ("... should pause... - T"); but your previous with "should run for sqrt(2)*T..." still seems a bit off, computationally... \$\endgroup\$ – Chas Brown Jul 26 '18 at 9:40
5
\$\begingroup\$

Bash, 56 55 bytes

-1 bytes thanks to Digital Trauma (using z instead of pushing 1)

for n in $2;{
sleep `dc -e"9k$n z$1d*-v/f"`&&echo $n&
}

Try it online!

Explanation

Sleep sort loops over all the integers, for each \$n\$ it does the following in the background:

  • set a timer of \$n\$ seconds (or another time unit)
  • print \$n\$

Instead of using one second we divide \$n\$ by \$\frac{1}{\sqrt{1-v^2}}\$ which is achieved by the following dc code:

9k              # set precision to 9 digits
  $n            # push n                    [n]
     z          # push size of stack        [1,n]
      $1        # push v                    [v,1,n]
        d*      # duplicate & multiply      [v^2,1,n]
          -     # subtract                  [1-v^2,n]
           v    # square root               [sqrt(1-v^2),n]
            /   # divide                    [n/sqrt(1-v^2)]
             f  # print
\$\endgroup\$
2
\$\begingroup\$

Python 2, 88 87 91 bytes

-1 byte thanks to Mr. Xcoder

from time import*
def f(l,v):t=time();s=sorted(l);d=time()-t;sleep(d/(1-v*v)**.5-d);print s

Try it online!

\$\endgroup\$
  • \$\begingroup\$ print instead of return should, as usual in Python 2, save a byte. \$\endgroup\$ – Mr. Xcoder Jul 25 '18 at 19:57
  • \$\begingroup\$ Suppose v=.5**.5; then 1/(1-v*v)**.5 = 2; and suppose the actual sort takes T=time()-t seconds. Your function then takes a total of 3*T seconds to complete, which is too long; it should only take 2*T seconds. So I think you want something like: u=(1-v*v)**.5;sleep((time()-t)*(1-u)/(u)). \$\endgroup\$ – Chas Brown Jul 25 '18 at 21:55
  • \$\begingroup\$ @ChasBrown hmm, I followed the OP's equation \$\endgroup\$ – Rod Jul 25 '18 at 23:53
  • 1
    \$\begingroup\$ @Rod: I've asked the question to OP. They key to me is when v=0, it should take the same amount of time as it would just to sort the list normally with none of this funny business; but using the (not unreasonable) interpretation you give, it would take twice that long. \$\endgroup\$ – Chas Brown Jul 26 '18 at 0:31
  • \$\begingroup\$ @ChasBrown I realised the error now, fixed it! \$\endgroup\$ – Rod Jul 26 '18 at 11:51
1
\$\begingroup\$

APL (Dyalog), 52 bytes

{t←2⊃⎕AI⋄r←⍵[⍋⍵]⋄r⊣⎕DL 1e¯3×s-(s←t-2⊃⎕AI)÷.5*⍨1-⍺*2}

Try it online!

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

Clean, 168 bytes

import StdEnv,System.Time,System._Unsafe,Debug.Performance
?u=:(Clock m,l)n#!(Clock i)=accUnsafe clock
|toReal i>toReal m*1E4/sqrt(one-n*n)=l= ?u n

?o(measureTime sort)

Try it online!

A composed function literal which times the sorting of the list, and then loops until an appropriate additional number of ticks have passed.

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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