Generalized FiveThirtyEight Sequences

dylnan 12/09/2017. 11 answers, 1.320 views
code-golf number sequence

Adapted from this FiveThirtyEight riddle.

Background

Examine the following infinite sequence:

3 3 3 2 3 3 3 2 3 3 3 2 3 3 2 3 3 3 2 ...

Let's say the sequence is 1-indexed. The ith number in the sequence determines how many 3s there are before the ith 2 and following any previous 2s. So since the sequence starts with a 3 the sequence must begin 3 3 3 2 and since there are three 3s at the beginning of the sequence the subsequence 3 3 3 2 must repeat itself three times. After that you reach 3 3 2 because the fourth number in the sequence is 2.

The FiveThirtyEight riddle asks for the limit of the ratios of threes to twos (which I won't spoil here) but you can also ask what the cumulative ratio is after index i. For example the ratio at i=4 is 3/1 = 3 and at i=15 it's 11/4 = 2.75.

Let's get general

Given numbers n and k we can make a similar sequence that starts with n and just like the original sequence described the number at index i determines how many ns show up before the ith k and following any previous ks.

Examples:

n=2, k=5 gives the sequence 2 2 5 2 2 5 2 2 2 2 2 5 2 2 5 ...

n=3, k=0 gives 3 3 3 0 3 3 3 0 3 3 3 0 0 3 3 3 0 ...

n=1, k=3 gives 1 3 1 1 1 3 1 3 1 3 1 3 1 1 1 3 1 ...

The Challenge

Write a function/program and with it do the following. Take as input:

  • a positive integer n
  • a nonnegative integer k ≠ n
  • a positive integer i > n

The first two inputs n and k determine a sequence as described above and i is an index. I am using 1-indexing in the examples but you have the freedom to use 0- or 1-indexing. If 0-indexed then the restriction on i is i ≥ n.

With the three numbers output the ratio of ns to ks in the sequence up to and including the number at the index i. The format of the output can either be a decimal value with at least 5 digits of precision or an exact value as a ratio like 3524/837 or 3524:837.

In decimal form, the last digit can be rounded however you like. Trailing zeros and whitespace are allowed.

In either of the string forms the two numbers need to be normalized so that they are coprime. For example if the ratio was 22/4, 11/2 and 11:2 are acceptable but 22/4 is not.

Examples

n   k   i      output
2   4   15     2.75     or   11/4
6   0   666    5.1101   or   557:109
50  89  64     63       or   63:1
3   2   1000   2.7453   or   733/267
9   12  345    9.4545   or   104/11

This is code golf per language, so shortest code in each language is the winner.

5 Comments
2 dylnan 12/09/2017
@JonathanAllan Yes I do actually mean that, thanks. What's the point of the sandbox if no one reads it and waits for actual posts to make these comments?
1 dylnan 12/10/2017
@JonathanAllan I'm going to require an actual ratio, not just the pair of numerator, denominator. But I did see your Jelly answer and it's only 3 extra bytes at most to get it to an acceptable format
3 J42161217 12/10/2017
I think OP is clear "the two numbers need to be normalized so that they are coprime"
2 J42161217 12/10/2017
@JonathanAllan just look at the last test case: the pair [312,33] is not right because it can be normalized to [104,11].Your first code would output [312,33]

11 Answers


Zgarb 12/10/2017.

Husk, 16 bytes

¤/#ωȯ↑⁰J¹`C∞²N¹²

Try it online!

Takes inputs in the same order as the test cases. Outputs a rational number. I feel like this has too many superscripts, but I don't know how to get rid of them...

Explanation

¤/#ωȯ↑⁰J¹`C∞²N¹²  Inputs are n, k, i.
             N    Starting with the natural numbers [1,2,3..
   ωȯ             do this until a fixed point is reached:
                    Argument is a list s.
           ∞²       Take the infinite list [n,n,n..
         `C         and split it to the lengths in s.
       J¹           Join the resulting blocks with k.
     ↑⁰             Take the first i elements.
                  Call the result x.
¤             ¹²  For each of n and k,
  #               count their number of occurrences in x
 /                and perform exact division on the results.

Neil 12/10/2017.

Python 3, 94 92 89 87 bytes

def g(n,k,i):o,t=[n],0;exec('o+=[n]*o[t]+[k];t+=1;'*i);return-1-i/(o[1:i+1].count(n)-i)

Try it online!

Credits

  • Reduced from 94 to 92 bytes: Colera Su.
  • Reduced from 92 to 89 bytes: dylnan.
  • Reduced from 89 to 87 bytes: ovs.
5 comments
Colera Su 12/10/2017
Shouldn't it be .count(n)?
Neil 12/10/2017
@ColeraSu Thanks. Don't know how I missed that, fixed.
Colera Su 12/10/2017
Neil 12/10/2017
@ColeraSu Thanks, updated. I'll try to start using exec's. That's pretty cool.
dylnan 12/10/2017

Erik the Outgolfer 12/10/2017.

Jelly, 22 bytes

³ẋЀ;€⁴Ẏḣ⁵
ẋ`;ÇÐLLƙ`÷/

Try it online!

Full program. Takes arguments n, k, i.

There's a bug that makes this need to be unnecessarily longer by 1 byte.

2 comments
Jonathan Allan 12/10/2017
Used some of your tricks - nice. Wondering about what the correct fix for the bug should really be...
Erik the Outgolfer 12/10/2017
@JonathanAllan What struck me is this line, although not sure why putting a ` makes it work. Oh, and where your answer differs is that I forgot to implement a golf I found in another language >_>

Jonathan Allan 12/10/2017.

Jelly,  25  16 bytes

-9 bytes ~50% attributable to Erik the Outgolfer's Jelly answer (1. using the new-ish key quick ƙ even with a bug in the interpreter currently costing a byte; 2. using a mapped repetition to avoid counting and indexing into the current sequence.) Go give him some credit!

³ẋЀj⁴ṁ⁵µÐLLƙ`÷/

A full program taking three arguments: n, k, i which prints the result.

Try it online!

How?

³ẋЀj⁴ṁ⁵µÐLLƙ`÷/ - Main link
        µ        - monadic chain separation
         ÐL      - apply the monadic chain to the left repeatedly until no change occurs:
³                -   program's 1st argument, n
  Ѐ             -   map across the current sequence (initially just n)
 ẋ               -     repeat (the first run give triangle of n i.e. [[n],[n,n],...,[n]*n]
     ⁴           -     program's 2nd argument, k
    j            -     join
       ⁵         -     program's 3rd argument, i
      ṁ          -     mould like (repeat the list to fill, or cut it, to length i)
            ƙ    - keyed application, map over groups of identical items:
             `   - (this has an arity of 2, make it monadic by repeating the argument)
           L     -   length -> [numberOfNs, numberOfKs]
               / - reduce with:
              ÷  -   division -> [numberOfNs / numberOfKs]
                 - implicit print (a single item list just prints its content)

example run with inputs n=2, k=3, i=30:

Start the "loop until no change", ÐL
Note: Initial left argument, n=2, implicitly range-ified by Ѐ to become [1,2]
1. mapped repeat of n: [[2],[2,2]]
          join with k: [2,3,2,2]
         mould like i: [2,3,2,2,2,3,2,2,2,3,2,2,2,3,2,2,2,3,2,2,2,3,2,2,2,3,2,2,2,3]

2. mapped repeat of n: [[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2]]
          join with k: [2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2]
         mould like i: [2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2]
                          ^different to previous result

3. mapped repeat of n: [[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2]]
          join with k: [2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2]
         mould like i: [2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2]
                                  ^different to previous result

4. mapped repeat of n: [[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2]]
          join with k: [2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2]
         mould like i: [2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2]
                                                      ^different to previous result

5. mapped repeat of n: [[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2],[2,2],[2,2,2],[2,2]]
          join with k: [2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2]
         mould like i: [2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,2,3,2,2,3,2,2,3,2,2,3,2]
                       all the same as the previous result; stop loop and yield this.

length applied to equal elements: [length([2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]), length([3,3,3,3,3,3,3,3,3])]
                                = [21,9]
reduce by division              = [21/9] = [2.3333333333333335]
implicit print                  2.3333333333333335

J42161217 12/10/2017.

Mathematica, 85 bytes

(s={#};Do[s=Join[s,#~Table~s[[t]],{#2}],{t,#3}];Last@@Ratios@Tally@s[[#+3;;#3+#+2]])&

Try it online!


J. Sallé 12/14/2017.

APL (Dyalog Unicode), 126 70 bytes

k n i←⎕
j←⍴v←⍬
:While j<i
v,←k,⍨n⍴⍨{v≢⍬:j⊃v⋄n}j+←1
:End
÷/+/¨n k⍷¨⊂j⍴v

Try it online!

Well, thanks to @Adám for obliterating 56 bytes out of this answer.

This is a niladic Tradfn (traditional function) taking 1 input, which is a 3 element list.

⎕PP←5 is not added to the byte count because it's only used to limit the Print Precision to 5 digits.

∇f and are not added to the byte count because they're not part of the code, only delimiters for the tradfn.

How it Works:

k n i←⎕                   ⍝ Take input (←⎕) for k, n and i.
j←⍴v←⍬                    ⍝ Assign (←) an empty vector (⍬) to v, then assign its shape (⍴, which is 0) to j.
:While j<i                ⍝ while j<i, do:
v,←k,⍨n⍴⍨{v≢⍬:j⊃v⋄n}j+←1 ⍝ this:
                     j+←1 ⍝ increment j (+←1)
          {v≢⍬:     }     ⍝ if (:) v does not match (≢) ⍬
               j⊃v        ⍝ return the jth element of v (v[j])
                  ⋄n      ⍝ else (⋄) return n
      n⍴⍨                 ⍝ shape (⍴) n as the result (repeats n result times)
   k,⍨                    ⍝ append (,⍨) k
v,←                       ⍝ append to (,←) v
:End                      ⍝ End while loop
÷/+/¨n k⍷¨⊂j⍴v            ⍝ then:
           j⍴v            ⍝ shape (⍴) v as j (truncates v to j elements)
          ⊂               ⍝ enclose the resulting vector
         ¨                ⍝ for each element
        ⍷                 ⍝ find (returns a boolean vector)
     n k                  ⍝ n and k (⍷ will return a boolean vector for each)
  +/¨                     ⍝ cumulative sum of each vector (returns the number of times n and k appear in v)
÷/                        ⍝ divide them and implicitly return the result.

duckmayr 12/10/2017.

R, 88 bytes

function(n,k,i){s=rep(n,n);for(j in 1:i){s=c(s,k,rep(n,s[j]))};z=sum(s[1:i]==n);z/(i-z)}

Try it online!

1 comments
Giuseppe 12/13/2017
you can get rid of the braces around the for loop body as there's only one statement.

Herman Lauenstein 12/10/2017.

Swift, 152 bytes

func f(n:Int,k:Int,i:Int){var a=[0];(1...i).map{a+=(0..<(a.count>$0 ?a[$0]:n)).map{_ in n}+[k]};let m=a[1...i].filter{n==$0}.count;print("\(m)/\(i-m)")}

Will it be shorter than Java?

Explanation

func f(n:Int,k:Int,i:Int){
  var a=[0]                                    // Initialize the array (the zero is to
                                               //  define the type of the array and will be
                                               //  ignored by the code)
  (1...i).map{                                 // Repeat i times (more than enough):
    a+=(0..<(a.count>$0 ?a[$0]:n)).map{_ in n} //  Add the right amount of n:s to the array
      +[k]                                     //  Add k to the array
  }                                            // End repeat
  let m=a[1...i].filter{n==$0}.count           // Count the amount of n:s in the first
                                               //  i elements of the array
  print("\(m)/\(i-m)")                         // Print the result
}

iamnotmaynard 12/10/2017.

Ruby, 77 71 70 bytes

->n,k,i{r=[n]
i.times{|c|r+=[n]*r[c]+[k]}
1r*(j=r[1,i].count n)/(i-j)}

Try it online!

Returns a Rational, which both operates as a number and stringifies to the exact reduced fraction.


Leaky Nun 12/13/2017.

Pyth, 24 bytes

AEtcH/e.u<sm+*d]QGNH]Q)G

Test suite.

Fixed point of [n] under certain function of array.


DLosc 12/14/2017.

Zephyr, 284 bytes

input n as Integer
input k as Integer
input m as Integer
set s to Array(m)
for i from 1 to n
set s[i]to n
next
set s[i]to k
set N to n
set K to 1
for a from 2 to m
for b from 1 to s[a]
inc i
if i<=m
set s[i]to n
inc N
end if
next
inc i
if i<=m
set s[i]to k
inc K
end if
next
print N/K

Takes the three numbers from stdin on three separate lines. Outputs an exact ratio such as 104/11 or 63.

Ungolfed

input n as Integer
input k as Integer
input maxIndex as Integer

set sequence to Array(maxIndex)
for i from 1 to n
    set sequence[i] to n
next
set sequence[i] to k

set nCount to n
set kCount to 1

for a from 2 to maxIndex
    for b from 1 to sequence[a]
        inc i
        if i <= maxIndex
            set sequence[i] to n
            inc nCount
        end if
    next
    inc i
    if i <= maxIndex
        set sequence[i] to k
        inc kCount
    end if
next

print nCount / kCount

Related questions

Hot questions

Language

Popular Tags