4
\$\begingroup\$

The Scenario

I am building a fancy oscilloscope but I need your help. The oscilloscope can display any number of individual waveforms at the same time (e.g. sine waves) but I don't know how to synchronise the display so it doesn't jump around too much.

The Challenge

Your program or function will take a series of floating point numbers as its input. The first number will be the width of the oscilloscope screen (there will be different models with larger or smaller screens). The remaining numbers will be the wavelength (not the frequency) of each waveform and will always be less than the width of the display. The amplitude of the waveforms is unimportant, so is not given. The only thing you need to know about the amplitude is that it will never be zero.

Your code must output the distance from the start where all the waveforms are as in-sync as possible for the width of the display. This is assumed to be when there is the smallest horizontal distance possible when each waveform is at 0 degrees (therefore, also with a height of zero). If there are multiple best matches, use the largest one (furthest from the left edge of the display).

An example is displayed below. The vertical lines are where each of the waves are most in-sync with the others. The inputs are 100 [3.14159265358979, 2.71828182845905, 1.41421356237310] (the image has been scaled up by a factor of 10) and the outputs, in order, are [40.8407044966673, 40.7742274268858, 41.0121933088199]. Your code must display at least 5 significant digits unless the decimal representation ends before that. The numbers must be output in the same order as the inputs.

Colour oscilloscope display

You need to find the greatest multiple of each input number where the maximum distance between them all is as small possible, without going over the upper bound of the screen width. If there is even a single irrational ratio the smallest maximum distance will never be 0 for finite numbers. [0 ...] will never be an answer as all of the waveforms will fit at least once on the display before repeating. The maths to calculate the numbers is a lot easier than it appears initially. You can separate the output numbers with any delimiter - it doesn't have to be a space or a comma; use brackets if there is an easier option in your language, as long as the digits are correct to as many places as shown. The same goes for the input; if it's easier to tab separate the numbers, for example, that's OK, as is any other delimiter as long as the numbers are input exactly as shown in the test data.

Test data:

In: 10 [3.16227766016838]
Out: [9.48683298050514]

In: 100 [3.16227766016838]
Out: [98.0306074652198]

In: 105 [6, 7]
Out: [84, 84]

In: 1050 [6, 7]
Out: [1050, 1050]

In: 90 [5, 6, 7]
Out: [85, 84, 84]

In: 100 [5, 6, 7]
Out: [90, 90, 91]

In: 200 [5, 6, 7]
Out: [175, 174, 175]

In: 300 [5, 6, 7]
Out: [210, 210, 210]

In: 100 [1.4142135623731, 3.14159265358979, 2.71828182845905]
Out: [41.0121933088199, 40.8407044966673, 40.7742274268858]

In: 100 [3.14159265358979, 2.71828182845905, 1.4142135623731]
Out: [40.8407044966673, 40.7742274268858, 41.0121933088199]

In: 300 [3.14159265358979, 2.71828182845905, 1.4142135623731]
Out: [141.371669411541, 141.350655079871, 141.42135623731]

In: 900 [3.14159265358979, 2.71828182845905, 1.4142135623731]
Out: [383.274303737954, 383.277737812726, 383.25187540311]

In: 1000 [3.14159265358979, 2.71828182845905, 1.4142135623731]
Out: [907.920276887449, 907.906130705323, 907.92510704353]

In: 100 [1.73205080756888, 2, 2.23606797749979, 2.44948974278318, 2.64575131106459]
Out: [24.2487113059643, 24, 24.5967477524977, 24.4948974278318, 23.8117617995813]

In: 1000 [1.73205080756888, 2, 2.23606797749979, 2.44948974278318, 2.64575131106459]
Out: [129.903810567666, 130, 129.691942694988, 129.822956367509, 129.641814242165]

As an example, lets take the following test case:

In: 200 [5, 6, 7]
Out: [175, 174, 175]

At [5, 6, 7] ([1*5, 1*6, 1*7]) you can show that each number is as close as possible to its neighbours without changing any of the multiples. The minimum distance to contain all the numbers is 2 (7-5). But is there a smaller solution less than 200? At [35, 36, 35] ([7*5, 6*6, 5*7]) the minimum distance to contain all the numbers is now only 1 (36-35). Can we get it smaller? The next smallest distance is at [210, 210, 210] ([42*5, 35*6, 30*7]) which is optimal at 0 (210-210), however, 210 is larger than 200 so is not allowed in this case. The largest solution below or equal to 200 is [175, 174, 175] ([35*5, 29*6, 25*7]), also with a distance of 1 (175-174).

This is code-golf, so shortest solution wins!

\$\endgroup\$
  • \$\begingroup\$ Judging by the test cases it looks like all the waveforms are at 0 degrees at position 0, but 0 isn't allowed as an answer? Unless I'm mistaken and missed something, could you please clarify these two points in the post? \$\endgroup\$ – user81655 Jan 31 '16 at 11:22
  • \$\begingroup\$ You are talking about the "point" where the horizontal distance is minimal. But where exactly is this point, as there actually is whole range to be considered? BTW: You could remove a ton of unnecessary information from this challenge. In the end we only have to consider arithmetic series, you can omit the whole part about sine waves and the oscilloscope. That way, the challenge itself would be a lot clearer. \$\endgroup\$ – flawr Jan 31 '16 at 11:29
  • \$\begingroup\$ @flawr It took me a while to grasp this. Take the test case 105 6 7 which looks a lot clearer like this: 105 [6,7]. The waveforms coincide exactly at 42 and 84, and then again at 126, but you have to take the largest which will fit in the screen width, which is therefore 84. For some of the other cases a perfect match is not available. I think the oscilloscope analogy does help a little because it is a practical application of what is required, but I think a bit of explanation of the test cases could make it much clearer. \$\endgroup\$ – Level River St Jan 31 '16 at 14:57
  • 2
    \$\begingroup\$ I think this question is asking for the greatest multiple of the LCM which is less than a given bound, but it's not clear what the output should be if the LCM exceeds that bound. \$\endgroup\$ – Peter Taylor Jan 31 '16 at 15:30
  • 3
    \$\begingroup\$ What does "closest to all of them" mean? What is the actual function to minimise? \$\endgroup\$ – Peter Taylor Feb 1 '16 at 0:01
2
\$\begingroup\$

Python (3.5) 240 bytes

A non optimal solution. It works on all test but that's a really really slow solution since we test each possibility.

Solution

import numpy as n
def f(w,s):
 l = len(s)
 def g(t,m,k,z):
  if t!=[]:
   u,*v=t
   for i in n.arange(u,w+1,u):
    m,k=g(v,m,k,[*z,i])
  else:
   j=sum(abs(sum(z[1:])/l-i) for i in z[1:])
   if j<=m+1e-9 :
    return j,z
  return m,k
 print(g(s,w,0,[0])[1][1:])

Explanation

Importation of numpy module

import numpy as n

Function definition w:screen length s:"wavelength"

def f(w,s):
 l = len(s)

Définition of the recursive function with t wavelength, m minimum, k value of the minimum point, z current point

 def g(t,m,k,z):

the recursive test : if t is non empty we go "deeper" in the recursion

  if t!=[]:
   u,*v=t

loop on each zeros of the sinus function

   for i in n.arange(u,w+1,u):

call the recursive function

    m,k=g(v,m,k,[*z,i])
  else:

the "function" to minimize

   j=max(z[1:])-min(z[1:])

test for the minimum (1e-9 because there is a precision issu)

   if j<=m+1e-9 :
    return j,z
  return m,k
 print(g(s,w,0,[0])[1][1:])

Results:

>>> f(300, [5, 6, 7])
[210, 210, 210]
>>> f(100, [5, 6, 7])
[90, 90, 91]

Previous iteration

In first try i use the distance between points and barycenter

   j=sum(abs(sum(z[1:])/l-i) for i in z[1:])
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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