5
\$\begingroup\$

Input

Two non-negative floating point numbers \$x < y\$. You can assume they are close enough to each other that there is no integer between \$x\$ and \$y\$.

Output

A fraction with the smallest possible denomination that lies strictly between \$x\$ and \$y\$.

Examples

Input: 1 and 2

Output: 3/2

Input: 0 and 0.33

Output: 1/4

Input: 0.4035 and 0.4036

Output: 23/57

\$\endgroup\$
4
  • 1
    \$\begingroup\$ How do we deal with float imprecision? Say we're given the float representing 1/3 which actually equals 0.3333333333333333148..., is the fraction 1/3 greater than that? \$\endgroup\$
    – xnor
    Commented Jan 12 at 22:00
  • \$\begingroup\$ @xnor The input is a float so if it just has 3s in its decimal expansion, it is less than 1/3. Is this going to cause a difficulty? \$\endgroup\$
    – Simd
    Commented Jan 12 at 22:02
  • 1
    \$\begingroup\$ I'm pretty sure this is a duplicate, but I can't find the original. \$\endgroup\$
    – Wheat Wizard
    Commented Jan 12 at 23:37
  • 5
    \$\begingroup\$ @WheatWizard Are you thinking of In between fractions? The only difference in that challenge is that \$x\$ and \$y\$ are fractions instead of floats. \$\endgroup\$
    – Dingus
    Commented Jan 13 at 2:00

6 Answers 6

3
\$\begingroup\$

JavaScript (Node.js), 42 bytes

x=>g=(y,d)=>(p=-~(x*d))<y*d?[p,d]:g(y,-~d)

Try it online!

If \$ \left \lfloor xd \right \rfloor +1 < yd \$, then \$ \left \lfloor xd \right \rfloor +1 \$ is an answer

\$\endgroup\$
1
  • \$\begingroup\$ Which is fortunate since ⌈xd⌉<yd is the wrong test. \$\endgroup\$
    – Neil
    Commented Jan 12 at 23:49
2
\$\begingroup\$

JavaScript (ES6), 47 bytes

Expects (x)(y), returns [numerator, denominator].

(x,p=q=1)=>g=y=>p<y*q++&&p++>x*--q?[--p,q]:g(y)

Try it online!

Commented

( x,          // x = first number
  p =         // p = numerator
  q = 1       // q = denominator
) =>          //
g = y =>      // y = second number
p < y * q++   // we test whether p/q < y
              // and increment q afterwards in case it's not
&&            // if truthy,
p++ > x * --q // we restore q, test whether p/q > x
              // and increment p afterwards in case it's not
?             // if truthy again:
  [--p, q]    //   we restore p and return [p, q]
:             // else:
  g(y)        //   we try again with either p or q incremented
\$\endgroup\$
2
  • \$\begingroup\$ But how does it work? \$\endgroup\$
    – Simd
    Commented Jan 12 at 22:37
  • \$\begingroup\$ @Simd I've added a commented version. This is a really simple algorithm, but written in a slightly convoluted way. \$\endgroup\$
    – Arnauld
    Commented Jan 12 at 22:56
2
\$\begingroup\$

Charcoal, 33 bytes

NθNη≔⌕E⁺²∕¹⁻ηθ⁻⌈×ηι⌊×θι²ζI⟦⊖⌈×ηζζ

Try it online! Link is to verbose version of code. Explanation:

NθNη

Input x and y.

≔⌕E⁺²∕¹⁻ηθ⁻⌈×ηι⌊×θι²ζ

Find d such that ⌈yd⌉-⌊xd⌋=2. d is never more than ⌊1+1/(y-x)⌋, but I have to add 2 due to 0-indexing.

I⟦⊖⌈×ηζζ

Output ⌈yd⌉-1 and d.

\$\endgroup\$
2
\$\begingroup\$

Jelly, 18 bytes

×ḞĊƭ€r/ḊṖ
1ç1#Ḣṭç¥

Try it online!

A pair of links which is called as a monad with a pair of floats and returns a pair of [numerator, denominator].

Explanation

×ḞĊƭ€r/ḊṖ | Helper link: takes a denominator as the left argument and a pair of floats as the right and returns a valid numerator, if any
×         | Multiply (denominator with floats)
 ḞĊƭ€     | Floor first, ceiling second
     r/   | Reduce using range
       ḊṖ | Remove first and last

1ç1#Ḣṭç¥ | Main link
1ç1#     | Starting with one, find first denominator where there’s a valid numerator (will be wrapped in a list)
    Ḣ    | Head (to unwrap the list)
     ṭç¥ | Tag this onto the result of  running the helper link again to find the numerator
```
\$\endgroup\$
1
\$\begingroup\$

Python 2, 95 bytes

(a,b),(c,d)=[input().as_integer_ratio()for m in 0,0]
while(m*d/c+1)*a>=m*b:m+=1
print m,m*d/c+1

Try it online!

Not a math guy, basically uses the formula of this answer.

The input should be in decimal format: 1.0 instead of just 1.

-2 bytes: replace // with /

-4 bytes: inlining m

\$\endgroup\$
1
\$\begingroup\$

R, 47 bytes

\(x,y){while((p=(x*F)%/%1+1)>=y*F)F=F+1
c(p,F)}

Attempt This Online!

Port of @l4m2's JavaScript answer.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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