17
\$\begingroup\$

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.

|improve this question
\$\endgroup\$
  • \$\begingroup\$ Related. Related. \$\endgroup\$ – Martin Ender Dec 9 '17 at 23:11
  • \$\begingroup\$ I recommend allowing a pair of integers as a ratio, needing answerers to separate the numbers with / or : just adds an unnecessary complication to the challenge. \$\endgroup\$ – Erik the Outgolfer Dec 10 '17 at 9:24
  • \$\begingroup\$ @EriktheOutgolfer a decimal number is allowed too \$\endgroup\$ – dylnan Dec 10 '17 at 13:29
  • \$\begingroup\$ Is a standard float exact enough for the decimal output? \$\endgroup\$ – iamnotmaynard Dec 10 '17 at 14:48
  • \$\begingroup\$ @iamnotmaynard I’m not strict about the float format so yes I think so \$\endgroup\$ – dylnan Dec 10 '17 at 15:06

11 Answers 11

5
\$\begingroup\$

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.
|improve this answer
\$\endgroup\$
4
\$\begingroup\$

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.
|improve this answer
\$\endgroup\$
  • \$\begingroup\$ Shouldn't it be .count(n)? \$\endgroup\$ – Colera Su Dec 10 '17 at 3:46
  • \$\begingroup\$ @ColeraSu Thanks. Don't know how I missed that, fixed. \$\endgroup\$ – Neil Dec 10 '17 at 3:47
  • \$\begingroup\$ 92 bytes. \$\endgroup\$ – Colera Su Dec 10 '17 at 3:52
  • \$\begingroup\$ @ColeraSu Thanks, updated. I'll try to start using exec's. That's pretty cool. \$\endgroup\$ – Neil Dec 10 '17 at 3:54
  • \$\begingroup\$ 89 bytes \$\endgroup\$ – dylnan Dec 10 '17 at 3:56
4
\$\begingroup\$

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.

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ Used some of your tricks - nice. Wondering about what the correct fix for the bug should really be... \$\endgroup\$ – Jonathan Allan Dec 10 '17 at 13:02
  • \$\begingroup\$ @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 >_> \$\endgroup\$ – Erik the Outgolfer Dec 10 '17 at 13:13
4
\$\begingroup\$

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
|improve this answer
\$\endgroup\$
3
\$\begingroup\$

Mathematica, 85 bytes

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

Try it online!

|improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.
|improve this answer
\$\endgroup\$
1
\$\begingroup\$

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!

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ you can get rid of the braces around the for loop body as there's only one statement. \$\endgroup\$ – Giuseppe Dec 13 '17 at 21:47
0
\$\begingroup\$

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
}
|improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

|improve this answer
\$\endgroup\$
0
\$\begingroup\$

Pyth, 24 bytes

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

Test suite.

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

|improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
|improve this answer
\$\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.