8
\$\begingroup\$

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:

P

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!

\$\endgroup\$
7
  • \$\begingroup\$ Possible spoiler... wouldn't this just be the product of the given frequencies? \$\endgroup\$ – danmcardle Feb 19 '14 at 23:50
  • \$\begingroup\$ @crazedgremlin No it isn't, but you are pretty close. \$\endgroup\$ – Victor Stafusa Feb 20 '14 at 0:30
  • \$\begingroup\$ @crazedgremlin - If A is 2s and B is 4s, then the resulting period would be 4s, not 8s. \$\endgroup\$ – Digital Trauma Feb 20 '14 at 0:36
  • \$\begingroup\$ 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. \$\endgroup\$ – danmcardle Feb 20 '14 at 0:41
  • \$\begingroup\$ 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. \$\endgroup\$ – Victor Stafusa Feb 20 '14 at 2:20
8
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ Holy bananas! \$\endgroup\$ – Cruncher Feb 20 '14 at 21:17
  • 3
    \$\begingroup\$ @Cruncher that would be † )) ! in APL. \$\endgroup\$ – Tobia Feb 20 '14 at 22:44
  • \$\begingroup\$ Bravo. I think that we have a winner. \$\endgroup\$ – Victor Stafusa Feb 21 '14 at 2:15
  • \$\begingroup\$ Simply amazing. Hats off to you. \$\endgroup\$ – DavidC Feb 21 '14 at 4:22
4
\$\begingroup\$

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.

\$\endgroup\$
8
  • \$\begingroup\$ The right tool for the right job. \$\endgroup\$ – Victor Stafusa Feb 20 '14 at 1:33
  • \$\begingroup\$ 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. \$\endgroup\$ – Michael Stern Feb 20 '14 at 2:27
  • \$\begingroup\$ 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). \$\endgroup\$ – DavidC Feb 20 '14 at 3:23
  • \$\begingroup\$ I was coming to post just such a solution, but you beat me to it. Very nice. \$\endgroup\$ – Jonathan Van Matre Feb 20 '14 at 3:42
  • \$\begingroup\$ @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? \$\endgroup\$ – DavidC Feb 20 '14 at 3:56
2
\$\begingroup\$

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.
\$\endgroup\$
8
  • \$\begingroup\$ GCD? That's the greatest common divisor, so it would always be smaller than the frequencies. I think you mean LCM (least common multiple). \$\endgroup\$ – Justin Feb 20 '14 at 1:08
  • \$\begingroup\$ @Quincunx No, it is the GCD. The total period is the LCM of the individual periods, not individual frequencies. \$\endgroup\$ – Victor Stafusa Feb 20 '14 at 1:23
  • 1
    \$\begingroup\$ Here's the APL: (⊃x÷z)×∨/z←{⍵×10}⍣{⍵≡⌈⍵}x←⎕ \$\endgroup\$ – marinus Feb 20 '14 at 1:40
  • \$\begingroup\$ 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. \$\endgroup\$ – DavidC Feb 20 '14 at 1:43
  • \$\begingroup\$ @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. \$\endgroup\$ – Victor Stafusa Feb 20 '14 at 1:50

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.