Inspired by http://xkcd.com/1331/

In this xkcd comic, there are several gifs that all blink with different frequency. I want to know what the period would be if was all a single GIF. Given a list of numbers representing the individual frequencies, output the period of the overall GIF.

Formal Definition

Input:

N
f1
f2
.
.
.
fN

Output:

Where N is the number of frequencies, fi is the ith frequency, and P is the resulting period of the total GIF.

You may choose to use any delimiting character you want(instead of \n), and you may exclude the N if you wish, and it will be inferred by the number of delimeters.

Some specifics

Frequencies are the closest double-precision floating point representation of the numbers provided as input.

The outputted period is a 64-bit unsigned integer, rounded(up on 0.5) to the nearest whole. Any input that would produce a period bigger than 2^64-1 is considered undefined behaviour.

Likewise any input <= 0 is considered undefined behaviour.

Win Condition

Code golf so shortest code wins!

code-golf

Cruncher

Posted 2014-02-19T21:08:08.107

Reputation: 2 135

Possible spoiler... wouldn't this just be the product of the given frequencies? – danmcardle – 2014-02-19T23:50:46.473

@crazedgremlin No it isn't, but you are pretty close. – Victor Stafusa – 2014-02-20T00:30:08.950

@crazedgremlin - If A is 2s and B is 4s, then the resulting period would be 4s, not 8s. – Digital Trauma – 2014-02-20T00:36:36.953

Ah, I see, thanks. @Cruncher, what exactly do you mean by "frequency"? Repetitions per second or the amount of time a repetition takes? I assume the former, as that is usually what frequency means. – danmcardle – 2014-02-20T00:41:12.073

There are at least 2 methods for this: Take the overall frequency as the GCD of the input frequencies and invert it. Or take the input frequencies, invert them all to get the periods and take the LCM as the overall period. I took the GCD. @DavidCarraher took the LCM. You just need to cope with the non-integers. – Victor Stafusa – 2014-02-20T02:20:30.117

I'm not going to post this since it's just expressing the already posted method in a more concise language, but the J answer would be 1%+./ with the requirement that the frequencies be given without N and space separated. Alternatively, *./1% with the same requirements. Right tool for the job. – Gareth – 2014-02-20T09:59:03.793

@crazedgremlin The inputs are frequencies (# of repetitions in unit time). And the output is period (units of time for each repetition) – Cruncher – 2014-02-20T13:42:22.357

Answers

APL, 4

∧/∘÷

∧ is both logical AND and numerical LCM (with domain over integers, floats, complex, rationals, whatever number stack is supported by the APL implementation) so ∧/ is reduction by LCM, or computing the LCM of an array.

Monadic ÷ is numeric inverse. So the composition ∧/∘÷ is the LCM of the inverses of the numbers supplied.

The other formula, inverse of the GCD, would be ÷∘(∨/), where the parentheses are needed to fix the precedence between ∘ and /.

You can try it online on http://tryapl.com/

Examples

      ∧/∘÷ .12 .02 3.9 .15 .99
100
      ∧/∘÷ (16÷5)(2÷3)(2.35)(1÷7)
420

Tobia

Posted 2014-02-19T21:08:08.107

Reputation: 5 455

Holy bananas! – Cruncher – 2014-02-20T21:17:28.673

3@Cruncher that would be † )) ! in APL. – Tobia – 2014-02-20T22:44:27.497

Bravo. I think that we have a winner. – Victor Stafusa – 2014-02-21T02:15:21.170

Simply amazing. Hats off to you. – DavidC – 2014-02-21T04:22:50.523

Mathematica 43 28

Second try

My first attempt was not correct, although it did have some of the necessary ingredients (LCM,Rationalize). The complete solution requires taking into account both the numerator and denominator of each frequency (expressed as a common fraction).

l is the list of frequencies.

Rationalizing 2.35 converts it to the common fraction 235/100.

f@l_:=LCM@@(1/Rationalize@l)

Assume that all GIFs fire at t=0.

The following approach does not require that the frequencies be expressed as "real numbers", ie. as decimal fractions. They may be other sort of fractions. The example below is a case where the fractions are in fifths, thirds, hundredths and sevenths.

If two or more frequencies are incommensurate (in which case at least one must be an irrational number) then there is no solution. In other words, there will be no point in time, t>0, at which all components fire at the same time.

Example1

f[{50, 10}]

1/10

Example 2

f[{16/5, 2/3, 2.35, 1/7}]

420

If we multiply the least overall period by each of the frequencies, we find a whole number of cycles in each case:

420*{16/5, 2/3, 2.35, 1/7}

{1344, 280, 987., 60}

(1344 hops of 16/5 units) lands at 420. (280 hops of 2/3 units) lands at 420. (987 hops of 2.35 units) lands at 420. (60 hops of 7 units) lands at 420.

DavidC

Posted 2014-02-19T21:08:08.107

Reputation: 24 524

The right tool for the right job. – Victor Stafusa – 2014-02-20T01:33:54.250

I am not sure I understand. If the inputs are frequencies, the f[{50,10}] would mean the common cycle of signal that fires 50 times per second and a cycle that files 10 times per second? The correct answer would be 1/10 of a second, but f[{50, 10}] returns 1. Actually, lots of random things return an answer of 1. f[{345345, h}] returns 1. – Michael Stern – 2014-02-20T02:27:58.490

My original approach was incomplete (and therefore incorrect). I've amended it in such a way as to address your observation. The current solution also makes sense geometrically (using line segments against the real line). – DavidC – 2014-02-20T03:23:53.047

I was coming to post just such a solution, but you beat me to it. Very nice. – Jonathan Van Matre – 2014-02-20T03:42:54.120

@Jonathan. Yes, your approach was almost identical to mine. But I don't see the need for Round. Won't Rationalize and LCM guarantee that the results be integers? – DavidC – 2014-02-20T03:56:01.377

Yep, the way you did it Round becomes unnecessary. – Jonathan Van Matre – 2014-02-20T04:05:34.887

Let's see the golfscript and APL aficionados try to beat this! – Michael Stern – 2014-02-20T10:41:14.873

@MichaelStern Never underestimate APL! Marinus' solution, among the Javascript comments, weighs in at 27 chars. – DavidC – 2014-02-20T13:47:47.533

Javascript: 191 characters

The input format that I chose (within the rules) is the frequency numbers separated by commas. No spaces allowed and no newlines. The initial N must not be given. Each number must be just a serie of at least one [0-9] digits with an optional dot somewhere within. If the input is malformed, the behaviour is undefined.

How it works:

The period of some integer frequency numbers is the GCD of these numbers. If the given numbers are not integer, it sucessively multiplies they by 10 until it gets everything as an integer number (this exploit the fact that the non-integer numbers are given in base 10). After calculating the GCD, it divides the result by the power of ten used to multiply the input numbers, and hence getting the overall frequency. Inverting this we get the period.
Note: I am pretty sure that now that I gave this answer, somebody will code the same in APL or J and beat it. :(

The code:

d=1,s=prompt().split(",");for(a in s){s[a]=parseFloat(s[a]);while(s[a]*d%1>0)d*=10}g=s[0]*d;for(a in s){u=g;v=s[a]*=d;p=2;q=1;while(u>=p&v>=p)if(u%p|v%p)p++;else{u/=p;v/=p;q*=p}g=q}alert(d/g)

Testing it:

Input: 50,10
Output: 0.1
Interpretation: One GIF blinks 10 times per second (period = 0.1s) and the other 50 times (period = 0.02s). So a combined GIF would repeat itself in 0.1 seconds.

Input: 2.7,3.4
Output: 10
Interpretation: One blinking at 2.7 times per second will blink 27 times in 10 seconds. One blinking 3.4 times per second will blink 34 times in 10 seconds. So, 10 seconds is a period, and since GCD(27,34)=1, it is the smallest.

Input: 4.8,7.2
Output: 0.4166666666666667
Interpretation: One blinking at 4.8 times per second and the other at 7.2 times per second, gives a frequency of 2.4 times per second, which is a period 0.41666... seconds.

Input: 0.6,12,7.9,4.33
Output: 100
Interpretation: Similar to second case. 60, 1200, 790 and 433 times each 100 seconds. The GCD of these numbers is 1.

Input: 400,200,25,350
Output: 0.04
Interpretation: The slowest is the 25 times per second, which is the overall frequency. 25 times per second is a period of 0.04 seconds.

Input: 440,200,35,360
Output: 0.2
Interpretation: In 0.2 seconds, we have 88, 40, 7 and 72 blinks.

Victor Stafusa

Posted 2014-02-19T21:08:08.107

Reputation: 8 612

GCD? That's the greatest common divisor, so it would always be smaller than the frequencies. I think you mean LCM (least common multiple). – Justin – 2014-02-20T01:08:17.937

@Quincunx No, it is the GCD. The total period is the LCM of the individual periods, not individual frequencies. – Victor Stafusa – 2014-02-20T01:23:05.220

1Here's the APL: (⊃x÷z)×∨/z←{⍵×10}⍣{⍵≡⌈⍵}x←⎕ – marinus – 2014-02-20T01:40:02.487

Would you run a test case with rational numbers or "real numbers" (in the computer science sense of the term)? I don't think an approach based on GCD will work. – DavidC – 2014-02-20T01:43:31.673

@DavidCarraher I messed frequency with period, but now I already fixed. Just changed the g/d to d/g. I will add some test cases. – Victor Stafusa – 2014-02-20T01:50:40.303

@marinus Go on and post it. :) (but insert a link in your answer to this one). – Victor Stafusa – 2014-02-20T01:51:21.387

@DavidCarraher Done, I added some test cases. – Victor Stafusa – 2014-02-20T02:12:30.600

I think an improvement would be multiply by two. Since these are all expressed in what is effectively "binary scientific notation" (i.e. floating-point), the multiple you are looking for is 2^n, for some n. – Malvolio – 2014-02-21T02:09:52.383

Find the overall period from a list of frequencies

Answers

APL, 4

Mathematica 43 28

Second try

Javascript: 191 characters